Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compression > #777 > unrolled thread

JBIG2

Back to article view | Back to comp.compression

Contents

  JBIG2 glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-01-17 23:58 +0000
    Re: JBIG2 Thomas Richter <thor@math.tu-berlin.de> - 2012-01-18 09:04 +0100
      Re: JBIG2 glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-01-18 12:53 +0000
    Re: JBIG2 James Dow Allen <jdallen2000@yahoo.com> - 2012-01-18 11:55 -0800
      Re: JBIG2 Sebastian <s.gesemann@gmail.com> - 2012-01-18 12:17 -0800
      Re: JBIG2 Thomas Richter <thor@math.tu-berlin.de> - 2012-01-18 21:59 +0100
        Re: JBIG2 glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-01-18 22:22 +0000
      Re: JBIG2 glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-01-18 22:06 +0000

#777 — JBIG2

It seems that JBIG2 isn't a popular topic here, if anywhere.

I am working with a JBIG2 encoder, processing scanned (mostly) text
pages, and wondering about the positions of the AT pixels.

Specifically, JBIG2 uses an arithmetic coder with a context of 16
different neighbor pixels as predictors. Four of the pixels are
movable, in that their locations are written into the header.

The files I have were scanned at 400dpi, so fairly high for scanned
text, such that the optimal choice for context might be larger 
(farther from the pixel being coded) than the nominal positions.

I wonder if anyone else has studied the optimal positions for
the AT pixels for different types of input files.

-- glen

[toc] | [next] | [standalone]

#779

Am 18.01.2012 00:58, schrieb glen herrmannsfeldt:
> It seems that JBIG2 isn't a popular topic here, if anywhere.
>
> I am working with a JBIG2 encoder, processing scanned (mostly) text
> pages, and wondering about the positions of the AT pixels.
>
> Specifically, JBIG2 uses an arithmetic coder with a context of 16
> different neighbor pixels as predictors. Four of the pixels are
> movable, in that their locations are written into the header.
>
> The files I have were scanned at 400dpi, so fairly high for scanned
> text, such that the optimal choice for context might be larger
> (farther from the pixel being coded) than the nominal positions.
>
> I wonder if anyone else has studied the optimal positions for
> the AT pixels for different types of input files.

Not myself, but certainly in our JBIG sub-committee. One of the reasons 
why JBIG2 left the positioning of the free pixels open is that you can 
tweak the last bit of performance out of the positioning of these 
pixels, and that the algorithms that did this type of smart positioning 
were, to my knowledge, patented and thus could not be included.

My best guess as how to position these pixels would be to observe the 
entropy of the probability distribution conditioned on these pixels, and 
pick the pixel that ensures the lowest entropy. This could certainly be 
extended to an adaptive algorithm, or if feasible, a multi-pass 
algorithm. There are probably heuristics, too, as where to place the 
pixels, but they are unknown to me (not being much of a JBIG guy).

Anyhow, the topic of JBIG is not off-topic at all here, and I'm glad 
someone came with a more elaborate question [rather than the usual 
nonsense we unfortunately see here so often.]

So long,
	Thomas

[toc] | [prev] | [next] | [standalone]

#780

Thomas Richter <thor@math.tu-berlin.de> wrote:
> Am 18.01.2012 00:58, schrieb glen herrmannsfeldt:
>> It seems that JBIG2 isn't a popular topic here, if anywhere.

>> I am working with a JBIG2 encoder, processing scanned (mostly) text
>> pages, and wondering about the positions of the AT pixels.

(snip)
>> I wonder if anyone else has studied the optimal positions for
>> the AT pixels for different types of input files.

> Not myself, but certainly in our JBIG sub-committee. One of the reasons 
> why JBIG2 left the positioning of the free pixels open is that you can 
> tweak the last bit of performance out of the positioning of these 
> pixels, and that the algorithms that did this type of smart positioning 
> were, to my knowledge, patented and thus could not be included.

I hadn't thought about that. I did wonder if the decoders have a fast
path for the nominal positions, such that they would run faster.
(Specifically Adobe reader, as I am writing PDFs with them.)

> My best guess as how to position these pixels would be to observe the 
> entropy of the probability distribution conditioned on these pixels, and 
> pick the pixel that ensures the lowest entropy. This could certainly be 
> extended to an adaptive algorithm, or if feasible, a multi-pass 
> algorithm. There are probably heuristics, too, as where to place the 
> pixels, but they are unknown to me (not being much of a JBIG guy).

So far, I have tried a few different positions, sort of trial and error
convergence. 

Well, from the beginning my program would write out some statistics
at the end, including how many contexts were used, and I was surprised
how small it was.  Maybe a few thousand out of 65536. I had thought
that using more contexts would allow for better prediction, and
so better compression. My tests should that I sometimes get a little
better, and sometimes a little worse, maybe a few percent either way.

> Anyhow, the topic of JBIG is not off-topic at all here, and I'm glad 
> someone came with a more elaborate question [rather than the usual 
> nonsense we unfortunately see here so often.]

It is already pretty slow, so I don't think I want a fully adaptive
algorithm. If I found some positions that did better consistently I
would use those. 

I thought I would ask here before trying something more, in case it
had been done before. Still, I am surprised by how rarely I hear
about JBIG2 being used.

-- glen

[toc] | [prev] | [next] | [standalone]

#782

On Jan 18, 6:58 am, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
> It seems that JBIG2 isn't a popular topic here, if anywhere.

I read about JBIG two decades ago.  Was that similar to JBIG2,
just somewhat simpler?  One minor point on which my recollection
differs:

Gray-scale images, e.g. 4 or 8 bits per pixel, *were* allowed, with
successive planes encoded.  A *VERY* simple trick was used to get
a win:
   Instead of encoding
     [ b0, b1, b2, b3 ]
where b0 os MSB and b3 LSB, they encode
     [ b0, b0 .xor. b1, b1 .xor b2, b2 .xor. b3 ]
where the k'th developed bit (k > 0) has about the entropy of b{k-1}.

> Specifically, JBIG2 uses an arithmetic coder with a context of 16
> different neighbor pixels as predictors....
> I wonder if anyone else has studied the optimal positions for
> the AT pixels for different types of input files.

What kind of predictor do they use?  If it's linear, the win
by switching to non-linear filter would be bigger
than optimizing pixel selection.
(Yes, I realize I'm implying non-conformance.)

James

[toc] | [prev] | [next] | [standalone]

#783

On 18 Jan., 20:55, James Dow Allen wrote:
>
> What kind of predictor do they use?  If it's linear, the win
> by switching to non-linear filter would be bigger
> than optimizing pixel selection.

As far as I know, there is no linear prediction. It's "context-
adaptive binary arithmetic coding". The context is provided by the
surrounding 9 to 16 pixels which have already been coded (making 512
to 65536 contexts) and for each context you have a separate estimate
of the probabilty distribution for the current to-code pixel value.

[toc] | [prev] | [next] | [standalone]

#784

On 18.01.2012 20:55, James Dow Allen wrote:
> On Jan 18, 6:58 am, glen herrmannsfeldt<g...@ugcs.caltech.edu>  wrote:
>> It seems that JBIG2 isn't a popular topic here, if anywhere.
>
> I read about JBIG two decades ago.  Was that similar to JBIG2,
> just somewhat simpler?

JBIG coding can be considered a subset of JBIG2, actually. JBIG2 allows 
also efficient coding of texture (shading) by special modes, and IIRC 
JBIG2 also allows you to build up an alphabet of glyphs (like a font) 
and compress only the errors relative to such a recognized set of 
glyphs. Of course, how to find such glyphs is left open - it is part of 
the implementation.

One minor point on which my recollection
> differs:
>
> Gray-scale images, e.g. 4 or 8 bits per pixel, *were* allowed, with
> successive planes encoded.

I believe we released an improved color version like about five years 
ago, but I was only indirectly involved in it.

> A *VERY* simple trick was used to get
> a win:
>     Instead of encoding
>       [ b0, b1, b2, b3 ]
> where b0 os MSB and b3 LSB, they encode
>       [ b0, b0 .xor. b1, b1 .xor b2, b2 .xor. b3 ]
> where the k'th developed bit (k>  0) has about the entropy of b{k-1}.

This is also known as Grey-code. It's actually a very old trick which 
was originally used in mechanical dials where a simple linear increment 
requires only one bit to change at each time, avoiding synchronization 
problems. This trick is also found in JPEG 2000 "MQ coder bypass coding".

> What kind of predictor do they use?  If it's linear, the win
> by switching to non-linear filter would be bigger
> than optimizing pixel selection.

It is not linear nor non-linear - rather context driven by a set of 
pixels in the causal neighbourhood of the pixel to code. As the pixels 
are binary (thus J-BI-G), the number of contexts remains limited (two 
per pixel - thus 1024 for ten pixels.) IIRC, it was basically a variant 
of the Q-coder that is used here, probably QM for JBIG and MQ for JBIG2, 
but I don't remember exactly.

Greetings,
	Thomas

[toc] | [prev] | [next] | [standalone]

#787

Thomas Richter <thor@math.tu-berlin.de> wrote:
> On 18.01.2012 20:55, James Dow Allen wrote:
>> On Jan 18, 6:58 am, glen herrmannsfeldt<g...@ugcs.caltech.edu>  wrote:
>>> It seems that JBIG2 isn't a popular topic here, if anywhere.

>> I read about JBIG two decades ago.  Was that similar to JBIG2,
>> just somewhat simpler?

> JBIG coding can be considered a subset of JBIG2, actually. JBIG2 allows 
> also efficient coding of texture (shading) by special modes, and IIRC 
> JBIG2 also allows you to build up an alphabet of glyphs (like a font) 
> and compress only the errors relative to such a recognized set of 
> glyphs. Of course, how to find such glyphs is left open - it is part of 
> the implementation.

Yes, I have thought about implementing that one. If you do lossy
coding, choosing the closest glyph, it should save many bits, but
sometimes will give the wrong character. The lossless form, as noted,
codes the difference.

With the generic code, and 16 pixel context, over a set of IBM
computer manuals I get about 40k bytes/page (not counting PDF overhead).

This is on 400dpi scanned images. My thought was that the 16 bit
context pixel positions were all close together, and so weren't
quite as good as they could be at 400dpi. Out of the 65536 possible
contexts, the mean (over 6000 pages) seems to be that 4771 are used.

-- glen

[toc] | [prev] | [next] | [standalone]

#786

James Dow Allen <jdallen2000@yahoo.com> wrote:
> On Jan 18, 6:58 am, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
>> It seems that JBIG2 isn't a popular topic here, if anywhere.

> I read about JBIG two decades ago.  Was that similar to JBIG2,
> just somewhat simpler?  

JBIG2 is the next edition. I don't know exactly how they compare.

> One minor point on which my recollection differs:

> Gray-scale images, e.g. 4 or 8 bits per pixel, *were* allowed, with
> successive planes encoded.  A *VERY* simple trick was used to get
> a win:
>   Instead of encoding
>     [ b0, b1, b2, b3 ]
> where b0 os MSB and b3 LSB, they encode
>     [ b0, b0 .xor. b1, b1 .xor b2, b2 .xor. b3 ]
> where the k'th developed bit (k > 0) has about the entropy of b{k-1}.

I don't remember that one in JBIG2, but then I wasn't looking
for it, either. JBIG2 does allow for halftone images, though.

There are some IBM manuals that use a (halftone) gray over non-standard
features. It seems to come through in the scanned images I have
(using the generic encoder) though not quite as readable as the
original.

>> Specifically, JBIG2 uses an arithmetic coder with a context of 16
>> different neighbor pixels as predictors....
>> I wonder if anyone else has studied the optimal positions for
>> the AT pixels for different types of input files.

> What kind of predictor do they use?  If it's linear, the win
> by switching to non-linear filter would be bigger
> than optimizing pixel selection.
> (Yes, I realize I'm implying non-conformance.)

I think it is linear, though I am not so sure about that.
Conformance is important. JBIG2 is in PDF 1.4, so I can write PDF files
viewable in all modern viewers. 

-- glen

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compression

csiph-web