001: /*
002: * $RCSfile: CBlkRateDistStats.java,v $
003: * $Revision: 1.1 $
004: * $Date: 2005/02/11 05:02:07 $
005: * $State: Exp $
006: *
007: * Class: CBlkRateDistStats
008: *
009: * Description: The coded (compressed) code-block with
010: * rate-distortion statistics.
011: *
012: *
013: *
014: * COPYRIGHT:
015: *
016: * This software module was originally developed by Raphaël Grosbois and
017: * Diego Santa Cruz (Swiss Federal Institute of Technology-EPFL); Joel
018: * Askelöf (Ericsson Radio Systems AB); and Bertrand Berthelot, David
019: * Bouchard, Félix Henry, Gerard Mozelle and Patrice Onno (Canon Research
020: * Centre France S.A) in the course of development of the JPEG2000
021: * standard as specified by ISO/IEC 15444 (JPEG 2000 Standard). This
022: * software module is an implementation of a part of the JPEG 2000
023: * Standard. Swiss Federal Institute of Technology-EPFL, Ericsson Radio
024: * Systems AB and Canon Research Centre France S.A (collectively JJ2000
025: * Partners) agree not to assert against ISO/IEC and users of the JPEG
026: * 2000 Standard (Users) any of their rights under the copyright, not
027: * including other intellectual property rights, for this software module
028: * with respect to the usage by ISO/IEC and Users of this software module
029: * or modifications thereof for use in hardware or software products
030: * claiming conformance to the JPEG 2000 Standard. Those intending to use
031: * this software module in hardware or software products are advised that
032: * their use may infringe existing patents. The original developers of
033: * this software module, JJ2000 Partners and ISO/IEC assume no liability
034: * for use of this software module or modifications thereof. No license
035: * or right to this software module is granted for non JPEG 2000 Standard
036: * conforming products. JJ2000 Partners have full right to use this
037: * software module for his/her own purpose, assign or donate this
038: * software module to any third party and to inhibit third parties from
039: * using this software module for non JPEG 2000 Standard conforming
040: * products. This copyright notice must be included in all copies or
041: * derivative works of this software module.
042: *
043: * Copyright (c) 1999/2000 JJ2000 Partners.
044: * */
045: package jj2000.j2k.entropy.encoder;
046:
047: import jj2000.j2k.entropy.*;
048: import jj2000.j2k.wavelet.analysis.*;
049: import java.io.*;
050:
051: /**
052: * This class stores coded (compressed) code-blocks with their associated
053: * rate-distortion statistics. This object should always contain all the
054: * compressed data of the code-block. It is applicable to the encoder engine
055: * only. Some data of the coded-block is stored in the super class, see
056: * CodedCBlk.
057: *
058: * <P>The rate-distortion statistics (i.e. R-D slope) is stored for valid
059: * points only. The set of valid points is determined by the entropy coder
060: * engine itself. Normally they are selected so as to lye in a convex hull,
061: * which can be achived by using the 'selectConvexHull' method of this class,
062: * but some other strategies might be employed.
063: *
064: * <P>The rate (in bytes) for each truncation point (valid or not) is stored
065: * in the 'truncRates' array. The rate of a truncation point is the total
066: * number of bytes in 'data' (see super class) that have to be decoded to
067: * reach the truncation point.
068: *
069: * <P>The slope (reduction of distortion divided by the increase in rate) at
070: * each of the valid truncation points is stored in 'truncSlopes'.
071: *
072: * <P>The index of each valid truncation point is stored in 'truncIdxs'. The
073: * index should be interpreted in the following way: a valid truncation point
074: * at position 'n' has the index 'truncIdxs[n]', the rate
075: * 'truncRates[truncIdxs[n]]' and the slope 'truncSlopes[n]'. The arrays
076: * 'truncIdxs' and 'truncRates' have at least 'nVldTrunc' elements. The
077: * 'truncRates' array has at least 'nTotTrunc' elements.
078: *
079: * <P>In addition the 'isTermPass' array contains a flag for each truncation
080: * point (valid and non-valid ones) that tells if the pass is terminated or
081: * not. If this variable is null then it means that no pass is terminated,
082: * except the last one which always is.
083: *
084: * <P>The compressed data is stored in the 'data' member variable of the super
085: * class.
086: *
087: * @see CodedCBlk
088: * */
089: public class CBlkRateDistStats extends CodedCBlk {
090:
091: /** The subband to which the code-block belongs */
092: public SubbandAn sb;
093:
094: /** The total number of truncation points */
095: public int nTotTrunc;
096:
097: /** The number of valid truncation points */
098: public int nVldTrunc;
099:
100: /** The rate (in bytes) for each truncation point (valid and non-valid
101: * ones) */
102: public int truncRates[];
103:
104: /** The distortion for each truncation point (valid and non-valid ones) */
105: public double truncDists[];
106:
107: /** The negative of the rate-distortion slope for each valid truncation
108: point */
109: public float truncSlopes[];
110:
111: /** The indices of the valid truncation points, in increasing
112: * order. */
113: public int truncIdxs[];
114:
115: /** Array of flags indicating terminated passes (valid or non-valid
116: * truncation points). */
117: public boolean isTermPass[];
118:
119: /** The number of ROI coefficients in the code-block */
120: public int nROIcoeff = 0;
121:
122: /** Number of ROI coding passes */
123: public int nROIcp = 0;
124:
125: /**
126: * Creates a new CBlkRateDistStats object without allocating any space for
127: * 'truncRates', 'truncSlopes', 'truncDists' and 'truncIdxs' or 'data'.
128: * */
129: public CBlkRateDistStats() {
130: }
131:
132: /**
133: * Creates a new CBlkRateDistStats object and initializes the valid
134: * truncation points, their rates and their slopes, from the 'rates' and
135: * 'dist' arrays. The 'rates', 'dist' and 'termp' arrays must contain the
136: * rate (in bytes), the reduction in distortion (from nothing coded) and
137: * the flag indicating if termination is used, respectively, for each
138: * truncation point.
139: *
140: * <P>The valid truncation points are selected by taking them as lying on
141: * a convex hull. This is done by calling the method selectConvexHull().
142: *
143: * <P> Note that the arrays 'rates' and 'termp' are copied, not
144: * referenced, so they can be modified after a call to this constructor.
145: *
146: * @param m The horizontal index of the code-block, within the subband.
147: *
148: * @param n The vertical index of the code-block, within the subband.
149: *
150: * @param skipMSBP The number of skipped most significant bit-planes for
151: * this code-block.
152: *
153: * @param data The compressed data. This array is referenced by this
154: * object so it should not be modified after.
155: *
156: * @param rates The rates (in bytes) for each truncation point in the
157: * compressed data. This array is modified by the method but no reference
158: * is kept to it.
159: *
160: * @param dists The reduction in distortion (with respect to no information
161: * coded) for each truncation point. This array is modified by the method
162: * but no reference is kept to it.
163: *
164: * @param termp An array of boolean flags indicating, for each pass, if a
165: * pass is terminated or not (true if terminated). If null then it is
166: * assumed that no pass is terminated except the last one which always is.
167: *
168: * @param np The number of truncation points contained in 'rates', 'dist'
169: * and 'termp'.
170: *
171: * @param inclast If false the convex hull is constructed as for lossy
172: * coding. If true it is constructed as for lossless coding, in which case
173: * it is ensured that all bit-planes are sent (i.e. the last truncation
174: * point is always included).
175: * */
176: public CBlkRateDistStats(int m, int n, int skipMSBP, byte data[],
177: int rates[], double dists[], boolean termp[], int np,
178: boolean inclast) {
179: super (m, n, skipMSBP, data);
180: selectConvexHull(rates, dists, termp, np, inclast);
181: }
182:
183: /**
184: * Compute the rate-distorsion slopes and selects those that lie in a
185: * convex hull. It will compute the slopes, select the ones that form the
186: * convex hull and initialize the 'truncIdxs' and 'truncSlopes' arrays, as
187: * well as 'nVldTrunc', with the selected truncation points. It will also
188: * initialize 'truncRates' and 'isTermPass' arrays, as well as
189: * 'nTotTrunc', with all the truncation points (selected or not).
190: *
191: * <P> Note that the arrays 'rates' and 'termp' are copied, not
192: * referenced, so they can be modified after a call to this method.
193: *
194: * @param rates The rates (in bytes) for each truncation point in the
195: * compressed data. This array is modified by the method.
196: *
197: * @param dists The reduction in distortion (with respect to no
198: * information coded) for each truncation point. This array is modified by
199: * the method.
200: *
201: * @param termp An array of boolean flags indicating, for each pass, if a
202: * pass is terminated or not (true if terminated). If null then it is
203: * assumed that no pass is terminated except the last one which always is.
204: *
205: * @param n The number of truncation points contained in 'rates', 'dist'
206: * and 'termp'.
207: *
208: * @param inclast If false the convex hull is constructed as for lossy
209: * coding. If true it is constructed as for lossless coding, in which case
210: * it is ensured that all bit-planes are sent (i.e. the last truncation
211: * point is always included).
212: * */
213: public void selectConvexHull(int rates[], double dists[],
214: boolean termp[], int n, boolean inclast) {
215: int first_pnt; // The first point containing some coded data
216: int p; // last selected point
217: int k; // current point
218: int i; // current valid point
219: int npnt; // number of selected (i.e. valid) points
220: int delta_rate; // Rate difference
221: double delta_dist; // Distortion difference
222: float k_slope; // R-D slope for the current point
223: float p_slope; // R-D slope for the last selected point
224: int ll_rate; // Rate for "lossless" coding (i.e. all coded info)
225:
226: // Convention: when a negative value is stored in 'rates' it meas an
227: // invalid point. The absolute value is always the rate for that point.
228:
229: // Look for first point with some coded info (rate not 0)
230: first_pnt = 0;
231: while (first_pnt < n && rates[first_pnt] <= 0) {
232: first_pnt++;
233: }
234:
235: // Select the valid points
236: npnt = n - first_pnt;
237: p_slope = 0f; // To keep compiler happy
238: ploop: do {
239: p = -1;
240: for (k = first_pnt; k < n; k++) {
241: if (rates[k] < 0) { // Already invalidated point
242: continue;
243: }
244: // Calculate decrease in distortion and rate
245: if (p >= 0) {
246: delta_rate = rates[k] - rates[p];
247: delta_dist = dists[k] - dists[p];
248: } else { // This is with respect to no info coded
249: delta_rate = rates[k];
250: delta_dist = dists[k];
251: }
252: // If exactly same distortion don't eliminate if the rates are
253: // equal, otherwise it can lead to infinite slope in lossless
254: // coding.
255: if (delta_dist < 0f
256: || (delta_dist == 0f && delta_rate > 0)) {
257: // This point increases distortion => invalidate
258: rates[k] = -rates[k];
259: npnt--;
260: continue; // Goto next point
261: }
262: k_slope = (float) (delta_dist / delta_rate);
263: // Check that there is a decrease in distortion, slope is not
264: // infinite (i.e. delta_dist is not 0) and slope is
265: // decreasing.
266: if (p >= 0 && (delta_rate <= 0 || k_slope >= p_slope)) {
267: // Last point was not good
268: rates[p] = -rates[p]; // Remove p from valid points
269: npnt--;
270: continue ploop; // Restart from the first one
271: } else {
272: p_slope = k_slope;
273: p = k;
274: }
275: }
276: // If we get to last point we are done
277: break;
278: } while (true); // We end the loop with the break statement
279:
280: // If in lossless mode make sure we don't eliminate any last bit-planes
281: // from being sent.
282: if (inclast && n > 0 && rates[n - 1] < 0) {
283: rates[n - 1] = -rates[n - 1];
284: // This rate can never be equal to any previous selected rate,
285: // given the selection algorithm above, so no problem arises of
286: // infinite slopes.
287: npnt++;
288: }
289:
290: // Initialize the arrays of this object
291: nTotTrunc = n;
292: nVldTrunc = npnt;
293: truncRates = new int[n];
294: truncDists = new double[n];
295: truncSlopes = new float[npnt];
296: truncIdxs = new int[npnt];
297: if (termp != null) {
298: isTermPass = new boolean[n];
299: System.arraycopy(termp, 0, isTermPass, 0, n);
300: } else {
301: isTermPass = null;
302: }
303: System.arraycopy(rates, 0, truncRates, 0, n);
304: for (k = first_pnt, p = -1, i = 0; k < n; k++) {
305: if (rates[k] > 0) { // A valid point
306: truncDists[k] = dists[k];
307: if (p < 0) { // Only arrives at first valid point
308: truncSlopes[i] = (float) (dists[k] / rates[k]);
309: } else {
310: truncSlopes[i] = (float) ((dists[k] - dists[p]) / (rates[k] - rates[p]));
311: }
312: truncIdxs[i] = k;
313: i++;
314: p = k;
315: } else {
316: truncDists[k] = -1;
317: truncRates[k] = -truncRates[k];
318: }
319: }
320: }
321:
322: /**
323: * Returns the contents of the object in a string. This is used for
324: * debugging.
325: *
326: * @return A string with the contents of the object
327: * */
328: public String toString() {
329: return super .toString() + "\n nVldTrunc = " + nVldTrunc
330: + ", nTotTrunc=" + nTotTrunc + ", num. ROI" + " coeff="
331: + nROIcoeff + ", num. ROI coding passes=" + nROIcp;
332: }
333: }
|