| 2150 |
mathias |
1 |
<html>
|
|
|
2 |
<head>
|
|
|
3 |
<title>Compress colors using VQ</title>
|
|
|
4 |
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
|
|
|
5 |
<style type="text/css">
|
|
|
6 |
@import "../../../dojo/resources/dojo.css";
|
|
|
7 |
@import "../../../dijit/tests/css/dijitTests.css";
|
|
|
8 |
|
|
|
9 |
.pane { margin-top: 2em; }
|
|
|
10 |
</style>
|
|
|
11 |
<script type="text/javascript" src="../../../dojo/dojo.js" djConfig="isDebug: true"></script>
|
|
|
12 |
<script type="text/javascript">
|
|
|
13 |
dojo.require("dojox.encoding.tests.colors");
|
|
|
14 |
dojo.require("dojox.encoding.splay");
|
|
|
15 |
dojo.require("dojox.encoding.bits");
|
|
|
16 |
|
|
|
17 |
var colors = dojox.encoding.tests.colors;
|
|
|
18 |
|
|
|
19 |
var dist = function(a, b){
|
|
|
20 |
var r = a[0] - b[0], g = a[1] - b[1], b = a[2] - b[2];
|
|
|
21 |
return r * r + g * g + b * b;
|
|
|
22 |
};
|
|
|
23 |
|
|
|
24 |
var hexcolor = function(c){
|
|
|
25 |
return "#" + (c[0] < 16 ? "0" : "") + c[0].toString(16) +
|
|
|
26 |
(c[1] < 16 ? "0" : "") + c[1].toString(16) +
|
|
|
27 |
(c[2] < 16 ? "0" : "") + c[2].toString(16);
|
|
|
28 |
};
|
|
|
29 |
|
|
|
30 |
var maxdist = function(a, b, maxdist){
|
|
|
31 |
var r = Math.abs(a[0] - b[0]), g = Math.abs(a[1] - b[1]), b = Math.abs(a[2] - b[2]);
|
|
|
32 |
++maxdist[bits(r)];
|
|
|
33 |
++maxdist[bits(g)];
|
|
|
34 |
++maxdist[bits(b)];
|
|
|
35 |
};
|
|
|
36 |
|
|
|
37 |
var encodeColor = function(a, b, splay, stream){
|
|
|
38 |
var r = a[0] - b[0], g = a[1] - b[1], b = a[2] - b[2];
|
|
|
39 |
stream.putBits(r < 0 ? 1 : 0, 1);
|
|
|
40 |
splay.encode(Math.abs(r), stream);
|
|
|
41 |
stream.putBits(g < 0 ? 1 : 0, 1);
|
|
|
42 |
splay.encode(Math.abs(g), stream);
|
|
|
43 |
stream.putBits(b < 0 ? 1 : 0, 1);
|
|
|
44 |
splay.encode(Math.abs(b), stream);
|
|
|
45 |
};
|
|
|
46 |
|
|
|
47 |
var bits = function(x){
|
|
|
48 |
var w = 1;
|
|
|
49 |
for(var v = 2; x >= v; v <<= 1, ++w);
|
|
|
50 |
return w;
|
|
|
51 |
};
|
|
|
52 |
|
|
|
53 |
var runVQ = function(n){
|
|
|
54 |
dojo.byId("status").innerHTML = "<em>Initializing...</em>";
|
|
|
55 |
dojo.byId("report").innerHTML = "<em>Running VQ...</em>";
|
|
|
56 |
var clusters = [];
|
|
|
57 |
// select initial cluster centers
|
|
|
58 |
var empty = {};
|
|
|
59 |
for(var i in colors){
|
|
|
60 |
if(i in empty){ continue; }
|
|
|
61 |
clusters.push({center: colors[i]});
|
|
|
62 |
if(clusters.length == n){ break; }
|
|
|
63 |
}
|
|
|
64 |
/*
|
|
|
65 |
for(var i = 0; i < n; ++i){
|
|
|
66 |
var r = Math.floor(Math.random() * 256), g = Math.floor(Math.random() * 256), b = Math.floor(Math.random() * 256);
|
|
|
67 |
clusters.push({center: [r, g, b]});
|
|
|
68 |
}
|
|
|
69 |
*/
|
|
|
70 |
// do runs
|
|
|
71 |
dojo.byId("status").innerHTML = "<div>Starting runs...</div>";
|
|
|
72 |
var jitter = 0, niter = 1;
|
|
|
73 |
do {
|
|
|
74 |
// save previous centers
|
|
|
75 |
var old_clusters = [];
|
|
|
76 |
dojo.forEach(clusters, function(c){ old_clusters.push({center: c.center}); c.members = []; });
|
|
|
77 |
// assign colors to clusters
|
|
|
78 |
for(var i in colors){
|
|
|
79 |
if(i in empty){ continue; }
|
|
|
80 |
var c = colors[i], k = -1, kd = Number.MAX_VALUE;
|
|
|
81 |
for(var j = 0; j < clusters.length; ++j){
|
|
|
82 |
var jd = dist(clusters[j].center, c);
|
|
|
83 |
if(jd < kd){ k = j, kd = jd; }
|
|
|
84 |
}
|
|
|
85 |
clusters[k].members.push(i);
|
|
|
86 |
}
|
|
|
87 |
// recalculate cluster centers
|
|
|
88 |
for(var i = 0; i < clusters.length; ++i){
|
|
|
89 |
if(!clusters[i].members.length){ continue; }
|
|
|
90 |
var r = 0, g = 0, b = 0;
|
|
|
91 |
dojo.forEach(clusters[i].members, function(name){
|
|
|
92 |
var c = colors[name];
|
|
|
93 |
r += c[0];
|
|
|
94 |
g += c[1];
|
|
|
95 |
b += c[2];
|
|
|
96 |
});
|
|
|
97 |
r = Math.round(r / clusters[i].members.length);
|
|
|
98 |
g = Math.round(g / clusters[i].members.length);
|
|
|
99 |
b = Math.round(b / clusters[i].members.length);
|
|
|
100 |
clusters[i].center = [r, g, b];
|
|
|
101 |
}
|
|
|
102 |
// calculate the jitter
|
|
|
103 |
jitter = 0;
|
|
|
104 |
for(var i = 0; i < clusters.length; ++i){
|
|
|
105 |
jitter = Math.max(jitter, dist(clusters[i].center, old_clusters[i].center));
|
|
|
106 |
}
|
|
|
107 |
var node = dojo.doc.createElement("div");
|
|
|
108 |
node.innerHTML = "Run #" + niter + ", jitter = " + jitter;
|
|
|
109 |
dojo.byId("status").appendChild(node);
|
|
|
110 |
++niter;
|
|
|
111 |
}while(jitter > 1 && niter < 1000);
|
|
|
112 |
// calculate the required number of bytes
|
|
|
113 |
var output = new dojox.encoding.bits.OutputStream(),
|
|
|
114 |
splay = new dojox.encoding.Splay(256);
|
|
|
115 |
for(var i = 0; i < clusters.length; ++i){
|
|
|
116 |
var c = clusters[i], m = c.members, d = 0, ol = output.getWidth();
|
|
|
117 |
output.putBits(c.center[0], 8);
|
|
|
118 |
output.putBits(c.center[1], 8);
|
|
|
119 |
output.putBits(c.center[2], 8);
|
|
|
120 |
splay.init();
|
|
|
121 |
c.maxdist = [0, 0, 0, 0, 0, 0, 0, 0, 0];
|
|
|
122 |
for(var j = 0; j < m.length; ++j){
|
|
|
123 |
var color = colors[m[j]];
|
|
|
124 |
maxdist(c.center, color, c.maxdist);
|
|
|
125 |
encodeColor(c.center, color, splay, output);
|
|
|
126 |
}
|
|
|
127 |
c.bits = output.getWidth() - ol;
|
|
|
128 |
}
|
|
|
129 |
var node = dojo.doc.createElement("div");
|
|
|
130 |
node.innerHTML = "Required " + Math.ceil(output.getWidth() / 8) + " bytes";
|
|
|
131 |
dojo.byId("status").appendChild(node);
|
|
|
132 |
// generate color tables
|
|
|
133 |
var reps = [];
|
|
|
134 |
for(var i = 0; i < clusters.length; ++i){
|
|
|
135 |
var c = clusters[i], m = c.members;
|
|
|
136 |
reps.push("<p>Cluster #" + i + " contains " + m.length + " members. Length histogram:");
|
|
|
137 |
for(var j = 0; j < c.maxdist.length; ++j){
|
|
|
138 |
if(c.maxdist[j]){
|
|
|
139 |
reps.push(" " + j + "—" + c.maxdist[j]);
|
|
|
140 |
}
|
|
|
141 |
}
|
|
|
142 |
reps.push(". It requires " + c.bits + " bits (" + Math.ceil(c.bits / 8) + " bytes) to be encoded.</p>");
|
|
|
143 |
reps.push("<table>");
|
|
|
144 |
var wd = dist([255,255,255], c.center), bd = dist([0,0,0], c.center);
|
|
|
145 |
reps.push("<tr><td style='background: " + hexcolor(c.center) + "; color: " +
|
|
|
146 |
(wd < bd ? "black" : "white") + "'><strong>CENTER</strong></td><td>" +
|
|
|
147 |
c.center[0] + "</td><td>" + c.center[1] + "</td><td>" + c.center[2] + "</td></tr>");
|
|
|
148 |
for(var j = 0; j < m.length; ++j){
|
|
|
149 |
var color = colors[m[j]];
|
|
|
150 |
wd = dist([255,255,255], color);
|
|
|
151 |
bd = dist([0,0,0], color);
|
|
|
152 |
reps.push("<tr><td style='background: " + m[j] + "; color: " +
|
|
|
153 |
(wd < bd ? "black" : "white") + "'><strong>" + m[j] + "</strong></td><td>" +
|
|
|
154 |
color[0] + "</td><td>" + color[1] + "</td><td>" + color[2] + "</td></tr>");
|
|
|
155 |
}
|
|
|
156 |
reps.push("</table>");
|
|
|
157 |
}
|
|
|
158 |
dojo.byId("report").innerHTML = reps.join("\n");
|
|
|
159 |
};
|
|
|
160 |
|
|
|
161 |
run = function(){
|
|
|
162 |
var n = parseInt(dojo.byId("ncluster").value);
|
|
|
163 |
runVQ(n);
|
|
|
164 |
};
|
|
|
165 |
|
|
|
166 |
dojo.addOnLoad(function(){
|
|
|
167 |
dojo.connect(dojo.byId("run"), "onclick", run);
|
|
|
168 |
});
|
|
|
169 |
</script>
|
|
|
170 |
</head>
|
|
|
171 |
<body>
|
|
|
172 |
<h1>Compress colors using VQ</h1>
|
|
|
173 |
<p>Select desirable number of clusters: <select id="ncluster">
|
|
|
174 |
<option value="1">1</option>
|
|
|
175 |
<option value="2">2</option>
|
|
|
176 |
<option value="4">4</option>
|
|
|
177 |
<option value="8">8</option>
|
|
|
178 |
<option value="16">16</option>
|
|
|
179 |
<option value="32">32</option>
|
|
|
180 |
<option value="64">64</option>
|
|
|
181 |
</select> <button id="run">Run</button></p>
|
|
|
182 |
<div id="status" class="pane"><em>No status yet.</em></div>
|
|
|
183 |
<div id="report" class="pane"><em>No results yet.</em></div>
|
|
|
184 |
</body>
|
|
|
185 |
</html>
|