jj2000.j2k.entropy.encoder
Class EBCOTRateAllocator

java.lang.Object
  |
  +--jj2000.j2k.image.ImgDataAdapter
        |
        +--jj2000.j2k.entropy.encoder.PostCompRateAllocator
              |
              +--jj2000.j2k.entropy.encoder.EBCOTRateAllocator

All Implemented Interfaces:

ImgData

public class EBCOTRateAllocator

extends PostCompRateAllocator

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.

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 Also:

PostCompRateAllocator, CodedCBlkDataSrcEnc, CodestreamWriter

Field Summary

private long	buildTime The wall time for the building of layers.
private CBlkRateDistStats[][][][][]	cblks 5D Array containing all the coded code-blocks: 1st index: tile index 2nd index: component index 3rd index: resolution level index 4th index: subband index 5th index: code-block index
private static boolean	DO_TIMING Whether to collect timing information or not: false.
private static float	FLOAT_ABS_PRECISION The precision for float data type, in an absolute sense.
private static float	FLOAT_REL_PRECISION The relative precision for float data.
private long	initTime The wall time for the initialization.
private EBCOTLayer[]	layers Array containing the layers information.
private static double	LOG2 The log of 2, natural base
private LayersInfo	lyrSpec The layer specifications
private float	maxSlope The maximum slope accross all code-blocks and truncation points.
private static int	MIN_AVG_PACKET_SZ Minimum average size of a packet.
private float	minSlope The minimum slope accross all code-blocks and truncation points.
private Coord[][][]	numPrec Number of precincts in each resolution level: 1st dim: tile index. 2nd dim: component index. 3nd dim: resolution level index.
private PktEncoder	pktEnc Packet encoder.
private static int	RD_SUMMARY_OFF The normalization offset for the R-D summary table
private static int	RD_SUMMARY_SIZE The size of the summary table
private int[]	RDSlopesRates The R-D summary information collected from the coding of all code-blocks.
private int[][][][][][]	truncIdxs 6D Array containing the indices of the truncation points.
private long	writeTime The wall time for the writing of layers.

Fields inherited from class jj2000.j2k.entropy.encoder.PostCompRateAllocator

bsWriter, encSpec, headEnc, numLayers, OPT_PREFIX, src

Fields inherited from class jj2000.j2k.image.ImgDataAdapter

imgdatasrc, tIdx

Constructor Summary

EBCOTRateAllocator(CodedCBlkDataSrcEnc src, LayersInfo lyrs, CodestreamWriter writer, EncoderSpecs encSpec, ParameterList pl)
Initializes the EBCOT rate allocator of entropy coded data.

Method Summary

private void	buildAndWriteLayers() This method builds all the bit stream layers and then writes them to the output bit stream.
private float	estimateLayerThreshold(int targetBytes, EBCOTLayer lastLayer) This function attempts to estimate a rate-distortion slope threshold which will achieve a target number of code bytes close the `targetBytes' value.
void	finalize() Prints the timing information, if collected, and calls 'finalize' on the super class.
private void	findTruncIndices(int layerIdx, int compIdx, int lvlIdx, int tileIdx, SubbandAn subb, float fthresh, int precinctIdx) This function finds the new truncation points indices for a packet.
private void	getAllCodeBlocks() This method gets all the coded code-blocks from the EBCOT entropy coder for every component and every tile.
private static int	getLimitedSIndexFromSlope(float slope) Returns the index of a slope for the summary table, limiting to the admissible values.
private static float	getSlopeFromSIndex(int index) Returns the minimum slope value associated with a summary table index.
void	initialize() Initializes the layers array.
private float	optimizeBitstreamLayer(int layerIdx, float fmaxt, int maxBytes, int prevBytes) This function implements the rate-distortion optimization algorithm.
void	runAndWrite() Runs the rate allocation algorithm and writes the data to the bit stream writer object provided to the constructor.
void	writeCompPosResLy(int t, int rs, int re, int cs, int ce, int[][] lys, int lye) Write a piece of bit stream according to the COMP_POS_RES_LY_PROG progression mode and between given bounds
void	writeLyResCompPos(int t, int rs, int re, int cs, int ce, int[][] lys, int lye) Write a piece of bit stream according to the LY_RES_COMP_POS_PROG progression mode and between given bounds
void	writePosCompResLy(int t, int rs, int re, int cs, int ce, int[][] lys, int lye) Write a piece of bit stream according to the COMP_POS_RES_LY_PROG progression mode and between given bounds
void	writeResLyCompPos(int t, int rs, int re, int cs, int ce, int[][] lys, int lye) Write a piece of bit stream according to the RES_LY_COMP_POS_PROG progression mode and between given bounds
void	writeResPosCompLy(int t, int rs, int re, int cs, int ce, int[][] lys, int lye) Write a piece of bit stream according to the RES_POS_COMP_LY_PROG progression mode and between given bounds

Methods inherited from class jj2000.j2k.entropy.encoder.PostCompRateAllocator

createInstance, getNumLayers, getParameterInfo, setHeaderEncoder

Methods inherited from class jj2000.j2k.image.ImgDataAdapter

getCompImgHeight, getCompImgWidth, getCompSubsX, getCompSubsY, getCompULX, getCompULY, getImgHeight, getImgULX, getImgULY, getImgWidth, getNomRangeBits, getNomTileHeight, getNomTileWidth, getNumComps, getNumTiles, getNumTiles, getTile, getTileCompHeight, getTileCompWidth, getTileHeight, getTileIdx, getTilePartULX, getTilePartULY, getTileWidth, nextTile, setTile

Methods inherited from class java.lang.Object

clone, equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

DO_TIMING

private static final boolean DO_TIMING

Whether to collect timing information or not: false. Used as a compile time directive.

See Also:

Constant Field Values

initTime

private long initTime

The wall time for the initialization.

buildTime

private long buildTime

The wall time for the building of layers.

writeTime

private long writeTime

The wall time for the writing of layers.

cblks

private CBlkRateDistStats[][][][][] cblks

5D Array containing all the coded code-blocks:

• 1st index: tile index
• 2nd index: component index
• 3rd index: resolution level index
• 4th index: subband index
• 5th index: code-block index

truncIdxs

private int[][][][][][] truncIdxs

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.

• 1st index: tile index
• 2nd index: layer index
• 3rd index: component index
• 4th index: resolution level index
• 5th index: subband index
• 6th index: code-block index

numPrec

private Coord[][][] numPrec

Number of precincts in each resolution level:

• 1st dim: tile index.
• 2nd dim: component index.
• 3nd dim: resolution level index.

layers

private EBCOTLayer[] layers

Array containing the layers information.

LOG2

private static final double LOG2

The log of 2, natural base

RD_SUMMARY_OFF

private static final int RD_SUMMARY_OFF

The normalization offset for the R-D summary table

See Also:

Constant Field Values

RD_SUMMARY_SIZE

private static final int RD_SUMMARY_SIZE

The size of the summary table

See Also:

Constant Field Values

FLOAT_REL_PRECISION

private static final float FLOAT_REL_PRECISION

The relative precision for float data. This is the relative tolerance up to which the layer slope thresholds are calculated.

See Also:

Constant Field Values

FLOAT_ABS_PRECISION

private static final float FLOAT_ABS_PRECISION

The precision for float data type, in an absolute sense. Two float numbers are considered "equal" if they are within this precision.

See Also:

Constant Field Values

MIN_AVG_PACKET_SZ

private static final int MIN_AVG_PACKET_SZ

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.

See Also:

Constant Field Values

RDSlopesRates

private int[] RDSlopesRates

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.

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.

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.

pktEnc

private PktEncoder pktEnc

Packet encoder.

lyrSpec

private LayersInfo lyrSpec

The layer specifications

maxSlope

private float maxSlope

The maximum slope accross all code-blocks and truncation points.

minSlope

private float minSlope

The minimum slope accross all code-blocks and truncation points.

Constructor Detail

EBCOTRateAllocator

public EBCOTRateAllocator(CodedCBlkDataSrcEnc src,
                          LayersInfo lyrs,
                          CodestreamWriter writer,
                          EncoderSpecs encSpec,
                          ParameterList pl)

Initializes the EBCOT rate allocator of entropy coded data. The layout of layers, and their bitrate constraints, is specified by the 'lyrs' parameter.

Parameters:

src - The source of entropy coded data.

lyrs - The layers layout specification.

writer - The bit stream writer.

See Also:

ProgressionType

Method Detail

finalize

public void finalize()
              throws java.lang.Throwable

Prints the timing information, if collected, and calls 'finalize' on the super class.

Overrides:

finalize in class java.lang.Object

java.lang.Throwable

runAndWrite

public void runAndWrite()
                 throws java.io.IOException

Runs the rate allocation algorithm and writes the data to the bit stream writer object provided to the constructor.

Specified by:

runAndWrite in class PostCompRateAllocator

java.io.IOException

See Also:

PostCompRateAllocator.initialize()

initialize

public void initialize()
                throws java.io.IOException

Initializes the layers array. This must be called after the main header has been entirely written or simulated, so as to take its overhead into account. This method will get all the code-blocks and then initialize the target bitrates for each layer, according to the specifications.

Specified by:

initialize in class PostCompRateAllocator

java.io.IOException

See Also:

PostCompRateAllocator.runAndWrite()

getAllCodeBlocks

private void getAllCodeBlocks()

This method gets all the coded code-blocks from the EBCOT entropy coder for every component and every tile. Each coded code-block is stored in a 5D array according to the component, the resolution level, the tile, the subband it belongs and its position in the subband.

For each code-block, the valid slopes are computed and converted into the mantissa-exponent representation.

buildAndWriteLayers

private void buildAndWriteLayers()
                          throws java.io.IOException

This method builds all the bit stream layers and then writes them to the output bit stream. Firstly it builds all the layers by computing the threshold according to the layer target bit-rate, and then it writes the layer bit streams according to the progressive type.

java.io.IOException

writeResLyCompPos

public void writeResLyCompPos(int t,
                              int rs,
                              int re,
                              int cs,
                              int ce,
                              int[][] lys,
                              int lye)
                       throws java.io.IOException

Write a piece of bit stream according to the RES_LY_COMP_POS_PROG progression mode and between given bounds

Parameters:

t - Tile index.

rs - First resolution level index.

re - Last resolution level index.

cs - First component index.

ce - Last component index.

lys - First layer index for each component and resolution.

lye - Index of the last layer.

java.io.IOException

writeLyResCompPos

public void writeLyResCompPos(int t,
                              int rs,
                              int re,
                              int cs,
                              int ce,
                              int[][] lys,
                              int lye)
                       throws java.io.IOException

Write a piece of bit stream according to the LY_RES_COMP_POS_PROG progression mode and between given bounds

Parameters:

t - Tile index.

rs - First resolution level index.

re - Last resolution level index.

cs - First component index.

ce - Last component index.

lys - First layer index for each component and resolution.

lye - Index of the last layer.

java.io.IOException

writePosCompResLy

public void writePosCompResLy(int t,
                              int rs,
                              int re,
                              int cs,
                              int ce,
                              int[][] lys,
                              int lye)
                       throws java.io.IOException

Write a piece of bit stream according to the COMP_POS_RES_LY_PROG progression mode and between given bounds

Parameters:

t - Tile index.

rs - First resolution level index.

re - Last resolution level index.

cs - First component index.

ce - Last component index.

lys - First layer index for each component and resolution.

lye - Index of the last layer.

java.io.IOException

writeCompPosResLy

public void writeCompPosResLy(int t,
                              int rs,
                              int re,
                              int cs,
                              int ce,
                              int[][] lys,
                              int lye)
                       throws java.io.IOException

Write a piece of bit stream according to the COMP_POS_RES_LY_PROG progression mode and between given bounds

Parameters:

t - Tile index.

rs - First resolution level index.

re - Last resolution level index.

cs - First component index.

ce - Last component index.

lys - First layer index for each component and resolution.

lye - Index of the last layer.

java.io.IOException

writeResPosCompLy

public void writeResPosCompLy(int t,
                              int rs,
                              int re,
                              int cs,
                              int ce,
                              int[][] lys,
                              int lye)
                       throws java.io.IOException

Write a piece of bit stream according to the RES_POS_COMP_LY_PROG progression mode and between given bounds

Parameters:

t - Tile index.

rs - First resolution level index.

re - Last resolution level index.

cs - First component index.

ce - Last component index.

lys - First layer index for each component and resolution.

lye - Last layer index.

java.io.IOException

optimizeBitstreamLayer

private float optimizeBitstreamLayer(int layerIdx,
                                     float fmaxt,
                                     int maxBytes,
                                     int prevBytes)
                              throws java.io.IOException

This function implements the rate-distortion optimization algorithm. It saves the state of any previously generated bit-stream layers and then simulate the formation of a new layer in the bit stream as often as necessary to find the smallest rate-distortion threshold such that the total number of bytes required to represent the layer does not exceed `maxBytes' minus `prevBytes'. It then restores the state of any previously generated bit-stream layers and returns the threshold.

Parameters:

layerIdx - The index of the current layer

fmaxt - The maximum admissible slope value. Normally the threshold slope of the previous layer.

maxBytes - The maximum number of bytes that can be written. It includes the length of the current layer bistream length and all the previous layers bit streams.

prevBytes - The number of bytes of all the previous layers.

Returns:

The value of the slope threshold.

java.io.IOException

estimateLayerThreshold

private float estimateLayerThreshold(int targetBytes,
                                     EBCOTLayer lastLayer)

This function attempts to estimate a rate-distortion slope threshold which will achieve a target number of code bytes close the `targetBytes' value.

Parameters:

targetBytes - The target number of bytes for the current layer

lastLayer - The previous layer information.

Returns:

The value of the slope threshold for the estimated layer

findTruncIndices

private void findTruncIndices(int layerIdx,
                              int compIdx,
                              int lvlIdx,
                              int tileIdx,
                              SubbandAn subb,
                              float fthresh,
                              int precinctIdx)

This function finds the new truncation points indices for a packet. It does so by including the data from the code-blocks in the component, resolution level and tile, associated with a R-D slope which is larger than or equal to 'fthresh'.

Parameters:

layerIdx - The index of the current layer

compIdx - The index of the current component

lvlIdx - The index of the current resolution level

tileIdx - The index of the current tile

subb - The LL subband in the resolution level lvlIdx, which is parent of all the subbands in the packet. Except for resolution level 0 this subband is always a node.

fthresh - The value of the rate-distortion threshold

getLimitedSIndexFromSlope

private static int getLimitedSIndexFromSlope(float slope)

Returns the index of a slope for the summary table, limiting to the admissible values. The index is calculated as RD_SUMMARY_OFF plus the maximum exponent, base 2, that yields a value not larger than the slope itself.

If the value to return is lower than 0, 0 is returned. If it is larger than the maximum table index, then the maximum is returned.

Parameters:

slope - The slope value

Returns:

The index for the summary table of the slope.

getSlopeFromSIndex

private static float getSlopeFromSIndex(int index)

Returns the minimum slope value associated with a summary table index. This minimum slope is just 2^(index-RD_SUMMARY_OFF).

Parameters:

index - The summary index value.

Returns:

The minimum slope value associated with a summary table index.