JBIG2

From HandWiki
Short description: Image file format
JBIG2
Developed byJoint Bi-level Image Experts Group
Latest release
2
Contained byPortable Document Format, FAX
StandardITU T.88 & ISO/IEC 14492

JBIG2 is an image compression standard for bi-level images, developed by the Joint Bi-level Image Experts Group. It is suitable for both lossless and lossy compression. According to a press release[1] from the Group, in its lossless mode JBIG2 typically generates files 3–5 times smaller than Fax Group 4 and 2–4 times smaller than JBIG, the previous bi-level compression standard released by the Group. JBIG2 was published in 2000 as the international standard ITU T.88,[2] and in 2001 as ISO/IEC 14492.[3]

Functionality

Ideally, a JBIG2 encoder will segment the input page into regions of text, regions of halftone images, and regions of other data. Regions that are neither text nor halftones are typically compressed using a context-dependent arithmetic coding algorithm called the MQ coder. Textual regions are compressed as follows: the foreground pixels in the regions are grouped into symbols. A dictionary of symbols is then created and encoded, typically also using context-dependent arithmetic coding, and the regions are encoded by describing which symbols appear where. Typically, a symbol will correspond to a character of text, but this is not required by the compression method. For lossy compression the difference between similar symbols (e.g., slightly different impressions of the same letter) can be neglected; for lossless compression, this difference is taken into account by compressing one similar symbol using another as a template. Halftone images may be compressed by reconstructing the grayscale image used to generate the halftone and then sending this image together with a dictionary of halftone patterns.[4] Overall, the algorithm used by JBIG2 to compress text is very similar to the JB2 compression scheme used in the DjVu file format for coding binary images.

PDF files versions 1.4 and above may contain JBIG2-compressed data. Open-source decoders for JBIG2 are jbig2dec[5] (AGPL), the java-based jbig2-imageio[6] (Apache-2), the JavaScript-based jbig2.js[7] (Apache-2), and the decoder by Glyph & Cog LLC found in Xpdf and Poppler[8] (both GPL). An open-source encoder is jbig2enc[9] (Apache-2).

Technical details

Typically, a bi-level image consists mainly of a large amount of textual and halftone data, in which the same shapes appear repeatedly. The bi-level image is segmented into three regions: text, halftone, and generic regions. Each region is coded differently and the coding methodologies are described in the following passage.

Text image data

Text coding is based on the nature of human visual interpretation. A human observer cannot tell the difference between two instances of the same characters in a bi-level image even though they may not exactly match pixel by pixel. Therefore, only the bitmap of one representative character instance needs to be coded instead of coding the bitmaps of each occurrence of the same character individually. For each character instance, the coded instance of the character is then stored into a "symbol dictionary".[10] There are two encoding methods for text image data: pattern matching and substitution (PM&S) and soft pattern matching (SPM).[11]

Block diagrams of (left) pattern matching and substitution method and (right) soft pattern matching method

Pattern matching and substitution (PM&S) is the more classic coding method. The encoder performs image segmentation to isolate character-sized chunks. For each individual chunk, the encoder looks for a match in the bitmap dictionary. If a match exists, we code an index of the corresponding representative bitmap in the dictionary and the position of the character on the page. The position is usually relative to another previously coded character. If a match is not found, the segmented pixel block is coded directly and added into the dictionary. Typical procedures of pattern matching and substitution algorithm are displayed in the left block diagram of the figure above. Although the method of PM&S can achieve outstanding compression, substitution errors could be made during the process if the image resolution is low.[11]

JBIG2 improves on PM&S with optional soft pattern matching (SPM). The same segmentation and searching is performed, but for each found match, the encoder saves not only the corresponding dictionary entry, but also refinement data describing the difference between the actual chunk and the dictionary chunk. Doing so greatly reduces substitution errors.[10][lower-alpha 1] Since the dictionary match requires that the actual character and the dictionary character are highly similar, SPM only adds a tiny amount of data.[11]

Halftones

Halftone images can be compressed using two methods. One of the methods is similar to the context-based arithmetic coding algorithm, which adaptively positions the template pixels in order to obtain correlations between the adjacent pixels. In the second method, descreening is performed on the halftone image so that the image is converted back to grayscale. The converted grayscale values are then used as indexes of fixed-sized tiny bitmap patterns contained in a halftone bitmap dictionary. This allows decoder to successfully render a halftone image by presenting indexed dictionary bitmap patterns neighboring with each other.[10]

Entropy coding

All three region types including text, halftone, and generic regions may all use arithmetic coding or huffman coding. JBIG2 specifically uses the MQ coder, the same entropy encoder employed by JPEG 2000.

Patents

Patents for JBIG2 are owned by IBM and Mitsubishi. Free licenses should be available after a request. JBIG and JBIG2 patents are not the same.[13][14][15]

Character substitution errors in scanned documents

JBIG2 compression can potentially alter the actual characters in text in documents that are scanned to PDF. This is in contrast to some other algorithms, which simply degrade into a blur, making the compression artifacts obvious.[16] Since JBIG2 uses "pattern matching" by matching up similar-looking symbols, the numbers "6" and "8" may get replaced, for example, especially if used as a more aggressive (higher) compression option.[17]

In 2013, various substitutions (including replacing "6" with "8") were reported to happen on many Xerox Workcentre photocopier and printer machines. Numbers printed on scanned (but not OCR-ed) documents had potentially been altered. This has been demonstrated on construction blueprints and some tables of numbers; the potential impact of such substitution errors in documents such as medical prescriptions was briefly mentioned.[18][19][20] German computer scientist David Kriesel and Xerox were investigating this.[21][22]

Xerox subsequently acknowledged that this was a long-standing software defect, and their initial statements in suggesting that only non-factory settings could introduce the substitution were incorrect. No attempt was made to recall or mandate updates to the affected devices – which was acknowledged to affect more than a dozen product families. However, in August 2013 a software patch was made available, that when installed, automatically disabled pattern matching.[17] Documents previously scanned continue to potentially contain errors making their veracity difficult to substantiate. Following publicity about the potential for errors authorities in some countries made statements to prevent the use of JBIG2.[23]

In Germany the Federal Office for Information Security has issued a technical guideline that says the JBIG2 encoding "MUST NOT be used" for "replacement scanning".[24] In Switzerland the Coordination Office for the Permanent Archiving of Electronic Documents (Koordinationsstelle für die dauerhafte Archivierung elektronischer Unterlagen) has recommended against the use of JBIG2 when creating PDF documents.[25]

Exploit

A vulnerability in the Xpdf implementation of JBIG2, re-used in Apple's iOS phone operating software, was used by the Pegasus spyware to implement a zero-click attack on iPhones by constructing an emulated computer architecture inside a JBIG2 stream. Apple fixed this "FORCEDENTRY" vulnerability in iOS 14.8 in September 2021.[26]

References

  1. ↑ If the refinement data is used without any threshold of difference, encoding would be completely lossless. This could be less efficient than just tagging the whole page as a "generic region" for direct arithmetic coding.[12]
  1. ↑ Press release from the Joint Bi-level Image experts Group .
  2. ↑ "ITU-T Recommendation T.88 – T.88 : Information technology - Coded representation of picture and audio information - Lossy/lossless coding of bi-level images". http://www.itu.int/rec/T-REC-T.88. 
  3. ↑ "ISO/IEC 14492:2001 – Information technology – Lossy/lossless coding of bi-level images". http://www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm?csnumber=22394. 
  4. ↑ JBIG2-the ultimate bi-level image coding standard, by F. Ono, W. Rucklidge, R. Arps, and C. Constantinescu, in Proceedings, 2000 International Conference on Image Processing (Vancouver, BC, Canada), vol. 1, pp. 140–143.
  5. ↑ jbig2dec decoder home page.
  6. ↑ jbig2-imageio decoder plugin for Java's ImageIO.
  7. ↑ jbig2.js decoder for PDF.js.
  8. ↑ JBIG2Stream decoder by Glyph & Cog LLC.
  9. ↑ jbig2enc encoder project home.
  10. ↑ 10.0 10.1 10.2 F. Ono, W. Rucklidge, R. Arps, and C. Constantinescu, "JBIG2-the ultimate bi-level image coding standard", Image Processing, 2000. Proceedings. 2000 International Conference on , vol. 1, pp. 140–143 vol. 1, 2000.
  11. ↑ 11.0 11.1 11.2 P. Howard, F. Kossentini, B. Martins, S. Forchhammer, and W. Rucklidge, "The emerging JBIG2 standard", Circuits and Systems for Video Technology, IEEE Transactions on , vol. 8, no. 7, pp. 838–848, Nov 1998.
  12. ↑ Langley, Adam. "jbig2enc: Documentation". https://github.com/agl/jbig2enc/blob/ea6a40a2cbf05efb00f3418f2d0ad71232565beb/doc/jbig2enc.html. "We can choose to do this for each symbol on the page, so we don't have to refine when we are only a couple of pixel off. If we refine whenever we [sic] a wrong pixel, we have lossless encoding using symbols." 
  13. ↑ What is the patent situation with JBIG?, http://www.jpeg.org/jbig/faq.phtml?action=show_answer&question_id=q3f042a7298c94 
  14. ↑ What is JBIG2?, http://www.swiftview.com/pclcorner/pclcorner1.htm#JBIG2, retrieved 2012-04-07 
  15. ↑ JBIG2 patents, http://www.archivum.info/comp.compression/2009-07/00024/Re-JBIG2-patents.html, retrieved 2012-04-07 
  16. ↑ Zhou Wang, Hamid R. Sheikh and Alan C. Bovik (2002). "No-reference perceptual quality assessment of JPEG compressed images". Proceedings 2002 International Conference on Image Processing. http://signal.ece.utexas.edu/~zwang/papers/icip02.pdf. 
  17. ↑ 17.0 17.1 Xerox Corporation. Scanning and Compression White Paper, 2013
  18. ↑ "Xerox scanners/photocopiers randomly alter numbers in scanned documents". 2013-08-02. http://www.dkriesel.com/en/blog/2013/0802_xerox-workcentres_are_switching_written_numbers_when_scanning. 
  19. ↑ "Confused Xerox copiers rewrite documents, expert finds". BBC News. 2013-08-06. https://www.bbc.co.uk/news/technology-23588202. 
  20. ↑ "Xerox Scanners / Photocopiers Randomly Alter Numbers". 5 August 2013. http://fontfeed.com/archives/xerox-scanners%E2%80%8A%E2%80%8Aphotocopiers-randomly-alter-numbers/. 
  21. ↑ "Xerox investigating latest mangling test findings". 2013-08-11. http://www.dkriesel.com/en/blog/2013/0810_xerox_investigating_latest_mangling_test_findings. 
  22. ↑ Update on Scanning Issue: Software Patches To Come, Xerox (blog), 2013-08-11, http://realbusinessatxerox.blogs.xerox.com/2013/08/07/update-on-scanning-issue-software-patches-to-come/, retrieved 2013-08-11 
  23. ↑ Kriesel, David. "Video and Slides of my Xerox Talk at 31C3". https://www.dkriesel.com/en/blog/2014/1229_video_meines_vortrags_auf_dem_31c3. 
    Note: The video there is dubbed over in English; if you understand German, the original might be easier to follow: David Kriesel: Traue keinem Scan, den du nicht selbst gefälscht hast
  24. ↑ "BSI Technical Guidelines 03138: Replacement Scanning". https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/TechGuidelines/TR03138/TR03138.pdf?__blob=publicationFile&v=1. 
  25. ↑ "JBIG2 Compression". https://kost-ceco.ch/cms/jbig2-compression_fr.html. 
  26. ↑ Beer, Ian; Groß, Samuel (2021-12-15). "Project Zero: A deep dive into an NSO zero-click iMessage exploit: Remote Code Execution". https://googleprojectzero.blogspot.com/2021/12/a-deep-dive-into-nso-zero-click.html. 

External links



Retrieved from "https://handwiki.org/wiki/index.php?title=JBIG2&oldid=3365568"