ebcotrateallocator.java

jpeg2000算法实现

/*
 * CVS identifier:
 *
 * $Id: EBCOTRateAllocator.java,v 1.90 2001/03/01 18:37:43 grosbois Exp $
 *
 * Class:                   EBCOTRateAllocator
 *
 * Description:             Generic interface for post-compression
 *                          rate allocator.
 *
 *
 *
 * COPYRIGHT:
 * 
 * This software module was originally developed by Rapha雔 Grosbois and
 * Diego Santa Cruz (Swiss Federal Institute of Technology-EPFL); Joel
 * Askel鰂 (Ericsson Radio Systems AB); and Bertrand Berthelot, David
 * Bouchard, F閘ix Henry, Gerard Mozelle and Patrice Onno (Canon Research
 * Centre France S.A) in the course of development of the JPEG2000
 * standard as specified by ISO/IEC 15444 (JPEG 2000 Standard). This
 * software module is an implementation of a part of the JPEG 2000
 * Standard. Swiss Federal Institute of Technology-EPFL, Ericsson Radio
 * Systems AB and Canon Research Centre France S.A (collectively JJ2000
 * Partners) agree not to assert against ISO/IEC and users of the JPEG
 * 2000 Standard (Users) any of their rights under the copyright, not
 * including other intellectual property rights, for this software module
 * with respect to the usage by ISO/IEC and Users of this software module
 * or modifications thereof for use in hardware or software products
 * claiming conformance to the JPEG 2000 Standard. Those intending to use
 * this software module in hardware or software products are advised that
 * their use may infringe existing patents. The original developers of
 * this software module, JJ2000 Partners and ISO/IEC assume no liability
 * for use of this software module or modifications thereof. No license
 * or right to this software module is granted for non JPEG 2000 Standard
 * conforming products. JJ2000 Partners have full right to use this
 * software module for his/her own purpose, assign or donate this
 * software module to any third party and to inhibit third parties from
 * using this software module for non JPEG 2000 Standard conforming
 * products. This copyright notice must be included in all copies or
 * derivative works of this software module.
 * 
 * Copyright (c) 1999/2000 JJ2000 Partners.
 * */
package jj2000.j2k.entropy.encoder;

import jj2000.j2k.codestream.writer.*;
import jj2000.j2k.wavelet.analysis.*;
import jj2000.j2k.entropy.encoder.*;
import jj2000.j2k.codestream.*;
import jj2000.j2k.entropy.*;
import jj2000.j2k.encoder.*;
import jj2000.j2k.image.*;
import jj2000.j2k.util.*;

import java.util.Vector;
import java.io.*;

/**
 * This implements the EBCOT post compression rate allocation algorithm. This
 * algorithm finds the most suitable truncation points for the set of
 * code-blocks, for each layer target bitrate. It works by first collecting
 * the rate distortion info from all code-blocks, in all tiles and all
 * components, and then running the rate-allocation on the whole image at
 * once, for each layer.
 *
 * <P>This implementation also provides some timing features. They can be
 * enabled by setting the 'DO_TIMING' constant of this class to true and
 * recompiling. The timing uses the 'System.currentTimeMillis()' Java API
 * call, which returns wall clock time, not the actual CPU time used. The
 * timing results will be printed on the message output. Since the times
 * reported are wall clock times and not CPU usage times they can not be added
 * to find the total used time (i.e. some time might be counted in several
 * places). When timing is disabled ('DO_TIMING' is false) there is no penalty
 * if the compiler performs some basic optimizations. Even if not the penalty
 * should be negligeable.
 *
 * @see PostCompRateAllocator
 *
 * @see CodedCBlkDataSrcEnc
 *
 * @see jj2000.j2k.codestream.writer.CodestreamWriter
 * */
public class EBCOTRateAllocator extends PostCompRateAllocator {

    /** Whether to collect timing information or not: false. Used as a compile
     * time directive. */
    private final static boolean DO_TIMING = false;

    /** The wall time for the initialization. */
    private long initTime;

    /** The wall time for the building of layers. */
    private long buildTime;

    /** The wall time for the writing of layers. */
    private long writeTime;

    /**
     * 5D Array containing all the coded code-blocks:
     * 
     * <ul>
     * <li>1st index: tile index</li>
     * <li>2nd index: component index</li>
     * <li>3rd index: resolution level index</li>
     * <li>4th index: subband index</li>
     * <li>5th index: code-block index</li>
     * </ul>
     **/
    private CBlkRateDistStats cblks[][][][][];
    
    /**
     * 6D Array containing the indices of the truncation points. It actually
     * contains the index of the element in CBlkRateDistStats.truncIdxs that
     * gives the real truncation point index.
     *
     * <ul>
     * <li>1st index: tile index</li>
     * <li>2nd index: layer index</li>
     * <li>3rd index: component index</li>
     * <li>4th index: resolution level index</li>
     * <li>5th index: subband index</li>
     * <li>6th index: code-block index</li>
     * </ul>
     **/
    private int truncIdxs[][][][][][];
    
    /** 
     * Maximum number of precincts :
     *
     * <ul>
     * <li>1st dim: tile index.</li>
     * <li>2nd dim: component index.</li>
     * <li>3nd dim: resolution level index.</li>
     * </ul>
     */
    private Coord maxNumPrec[][][];
    
    /** Array containing the layers information. */
    private EBCOTLayer layers[];
    
    /** The log of 2, natural base */
    private static final double LOG2 = Math.log(2);

    /** The normalization offset for the R-D summary table */
    private static final int RD_SUMMARY_OFF = 24;

    /** The size of the summary table */
    private static final int RD_SUMMARY_SIZE = 64;

    /** The relative precision for float data. This is the relative tolerance
     * up to which the layer slope thresholds are calculated. */
    private static final float FLOAT_REL_PRECISION = 1e-4f;

    /** The precision for float data type, in an absolute sense. Two float
     * numbers are considered "equal" if they are within this precision. */
    private static final float FLOAT_ABS_PRECISION = 1e-10f;

    /** 
     * Minimum average size of a packet. If layer has less bytes than the this
     * constant multiplied by number of packets in the layer, then the layer
     * is skipped.  
     * */
    private static final int MIN_AVG_PACKET_SZ = 32;

    /**
     * The R-D summary information collected from the coding of all
     * code-blocks. For each entry it contains the accumulated length of all
     * truncation points that have a slope not less than
     * '2*(k-RD_SUMMARY_OFF)', where 'k' is the entry index.
     *
     * <P>Therefore, the length at entry 'k' is the total number of bytes of
     * code-block data that would be obtained if the truncation slope was
     * chosen as '2*(k-RD_SUMMARY_OFF)', without counting the overhead
     * associated with the packet heads.
     *
     * <P>This summary is used to estimate the relation of the R-D slope to
     * coded length, and to obtain absolute minimums on the slope given a
     * length.
     **/
    private int RDSlopesRates[];
    
    /** Packet encoder. */
    private PktEncoder packetEnc;
     
    /** The layer specifications */
    private LayersInfo lyrSpec;
     
    /** The maximum slope accross all code-blocks and truncation points. */
    private float maxSlope;

    /** The minimum slope accross all code-blocks and truncation points. */
    private float minSlope;
    
    /**
     * Initializes the EBCOT rate allocator of entropy coded data. The layout
     * of layers, and their bitrate constraints, is specified by the 'lyrs'
     * parameter.
     *
     * @param src The source of entropy coded data.
     *
     * @param lyrs The layers layout specification.
     *
     * @param writer The bit stream writer.
     *
     * @see ProgressionType
     * */
    public EBCOTRateAllocator(CodedCBlkDataSrcEnc src, LayersInfo lyrs,
                              CodestreamWriter writer,
                              EncoderSpecs encSpec, ParameterList pl) {
                              
        super(src,lyrs.getTotNumLayers(),writer,encSpec);
    
        int minsbi, maxsbi;
        int i;
        SubbandAn sb, sb2;
        Coord ncblks = null;

        // If we do timing create necessary structures
        if (DO_TIMING) {
            // If we are timing make sure that 'finalize' gets called.
            System.runFinalizersOnExit(true);
            // The System.runFinalizersOnExit() method is deprecated in Java
            // 1.2 since it can cause a deadlock in some cases. However, here
            // we use it only for profiling purposes and is disabled in
            // production code.
            initTime = 0L;
            buildTime = 0L;
            writeTime = 0L;
        }

        // Save the layer specs
        lyrSpec = lyrs;

        //Initialize the size of the RD slope rates array
        RDSlopesRates = new int[RD_SUMMARY_SIZE];
        
        //Get number of tiles, components
        int nt = src.getNumTiles();
        int nc = getNumComps();
        
        //Allocate the coded code-blocks and truncation points indexes arrays
        cblks = new CBlkRateDistStats[nt][nc][][][];
        truncIdxs = new int[nt][numLayers][nc][][][];

        int cblkPerSubband; // Number of code-blocks per subband
        int t=0; // tile index
	int mrl; // Number of resolution levels
        int l; // layer index
	int s; //subband index

        // Used to compute the maximum number of precincts for each resolution
        // level
        int tx0, ty0, tx1, ty1; // Current tile position in the reference grid
        int tcx0, tcy0, tcx1, tcy1; // Current tile position in the domain of
        // the image component
        int trx0, try0, trx1, try1; // Current tile position in the reduced
        // resolution image domain
        int xrsiz, yrsiz; // Component sub-sampling factors

        src.setTile(0,0); // Go to the first one

        while(t<nt){ // Loop on tiles
            for(int c=0; c<nc; c++){ // loop on components

                //Get the number of resolution levels
                sb = src.getSubbandTree(t,c);
                mrl = sb.resLvl+1;

                // Initialize maximum number of precincts per resolution array
                if( maxNumPrec == null ){
                    maxNumPrec = new Coord[nt][nc][];
                }
                if( maxNumPrec[t][c] ==null ){
                    maxNumPrec[t][c] = new Coord[mrl];
                }

                // Tile's coordinates on the reference grid
                tx0 = src.getULX(c);
                ty0 = src.getULY(c);
                tx1 = tx0 + src.getWidth();
                ty1 = ty0 + src.getHeight();
                
                // Subsampling factors
                xrsiz = src.getCompSubsX(c);
                yrsiz = src.getCompSubsY(c);

                // Tile's coordinates in the image component domain
                tcx0 = (int)Math.ceil(tx0/(double)(xrsiz));
                tcy0 = (int)Math.ceil(ty0/(double)(yrsiz));
                tcx1 = (int)Math.ceil(tx1/(double)(xrsiz));
                tcy1 = (int)Math.ceil(ty1/(double)(yrsiz));

                cblks[t][c] = new CBlkRateDistStats[mrl][][];

                for(l=0; l<numLayers; l++) {
                    truncIdxs[t][l][c] = new int[mrl][][];
                }

                for(int r=mrl-1; r>=0; r--){ // loop on resolution levels
                    
                    // Tile's coordinates in the reduced resolution image
                    // domain
                    trx0 = (int)Math.ceil(tcx0/(double)(1<<(mrl-1-r)));
                    try0 = (int)Math.ceil(tcy0/(double)(1<<(mrl-1-r)));
                    trx1 = (int)Math.ceil(tcx1/(double)(1<<(mrl-1-r)));
                    try1 = (int)Math.ceil(tcy1/(double)(1<<(mrl-1-r)));

                    // Calculate the maximum number of precincts for each
                    // resolution level taking into account tile specific
                    // options.
                    double twoppx = (double)encSpec.pss.getPPX(t,c,r);
                    double twoppy = (double)encSpec.pss.getPPY(t,c,r);
                    maxNumPrec[t][c][r] = new Coord();
                    if( trx1>trx0 ) {
                        maxNumPrec[t][c][r].x = (int)Math.ceil(trx1/twoppx)
                            - (int)Math.floor(trx0/twoppx);
                    }
                    if( try1>try0 ) {
                        maxNumPrec[t][c][r].y = (int)Math.ceil(try1/twoppy)
                            - (int)Math.floor(try0/twoppy);
                    }

                    //Find subband with highest index
                    sb2 = sb;
                    while(sb2.subb_HH != null)
                        sb2 = sb2.subb_HH;
                    maxsbi = sb2.sbandIdx + 1;
                    minsbi = maxsbi >> 2;

                    cblks[t][c][r] = new CBlkRateDistStats[maxsbi][];
                    for(l=0; l<numLayers; l++)
                        truncIdxs[t][l][c][r] = new int[maxsbi][];

                    sb2 = (SubbandAn)sb.getSubbandByIdx(r,minsbi);
                    for(s=minsbi; s<maxsbi; s++){ // loop on subbands
                        //Get the number of blocks in the current subband
                        ncblks = src.getNumCodeBlocks(sb2,ncblks);
                        cblkPerSubband = ncblks.x*ncblks.y;
                        cblks[t][c][r][s] = 
                            new CBlkRateDistStats[cblkPerSubband];
                        
                        for(l=0; l<numLayers; l++){
                            truncIdxs[t][l][c][r][s] = new int[cblkPerSubband];
                            for(i=0; i<cblkPerSubband; i++)
                                truncIdxs[t][l][c][r][s][i] = -1;
                        }
                        sb2 = (SubbandAn) sb2.nextSubband();
                    } // End loop on subbands

                    sb = sb.subb_LL;
                } // End lopp on resolution levels
            } // End loop on components

            // Go to the next tile
            if(t<nt-1) { //not at last tile
                src.nextTile();
            }
            t++;
        } // End loop on tiles
        
        //Initialize the packet encoder
        packetEnc = new PktEncoder(src,encSpec,maxNumPrec,pl);

        // The layers array has to be initialized after the constructor since
        // it is needed that the bit stream header has been entirely written
    }