-1
$\begingroup$

How does arithmetic coding work with images? I understand how it works with textual messages but I don't understand how it works with images.

So with textual data, we use the probabilities of the symbols to divide the interval between 0 and 1 into subintervals and then at each round we choose one of the intervals to be the new interval.

For example, we can code the word "wiki" with fractional value 0.001011 (decimal 0.172). (https://en.wikipedia.org/wiki/Arithmetic_coding)

With images, do we partition the image into subimages? For example 10x10 blocks. Then we count the probabilities of each pixel value in that block and use that as our model. Then subdivide the interval from 0 to 1 into 100 subintervals according to the probabilities. Then we choose one of the subintervals as the new interval, depending on which symbol (pixel value) we are coding? So the pixel values are the symbols and the probabilities of each symbol is the model. Finally, one fractional number represents the whole block of pixels, i. e. 100 pixels.

The reason why I think that we have to partition the image into blocks is that it would result in a huge model if we have to count the probabilities of every pixel value of an image where a pixel can take any value between 0 and 255. Also we should have to subdivide the interval [0, 1) into a huge amount of subintervals. And the final fractional value would require a lot of bits if it would represent an entire image.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

For example 10x10 blocks [...] Then subdivide the interval from 0 to 1 into 100 subintervals according to the probabilities

It appears that you assume that each value coded requires its own range in the original interval.

This is not the case. In arithmetic coding, symbols are coded iteratively, so each time the interval is narrowed, the new narrowed interval becomes the interval the next symbol is coded in:

  1. Divide interval into ranges from 0 to 255.
  2. Pick the one corresponding to your symbol.
  3. Subdivide the selected interval into new ranges from 0 to 255 for the next symbol to be coded.

Arithmetic coders still have an issue with growing model size when coding many symbols though. This is circumvented by limiting the interval limits to some precision, emitting their upper bits into the bitstream when they grow beyond this.

Dividing images into blocks is indeed done, but rather for purposes of modelling (exploiting local differences in characteristics) than to accommodate arithmetic coders. Also, the probabilities used are for most practical use cases residuals from prediction, not raw pixel values.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.