Multimedia Communications (10EC841) Unit 3: Text and Image Compression TEXT AND IMAGE COMPRESSION Unit 3: Text and Image Compression: Introduction, Compression principles, Text compression, Image compression 6 Hours INTRODUCTION Multimedia applications – in compression is applied Compression: Technique, which is first applied to the source information prior to its transmission Compression done to: 1. Reduce the volume of information to be transmitted – text, fax, and images 2. Reduce the bandwidth – required for the transmission of speech, audio, and video COMPRESSION PRINCIPLES Compression algorithms – based on the following compression principles 1. Source encoders and destination decoders 2. Lossless and lossy compression 3. Entropy encoding 4. Source encoding 1. Source encoders and destination decoders Compression algorithm – is applied to the source information – relating to a particular multimedia application – prior to transmitting Matching decompression algorithm – must be applied – to reproduce the original source information or a nearly exact copy of it Source encoder: used for the application of the compression algorithm Destination decoder: used for the application of decompression algorithm Two computers – communicating cases in: Time required to perform – the compression and decompression – is not always critical – so, Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression Both algorithms: Implemented in software – within the two computers Time required to perform – the compression and decompression – is not always critical Other communication cases in: Compression and decompression algorithm in software forms – is not acceptable Two algorithms – here, must be performed – by special processors in separate units 2. Lossless and lossy compression Compression algorithms – can be lossless or lossy Lossless compression algorithm: Aim – reduce the amount of source information – to be transmitted – in such a way that – destination in, when decompressed – there is no loss of information Reversible compression – another name of lossless compression Ex.: Text file – transfer over the network – no, part of the source information is lost – during either the compression or decompression operations Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression Lossy compression algorithm: Aim – normally, not to produce the exact copy of the source information after decompression – but, a version of it which is perceived by the recipient as a true copy Such applications – in higher the level of compression being applied to the source information – the more approximate – the received version becomes Ex.: Transfer of digitized images and audio and video streams In such cases: sensitivity of the human eye or ear – is such that – any fine details, may be missing from the original source signal after decompression – are not detected 3. Entropy encoding Is lossless Independent of the type of the information – that is being compressed Concerned solely with how the information is represented Examples of entropy encoding: 1. Run-length encoding and 2. Statistical encoding Applications – in either the one of above or both – are used 1. Run-length encoding Typical applications: When source information comprises – long substrings of the same character or binary digit Here, instead of transmitting – source string in the form of independent codewords or bits – source string is transmitted in the form of different set of codewords – which indicate: 1. Particular character or bit being transmitted and 2. Number of characters/bits in the substring Destination – knows the set of codewords – being used Destination – simply, interprets – each codeword received and outputs the appropriate number of characters or bits Ex.: Application involves – transmission of long strings of binary bits – that comprise – limited number of substrings Each substring can be assigned – a separate codeword Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression Total bit string – is then, transmitted – in the form of the string of codewords – selected from the codeword set Ex.: Transmission of the binary strings produced by the scanner in a facsimile machine When scanning typed documents – in many instances – scanner produces – long substrings of either binary 0s or 1s Transmitting directly – instead, they are sent in the form of a string of codewords – each indicating both the bit 0 or 1 – and the number of strings in the substring Ex.: if the output of the scanner was – 000000011111111110000011… can be represented as 0,7 1,10 0,5 1,2 … Since, only the two binary digits 0 and 1 are involved – and if, first substring always comprises binary 0s – then, the string could be represented as 7, 10, 5, 2 … To send this in the digital form – individual decimal digits – would be sent – in their binary form Assuming the fixed number of bits per codeword – number of bits per codeword – would be determined by the largest possible substring Statistical encoding Applications – uses - a set of codewords – to transmit the source information Ex.: Set of ASCII codewords – are often used for the transmission of strings of characters Normally, all the codewords in the set comprise a fixed number of binary bits – Ex.: 7 bits in the case of ASCII In many applications: Symbols and hence codewords – that are present in the source information do not occur with – the same frequency of occuring - that is with equal probability Ex.: String of text – in character A – may occur – more frequently than – character P – which again , will occur more frequently than character Z, and so on Statistical encoding – uses this property – by using the set of variable length codewords – with the shortest codewords used to represent the most frequently occurring symbols Use of variable-length codewords – is not quite as straight-forward Destination must know – the set of codewords being – used by the source – as in run-length encoding Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression When variable-length codewords used – in order for the decoding operation to be carried out correctly – it is necessary – to ensure that – a shorter codeword in the set does not form – the start of a longer codeword – otherwise, the decoder Will interpret the string on the wrong codeword boundaries Prefix property – codeword set, which avoids the above happening Ex.: Huffman encoding algorithm Source entropy: Theoretical minimum average number of bits – that are required to transmit a particular source stream Shannon’s formula – from can be calculated – Entropy, H = pi log Pi Where, n – number of different symbols in the source stream Pi – probability of occurrence of symbol i Efficiency of a encoding scheme: ratio of the entropy of the source to the average number of bits per codeword that are required with the scheme Average number of bits per codeword = Ni Pi Source encoding Uses: a particular property of the source information – to produce an alternative form of representation – which is 1. Compressed version of the original form or 2. Is more amenable to the application of compression 1. Differential encoding Used – extensively – in applications – where, the amplitude of a value or signal covers a large range Difference in amplitude – between successive values/signals is relatively small Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression To exploit this property of the source information: A set of smaller codewords can be used – each of which indicates – only difference in amplitude between the current value/signal being encoded and the immediately preceding value/signal – instead, of using a relatively large codewords to represent the amplitude of each value/signal Ex.: If the digitization of analog signal requires: say, 12 bits to obtain – the required dynamic range – but, the maximum difference in amplitude between successive samples of the signal – requires only 3 bits – then, by using only the difference values – a saving of 75% on transmission bandwidth – can be obtained Can be lossless or lossy – depends on the number of bits used to encode the difference values Can be lossless – if the number of bits used is sufficient to cater for the maximum difference value Can be lossy – if the number of bits used is not sufficient to cater for the maximum difference value In these cases – when the difference value exceeds the maximum number of bits being used – temporary Loss of information will result 2. Transform encoding Involves – transforming the soruce information – from one form into another form (which, lending it to more readily to the application of compression) In general – there is no loss of information associated with the transformation operation Applcations: image and video applications Ex.: Digitization of a continuous tone monochromatic image – produces a 2-D matrix of pixel values – each of which represents – the level of gray in a particular position of the image Moving from one position in the matrix to the next – magnitude of each pixel value can be vary So, if a scan across the pixel locations – rate of change in magnitude – will vary from zero If all the pixel values – remain the same – to a low rate of change 9if, say – one half is different from the next half) through to a high rate of change – if each pixel magnitude changes from one location to the next Ex.: shown in the Fig.. Spatial frequency: rate of change in magnitude – as one traverses the matrix For any particular image – there will be a mix of different spatial frequencies – whose amplitudes are determined by – the related changes in magnitude of the pixels Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression It true – if, matrix been scanned – in either, the horizontal or vertical direction – which provides – the horizontal and vertical frequency components of the image In practice: Human eye is less sensitive – to the higher spatial frequency components – associated with an image – than, the lower frequency components If the amplitude of the higher frequency components – falls below a certain amplitude threshold – they will not be detected by the eye - So, in terms of compression: If we can transform the original spatial form of representation into an Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression equivalent representation involving spatial frequency components – then, more readily identifying and eliminating those higher frequency components – which the eye cannot detect – can be done – It reduces the volume of information – to be transmitted – without degrading the perceived quality of the original image DCT (Discrete Cosine Transform): Transformation of 2-D matrix of pixel values – into an equivalent matrix of spatial frequency components – can be carried out from this mathematical technique Transformation using DCT – is lossless – apart, from small rounding errors in the mathematics Once – the equivalent matrix of spatial frequency components – known as coefficients – has been derived –then any frequency components in the matrix - whose amplitude is less than a defined threshold can be dropped – it is at this point DCT operation, will become lossy Fig. shows – the basic principle behind the DCT TEXT COMPRESSION 3 different types of text: represented as strings of characters - selected a defined set strings - alphanumeric characters interspersed - with additional control characters (additional control characters - use and interpret different form - by different types of text Entropy encoding(statistical encoding methods) - for lossless - thing for text compression Statistical encoding method: Types: 2 1. Use single character - as the basis of deriving an optimum set of codewords Ex.: Huffman and arithmetic coding algorithm 2. Use variable-length strings of characters Ex.: Lempel-Ziv (LZ) algorithm Coding: 2 types - used for text 1. Static coding: Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression Intended for applications - in which the text to be compressed - has known characteristics - in terms of the characters used and their relative frequencies of occurrence From using above - an optimum set of variable-length codewords - is derived - with the shortest codewords used to have more frequently occurring characters Static coding: resulting set of codewords - used for all subsequent transfers - involving - this type of text 2. Dynamic coding(adaptive coding): Each uses - a different algorithm to derive the codeword set Intended for more general applications - type of text transferring may vary from one transfer to another Optimum set of codewords - also likely to vary - from one transfer to another Codeword set used to transfer a particular text string is derived as the transfer takes place - this can be done by building up knowledge of both the characters that are present in the text - and their relative frequency of occurrence dynamically as the characters are being transmitted Codewords used - change as a transfer takes place - in such a way that - receiver is able to dynamically Compute the same set of codewords - that are being used at each point during a transfer Static Huffman coding Character string to be transmitted - is first analyzed Character types and their relative frequency determined Coding operation: involves creating an unbalanced tree - with some branches shorter than others Degree of imbalance - function of relative frequency of occurrence of the characters - larger the spread, more unbalanced the tree Resulting tree - Huffman code tree Huffman code tree: Binary tree - with branches assigned a value 0 of 1 Base of the tree - normally, the geometric top in practice - known as root node Point at which the branch divides - branch node Leaf node - termination point of a branch - for which the symbols being encoded are assigned Fig: Example of Huffman code tree - corresponding to string of characters - AAAABBCD branch as divides - binary value 0 of 1 - assigned to each new branch - 0 for left and 1 for right Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression codewords used for each character (shown in leaf nodes) - are got by tracing the path from root node to each leaf node and forming a string of binary values - associated with each branch traced Set of codes associated with this tree - 4*1+2*2+1*3+1*3=14bits - to transmit the complete string - AAAABBCD Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression Fig. shows the Huffman tree - each characters frequency of occurring must be added Fig. in characters listed in a column in decreasing weight order Huffman tree can be constructed - from the set of codewords - optimum tree it must be - so, set of codewords - by listing the resulting weights of all the leaf and branch nodes in the tree - starting with the smallest weight and proceeding from left to right and from bottom to top Codewords are optimum - if the resulting list increments in weight order Each character -in its encoded form has a variable number of bits - received bitstream must be interpreted (decoded) in a bit-oriented way - rather than on fixed 7/8 bit boundaries Shorter codeword will never form the start of a longer codeword - prefix property Prefix property - received bitstream can be decoded - by carrying out a recursive search bit by bit until each valid codeword is found Fig. shows the flowchart of a suitable decoding algorithm Assumption: Table of codewords - are avaialable at the receiver - and also had corresponding ASCII codeword received bit stream is held in the variable BIT-STREAM Variable CODEWORD - used to hold the bits in each codeword - while it is being constructed From the flow chart - once the codeword is identified - corresponding ASCII codeword is written into the variable RECEIVE_BUFFER Procedure - repeats until all the bits in the received string have been processed Fig. shows example of the decoded string Huffman code tree and hence, codewords - varies for different sets of characters being transmitted - for the receiver to perform the decoding operation, it must know the codewords relating to the data being transmitted can be done in 2 ways: 1. Codewords relating to the next set of data are sent before the data is transmitted 2. Receiver knows in advance - what codewords are being used 1. Codewords relating to the next set of data are sent before the data is transmitted Leads to the adaptive compression Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression Codewords can be changed to suit the type of data being transmitted Disadvantage: overhead of having to send the new set of codewords (and characters corresponding) whenever a new type of data is to be sent Alternative - for the receiver to have one or more different sets of codewords and Sender to indicate to the receiver through an agreed message - which codeword set to use for the next set of data Ex.: word processor and bibliography in text books - frequency of occurrence of characters - is used to construct the Huffman code tree for alphabet If this data - is being sent - transmitter and receiver automatically use this et of codewords Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression Arithmetic coding No. of decimal digits in the final codeword - increases linearly with the number of characters in the string to be encoded Max. no. of characters in a string - is determined by the precision with which floating-point numbers are represented in the source and destination computers Complete message may be first fragmented into multiple smaller strings Each string is then encoded separately - and the resulting set of codewords sent as a block of floating-point numbers each in a known format Alternatively - binary arithmetic coding can be used Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression LZ coding Lempel-Ziv compression algorithm: uses strings of characters - as the basis of the coding algorithm Ex.: For compression of text Table containing all the possible character strings – Ex. words – that occur in the text to be transferred is held by both encoder and decoder Each word occur in the text - instead of sending the word as a set of individual say ASCII codewords - the encoder sends only the index of where the word is stored in the table and , on receipt of each index - decoder - uses this to access the corresponding word/string of characters from the table and proceeds to reconstruct the text into its original form - hence, table is used as a dictionary and LZ algorithm is known as a dictionary-based compression algorithm Ex. Word processing packages - had dictionary associated with them - used for spell checking and for compression of text around 25000words will be - hence 15 bits which has 32768 combinations are required to encode the index to send "multimedia" - just 15bits needed instead 70bits with 7bit ASCII codewords compression ratio - 4.7:1 shorter words will have - lower compression ratio and longer words a higher ratio LZ algorithm - requirement - as other static coding methods - is: Copy of the dictionary is held by both the encoder and the decoder standard word processing package - to be used for transmission of text - can be relatively inefficient if the text to be transmitted Comprises only a small subset of the words stored in the dictionary Variation of LZ algorithm: allows the dictionary to be built up dynamically by the encoder and decoder - text compressed been as transferred Size of the dictionary - is often a better match to the number of different words in the text being transmitted than if a standard dictionary was used LZW coding: Principle for encoder and decoder - to build the contents of the dictionary dynamically as the text is being transferred dictionary held by both the encoder and decoder contains only contains only the character set - ex ASCII - that has been used to create the text Remaining entries in the text - are used to built up dynamically by both the encoder and decoder and contain the words that occur in the text Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression Ex.: If the character set comprise 128 characters Dictionary is limited to 4096 entries First 128 entries contain - single characters that make up the character set Remaining - 3968 entries - would each contain strings of two or more characters that make up he words in the text beig transferred More frequently the words stored i the dictionary occur in the text - the higher the level of compression Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression To describe how the dictionary is built up: Assumption: text to be compressed starts with the string: This is simple as it is ... Dictionary - idea is to contain - only words - then, only strings of characters that consist of alphanumeric characters are stored in the dictionary and all the other characters in the set are interpreted as word delimiters initially dictionary held by both the encoder and decoder contains - only the individual characters from the character set being used Ex.: 128 characters in the ASCII character set First word in the ex text: is send by the encoder using he index of each of the four characters T h i and s When the encoder reads the next character from the string - first space character (SP) determines that - this is not an alphanumeric character It transmits the character using its index as before - but in addition interprets it as terminating the first word and hence stores the preceding four characters in the next available free location in the dictionary similarly - decoder on receipt of the first five indices/codewords - reads the character stored at each index and commences to reconstruct the text Fifth character space - it interprets this as the word delimiter - proceeds to store the word This in its dictionary same procedure is followed by encoder and decoder - for transferring the other words - except the encoder prior to sending each word in the form of single characters - first checks to determine if the word is currently stored in its dictionary and if it is - it sends only the index for the word Similarly - the decoder - since it also has the word stored in its dictionary - uses the index to access the string of characters that make up the word Ex.: Of text string - after the space character - following the second occurrence of the word is - contents of the dictionary held by both the encoder and the decoder will be as shown in Fig. Since, it is second occurrence of the word is - it is transferred using only the index of - where it is stored in the dictionary (129) Ex. Above from: Key issue in level of compression - is the number of entries in the dictionary - since, this in turn determines the number of bits that are required for the index Dictionary of static type - number of entries is fixed Ex.: Dictionary containing - 25000 words - requires 15 bits to encode the index Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression When dynamically - building the dictionary - question arises how many entries should be provided for the dictionary if too few entries are provided - dictionary will contain only a subset of words that occur in the text while it too many are provided – then it will contain empty spaces which, in turn, makes the index unnecessarily log To optimize the number of bits used for the index - at the commencement of each transfer the number of entries is set to a relatively low value but, should the available space before full - then the number of entries is allowed to increase incrementally Ex.: Application uses 128 characters in the basic character set - both the encoder and decoder would start with - say, 256 entries in the dictionary Requires an index /codeword - length of 8 bits Dictionary would provide space for the 128 characters in the character set Further 128 locations for words that occur in the text Should this number of locations become insufficient – on detecting this - both the encoder and decoder would double the size of their dictionary to 512 locations It necessitates - an index length of - 9 bits - from this point encoder uses - 9 bit codewords Since, the decoder also had doubled the size of its - dictionary - it expects 9 bit codewords from this point Number of entries in the dictionary - more accurately reflects - the number of different words in the text being transferred and hence, optimizes the number of bits used for each index/codeword Fig. shows- Diagrammatic form of this Assumption: Last entry in the existing table at location 255 is the word fish - and the next word in the text that is not currently in the dictionary is pond Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression IMAGE COMPRESSION GIF(Graphics Interchange Format) Used extensively - with the Internet for the representation and compression of graphical images Color images comprising 24-bit pixels (8 bits each for R, G, and B) are supported 224 colors among - 256 colors choosing by GIF (reduces no of possible colors that are present) - which matches most closely- those used in original image Resulting table of colors - so, consists of 256 entries - each of which contains - a 24-bit color value Instead of sending 24-bit value - 8-index to the table entry - that contains closest match color to the original - is sent to decoder Compression ratio of 3:1 - is obtained Global color table - is called to table of colors - if - table of colors can relate to the whole image Local color table - is called to table of colors - if - table of colors if relate to - a portion of the image Contents of the table are sent across the network - together with the compressed image data and other information such as aspect ratio, screen size, in standardized format LZW LZW - coding - also, possible to allow for further levels of compression Can be done - in the case of image compression - by extending the basic color table dynamically - as the compressed image data is being encoded and decoded Color table in after 256 selected color - occurrence of common strings of pixel values - such as, long strings of the same color - are detected - entered Each entry in the color table - comprises 24 bits To save memory - each string of pixel values are represented by - corresponding string of 8-bit indices to the basic color table - are used If each entry in the table is limited to 24 bits - will allow common strings comprising 3 pixel values to be stored in each location of the extended table Normally, basic table contains - 256 entries, an initial table size of 512 entries is selected which allows for up to 256 common strings to be stored Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression If, more entries for table needed - no. of entries in the table are allowed to incrementally increase - by extending length of index by 1 bit Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression GIF Allows - image to be stored Allows - image transfer over the network - in an interlaced mode These above - can be used to transfer images over either low bit rate channels or the Internet - which provides a variable transmission rate From this - compressed image data is organized - so, that decompressed image is built up in a progressive way as - the data arrives – this is done by - dividing the compressed data by 4 groups: 1. Contains 1/8 th of total compressed image data 2. Contains a further 1/8 th 3. Contains a further 1/4 th 4. Contains the last remaining 1/2 nd TIFF(Tagged Image File Format) Used extensively Supports pixel resolution of up to 48 bits - 16 bits each for R, G, and B Intended for transfer of both images and digitized documents Image data - can be stored and transferred over the network - in a number of different formats and particular Format being use - is indicated by a number - which are following: 1. Uncompressed format (code number 1) 2. Digitized documents (code number 2 3 and 4) 3. LZW compressed (code number 5) Same compression algorithms - used in the facsimile machines LZW compression algorithm: Used is the same as that used with GIF Starts with the basic color table - containing 256 colors Table can be extended to contain up to 4096 entries - containing common strings of pixels - in the image being transferred Standard format is used - for the transfer of both the color table and the compressed image data Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression Digitized documents In an digital representation of scanned page - If only one single binay bit is used to represent eah cpicture element with the resolutions of needed - uncompressed bit stream of the order of 2Mbits - will be Most of the cases in - this must be transferred using modems and PSTN If the relatively low bit rate modems and PSTN used - it will costly and time consuming to transfer a total document comprising many pages in the basic form In most documents - many scanned lines consist only of long strings of white pels While - others comprise - a mix of long strings of white and long strings of black pels Normally - facsimile machines are used with - public carrier networks - ITU-T relating to facsimile machines been done ITU-T standards - for facsimile machines are 1. T2 (Group 1) 2. T3 (Group 2) 3. T4 (Group 3) 4. T6 (Group 4) T2 and T3 - are earlier standards - now rarely, used - both operate digitally T4: Uses modems for use with analog PSTN Time taken to transmit a page - is reduced to less than a minute with these machines Uses no error-correction protocol T6 - is all digital - is used with digital networks such as ISDN Higher transmission rate of 64kbps - is used Time taken to transmit a page - is less than a few second T4 and T6: Use data compression Compression ratios - in excess of 10:1 are common with most document pages Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression Standardization process - extensive analyses of typical scanned document pages were made Tables of codewords - produced based on the relative frequency of occurrence of the number of contiguous white and balck pels found in a scanned line Resulting codewords are fixed and grouped into two separate tables 1. Termination-codes table 2. Make-up codes table Fig. shows - the codewords in each table Codewords in the termination - codes table are for white or black runlengths of from 0 to 63 pels - in steps of 1 pel Make-up codes table contains - codewords for white or black run-lengths - that are multiples of 64 pels Overscanning: technique used - in which all lines start with a minimum of one white pel -so, here - receiver knows the first codeword always relates to white pels and then alternates between black and white This scheme- use 2 sets of codewords (termination and make-up) - these are known as modified Huffman codes Ex.: Run-length of 12 white pels is coded directly as 0010000 Run-length of 12 black pels is coded directly as 0000111 Run-length of 140 black pels is coded as - 000011001000 + 0000111 - 128 +12 pels Run-length exceeding 2560 pels - are encoded - using more than one make-up code + one termination code From the list of the codeword - it can be deduce that - if one or more bits is corrupted during its transmission through the network - receiver will start o interrupt subsequent codewords o the wrong bit boundaries receiver thus - becomes unsynchronized - and, cannot decode the received bit string EOL ( End-of-line) code: to enable the receiver to regain synchronism - each scanned line is transmitted with EOL code If, receiver fails to decode - a valid codeword after the maximum number of bits in a codeword - have been scanned or parsed - it search for the EOL pattern If it fails to decode the EOL pattern, after a preset number of lines - it aborts the reception process and informs the sending machine Single EOL precedes - the codewords for each scanned page and a string of six consecutive EOLs indicates the end of each page Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression T4 (Group 3): One-dimensional coding scheme - used here - since, each scanned line is encoded independently scanned image contains significant areas of white or black pels - for ex. which occur - where documents consist of letters and line drawings - T4 works satisfactorily Documents containing - photographic images - however, not satisfactory - as the different shades of black and white – are represented by varying densities of black and white pels This in turn - results - in a large number of very short black or white run-lengths which - with T4 coding scheme - can lead to negative compression ratio (more bits are needed to send the scanned document in its compressed form than are needed in its uncompressed form T6 coding scheme: Compulsory feature in Group 4 machines Optional feature for Group 3 facsimile machines - when used here, EOL code at the end of each (compressed) line has an additional tag bit added: If, it is a binary 1, then the next line has been encoded using T4 coding scheme If, it is a binary 0, then the next line has been encoded using T6 coding scheme (known as MMR coding) 2-D coding : Alternative name is MMR coding (Modified Modified READ coding) - since, it identifies black and white run-lengths by comparing adjacent scan lines READ(Relative Element Address Designate) - "modified" it is since, it's a modified version of earlier (modified) coding schemes MMR coding: It uses the fact that - most scanned lines differ from - the previous line by only a few pels Ex.: If a line contains a black-run hen the next line will normally contain the same run plus or minus up to 3 pels run-lengths associated with a line are identified by comparing the line contents - known as - coding line (CL) - with the immediately Preceding line - known as the reference line (RL) Assumption: first reference line is assumed to be an imaginary all-white line and the first lien proper is encoded relative to this Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression Encoded line then becomes the reference line - for the following line, and so on Complete page - scan - to ensure - scanner head always starts to the left of the page - so, each line always starts with an imaginary white pel Run lengths associated with a coding line - can be identified - as one of 3 possibilities of modes - relative to the reference line Ex.: Of 3 modes is shown in Fig. 3 modes are identified by the position of the next run-length - in the reference line (b1b2) relative to the start and end of the next pair of run-lengths in the coding line (a0a1 and a1a2) Note: Same procedure is used to encode - the runs of both black and white pels 3 possibilities are: 1. Pass mode: Run-length in the reference line (b1b2) is to the left of the next run-length in the coding line (a1a2) i.e., b2 is to the left of a1 Ex.: in Fig. For this mode - run-length b1b2 is coded using the codewords given in Fig. Note: If the next pel on the coding line - a1, is directly below b2 - then, this is not pass mode 2. Vertical mode: Run-length - in the reference line (b1b2) overlaps the next run-length in the coding line (a1a2) by a maximum of plus or minus 3 pels Fig. shows - 2 Ex. For this mode - just the difference run-length a1b1 is coded Most codewords - are in this category 3. Horizontal mode: Run-length - in the reference line (b1b2) overlaps the run-length (a1a2) - by more than plus or minus 3 pels Fig. shows 2 Ex. For this mode - two run-lengths a0a1 and a1a2 are coded using the codewords in Fig. Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression Fig. shows the flowchart of the coding procedure Note: first a0 is set to an imaginary white pel before the first pel of te lien and hence, the first a0a1 run-length will be a0a1-1 If - coding during of the line - a1,a2,b1,or b2 - are not detected - then, they are set to an imaginary pel positioned immediately after the last pel on the respective line First and next position of a0 - once been determined - positions of a1,a2, b1, and b2 for the next codeword are located mode is then - determined by - computing the position of b2 relative to a1 If it is not to the left - then the magnitude of a1b1 is used to determine whether the mode is vertical or horizontal codeword for the identified mode - is then computed - and the start of the next codeword position - a0 - updated to the appropriate position Above procedure - repeats - between white and black runs until - the end of the line is reached It is an imaginary pel position - immediately after the last pel of the line and is assumed to have a different color from the last pel Current coding line - then, becomes the new reference line and the next scanned line the new coding line Coded run-lengths relate - to one of 3 modes - additional codewords are used - either 1. To indicate to which mode the following codeword(s) relate - pass or horizontal or 2. To specify the length of the codeword directly - vertical 2-D code table: Additional codwords are given - in the third table - known as 2-D code table Contents are - as shown in Fig. Extension mode: It's the final entry in the table It's the unique codeword that aborts - encoding operation prematurely before the end of the page Allows - a portion of a page to be sent in its uncompressed form or possibly with a different coding scheme Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression Digitized pictures Digitization of both continuous-tone monochromatic pictures and color pictures - can be performed Amount of computer memory store and display - pictures - on a number of popular types of display - are as in table Amount of memory needed - 307 kbyte (approx.) to 2.4 Mbytes Interactive applications - in unacceptable long delays - in some low bit rate networks - are causes problem Digitized pictures - time to transmit - to reduce - compression is normally done to 2-D array of pixel values - that represents the digitized picture - before it is transmitted over the network Most widely adopted standard - relating to the compression of digitized pictures - is developed by an international standards body - known as JPEG (Joint Photographic Experts Group) JPEG - also forms the basis for most of the video compression algorithms Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913 Multimedia Communications (10EC841) Unit 3: Text and Image Compression Bibliography: Multimedia Communications: Applications, Networks, Protocols and Standards, Fred Halsall, Pearson Education, Asia, Second Indian reprint 2002. Ramesh S Asst. Prof.(ECE Dept.), Bengaluru
[email protected] cell: +91 9449851913