001: /*
002: * $RCSfile: TagTreeDecoder.java,v $
003: * $Revision: 1.1 $
004: * $Date: 2005/02/11 05:02:02 $
005: * $State: Exp $
006: *
007: * Class: TagTreeDecoder
008: *
009: * Description: Decoder 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:
048: package jj2000.j2k.codestream.reader;
049:
050: import jj2000.j2k.io.*;
051: import jj2000.j2k.util.*;
052: import java.io.*;
053:
054: /**
055: * This class implements the tag tree decoder. A tag tree codes a 2D
056: * matrix of integer elements in an efficient way. The decoding
057: * procedure 'update()' updates a value of the matrix from a stream of
058: * coded data, given a threshold. This procedure decodes enough
059: * information to identify whether or not the value is greater than
060: * or equal to the threshold, and updates the value accordingly.
061: *
062: * <P>In general the decoding procedure must follow the same sequence
063: * of elements and thresholds as the encoding one. The encoder is
064: * implemented by the TagTreeEncoder class.
065: *
066: * <P>Tag trees that have one dimension, or both, as 0 are allowed for
067: * convenience. Of course no values can be set or coded in such cases.
068: *
069: * @see jj2000.j2k.codestream.writer.TagTreeEncoder
070: * */
071: public class TagTreeDecoder {
072:
073: /** The horizontal dimension of the base level */
074: protected int w;
075:
076: /** The vertical dimensions of the base level */
077: protected int h;
078:
079: /** The number of levels in the tag tree */
080: protected int lvls;
081:
082: /** The tag tree values. The first index is the level,
083: * starting at level 0 (leafs). The second index is the element
084: * within the level, in lexicographical order. */
085: protected int treeV[][];
086:
087: /** The tag tree state. The first index is the level, starting at
088: * level 0 (leafs). The second index is the element within the
089: * level, in lexicographical order. */
090: protected int treeS[][];
091:
092: /**
093: * Creates a tag tree decoder with 'w' elements along the
094: * horizontal dimension and 'h' elements along the vertical
095: * direction. The total number of elements is thus 'vdim' x
096: * 'hdim'.
097: *
098: * <P>The values of all elements are initialized to
099: * Integer.MAX_VALUE (i.e. no information decoded so far). The
100: * states are initialized all to 0.
101: *
102: * @param h The number of elements along the vertical direction.
103: *
104: * @param w The number of elements along the horizontal direction.
105: *
106: *
107: * */
108: public TagTreeDecoder(int h, int w) {
109: int i;
110:
111: // Check arguments
112: if (w < 0 || h < 0) {
113: throw new IllegalArgumentException();
114: }
115: // Initialize dimensions
116: this .w = w;
117: this .h = h;
118: // Calculate the number of levels
119: if (w == 0 || h == 0) {
120: lvls = 0; // Empty tree
121: } else {
122: lvls = 1;
123: while (h != 1 || w != 1) { // Loop until we reach root
124: w = (w + 1) >> 1;
125: h = (h + 1) >> 1;
126: lvls++;
127: }
128: }
129: // Allocate tree values and states
130: treeV = new int[lvls][];
131: treeS = new int[lvls][];
132: w = this .w;
133: h = this .h;
134: for (i = 0; i < lvls; i++) {
135: treeV[i] = new int[h * w];
136: // Initialize to infinite value
137: ArrayUtil.intArraySet(treeV[i], Integer.MAX_VALUE);
138:
139: // (no need to initialize to 0 since it's the default)
140: treeS[i] = new int[h * w];
141: w = (w + 1) >> 1;
142: h = (h + 1) >> 1;
143: }
144: }
145:
146: /**
147: * Returns the number of leafs along the horizontal direction.
148: *
149: * @return The number of leafs along the horizontal direction.
150: *
151: *
152: * */
153: public final int getWidth() {
154: return w;
155: }
156:
157: /**
158: * Returns the number of leafs along the vertical direction.
159: *
160: * @return The number of leafs along the vertical direction.
161: *
162: *
163: * */
164: public final int getHeight() {
165: return h;
166: }
167:
168: /**
169: * Decodes information for the specified element of the tree,
170: * given the threshold, and updates its value. The information
171: * that can be decoded is whether or not the value of the element
172: * is greater than, or equal to, the value of the
173: * threshold.
174: *
175: * @param m The vertical index of the element.
176: *
177: * @param n The horizontal index of the element.
178: *
179: * @param t The threshold to use in decoding. It must be non-negative.
180: *
181: * @param in The stream from where to read the coded information.
182: *
183: * @return The updated value at position (m,n).
184: *
185: * @exception IOException If an I/O error occurs while reading
186: * from 'in'.
187: *
188: * @exception EOFException If the ned of the 'in' stream is
189: * reached before getting all the necessary data.
190: *
191: *
192: * */
193: public int update(int m, int n, int t, PktHeaderBitReader in)
194: throws IOException {
195: int k, tmin;
196: int idx, ts, tv;
197:
198: // Check arguments
199: if (m >= h || n >= w || t < 0) {
200: throw new IllegalArgumentException();
201: }
202:
203: // Initialize
204: k = lvls - 1;
205: tmin = treeS[k][0];
206:
207: // Loop on levels
208: idx = (m >> k) * ((w + (1 << k) - 1) >> k) + (n >> k);
209: while (true) {
210: // Cache state and value
211: ts = treeS[k][idx];
212: tv = treeV[k][idx];
213: if (ts < tmin) {
214: ts = tmin;
215: }
216: while (t > ts) {
217: if (tv >= ts) { // We are not done yet
218: if (in.readBit() == 0) { // '0' bit
219: // We know that 'value' > treeS[k][idx]
220: ts++;
221: } else { // '1' bit
222: // We know that 'value' = treeS[k][idx]
223: tv = ts++;
224: }
225: // Increment of treeS[k][idx] done above
226: } else { // We are done, we can set ts and get out
227: ts = t;
228: break; // get out of this while
229: }
230: }
231: // Update state and value
232: treeS[k][idx] = ts;
233: treeV[k][idx] = tv;
234: // Update tmin or terminate
235: if (k > 0) {
236: tmin = ts < tv ? ts : tv;
237: k--;
238: // Index of element for next iteration
239: idx = (m >> k) * ((w + (1 << k) - 1) >> k) + (n >> k);
240: } else {
241: // Return the updated value
242: return tv;
243: }
244: }
245: }
246:
247: /**
248: * Returns the current value of the specified element in the tag
249: * tree. This is the value as last updated by the update() method.
250: *
251: * @param m The vertical index of the element.
252: *
253: * @param n The horizontal index of the element.
254: *
255: * @return The current value of the element.
256: *
257: * @see #update
258: *
259: *
260: * */
261: public int getValue(int m, int n) {
262: // Check arguments
263: if (m >= h || n >= w) {
264: throw new IllegalArgumentException();
265: }
266: // Return value
267: return treeV[0][m * w + n];
268: }
269: }
|