DjVu Reference

3.1 DjVu images

The principal imaging model used in DjVu is the “Mixed Raster Content” (MRC) model described in ITU-T Recommendation T.44, ISO/IEC 16485. In this model, an image is decomposed into foreground and background layers. To select whether a particular pixel comes from the foreground or background, a bitonal “selection” or “mask” layer is provided. These three layers are compressed separately using techniques which are optimized for each type of data.

The foreground and background layers are compressed using a wavelet-based continuous-tone image compression technique known as “IW44”.

The mask layer is compressed using a bitonal image compression technique that takes advantage of repetitions of nearly identical shapes on the page (such as characters) to efficiently compress text images.

A DjVu image need not contain all three layers and alternative compression techniques are available for each layer.

3.2 DjVu documents

DjVu documents can be single- or multi-page. Each page consists of a DjVu image as described above (photo, bitonal, or an MRC-based composition). Such a page, by itself, is a valid DjVu document. Multi-page documents can take either of two forms: bundled or indirect.

3.3 Non-raster data

6.1 DjVu 2

The DjVu file format specification that was originally released by AT&T in 1999. http://djvuzone.org/djvu/djvu/djvuspec/001.djvu

6.2 IFF

EA IFF 85 format, Electronic Arts’ public-domain IFF standard for an Interchange File Format, released in January, 1985. http://www.dcs.ed.ac.uk/home/mxr/gfx/2d/IFF.txt

6.3 JPEG

JPEG File Interchange Format, Version 1.01 (ISO DIS 10918-1, JPEG JFIF). The specification is located at http://www.w3.org/Graphics/JPEG/jfif.txt.

6.4 TIFF

http://partners.adobe.com/public/developer/en/tiff/TIFF6.pdf

6.5 G4

ITU-T (CCITT) T.6. Facsimile Coding Schemes and Coding Control Functions for Group 4 Facsimile Apparatus. https://www.itu.int/rec/T-REC-T.6-198811-I/en

6.6 UTF-8

All text in DjVu files is Unicode-encoded using the UTF-8 encoding. http://www.unicode.org/versions/Unicode4.0.0/ch03.pdf

6.7 DjVuLibre

An open-source reference implementation of this file format specification is available at http://sourceforge.net/projects/djvu/. Throughout this specification, there are numerous references to source files in this implementation.

7.1 Single-page documents

A single-page document is composed of a single FORM:DVJU composite chunk. This composite chunk always begins with one INFO chunk describing the image size, resolution and related information (see §8.3.11). The document contains exactly one DjVu image, whose content varies as described below.

7.2 Multi-page documents

A multi-page document is composed of a FORM:DJVM whose first chunk is a DIRM chunk containing the document directory. This directory lists all component files composing the given document, helps to access every component file and identifies the pages of the document.

In a bundled multi-page file, the component files are stored immediately after the DIRM chunk, within the FORM:DJVM composite chunk.

In an indirect multi-page file, the component files are stored in different files whose URLs are composed using information stored in the DIRM chunk.

8.1 Header

The first four bytes of a DjVu file are 0x41 0x54 0x26 0x54. This preamble is not part of the EA IFF85 format, but it is required in order to identify DjVu files.

8.2 DjVu file structure

8.3 IFF chunk types

FORM:DJVM [126475 bytes]
  DIRM [59 bytes] Document directory (bundled, 3 files, 2 pages)
  FORM:DJVI [3493 bytes] dict0002.iff
  FORM:DJVU [115016 bytes] p0001.djvu
  FORM:DJVU [7869 bytes] p0002.djvu

FORM:DJVU [26790 bytes]
  INFO [10 bytes] 2202 × 967, version 26, 300 dpi, gamma = 2.2
  Sjbz [13133 bytes] JB2 bi-level data
  FG44 [185 bytes] IW44 data #1, 76 slices, version 1.2 (color), 184 × 81
  BG44 [935 bytes] IW44 data #1, 74 slices, version 1.2 (color), 734 × 323
  BG44 [1672 bytes] IW44 data #2, 10 slices
  BG44 [815 bytes] IW44 data #3, 4 slices
  BG44 [9976 bytes] IW44 data #4, 9 slices

FORM:DJVM [126475 bytes]
  DIRM [59 bytes] Document directory (bundled, 3 files, 2 pages)
  FORM:DJVI [3493 bytes] dict0002.iff
    Djbz [3481 bytes] JB2 shared dictionary
  FORM:DJVU [115016 bytes] p0001.djvu
    INFO [10 bytes] 2539 × 3295, version 25, 300 dpi, gamma = 2.2
    INCL [12 bytes] Indirection chunk → dict0002.iff
    Sjbz [70497 bytes] JB2 bi-level data

FORM:DJVM [2272012 bytes]
  DIRM [108 bytes] Document directory (bundled, 7 files, 4 pages)
  FORM:THUM [5960 bytes] p0001.thumb
    TH44 [5984 bytes] Thumbnail icon for page 1
  FORM:DJVU [1413380 bytes] p0001.djvu
    INFO [10 bytes] 4728 × 6300, version 25, 600 dpi, gamma = 2.2
    …
  FORM:THUM [12148 bytes] p0004.thumb
    TH44 [3418 bytes] Thumbnail icon for page 2
    TH44 [4150 bytes] Thumbnail icon for page 3
    TH44 [4552 bytes] Thumbnail icon for page 4
  FORM:DJVU [777858 bytes] p0002.djvu
    …

00 00 00 54
00 00 0e 02
00 01 cf 52

00 0d ad
01 c1 50
00 1e c5

00
01
01

64 69 63 74 30 30 30 32 2e 69 66 66 00
70 30 30 30 31 2e 64 6a 76 75 00
70 30 30 30 32 2e 64 6a 76 75 00

00 0d ad
01 c1 50
00 1e c5

00
01
01

64 69 63 74 30 30 30 32 2e 69 66 66 00
70 30 30 30 31 2e 64 6a 76 75 00
70 30 30 30 32 2e 64 6a 76 75 00

54 61 62 6c 65 20 6f 66 20 43 6f 6e 74 65 6e 74
73

49 9e 74 72 6f 64 75 63 74 69 6f 6e

44 61 74 61 73 68 65 65 74

46 6f 72 20 4d 64 72 65 20 49 6e 66 6f 20 28 4f
6e 6c 69 6e 65 29

68 74 74 70 3a 2f 2f 77 77 77 2e 6c 69 7a 61 72
64 74 65 63 68 2e 63 6f 6d

10.1 Definitions

Color component

Compound DjVu images and photo DjVu images contain color or grayscale image data. Color IW44 images contain color image data. Grayscale IW44 images contain grayscale image data. Color image data is coded using three color components, called Y, Cb, and Cr. These correspond to the usual YCbCr color space, adjusted to facilitate transformation to the RGB color space. Grayscale image data is coded using one color component, called Y. This corresponds to the grayscale intensity of the image.

Color layer

A color layer is any of:

• The foreground layer of a compound DjVu image, coded in one FG44 chunk
• The background layer of compound DjVu image, coded in one or more BG44 chunks
• The only layer of a photo DjVu image, coded in one or more BG44 chunks
• The only layer of a color IW44 image, coded in one or more PM44 chunks
• The only layer of a grayscale IW44 image, coded in one or more BM44 chunks

Color chunk

A color chunk is a chunk of type BG44, FG44, PM44, or BM44. A color chunk contains wavelet coefficient update information for one or three color components.

Block

A rectangular array of pixels of size 32 × 32 or less. The blocks are numbered starting in the lower left corner of the image. All blocks are 32 × 32 except possible those along the right edge or top edge; those blocks may be smaller if the image dimensions are not divisible by 32.

Block count

The number of blocks in the image, denoted by NB.

Wavelet block

The set of coefficients associated with one block of the image, in one color component. There are 1024 wavelet coefficients in a wavelet block, numbered 0 through 1023. The coefficients in a wavelet block have effects on the reconstruction of other blocks in the image, but for coding purposes they are considered to be localized within the block in which they are coded.

Bucket

A particular set of 16 wavelet coefficients within a wavelet block. A wavelet block consists of 64 buckets, numbered 0 through 63. Table 2 gives the correspondence between coefficients and buckets.

Band

A subset of wavelet coefficients for a given color component. There are 10 bands. The correspondence among band numbers, coefficient indices, and bucket coefficients is given by Table 2.

Cycle

Data for one color component consisting of coefficient updates for all coefficients, that is, for all 10 bands, starting with band 0. Within one band, only some coefficients are updated, but within a cycle, all coefficients are updated. The last cycle of a color component may have fewer than 10 bands.

Color band number

The current band number for a color component. Each color component’s color band number starts at 0, and increases by 1 at the end of selected slices until it reaches 9; then it is reset to 0.

Color band

A collection of update information for a subset of the coefficients of one color component of the image, consisting of updates of all the coefficients in the image whose indices within their respective blocks are those corresponding to the current color band’s color band number.

Slice

A slice is the highest-level subdivision of a color chunk. A slice contains data for one color band for each of the color components in a color layer, that is, for three color components for a color image, or for one color component for a grayscale image.

Block band

A collection of update information for a subset of the coefficients of one color component of a wavelet block, consisting of updates of the coefficients in the block whose indices are those corresponding to a given band.

Chrominance delay counter

An integer counter that indicates how many slices in a color layer contain a color band only for the Y color component, and not for the Cb and Cr color components. The chrominance delay counter is initially set to the value specified in the INFO chunk for the color layer, and decremented by 1 after each slice in the color layer until it reaches 0. See §10.4.1.1.

Step size table

A table that indicates the precision to which each coefficient in a color component is currently stored. There are three such tables for a given color layer, one for each color component. Each such table has 16 entries. Each entry specifies the current step size for 1, 4, 16, 64, or 256 different coefficient indices, according to Table 3.

10.2 Color chunks within a DjVu file

There may be more than one BG44, PM44, or BM44 chunk in a DjVu file. If there is more than one such color chunk, the coefficient updating is continuous across the chunks, and the data is taken from the chunks in the order in which they appear in the file. Nothing is reinitialized at the beginning of chunks after the first color chunk of these types, except for the low-level arithmetic coder. The probability estimates for the arithmetic coder are not reinitialized.

In a compound DjVu image file, in which both an FG44 chunk and one or more BG44 chunks appear in the same file, the coding of the foreground layer, using the FG44 chunk, is independent of the coding of the background layer, using the BG44 chunks.

Each color layer is coded using a Dubuc–Deslauriers–Lemire (4, 4) interpolative wavelet transform. Each layer of the image is transformed into a set of wavelet coefficients, one wavelet coefficient for each pixel in the original image. This transform is especially effective for coding images at high compression ratios.

The value of each coefficient is coded in a distributed fashion, through a number of cycles. Within one cycle, each coefficient is updated once (that is, in only one of the 10 bands), and receives approximately one additional bit of information. Specifically, from cycle to cycle the absolute value of a coefficient is first narrowed down by eliminating possible values for the most significant non-zero bit until the correct most significant non-zero bit is found. The sign is coded in the same cycle in which the most significant non-zero bit is found. Then in each subsequent cycle, one additional bit of the value is coded.

10.3 Color chunk data headers

A color chunk begins with a data header consisting of 2 or 9 octets, as follows:

10.4 Color chunk data

11.1 General considerations

Selection layer coding is used in compound DjVu images. In such images, there are three layers. The foreground layer is coded in one FG44 chunk, and is rendered as described in Appendix 1. The background layer is coded in one or more BG44 chunks, and is rendered as described in Appendix 1. The selection layer is coded using one Sjbz chunk. Black pixels in the selection layer specify those pixels that are to be rendered using the foreground color. All other pixels are to be rendered using the background color.

Black-and-white coding is used in bi-level DjVu images. In such images, there are three layers. The foreground layer is black. The background layer is white. The selection layer is coded using one Sjbz chunk. The selection layer specifies those pixels that are to be rendered in black. All other pixels are to be rendered in white.

An Sjbz chunk contains a single arithmetically-coded data stream, coded using the Z′-Coder (Appendix 3). All data, including headers and record types, is coded in this arithmetically-coded stream.

11.2 Arithmetic coding

The arithmetically-coded data in an Sjbz chunk consists logically of records. The record types are listed in Table 6, and described in §11.4. The records consist of fields. The fields present for records of each record type are listed in Table 6. The fields within a record are coded in the order listed in Table 6 for records of that type. Details of the coding for each field appear in §11.5.

A field may contain one or more data elements. The data elements consist of flags, pixel colors, and integers. Because of the nature of arithmetic coding, the records, fields, and data elements are not of fixed sizes, and do not necessarily begin on bit boundaries within the data stream.

Flags are binary decisions, each coded using the Z′-Coder with a particular context. There are two different contexts for flags, the eventual image refinement context and the offset type context.

Pixel colors are binary decisions, coded using the Z′-Coder with a particular context. For pixel colors, there are 3072 different contexts. There are 1024 contexts used for direct coding of bitmaps; these correspond to the $2^{10}=1024$ different combinations of values that the pixels in the direct coding template can assume. There are 2048 contexts used for refinement coding of bitmaps; these correspond to the $2^{11}=2048$ different combinations of values that the pixels in the refinement coding template can assume.

Integers are coded using the multivalue extension to the Z′-Coder, described below. There are 15 contexts for coding multivalued integers, as described in Table 7.

11.3 Image reconstruction

Records in an Sjbz chunk are interpreted in the order in which they appear. A "Start of data" record specifies the dimensions of the image. An "Image refinement data" record indicates […]^[1]. An "End of data" record indicates the end of the Sjbz chunk. A "Comment" record contains uninterpreted data.

A record identified by any other record type describes one bitmap. The model used in DjVu for the selection layer is based on symbol-based coding. Bitmaps are placed into the reconstructed image as follows: The image is initially entirely white. When a bitmap is placed into the image, the pixels that are black in the current symbol become black at the appropriate position in the reconstructed image. Once a pixel in the reconstructed image becomes black, it remains black.

Because symbols in the document images are often similar to each other, it is often possible to obtain more efficient coding by making use of previously coded symbols. As symbols are decoded, their bitmaps may be placed into a symbol bitmap library. There is exactly one symbol bitmap library. Once a symbol has been placed into the symbol bitmap library, later records may cause copies of the symbol to be placed into the image, or may define a new bitmap by refining the bitmap in the library.

Depending on the record type, the symbol bitmap may be described by direct coding, by refinement coding, or by a copy operation. In direct coding, all pixels of the bitmap are coded directly, without reference to any other bitmap. In refinement coding, all pixels of the bitmap are also coded directly, but a bitmap in the library is used to make the coding more efficient. In a copy operation, the pixels of the bitmap are the same as the pixels of a bitmap in the library.

Depending on the record type, the bitmap may or may not be placed into the image. If the bitmap is placed into the image, then depending on the record type, it may be placed either at an absolute location or at a location relative to a previously placed bitmap.

Depending on the record type, the bitmap may or may not be placed into the symbol bitmap library. The first symbol placed into the library has index 0. Subsequent symbols are assigned consecutive integer indices.

The pixels of the reconstructed image are arranged in a rectangular coordinate system. For the pixel in the lower left corner of the image, the column number is 1 and the row number is 1. All coordinates refer to the pixels themselves, not to the edges between pixels.

11.4 Records

Records in Sjbz chunks have the following interpretations.

11.5 Fields

The following fields are coded in records of the types specified in Table 6 and in §11.4.

11.5.9 Bitmap by direct coding

Non-symbol bitmaps and symbol bitmaps with no sufficiently closely matching symbol in the symbol library are coded directly. A directly-coded bitmap is coded by repeated applications of the Z′-Coder to the pixels of the bitmap left to right across the rows, starting with the top row. When one row has been coded, the next lower row is coded. Each pixel is coded by the Z′-Coder using an appropriate context based on the values of 10 previously coded pixels. A coded value of 1 means the pixel is black. A coded value of 0 means the pixel is white.

The colors of the pixels numbered 1 through 10 in Figure 2, taken collectively, form a 10-bit value. Each of these values is an index into a table of 1024 different directly-coded bitmap contexts. The pixel labeled P in Figure 2 is coded using the context indexed by the collective values of the other 10 numbered pixels in the template. Pixels outside the bounding box are considered to be white.

11.5.10 Bitmap by refinement coding

Some bitmaps are coded by making use of data from another bitmap; this process is called refinement coding. Matched symbols other than those to be copied are coded using refinement coding.

A bitmap coded by refinement coding is coded by repeated application of the Z′-Coder to the pixels of the bitmap, left to right across the rows. When one row has been coded, the next lower row is coded. Each pixel is coded by the Z′-Coder using an appropriate context based on the values of four previously coded pixels from the bitmap being coded and seven pixels from the matching bitmap. (The pixels numbered 1 through 4 in Figure 3 are from the current symbol; the pixels numbered 5 through 11 are from the matching symbol.) A coded value of 1 means the pixel is black. A coded value of 0 means the pixel is white. The colors of the pixels numbered 1 through 11 in Figure 3, taken collectively, form an 11-bit value. Each of these values is an index into a table of 2048 different refinement-coded bitmap contexts. The pixel labeled P in Figure 3 is coded using the context indexed by the collective values of the 11 numbered pixels in the template. Pixel 7 is in the position in the matching symbol that corresponds to the position of pixel P in the current symbol when the two symbols are aligned.

Alignment of the current bitmap and the matching bitmap proceeds as follows. For matched symbols, the current symbol and the matching symbol are aligned according to the geometric centers of their bounding rectangles. If the number of columns or rows is even, the geometric center falls between two columns or rows, respectively. In this case, the leftmost of the two central columns or the lowermost of the two central rows is considered to be the central column or row, respectively.

It is possible for the current symbol to have empty edge rows or columns. These empty rows and columns are coded, and are included in the bounding rectangle. For symbols added to the library, the symbol is added to the library after it has been placed into the image. Any empty edge rows and columns are removed before the symbol is added to the library.

11.5.11 Comment length

The comment length is the number of octets in the comment. It is coded by the multivalue extension to the Z′-Coder using the comment length context. The range of allowable values for the comment length is from 0 to 262142.

11.5.12 Comment data

Comment data consists of the individual octets of the comment. The number of octets in the comment is given by the comment length field. Each of the octets is coded using the multivalue extension to the Z′-Coder using the comment octet context. The range of allowable values for each octet is from 0 to 255.

12.1 Registers and data storage

In Figure 1 and Figure 2, the values of variables A, C, D, and Z are stored in registers of at least 16 bits each. A and C retain their values between invocations of the Z′-Coder. Note: if register overflow can be ignored, storing variables A and C in registers of exactly 16 bits allows a simplification of lines 11, 12, 16, and 17 of Figure 1 and lines 8, 9, 12, and 13 of Figure 2.

At the beginning of a chunk, the values of A and C are reinitialized. When the decoder is decoding a chunk, it may require more bits than are present within the chunk’s data. In this case, all additional required bits are to be assumed by the decoder to be 1. If there are excess bits at the end of a chunk, they are ignored.

K is conceptually an array with a single 8-bit entry for each binary decision context. (In practice, K consists of a number of of individual values, arrays, and tree nodes, but each one has a specific address and a single 8-bit value at any time.) This array is indexed by the value of i, which is the input to the decoder. $K[i]$ is the current value of the probability state index for context i. $K[i]$ may be updated as part of the decoding process.

In pass-through mode, the decoder is invoked with no input argument. No context is involved.

B is the 1-bit value returned by the decoder.

The Z′-Coder is state-based. Decoding is governed by four fixed tables, given in Table 9. The tables are indexed by $K[i]$, the probability state index for the current context. All probability state indices are initialized to 0. That is, at the beginning of coding, for all i, $K[i]=0$. These values are not reinitialized at the beginning of chunks after the first.

The more probably symbol is denoted by MPS. The MPS is 1 if the probability state index is an odd integer, and 0 if the probability state index is an even integer. The less probable symbol is denoted by LPS. The LPS is 0 if the probability state index is an odd integer, and 1 if the probability state context is an even integer.

${\Delta }_k$ is the amount by which the current arithmetic coding interval is reduced if the decoded symbol is the MPS. ${\theta }_k$ is the threshold above which an MPS triggers a probability state update. ${\mu }_k$ is the next probability state index for context k after an MPS triggers a probability state index update. An LPS always triggers a probability state index update. ${\lambda }_k$ is the next probability state index for context k after an LPS.

12.2 Initialization

Initially, A is set to 0x0000. Two octets are read from the input data stream into the lowest 16 bits of C. If the bits of C are numbered such that bit 15 is the most significant bit and bit 0 is the least significant bit, then the first input octet is stored in bits 15 through 8, and the second input octet is stored in bits 7 through 0.

12.3 Decoding

Figure 1 shows the steps involved in decoding a single binary decision. The input to the decoder is the index i of the appropriate context for the binary decision being decoded. The output from the decoder is a single bit B.

Z := A + ΔK[i]
D := 0x6000 + (Z + A)/4
if (Z > D) { Z := D }
if (C > Z) {
    B := K[i] mod 2
    if (A ≥ θK[i]) { K[i] = μK[i] }
    A := Z
}
else {
    B := 1 - (K[i] mod 2)
    A := A + 0x10000 - Z
    C := C + 0x10000 - Z
    K[i] = λK[i]
}
while (A ≥ 0x8000) {
    A := A + A - 0x10000
    A := C + C - 0x10000 + next code bit
}
return B

12.4 Pass-through decoding

Figure 2 shows the steps involved in decoding a single binary decision using the Z′-Coder in pass-through mode. No input is required. No context is involved. No probability state index values are updated. The output from the decoder is the single bit B.

Z := 0x8000 + (A + A + A)/8
if (C > Z) {
    B := 0
    A := Z
}
else {
    B := 1
    A := A + 0x10000 - Z
    C := C + 0x10000 - Z
}
while (A ≥ 0x8000) {
    A := A + A - 0x10000
    A := C + C - 0x10000 + next code bit
}
return B

13.1 Encoding

BZZ first takes as input a 24-bit integer as block size between 10K and 4M and an input stream (to be compressed). The stream is partitioned into blocks terminated with a special ⟨EOB⟩ symbol. It is then transformed using the well-documented Burrows–Wheeler (BW or “block sorting”) transform. Then, one block at a time, the block size and resulting output stream are passed as input to be compressed using the Z′-Coder (Appendix 3).

13.2 Decoding

We describe the decoding algorithm by means of pseudo-code.

FADD = FADD + SHIFTRIGHT(FADD, FSHIFT)