|
/Users/lyon/j4p/src/ip/color/Octree.java
|
1 package ip.color;
2
3 public class Octree {
4 private static final int MAXDEPTH = 7;
5 private int numNodes = 0;
6 private int maxNodes = 0;
7 private int size, level, leafLevel;
8 private RGB colorLut[];
9 private Node tree = null;
10 private Node reduceList[] = new Node[MAXDEPTH + 1];
11 private int k;
12 private short r[][], g[][], b[][];
13
14 public Octree() {
15
16 }
17
18 public void octreeQuantization(short ra[][],
19 short ga[][],
20 short ba[][],
21 int ki) {
22 r = ra;
23 g = ga;
24 b = ba;
25 k = ki;
26
27 setColor();
28 reMap(r, g, b);
29 }
30
31 public void reMap(short r[][], short g[][], short b[][]) {
32 for (int x = 0; x < r.length; x++)
33 for (int y = 0; y < r[0].length; y++) {
34 RGB c = new RGB();
35 c.r = r[x][y];
36 c.g = g[x][y];
37 c.b = b[x][y];
38 int id = findColor(tree, c);
39 c = colorLut[id];
40 r[x][y] = c.r;
41 g[x][y] = c.b;
42 b[x][y] = c.g;
43 }
44 }
45
46 /**
47 * Use the octree color reduction algorithm on a image sequence, so
48 * that you can have a consistent color map for each image in the
49 * sequence. After you have added all the images, go back an remap each
50 * image. - DL
51 *
52 * @param r
53 * @param g
54 * @param b
55 */
56 public void addImagesSeen(short r[][], short g[][], short b[][]) {
57 RGB color = new RGB();
58 leafLevel = level + 1;
59 for (int y = 0; y < r[0].length; y++) {
60 for (int x = 0; x < r.length; x++) {
61 color.r = r[x][y];
62 color.g = g[x][y];
63 color.b = b[x][y];
64 tree = insertNode(tree, color, 0);
65 if (size > k)
66 reduceTree();
67 }
68 }
69 int index[] = new int[1];
70 index[0] = 0;
71 initVGAPalette(tree, index);
72 }
73
74 public void setColor() {
75 RGB color = new RGB();
76
77 colorLut = new RGB[k];
78 tree = null;
79 size = 0;
80 level = MAXDEPTH;
81 leafLevel = level + 1;
82 for (int y = 0; y < r[0].length; y++) {
83 for (int x = 0; x < r.length; x++) {
84 color.r = r[x][y];
85 color.g = g[x][y];
86 color.b = b[x][y];
87 tree = insertNode(tree, color, 0);
88 if (size > k)
89 reduceTree();
90 }
91 }
92 int index[] = new int[1];
93 index[0] = 0;
94 initVGAPalette(tree, index);
95
96 }
97
98 public int findColor(Node tree, RGB color) {
99 if (tree.leaf)
100 return tree.colorIndex;
101 else {
102 final int i = ((color.r >> (MAXDEPTH - tree.level)) & 1) <<
103 2 |
104 ((color.g >> (MAXDEPTH - tree.level)) & 1) << 1 |
105 (color.b >> (MAXDEPTH - tree.level)) & 1;
106 final Node treeNode = tree.link[i];
107 if (treeNode != null)
108 return findColor(treeNode, color);
109 return findNearestEntry(color);
110 }
111 }
112 /**
113 * search the color lookup table for
114 * @param color
115 * @return an index of the closest entry.
116 */
117 public int findNearestEntry(RGB color) {
118 int n = colorLut.length;
119 int error = Integer.MAX_VALUE;
120 int bestIndex = 0;
121 for (int i=0; i < n ; i++) {
122 RGB c = colorLut[i];
123 int e = c.getError(color);
124 if (e < error) {
125 error = e;
126 bestIndex = i;
127 }
128 }
129 return bestIndex;
130 }
131
132 public Node insertNode(Node node, RGB color, int depth) {
133 int branch;
134
135 if (node == null) // create new node
136 {
137 node = new Node();
138 numNodes++;
139 if (numNodes > maxNodes)
140 maxNodes = numNodes;
141 node.level = depth;
142 node.leaf = (depth >= leafLevel) ? true : false;
143 if (node.leaf)
144 size++;
145 }
146 node.colorCount++;
147 node.RGBSum.r += color.r;
148 node.RGBSum.g += color.g;
149 node.RGBSum.b += color.b;
150 if (!(node.leaf) && (depth < leafLevel)) {
151 branch = ((color.r >> (MAXDEPTH - depth)) & 1) << 2 |
152 ((color.g >> (MAXDEPTH - depth)) & 1) << 1 |
153 (color.b >> (MAXDEPTH - depth)) & 1;
154 if (node.link[branch] == null) {
155 node.child++;
156 if (node.child == 2) {
157 node.nextReduceable = reduceList[depth];
158 reduceList[depth] = node;
159 }
160 }
161 node.link[branch] =
162 insertNode(node.link[branch], color, depth + 1);
163 }
164
165 return node;
166 }
167
168 public Node killTree(Node tree) {
169 if (tree == null)
170 return null;
171 for (int i = 0; i < 8; i++)
172 tree.link[i] = killTree(tree.link[i]);
173
174 numNodes--;
175
176 return null;
177 }
178
179 public void reduceTree() {
180 Node node;
181 int new_Level;
182 int depth;
183
184 new_Level = level;
185 while (reduceList[new_Level] == null)
186 new_Level--;
187 node = reduceList[new_Level];
188 reduceList[new_Level] = reduceList[new_Level].nextReduceable;
189 node.leaf = true;
190 size = size - node.child + 1;
191 depth = node.level;
192 for (int i = 0; i < 8; i++)
193 node.link[i] = killTree(node.link[i]);
194 if (depth < level) {
195 level = depth;
196 leafLevel = level + 1;
197 }
198 }
199
200 public void initVGAPalette(Node tree, int index[]) {
201 if (tree != null) {
202 if (tree.leaf || tree.level == leafLevel) {
203 if (colorLut[index[0]] == null)
204 colorLut[index[0]] = new RGB();
205 colorLut[index[0]].r =
206 (short) (tree.RGBSum.r / tree.colorCount);
207 colorLut[index[0]].g =
208 (short) (tree.RGBSum.g / tree.colorCount);
209 colorLut[index[0]].b =
210 (short) (tree.RGBSum.b / tree.colorCount);
211 tree.colorIndex = index[0]++;
212 tree.leaf = true;
213 } else
214 for (int octant = 0; octant < 8; octant++)
215 initVGAPalette(tree.link[octant], index);
216 }
217 }
218
219 public static int getMAXDEPTH() {
220 return MAXDEPTH;
221 }
222
223 public int getNumNodes() {
224 return numNodes;
225 }
226
227 public void setNumNodes(int numNodes) {
228 this.numNodes = numNodes;
229 }
230
231 public int getMaxNodes() {
232 return maxNodes;
233 }
234
235 public void setMaxNodes(int maxNodes) {
236 this.maxNodes = maxNodes;
237 }
238
239 public int getSize() {
240 return size;
241 }
242
243 public void setSize(int size) {
244 this.size = size;
245 }
246
247 public int getLevel() {
248 return level;
249 }
250
251 public void setLevel(int level) {
252 this.level = level;
253 }
254
255 public int getLeafLevel() {
256 return leafLevel;
257 }
258
259 public void setLeafLevel(int leafLevel) {
260 this.leafLevel = leafLevel;
261 }
262
263 public Node getTree() {
264 return tree;
265 }
266
267 public int getK() {
268 return k;
269 }
270
271 public short[][] getR() {
272 return r;
273 }
274
275 public short[][] getG() {
276 return g;
277 }
278
279 public short[][] getB() {
280 return b;
281 }
282
283 public RGB[] getColorLut() {
284 return colorLut;
285 }
286
287 public Node[] getReduceList() {
288 return reduceList;
289 }
290 }
291
292 class ColorSum {
293 public long r, g, b;
294
295 public ColorSum() {
296 r = g = b = 0;
297 }
298 }
299
300 class RGB {
301 public short r, g, b;
302 /**
303 *
304 * @param rgb
305 * @return the square of the error in RGB space.
306 */
307 public int getError(RGB rgb) {
308 if (rgb == null) return 0;
309 int dr = r - rgb.r;
310 int dg = g - rgb.g;
311 int db = b - rgb.b;
312 return dr*dr+dg*dg+db*db;
313 }
314 }
315
316 class Node {
317 boolean leaf = false;
318 int level = 0;
319 int colorIndex = 0;
320 int child = 0;
321 long colorCount = 0;
322 ColorSum RGBSum = new ColorSum();
323 Node nextReduceable = null;
324 Node link[] = new Node[8];
325
326 public Node() {
327 for (int i = 0; i < 8; i++)
328 link[i] = null;
329 }
330 }