Enhanced Binary MQ Arithmetic Coder with Look-Up Table
Round 1
Reviewer 1 Report
I think the idea presented by the authors is good and deserves to be published. In my opinion readers would benefit from reading the authors idea.
I have to highlight that this is a paper difficult to check for correctedness (mainly in 10 days). Only the ones really interested in the results will be able to replicate results and discover any flaw --- if there is any.
I believe everything sounds correct and convincing in this paper.
Authors have proposed an improvement and I believe their proposal is serious and correct. It is hard to check if everything is OK but not hard to believe that it is sound and good.
The writing need to be improved. To save the readers from the effort to understand the procedures used by the authors. And I believe they are able to manage it.
SPECIFIC COMMENTS:
- The acronym LPS and MPS should be explicated ion lines 50 and 58. An no explanation needed elsewhere.
- Line 93 - I suggest authors to use the terminology "Range" instead of "section"
- Figure 2 needs two be enlarged (or improved). Hard to read the text in boxes.
- Line 193 - replace 'defined as" by 'envisioned as".
- Line 218: used indexes properly. $Q_{K-1}$ instead of "QK-1". Indexes should be taken care off all over the paper.
- Line 230. replace "eliminate" by "replace". Unless authors really mean "elimination". I understood that M-coder replaces Huffman.
Section 3 is for me the crux of the paper. That's were the authors should concentrate their effort to improve the writing. This is where the contribution lies. A lot of "polishing and improvement is needed here".
For instance
- Lines 235-238. Do the authors mean that with increased computing power a more sophisticated approach (procedure) pays off. Thats the idea conveyed there but "there are needs to improve" which I would rewrite as "there are lots of room for improvement".
- Line 240 - Replace "... section division ..." by "... interval segmentation ..."
- Line 257 - replace "..., A value should ..." by "the value $A$ should"
- Line 263 - replace "... level is 2 ..." by "... levels are two ..."
- Line 267 - replace "... make the quantized value is the center of ..." by " ... set the quantization levels to the interval mid value ..."
And so on.
Author Response
Please see the attachment
Author Response File: Author Response.pdf
Reviewer 2 Report
The paper is dedicated to implementation of adaptive binary arithmetic coding. A more precise look-up table approximation of multiplication for MQ-coder is proposed. Experimental results show that bit rate reduction from 0.3 to 3% is achieved.
Comments to the authors:
- In Introduction (lines 37-41) the authors first mention that the binary arithmetic coding has lower complexity than multi-symbol ones. But then, they mention two implementations by Witten and Langdon which actually multi-symbol ones. I think, it may confuse a reader. I think, it is better, first, to mention about Witten’s and Langdon’s, then write why they have a high complexity, and then mention the binary arithmetic coding. Probably, some parts of Section 3.1 should be mentioned here.
- In Introduction (line 42) the authors write “The most interesting arithmetic coder is the Q coder…” Please explain, why Q-coder is the most interesting AC.
- In general, Introduction does not contain description of the disadvantages of the existing binary arithmetic coders (M-coder, MQ-coder), i.e., the goal of the paper is not clear for a reader, i.e., why we need the new one? Please change it.
- I think, Section 2.1 should be rewritten. “In the 1960s, along with Huffman coding, an arithmetic encoder with a high compression rate was developed.” sounds incorrect, since in theory we can achieve very high compression rate using Huffman coding as well. In order to do it, we need to enlarge the alphabet, i.e., encode the whole message as a one letter of huge alphabet. But it cannot be achieved since the very high complexity of such Huffman code tree building. It was the reason, why the arithmetic coding was developed: it can build the code word for a whole message with an acceptable complexity. The arithmetic coding is based on Gilbert-Moore coding (also called Shannon-Fano-Elisas code) where first |-log P(X)/2|bits of number Q(X)+P(X)/2 represents the code word for message X=(x1,x2,…,xN), where Q(X) is cumulative probability, and P(X) is probability of X. The idea of arithmetic coding is that these Q(X) and P(X) could be easily computed by equations (1) and (2), while in Huffman coding such operation could have infinite complexity for large N.
- In Section 2.7 the authors mention “H.264/AVC is standardized to use M-coder [17] and HEVC adopts M-coder as a default entropy coding to eliminate Huffman coding in the standard video coding [20]”, but H.264/AVC does not use Huffman codes (it uses other VLC codes based on Golomb coding).
- I think the related works section should be expanded. First of all, the authors should mention adaptive binary arithmetic and range coding based on virtual sliding window [b,c]. The both coders can change the balance between probability estimation speed and precision by changing the window size. Please also refer modifications of AC from [e] and logarithmic aritmetic coding from [d]. Finally, novel solutions based on neural networks should be also noticed, for example [f].
[b] E. Belyaev, A. Turlikov, K. Egiazarian and M. Gabbouj, "An Efficient Adaptive Binary Arithmetic Coderw with Low Memory Requirement," IEEE Journal of Selected Topics in Signal Processing, 2013.
[c] E. Belyaev, K. Liu, M. Gabbouj and Y. Li, "An Efficient Adaptive Binary Range Coder and Its VLSI Architecture," in IEEE Transactions on Circuits and Systems for Video Technology, 2015.
[d] F. Aulí-Llinàs, "Highly efficient, low complexity arithmetic coder for JPEG2000," 2014 IEEE International Conference on Image Processing (ICIP), 2014.
[e] B. Niu et al., "An Efficient Probability Estimation Design for Logarithmic Binary Arithmetic Coding," Picture Coding Symposium (PCS), 2019.
[f] C. Ma, D. Liu, X. Peng, L. Li and F. Wu, "Convolutional Neural Network-Based Arithmetic Coding for HEVC Intra-Predicted Residues," IEEE Transactions on Circuits and Systems for Video Technology, 2020.
- In experimental results, it would be nice to compare the proposed improved MQ-coder with existing binary coders, i.e., it could be useful to compare redundancy for different binary sources as it was done in TABLE IX in [c]. I think such table will clearly show the advantages of the proposed coder.
- Figure 2 has low resolution. Please make it better.
Author Response
Please see the attachment.
Author Response File: Author Response.pdf
Reviewer 3 Report
Line 306, “and the parameter α and β are set to find the optimal quantization value 306 through experiment.” Please explain in detail the procedure of finding the “optimal values of alpha and beta”. What is the metric used during this optimization procedure? Given a new dataset, how does a user know what values of should be used. Any guidelines?
Other issues: Line 30: using fractional decimal, value a method -> decimal value, a method
Line 34: Insert space in between, in many places in the paper: for example: Rissanen[3] -> Rissanen [3]
Line 48: consecutive 1’s occurs (-> occur), 0’s is (-> are) inserted.
Line 49: process (-> process) of
Line 91: Let me briefly look at the -> Let us briefly review the Equations (1) and (2); the minus signs should have the same length
Line 97-98: cumulative distribution function (cumulative distribution function): remove the repetition.
Line 102: is applied is expressed (-> is expressed) Equation (3): AxQe -> A x Qe (add spaces)
Line 136: In equation(s) (3) and (4)
Line 158: 0.75(=0x8000) -> 0.75 (= 0x8000) Figure 2: the plots are hard to read – need to increase resolution
Line 202: JPEG, has 112 -> JPEG with 112
Line 216: D = [2^(b-2),2^(b-1)), replace ^(b-2) with superscripted text
Line 219: K = 2K -> 2^K Line 225: ┤| means what?
Line 228: with b is (->being) 10
Line 253 – 254, this shortcomings > shortcoming
Line 267: quantized value is (->be) the center
Line 273: α and β value (s), (the) compression
Author Response
Please see the attachment.
Author Response File: Author Response.pdf
Round 2
Reviewer 1 Report
A few more suggestions to improve the witing.
LINE 27. Replace "In theory, ... high compression rate ... Huffman" by "In theory, close to optimal compression rate can be obtained using Huffman coding."
Not a big deal (not a catastrophic mistake) but clear writing is imperative.
It is a hard task but it pays off --- one learns with practice. That is teh reason why I am insisting.
LINE 37. Improve the whole text that begin with "Arithmetic coding has the disadvantage of increasing precision by ... has also been developed." and ends with " ... is normalized."
My guess is that what the authors are trying to say is:
"To circumvent the precision problem posed by the partitioning of the real interval $[0,1]$ in Arithmetic Coding, one uses instead the set of integers [0, N]. To handle the precision issue a renormalization is performed and output bits are used to indicate that normalization has occurred"
LINE 147. Replace "Let us call the current RANGE (Lower, Upper)" by "Let us say that the current range is represented by the interval $(Lower, Upper)$". Let the initial range be (Lower, Upper) = [0,1)."
LINE 272. The set Q on Line 270 has elements properly indexed. Use the same typesetting to write the set $P$ in line 272 with proper indexing. It will help the reader,
LINES 272. Same comment apply to p_LPS. In latex I would typeset using $p_{LPS}$.
And so on.
I will not suggest further changes. I advise the authors to take same time and attempt to express the idea as clearly as possible. As a reader I could guess what the authors meant. But it should not be like this, the authors should be thorough and leave no guessing for the readers.
Author Response
Please see the attached file.
Author Response File: Author Response.pdf
Reviewer 2 Report
I'm satisfied with the answers.
Author Response
Thank you so much for your sincere review.