CCITT T4

Rechnernetze

CCITT T.4 2-Dimensional Compression Standard

INTRODUCTION
The CCITT Group 3 two-dimensional coding uses the Modified Huffman code and the Modified Relative element address designate (MR)code.The main atvantage of the CCITT Group 3 two-dimensional coding over the CCITT Group 3 one-dimensional coding is that compression efficiency is improved.This is due to the fact that the two-dimensional coding explores correlation of pixels in two successive lines.

In Group 3, a scanline is encoded as a set of runs, each representing a number of white or black pixels, with white runs alternating with black runs. Every run is encoded using a variable number of bits, which can be uniquely identified upon decoding. This means that frequently occurring lengths of run may be encoded very efficiently, at the expense of the infrequent ones. For example, a black run of 2 or 3 pixels is encoded using just 2 bits, whereas one of 1000 pixels is encoded in 25.

Important terms used in CCITT T.4
Term	Definition
Color of an element	Black or white
Changing element	An element whose color is different from that of the previous element along the same scan line
Coding element	The current scan line
Reference line	The previous scan line
Coding mode	A method to code the position of each changing element along the coding line.
Reference element	An element whose position determines a coding mode

HOW DOES CCITT T.4 WORK?

The CCITT Group 3 two-dimensional coding is a line-by-line coding method. The position of each changing picture element on the coding line is coded with respect to the position of a corresponding reference element. The reference element is located on either the coding line or the reference line. After the coding line has been coded, it becomes the reference line for the next coding line. In order to limit the facsimile transmission error, a Modified Huffman coded line (i.e. one-dimensional coded line) is sent periodically. This period is referred to as K factor. For facsmile, at the standard vertical resolution, K is equal to 2; at the higher vertical resolution, K is equal to 4. For digital image, K can be any positive non-zero integer.

In summary, for every group of K lines, the CCITT Group two-dimensional scheme encodes 1 line in one-dimensional coding and the other K-1 lines in two-dimensional coding.

In the CCITT Group 3 2-D coding there are 5 changing picture elements

Changing elements
Changing element	Definition
a0	The reference element on the coding line
a1	The next changing element to the right of a0 on the coding line
a2	The next changing element to the right of a1 on the coding line
b1	The next changing element on the reference line to the right of a0 and of opppsite color of a0
b2	The next changing element to the right of b1 on the reference line

At the starting the coding line, the changing element a0 is first set on imaginary white changing element located just before the first element on the coding line. During the encoding of the coding line, the position of a0 is determined by the previous coding mode.

EXAMPLE

                 b1       b2

////	////	////	__	__	__	////	////	__	__
////	////	__	__	__	////	////	////	////	__

      a0       a1         a2

MODES

In the CCITT T.4 standard, there are three coding modes: Pass Mode(P) ,Vertical Mode, and Horizontal Mode (H). Depending on the position of a changing element along the coding line, one of three coding modes can be identified.

Coding Modes
Coding Mode	Condition
Pass Mode	When the position of b2 lies to the left of a2
Vertical Mode	When the relative distance between a1 and b1 is less than or equal to 3
Horizontal Mode	When neither pass mode nor vertical mode occur

In the Vertical Mode, depending on the relative distance between a1 and b1, 7 possible cases can be identified:

               -  V  (0):a1 just under b1,
               -  Vr (1):a1 one pixel to the right of b1,
               -  Vr (2):a1 two pixels to the right of b1,
               -  Vr (3):a1 three pixels to the right of b1,
               -  Vl (1):a1 one pixel to the left b1,
               -  Vl (2):a1 two pixels to the left b1,
               -  Vl (3):a1 three pixels to the left b1.

The code words for three coding modes (pass, horizontal and vertical coding modes) are shown in Table 4. with the optional extension. In Table 4. M(ai,aj) represents the code words of 1-D compression standard for the run ai aj.

Table 4: Two-Dimensional Code Table
Mode	Elements to be coded		Code word
Pass P	b1,b2		0001
Horizontal H	a0a1,a1a2		001+M (a0 a1) + M (a1 a2)
Vertical:V(0)	a1 just under b1	a1b1 = 0	1
Vr (1)		a1b1 = 1	011
Vr (2)		a1b1 = 2	000011
Vr (3)		a1b1 = 3	0000011
Vl (1)		a1b1 = 1	010
Vl(2)		a1b1 = 2	000010
Vl(3)		a1b1 = 3	0000010
Extension	2-D (extensions)		0000001xxx
	1-D (extensions)		000000001xxx