001: /*
002: * $RCSfile: TagTreeEncoder.java,v $
003: * $Revision: 1.1 $
004: * $Date: 2005/02/11 05:02:03 $
005: * $State: Exp $
006: *
007: * Class: TagTreeEncoder
008: *
009: * Description: Encoder of tag trees
010: *
011: *
012: *
013: * COPYRIGHT:
014: *
015: * This software module was originally developed by Raphaël Grosbois and
016: * Diego Santa Cruz (Swiss Federal Institute of Technology-EPFL); Joel
017: * Askelöf (Ericsson Radio Systems AB); and Bertrand Berthelot, David
018: * Bouchard, Félix Henry, Gerard Mozelle and Patrice Onno (Canon Research
019: * Centre France S.A) in the course of development of the JPEG2000
020: * standard as specified by ISO/IEC 15444 (JPEG 2000 Standard). This
021: * software module is an implementation of a part of the JPEG 2000
022: * Standard. Swiss Federal Institute of Technology-EPFL, Ericsson Radio
023: * Systems AB and Canon Research Centre France S.A (collectively JJ2000
024: * Partners) agree not to assert against ISO/IEC and users of the JPEG
025: * 2000 Standard (Users) any of their rights under the copyright, not
026: * including other intellectual property rights, for this software module
027: * with respect to the usage by ISO/IEC and Users of this software module
028: * or modifications thereof for use in hardware or software products
029: * claiming conformance to the JPEG 2000 Standard. Those intending to use
030: * this software module in hardware or software products are advised that
031: * their use may infringe existing patents. The original developers of
032: * this software module, JJ2000 Partners and ISO/IEC assume no liability
033: * for use of this software module or modifications thereof. No license
034: * or right to this software module is granted for non JPEG 2000 Standard
035: * conforming products. JJ2000 Partners have full right to use this
036: * software module for his/her own purpose, assign or donate this
037: * software module to any third party and to inhibit third parties from
038: * using this software module for non JPEG 2000 Standard conforming
039: * products. This copyright notice must be included in all copies or
040: * derivative works of this software module.
041: *
042: * Copyright (c) 1999/2000 JJ2000 Partners.
043: *
044: *
045: *
046: */
047: package jj2000.j2k.codestream.writer;
048:
049: import jj2000.j2k.util.*;
050: import jj2000.j2k.io.*;
051: import java.io.*;
052:
053: /**
054: * This class implements the tag tree encoder. A tag tree codes a 2D
055: * matrix of integer elements in an efficient way. The encoding
056: * procedure 'encode()' codes information about a value of the matrix,
057: * given a threshold. The procedure encodes the sufficient information
058: * to identify whether or not the value is greater than or equal to
059: * the threshold.
060: *
061: * <P>The tag tree saves encoded information to a BitOutputBuffer.
062: *
063: * <P>A particular and useful property of tag trees is that it is
064: * possible to change a value of the matrix, provided both new and old
065: * values of the element are both greater than or equal to the largest
066: * threshold which has yet been supplied to the coding procedure
067: * 'encode()'. This property can be exploited through the 'setValue()'
068: * method.
069: *
070: * <P>This class allows saving the state of the tree at any point and
071: * restoring it at a later time, by calling save() and restore().
072: *
073: * <P>A tag tree can also be reused, or restarted, if one of the
074: * reset() methods is called.
075: *
076: * <P>The TagTreeDecoder class implements the tag tree decoder.
077: *
078: * <P>Tag trees that have one dimension, or both, as 0 are allowed for
079: * convenience. Of course no values can be set or coded in such cases.
080: *
081: * @see BitOutputBuffer
082: *
083: * @see jj2000.j2k.codestream.reader.TagTreeDecoder
084: * */
085: public class TagTreeEncoder {
086:
087: /** The horizontal dimension of the base level */
088: protected int w;
089:
090: /** The vertical dimensions of the base level */
091: protected int h;
092:
093: /** The number of levels in the tag tree */
094: protected int lvls;
095:
096: /** The tag tree values. The first index is the level, starting at
097: * level 0 (leafs). The second index is the element within the
098: * level, in lexicographical order. */
099: protected int treeV[][];
100:
101: /** The tag tree state. The first index is the level, starting at
102: * level 0 (leafs). The second index is the element within the
103: * level, in lexicographical order. */
104: protected int treeS[][];
105:
106: /** The saved tag tree values. The first index is the level,
107: * starting at level 0 (leafs). The second index is the element
108: * within the level, in lexicographical order. */
109: protected int treeVbak[][];
110:
111: /** The saved tag tree state. The first index is the level, starting at
112: * level 0 (leafs). The second index is the element within the
113: * level, in lexicographical order. */
114: protected int treeSbak[][];
115:
116: /** The saved state. If true the values and states of the tree
117: * have been saved since the creation or last reset. */
118: protected boolean saved;
119:
120: /**
121: * Creates a tag tree encoder with 'w' elements along the
122: * horizontal dimension and 'h' elements along the vertical
123: * direction. The total number of elements is thus 'vdim' x
124: * 'hdim'.
125: *
126: * <P>The values of all elements are initialized to Integer.MAX_VALUE.
127: *
128: * @param h The number of elements along the horizontal direction.
129: *
130: * @param w The number of elements along the vertical direction.
131: *
132: *
133: * */
134: public TagTreeEncoder(int h, int w) {
135: int k;
136: // Check arguments
137: if (w < 0 || h < 0) {
138: throw new IllegalArgumentException();
139: }
140: // Initialize elements
141: init(w, h);
142: // Set values to max
143: for (k = treeV.length - 1; k >= 0; k--) {
144: ArrayUtil.intArraySet(treeV[k], Integer.MAX_VALUE);
145: }
146: }
147:
148: /**
149: * Creates a tag tree encoder with 'w' elements along the
150: * horizontal dimension and 'h' elements along the vertical
151: * direction. The total number of elements is thus 'vdim' x
152: * 'hdim'. The values of the leafs in the tag tree are initialized
153: * to the values of the 'val' array.
154: *
155: * <P>The values in the 'val' array are supposed to appear in
156: * lexicographical order, starting at index 0.
157: *
158: * @param h The number of elements along the horizontal direction.
159: *
160: * @param w The number of elements along the vertical direction.
161: *
162: * @param val The values with which initialize the leafs of the
163: * tag tree.
164: *
165: *
166: * */
167: public TagTreeEncoder(int h, int w, int val[]) {
168: int k;
169: // Check arguments
170: if (w < 0 || h < 0 || val.length < w * h) {
171: throw new IllegalArgumentException();
172: }
173: // Initialize elements
174: init(w, h);
175: // Update leaf values
176: for (k = w * h - 1; k >= 0; k--) {
177: treeV[0][k] = val[k];
178: }
179: // Calculate values at other levels
180: recalcTreeV();
181: }
182:
183: /**
184: * Returns the number of leafs along the horizontal direction.
185: *
186: * @return The number of leafs along the horizontal direction.
187: *
188: *
189: * */
190: public final int getWidth() {
191: return w;
192: }
193:
194: /**
195: * Returns the number of leafs along the vertical direction.
196: *
197: * @return The number of leafs along the vertical direction.
198: *
199: *
200: * */
201: public final int getHeight() {
202: return h;
203: }
204:
205: /**
206: * Initializes the variables of this class, given the dimensions
207: * at the base level (leaf level). All the state ('treeS' array)
208: * and values ('treeV' array) are intialized to 0. This method is
209: * called by the constructors.
210: *
211: * @param w The number of elements along the vertical direction.
212: *
213: * @param h The number of elements along the horizontal direction.
214: *
215: *
216: * */
217: private void init(int w, int h) {
218: int i;
219: // Initialize dimensions
220: this .w = w;
221: this .h = h;
222: // Calculate the number of levels
223: if (w == 0 || h == 0) {
224: lvls = 0;
225: } else {
226: lvls = 1;
227: while (h != 1 || w != 1) { // Loop until we reach root
228: w = (w + 1) >> 1;
229: h = (h + 1) >> 1;
230: lvls++;
231: }
232: }
233: // Allocate tree values and states
234: // (no need to initialize to 0 since it's the default)
235: treeV = new int[lvls][];
236: treeS = new int[lvls][];
237: w = this .w;
238: h = this .h;
239: for (i = 0; i < lvls; i++) {
240: treeV[i] = new int[h * w];
241: treeS[i] = new int[h * w];
242: w = (w + 1) >> 1;
243: h = (h + 1) >> 1;
244: }
245: }
246:
247: /**
248: * Recalculates the values of the elements in the tag tree, in
249: * levels 1 and up, based on the values of the leafs (level 0).
250: *
251: *
252: * */
253: private void recalcTreeV() {
254: int m, n, bi, lw, tm1, tm2, lh, k;
255: // Loop on all other levels, updating minimum
256: for (k = 0; k < lvls - 1; k++) {
257: // Visit all elements in level
258: lw = (w + (1 << k) - 1) >> k;
259: lh = (h + (1 << k) - 1) >> k;
260: for (m = ((lh >> 1) << 1) - 2; m >= 0; m -= 2) { // All quads with 2 lines
261: for (n = ((lw >> 1) << 1) - 2; n >= 0; n -= 2) { // All quads with 2 columns
262: // Take minimum of 4 elements and put it in higher
263: // level
264: bi = m * lw + n;
265: tm1 = (treeV[k][bi] < treeV[k][bi + 1]) ? treeV[k][bi]
266: : treeV[k][bi + 1];
267: tm2 = (treeV[k][bi + lw] < treeV[k][bi + lw + 1]) ? treeV[k][bi
268: + lw]
269: : treeV[k][bi + lw + 1];
270: treeV[k + 1][(m >> 1) * ((lw + 1) >> 1) + (n >> 1)] = tm1 < tm2 ? tm1
271: : tm2;
272: }
273: // Now we may have quad with 1 column, 2 lines
274: if (lw % 2 != 0) {
275: n = ((lw >> 1) << 1);
276: // Take minimum of 2 elements and put it in higher
277: // level
278: bi = m * lw + n;
279: treeV[k + 1][(m >> 1) * ((lw + 1) >> 1) + (n >> 1)] = (treeV[k][bi] < treeV[k][bi
280: + lw]) ? treeV[k][bi] : treeV[k][bi + lw];
281: }
282: }
283: // Now we may have quads with 1 line, 2 or 1 columns
284: if (lh % 2 != 0) {
285: m = ((lh >> 1) << 1);
286: for (n = ((lw >> 1) << 1) - 2; n >= 0; n -= 2) { // All quads with 2 columns
287: // Take minimum of 2 elements and put it in higher
288: // level
289: bi = m * lw + n;
290: treeV[k + 1][(m >> 1) * ((lw + 1) >> 1) + (n >> 1)] = (treeV[k][bi] < treeV[k][bi + 1]) ? treeV[k][bi]
291: : treeV[k][bi + 1];
292: }
293: // Now we may have quad with 1 column, 1 line
294: if (lw % 2 != 0) {
295: // Just copy the value
296: n = ((lw >> 1) << 1);
297: treeV[k + 1][(m >> 1) * ((lw + 1) >> 1) + (n >> 1)] = treeV[k][m
298: * lw + n];
299: }
300: }
301: }
302: }
303:
304: /**
305: * Changes the value of a leaf in the tag tree. The new and old
306: * values of the element must be not smaller than the largest
307: * threshold which has yet been supplied to 'encode()'.
308: *
309: * @param m The vertical index of the element.
310: *
311: * @param n The horizontal index of the element.
312: *
313: * @param v The new value of the element.
314: *
315: *
316: * */
317: public void setValue(int m, int n, int v) {
318: int k, idx;
319: // Check arguments
320: if (lvls == 0 || n < 0 || n >= w || v < treeS[lvls - 1][0]
321: || treeV[0][m * w + n] < treeS[lvls - 1][0]) {
322: throw new IllegalArgumentException();
323: }
324: // Update the leaf value
325: treeV[0][m * w + n] = v;
326: // Update all parents
327: for (k = 1; k < lvls; k++) {
328: idx = (m >> k) * ((w + (1 << k) - 1) >> k) + (n >> k);
329: if (v < treeV[k][idx]) {
330: // We need to update minimum and continue checking
331: // in higher levels
332: treeV[k][idx] = v;
333: } else {
334: // We are done: v is equal or less to minimum
335: // in this level, no other minimums to update.
336: break;
337: }
338: }
339: }
340:
341: /**
342: * Sets the values of the leafs to the new set of values and
343: * updates the tag tree accordingly. No leaf can change its value
344: * if either the new or old value is smaller than largest
345: * threshold which has yet been supplied to 'encode()'. However
346: * such a leaf can keep its old value (i.e. new and old value must
347: * be identical.
348: *
349: * <P>This method is more efficient than the setValue() method if
350: * a large proportion of the leafs change their value. Note that
351: * for leafs which don't have their value defined yet the value
352: * should be Integer.MAX_VALUE (which is the default
353: * initialization value).
354: *
355: * @param val The new values for the leafs, in lexicographical order.
356: *
357: * @see #setValue
358: *
359: *
360: * */
361: public void setValues(int val[]) {
362: int i, maxt;
363: if (lvls == 0) { // Can't set values on empty tree
364: throw new IllegalArgumentException();
365: }
366: // Check the values
367: maxt = treeS[lvls - 1][0];
368: for (i = w * h - 1; i >= 0; i--) {
369: if ((treeV[0][i] < maxt || val[i] < maxt)
370: && treeV[0][i] != val[i]) {
371: throw new IllegalArgumentException();
372: }
373: // Update leaf value
374: treeV[0][i] = val[i];
375: }
376: // Recalculate tree at other levels
377: recalcTreeV();
378: }
379:
380: /**
381: * Encodes information for the specified element of the tree,
382: * given the threshold and sends it to the 'out' stream. The
383: * information that is coded is whether or not the value of the
384: * element is greater than or equal to the value of the threshold.
385: *
386: * @param m The vertical index of the element.
387: *
388: * @param n The horizontal index of the element.
389: *
390: * @param t The threshold to use for encoding. It must be non-negative.
391: *
392: * @param out The stream where to write the coded information.
393: *
394: *
395: * */
396: public void encode(int m, int n, int t, BitOutputBuffer out) {
397: int k, ts, idx, tmin;
398:
399: // Check arguments
400: if (m >= h || n >= w || t < 0) {
401: throw new IllegalArgumentException();
402: }
403:
404: // Initialize
405: k = lvls - 1;
406: tmin = treeS[k][0];
407:
408: // Loop on levels
409: while (true) {
410: // Index of element in level 'k'
411: idx = (m >> k) * ((w + (1 << k) - 1) >> k) + (n >> k);
412: // Cache state
413: ts = treeS[k][idx];
414: if (ts < tmin) {
415: ts = tmin;
416: }
417: while (t > ts) {
418: if (treeV[k][idx] > ts) {
419: out.writeBit(0); // Send '0' bit
420: } else if (treeV[k][idx] == ts) {
421: out.writeBit(1); // Send '1' bit
422: } else { // we are done: set ts and get out of this while
423: ts = t;
424: break;
425: }
426: // Increment of treeS[k][idx]
427: ts++;
428: }
429: // Update state
430: treeS[k][idx] = ts;
431: // Update tmin or terminate
432: if (k > 0) {
433: tmin = ts < treeV[k][idx] ? ts : treeV[k][idx];
434: k--;
435: } else {
436: // Terminate
437: return;
438: }
439: }
440: }
441:
442: /**
443: * Saves the current values and state of the tree. Calling
444: * restore() restores the tag tree the saved state.
445: *
446: * @see #restore
447: *
448: *
449: * */
450: public void save() {
451: int k, i;
452:
453: if (treeVbak == null) { // Nothing saved yet
454: // Allocate saved arrays
455: // treeV and treeS have the same dimensions
456: treeVbak = new int[lvls][];
457: treeSbak = new int[lvls][];
458: for (k = lvls - 1; k >= 0; k--) {
459: treeVbak[k] = new int[treeV[k].length];
460: treeSbak[k] = new int[treeV[k].length];
461: }
462: }
463:
464: // Copy the arrays
465: for (k = treeV.length - 1; k >= 0; k--) {
466: System.arraycopy(treeV[k], 0, treeVbak[k], 0,
467: treeV[k].length);
468: System.arraycopy(treeS[k], 0, treeSbak[k], 0,
469: treeS[k].length);
470: }
471:
472: // Set saved state
473: saved = true;
474: }
475:
476: /**
477: * Restores the saved values and state of the tree. An
478: * IllegalArgumentException is thrown if the tree values and state
479: * have not been saved yet.
480: *
481: * @see #save
482: *
483: *
484: * */
485: public void restore() {
486: int k, i;
487:
488: if (!saved) { // Nothing saved yet
489: throw new IllegalArgumentException();
490: }
491:
492: // Copy the arrays
493: for (k = lvls - 1; k >= 0; k--) {
494: System.arraycopy(treeVbak[k], 0, treeV[k], 0,
495: treeV[k].length);
496: System.arraycopy(treeSbak[k], 0, treeS[k], 0,
497: treeS[k].length);
498: }
499:
500: }
501:
502: /**
503: * Resets the tree values and state. All the values are set to
504: * Integer.MAX_VALUE and the states to 0.
505: *
506: *
507: * */
508: public void reset() {
509: int k;
510: // Set all values to Integer.MAX_VALUE
511: // and states to 0
512: for (k = lvls - 1; k >= 0; k--) {
513: ArrayUtil.intArraySet(treeV[k], Integer.MAX_VALUE);
514: ArrayUtil.intArraySet(treeS[k], 0);
515: }
516: // Invalidate saved tree
517: saved = false;
518: }
519:
520: /**
521: * Resets the tree values and state. The values are set to the
522: * values in 'val'. The states are all set to 0.
523: *
524: * @param val The new values for the leafs, in lexicographical order.
525: *
526: *
527: * */
528: public void reset(int val[]) {
529: int k;
530: // Set values for leaf level
531: for (k = w * h - 1; k >= 0; k--) {
532: treeV[0][k] = val[k];
533: }
534: // Calculate values at other levels
535: recalcTreeV();
536: // Set all states to 0
537: for (k = lvls - 1; k >= 0; k--) {
538: ArrayUtil.intArraySet(treeS[k], 0);
539: }
540: // Invalidate saved tree
541: saved = false;
542: }
543: }
|