|
||||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | |||||||||
java.lang.Object | +--jj2000.j2k.entropy.encoder.MQCoder
This class implements the MQ arithmetic coder. When initialized a specific state can be specified for each context, which may be adapted to the probability distribution that is expected for that context.
The type of length calculation and termination can be chosen at construction time. ---- Tricks that have been tried to improve speed ----
1) Merging Qe and mPS and doubling the lookup tables
Merge the mPS into Qe, as the sign bit (if Qe>=0 the sense of MPS is 0, if
Qe<0 the sense is 1), and double the lookup tables. The first half of the
lookup tables correspond to Qe>=0 (i.e. the sense of MPS is 0) and the
second half to Qe<0 (i.e. the sense of MPS is 1). The nLPS lookup table is
modified to incorporate the changes in the sense of MPS, by making it jump
from the first to the second half and vice-versa, when a change is
specified by the swicthLM lookup table. See JPEG book, section 13.2, page
225.
There is NO speed improvement in doing this, actually there is a slight
decrease, probably due to the fact that often Q has to be negated. Also the
fact that a brach of the type "if (bit==mPS[li])" is replaced by two
simpler braches of the type "if (bit==0)" and "if (q<0)" may contribute to
that.
2) Removing cT
It is possible to remove the cT counter by setting a flag bit in the high
bits of the C register. This bit will be automatically shifted left
whenever a renormalization shift occurs, which is equivalent to decreasing
cT. When the flag bit reaches the sign bit (leftmost bit), which is
equivalenet to cT==0, the byteOut() procedure is called. This test can be
done efficiently with "c<0" since C is a signed quantity. Care must be
taken in byteOut() to reset the bit in order to not interfere with other
bits in the C register. See JPEG book, page 228.
There is NO speed improvement in doing this. I don't really know why since
the number of operations whenever a renormalization occurs is
decreased. Maybe it is due to the number of extra operations in the
byteOut(), terminate() and getNumCodedBytes() procedures.
3) Change the convention of MPS and LPS.
Making the LPS interval be above the MPS interval (MQ coder convention is
the opposite) can reduce the number of operations along the MPS path. In
order to generate the same bit stream as with the MQ convention the output
bytes need to be modified accordingly. The basic rule for this is that C =
(C'^0xFF...FF)-A, where C is the codestream for the MQ convention and C' is
the codestream generated by this other convention. Note that this affects
bit-stuffing as well.
This has not been tested yet.
4) Removing normalization while loop on MPS path
Since in the MPS path Q is guaranteed to be always greater than 0x4000
(decimal 0.375) it is never necessary to do more than 1 renormalization
shift. Therefore the test of the while loop, and the loop itself, can be
removed.
5) Simplifying test on A register
Since A is always less than or equal to 0xFFFF, the test "(a & 0x8000)==0"
can be replaced by the simplete test "a < 0x8000". This test is simpler in
Java since it involves only 1 operation (although the original test can be
converted to only one operation by smart Just-In-Time compilers)
This change has been integrated in the decoding procedures.
6) Speedup mode
Implemented a method that uses the speedup mode of the MQ-coder if
possible. This should greately improve performance when coding long runs of
MPS symbols that have high probability. However, to take advantage of this,
the entropy coder implementation has to explicetely use it. The generated
bit stream is the same as if no speedup mode would have been used.
Implemented but performance not tested yet.
7) Multiple-symbol coding
Since the time spent in a method call is non-negligable, coding several
symbols with one method call reduces the overhead per coded symbol. The
decodeSymbols() method implements this. However, to take advantage of it,
the implementation of the entropy coder has to explicitely use it.
Implemented but performance not tested yet.
| Field Summary | |
(package private) int |
a
The current interval |
(package private) int |
b
The last encoded byte of data |
(package private) int |
c
The current bit code |
(package private) int |
cT
The bit code counter |
(package private) boolean |
delFF
If a 0xFF byte has been delayed and not yet been written to the output (in the MQ we can never have more than 1 0xFF byte in a row). |
(package private) int[] |
I
The current index of each context |
(package private) int[] |
initStates
The initial state of each context |
static int |
LENGTH_LAZY
Identifier for the lazy length calculation. |
static int |
LENGTH_LAZY_GOOD
Identifier for a very simple length calculation. |
static int |
LENGTH_NEAR_OPT
Identifier for the near optimal length calculation. |
(package private) int |
ltype
The length calculation type to use. |
(package private) int[] |
mPS
The current most probable signal for each context |
(package private) static int[] |
nLPS
The indexes of the next LPS |
(package private) static int[] |
nMPS
The indexes of the next MPS |
(package private) int |
nrOfWrittenBytes
The number of written bytes so far, excluding any delayed 0xFF bytes. |
(package private) int |
nSaved
Number of saved states. |
(package private) ByteOutputBuffer |
out
The ByteOutputBuffer used to write the compressed bit stream. |
(package private) static int[] |
qe
The data structures containing the probabilities for the LPS |
(package private) static int |
SAVED_INC
The increase in length for the arrays to save states |
(package private) static int |
SAVED_LEN
The initial length of the arrays to save sates |
(package private) int[] |
savedA
Saved values of the A register. |
(package private) int[] |
savedB
Saved values of the B byte buffer. |
(package private) int[] |
savedC
Saved values of the C register. |
(package private) int[] |
savedCT
Saved values of CT counter. |
(package private) boolean[] |
savedDelFF
Saved values of the delFF (i.e. |
(package private) static int[] |
switchLM
Whether LPS and MPS should be switched |
static int |
TERM_EASY
The identifier for the easy termination that is simpler than the 'TERM_NEAR_OPT' one but slightly less efficient. |
static int |
TERM_FULL
The identifier fort the termination that uses a full flush. |
static int |
TERM_NEAR_OPT
The identifier for the termination that uses the near optimal length calculation to terminate the arithmetic codewrod |
static int |
TERM_PRED_ER
The identifier for the predictable termination policy for error resilience. |
(package private) int |
ttype
The termination type to use. |
| Constructor Summary | |
MQCoder(ByteOutputBuffer oStream,
int nrOfContexts,
int[] init)
Instantiates a new MQ-coder, with the specified number of contexts and initial states. |
|
| Method Summary | |
private void |
byteOut()
This function puts one byte of compressed bits in the output stream. |
void |
codeSymbol(int bit,
int context)
This function performs the arithmetic encoding of one symbol. |
void |
codeSymbols(int[] bits,
int[] cX,
int n)
This function performs the arithmetic encoding of several symbols together. |
void |
fastCodeSymbols(int bit,
int ctxt,
int n)
This method performs the coding of the symbol 'bit', using context 'ctxt', 'n' times, using the MQ-coder speedup mode if possible. |
void |
finishLengthCalculation(int[] rates,
int n)
Terminates the calculation of the required length for each coding pass. |
int |
getNumCodedBytes()
Returns the number of bytes that are necessary from the compressed output stream to decode all the symbols that have been coded this far. |
int |
getNumCtxts()
Returns the number of contexts in the arithmetic coder. |
void |
reset()
Reinitializes the MQ coder and the underlying 'ByteOutputBuffer' buffer as if a new object was instantaited. |
void |
resetCtxt(int c)
Resets a context to the original probability distribution, and sets its more probable symbol to 0. |
void |
resetCtxts()
Resets all contexts to their original probability distribution and sets all more probable symbols to 0. |
private void |
saveState()
Saves the current state of the MQ coder (just the registers, not the contexts) so that a near optimal length calculation can be performed later. |
void |
setLenCalcType(int ltype)
Set the length calculation type to the specified type. |
void |
setTermType(int ttype)
Set termination type to the specified type. |
int |
terminate()
This function flushes the remaining encoded bits and makes sure that enough information is written to the bit stream to be able to finish decoding, and then it reinitializes the internal state of the MQ coder but without modifying the context states. |
| Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
| Field Detail |
public static final int LENGTH_LAZY
public static final int LENGTH_LAZY_GOOD
public static final int LENGTH_NEAR_OPT
public static final int TERM_FULL
public static final int TERM_NEAR_OPT
public static final int TERM_EASY
public static final int TERM_PRED_ER
static final int[] qe
static final int[] nMPS
static final int[] nLPS
static final int[] switchLM
ByteOutputBuffer out
int[] mPS
int[] I
int c
int cT
int a
int b
boolean delFF
int nrOfWrittenBytes
int[] initStates
int ttype
int ltype
int[] savedC
int[] savedCT
int[] savedA
int[] savedB
boolean[] savedDelFF
int nSaved
static final int SAVED_LEN
static final int SAVED_INC
| Constructor Detail |
public MQCoder(ByteOutputBuffer oStream,
int nrOfContexts,
int[] init)
oStream - where to output the compressed data.nrOfContexts - The number of contexts used by the MQ coder.init - The initial state for each context. A reference is kept to
this array to reinitialize the contexts whenever 'reset()' or
'resetCtxts()' is called.| Method Detail |
public void setLenCalcType(int ltype)
ltype - The type of length calculation to use. One of
'LENGTH_LAZY', 'LENGTH_LAZY_GOOD' or 'LENGTH_NEAR_OPT'.public void setTermType(int ttype)
ttype - The type of termination to use. One of 'TERM_FULL',
'TERM_NEAR_OPT', 'TERM_EASY' or 'TERM_PRED_ER'.
public final void fastCodeSymbols(int bit,
int ctxt,
int n)
If the symbol 'bit' is the current more probable symbol (MPS) and qe[ctxt]<=0x4000, and (A-0x8000)>=qe[ctxt], speedup mode will be used. Otherwise the normal mode will be used. The speedup mode can significantly improve the speed of arithmetic coding when several MPS symbols, with a high probability distribution, must be coded with the same context. The generated bit stream is the same as if the normal mode was used.
This method is also faster than the 'codeSymbols()' and 'codeSymbol()' ones, for coding the same symbols with the same context several times, when speedup mode can not be used, although not significantly.
bit - The symbol do code, 0 or 1.ctxt - The context to us in coding the symbol.n - The number of times that the symbol must be coded.
public final void codeSymbols(int[] bits,
int[] cX,
int n)
The advantage of using this function is that the cost of the method call is amortized by the number of coded symbols per method call.
Each context has a current MPS and an index describing what the current probability is for the LPS. Each bit is encoded and if the probability of the LPS exceeds .5, the MPS and LPS are switched.
bits - An array containing the symbols to be encoded. Valid
symbols are 0 and 1.cX - The context for each of the symbols to be encoded.n - The number of symbols to encode.
public final void codeSymbol(int bit,
int context)
Each context has a current MPS and an index describing what the current probability is for the LPS. Each bit is encoded and if the probability of the LPS exceeds .5, the MPS and LPS are switched.
bit - The symbol to be encoded, must be 0 or 1.context - the context with which to encode the symbol.private void byteOut()
public int terminate()
After calling this method the 'finishLengthCalculation()' method should be called, after compensating the returned length for the length of previous coded segments, so that the length calculation is finalized.
The type of termination used depends on the one specified at the constructor.
public final int getNumCtxts()
public final void resetCtxt(int c)
c - The number of the context (it starts at 0).public final void resetCtxts()
public final int getNumCodedBytes()
The values returned by this method are then to be used in finishing the length calculation with the 'finishLengthCalculation()' method, after compensation of the offset in the number of bytes due to previous terminated segments.
This method should not be called if the current coding pass is to be terminated. The 'terminate()' method should be called instead.
The calculation is done based on the type of length calculation specified at the constructor.
public final void reset()
private void saveState()
public void finishLengthCalculation(int[] rates,
int n)
The values in 'rates' must have been compensated for any offset due to previous terminated segments, so that the correct index to the stored coded data is used.
rates - The array containing the values returned by
'getNumCodedBytes()' for each coding pass.n - The index in the 'rates' array of the last terminated length.
|
||||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | |||||||||