1、ITU-T RECflN*T*82 93 W 48b2591 0.586828 573 INTERNATIONAL TELECOMMUNICATION UNION ITU-T TELECOMMUNICATION STANDARDIZATION SECTOR OF ITU TERMINAL EQUIPMENT AND PROTOCOLS FOR TELEMATIC SERVICES T.82 (03/93) INFORMATION TECHNOLOGY - CODED AUDIO INFORMATION - PROGRESSIVE BI-LEVEL IMAGE COMPRESSION REPRE
2、SENTATION OF PICTURE AND ITU-T Recommendation T.82 (Previously “CCITT Recommendation”) ITU-T RECMN*T*82 93 4Bb2.591 0.586829 40T Foreword ITU (International Telecommunication Union) is the United Nations Specialized Agency in the field of telecommunications. The ITU Telecommunication Standardization
3、 Sector (ITU-T) is a permanent organ of the ITU. Some 179 member countries, 84 telecom operating entities, 145 scientific and industrial organizations and 38 international organizations participate in ITU-T which is the body which sets world telecommunications standards (Recommendations). The approv
4、al of Recommendations by the members of ITU-T is covered by the procedure laid down in WTSC Resolution No. 1 (Helsinki, 1993). In addition, the World Telecommunication Standardization Conference (WTSC), which meets every four years, approves Recommendations submitted to it and establishes the study
5、programme for the foilowing period. In some areas of information technology which fail within ITU-Ts purview, the necessary standards are prepared on a collaborative basis with IS0 and EC. The text of ITlJ-T Recommendation T.82 was approved by the WTSC (Helsinki, March 1-12, 1993). The identical tex
6、t is also published as ISO/IEC International Standard 11544. NOTES 1 As a consequence of a reform process within the International Telecommunication Union (KU), the CCIT ceased to exist as of 28 February 1993. In its place, the ITU Telecommunication Standardization Sector (IT-T) was created as of 1
7、March 1993. Similarly, in this reform process, the CCIR and the IFRE3 have been replaced by the Radiocommunication Sector. In order not to delay publication of this Recommendation, no change has been made in the text to references containing the acronyms “CCITT, CCIR or IFRB” or their associated ent
8、ities such as Plenary Assembly, Secretariat, etc. Future editions of this Recommendation will contain the proper terminology related to the new ITU structure. 2 telecommunication administration and a recognized operating agency. In this Recommendation, the expression “Administration” is used for con
9、ciseness to indicate both a O ITU 1993 Ail rights reserved. No part of this publication may be reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying and microfilm, without permission in writing from the ITU. ITU-T RECMN*T*82 73 W 4862591 0586830 121 CON
10、TENTS Intro . 1 Intro . 2 Intro . 3 General characteristics . Stripes and data ordering . Encoder functional blocks Resolution reduction and differential layer encoder . Lowest resolution layer encoder Decoder functional blocks Intro . 3.1 Intro . 3.2 Intro . 4 scope . Normative references . Definit
11、ions . Symbols and abbreviations . 4.1 Acronyms 4.3 Mathematical symbols, operators, and indicators . 4.4 Variables with mnemonic names . Conventions . 5.1 Flow diagram conventions and symbols . 5.2 Template graphics . 5.3 Spatial ph ase . 5.4 Data structure graphics . Requirements . 6.1 General rul
12、es . 6.2 Data organization 6.3 Resolution reduction . 6.4 Differentiai-layer typical prediction . 6.5 Lowest-resolution-layer typical prediction . 6.7 Model templates and adaptive templates 6.6 Deterministic prediction (DP) . 6.8 Arithmetic coding . Test methods and datastream examples 7.1 Arithmeti
13、c coding . 7.2 Parameterized algorithm . 7.3 Datastream examples Annex A . Suggested minimum support for free parameters . Annex B . Design of the resolution reduction table B.1 Filtering B.2 Exceptions Annex C . Adaptive template changes C.1 General . C.2 Differential layers . C.3 Lowest resolution
14、 layer CCK Rec . T.82 (1993 E) Page 1 11 iv Vii Vii 1 1 1 2 2 3 3 3 3 3 4 4 7 7 7 12 13 16 19 23 26 43 44 51 55 56 57 57 58 60 60 60 60 V 1 ITU-T RECMN*T-82 93 4862593 05Bb833 Ob8 Annex D . Design of the probability-estimation table D . 1 Bayesian estimation D.2 Multiple contexts D.4 Rapid trackmg .
15、 D.3 MPSLPS parameterization . D.5 Reducing computational burden . Annex E - Patents . E.l Introductory remarks . E.2 List of parents . E.3 Contact addresses for patent information Annex F - Bibliography 63 63 63 63 64 64 68 68 68 69 71 11 CCITT Rec . T.82 (1993 E) ITU-T RECMN*T-82 93 4862591 058b83
16、2 TT4 Introduction and overview (This introduction does not form an integral part of this Recommendation I International Standard) This Recommendation I International Standard was prepared by the Joint Bi-level image experts Group (JBIG) of ISOAFC JTCllSC29WG9 and CCm SGVIII. The BIG experts group w
17、as formed in 1988 to establish a standard for the progressive encoding of bi-level images. A progressive encoding system transmits a compressed image by first sending the compressed data for a reduced- resolution version of the image and then enhancing it as needed by transmitting additional compres
18、sed data, which builds on that aiready transmitted. This Recommendation I International Standard defines a coding method having progressive, progressive-compatible sequential, and singleprogression sequential modes and suggests a method to obtain any needed low-resolution renditions. It has been fou
19、nd possible to effectively use the defined ding and resolution-reduction algorithms for the lossless coding of greyscale and color images as well as bi-level images. The Introduction-and-overview clause and Annexes A to F are informative and thus do not form an integral part of this Recommendation I
20、 Intemational Standard. Intro. 1 General characteristics This Specification defines a method for lossless compression encoding of a bi-level image (that is, an image that, like a black-and-white image, has only two colors). The defined method can also be used for coding greyscale and color images. B
21、eing adaptive to image characteristics, it is robust over image type. On scanned images of printed characters, observed compression ratios have been from 1,l to 1,5 times as great as those achieved by the MMR encoding algorithm (which is less complex) described in Recommendations T.4 (G3) and T.6 (G
22、4). On computer generated images of printed characters, observed compression ratios have been as much as 5 times as great. On images with greyscale rendered by halftoning or dithering, observed compression ratios have been from 2 to 30 times as great. The method is bit-preserving, which means that i
23、t, like Recommendations T.4 and T.6, is distortionless and that the final decoded image is identical to the original. The method also has “progressive” capabiity. When decoding a progressively coded image, a low-resolution rendition of the original image is made available first with subsequent doubi
24、ings of resolution as more data is decoded. Note that resolution reduction is performed from the higher to lower resolution layers, while decoding is performed from the lower to higher resolution layers. The lowest resolution image sent in a progressive sequence is a sequentially coded image. In a s
25、ingle-progression sequential coding application, this is the only image sent. Progressive encodings bave two distinct benefits. One is that with them it is possible to design an application with one common database that can efficiently serve output devices with widely different resolution capabiliti
26、es. Only that portion of the compressed image file required for reconstruction to the resolution capabiiity of the particular output device has to be sent and decoded. Aiso, if additional resolution enhancement is desired, for say, a paper copy of an image aiready on a CRT screen, only the needed re
27、solution-enhancing information has to be sent. The other benefit of progressive endings is that they can provide subjectively superior image browsing (on a CRT) for an application using low-rate and medium-rate communication links. A low-resolution rendition is transmitted and displayed rapidly, and
28、 then followed by as much resolution enhancement as desired. Each stage of resolution enhancement builds on the image already available. Progressive encoding can make it easier for a user to quickly recognize the image as it is being built up, which in turn allows the user to interrupt the transmiss
29、ion of the image. Let D denote the number of doublings in resolution (called differential layers) provided by the progressive coding. Let ID denote the highest resolution image and let its horizontal and vertical dimensions in pixels be XD and YO. Let RD denote the sampiing resolution of the image I
30、D. This Specification imposes almost no restrictions on the parameters RD, XD, YD, or D. Choices such as 400 or 200 dpi (dots-per-inch) for the resolution RD of the highest resolution layer result in a hierarchy of resolutions commensurate with current facsimile standards. Choosing RD as 600 or 300
31、dpi gives a progressive hierarchy more compatible with the laser printer resolutions available as of the writing of this Specification. CCW Rec. T.82 (1993 E) i Intro. 2 Stripes and data ordering When it is necessary to distinguish progressive coding from the more traditional form of image coding in
32、 which the image is coded at full resolution from left to right and top to bottom, this older form of coding will be referred to as “sequential”. The advantage of sequential coding over progressive coding is that no page (frame) buffer is required. Progressive coding does require a page buffer at th
33、e next-to-highest resolution because lower resolution images are used in coding higher resolution images. It is possible to create a JBIG datastream with only a lowest resolution layer and this can be named single-progression sequential coding. In such coding, a fuli-resolution image is coded withou
34、t reference to any differential resolution layers. The parameter D (mentioned in Intro. 1) is set equal to zero. It should be noted that in a progressive encoding of an image, the lowest resolution layer is actually encoded in single-progression sequential coding. If a fuli-resolution image is encod
35、ed using single-progression sequential coding, it will not be possible to decode the image progressively. Coding in the progressive-compatible sequential mode is said to be “compatible” with coding in the progressive mode because the datastreams created (encoder) or read (decoder) in either mode car
36、ry exactly the same information. All tbat changes with a switch from progressive to progressive-compatible sequential encoding is the order in which parts of the compressed data are created by the encoder. All that changes with a switch from progressive to progressive-compatible sequential decoding
37、is the order in which these parts are used by the decoder. This compatibility is achieved by breaking an image into smaller parts before compression. These parts are created by dividing the image in each of its resolution “layers” into horizontal bands called “stripes.” Progressive-compatible sequen
38、tial coding does require a stripe” buffer (much smaller than a page buffer) and additional individual “state” memory used for adaptive entropy coding of each resolution layer and bit plane. Figure Intro. 1 shows such a decomposition when there are three resolution layers, three stripes per layer, an
39、d only one bit plane. Table Intro. 1 shows defined ways to sequence through the nine stripes. Notice that in addition to the progressive-versus-sequential distinction that is carried by the SEP bit, there is also a resolution-order distinction that is carried by the HITOLO bit. Encoders work from hi
40、gh resolution downward and so most naturally encode the stripes in HITOLO order. Decoders must build up the image from low resolution and so most naturally process stripes in the opposite order. When an application uses an encoder that sends progressively coded data directly to a decoder, one or the
41、 other must buffer to invert the order. When an application includes a database, the database (with appropriate Set-up) can be used to buffer and invert the order (including setting HITOLO correctly) thereby removing this requirement from the encoder and decoder. A stripe has a vertical size that is
42、 typically much smaller than that of the entire image. The number Lo of lines per stripe at the lowest layer is another free parameter. As an example, Lo might be chosen so that a stripe is about 8 mm. if such a choice is made, the number S of stripes in an image of a business-letter-sized sheet of
43、paper will be about 35. 11 CCiT Rec. T.82 (1993 E) s=o s= 1 s=2 7 . . . . - . - 25 dpi d= O 50 dpi d= 1 100dpi d=2 To808630-911DO1 Figure Intro. 1 - Decomposition in the special case of 3 layers, 3 stripe, and 1 bit plane Table Intro. 1 - Possible bi-level data orderings HITOLO I SEQ Example order 0
44、,1,2 3,4,5 6,7,8 0,3,6 1,4,7 2,5,8 6,7,8 3,4,5 0,1,2 6,3,0 7,4,1 8,5,2 When there is more than one bit plane, as in Figure Intro. 2, there are twelve defined stripe orderings. Table Intro. 2 lists them. As before, the HITOLO bit Cames the resolution-order distinction, and the SEQ bit Cames the progr
45、essive-versus- sequential distinction. When the ILEA- bit is 1, it indicates the interleaving of multiple bit planes. When the SMID bit is 1, it indicates s, the index over the stripe, is in the middle as shown more clearly in Table 11 of 6.2.4. p = 1 (MSB) s= o s= 1 s=2 o1 1“l d= O - o9 _. 10 _. 11
46、 I 50 dpi d= 1 Figure Intra 2 - Decomposition in the special case of 3 layers, 3 stripes, and 2 bit planes . CCITT Rec. T.82 (1993 E) u1 ITU-T RECMN*T=82 73 48632593 0586835 703 m ID-1 HITOLO /O-2 - - Resdutim reduction and differential layer encoder O O O O O O 1 1 1 1 1 1 - SEQ O O O 1 1 1 O O O 1
47、 1 I - - ILEAVE O 1 1 O O 1 O 1 1 O O 1 Table Intro. 2 - Possible multi-plane data orderings SMID O O 1 O 1 O O O 1 O 1 O Example order (OO,Ol, 02 06, O?, 08 12,13,14 (03,04,05 09,10,11 15,16,171 (00,01,02 03,04,05) (06,07,08 09,10,11) (12,13,14 15,16,17) (00,03 01,04 02,OS) (06,09 07,lO 08,111 (12,
48、15 13,16 14,17) (00,06,12 03,09,15) (01,07,13 04,10,16) (02,08,14 05,11,17) (00,06,12 01,07,13 02,08,14) (03,09,15 04,10,16 05,11,17) (00,03 06,09 12,15) (01,04 07,lO 13,16) (02,05 08,ll 14,1?) (12,13,14 06,07,08 00,01,02) (15,16,17 09,10,11 03,04,05) (12,13,14 15,16,17) (06,07,08 09,10,11) (00,01,0
49、2 03,04,05) (12,15 13,16 14,171 (06,09 07,lO 08,ll (00,03 01,04 02,05) (12,06,00 15,09,03) (13,0?, O1 16,10,041 (14,08,02 17,11,05) (12,06,00 13,07,01 14,08,02) (15,09,03 16,10,04 17,11,05) (12,lS 06,09 00,031 (13,16 07,lO 01,04) (14,17 08,ll 02,051 The two new variables ILEAVE and SMID plus the two earlier variables HITOLO and CEO make it possible to index all twelve of these orders. The other four of the sixteen possible combinations for these four binary variables have no stripe ordering associated with them. If there is only one plane, stripe order is not dependent on ILEAVE
