001: /*
002: *
003: * $RCSfile: Subband.java,v $
004: * $Revision: 1.1 $
005: * $Date: 2005/02/11 05:02:27 $
006: * $State: Exp $
007: *
008: * Class: Subband
009: *
010: * Description: Asbtract element for a tree strcuture for
011: * a description of subbands.
012: *
013: *
014: *
015: * COPYRIGHT:
016: *
017: * This software module was originally developed by Raphaël Grosbois and
018: * Diego Santa Cruz (Swiss Federal Institute of Technology-EPFL); Joel
019: * Askelöf (Ericsson Radio Systems AB); and Bertrand Berthelot, David
020: * Bouchard, Félix Henry, Gerard Mozelle and Patrice Onno (Canon Research
021: * Centre France S.A) in the course of development of the JPEG2000
022: * standard as specified by ISO/IEC 15444 (JPEG 2000 Standard). This
023: * software module is an implementation of a part of the JPEG 2000
024: * Standard. Swiss Federal Institute of Technology-EPFL, Ericsson Radio
025: * Systems AB and Canon Research Centre France S.A (collectively JJ2000
026: * Partners) agree not to assert against ISO/IEC and users of the JPEG
027: * 2000 Standard (Users) any of their rights under the copyright, not
028: * including other intellectual property rights, for this software module
029: * with respect to the usage by ISO/IEC and Users of this software module
030: * or modifications thereof for use in hardware or software products
031: * claiming conformance to the JPEG 2000 Standard. Those intending to use
032: * this software module in hardware or software products are advised that
033: * their use may infringe existing patents. The original developers of
034: * this software module, JJ2000 Partners and ISO/IEC assume no liability
035: * for use of this software module or modifications thereof. No license
036: * or right to this software module is granted for non JPEG 2000 Standard
037: * conforming products. JJ2000 Partners have full right to use this
038: * software module for his/her own purpose, assign or donate this
039: * software module to any third party and to inhibit third parties from
040: * using this software module for non JPEG 2000 Standard conforming
041: * products. This copyright notice must be included in all copies or
042: * derivative works of this software module.
043: *
044: * Copyright (c) 1999/2000 JJ2000 Partners.
045: * */
046: package jj2000.j2k.wavelet;
047:
048: import java.awt.Point;
049:
050: /**
051: * This abstract class represents a subband in a bidirectional tree structure
052: * that describes the subband decomposition for a wavelet transform. This
053: * class is implemented by the SubbandAn and SubbandSyn classes, which are for
054: * the analysis and synthesis sides, respectively.
055: *
056: * <P>The element can be either a node or a leaf of the tree. If it is a node
057: * then ther are 4 descendants (LL, HL, LH and HH). If it is a leaf ther are
058: * no descendants.
059: *
060: * <P>The tree is bidirectional. Each element in the tree structure has a
061: * "parent", which is the subband from which the element was obtained by
062: * decomposition. The only exception is the root element which has no parent
063: * (i.e.it's null), for obvious reasons.
064: *
065: * @see jj2000.j2k.wavelet.analysis.SubbandAn
066: * @see jj2000.j2k.wavelet.synthesis.SubbandSyn
067: * */
068: public abstract class Subband {
069:
070: /** The ID for the LL orientation */
071: public final static int WT_ORIENT_LL = 0;
072:
073: /** The ID for the HL (horizontal high-pass) orientation */
074: public final static int WT_ORIENT_HL = 1;
075:
076: /** The ID for the LH (vertical high-pass) orientation */
077: public final static int WT_ORIENT_LH = 2;
078:
079: /** The ID for the HH orientation */
080: public final static int WT_ORIENT_HH = 3;
081:
082: /**
083: * True if it is a node in the tree, false if it is a leaf. False by
084: * default. */
085: public boolean isNode;
086:
087: /**
088: * The orientation of this subband (WT_ORIENT_LL, WT_ORIENT_HL,
089: * WT_ORIENT_LH, WT_ORIENT_HH). It is WT_ORIENT_LL by default. The
090: * orientation of the top-level node (i.e. the full image before any
091: * decomposition) is WT_ORIENT_LL. */
092: // The default value is always 0, which is WT_ORIENT_LL.
093: public int orientation;
094:
095: /**
096: * The level in the tree to which this subband belongs, which is the
097: * number of wavelet decompositions performed to produce this subband. It
098: * is 0 for the top-level (i.e. root) node. It is 0 by default.
099: * */
100: public int level;
101:
102: /**
103: * The resolution level to which this subband contributes. Level 0 is the
104: * smallest resolution level (the one with the lowest frequency LL
105: * subband). It is 0 by default.
106: * */
107: public int resLvl;
108:
109: /** The number of code-blocks (in both directions) contained in this
110: * subband. */
111: public Point numCb = null;
112:
113: /**
114: * The base 2 exponent of the analysis gain of the subband. The analysis
115: * gain of a subband is defined as the gain of the previous subband
116: * (i.e. the one from which this one was obtained) multiplied by the line
117: * gain and by the column gain. The line (column) gain is the gain of the
118: * line (column) filter that was used to obtain it, which is the DC gain
119: * for a low-pass filter and the Nyquist gain for a high-pass filter. It
120: * is 0 by default.
121: *
122: * <P>Using the base 2 exponent of the value contrains the possible gains
123: * to powers of 2. However this is perfectly compatible to the filter
124: * normalization policy assumed here. See the split() method for more
125: * details.
126: *
127: * @see #split
128: * */
129: public int anGainExp;
130:
131: /**
132: * The subband index within its resolution level. This value uniquely
133: * identifies a subband within a resolution level and a decomposition
134: * level within it. Note that only leaf elements represent "real"
135: * subbands, while node elements represent only intermediate stages.
136: *
137: * <P>It is defined recursively. The root node gets a value of 0. For a
138: * given node, with a subband index 'b', its LL descendant gets 4*b, its
139: * HL descendant 4*b+1, its LH descendant 4*b+2, and its HH descendant
140: * 4*b+3, for their subband indexes.
141: * */
142: public int sbandIdx = 0;
143:
144: /**
145: * The horizontal coordinate of the upper-left corner of the subband, with
146: * respect to the canvas origin, in the component's grid and subband's
147: * decomposition level. This is the real horizontal index of the first
148: * column of this subband. If even the horizontal decomposition of this
149: * subband should be done with the low-pass-first convention. If odd it
150: * should be done with the high-pass-first convention.
151: * */
152: public int ulcx;
153:
154: /**
155: * The vertical coordinate of the upper-left corner of the subband, with
156: * respect to the canvas origin, in the component's grid and subband's
157: * decomposition level. This is the real vertical index of the first
158: * column of this subband. If even the vertical decomposition of this
159: * subband should be done with the low-pass-first convention. If odd it
160: * should be done with the high-pass-first convention.
161: * */
162: public int ulcy;
163:
164: /** The horizontal coordinate of the upper-left corner of the subband */
165: public int ulx;
166:
167: /** The vertical coordinate of the upper-left corner of the subband */
168: public int uly;
169:
170: /** The width of the subband */
171: public int w;
172:
173: /** The height of the subband */
174: public int h;
175:
176: /** The nominal code-block width */
177: public int nomCBlkW;
178:
179: /** The nominal code-block height */
180: public int nomCBlkH;
181:
182: /**
183: * Returns the parent of this subband. The parent of a subband is the
184: * subband from which this one was obtained by decomposition. The root
185: * element has no parent subband (null).
186: *
187: * @return The parent subband, or null for the root one.
188: * */
189: public abstract Subband getParent();
190:
191: /**
192: * Returns the LL child subband of this subband.
193: *
194: * @return The LL child subband, or null if there are no childs.
195: * */
196: public abstract Subband getLL();
197:
198: /**
199: * Returns the HL (horizontal high-pass) child subband of this subband.
200: *
201: * @return The HL child subband, or null if there are no childs.
202: * */
203: public abstract Subband getHL();
204:
205: /**
206: * Returns the LH (vertical high-pass) child subband of this subband.
207: *
208: * @return The LH child subband, or null if there are no childs.
209: * */
210: public abstract Subband getLH();
211:
212: /**
213: * Returns the HH child subband of this subband.
214: *
215: * @return The HH child subband, or null if there are no childs.
216: * */
217: public abstract Subband getHH();
218:
219: /**
220: * Splits the current subband in its four subbands. This creates the four
221: * childs (LL, HL, LH and HH) and converts the leaf in a node.
222: *
223: * @param hfilter The horizontal wavelet filter used to decompose this
224: * subband.
225: *
226: * @param vfilter The vertical wavelet filter used to decompose this
227: * subband.
228: *
229: * @return A reference to the LL leaf (getLL()).
230: * */
231: protected abstract Subband split(WaveletFilter hfilter,
232: WaveletFilter vfilter);
233:
234: /**
235: * Initializes the childs of this node with the correct values. The sizes
236: * of the child subbands are calculated by taking into account the
237: * position of the subband in the canvas.
238: *
239: * <P>For the analysis subband gain calculation it is assumed that
240: * analysis filters are normalized with a DC gain of 1 and a Nyquist gain
241: * of 2.
242: * */
243: protected void initChilds() {
244: Subband subb_LL = getLL();
245: Subband subb_HL = getHL();
246: Subband subb_LH = getLH();
247: Subband subb_HH = getHH();
248:
249: // LL subband
250: subb_LL.level = level + 1;
251: subb_LL.ulcx = (ulcx + 1) >> 1;
252: subb_LL.ulcy = (ulcy + 1) >> 1;
253: subb_LL.ulx = ulx;
254: subb_LL.uly = uly;
255: subb_LL.w = ((ulcx + w + 1) >> 1) - subb_LL.ulcx;
256: subb_LL.h = ((ulcy + h + 1) >> 1) - subb_LL.ulcy;
257: // If this subband in in the all LL path (i.e. it's global orientation
258: // is LL) then child LL band contributes to a lower resolution level.
259: subb_LL.resLvl = (orientation == WT_ORIENT_LL) ? resLvl - 1
260: : resLvl;
261: subb_LL.anGainExp = anGainExp;
262: subb_LL.sbandIdx = (sbandIdx << 2);
263: // HL subband
264: subb_HL.orientation = WT_ORIENT_HL;
265: subb_HL.level = subb_LL.level;
266: subb_HL.ulcx = ulcx >> 1;
267: subb_HL.ulcy = subb_LL.ulcy;
268: subb_HL.ulx = ulx + subb_LL.w;
269: subb_HL.uly = uly;
270: subb_HL.w = ((ulcx + w) >> 1) - subb_HL.ulcx;
271: subb_HL.h = subb_LL.h;
272: subb_HL.resLvl = resLvl;
273: subb_HL.anGainExp = anGainExp + 1;
274: subb_HL.sbandIdx = (sbandIdx << 2) + 1;
275: // LH subband
276: subb_LH.orientation = WT_ORIENT_LH;
277: subb_LH.level = subb_LL.level;
278: subb_LH.ulcx = subb_LL.ulcx;
279: subb_LH.ulcy = ulcy >> 1;
280: subb_LH.ulx = ulx;
281: subb_LH.uly = uly + subb_LL.h;
282: subb_LH.w = subb_LL.w;
283: subb_LH.h = ((ulcy + h) >> 1) - subb_LH.ulcy;
284: subb_LH.resLvl = resLvl;
285: subb_LH.anGainExp = anGainExp + 1;
286: subb_LH.sbandIdx = (sbandIdx << 2) + 2;
287: // HH subband
288: subb_HH.orientation = WT_ORIENT_HH;
289: subb_HH.level = subb_LL.level;
290: subb_HH.ulcx = subb_HL.ulcx;
291: subb_HH.ulcy = subb_LH.ulcy;
292: subb_HH.ulx = subb_HL.ulx;
293: subb_HH.uly = subb_LH.uly;
294: subb_HH.w = subb_HL.w;
295: subb_HH.h = subb_LH.h;
296: subb_HH.resLvl = resLvl;
297: subb_HH.anGainExp = anGainExp + 2;
298: subb_HH.sbandIdx = (sbandIdx << 2) + 3;
299: }
300:
301: /**
302: * Creates a Subband element with all the default values. The dimensions
303: * are (0,0), the upper left corner is (0,0) and the upper-left corner
304: * with respect to the canvas is (0,0) too.
305: * */
306: public Subband() {
307: }
308:
309: /**
310: * Creates the top-level node and the entire subband tree, with the
311: * top-level dimensions, the number of decompositions, and the
312: * decomposition tree as specified.
313: *
314: * <P>For the analysis subband gain calculation it is assumed that
315: * analysis filters are normalized with a DC gain of 1 and a Nyquist gain
316: * of 2.
317: *
318: * <P>This constructor does not initialize the value of the magBits member
319: * variable. This variable is normally initialized by the quantizer, on
320: * the encoder side, or the bit stream reader, on the decoder side.
321: *
322: * @param w The top-level width
323: *
324: * @param h The top-level height
325: *
326: * @param ulcx The horizontal coordinate of the upper-left corner with
327: * respect to the canvas origin, in the component grid.
328: *
329: * @param ulcy The vertical coordinate of the upper-left corner with
330: * respect to the canvas origin, in the component grid.
331: *
332: * @param lvls The number of levels (or LL decompositions) in the tree.
333: *
334: * @param hfilters The horizontal wavelet filters (analysis or synthesis)
335: * for each resolution level, starting at resolution level 0. If there are
336: * less elements in the array than there are resolution levels, the last
337: * element is used for the remaining resolution levels.
338: *
339: * @param vfilters The vertical wavelet filters (analysis or synthesis)
340: * for each resolution level, starting at resolution level 0. If there are
341: * less elements in the array than there are resolution levels, the last
342: * element is used for the remaining resolution levels.
343: *
344: * @see WaveletTransform
345: * */
346: public Subband(int w, int h, int ulcx, int ulcy, int lvls,
347: WaveletFilter hfilters[], WaveletFilter vfilters[]) {
348: int i, hi, vi;
349: Subband cur; // The current subband
350:
351: // Initialize top-level node
352: this .w = w;
353: this .h = h;
354: this .ulcx = ulcx;
355: this .ulcy = ulcy;
356: this .resLvl = lvls;
357: // First create dyadic decomposition.
358: cur = this ;
359: for (i = 0; i < lvls; i++) {
360: hi = (cur.resLvl <= hfilters.length) ? cur.resLvl - 1
361: : hfilters.length - 1;
362: vi = (cur.resLvl <= vfilters.length) ? cur.resLvl - 1
363: : vfilters.length - 1;
364: cur = cur.split(hfilters[hi], vfilters[vi]);
365: }
366: }
367:
368: /**
369: * Returns the next subband in the same resolution level, following the
370: * subband index order. If already at the last subband then null is
371: * returned. If this subband is not a leaf an IllegalArgumentException is
372: * thrown.
373: *
374: * @return The next subband in the same resolution level, following the
375: * subband index order, or null if already at last subband.
376: * */
377: public Subband nextSubband() {
378: Subband sb;
379:
380: if (isNode) {
381: throw new IllegalArgumentException();
382: }
383:
384: switch (orientation) {
385: case WT_ORIENT_LL:
386: sb = getParent();
387: if (sb == null || sb.resLvl != resLvl) {
388: // Already at top-level or last subband in res. level
389: return null;
390: } else {
391: return sb.getHL();
392: }
393: case WT_ORIENT_HL:
394: return getParent().getLH();
395: case WT_ORIENT_LH:
396: return getParent().getHH();
397: case WT_ORIENT_HH:
398: // This is the complicated one
399: sb = this ;
400: while (sb.orientation == WT_ORIENT_HH) {
401: sb = sb.getParent();
402: }
403: switch (sb.orientation) {
404: case WT_ORIENT_LL:
405: sb = sb.getParent();
406: if (sb == null || sb.resLvl != resLvl) {
407: // Already at top-level or last subband in res. level
408: return null;
409: } else {
410: sb = sb.getHL();
411: }
412: break;
413: case WT_ORIENT_HL:
414: sb = sb.getParent().getLH();
415: break;
416: case WT_ORIENT_LH:
417: sb = sb.getParent().getHH();
418: break;
419: default:
420: throw new Error("You have found a bug in JJ2000");
421: }
422: while (sb.isNode) {
423: sb = sb.getLL();
424: }
425: return sb;
426: default:
427: throw new Error("You have found a bug in JJ2000");
428: }
429: }
430:
431: /**
432: * Returns the first leaf subband element in the next higher resolution
433: * level.
434: *
435: * @return The first leaf element in the next higher resolution level, or
436: * null if there is no higher resolution level.
437: * */
438: public Subband getNextResLevel() {
439: Subband sb;
440:
441: if (level == 0) { // No higher res. level
442: return null;
443: }
444: // Go up until we get to a different resolution level
445: sb = this ;
446: do {
447: sb = sb.getParent();
448: if (sb == null) { // No higher resolution level
449: return null;
450: }
451: } while (sb.resLvl == resLvl);
452: // Now go down to HL, which is in next higher resolution level
453: sb = sb.getHL();
454: // Now go down LL until get to a leaf
455: while (sb.isNode) {
456: sb = sb.getLL();
457: }
458: return sb;
459: }
460:
461: /**
462: * Returns a subband element in the tree, given its resolution level and
463: * subband index. This method searches through the tree.
464: *
465: * @param rl The resolution level.
466: *
467: * @param sbi The subband index, within the resolution level.
468: * */
469: public Subband getSubbandByIdx(int rl, int sbi) {
470: Subband sb = this ;
471:
472: // Find the root subband for the resolution level
473: if (rl > sb.resLvl || rl < 0) {
474: throw new IllegalArgumentException(
475: "Resolution level index " + "out of range");
476: }
477:
478: // Returns directly if it is itself
479: if (rl == sb.resLvl && sbi == sb.sbandIdx)
480: return sb;
481:
482: if (sb.sbandIdx != 0)
483: sb = sb.getParent();
484:
485: while (sb.resLvl > rl)
486: sb = sb.getLL();
487: while (sb.resLvl < rl)
488: sb = sb.getParent();
489:
490: switch (sbi) {
491: case 0:
492: default:
493: return sb;
494: case 1:
495: return sb.getHL();
496: case 2:
497: return sb.getLH();
498: case 3:
499: return sb.getHH();
500: }
501:
502: }
503:
504: /**
505: * Returns a reference to the Subband element to which the specified point
506: * belongs. The specified point must be inside this (i.e. the one defined
507: * by this object) subband. This method searches through the tree.
508: *
509: * @param x horizontal coordinate of the specified point.
510: *
511: * @param y horizontal coordinate of the specified point.
512: * */
513: public Subband getSubband(int x, int y) {
514: Subband cur, hhs;
515:
516: // Check that we are inside this subband
517: if (x < ulx || y < uly || x >= ulx + w || y >= uly + h) {
518: throw new IllegalArgumentException();
519: }
520:
521: cur = this ;
522: while (cur.isNode) {
523: hhs = cur.getHH();
524: // While we are still at a node -> continue
525: if (x < hhs.ulx) {
526: // Is the result of horizontal low-pass
527: if (y < hhs.uly) {
528: // Vertical low-pass
529: cur = cur.getLL();
530: } else {
531: // Vertical high-pass
532: cur = cur.getLH();
533: }
534: } else {
535: // Is the result of horizontal high-pass
536: if (y < hhs.uly) {
537: // Vertical low-pass
538: cur = cur.getHL();
539: } else {
540: // Vertical high-pass
541: cur = cur.getHH();
542: }
543: }
544: }
545:
546: return cur;
547: }
548:
549: /**
550: * Returns subband informations in a string.
551: *
552: * @return Subband informations
553: * */
554: public String toString() {
555:
556: String string = "w=" + w + ", h=" + h + ", ulx=" + ulx
557: + ", uly=" + uly + ", ulcx= " + ulcx + ", ulcy=" + ulcy
558: + ", idx=" + sbandIdx + "\norient=" + orientation
559: + ", node=" + isNode + ", level=" + level + ", resLvl="
560: + resLvl + ", nomCBlkW=" + nomCBlkW + ", nomCBlkH="
561: + nomCBlkH;
562:
563: return string;
564: }
565:
566: /**
567: * This function returns the horizontal wavelet filter relevant to this
568: * subband
569: *
570: * @return The horizontal wavelet filter
571: * */
572: public abstract WaveletFilter getHorWFilter();
573:
574: /**
575: * This function returns the vertical wavelet filter relevant to this
576: * subband
577: *
578: * @return The vertical wavelet filter
579: * */
580: public abstract WaveletFilter getVerWFilter();
581:
582: }
|