ERROR RESISTANT SCHEMES FORALL-DIGITAL HIGH DEFINITION TELEVISIONbyPanagiotis NasiopoulosB. Sc. (Physics) Aristotelion University of ThessalonikiB. A. Sc. (Electrical Engineering) University of British ColumbiaM. A. Sc. (Electrical Engineering) University of British ColumbiaA THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinTHE FACULTY OF GRADUATE STUDIESDEPARTMENT OF ELECTRICAL ENGINEERINGWe accept this thesis as conformingto the required standardTHE UNIVERSITY OF BRITISH COLUMBIAApril 1994© Panagiotis Nasiopoulos, 1994In presenting this thesis in partial fulfilment of the requirements for an advanceddegree at the University of British Columbia, I agree that the Library shall make itfreely available for reference and study. I further agree that permission for extensivecopying of this thesis for scholarly purposes may be granted by the head of mydepartment or by his or her representatives. It is understood that copying orpublication of this thesis for financial gain shall not be allowed without my writtenpermission.•__(Signature)Department of ,CJ2;,F/ ,))1 27}/?:: 1)’7iThe University of British ColumbiaVancouver, CanadaDate________________DE-6 (2188)AbstractThe picture quality of digital HDTV in the presence of bit errors in the transmissionchannel is addressed in this thesis. New coding and data synchronization schemes whichimprove the performance of the picture quality are subsequently developed.I first analyze the causes of the different kinds of digital picture impairments which mayarise when the compression schemes proposed by the present HDTV systems are used. Allthese compression schemes are Discrete Cosine Transform (DCT) based. The picture qualityperformance is found to suffer mostly from the proposed differential coding of the DC termsof the DCT coefficients and from the variable length coding used. Due to the differentialcoding of the DC terms a bit error in one of these terms will propagate to consecutive bits.The use of variable length coding, i.e., coding the different DCT terms by words of differentlengths, results in the synchronization problem where the received bits do not correspondanymore to the originally intended information.I develop a new method which codes the actual values of the DC terms instead oftheir differences. This solves the error propagation problem without altering the overallcompression ratio of the system. To solve the synchronization problem, I present a newsynchronization method which restricts the effects of any bit error to a block of the picturewhose size is much smaller than those presently proposed by the HDTV systems. Bymodifying the originally proposed schemes for HDTV with my proposed DC term encodingand synchronization schemes, the signal-to-noise ratio at which the HDTV picture suddenlydeteriorates is deferred by 2.5 to 3 dB. This has a special advantage when higher ordermodulation transmission schemes are used. Using higher order modulation improves the bit11transmission rate but increases the system’s susceptibility to noise.I then develop a novel fixed length coding method which compresses each DCT coefficient by a codeword of a fixed length. Fixed length coding methods do not suffer fromthe error propagation and synchronization problems inherent in the variable length codingmethods. Thus, my method is extremely resistant to errors, produces high quality picturesand is easier to implement. However, it does not improve the compression ratio. It is, thus,an ideal candidate for compressing video sequences with fast motion, such as sports, wherethe high compression ratios obtained by the motion compensation schemes are not attainabledue to the fast motion.Finally, a hybrid method that modifies the originally proposed HDTV schemes using thethree above proposed methods is presented. The three modifications involve the use of thefixed length coding method, the actual DC coding method and the synchronization scheme Ideveloped. These modifications significantly improve the picture performance of the systemin the presence of noise and do not alter the overall data transmission rate.111Table of ContentsAbstract iiListofFigures viiList of Tables xivAcknowledgment xviChapter 1 INTRODUCTION 11.1 THESIS SCOPE 4Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISYCONDITIONS— ANALYSIS AND MEASURES FORIMPROVEMENT 72.1 INTRODUCTION 72.2 SYSTEM MODEL DESCRIPTION 102.2.A Video Compression Model 102.2.B Digital Transmission 182.3 STUDY AND CLASSIFICATION OF THE EFFECTS OF BIT ERRORSON COMPRESSED IMAGES 21Errors due to a DC coefficient 25Errors due to an AC coefficient 282.4 A NEW NOVEL METHOD FOR CODING THE ACTUAL DC VALUES OFDCT COEFFICIENTS 322.5 SUMMARY 40ivChapter 3 A NOISE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIA 413.1 INTRODUCTION 413.2 SYNCHRONIZATION AT 32X16 PIXEL LEVEL FOR ALL FRAMES .. . 473.3 TWO-SYNC BLOCK SIZE METHOD 523.4 USING HIGHER ORDER MODULATION SCHEMES 643.5 SUMMARY 69Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSIONSCHEME 704.1 INTRODUCTION 704.2 A FIXED LENGTH CODING OF FREQUENCY COEFFICIENTS 734.3 APPLICATION OF OUR DCT FIXED LENGTH CODING METHOD ONCOLOR IMAGES 824.4 COMPARING OUR FLC METHOD WITH ABSOLUTE MOMENT BLOCKTRUNCATION CODING 904.5 USE OF HIGHER ORDER MODULATION SCHEMES 984.6 SUMMARY 102Chapter 5 A NOISE RESISTANT SCHEME FOR HDTV SYSTEMSAND FULL-MOTION MULTIMEDIA WHICH USES A FIXEDAND A VARIABLE LENGTH CODING METHOD 1035.1 INTRODUCTION 1035.2 A HYBRID FLCNLC METHOD 106V5.3 A ROBUST SCHEME WHICH COMBINES THE FLC, FRAME-ADAPTIVESYNCHRONIZATION, AND ACTUAL DC CODING METHODS 1145.4 SUMMARYChapter 66.1 TOPICS6.1.A122CONCLUSIONS AND RECOMMENDATIONS 123FOR FUTURE STUDY 125Improving the Compression Performance of our Fixed LengthCoding Method 125Using our Fixed Length Coding Scheme to Compress theKarhunen-Loève Transform Coefficients 126Compression of DCT Coefficients Using Fractals 129132BibliographyAppendix A Bit Error Rate Performance 140Appendix B Partitioning of DCT Coefficients into Regions 141Appendix C Quantization Levels for Negative DCT Coefficients ... 144Appendix D Bit Size of FLC Coefficients and Locations for 0 = 3 . . 146Appendix E List of Acronyms 1486.1.B6.1.CviList of FiguresFigure 2.1 Full-motion video HDTV encoder — decoder 11Figure 2.2 Detailed block diagrams of the encoder and decoder videoprocessing subsystems 13Figure 2.3 Compression of a 3x(32x16) color image area into a 40x16superblock 14Figure 2.4 Zigzag sequence of quantized DCT coefficients 16Figure 2.5 Block diagram of the communication scheme used by ourmodel 20Figure 2.6 Original and decompressed images obtained using qualityfactor Q = 3, under noiseless conditions. Compression ratioof the corresponding color image 12.60: 1 22Figure 2.7 Image obtained using baseline-JPEG compression over anoisy channel (SNR = 16 dB) 23Figure 2.8 Image obtained using end-of-block codeword synchronizationat 16 dB SNR channel noise 25Figure 2.9 Image obtained by the average-DC extrapolation method at16 dB SNR channel noise 28Figure 2.10 Image showing the visual effect of wrong alignment at thedecoder due to the inefficient synchronization achieved by theend-of-block codeword (channel SNR = 16.5 dB) 30viiFigure 2.11 Distribution of size frequencies of DC differences at threedifferent quality factors (a) and average distribution of sizefrequency (b) 33Figure 2.12 Distribution of the size frequency of DC coefficients at threedifferent quantization levels (Q=1, Q=3, and Q=16) 35Figure 2.13 Impaired image obtained by the differential DC codingmethod in the presence of noise 39Figure 2.14 Image obtained by our actual DC coding method under thesame noise conditions as the image shown in Figure 2.13.. 39Figure 3.1 Reference image obtained using DigiCipher/CCDCmacroblock-pointer method at channel SNR = 15 dB (RMSE=39.21) 43Figure 3.2 Fifth frame from the reference frame (Figure 3.1) usingDigiCipher/CCDC at 15 dB channel SNR (RMSE = 69.22). . 43Figure 3.3 ADTV data-line. Note that up to 5 slices can fit in one data-line.An error in slice 2 will result in the loss of slice 2 ,3, 4 and 5. . 45Figure 3.4 Image obtained using our 32x16 superblock headercodewords at 15 dB SNR channel noise (RMSE = 12.04).. 50Figure 3.5 Image obtained using our 32x16 superblockheader-codewords in conjunction with our actual DC codingmethod at 15 dB SNR channel noise (RMSE = 6.30) 50vii’Figure 3.6 Fifth frame from the reference frame (Figure 3.5) obtainedusing our actual DC coding scheme and the 32x1 6 inter-framessync blocks at 15 dB SNR channel noise (RMSE = 27.28). . 51Figure 3.7 Reference image obtained using our synchronization schemefor an 8x8 pixel sync blocks at channel SNR = 15 dB (RMSE=3.81) 56Figure 3.8 Fifth frame from the reference frame Figure 3.7 obtained by a32x16 inter-frames sync blocks at 15 dB channel SNR(RMSE = 28.53) 56Figure 3.9 Fifth frame from the reference frame Figure 3.7 obtained by a32x1 6 inter-frames sync blocks in conjunction with the actualDC coding scheme at 15 dB channel SNR (RMSE = 25.07).. 57Figure 3.10 Reference image obtained using our synchronization schemefor a 16x16 pixel level at channel SNR = 15 dB (RMSE =9.11) 61Figure 3.11 Fifth frame from the reference frame Figure 3.10 obtained byusing a 64x1 6 synchronization scheme for the inter-frames at15 dB channel SNR (RMSE = 30.01) 61Figure 3.12 Reference image obtained using our synchronization schemefor a 16x16 pixel level and our actual coding scheme atchannel SNR = 15 dB (RMSE = 8.02) 62ixFigure 3.13 Fifth frame from the reference frame Figure 3.12 obtained byusing a 64x16 synchronization scheme for the inter-framesand our actual DC coding scheme at 15 dB channel SNR(RMSE = 26.55) 62Figure 3.14 Same as Figure 3.7 but at 32—QAM instead of 16—QAM(RMSE = 10.09) 66Figure 3.15 Same as Figure 3.9 but at 32—QAM instead of 16—QAM(RMSE = 29.80) 66Figure 3.16 Same as Figure 3.12 but at 32—QAM instead of 16—QAM(RMSE = 20.00) 67Figure 3.17 Same as Figure 3.13 but at 32—QAM instead of 16—QAM(RMSE=34.07) 67Figure 3.18 Reference image obtained by DigiCipher at 32—QAM and 15dBSNR 68Figure 3.19 Fifth frame from the reference frame (Figure 14) obtained byDigiCipher at 32—QAM and 15 dB SNR 68Figure 4.1 Overview of the fixed length four quantization levelscompression technique of DCT coefficients 81Figure 4.2 Digital Video Encoder (a) and Decoder (b) Block Diagrams . 83Figure 4.3 Zigzag sequence of quantized DCT coefficients 85Figure 4.4 Partitioned original luminance 8x8 block of DCT coefficientsinto 5 regions 85xFigure 4.5 Partitioned original chrominance 8x8 block of DCTImage obtained by DigiCipher using 16 QAM at 15 dB SNR(this image requires 70217 symbols to be transmitted). . . 100Image obtained by our fixed length coding method using 16QAM at 15 dB SNR (this image requires 79643 symbols to betransmitted) 100Image obtained by DigiCipher using 64 QAM at 15 dB SNR(this image requires 46811 symbols to be transmitted). . . 101Image obtained by our fixed length coding method using 64QAM at 15 dB SNR (this image requires 53089 to betransmitted) 101xicoefficients into 3 regions. . 89Figure 4.6Figure 4.7Figure 4.8Figure 4.9Figure 4.10Figure 4.11Figure 4.12Figure 4.13Figure 4.14Image obtained by using our FLC method (RMSEImage obtained by using AMBTC (RMSE = 6.88).Image obtained by JPEG (RMSE = 4.01).Difference image of Figure 4.6 (FLC)Difference image of Figure 4.7 (AMBTC)Difference image of Figure 4.8 (JPEG)Image obtained by using our FLC method (RMSEImage obtained by using AMBTC (RMSE = 7.35).Difference image of Figure 4.12 (FLC)= 4.76). . 909192939394= 5.92). . 95959696Figure 4.15 Difference image of Figure 4.13 (AMBTC).Figure 4.16Figure 4.17Figure 4.18Figure 4.19Figure 5.1 Image obtained by the DigiCipher coding method at 15 dBSNR. Compression ratio = 12.60: 1 109Figure 5.2 Image obtained by the DigiCipher system using VLC and ourFLC methods at 15 dB SNR. Compression ratio = 14.69: 1 109Figure 5.3 Image obtained by the DigiCipher coding method at 15 dBSNR. Compression ratio = 6.40: 1 110Figure 5.4 Image obtained by the DigiCipher system using VLC and ourFLC methods at 15 dB SNR. Compression ratio = 11.30: 1 110Figure 5.5 Image obtained by the DigiCipher coding method at 15 dBSNR. Compression ratio = 16.62: 1 111Figure 5.6 Image obtained by the DigiCipher system using VLC and ourFLC methods at 15 dB SNR. Compression ratio = 18.20: 1 111Figure 5.7 Image obtained by our hybrid FLCNLC, DC, 1 6x1 6 sync blocksmethod at 15 dB SNR. Compression ratio = 14.14:1. . . 117Figure 5.8 Image obtained by the VLC, DC, 1 6x1 6 sync blocks methodat 15 dB SNR. Compression ratio = 12.00: 1 117Figure 5.9 Image obtained by our hybrid FLCNLC, DC, 1 6x1 6 sync blocksmethod at 15 dB SNR. Compression ratio = 16.60 :1. . . 118Figure 5.10 Reference image obtained by DigiCipher at channel SNR =15dB 120Figure 5.11 Fifth frame from the reference frame Figure 5.10 obtained byDigiCipher at channel SNR = 15 dB 120xiiFigure 5.12 Reference image obtained by our hybrid FLCNLC, DC,16x16 sync blocks method at channel SNR = 15 dB..... 121Figure 5.13 Fifth frame from the reference frame Figure 5.12 obtained byour hybrid FLCNLC, DC, 16x16 sync blocks method atchannel SNR = 15 dB 121Figure 6.1 Image obtained by the fixed length KLT method.Compression ratio 15.37 : 1 127Figure 6.2 Image obtained by AMBTC. Compression ratio 9.14 : 1. . . 127Figure 6.3 Difference image of Figure 6.1 128Figure 6.4 Difference image of Figure 6.2 128Figure 6.5 Similar regions in image of “Eleni” at different scales andorientations 129Figure 6.6 Decompressed image of “Eleni” obtained by fractal coding.The compression ratio of the luminance component is 6.2 : 1which is slightly higher than the 5.8 : 1 obtained by JPEG (forapproximately the same RMSE in both cases) 131Figure A.1 Reed-Solomon (116,106) coded versus uncoded 16—QAM.. 140XIIIList of TablesTable 2.1 Quantization weights for luminance (a) and chrominance (b) . 16Table 2.2 The pair of intermediate symbols used to represent the DCTcoefficients 17Table 2.3 Our new set of Huffman codewords for actual DC values.This set adapts to the quality factor Q which determines thesize of the DC coefficients 36Table 2.4 Compression ratios obtained by coding actual and differentialDC coefficients at two different quantization levels (Q=1 andQ=3) 37Table 3.1 This table shows different combinations of block sizes, thelength of the header-codewords for each size, theReed-Solomon protection code needed, and the total numberof extra bits required for one reference frame 54Table 3.2 This table shows the number of extra bits required fordifferent combinations of sync block sizes for the referenceand inter-frames 54Table 3.3 RMSE values for the first and the fifth frame of the videosequence “old city”, obtained by DigiCipher, oursynchronization method, and our synchronization method inconjunction with the actual DC coding method 60xivTable 3.4 Video data rates (Mbps) for the DigiCipher and the DigiCipherin conjunction with different version of our synchronizationmethod 63Table 4.1 The four quantization levels used to reconstruct the DCTcoefficients and the 2—bit code that identifies the pixel level. . 80Table 4.2 RMSE and compression rates for FLC and AMBTC 97Table 5.1 Number of blocks encoded by FLC for each image, thepercentage of bits encoded by FLC and compressionratios 108Table 5.2 Compression ratios of “Lena”, “Mandril” and “Hockey Player”obtained by VLC and different combinations of our codingand synchronization methods 116Table B.1 Grey values of an 8x8 pixel block (a) and the resultingweighted DCT coefficients (b) with weights of Table 2.la andquality factor Q = 3 141xvAcknowledgmentFirst, my greatest debt of gratitude goes to my supervisor, Professor Rabab K. Ward,from whom I received the most valuable inspiration, encouragement and support. I wouldalso like to thank Dr. Takis Mathiopoulos and Mr. Dimitrios Bouras for their friendship,advice and suggestions.I am very grateful to Dr. Mike Sablatash of the Communications Research Centre forproviding me with the preliminary submissions of the HDTV proposals. A special note ofthanks to Di-. Matthew Yedlin and Dr. Hussein Alnuweiri for the helpful discussions wehave had over the past two years.I dedicate this work to my parents, my daughter Eleni and my son Akyla.xviChapter 1INTRODUCTIONThe world of communications and broadcasting is in the throes of transformation. Forthe past two years, impressive progress in computer-imaging technology, full-motion videocompression, and digital signal processing has linked the futures of the computer, telephone,and television industries, and has stirred a convergence of these technologies into an all-digital telecomputer system [1, 2, 15, 23, 39, 59, 62, 69, 72]. It began in 1990 with theUnited States’ announcement to adopt an all-digital High Definition Television (HDTV’)system, entirely different from the analog Japanese high-vision project [4, 9, 21, 30, 31, 551.In 1968 the Japanese Broadcasting Corporation, NHK, pioneered HDTV research whichresulted in the development of the first HDTV system, known as the MUSE (MultipleSub-Nyquist Sampling Encoding) system [9]. In 1986, the Eureka EU-95 project aroseas a European response to MUSE and marked the beginning of the development of theHD-MAC (High Definition Multiplexed Analog Component) system [6, 7, 9, 16, 33].North America was the last to enter the HDTV arena. The rules and regulations of theFederal Communications Commission (FCC) and the idiosyncrasies of satellite and terrestrialbroadcasting in North America made this effort more challenging than MUSE or HD-MAChad been [4, 8, 9, 12, 14, 16, 31, 42]. The move to digital began in June 1990 whenGeneral Instruments Corp. announced its DigiCipher all-digital system [18, 36, 61]; by April3, 1992 another three organizations, the American Television Alliance (MIT and GeneralInstruments) [11], the Advanced TV Research Consortium (NBC, David Sarnoff ResearchCenter, Philips, and Thomson Consumer Electronics) [3], and Zenith and AT&T [20, 37]submitted descriptions of their all-digital HDTV systems.See List of Acronyms in Appendix D.1Chapter I INTRODUCTIONHigh Definition Television (HDTV) has been hailed as the world’s most significant newtechnology, stirring a transformation of markets for information and entertainment [2, 23,69, 72). The main objective of HDTV development is to provide a high quality widescreenimage comparable to that of motion pictures [4, 9, 63, 66]. An HDTV image has four timesthe luminance definition of the conventional NTSC images. Furthermore, the luminanceis separated from the chrominance for excellent color rendition. Digital HDTV signalsoccupy six to eight times more bandwidth than their analog counterparts, requiring datatransmission rates of approximately 1 Gbps; for transmission purposes this would occupya bandwidth too wide to be practical. As a result, the applicability of an HDTV systemdepends heavily on the use of data compression [5, 7, 34]. Powerful compression schemessuch as MPEG (Motion Pictures Experts Group) have been invented which, in conjunctionwith efficient modulation techniques (e.g., QAM— quadrature amplitude modulation), canreduce bit rates to the 6 MHz bandwidth required by the FCC [3, 5, 11, 18, 20, 44, 47,70]. As the focus of HDTV has broadened and with the HDTV system evolving into amultimedia telecomputer, more services such as video-telephony and computer informationwill be added to the system, increasing the demand for greater compression. Cable companiesand broadcasters in North America are now considering transmitting two HDTV signals ineach 6 MHz channel [52]. Furthermore, there is consideration given to converting the analogNTSC signals to digital and, by using techniques similar to those of HDTV, transmit up to10 digital NTSC signals within each 6 MHz channel. With the future additions of video-telephony and computer information to the system, it is obvious that further reduction ofthe transmission rate will be essential. To accomplish that, efforts are being directed towardincreasing the order of the modulation schemes2 (i.e., increase the number of modulation2 The use of I 6—QAM, 32—QAM, and 4—VSB modulation schemes was considered by the original all-digital HDTV proposals [3, 11,18, 20].2Chapter 1 INTRODUCTIONlevels) [2, 15, 52]. As the number of modulation levels in the transmitted data is increased,the difficulty in distinguishing between the levels increases [14, 52, 58]. Since we are notfree to increase the carrier power as the order of modulation is increased, the system becomesmore susceptible to errors. Higher order modulation techniques will thus increase the errortransmission rate and force the systems to operate at higher signal-to-noise ratios (SNR)[51, 58]. This is a serious issue, since compressed digital video services tend to deteriorateabruptly in the presence of noise. Unlike the analog TV images which deteriorate graduallyas interference increases, the digital HDTV and all other forms of multimedia pictures simplyvanish [4, 31, 64, 65]. Error correcting codes allow operation at lower signal-to-noise ratios.Beyond a certain SNR the probability of errors being uncorrected significantly increases,resulting in the sudden deterioration of the picture (see Appendix A). Errors, however, mightstill occur above that SNR critical value. The signal must be transmitted a certain distancebefore channel distortion causes erroneous bits to reach the receiver. If erroneous bits reachthe decoder, they cause misinterpretation of the bit stream. Also because of the variablelength encoding methods and the differential coding techniques used by the compressionschemes, these errors might propagate to the rest of the frame and to the following frames;synchronization of the data with the blocks they represent is lost and this causes the suddendegradation of the digital picture. “One home receiver might get an excellent picture andthe receiver just down the block might get nothing,” said James Carnes, head of the DavidSarnoff Research Center [31]. This error sensitivity of compressed digital signals is one ofthe most critical problems facing the emerging multimedia services today. System robustnessis essential so that short durations of interference will not produce catastrophic effects, butrather a gradual deterioration of the picture.Our aim in this thesis is to develop methods which will improve the picture performance3Chapter / INTRODUCTIONof digital HDTV and other forms of full-motion multimedia in the presence of bit errors.Our plan of research as well as our contributions are summarized in the following section.1.1. THESIS SCOPEOur objectives are:1. To analyze the full-motion video compression schemes and study the causes of the differentkinds of picture impairments.2. Based on the findings of the above study, to develop methods which will increase the noiseresistance of the video compression schemes.3. To address awi provide an efficient solution to the synchronization problem caused by thevariable length coding (VLC) used by the compression schemes.4. To develop a new method that significantly improves the overall error-robustness of theHDTV system and eliminates the sudden picture loss characteristic of compressed digitalservices while maintaining the other desirable qualities of the proposed systems.In Chapter 2, we study the performance of the picture quality of HDTV in the presenceof bit errors and we investigate in great detail the problems associated with picture coding.The potential sources of image impairments are identified and classified. We find that inthe presence of noise the quality of the picture is mainly affected by the variable lengthcoding which causes desynchronization problems resulting in deterioration of the imagequality. Besides the synchronization problem, we find that the errors in the DC coefficientsseriously affect the quality of the picture and that the proposed coding of DC coefficients (asdifferences between the DC levels of consecutive picture blocks) is the most sensitive partof the coding scheme. The traditional differential DC coding, whose intent is to improvethe compression of the system, increases the sensitivity of the system to errors. To solve the4Chapter / INTRODUCTIONproblem associated with the differential coding of the DC coefficients we develop a methodthat codes the actual DC values instead of their differences. Using our method it is possibleto obtain compression rates comparable to those of the differential DC method. However,our method does significantly improve the error resistance of the full-motion compressionscheme while reducing the complexity of the system.Variable length coding entails representing different blocks of the picture by segments ofdata bits which contain different number of bits. When a bit error occurs, the synchronizationof the data bits with the blocks they represent may be lost and the effects of the bit errormight propagate to adjacent blocks of the picture. The synchronization problem and thesolutions presently offered by the HDTV proposals are discussed in detail in Chapter 3.Although all HDTV proposals provide measures for synchronizing the transmitted data withthe picture blocks, they still allow a bit error to affect large areas of the image. As a result, asthe signal-to-noise ratio (SNR) drops below a certain threshold value, sudden deteriorationof the picture occurs. To solve the synchronization problem, we introduce a new frame-adaptive synchronization method which provides synchronization at block levels much lowerthan those used by the proposed HDTV methods. Our new method significantly improves theerror-resistance performance of the system by restricting the affects of a bit error to imageareas much smaller than those of the proposed systems. Further improvement of the pictureperformance of the system is obtained by incorporating this synchronization method with theactual DC coding method presented in Chapter 2.The combination of the Discrete Cosine Transform (DCT) and variable length codinghas emerged as the most popular compression scheme. This is because this combinationyields excellent compression ratios and high quality reconstructed images. This scheme,however, is very sensitive to bit errors, resulting in error propagation and desynchronization5Chapter I INTRODUCTIONproblems which deteriorate the quality of the image in the presence of noise. In Chapter 4,we introduce a novel fixed-length compression method (i.e., each picture block is encodedby a fixed number of data bits). Our method uses fixed length codewords to compress theDCT coefficients of the different picture blocks. This method has the distinct advantage ofbeing fixed length and also yields high quality images comparable to the DCT-based codingmethods. Since our method has no synchronization problems, it is ideal for use with higherorder modulation schemes which are more noise prone than the lower order levels. Thismethod, however, does not offer higher compression ratios than the VLC based methods.In Chapter 5, we combine our fixed-length coding (Chapter 4) with the VLC method. Thishybrid method improves the compression of the VLC based system by approximately 20%.To further improve the error resistance of the system we combine this hybrid method withour new synchronization method (Chapter 3) and our actual DC coding method (Chapter2). The resulting scheme has excellent error performance characteristics and significantlyimproves the picture performance of the system in the presence of noise, without alteringthe total transmission rate. After that, the deterioration of the picture becomes much moregraceful than that of the proposed HDTV systems, thus eliminating the sudden picture losscharacteristic inherent in compressed digital video services. In Chapter 6, we summarize theaccomplishments of our research and we discuss future research directions.6Chapter 2HDTV PICTURE QUALITY PERFORMANCEUNDER NOISY CONDITIONS— ANALYSISAND MEASURES FOR IMPROVEMENT21. INTRODUCTIONDigital High Definition Television (HDTV) is upon us. Impressive advances in the field ofstill-image compression (Joint Photographic Experts Group— JPEG), video teleconferencing(Consulting Committee on International Telegraph and Telephone — CCITT) and full motioncompression (Moving Pictures Experts Group— MPEG) have stirred an explosion in theworld of communications and have led to the development of all-digital HDTV [4, 9, 18,30, 34, 38, 39, 42—44, 54, 57, 63, 68].Unlike the digital audio signals of the past, the applicability of the digital HDTV systemsdepends on the use of data compression. The four HDTV proponents [3, 11, 18, 20] presentlyforming the “Grand Alliance” are DigiCipher (by General Instruments), Channel CompatibleDigiCipher (CCDC) (by the Massachusetts Institute of Technology in conjunction with theGeneral Instruments), Advanced Digital Television (ADTV) (by David Sarnoff and Philipslaboratories) and Digital Spectrum Compatible HDTV (DSC-HDTV) (by Zenith and AT&T).All four HDTV proposals adopt compression schemes which are based on the compressionstandards mentioned in the previous paragraph and are able to compress the digital videoHDTV signals to approximately 15 Mbps [5, 43, 68]. Efficient modulation techniques (e.g.,QAM— quadrature amplitude modulation) are then used to further compress the data bit7Chapter 2 HDTV PICTURE QUALiTY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENTstream into symbols and thus yield symbol rates which fall within the required 6 MHzbandwidth [9, 12, 14, 32, 67].The compression of the digital HDTV signals is the cause of the system’s sensitivity toerrors, a critical concern of the emerging HDTV system. Compression methods are based onredundancies in data and the nonlinearities of human vision. The Discrete Cosine Transform(DCT) has emerged as the most powerful compression technique for still images. All theHDTV proposals use DCT to exploit the spacial correlation within a frame and they couple itwith motion estimation for the reduction of temporal redundancies between adjacent frames.Motion compensation involves estimation of motion vectors, of blocks of predefined sizes,between two consecutive frames. Once a motion vector is estimated, the predicted blockof the new frame is subtracted from the actual corresponding block in the new frame. Theresulting differences of all the blocks in the new frame are compressed in the same manneras the still-image, i.e., they are (DCT) transformed, quantized, and encoded using variablelength coding techniques. The encoding process yields variable and fixed length words. Thefixed length words are replaced by Huffman (variable length) codewords to further improvethe compression rate [19, 43, 44, 70]. Although the above procedures add up to a verypowerful compression scheme, they are only able to work in an error free environment [56,64, 65]. Thus, to minimize the effects of transmission errors, Forward Error Correction (FEC)codes are used [3, 11, 18, 20, 43, 48]. However, errors will still remain even with the use ofthese codes [51, 58]. When erroneous bits reach the decoder they cause misinterpretation ofthe codewords and, because of the variable length coding (VLC), these errors will propagateto the rest of the codewords resulting in desynchronization of the bit stream and suddendeterioration of the picture quality.8Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENTOur aim in this chapter is to improve the quality of the video pictures in the presenceof residual errors, i.e., in the presence of uncorrected errors beyond the capability of theerror correction code used. To address this issue we analyze the DCT based transform videocompression scheme and study the causes of the different kinds of picture impairments thatmight arise when this scheme is used with the variable length coding (VLC). Impairmentssuch as loss of information in some parts of the picture, vertical bars, picture slicing effects,and abrupt intensity changes within the picture may occur depending on which bit in the datastream is in error. The potential sources of image impairments and the problems associatedwith picture coding are identified and classified. We find that while effects of uncorrectederrors in certain bits go unnoticed, errors in other bits, which represent different information,have drastic results on the quality of the picture. The results of our study show that theloss of synchronization and the DC coefficients coding are the parts of the coding schemewhich are most sensitive to errors. The presently proposed differential coding of DC terms— as the differences between the DC’ s of consecutive 8x8 pixel blocks — increases thenoise sensitivity of the system. As a remedy we propose a novel method which codes theactual DC values instead of their differences. We show that, contrary, to present belief, itis possible by using actual DC value coding to obtain compression ratios which are almostas high as those obtained by the differential DC coding method. By encoding actual DCvalues, the noise resistance of the coding scheme improves significantly.The organization of this chapter is as follows. In Section 2.2 we describe the HDTVcompression model. In Section 2.3, we study and classify the effects of bit errors oncompressed images and we identify the most error sensitive parts of the compression scheme.In Section 2.4, we introduce a new method which codes the actual values of the DC9Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENTcoefficients and improves the error resistance of the coding scheme.2.2. SYSTEM MODEL DESCRIPTION2.2.A. Video Compression ModelWe have implemented a generic model to simulate an all-digital HDTV system. Ourintra-frame compression method was based on the DCT coding of 8x8 pixel blocks followedby variable length coding and Huffman coding. This compression scheme has been adoptedwith some variations by the DigiCipher, ADTV, and CCDC HDTV systems [3, 11, 18,20]. The inter-frame compression method used in our model is the same as the one usedby DigiCipher. Figure 2.1 shows the block diagram of the full-motion video encoder anddecoder.10Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENTFigure 2.1. Full-motion video HDTV encoder— decoder.DECODERto channelENCODER11Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENTThe video encoder processes a picture in 8x8 pixel blocks and in 32x16 pixel superblocks(32 pixels in the horizontal direction and 16 pixels in the vertical direction). Each superblockconsists of 8 luminance blocks and it is also associated with one U and one V chrominanceblock derived from the same 32x16 image area. The 8 luminance blocks and the U and Vblocks are assembled into a 40 x16 pixel superblock as will be shown in Figure 2.3. Ourchoice of the size of blocks and superbiocks was based on the DigiCipher HDTV systemproposal [18]. The CCDC HDTV system and the ADTV system use similar coding method,with a different superblock size of (16x16) pixels [3, 11]. The DSC-HDTV system uses acombination of 32x16 and 16x16 pixel superblocks [20].Detailed block diagrams of the encoder and the decoder video processing subsystemsare illustrated in Figure 2.2.12Chapter 2 HDTV PICTURE QUAL1TY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENTFigure 2.2. Detailed block diagrams of the encoder and decoder video processing subsystems.After converting the RGB signal into the YUV color space, the chrominance signals (Uand V) are sampled at lower spatial resolution and hence are represented by fewer bits thanthe luminance signal (Y). Horizontal decimation in the chrominance signal is achieved byapplying a digital Finite Impulse Response (FIR) low-pass filter and then subsampling by13RGBof DCTDCT HH Quantization_H Encoding HcoefficientsDECODERRGBChapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENTa factor of 4. At the decoder, horizontal interpolation is performed by zero-padding andapplying the same filter with the gain increased by a factor of 4. Vertical decimation by afactor of 2 is obtained by discarding every other line. The receiver reconstructs the imageby repeating each chrominance line. The luminance signal (Y) bypasses the filters and thusmaintains its full resolution (see Figure 2.2). The U and V information of a 32x16 block arenow each represented by an 8x8 block. Thus a 3x(32x 16) color-image area is now representedby a 40x 16 data block (also referred to as a superblock). A graphical representation of theabove convention is illustrated in Figure 2.3.16LUMINANCEV16__CHROMINANCE I32______V..Figure 2.3. Compression of a 3x(32x1 6) color image area into a 40x16 superbiock.The DCT is applied onto each 8x8 pixels block, transforming it into a new block(matrix) of frequency coefficients. In the resulting matrix, the direction of the increase of14Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENTthe horizontal frequency is from left to right and the vertical frequency is from top to bottom[19, 34]. Since the human eye is less sensitive to energy with high spatial frequencies,some of the DCT coefficients are visually more important than others. For this reason,non-uniform quantization is used to quantize the coefficients. The non-uniform quantizationprocess is achieved by dividing each coefficient by a different weight. The weights varywith the frequency, the low-frequency coefficients are quantized using smaller quantizationsteps than the high-frequency ones [101. The human visual system is less susceptible toquantization noise in the chrominance than in the luminance components and for this reason,the chrominance can be quantized more coarsely by a different set of weights. The weight-sets implemented by our model are shown in Table 2.1. This set is one of many differentsets suggested by the JPEG standard and the proposed HDTV systems [3, 11, 18, 19, 20,34]; we found that all of the proposed tables yield relatively the same results. Each DCTcoefficient is divided by the respective weighting factor from the table. Lower compressionrates are obtained by dividing the quantization weights in Table 2.1 by a factor greater than1. This factor is called the quality factor (Q). As a result of applying the above non-uniformquantization, many of the resulting DCT coefficients (usually the high frequency ones) aredriven to a value of zero.15Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENT(a) (b)Table 2.1. Quantization weights for luminance (a) and chrominance (b)Following the above quantization, the coefficients are reordered into a one-dimensionalarray by reading out the entries of the two dimensional array along a zigzag sequence asshown in Figure 2.4.AC01DCAC 63Figure 2.4. Zigzag sequence of quantized DCT coefficients.Using the zigzag sequence, the coefficients are “approximately” arranged in order ofascending frequency. This process has proved to increase the number of consecutive DCTzero-coefficients and, as shall be shown, improve the compression ratios achieved by variablelength coding [19, 34, 41, 70].16 16 19 22 26 27 29 3016 16 22 24 27 29 34 3719 22 26 27 29 34 34 3822 22 26 27 29 34 37 4022 26 27 29 32 35 40 4826 27 29 32 35 40 48 5826 27 29 34 38 46 56 6927 29 35 38 46 56 69 8317 18 24 47 99 99 99 9918 21 26 66 99 99 99 9924 26 56 99 99 99 99 9947 66 99 99 99 99 99 9999 99 99 99 99 99 99 9999 99 99 99 99 99 99 9999 99 99 99 99 99 99 9999 99 99 99 99 99 99 9916Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENTThe final step in the compression process is the entropy encoding which is explained as atwo step process. The first step converts the zigzag sequence of the quantized coefficients intoan intermediate sequence of symbols. The second step compresses some of these symbolsusing Huffman coding.In the intermediate symbol sequence, each AC coefficient is represented by a pair ofsymbols, which are shown in Table 2.2 as symbol-i and symbol-2.symbol-i: [Runlength, Size]symbol-2: [Amplitude]Table 2.2. The pair of intermediate symbols used to represent the DCT coefficients.Symbol-2: represents the amplitude of this coefficient. The “runlength” in symbol-irepresents the number of consecutive AC coefficients whose values are zeros and whichprecede the AC coefficient represented in symbol-2. “Size” is the number of bits needed torepresent the amplitude of this AC coefficient. The maximum size allowed for the runlengthis 15 coefficients. Since actual zero-runs can be greater than 15, a symbol with value (15,0) is used to indicate continuation. This continuation symbol is not followed by symbol-2.Each 8x8 block can have a maximum of three continuation-symbols.As for the DC coefficients, they are also represented by symbol-i and symbol-2 as inthe AC coefficients case. The difference is that the symbol-i for DC coefficients consistsonly of information concerning the size of the amplitude, since in this case the runlengthis always zero.17Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENTSymbol-2 is simply the amplitude of the DC or the nonzero AC coefficient encoded asa variable-length integer. Because of the strong correlation between the DC coefficients ofadjacent 8x8 blocks, the DC coefficients are differentially encoded (i.e., in this case, symbol-2 represents the difference between the present DC coefficient and the previous adjacent DCcoefficient).For each 8x8 block, each DC and AC symbol-i are then losslessly encoded usingHuffman coding. This coding method assigns relatively short codewords to symbols with thehighest probability of occurrence. Symbols with low probability of occurrence are assignedlonger codewords. This results in a reduction in the number of bits needed to represent a dataset. The Huffman tables used for the coding of DC and AC coefficients are those adoptedby the JPEG baseline standard [19, 34].A special “end of block” (EOB) codeword was adopted by the HDTV proposals [3, 11,18, 20]. This EOB codeword is inserted at the end of each block marking the last non-zerocoefficient in a DCT block. It can also be used to help the decoder achieve synchronizationin the presence of bit errors. It is clear from the above that each 8x8 picture block isrepresented by a number of data bits that vary from one block to another. This referred toas variable length coding (VLC).2.2.B. Digital TransmissionTo deliver a high rate digital stream of data with a very high degree of reliability,all HDTV proposals employ some bandwidth efficient modulation techniques and powerfulFEC codes [3, 9, 16, 18, 20, 26, 27, 50, 67]. Our model employs 16 Quadratic AmplitudeModulation (QAM) coded by (116, 106) Reed-Solomon (RS) forward error correcting (FEC)18Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENTcode, as they are the most popular modulation and FEC techniques proposed amongst theHDTV proposals. However, it should be noted that the analysis of the compression schemethat follows (see Section 2.3) is independent of the transmission method since the objectiveof this analysis is to identify the relative sensitivity of the different parts of the compressionscheme to undetected bit errors. By employing a specific transmission scheme we are ableto define specific operating points, i.e., signal-to-noise ratios (SNR), at which our methodswill be compared against those of the existing HDTV proposals.Figure 2.5 shows the basic communication system blocks including the FEC coding, themodulation, the transmit and receive filtering, the demodulation and decoding blocks.3The Signal Processing WorkSystem® (SPWTM) software package was used for the computer simulation of the digital transmissionprocess [60].19Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENTFigure 2.5. Block diagram of the communication scheme used by our model.FromcompressionencoderTRANSMIHERTodigital videodecompressiondecoderRECEIVER20Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITiONS— ANALYSIS AND MEASURES FOR IMPROVEMENT23. STUDY AND CLASSIFICATION OF THE EFFECTSOF BIT ERRORS ON COMPRESSED IMAGESIn general, the distortions in HDTV pictures fall into one of the following two categories:(i) Artifacts which are due to the compression and quantization; and(ii) Impairments that result from transmission bit errors.Because our objective is the extensive study of the latter case, we selected the qualityfactor to be equal to 3, i.e., using 1/3 of the standard weight-coefficients shown in Table 2.1.This quantization yields high quality pictures but relatively small compression rates. Undernoiseless conditions, Figures 2.6(a) and 2.6(b) show the original and the decompressed Ycomponent of the image, respectively. The compression ratio of the corresponding colorimage in this case is 12.60 : 1.Since the U and V chrominance components are encoded in the same manner as the Ycomponent, we restrict the following analysis to the luminance component only.(a) Original image.21Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENTFigure 2.6. Original and decompressed images obtained using quality factor Q 3,under noiseless conditions. Compression ratio of the corresponding color image 12.60 : 1.Now assume that an uncorrected error in one of the transmitted bits occurs and that thisbit belongs to symbol—i of a certain DCT term. At the decoder, the resultant symbol—iwould either correspond to a nonexisting Huffman code or to an erroneous entry from theHuffman table. In either case, the erroneous decoding of the DCT coefficients may yieldintensity values that lie outside the values used for the representation of an image (0 —black; 255 — white). For the purpose of this study, in order to analyze and compare suchimpaired images, the decoder was adjusted so that it truncates all the intensity values thatare smaller or greater than the allowable intensity limits to 0 and 255 respectively. Figure2.7 shows an example of the visual effects on the test image when one error in symbol-iof a DCT coefficient occurs.(b) Decompressed image.22Chapter 2 HDTV PICTURE QUALiTY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENTIn this figure, we observe that because of an error, the decoder produces a few corruptedsuperbiocks and the error eventually leads into the complete loss of the image. The reasonis that the error has propagated to the Huffman codewords, representing symbol—i’s of DCand AC coefficients. Since the decoder was not able to find the erroneous entries in theHuffman tables, it assigned a zero (default) value to the corresponding coefficients. If adifferent default value is assigned, the intensity and the texture of the black area in the aboveimage will be different, but this area will lack any information about the actual image. Inthe above particular example, no synchronization schemes were used.A solution to the above problem is to restrict the effects of a bit error to the 8x8 blockin which the error occurred. This can be achieved if the end-of-block (EOB) codewordof each 8x8 block which is originally intended to indicate the end of non-zero coefficientsin the block— like the original EOB Huffman codeword used by JPEG and MPEG — isalso used to help the decoder achieve synchronization. Some attempts have been made toFigure 2.7. Image obtained using baseline-JPEG compression over a noisy channel (SNR = 16 dB).23Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDIT1ONS— ANALYSIS AND MEASURES FOR IMPROVEMENTdesign self-synchronizing Huffman codes [22, 40]. These codes contain a codeword that,in a probabilistic sense, helps the decoder resynchronize itself. The synchronizing methodsare based on the assumptions that the incoming data is a continuous Huffman-coded bitstream and that the only errors that occur are changes in the bit values, i.e., 0 to 1 and 1 to0. However, in the HDTV bit stream, Huffman coded data (symbol-i) and variable lengthcoded data (symbol-2) are concatenated in a single stream. An error in a Huffman codewordwill cause a bit slippage in symbol-2’s, preventing the decoder from resynchronizing evenif the Huffman coded part of the bit stream is error free. Thus, using the self synchronizingcodes and replacing the original EOB codeword with a synchronizing codeword does notprovide a solution to the above problem. Instead, we selected a sync-EOB codeword whichhas the largest Hamming distance from all entries in the Huffman table, i.e., it has thesmallest probability of being matched with one of the Huffman codewords and thus hasthe least chance of being mistaken. For this reason, this sync-EOB codeword is 16 bitslong, equal to the size of the largest Huffman codewords [19]. In addition to the aboveconstraints, this codeword should also have a small probability of being matched with asymbol-2. Thus, when an error occurs, the decoder tries to find this sync-EOB codewordand will eventually achieve synchronization. Figure 2.8 shows the resulting image when thesync-EOB codeword is added to the system.24Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENTFigure 2.8. Image obtained using end-of-block codeword synchronization at 16 dB SNR channei noise.It is obvious that the use of the sync-EOB codewords have achieved synchronizationbut the recovered image falls short of being visually acceptable. This is because evenif synchronization is achieved, once a DC term becomes erroneous it will affect all thesubsequent blocks (as will be discussed later).There are two types of errors:i. An error in the symbols related to a DC coefficient.ii. An error in the symbols related to an AC coefficient.i) Errors due to a DC coefficientEach DC and AC coefficient is represented as a codeword made of two parts: Symbol-iand Symbol-2. Each symbol-i is encoded using a Huffman code. If a bit error occurs in thesymbol-i of the codeword of a DC coefficient, the decoder searches the DC Huffman tablefor the corresponding entry. If an entry is found, then this will correspond to a wrong DC25Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENTvalue. In this case, the decoder will not realize that an error has occurred; the fact that thefound entry is erroneous will cause the decoder to assign an erroneous number of bits whichmay be either smaller or greater than the number of intended bits of this DC coefficient.Because of the VLC, this error will perpetuate to the following AC symbols and the effectsof the subsequent errors in the AC symbols will cause synchronization to be lost (as willbe discussed further in Chapter 3).However, if a corresponding entry in the Huffman (luminance or chrominance) table isnot found then the decoder by default assigns a zero value (or any other preset value) tothe DC coefficient. The decoder, realizing that an error has occurred, will now search forthe sync-EOB codeword and it will achieve synchronization. However, the DC coefficientis erroneously decoded, and more seriously all the DC coefficients of the consecutive blockswill also be affected. This is because each DC value is differentially encoded, i.e., it is thedifference in the DC levels between two consecutive blocks that are encoded. As a result,an error occurring in a symbol—i of a DC term of one block may lead to a complete loss ofinformation in consecutive areas of the image. The resulting visual effect can be observedon the image shown in Figure 2.8, where synchronization is achieved but parts of the pictureappear overexposed (white) due to the erroneous values of the DC coefficients.In an effort to adjust or minimize the effects that a wrong DC coefficient has on thequality of the reconstructed image, we tested a number of different methods that reconstructthe value of the DC coefficient. Before adjusting the DC term, however, the decoder hasto realize that such an error occurred. After introducing such a scheme and testing severaldifferent interpolation and extrapolation methods, none gave satisfactory results. Figure 2.9shows the best result which is obtained using an average DC value extrapolated from the26Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENTprevious blocks lying within the superblock in which the error occurred. In Section 2.4 weshall present a novel solution to this problem.If an error in one of the bits of symbol-2 of a DC coefficient occurs, then althoughsuch an error will not perpetuate to the following AC symbols, it will affect the DC valuesof the consecutive blocks. Unfortunately, the decoder cannot detect such an error. Theresulting visual effects on the picture depend entirely on the location of the erroneous bitwithin the symbol-2, i.e., an error in the most significant bit may lead to a complete lossof information in some areas of the picture, while an erroneous least significant bit will notaffect the visual quality of the picture at all, even though it will affect the amplitudes ofthe consecutive DC terms.From the above we conclude that the differential coding of DC coefficients may causeone of two serious problems: 1) loss of synchronization of the data and the blocks theyrepresent and 2) error propagation even if synchronization is not lost. Thus, an error in aDC coefficient seriously affects the quality of the picture.27Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENTii) Errors due to an AC coefficientWe now study the effects of one or more uncorrected errors occurring in the bits of thesymbol-i or symbol-2 codewords representing an AC coefficient. If an error occurs in asymbol-2 alone, it will not alter the visual quality of the picture. However, this is not thecase when an error occurs in a symbol-i of an AC coefficient.An error in symbol-i, as explained previously, can be the result of an error that hasoccurred in the preceding DC coefficient and has perpetuated to the AC symbol-i, or itcan result from the following situations. The symbol-i codeword consists of two piecesof information, the “runlength” and the “size” of the amplitude of the new non-zero ACcoefficient (see Table 2.2). An erroneous symbol-i codeword will either correspond to anexisting entry in the AC Huffman table or it will not. In the latter case, the decoder willFigure 2.9. Image obtained by the average-DC extrapolation method at 16 dB SNR channel noise.28Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENTlook for the sync-EOB codeword, i.e., the end of the block, and replace each in-betweenAC coefficient with zero or with other default value. This process generally results in ablurred 8x8 block and thus it does not constitute a serious error. However, it is more likelythat the decoder will, unfortunately, recover an erroneous entry from the AC Huffman table.This is bound to produce a faulty number of in-between zero coefficients and also assignan erroneous number of bits to the amplitude of the encoded non-zero AC coefficient. Theresulting misinterpretation of the encoded data bits will most likely cause the decoder toassume a part of the sync-EOB codeword as part of an AC symbol, and thus the syncEOB codeword of this block does not serve its function anymore. Search of the sync-EOBcodeword for this block will eventually find the sync-EOB codeword of the following block.Thus the sync-EOB codeword of the following block will be assumed to be that of thepresent block. This will cause two blocks to be interpreted as one block only. The sync-EOBcodeword obtained from this following block will eventually help the decoder to successfullyrecover the DC and AC coefficients for the rest of the blocks, but there is no way of correctlyidentifying the order of occurrence of blocks within a superbiock from this point on, i.e.,synchronization is lost.For example, if such an error occurred in a luminance block, and since a chrominanceblock of a superbiock follows four luminance blocks, a chrominance block will be wronglyassumed to be a luminance block. The luminance block following a chrominance one willbe assumed to be a chrominance block, and so on. This error will perpetuate until the end ofthe frame or until another error occurs. The vertical bars in Figures 2.8 and 2.9 are the resultof such erroneous identification of chrominance and luminance blocks. The location of allthe blocks is shifted, and chrominance blocks may take the place of some luminance blocks29Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENTand vice versa (see Figure 2.3). This process is passed to the following superbiocks and thechrominance blocks appear in the luminance component of the image aligned in columns.The idiosyncracy of the information contained in the chrominance blocks, and the fact thatthey consist mostly of a DC coefficient (since the U and V signals have been filtered), makethe intensity values produced from these blocks differ from the rest.The lack of synchronization also has a “slicing” effect on the image, making parts of itappear shifted. This can be seen on the image shown in Figure 2.10.From the above analysis we conclude that there are two main problems. The first problemrelates to the desynchronization of the data. The introduction of the sync-EOB codewordwas seen to be unable, by itself, to solve this problem. The second problem relates to thedifferential encoding of the DC terms. Even if there are no synchronization problems, errorsin the DC coefficient will still perpetuate to subsequent blocks. The use of differential DCFigure 2.10. Image showing the visual effect of wrong alignment at the decoder due to theinefficient synchronization achieved by the end-of-block codeword (channel SNR = 16.5 dB).30Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENTcoding is proposed by all four HDTV systems (and other image compression standards suchas JPEG and MPEG) and is by far the most noise sensitive part of the compression scheme.Although extrapolation of DC-values was seen to improve the quality of the impaired image,it did not deal directly with the propagation of errors caused by the differential DC coding. InSection 2.4 we propose a novel solution to the DC coefficient problem. The synchronizationproblem is addressed in Chapter 3.31Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENT24. A NEW NOVEL METHOD FOR CODING THEACTUAL DC VALUES OF DCT COEFFICIENTSWe propose coding the actual DC values instead of their differences, a process thatwould increase the noise resistance of the system by eliminating error propagation due todifferential encoding.The reason for using differential DC coding is to improve the compression ratio byexploiting the high correlation between adjacent DC coefficients [3, 11, 18, 19, 20, 43]. Aswe have seen in Section 2.2, the first step in the coding process of a DC coefficient involvesthe formation of a fixed length word, known as symbol-i, which contains the number of bitsneeded to represent the amplitude of this DC coefficient or the DC difference. This wordis followed by symbol-2 which is a variable length word containing the actual amplitudeof the DC coefficient or the difference. Because of the existing correlation among the DCcoefficients, the resulting DC differences are relatively small in size compared to the actualDC coefficients and as a result, smaller number of bits for symbol-2’s are transmitted. Sincesome of the symbol-i words occur more often than others, further compression is achievedby using Huffman coding. Thus instead of transmitting symbol-i, its corresponding Huffmancodeword is transmitted. As also seen in Section 2.2, the differential DC coefficients, as wellas the other AC coefficients, are usually divided by the adjusted quantization weights (Table2.1). The adjusted quantization weights are obtained by dividing each entry in Table 2.1 bythe quality factor Q. Since the quantization weight of the DC term in Table 2.1 is equal to16, the adjusted weight for the DC term is thus its actual value multiplied by Q116.Let us now study the frequency distribution of the amplitude sizes of the differential DC32Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENTcoefficient. The size is the number of bits needed to represent this term. Figure 2.11 a depictsthe frequencies at which the non-quantized sizes of the DC differences occur, as well as thefrequency distribution of these sizes at two quality factors 3 and 1. Figure 2.1 lb showsthe average distribution (over different Q’s) of the DC differences. The above results werederived using the average statistics of a large set of images.I Q=3HQ.1I • 16 (not quantized) I9CDCDD00C)C)CDC)CDAverage distribution600 —500 —400 —300 —200 —100 —1 2 3 4 5 6 7 8 9 10 11Bit—size of DC differencesINI I I I I I I I1 2 3 4 5 6 7 8 9 10 11Bit—size of DC differencesa bFigure 2.11. Distribution of size frequencies of DC differences at threedifferent quality factors (a) and average distribution of size frequency (b).We observe that the frequency distribution of the size of the DC differences changessignificantly with the quality factor. Since Huffman coding assigns shorter codewords to themost frequently occurring words, for each of the distributions in Figure 2.11 a correspondingdifferent optimal Huffman table exists. However, in real time applications such as HDTV,a single Huffman table is used which is generated based on the average distribution ofoccurrence of amplitude sizes (see Figure 2.1 lb) [3, 11, 18, 20). This means that thecompression efficiency of this Huffman code is very low (except when Q is approximatelyequal 3). In reality, except for values in the vicinity of 3, the Huffman code used is notoptimal and does not offer much compression of the differential DC values. Thus, most of33Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENTthe compression improvement obtained using differential DC coding does not result fromthe Huffman code (symbol-i’s) but from the size reduction in the transmitted amplitude(symbol-2).Let us now consider coding the actual values of the DC coefficients. For this methodto be successful it should compress the DC coefficients with an efficiency close to thatof the differential technique. Let us first investigate whether some amplitude sizes of DCcoefficients have higher probability of occurrence than others and if the distribution of theseoccurrences leads to an efficient compression when Huffman coding is used.Consider an image whose grey level values range from 0 (black) to 255 (white). Usingthe direct discrete cosine transform which is given by the formula:1 (2x+1)u7r (2y+1)virS =—C C S COSuv 4 u v xy 16 16 21x=O y=0where C , C = 1/v for u, v =0 and C , C = 1 otherwise,U V U Vwe find that the corresponding range of the non-quantized DC values of the DCT coefficientsis 0 to 2040 (i.e., is represented by words whose lengths vary from 1 to 11 bits), respectively.In general, the DC value is a measure of the brightness of an image. Since the average valueof image brightness is 127.5, the size of the corresponding DC coefficient, will be around1020 (or 10 bits long). Figure 2.12, which is based on results derived from a large numberof images, depicts the frequency distribution of the sizes of DC values for different qualityfactors. It is interesting to note that unlike Figure 2.11, the frequency distributions at differentQ’s have similar shapes with the exception of a shift in the horizontal direction. Also as Qis decreased, the maximum number of bits needed to represent the amplitude (the bit size)value decreases from that of 11 bits.34Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENT12001100,1000CD.0900800! 700600CD500400300200100Figure 2.12. Distribution of the size frequency of DC coefficientsat three different quantization levels (Q=1, Q=3, and Q=16).As Q decreases, the frequency distribution of the sizes of the DC coefficients will shiftto the left. This is a significant advantage over the differential method, because the overallpattern of the frequency distribution remains relatively unchanged (except for the shift andthe maximum number of bit size needed for the DC coefficients). Because of the relationshipbetween the Huffman coding and the frequency distribution, this means that we can use asingle set of Huffman codewords in this case, and this set will simply be shifted as Qdecreases. Thus, for each Q the resulting Huffman code will not deviate much from theU 0=1I 0=3•non—quantized(0=16)1 2 3 4 5 6 7 8 9 10 11Bit—size of DC coefficients35Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENToptimal one. This is unlike the DC differential case where the Huffman code used is farfrom optimal except for values near Q=3.Based on the probability distribution of the sizes of the DC coefficients, we derived the“adaptive” set of Huffman codewords shown in Table 2.3. This table shows how the same setof codewords is shifted to accommodate the size changes caused by different quality factors.Another advantage of this approach over the differential one is that as Q decreases the largercodewords are removed from the Huffman table. Note that in Table 2.3 the smallest numberof bits in the Huffman code is allocated for the average bit size (e.g. for bit size of 10 thecorresponding codeword is 00 when 8 < Q 16).Bit-size of DC Codewords Codewords Codewords Codewords Codewordscoefficient for for for for for8<Q16 4.<Q8 2.<Q4 1.<Q2 O.5.<Q111 010----10 00 010---9 011 00 010--8 100 011 00 010-7 101 100 011 00 0106 110 101 100 011 005 1110 110 101 100 0114 11110 1110 110 101 1003 111110 11110 1110 110 1012 1111110 111110 11110 1110 1101 11111110 1111110 111110 11110 1110Table 2.3. Our new set of Huffman codewords for actual DC values. This setadapts to the quality factor Q which determines the size of the DC coefficients.Since we encode the actual DC value and not the difference value, our method, unfortunately, has to use larger symbol-2 words. This is however compensated for since our36Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENTmethod yields a considerable improvement in compressing symbol-i over that of the differential approach. Table 2.4 shows the compression ratios obtained by our actual DC codingmethod and the differential coding method at two different quality factors, Q 1 and Q = 3.We observe that our method yields compression rates which are slightly less than those ofthe differential method. Performance evaluations have shown that for the compression of theDC coefficients, the efficiency of our method is 95% that of the differential coding method.However, since each DC coefficient comprises only a fraction of an 8x8 block, our overallcompression is, on average, 99% that of the DC differential method.Image Differential DC coding method Our DC coding methodquality factor = 3 quality factor = 1 quality factor = 3 quality factor = 1Lena 12.601 : 1 21.860 : 1 12.432 : 1 21.302 : 1Old_city 11.650: 1 20.000: 1 11.564 : 1 19.640: 1Peppers 11.350 : 1 18.438 : 1 11.305 : 1 18.229 : 1Table 2.4. Compression ratios obtained by coding actual and differentialDC coefficients at two different quantization levels (Q=1 and Q=3).Having established the compression capabilities of our method, we will now evaluate itsperformance in the presence of undetected bit errors. Figures 2.13 and 2.14 show the impairedimages obtained under the same noise conditions by the differential DC coding method andby our DC coding method, respectively. In both examples the DigiCipher/CCDC macroblocksynchronization is used. In Figure 2.13, the error above the left eye occurred in the amplitudeof a DC coefficient. Since the DC coefficients that followed are differentially encoded, theerror was passed to the subsequent blocks until the next macroblock is reached. However,in Figure 2.14 the effects of an error occurring in the amplitude of a DC coefficient of37Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENTan 8x8 block located below the left eye were restricted to within that block. We observethat, in general, our method increases the noise resistance of the system by eliminatingthe error propagation caused by differential DC coding. In addition, coding the actual DCvalues instead of their differences reduces the complexity of the coding system. As it willbe shown in Chapters 3 and 5, incorporation of this actual DC coding method with ournew synchronization and coding methods results in a significant improvement in the noiseperformance of the overall system.38Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENTFigure 2.14. Image obtained by our actual DC coding method underthe same noise conditions as the image shown in Figure 2.13.Figure 2.13. Impaired image obtained by the differential DC coding method in the presence of noise.39Chapter 2 HDTV PICTURE QUALITY PERFORMANCE UNDER NOISY CONDITIONS— ANALYSIS AND MEASURES FOR IMPROVEMENT2.5. SUMMARYWe have studied the picture quality of the HDTV picture under noisy transmissionconditions and analyzed the effects of errors in bits belonging to different parts of the codedinformation. The picture quality is mainly affected by the variable length coding (VLC) andthe differential DC terms coding. The VLC causes desynchronization problems. However,even in the absence of desynchronization, errors in the DC terms will severely affect thequality of the picture.We have shown that the variable length coding of symbol-2 and the use of the Huffmancoding on symbol-i present a serious problem when bit errors reach the decoder. An errorin a symbol-i may be magnified and perpetuated throughout the picture. Such an error maycause loss of block synchronization even with the use of special sync-BOB codewords. Thesynchronization problem will be addressed in the next chapter.Besides the synchronization problem, we have also found that the DC coefficients areby far the most error sensitive parts of the coding scheme. The “traditional” differential DCcoding adds to the noise sensitivity of these coefficients. To solve the above problem wedeveloped a new method which codes the actual DC values and we showed that contrary topresent belief, it is possible by using actual DC value coding to obtain compression ratioswhich are almost as high as those obtained by the differential DC coding method. Byencoding actual DC values, the noise resistance of the coding scheme improves significantly.40Chapter 3A NOISE RESISTANT SYNCHRONIZATIONMETHOD FOR HDTV IMAGESAND FULL-MOTION MULTIMEDIA3.1. INTRODUCTIONIn the last chapter it was shown that the effects of an error in any transmitted bit mayperpetuate to the following bits due to two factors: 1) the variable length encoding, VLC,of the data and 2) the DC term differential coding used in the HDTV compression scheme.The second factor was addressed in the previous chapter. In this chapter we address thefirst factor, i.e., the problem of data desynchronization arising from the VLC. Because ofthe VLC, an erroneous bit may result in loss of synchronization of the compressed datawith the original picture blocks, the data is supposed to represent [40, 64, 65]. In addition,since a motion compensation process is used, errors in any frame will also propagate tofollowing frames.To protect the transmitted data from errors, Forward Error Correction (FEC) codes areused [3, 11, 18, 20]. These codes minimize the effects of transmission errors and allowoperation at lower signal-to-noise ratio (SNR) levels. FEC codes do not, however, corrector detect all errors which may arise during transmission. Thus all HDTV proposals providemeasures to synchronize the transmitted data with the picture blocks. Each frame (image) isdivided into sub-images called macroblocks or slices. An error is allowed to perpetuate onlyto within the boundaries of the slice the error belongs to. The parameters of each slice areencoded independently of those of other slices. Thus, for any parameter which is encoded41Chapter 3 A NOISE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIAdifferentially, i.e., as the difference between its actual values in the present block and aprevious block, such as DC coefficient and motion compensation vector, the original truevalues of these parameters are re-initiated at the beginning of every slice. A video buffer offixed bit-length (data-line) is used to form a whole codeword consisting of the video databits and the corresponding FEC bits. Each buffer codeword also contains a pointer whichidentifies the picture slice the present buffer data belong to. The re-initialization of the truevalues of differential parameters and the use of the pointer restrict the effects of bit errorsto within the slice in which the errors occurred. In other words, synchronization at the slice(or macroblock) level is achieved.The DigiCipher and Channel Compatible DigiCipher (CCDC) systems (by GeneralInstruments and by the Massachusetts Institute of Technology in conjunction with GeneralInstruments, respectively), use macroblocks of 5632 pixels each comprised of 16 lines highand 352 pixels wide [11, 18]. The compressed data are transmitted as consecutive data-lines of 106 bytes (for 16—QAM). Each data-line includes a 16—bit macroblock pointerwhich points to the next macroblock in the bit stream [11, 18, 61, 65]. The large size of themacroblock ensures that the number of bits representing it, is always larger than the bit lengthof the data-line and thus each data-line cannot contain more than one complete macroblock.This mechanism guarantees that the maximum image area lost because of an error is onemacroblock. We evaluated the picture performance of this system using computer simulation.In terms of transmission, our model employs 16—QAM and a Reed-Solomon (116,106) FECcode. Figure 3.1 shows the reference image obtained by the DigiCipher and CCDC HDTVmethod at 15 dB SNR in the channel. Figure 3.2 shows the fifth frame from the referenceframe (Figure 3.1), obtained by using inter-frame compression utilizing motion compensation.42Chapter 3 A NOISE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIAFigure 3.1. Reference image obtained using DigiCipher/CCDCmacroblock-pointer method at channel SNR = 15 dB (RMSE = 39.21).Figure 3.2. Fifth frame from the reference frame (Figure 3.1)using DigiCipher/CCDC at 15 dB channel SNR (RMSE = 69.22).43Chapter 3 A NOiSE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIAFigure 3.1 shows that if a bit error occurs, its effects perpetuate to the consecutive blockswithin the macroblock, resulting in block streaking effects in the picture. The horizontal widthof this block may be less or equal to 352 pixels and its vertical length is 16 lines. Figure3.2 contains errors which have perpetuated from the reference frame, Figure 3.1, as well asnewly introduced errors in the inter-frame data.The Advanced Digital Television (ADTV) synchronization scheme (by David Sarnoff andPhilips laboratories) is much more complex than that of the DigiCipher and CCDC [3]. Itincludes prioritization of the Discrete Cosine Transform (DCT) coefficients into two streams,the high and the standard priority data bit streams, and a spectrally shaped QAM channel forthe transmission of the high priority and the standard priority DCT bits. For each of the twodata streams a 960—bit data-line (cell) is used. The image is divided into 64 pixels wide x 16pixels high slices and the system aims at providing synchronization at the slice level. Eachdata-line contains the compressed video and audio data and the FEC bits. It also contains a10—bit pointer which points to where slice 2 starts, i.e., number of bits in slice 1 in this cell,and a 10—bit slice-number that identifies the position of slice 2 in the frame (Figure 3.3).The small size of the slices allows up to 5 compressed slices to fit in one data-line. As aresult, if an error occurs in slice 2, and since the pointer points only to the end of slice 1,slice 2 and the following slices in the data-line will be lost (see Figure 3.3). In the case ofhigh compression, i.e., inter-frames, this could result in a total loss of 4096 pixels.44Chapter 3 A NOISE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIA10 960 bits 10 2 20bits video & audio data bits bits bitsFigure 3.3. ADTV data-line. Note that up to 5 slices can fit in onedata-line. An error in slice 2 will result in the loss of slice 2 ,3, 4 and 5.Finally, the Digital Spectrum Compatible HDTV (DSC-HDTV) proposal (by Zenith andAT&T) uses a complex transmission system that multiplexes between 1 bit per symbol and 2bits per symbol transmission, resulting in more robust transmission for the binary portion (1bit per symbol) of the video data [20, 37]. The image is divided into slices which correspondto 3072 pixel regions, 64 pixels horizontally x 48 pixels vertically. The encoded data streamis divided into fixed length (648 bytes) data-lines. Synchronization for each data—line isprovided by four repeated sync-interval symbols. These repeated sync symbols are the onlyones which recur with the same pattern. Their periodic identical recurrence is used to providesynchronization. These symbols are not provided with any FEC protection. We note thatthe complexity of the transmission scheme of the system is higher than the DigiCipher andCCDC systems, while an error may still affect a large area of the image (3072 pixels).We observe that all four HDTV systems allow a bit error to affect large areas of theimage. As the SNR drops below a threshold value, sudden picture degradation results. Higherorder modulation schemes will further increase the error rate and this increases the rate of thedeterioration of the picture quality. System robustness is essential so that noise interferencewill not produce catastrophic effects, but rather a gradual degradation of the picture.45Chapter 3 A NOISE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIAIn this chapter, we present a novel synchronization method that increases the errorresistance of the HDTV system and offers graceful picture degradation in the presence of biterrors. Our method is similar to the HDTV systems in that it provides synchronization ofthe data at the block levels. Our blocks are however significantly smaller than those usedby the HDTV systems. Since the use of smaller block sizes affects the compression ratenegatively, we use two block sizes. The smaller synchronization block is assigned to thereference frames since the quality of a reference frame affects all consecutive frames. Thelarger synchronization block is assigned to the inter-frames. For each block, synchronizationis achieved by transmitting an extra word (denoted by header-word) which contains thenumber of data in the block. The header-word enables the decoder to recover the exactnumber of bits assigned for each synchronization block. Each header-word is protected byan FEC code added to each data-line. The protected header-words and the rest of the dataare then protected as usual by the FEC code.In the following section (Section 3.2), we present the new synchronization method. InSection 3.3, we show how the efficiency of this method increases by using two differentsynchronization block sizes: a relatively small size for the reference frames and a larger sizefor the inter-frames. In both sections we incorporate the actual DC coding scheme presentedin Chapter 2 with the new synchronization method, and we show how this combinationfurther improves the overall error resistance of the HDTV system. Trade-off combinationsbetween the error protection and the overhead used for synchronization are also studied.In Section 3.4, we study the performance of our method when higher order modulationschemes are used.46Chapter 3 A NOISE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIA32. SYNCHRONIZATION AT 32X16 PIXEL LEVEL FOR ALL FRAMESAs mentioned above, we propose a new method that provides synchronization of data withpicture blocks which are much smaller than the macroblock or the slice. To distinguish thiskind of a block from others we call it a sync block. Our method achieves synchronizationby transmitting a header-word for each sync block. This header-word contains the exactnumber of bits assigned to the sync block. By knowing the exact number of bits belongingto each sync block, the decoder is able to find the beginning of the following sync block,thus limiting the effects of an uncorrected error to within the sync block the error belongsto. It is clear that sync blocks of smaller sizes offer better error protection than larger ones.However, the smaller the sync block size is, the greater the number of the codewords thatshould be added to the data stream. Thus, the size of the sync block affects the total videorate which should not exceed the required bandwidth limit of 6 MHz [3, 4, 9, 11, 18, 20].Therefore, the size of the sync block should be chosen carefully.Let us first consider the case where the size of the sync block is the same for both thereference frames and the inter-frames and is 32x16 pixels, i.e., the same size as the superblock.As it will be shown later, this sync block size significantly improves the error resistance ofthe system, while maintaining the overall transmission rate to within the required bandwidthlimits. For each sync block, a header-codeword indicating the number of bits belonging tothe sync block, is added. For coding efficiency, the R, G and B components are convertedto one luminance (Y) and two chrominance (U and V) components by a color conversionmatrix [9]. The chrominance components are lowpass filtered and subsampled by a factor of4:1 horizontally and by a factor of 2:1 vertically. A 12—bit fixed-size word is large enough47Chapter 3 A NOISE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIAto accommodate the number of bits representing a luminance sync block of this size andthe corresponding chrominance information for the block. To ensure the fidelity of this12—bit word, we protect it by using a (6,4) Reed-Solomon code (12 information-bits, 18 bitstotal). Thus, each of these special header-codewords has a fixed length of 18 bits. Thisprocess provides an extra layer of error protection for the header-codewords, since the wholedata stream (the original data and the header-codewords) is latter protected by the channelerror protection code. The channel noise has two effects on the picture: 1) an erroneousdata bit changes the information of the block it belongs to, and 2) the effects of the errormay perpetuate to the following blocks causing loss of synchronization of the informationbits with the blocks. If the second effect (loss of synchronization) is not present, it hasbeen found experimentally that the SNR at which the picture deteriorates to the level ofbeing unrecognizable is advanced by approximately 3 dB. Thus, the synchronization schemeshould improve the system by 3 dB only, since beyond that level the picture becomes ofunrecognizable quality and there is no point in protecting the synchronization of such atotally degraded picture. To obtain this 3 dB improvement, performance evaluation resultshave shown that a (6,4) Reed-Solomon code (in addition to the channel Reed-Solomon code)ensures the errorless recovery of the header-codewords, i.e., ensures synchronization up tonoise levels at which the original signal does not yield images of unrecognizable quality.The DC coefficients in this case are only differentially encoded within each sync block. Thiseliminates the DC error propagation between consecutive sync blocks and makes each syncblock independent of the others. The use of the 18—bit header-codeword for each sync blockadds 47.5 Kbits to every 1408x960 pixel image for a total of 1.42 Mbps.Figure 3.4 shows the reference frame obtained by the DigiCipher scheme in conjunction48Chapter 3 A NOISE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIAwith our 32x16 synchronization method at 15 dB channel noise, i.e., under the same noiseconditions as that of Figure 3.1.We observe that our synchronization method manages to limit the effects of errors towithin superbiock boundaries. However, in several cases errors have propagated to a largearea of several superblocks, an effect resulting from the differential DC coding used withineach superblock. To avoid this, we incorporate our synchronization scheme with the actualDC coding method presented in Chapter 2. Figure 3.5 shows the reference frame obtainedby the DigiCipher scheme and the combination of the actual DC coding scheme and the32x16 synchronization method at 15 dB channel noise. Thus Figure 3.5 is obtained insteadof Figure 3.1 when our synchronization scheme and our DC coding scheme are used.49Chapter 3 A NOISE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIAFigure 3.4. Image obtained using our 32x1 6 superblock header-codewordsat 15 dB SNR channel noise (RMSE = 12.04).Figure 3.5. Image obtained using our 32x1 6 superblock header-codewords in conjunctionwith our actual DC coding method at 15 dB SNR channel noise (RMSE = 6.30).50Chapter 3 A NOISE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIAFigure 3.6 shows the fifth frame obtained by DigiCipher utilizing inter-frame motioncompensation and our block synchronization method in conjunction with the actual DCcoding method. Comparing Figures 3.5 and 3.6 with Figures 3.1 and 3.2, we find that ourmethod improves the quality of the decompressed picture by restricting the effects of errorsto within much smaller block boundaries. In the following section we present a way toimprove the trade-off between the error protection and the total number of overhead bitsused by this synchronization method.Figure 3.6. Fifth frame from the reference frame (Figure 3.5) obtained using our actual DCcoding scheme and the 32x16 inter-frames sync blocks at 15 dB SNR channel noise (RMSE = 27.28).51Chapter 3 A NOISE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIA3.3. TWO-SYNC BLOCK SIZE METHODSo far we have presented a method that provides synchronization at the 32x 16 pixel level(superbiock) for both the reference frames and the inter-frames, (i.e., the same synchronization block size was used for all the frames). However, it is more efficient to provide betterprotection to those frames whose quality affects the other frames the most. Generally, for every 10 frames a reference frame (intra-frame) is transmitted, the other 9 frames (inter-frames)are encoded using inter-frame motion compensation techniques. Motion compensation exploits the temporal redundancies between consecutive frames. Each frame is divided intoblocks of a predefined size and each such block of the current frame is matched with a blockin the previous frame. The difference between the current block and the best match in theprevious frame is DCT transformed, quantized, encoded and transmitted together with theoffset (motion) vectors between the two blocks [3, 5, 18, 20, 43, 44].The fidelity of the reference frames is crucial since the effects of any error in a referenceframe will perpetuate and will affect all subsequent 9 inter-frames because of the motioncompensation process. Errors occurring in an inter-frame will also propagate to subsequentframes (until the next reference frame is encountered). Thus, while an error in a referenceframe affects all 10 frames, an error in an inter-frame, on average, affects 5 frames. This isthe first reason why reference frames should be offered more protection than the inter-frames.Another reason is that the probability of an error occurring in a reference frame is around4 times greater than an error occurring in an inter-frame. This is because most of the videocompression is due to the motion compensation process. We have experimentally foundthat, on average, around 30% of the total number of compressed bits belong to the reference52Chapter 3 A NOISE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIAframes and around 70% belong to the inter-frames. Thus the probability of an error affectinga reference frame is equal to 0.3ONp where N is the number of bits in a 10 frames sequenceand p is the probability of a bit error. Similarly, the probability of an error affecting aninter-frame is 0.70NpI9 = 0.077Np. Thus, the probability of an error in the reference frameis greater than that in an inter-frame by a factor of 3.89.We conclude that, preserving the quality of the reference frames is more important thanthat of the average inter-frame since an error in the reference frames, on average, affectsdouble the number of frames and since errors in the reference frames are 4 times morelikely to occur than in an inter-frame. This approximately means that we should provide thereference frames with error protection greater than the inter-frame by a factor of 8.Motivated by the above, we propose a method that provides synchronization using twodifferent sync block sizes: a relatively small size for the sync blocks of the reference framesand a larger size for the sync blocks of the inter-frames. This scheme offers higher protectionto the reference frames. Choosing the sizes of the two sync blocks requires a trade-offdecision between the achieved degree of error protection and the number of the extra bits ofthe header-codewords to be added to the data stream.Table 3.1 shows the bit length of the header codewords for different sync block sizes,the number of the corresponding Reed-Solomon protection bits, and the total number ofextra bits required for one frame. Table 3.2 shows the number of extra bits required fordifferent combinations of sync block sizes for the reference and inter-frames. From thistable we observe that as the sizes of the sync blocks increase the number of extra bits neededdecreases.53Chapter 3 A NOISE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIABlock Header Reed- Number of extrasize size Solomon bits/frame8x8 9 5,3 396,0008x1 6 11 6,4 237,60016x16 12 6,4 95,04032x16 12 6,4 47,50064x16 14 7,5 27,720Table 3.1. This table shows different combinations of block sizes, the length of the header-codewords for each size, theReed-Solomon protection code needed, and the total number of extra bits required for one reference frame.Reference frame Inter-frame Number ofextra bits/sec8x8 32x16 2.47 Mbits8x16 32x16 1.99 Mbits8x16 64x16 1.46 Mbits16x16 32x16 1.56 Mbits16x16 64x16 1.03 MbitsTable 3.2. This table shows the number of extra bits required for differentcombinations of sync block sizes for the reference and inter-frames.Let us first consider the case which uses the smallest synchronization block size possible(8x8 pixels) for the reference frames and a larger 32x 16 pixels synchronization block forthe inter-frames. This implementation offers the eight times more protection to the referenceframes than the inter-frames. A 9—bit fixed-size header-word is large enough to accommodatethe number of bits representing an 8x8 luminance or chrominance block. An error protection54Chapter 3 A NOISE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIAfor this header-word is provided by a (5,3) Reed-Solomon code (9 information bits, 15 bitstotal). Thus, after the addition of the parity bits, each of the resultant header-codewords hasa fixed length of 15 bits. The resultant data stream is now composed of blocks of bits, eachblock consists of the 15 (header codeword) bits followed by the bits representing the 8x8pixel block. For each inter-frame, synchronization at the 32x 16 superbiock level is providedby an 18—bit header-codeword, as previously outlined in Section 3.2.Under the same noise conditions as those of Figure 3.1 and Figure 3.2 and using our 8x8header-codeword synchronization scheme for the reference frame, Figure 3.7 is obtained.Figure 3.8 depicts the fifth frame (from the reference) obtained by using the 32x16 headercodeword scheme for all the inter-frames. To further improve the error resistance of thesystem, we incorporate our actual DC coding scheme with this synchronization method. Notethat when 8x8 synchronization blocks are used for the reference frames, the DC coefficientsare never differentially encoded. Figure 3.9 shows the improved fifth frame obtained byusing our actual DC coding method for the inter-frames.55Chapter 3 A NOISE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIAFigure 3.7. Reference image obtained using our synchronization schemefor an 8x8 pixel sync blocks at channel SNR = 15 dB (RMSE = 3.81).Figure 3.8. Fifth frame from the reference frame Figure 3.7 obtained by a32x16 inter-frames sync blocks at 15 dB channel SNR (RMSE = 28.53).56Chapter 3 A NOISE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIAFigure 39. Fifth frame from the reference frame Figure 3.7 obtained by a 32x1 6 inter-frames sync blocksin conjunction with the actual DC coding scheme at 15 dB channel SNR (RMSE = 25.07).57Chapter 3 A NOISE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIA/The root mean-square errors (, / y E original (x,y)—reconstructed (x,y)12) of the reconV 2=0structed images are 3.81 and 25.07 for Figures 3.7 and 3.9 respectively, while for Figures 3.1and 3.2 the RMSE is 39.21 and 69.22 respectively. In the case of the DigiCipher and CCDCsystems (Figure 3.1 and Figure 3.2), each of the errors affects an area of up to 88 (8x8 pixels)blocks (one macroblock). With the addition of our method the effects of errors are limitedto within 1 or 8 (8x8 pixel) block boundaries. We observe that using our synchronizationscheme significantly improves the picture quality. As mentioned earlier, the performance ofHDTV picture is expected to be very good up to a certain SNR. Below that ratio the qualityof the HDTV picture suddenly deteriorates. Performance evaluations have shown that byusing our synchronization method the SNR at which the HDTV picture suddenly deterioratesis deferrer by approximately 3 dB.For the proposed 1408 x 960 pixel HDTV image, and using our method with the presentsync block sizes, an extra 2.47 Mbps is needed for the synchronization control bits. Theseconstitute 26400 (8x8) luminance and chrominance blocks for each reference frame, eachblock having 15 bits header-codeword + 2640 (32x 16) luminance blocks which include thecorresponding chrominance information, each block having 18 bits header-codewords foreach of the 27 inter-frames. If this scheme is simply added to the compression scheme ofthe DigiCipher system, the total data rate becomes 13.09+0.25+ 2.47 = 15.81 Mbps.The combination which provides synchronization at the 16x16 pixel level for the reference frames and 64xl6 pixel level for the inter-frames requires 1.03 Mbps only. Let usnow examine the error protection performance of this scheme. Under the same noise conditions, i.e., 15 dB SNR, Figure 3.10 shows the reference frame obtained by using the 16x1658Chapter 3 A NOISE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIAheader—codewords scheme. Figure 3.11 depicts the fifth frame from the reference (Figure3.10) when 64x16 pixel sync blocks are used for the inter-frames. Figures 3.12 and 3.13show the reference frame and the fifth frame obtained when this synchronization method iscombined with the actual DC coding scheme. Once more we observe that the addition of theactual DC coding scheme eliminates the propagation of errors due to differential DC codingand improves the picture performance of the system. Table 3.3 shows the RMSE valuesfor the first and the fifth frame of the video sequence “old city”, obtained by DigiCipher,our synchronization method, and our synchronization method in conjunction with the actualDC coding method.59Chapter 3 A NOISE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIAMethod I Modulation Frame I RMSEDigiCipher 16 QAM 1st 39.215th 69.2232x16 sync blocks for reference frames 16 QAM 1st 12.0432x16 sync blocks for reference frames + actual DC coding 16 QAM 1st 6.3032x16 sync blocks for reference and inter-frames + actual DC coding 16 QAM 5th 27.288x8 sync blocks for reference frames and 16 QAM 1st 3.8132x16 sync blocks for inter-frames 16 QAM 5th 28.5332x16 sync blocks for inter-frames + actual DC coding 16 QAM 5th 25.071 6x 16 sync blocks for reference frames and 16 QAM 1St 9.1164x16 sync blocks for inter-frames 16 QAM 5th 30.01I 6x 16 sync blocks for reference frames and 16 QAM 1st 8.0264x16 sync blocks for inter-frames + actual DC coding 16 QAM 5th 26.558x8 sync block for reference and 32 QAM 1st 10.0932x16 sync blocks for inter-frames + actual DC coding 32 QAM 5th 29.80I 6x 16 sync block for reference and 32 QAM 1st 20.0064x16 sync blocks for inter-frames + actual DC coding 32 QAM 5th 34.07Table 3.3. RMSE values for the first and the fifth frame of the video sequence “old city”, obtained by DigiCipher, oursynchronization method, and our synchronization method in conjunction with the actual DC coding method.60Chapter 3 A NOISE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIAFigure 3.11. Fifth frame from the reference frame Figure 3.10 obtained by using a 64x1 6synchronization scheme for the inter-frames at 15 dB channel SNR (RMSE = 30.01).Figure 3.10. Reference image obtained using our synchronization schemefor a 16x16 pixel level at channel SNR = 15 dB (RMSE = 9.11).61Chapter 3 A NOISE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIAFigure 3.13. Fifth frame from the reference frame Figure 3.12 obtained by using a 64x1 6 synchronizationscheme for the inter-frames and our actual DC coding scheme at 15 dB channel SNR (RMSE = 26.55).Figure 3.12. Reference image obtained using our synchronization scheme for a I 6x 16pixel level and our actual coding scheme at channel SNR = 15 dB (RMSE = 8.02).62Chapter 3 A NOISE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIAComparing the present synchronization method, which uses 16x16 and 64x16 pixels forthe reference and inter frames respectively, with that presented in Section 3.2 which uses thesame sizes (32x 16 pixel sync blocks) for both the reference and inter frames, we observe thatthe latter method does not offer better picture performance (Table 3.3). More importantly,the present method reduces the overhead synchronization bits added to the data stream byapproximately 28 % (1.03 Mbps compared to 1.42 Mbps). Table 3.4 illustrates the videodata rates for the DigiCipher and the DigiCipher in conjunction with different versions ofour synchronization method, as well as the corresponding total video rates obtained afterthe addition of the synchronization control bits. Clearly, providing better protection to thereference frames than the inter-frames improves the efficiency of the synchronization method.Performance evaluations have shown that by using 16x16 and 64x16 pixel sizes of sync blocksthe SNR at which the HDTV picture suddenly deteriorates is reduced by 2.5 dB.DigiCipher DigiCipher with DigiCipher with the DigiCipher withthe 32x16 8x8132x16 the 16x16164x16Synchronization Synchronization SynchronizationMethod Method MethodVideo Data Rate (Mbps) 13.09 13.09 13.09 13.09Total Data Rate (Mbps) = 13.34 14.76 15.81 14.37(video & synchronization bits) (13.34+1.42) (13.34+2.47) (13.34+1.03)Transmission Rate (Mbps) = 19.51 20.93 21.98 20.54(total data rate & FEC)Transmission Symbol Rate 4.88 5.23 5.50 5.13using 16-QAM (MBaud)Transmission Symbol Rate 3.90 4.19 4.40 4.10using_32-QAM_(MBaud)Table 3.4. Video data rates (Mbps) for the DigiCipher and the DigiCipherin conjunction with different version of our synchronization method.63Chapter 3 A NOISE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIA3.4. USING HIGHER ORDER MODULATION SCHEMESHigher order modulation schemes have the advantage of reducing the transmission rate,i.e., the bandwidth. An increase in the number of modulation levels from 2’ to 2n+1 improvesthe transmission symbol rate by x 100%. For example, the DigiCipher system requires3.90 MBaud at 32—QAM instead of 4.88 MBaud at 16—QAM. However, by going to 32—QAMfrom 16—QAM, the performance of the system will deteriorate by 2.5 to 3 dB. This is becauseas the order of modulation levels is increased, the system becomes more susceptible to channelerrors. To maintain the same performance at the higher modulation level as in the lowerlevel, the signal power must be increased. For an increase in the number of modulationlevels from 2” to 21+1, either the signal power has to be increased by 2.5 to 3 dB [511 or thesame amount of dB deterioration in the system performance is expected.Our synchronization scheme produces a more graceful deterioration and defers the SNRat which the HDTV picture suddenly deteriorates by 2.5 to 3 dB. Thus, our scheme allowsthe operation at a higher modulation level (2’’) while maintaining the picture performanceat the 2 modulation level scheme. The cost is the number of extra bits needed for thesynchronization. This cost, however, is still favorable as will be seen below.Let us examine the picture performance of DigiCipher in conjunction with the actual DCcoding method and our synchronization method, using 32—QAM at 15 dB SNR. Figures 3.14and 3.15 show the reference and fifth frames, obtained using our 8x8 and 32x16 blocks for thereference frames and the inter-frames, respectively. In this case, the resulting transmissionsymbol rate is 4.40 MBaud (21.98 Mbps / 5 bits per symbol). Figures 3.16 and 3.17 showthe reference and fifth frames, respectively, obtained by our 16xl6 and 64x16 blocks. Using64Chapter 3 A NOISE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIAthese sizes of sync blocks we obtain a total symbol rate of 4.10 MBaud (20.54 Mbps I 5). Weobserve that at 15 dB SNR, the picture quality obtained by our (16x16/64x16) synchronizationmethod at 32—QAM is comparable to that of DigiCipher at 16—QAM (also see Table 3.3). Theadvantage of using our method at 32—QAM, however, is that it reduces the transmission rateto 4.40 and 4.10 MBaud, down from 4.88 obtained by DigiCipher at 16—QAM (Table 3.3).Thus, when our synchronization method is used at 32—QAM, it improves the overall systemcompression while it still provides more graceful picture deterioration than DigiCipher at16—QAM. For comparison reasons, Figures 3.18 and 3.19 show the reference and fifth frameobtained by DigiCipher at 32—QAM and 15 dB SNR. As expected, the DigiCipher system isunable to handle the increased number of errors, resulting in a complete loss of the picture.65Chapter 3 A NOISE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIAFigure 3.14. Same as Figure 3.7 but at 32—QAM instead of 16—QAM (RMSE = 10.09).Figure 3.15. Same as Figure 3.9 but at 32—QAM instead of 16—QAM (RMSE = 29.80).66Chapter 3 A NOISE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIAFigure 3.16. Same as Figure 3.12 but at 32—QAM instead of 16—QAM (RMSE = 20.00).Figure 3.17. Same as Figure 3.13 but at 32—QAM instead of 16—QAM (RMSE = 34.07).67Chapter 3 A NOISE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIAIFigure 3.19. Fifth frame from the reference frame (Figure 14) obtained by DigiCipher at 32—QAM and 15 dB SNR.Figure 3.18. Reference image obtained by DigiCipher at 32—QAM and 15 dB SNR.68Chapter 3 A NOISE RESISTANT SYNCHRONIZATION METHOD FORHDTV IMAGES AND FULL-MOTION MULTIMEDIA3.5. SUMMARYIn this chapter, we presented a novel frame-adaptive synchronization method whichincreases the error resistance of a full-motion digital system by restricting the effects of biterrors to block levels significantly smaller than those used by the HDTV systems. A trade-offbetween the error protection and the overhead used is obtained by using a relatively smallsynchronization block size for the reference frames and a large size for the inter-frames.For each such block, synchronization is achieved by transmitting a header-codeword whichcontains the number of data in the block and is protected by two levels of FEC code. Furtherimprovement of the noise performance is obtained by incorporating this synchronizationmethod with the actual DC coding method. The resulting scheme improves the quality of thepicture in the presence of errors and defers the SNR at which the HDTV picture suddenlydeteriorates by 2.5 to 3 dB. Thus, it has a special advantage when higher order modulationschemes are used.69Chapter 4A HIGH QUALITY FIXED-LENGTHCOMPRESSION SCHEME4.1. INTRODUCTIONIn Chapter 2, we identified the coding of the differential DC terms and the use ofvariable length coding to be the two problems associated with the proposed HDTV, DCTbased compression scheme. We then, in Chapter 2 and Chapter 3, proposed solutions forthese problems. In this chapter we propose the use of a different scheme which is alsoDCT based and codes the actual DC values but results in fixed length coding. Fixed lengthcoding refers to encoding each 8x8 pixels block by a fixed number of bits, thus alleviatingthe desynchronization problem.Many recent applications in image compression involve transform-based coding techniques [3—5, 11, 13, 14, 18—20, 30, 43, 44]. As previously discussed in Chapter 2, thediscrete cosine transform (DCT) has become the most popular and is used in the JointPhotographic Experts Group (JPEG) compression method, the Consultive Committee on International Telephony and Telegraphy (CCITT) method and the different versions of theMoving Picture Experts Group (MPEG) compression methods [19, 38, 43]. This is becausethe DCT-based encoders are easy to implement and result in relatively large compressionrates and high quality reconstructed images [6, 19, 29, 49, 68].The above compression methods encode the DCT coefficients of 8 x 8 pixel blocksof the picture [19, 30, 43, 44]. Data compression is then achieved by applying runlength encoding on the coefficients (or a weighted version of them), resulting in symbol70Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEMEcodewords. Each codeword has two parts: symbol-i and symbol-2. The symbol-i partof every codeword is of fixed length and the symbol-2 is of variable length (see Chapter2). Given the probability distribution of the fixed length symbol-codewords (symbol-i’s),further compression is achieved by assigning variable length Huffman codewords to thesesymbols [19, 30]. Thus, the number of compressed data bits for each 8x8 pixel block variesfrom one block to another resulting in variable length coding. The use of variable lengthcoding (VLC) improves the compression ratio.In VLC, different blocks of the picture are encoded by blocks of data of differentlengths. As mentioned earlier, the disadvantage of VLC is that if an error in the data streamrepresenting the compressed picture reaches the decoder, the effects of this error propagatethroughout the rest of the data bits. This necessitates the use of special synchronizationschemes (described in Section 3.1) in conjunction with the error correction codes [56].Another disadvantage of VLC is the need for a rate buffer to control the channel rate.On the other hand, fixed-length compression methods have no synchronization problems[17, 35]. Every block of the picture is encoded by a fixed number of bits and, thus, thecompression rates of fixed length coding are the same for all images. This leads to easyimplementation and a variety of applications [35, 45]. A well known fixed length compressionscheme is Block Truncation Coding (BTC). The drawback of BTC is that the quality of thereconstructed images is inferior to that of the transform-based methods. Although the generalperformance of BTC compressed pictures is acceptable, BTC does not perform equally wellin all the regions of an image and, by its nature, results in images with ragged and noisyedges. Because the human eye is sensitive to the quality of the edges of the picture, the BTCcompressed images are not of high enough quality for many applications. Efforts to preserve71Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEMEthe edges of BTC have been reported [e.g. 37] but unfortunately all these efforts result invariable-length encoders and, thus, the main advantage of BTC, the fixed-length encodingability, is lost. Despite the fact that BTC does not achieve image quality comparable tothat of DCT based compression techniques, it has the distinct advantage of being a fixedlength encoder. Thus, it would be advantageous to devise a method which combines thehigh quality advantage of DCT compression techniques and the fixed length coding of BTCmethods. Such a method would compress the DCT coefficients using BTC methods.Our aim in this chapter is to develop a fixed-length compression method that 1) yieldsreconstructed images of quality significantly higher than that of BTC, and 2) gives acompression ratio which is better than BTC. A compression method with these characteristicsis better able to meet the high-quality requirements of today’s multimedia applications. In thefollowing section, we present a novel fixed-length coding (FLC) method and we show howthis method is used to compress a block or group of DCT coefficients. In Section 4.2, wedescribe a scheme for partitioning the DCT coefficients of color images into regions whichare efficiently compressed by our FLC method. In Section 4.3, we compare our methodwith BTC.72Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEME4.2. A FIXED LENGTH CODING OF FREQUENCY COEFFICIENTSWe introduce a new compression method that compresses the DCT coefficients usingsome principles from the Block Truncation Coding (BTC) [17]. BTC in its original formis applied on the picture itself and not on the DCT coefficients. It compresses a picture bydividing it into 4 x 4 pixel blocks. For each block the sample mean and the variance arecalculated. Both values are then transmitted using a fixed number of bits along with a 1—bitplane. In the 1—bit plane, pixels whose grey levels are greater than or equal to the meanare represented by ones and the other pixels are represented by zeros. At the receiver, theimage is reconstructed with a 2—level quantizer, i.e., the grey level of each pixel takes oneof 2 values. The 2—level quantizer is designed so that the mean and the variance of thereconstructed blocks have the same values as those of the original block.The Absolute Moment Block Truncation Coding (AMBTC) is a form of BTC where thesample first absolute central moment is used instead of the variance [35]. For gray images,Block Truncation Coding [AMBTC or BTC] achieves a compression ratio of 4: 1 when thesample mean and absolute central moment (variance in case of BTC) are represented by 8bits each. If 6 bits are used for the sample mean and 4 bits are used for the absolute centralmoment then the compression is 4.92 : 1.As mentioned earlier, the pixel values of a reconstructed block of AMBTC (and BTC)assume one of two quantization levels only. AMBTC and BTC are basically a form ofadaptive vector quantization method where each block is vector quantized into two levels.The values of these levels depend on the original pixel values of the blocks, specifically theydepend on the average and on the variance of the grey levels within the block.73Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEMEWe desire to derive a method which combines the high quality advantage of DTcompression schemes and the fixed length advantages of BTC methods. Our aim is tocompress the DCT coefficients using BTC methods. However, applying AMBTC (or BTC)in its known form on the DCT coefficients or their weighted versions does not result ina favorable compression ratio; more seriously such direct application results in a totallydegraded or incomprehensible decompressed pictures. This is irrespective of whether theblock truncation scheme is applied on 4 x 4 DCT coefficient blocks or different block sizesof the coefficients. Thus the direct application of AMBTC or BTC on DCT coefficients failsto give good results and should be abandoned.To obtain a fixed-length compression scheme we study the following two problems. Thefirst is how to section a block of 8x8 DCT coefficients into subblocks of coefficients soas to compress each subblock separately. While block truncation coding operates on 4 x 4pixel blocks, our method is not applied on square blocks of DCT coefficients, but rather ondifferent groups of coefficients. The coefficients in a subblock also need not be adjacent orform a square block as in the original version of BTC (or AMBTC). The second problem ishow to compress each subblock of DCT coefficients using block truncation coding. Since thefirst problem depends on the second one, we shall, in the remaining of this section, addressthe latter. The first problem is addressed in the following section.In applying block truncation coding on a block (or a subblock) of DCT coefficients, weshould first address the problem of how to group the DCT coefficients in this block, so as toget good quality decompressed pictures. To every group in the block we shall apply blocktruncation coding, i.e., represent the group by 2—level quantizers calculated from the meanand second central moment of the group.74Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEMEOne important difference between the values of the DCT coefficients and the grey levelsof a block of a picture is that the values of the DCT coefficients assume positive, negativeand zero values, whereas the picture’s grey levels assume non-negative values only. Pleaserefer to Table B.1 in Appendix B which shows the weighted DC!’ coefficients of a typical8x8 pixel block of a picture. Note that the DCT coefficients may be of positive, negative orzero values and that the high frequency components have values equal to zero.If the decoder changes the sign of a DCT coefficient from positive to negative or viceversa, then this affects the quality of the decompressed picture unfavorably. The reason isthat the sign of the DCT coefficients (being analogous to the phase of the Fourier transfonn)can be shown to carry information about edges and ridges in the picture. It also can beshown that the sign carries information about the direction of change of intensities, i.e., ifthe picture intensity was increasing in a certain direction, by changing the sign of the DCTcoefficient the intensity will appear decreasing. Thus, it is important for the compressionscheme to preserve the signs of the DCT coefficients.Using block truncation encoding, it is then desired to encode the positive and the negativecoefficients separately. It is also desired to encode the zero coefficients separately and notinclude them with the positive or negative groups. This is because the number of zerocoefficients for an 8 x 8 DCT block is large and usually constitutes up to 50% or more of thetotal number of coefficients. Thus, including the zero coefficients with any of the positive ornegative groups biases the values of the resulting AMBTC or BTC quantization levels of thisgroup towards zero. This, in turn, will affect the quality of the reconstruction unfavorably.Thus, the DCT coefficients should be grouped into three groups, the positive, the negativeand the zero groups and each group should be encoded separately. Separate encoding of75Chapter 4 A HiGH QUALITY FIXED-LENGTH COMPRESSION SCHEMEeach group will then result in two quantization levels for the positive coefficients, two forthe negative coefficients and only one quantization level for the zero coefficients. That is,the reconstructed block will have 5 different quantization levels.The AMBTC (or BTC) method, being a 2—level quantizer, requires a 1—bit plane toidentify each pixel in the block, that is, only one bit is necessary to represent the pixelswhose values are less than the mean or greater than or equal to the mean. In our case, foreach block of coefficients we must send information identifyinga) the two quantization levels for the positive coefficients and the locations of the positivecoefficients,b) the two quantization levels for the negative coefficients and the locations of thesecoefficients, andc) the location of the coefficients whose values are zeros.For the latter (part c) we do not need to send the actual values since these are already knownto be equal to zeros. That means for our 5—level quantizer we need a 3—bit plane, i.e., 3bits will be required to uniquely identify the five different cases each coefficient in the blockbelongs to. This results in a total of 3m bits to identify the m different coefficients.Therefore, if we were to use this straight forward quantization method, we must transmit1) two quantization levels for the positive coefficients, 2) two quantization levels for thenegative coefficients and 3) a 3—bit plane to identify which of the 5 quantization levels apixel belongs to. As a result, no reasonable compression is obtained. The problem nowis that of reducing the amount of information to be transmitted without introducing anynoticeable distortion. We shall, in the remainder of this section, reduce our 5—level quantizer76Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEMEto a 4—level one and, consequently, the 3—bit plane to a 2—bit plane. Before addressing thedetails of this process, let us first find the 2—level quantizer for each of the positive and thenegative groups of coefficients. We shall use the AMBTC method because it provides bettercomputing speed and reconstructed image quality than the BTC [35].Consider a sequence of m DCT coefficients that consists of p positive coefficients, nnegative and m — (p+n) zero coefficients.Let x be a positive coefficient. Then the sample mean is given by=x , x >0 (4.1)p p=1 pand the sample first absolute central moment by= x— x > 0 (4.2)p p=1 p pIn the original AMBTC method, both of these values are transmitted along with a 1—bitplane which contains ones for the coefficients where x,and zeros otherwise.At the receiver, the two-level quantizer yields the two valuesb = +-- forxp q p (4.3)a =F — forx <p p p—q pi Ppa—where-y=—-- and q is the number of pixels greater than or equal to xIt is apparent that one could transmit either and , or b and a along with the1—bit plane. However, usually and are transmitted since in a different version ofAMBTC these are quantized in 6 bits and 4 bits respectively. Thus 10 bits are transmittedfor and instead of 8 bits for each.77Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEMENow let us find the quantization levels when the grey levels are all negative. Let z be anegative coefficient. Then it can be shown (Appendix C) that the two negative quantizationlevels are given byb = — -- for x F (4.4)n n q n na = + forx >3 (4.5)n n n—q nAs mentioned earlier, to reduce the amount of information to be transmitted (or stored)we shall reduce our 5—level quantizer to a 4—level one and consequently the 3—bit plane isreduced to a 2—bit plane. To do so, we categorize one of the positive or negative groupsas more “important” or “dominant” in some sense. Then we shall compress the dominantgroup as in AMBTC, i.e., using a 2—level quantizer. The non-dominant group shall also berepresented by a 2—level quantizer, however the value of one of the levels, the level withthe smaller absolute magnitude, shall be replaced by zero. Thus the 5—level quantization isreduced a 4-level one.To categorize one of the positive or negative groups of coefficients as dominant, weshall base our classification on the extent of the spread in the values of the coefficients ofthe same group and the number of coefficients in each group. A reasonable measure of theextent of the spread is the sample first absolute central moment,,or . If the valueof this absolute central moment for the positive coefficients, , is greater than that of thenegative coefficients, , then we declare that the positive group is dominant and vice versa.In the case that the central moments of both groups are equal (which is not a rare case), then78Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEMEthe total number of positive and total number of negative coefficients are used to determinewhich of the two groups is the dominant one.As mentioned earlier, our version of AMBTC is not applied on square blocks but ratheron different shapes of blocks of DCT coefficients. To obtain good results, the number ofDCT coefficients in a block should not be too large. We found that if we keep the numberof coefficients in each block to around 10 or less, then we need only encode the coefficientsin the dominant group by the usual 2-level AMBTC quantizer (that is, the dominant groupis encoded by a and b if the positive group is dominant and by a and b otherwise). Thenon-dominant group in this case may be encoded by the 2—level quantizer where the valueof the level with the smaller magnitude is made equal to zero. Thus, if the non-dominantgroup is the positive group then it is encoded by zero and b and if the non-dominant groupis the negative one then it is encoded by zero and b.So far we have reduced our compression scheme from a 5—level quantizer to a 4—levelone. These four levels are a) two (AMBTC) quantization levels for the coefficients ofthe dominant group, b) one level for coefficients of the non-dominant group which is theAMBTC level with the larger absolute magnitude (b or br), and c) zero. The first advantageof this scheme is that it allows us to transmit only the two levels of the dominant group (orpreferably its mean and first absolute central moment) and one level for the non-dominantgroup (instead of two). The zero level need not be transmitted as its value is known to bealways equal to zero.The second advantage is that each coefficient now belongs to one of four values. Thus,the number of different cases (by which each coefficient is identified) is reduced from 5 to4 and, therefore, we now need to transmit 2 bits for each coefficient instead of 3, that is,79Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEMEa 2—bit plane instead of 3—bit plane.Table 4.1 shows the four quantization levels used to reconstruct the coefficients and the2—bit plane code that identifies which of the levels (ar, b, a, b, zero) the correspondingpixel will assume.Values of DCT coefficients Code of the Quantization levels2-bit planex2=O 00 zeroxpp 10x<F 11 bIf the negative group is dominant then01 a00 zeroIf the positive group is dominant thenx<?E 01 ax, >Ti 00 zeroTable 4.1. The four quantization levels used to reconstruct theDCT coefficients and the 2—bit code that identifies the pixel level.80Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEMEThe flow chart of Figure 4.1 depicts an overview of the algorithm.()Separate coefficients into positive,negative and zero groups.Mark each zero coefficient with 00Calculate the mean I Calculate the meanand absolute central and the absolute centralmoment moment .Compute the large Compute the absolute largerquantization level b. quantization level b.Mark each location with Mark each location withx1>=with 1 0 X< 1n with 11IsNo YesStoreStore 5Store the bit map thatidentifies each pixel locationFigure 4.1. Overview of the fixed length four quantization levels compression technique of DCI’ coefficients.Store a 1 (one bit) to indicatethat the negative group isthe dominant.Identify each negative locationwith xn>10with 01StoreMake p=bpStore a 0 (one bit) to indicatethat the positive group isthe dominant.Identify each positive locationwhere xp. < I p with 01StoreMake liEn81Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEME4.3. APPLICATION OF OUR DCT FIXED LENGTHCODING METHOD ON COLOR IMAGESIn the previous section, we described an AMBTC based scheme for compressing a blockor a group of DCT coefficients. In this section, we describe a scheme for partitioning theDCT coefficients of an 8 x 8 pixel region into different blocks which can be efficiently codedby our FLC method. Each of these blocks will be compressed separately. Before we describethe partitioning scheme we shall quickly summarize our general scheme.Figure 4.2 depicts the block diagrams of the encoder and the decoder for our fixed-lengthcoding method. The RGB signals are first converted to the Y (luminance) signal and the Uand V (chrominance) signals. Except for the contents of the last block in the encoder (Figure4.2a) and the first block in the decoder (Figure 4.2b), the other blocks and the general layoutare the same as the conventional ones (Figure 2.2), i.e., as in SMPTE [9], JPEG [19, 34],or the reference frames in MPEG [3, 43, 44].82Chapter 4 A HiGH QUALITY FIXED-LENGTH COMPRESSION SCHEMEFigure 4.2. Digital Video Encoder (a) and Decoder (b) Block DiagramsRecall from Section 2.2A (Figure 2.2) that a 32x16 block of the image is representedby a 40x 16 information superbiock. The DCT is applied on each 8 x 8 pixel block of theinformation superblock of the color picture. In order to exploit the fact that some DCTcoefficients are visually more important than others, we divide each of the DCT coefficientsRFixed-lengthencoding ofOCT coefficientsOecoding of DCTcoefficients usingour FLC methodDECODERRGB83Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEMEby a different weight (as in JPEG and MPEG), i.e., a set of non-uniform weights are usedto quantize the coefficients. Table 2.1 in Chapter 2 shows the luminance and chrominanceweight sets used in all of our experiments. Higher compression rates are obtained by dividingthe quantization weights in Table 2.1 prior to their application on the DCT coefficients bya factor greater than 1. This factor is called the quality factor (Q). If the quality factor issmaller than or equal to 3, the values of many DCT coefficients are driven to zero.Following the application of the quantization weights and the quality factor, we recall thatthe coefficients are usually reordered into a one-dimensional array by reading out the entriesof the two dimensional array along a zigzag sequence as shown in Figure 4.3 (Figure 4.3 is thesame as Figure 2.3 re-drawn here for the convenience of the reader). This way the quantizedcoefficients are “approximately” arranged in order of ascending frequency. This order also“approximately” represents the significance of the values of the different DCT coefficients.Significance here means that if an error occurred in the value of a coefficient, the effectson the block after decompression, are serious. The DC coefficient (upper left corner inFigure 4.3) is the most significant or important coefficient and the AC63 (bottom right) is theleast significant one. This order also “approximately” corresponds to the magnitudes of theDCT coefficients: as the radial distance of a DCT coefficient from the DC term increases, theamplitude of the coefficient is expected to decrease (to see the values of the DCT coefficientsof a typical 8x8 picture block, refer to Table B. I in Appendix B).To apply our version of AMBTC on colored pictures let us first consider the luminancesignal Y. In order to efficiently implement our fixed length compression method, we shallpartition the total number of coefficients into different blocks or regions and we shall encodeeach region separately. We divide the DCT coefficients of the luminance component into 584Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEMEregions as shown in Figure 4.4. Notice that regions 2 and 3 are discontinuous.AC01 AC05 AC06.4 AC63Figure 4.3. Zigzag sequence of quantized DCT coefficients.Figure 4.4. Partitioned original luminance 8x8 block of DCT coefficients into 5 regions.Region 1 is composed of the DC coefficient plus the two AC coefficients with thesmallest frequencies. Because of their relatively large significance, we do not compress the85DC -*‘ACACChapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEMEcoefficients of this region, i.e., the exact value of each of these coefficients is transmitted. Theadditional advantage of coding the DC coefficient separately is that it allows error protectionfor this coefficient. This is desirable since as seen in Chapter 2, the fidelity of preservingthe DC coefficient is of the most importance and a wrong DC value may drastically affectthe reconstruction of the whole 8x8 block [46]. In partitioning the rest of the block, thegeneral criterion followed is that the coefficients nearest to region I are relatively larger andthus are more important and should be compressed with relatively less expected errors thanthe ones further.Regions 2, 3 and 4 are each encoded using our fixed compression method described inthe section above. The number of coefficients in each region is either 9 or 10; that is theregions are almost equal in size.To decide upon the coefficients to be included in each group, we use the knowledge thatthe coefficients adjacent or nearest to region 1 are expected to have larger absolute valuesthan the ones further. To decide upon the boundaries of each group, let us first study thefollowing problem:Assume that AMBTC is to be applied on a group of p positive coefficientsx 1’ x ..., x The question is: what should the relative values of the coefficientsx x , ..., x be, so that after compression and decompression by AMBTC, the coefficients with large values are preserved better than the others?From Appendix B we find that to preserve the positive coefficients whose values are/ p\\greater than the mean ( = x j, these coefficients should all be equal. Furthermore,\ i=1 /A) If one coefficient only is greater than , then AMBTC preserves this coefficient exactly.86Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEMEB) If two coefficients only are greater than the mean then the closer the values of thesecoefficients are to each other, the smaller is the error in their reproduction. If these twocoefficients are equal in value, then they are reproduced exactly.C) The same as in 2) applies for k coefficients. That is, if k coefficients only are greaterthan then the closer these coefficients are in value to each other, the smaller arethe errors in their reproduction. Also if the k coefficients are equal in value then thereproduction error of each is zero.It can be shown that similar results to the above apply for n negative coefficientsx 1’ x 2’ •• x , except that the coefficients to be reproduced with less error are requiredto be smaller than the averageSince it is desired to preserve or reproduce the coefficients nearest to region I with leasterrors, we shall choose region 2 so that its coefficients are expected to follow 1) or 2) above.Thus, we choose region 2 to be composed of two coefficients AC03 and AC04 which areadjacent to region 1 (i.e., are relatively larger in magnitude) and the other seven coefficientsare far from region I (i.e., are expected to be relatively smaller in magnitude). Therefore,AC03 and AC04 are expected to be better preserved by AMBTC because of the following.If AC03 and AC have opposite signs then one will belong to the dominant group andthe other to the non-dominant group. In this case, it is straight forward to show that eachterm will be exactly reproduced if the absolute value of that term is large enough with respectto the other coefficients with the same sign in region 2. The term “large enough” meansthat this coefficient is the only term which is larger than the average of all the coefficients(including this coefficient) with the same sign in that region. This is usually the case, since87Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEMEthe other coefficients being much further from the DC term are expected to be much smallerin magnitude. If both terms AC03 and AC04 happened to have the same sign, then it ismost likely that they belong to the dominant group and the error in the reproduction of each.(Ac_Ac)2coefficient is 03 04 (Appendix B).The same reasoning behind choosing the composition of region 2 applies to designingthe different boundaries of region 3. Region 4 is then formed of the coefficients lying inbetween the high and low frequencies of regions 2 and 3.Finally, region 5 contains the highest frequencies of the block. The boundaries of thisregion are chosen so that when the quality factor is equal to 3 or less, all of the resultingweighted coefficients of this region are expected to have zero values. If the value of thequality factor is greater than 3, some of the coefficients of region 5 may not be zeros.In this case, we shall preserve the two coefficients with the largest absolute values in thedominant group. All the other coefficients are encoded so as to have zero values. That is thedominant group is first found and only its two largest coefficients along with their positionsare transmitted. Thus fixed length vector quantization is again used.Let us now consider the chrominance components. Because of the idiosyncracy of thesesignals, most of the non-zero DCT coefficients are concentrated in the low frequencies. Forthis reason, the partitioning of the chrominance DCT block differs from that of the luminanceone and involves only 3 regions as shown in Figure 4.5.88Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEMEThe first two coefficients are exactly preserved while the coefficients of region 2 arecompressed by our fixed-length coding method as described in the previous section. Region3 is similar to region 5 of the luminance coefficients, except that we here always transmitthe two coefficients with the largest absolute values in the dominant group, regardless of thevalue of the quality factor.The numbers of bits used to represent the coefficients, the means and the absolute centralmoments of the regions of the luminance and chrominance blocks depend on the quality factorwhich scales the weighted coefficients. The lower the value of the quality factor the smallerthe values of the resulting coefficients and, thus, the smaller the number of bits required torepresent them. The numbers of bits used to represent the different coefficients, locations,etc. which we used when the quality factor is equal to 3 are shown in Appendix D.Figure 4.5. Partitioned original chrominance 8x8 block of DCT coefficients into 3 regions.89Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEME4.4. COMPARING OUR FLC METHOD WITH ABSOLUTEMOMENT BLOCK TRUNCATION CODINGWe now compare our FLC method with the other fixed-length compression method, theAbsolute Moment Block Truncation Coding (AMBTC) [35]. Figures 4.6 and 4.7 show thedecompressed image of Lena obtained by our method and AMBTC, respectively.Figure 4.6. Image obtained by using our FLC method (RMSE = 4.76).90Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEMEFigure 4.7. Image obtained by using AMBTC (RMSE = 6.88).The compression ratios for the image obtained by our FLC method is 11.11: 1 while thatobtained by AMBTC is 9.14 : 1. The Root Mean Square Error (RMSE) for the luminancecomponent (Y) of the image obtained by FLC is 4.76 while that of AMBTC is 6.88. Becausethe RMSE is not an especially accurate measure of visual quality, and since the improvementin the picture quality is not as obvious from Figures 4.6 and 4.7 as from the large screen,we include the difference images (Figures 4.9 and 4.10). These show the loss of informationand the degradation of the edges of the picture incurred. Actually, the quality of the picturesobtained by our fixed-length coding scheme is extremely close to that of the variable-lengthJPEG encoding scheme. Figures 4.8 and 4.11, respectively, show the image of Lena obtainedby JPEG and the difference image. The compression ratio for this image is 12.60 : 1 andthe RMSE is 4.01. Better compression rates can be obtained by JPEG but at some loss ofimage quality.91Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEMEFigure 4.8. Image obtained by JPEG (RMSE = 4.01).92Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEMEFigure 4.10. Difference image of Figure 4.7 (AMBTC),Figure 4.9. Difference image of Figure 4.6 (PLC).93Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEMEFigures 4.12 and 4.13 show the decompressed images of an old city obtained by ourFLC method and AMBTC, respectively. The RMSE for the image obtained by our methodis 5.92, significantly smaller than the 7.35 for the image obtained by AMBTC (Table 4.2).The difference pictures are shown in Figures 4.14 and 4.15.Figure 4.11. Difference image of Figure 4.8 (JPEG).94Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEMEFigure 4I2. Image obtained by using our FLC method (RMSE = 5.92)Figure 4.13. Image obtained by using AMBTC (RMSE = 7.35).95Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEMEFigure 4.15. Difference image of Figure 4.13 (AMBTC).Figure 4.14. Difference image of Figure 4.12 (FLC).96Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEMEImage Method Compression Ratio RMSELena FLC 11.11 : 1 4.76Lena AMBTC 9.14: 1 6.88Old city FLC 11.11 : 1 5.92Old city AMBTC 9.14 : 1 7.35Table 4.2. RMSE and compression rates for FLC and AMBTC.We observe that the edges of the images obtained by AMBTC are noisy and have aragged appearance. On the other hand, the images obtained by our method are almostperfectly preserved. The compression ratio obtained by our method for the above images(Figures 4.6 and 4.12) is 11.11: 1 (quality factor = 3) and becomes larger as the qualityfactor becomes smaller, while the AMBTC compression ratio for Figures 4.7 and 4.13 is 9.141. If the mean and the first absolute central moment of the AMBTC blocks are representedby 6 bits and 4 bits respectively [35] then the compression rate of AMBTC is driven to 111 but at further loss in the quality of the decompressed picture.Thus, our method retains the fixed length encoding advantage of AMBTC but givesconsiderably better quality pictures than AMBTC. In the next section and in Chapter 5, weshow how these two important features make this coding method an excellent candidate forHDTV applications.97Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEME4.5. USE OF HIGHER ORDER MODULATION SCHEMESSo far we have discussed the picture performance of our fixed length coding method. Inthis section we study the noise-resistance performance of this method. Figure 4.16 shows thereconstructed image obtained by the DigiCipher HDTV system using 16 QAM (quadraticamplitude modulation) at 15 dB signal-to-noise ratio (SNR) channel noise. This imagerequires 70217 symbols to be transmitted. Under the same noise conditions, Figure 4.17shows the image obtained by our fixed length coding method. This image requires 79643symbols to be transmitted. We observe that our fixed length compression method has nosynchronization problems and is extremely noise-resistant. For some pictures, however, thetransmission rates obtained by our method are not as favorable. To compensate for that,higher order modulation levels in the transmission may be used. As previously discussed inChapter 3, higher order modulation levels increase the transmission rate but unfortunatelyincrease the number of occurrences of bit errors in the transmission channel. Our methodallows the operation at higher modulation levels without altering the picture performance.Due to its error robustness, our scheme will protect the picture at higher modulation levelswhereas the other variable length coding methods do not.Using 64 QAM at 15 dB SNR channel noise, the reconstructed images obtained bythe DigiCipher and our method are shown in Figures 4.18 and 4.19, respectively. Theseimages require 46811 and 53089 symbols to be transmitted, respectively. Using our methodat 64 QAM reduces the transmission rate of that obtained using 16 QAM by 33.3 %. Weobserve that at 15 dB SNR, the DigiCipher system results in a complete loss of the picture,while the picture performance of our method and the compression rates are better than that98Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEMEof DigiCipher at 16 QAM. Our method is ideal for compressing reference-frames (stillimages) and video sequences with significant motion, e.g., sports events. In the latter case,the differences between any two consecutive frames are large. The motion compensationcompression process thus becomes inefficient since the compression rates of the inter-framesapproach or even surpass those of the reference frames. Therefore, our method may beused for compressing such video sequences, resulting in transmission rates comparable tothose of the proposed methods while providing excellent noise-resistance performance. Thismethod can be easily incorporated by the proposed HDTV systems, with the latter slightlymodified to include the following options: 1) to code the DCT coefficients using our fixedlength coding method, 2) to code every frame as a reference frame, i.e., motion compensationschemes are not utilized, and 3) to use a higher order modulation scheme than that used bythe original system. Our method can also be implemented as an independent scheme which issignificantly simpler than the proposed HDTV schemes due to the elimination of the motioncompensation process and the data synchronization techniques.99Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEMEFigure 4.16. Image obtained by DigiCipher using 16 QAM at 15dB SNR (this image requires 70217 symbols to be transmitted).Figure 4.17. Image obtained by our fixed length coding method using 16QAM at 15 dB SNR (this image requires 79643 symbols to be transmitted).100Chapter 4 A HiGH QUALITY FIXED-LENGTH COMPRESSION SCHEMEFigure 4.19. Image obtained by our fixed length coding method using64 QAM at 15 dB SNR (this image requires 53089 to be transmitted).Figure 4.18. Image obtained by DigiCipher using 64 QAM at 15dB SNR (this image requires 46811 symbols to be transmitted).101Chapter 4 A HIGH QUALITY FIXED-LENGTH COMPRESSION SCHEME46 SUMMARYIn this chapter we described a fixed-length color-image compression method. Our methodcombines the distinct advantage of being fixed-length and at the same time retains the highimage quality of DCT-based coding methods. Fixed-length encoding schemes are simpler toimplement than variable-length ones and are not susceptible to the error propagation probleminherent in the variable-length coding methods.We showed how to segment the DCT coefficients of an 8x8 block into regions and howto encode the coefficients of each region so that high quality pictures and high compressionrates are obtained. We then compared our method with AMBTC, a fixed-length codingmethod. Our method gave better quality pictures and a better compression ratio. Because ofthe noise-resistance performance of this method and its robustness to errors, it is suitable foruse with higher order modulation schemes. We conclude that this method may be used forthe compression of video programs which have considerable motion.102Chapter 5A NOISE RESISTANT SCHEME FOR HDTV SYSTEMSAND FULL-MOTION MULTIMEDIA WHICH USES AFIXED AND A VARIABLE LENGTH CODING METHOD5.1. INTRODUCTIONThe huge bandwidth demand of full-motion multimedia services prevails as the mostcritical aspect of the system. Solutions based on greater compression and higher ordermodulation techniques simply lead to an inescapable increase in the error sensitivity of thesystem [1, 2, 15, 28, 31, 47, 521.In Chapter 3 it was shown that the four HDTV proposals offer some error protection byrestricting the effects of bit errors to within individual macroblocks [3, 11, 18, 20]. Theseblocks, however, comprise large areas of the image and, as the SNR drops below a thresholdvalue, sudden degradation of the picture remains a problem. A solution was offered byour synchronization method which improves the noise performance of the HDTV system byusing a header-codeword for each block. This limits the bit error effects to blocks muchsmaller in size than those allowed by the other HDTV proposals. However, the disadvantageof that method is the addition of extra synchronization bits (header-codewords) to the datastream, resulting in a slight increase in the total transmission rate.Our aim in this chapter is to restrict the propagation of errors to within small regionsof the frame without altering the overall transmitted bit rate. It is well known that fixedlength compression schemes do not have synchronization problems and, by their nature, areextremely noise resistant. Thus, the first advantage of fixed-length compression methods103ChapterS A NOISE RESiSTANT SCHEME FOR HDTV SYSTEMS AND FULL-MOTIONMULTIMEDIA WHICH USES A FIXED AND A VARIABLE LENGTH CODING METHODover the variable length coding (VLC) methods lies in their superior performance in thepresence of noise, by limiting the effects of a bit error to the bit itself. In fixed-lengthcoding the effects of an error in any bit do not propagate to other bits and, thus, under noisyconditions the quality of the picture is considerably improved. The second advantage is thesimplicity of implementation since fixed-length coding methods eliminate the synchronizationproblems inherent in VLC techniques. Fixed-length coding (FLC) does not require the useof macroblock-pointers, since the synchronization problems inherent in VLC methods areeliminated. In Chapter 4, we presented a new compression method which has the advantageof being fixed length and also retains the high picture quality obtained by DCT-based codingmethods. The latter is a necessary feature of today’s demanding multimedia applications.However, in many circumstances (particularly in the case of compressing the inter-frames)the fixed compression ratio obtained by the FLC method is not as favorable as that of MPEG.For these cases, higher order modulation schemes may be used to improve the transmissionrate. Because of the error robustness characteristics of this method, the picture performanceof the system is not affected by the higher levels of modulation. This makes FLC ideal forcompressing video sequences with fast motion.To improve the compression ratio of our FLC method we combine it with the VLCmethod proposed for HDTV. We present a novel coding method which encodes the DCTcoefficients of each 8x8 block by either our FLC method or by the VLC method. Thiscombines the error resistivity advantage inherent in FLC methods and the high compressionrates achieved by the VLC methods. In Section 5.2, we describe our hybrid FLCNLCmethod and we study the error and compression performance of this hybrid method. InSection 5.3 we combine our FLC method with our proposed VLC method, i.e., using the104ChapterS A NOISE RESISTANT SCHEME FOR HDTV SYSTEMS AND FULL-MOTIONMULTIMEDIA WHICH USES A FIXED AND A VARIABLE LENGTH CODING METHODactual DC coding of Chapter 2 and the synchronization method presented in Chapter 3. Weshow that the combination of these methods yields a robust method which 1) has excellentnoise performance characteristics, 2) yields image quality comparable to the MPEG basedVLC method and better than the FLC method, and 3) improves the compression ratio overthat of the MPEG based VLC scheme.105ChapterS A NOISE RESISTANT SCHEME FOR HDTV SYSTEMS AND FULL-MOTIONMULTIMEDIA WHICH USES A FIXED AND A VARIABLE LENGTH CODING METHOD5.2. A HYBRID FLCNLC METHODOur proposed method codes each 8x8 block of DCT coefficients by either our FLCmethod or the MPEG based VLC method (discussed in Chapter 2), depending on whichyields the better compression rate. This hybrid approach allows us to combine the excellentnoise-resistance performance of the FLC methods with the compression efficiency of the VLCmethods. We use the FLC method described in Chapter 4. This method uses a fixed qualityfactor (equal to 3) which yields decompressed images of high quality. Thus, regardless ofthe quality factor used by the system, blocks encoded by FLC are always of good visualquality. The blocks encoded by the FLC method will be very resistive to bit errors whilethe error effects will be limited to within the block in which the error occurs. Thus, thelarger the number of 8x8 FLC-coded blocks in a frame, the better the error protection. Thepresence of variable length coded codewords in the FLC/VLC hybrid scheme may causedesynchronization problems. The overall synchronization of the data bit stream is controlledby the DigiCipher’s macroblock synchronization scheme (Chapter 3).Recall that, in the case of HDTV, for every 10 frames a reference frame (intra-frame)is transmitted. The other 9 frames (inter-frames) are encoded using inter-frame motioncompensation techniques [3, 11, 18, 20]. Let us study the compression and error performanceof our hybrid method. We first apply it to the reference frames. In the case of the referenceframes, the number of blocks of DCT coefficients which are coded by our FLC method isimage dependant. We expect the smooth regions to be encoded by the VLC method sinceit gives better compression in these regions. This is because smooth blocks will have themajority of their DCT coefficients equal to zero, and thus can be coded more efficiently106ChapterS A NOISE RESISTANT SCHEME FOR HDTV SYSTEMS AND FULL-MOTIONMULTIMEDIA WHICH USES A FIXED AND A VARIABLE LENGTH CODING METHODby the VLC method. Regions with texture, however, are expected to be encoded by theFLC method, since these regions yield many non-zero DCT coefficients which reduce thecompression efficiency of the VLC method below that of our FLC method. The same alsoapplies to regions with edges. In order to assess the compression and error performance ofour method, three test images with different kinds of contents are used. “Lena” (Figures 5.1and 5.2) represents an image with texture, edges and smooth areas, “Mandril” (Figures 5.3and 5.4) represents an image with high degree of texture, while “Hockey Player” (Figures5.5 and 5.6) mostly consists of smooth areas and low contrast edges. Table 5.1 shows thenumber of blocks encoded by FLC in each image, the percentage of bits encoded by FLC andthe compression ratios. For these images our simulation employs a 16—QAM transmissionscheme and a (116,106) Reed-Solomon FEC code. The SNR of the channel noise is 15 dB.Figures 5.1, 5.3 and 5.5 show the reconstructed images of “Lena”, “Mandril” and“Hockey Player” obtained by the original DigiCipher coding method. Figures 5.2, 5.4 and 5.7depict the same images obtained by our modified DigiCipher coding scheme which includesthe FLC method.107Chapter 5 A NOISE RESISTANT SCHEME FOR HDTV SYSTEMS AND FULL-MOTIONMULTIMEDIA WHICH USES A FIXED AND A VARIABLE LENGTH CODING METHODImage/Method # of blocks encoded by % of bits CompressionFLC encoded by FLC ratiosLenaJVLC only 12.60: 1LenaJVLC & FLC 722 Luminance 47 % 14.69: 1485 ChrominanceMandrilJVLC only 6.40: 1Mandril/VLC & FLC 1982 Luminance 85 % 11.30: 1533 ChrominanceHockey/VLC only 16.62: 1Hockey/VLC & FLC 301 Luminance 18 % 18.20: 121 1 ChrominanceTable 5.1. Number of blocks encoded by FLC for each image, the percentage of bits encoded by FLC and compression ratios.108ChapterS A NOISE RESISTANT SCHEME FOR HDTV SYSTEMS AND FULL-MOTIONMULTIMEDIA WHICH USES A FIXED AND A VARIABLE LENGTH CODING METHODFigure 5.1. Image obtained by the DigiCipher coding method at 15 dB SNR. Compression ratio = 12.60 1.Figure 5.2. Image obtained by the DigiCipher system using VLC andour FLC methods at 15 dB SNR. Compression ratio = 14.69 : 1.109ChapterS A NOISE RESISTANT SCHEME FOR HDTV SYSTEMS AND FULL-MOTIONMULTIMEDIA WHICH USES A F1XED AND A VARIABLE LENGTH CODING METHODFigure 5.3. Image obtained by the DigiCipher coding method at 15 dB SNR. Compression ratio = 6.40 : 1.Figure 5.4. Image obtained by the DigiCipher system using VLC andour FLC methods at 15 dB SNR. Compression ratio = 11.30 1.110Chapter 5 A NOISE RESISTANT SCHEME FOR HDTV SYSTEMS AND FULL-MOTIONMULTIMEDIA WHICH USES A FIXED AND A VARIABLE LENGTH CODING METHODFigure 5.5. Image obtained by the DigiCipher coding method at 15 dB SNR. Compression ratio = 16.62 : 1.Figure 5.6. Image obtained by the DigiCipher system using VLC andour FLC methods at 15 dB SNR. Compression ratio = 18.20 : 1.111ChapterS A NOISE RESISTANT SCHEME FOR HDTV SYSTEMS AND FULL-MOTIONMULTIMEDIA WHICH USES A FIXED AND A VARIABLE LENGTH CODING METHODIn the decompressed image of “Lena” obtained by the combination of VLC and ourFLC (Figure 5.2), 1207 blocks of 8x8 DCT coefficients were coded by our FLC method.This corresponds to 47 % of the total number of bits needed to represent the compressedimage. In other words, a bit error has a 47 % chance of occurring in a block encoded bythe fixed-length method and the effects of an error occurring in such a block will either benot visible or will be limited to within that block. Because the chance of a bit causing anerroneous macroblock is now 47 % less, this approximately means a 3 dB improvement inthe SNR. The compression ratio obtained by our method is 14.69 : 1, which is better thanthe 12.60 : 1 obtained by the original DigiCipher method.The image “Mandril” was chosen for its high contents of texture. In this case, 2461 (8x8)blocks were encoded by FLC (Figure 5.4). This corresponds to approximately 85 % of thetotal number of bits. As a result, we observe that the decompressed image obtained by thecombination of VLC and FLC (Figure 5.4) appears error-free while the VLC method (Figure5.3) yields a visually unacceptable image. The compression ratio obtained by our method is11.30: 1, which is much better than the 6.40: 1 obtained by the original DigiCipher method.Finally, the image “Hockey Player” represents an image with very large smooth areasand low contrast. In this case, only 18 % of the image shown in Figure 5.6 is coded byfixed-length coding. As expected the FLC method does not offer much protection to thisimage (Figure 5.6) as in the previous two cases (Figures 5.2 and 5.4), since the majority ofthe blocks are encoded by the VLC method. However, the compression ratio still improvesto 18.20 : I from the 16.62 : 1.We conclude that the combination of the original VLC method and our FLC methodimproves the system’s compression performance as well as increases its resistance to bit112ChapterS A NOISE RESISTANT SCHEME FOR HDTV SYSTEMS AND FULL-MOTIONMULTIMEDIA WHICH USES A FIXED AND A VARIABLE LENGTH CODING METHODerrors. However, large erroneous 352x16 macroblocks remain in the pictures since not all8x8 blocks are encoded by FLC. In the following section, we improve the noise-resistanceperformance of the HDTV system by a different hybrid FLC/VLC method which combinesour FLC method with the above VLC method, except that in the latter the actual DC codingmethod (Chapter 2) and the frame-adaptive synchronization scheme (Chapter 3) are used.113ChapterS A NOISE RESISTANT SCHEME FOR HDTV SYSTEMS AND FULL-MOTIONMULTIMEDIA WHICH USES A FIXED AND A VARIABLE LENGTH CODING METHOD5.3. A ROBUST SCHEME WHICH COMBINES THEFLC, FRAME-ADAPTIVE SYNCHRONIZATION,AND ACTUAL DC CODING METHODSAs discussed in Chapter 3, further improvement in the quality of the picture (under noisytransmission conditions) can be obtained if the effects of a bit error are limited to withinsynchronization blocks much smaller than the macroblock or slice. This is achieved by oursynchronization method which uses two different sync block sizes for the reference frames andinter-frames. It was also shown that the noise-resistance performance of this synchronizationmethod is significantly improved when our actual DC coding method is used (see Chapters2 and 3). In this section we combine our FLC method with our modified VLC method, i.e.,the original VLC method modified to use the actual DC coding scheme presented in Chapter2 and our synchronization method proposed in Chapter 3. For our synchronization methodwe adopt 1 6x 16 sync blocks for the reference frames and Mx 16 sync blocks for the inter-frames. The resulting hybrid FLC/VLC method thus yields a scheme that combines the highcompression rate offered by our VLC and the noise-resistance performance characteristics.As we shall be discussing many VLC versions, to distinguish amongst the different oneswe shall adopt the following notation:1) VLC: refers to the original VLC method adopted by the HDTV DigiCipher’ssystem (discussed in Chapter 2).2) VLC, DC: refers to the above (1), but instead of encoding the differential DCcoefficient values we encode the actual DC values using our modifiedHuffman Tables (refer to Section 2.4).114ChapterS A NOISE RESISTANT SCHEME FOR HDTV SYSTEMS AND FULL-MOTIONMULTIMEDIA WHICH USES A FIXED AND A VARIABLE LENGTH CODING METHOD3) VLC, DC, l6x16 sync blocks: refers to the VLC, DC (notation 2 above), but inaddition to DigiCipher’ s macroblock synchronization scheme we also useour synchronization scheme of Chapter 3 with 16x16 sync blocks for thereference frames and 64x 16 sync blocks for the inter-frames.Note that for the hybrid FLC/VLC method discussed in the previous section, the 8x8pixel blocks that are coded by VLC are not necessarily adjacent. As a result, the degree ofcorrelation amongst the DC coefficients of these blocks is reduced, which in turn unfavorablyaffects the compression efficiency of the FLC/VLC method. In the case of the hybridFLCNLC, DC method, which uses our actual DC coding scheme, a higher compression rateis expected. For instance, for the image of “Lena” whose 47 % of the total number of 8x8blocks were coded by FLC (Figure 5.2), the hybrid FLC/VLC, DC method results in 12.911 compression ratio, which is a slight improvement over the 12.60 : 1 obtained by theFLCIVLC method (Table 5.1). The improvement in the compression ratio of the FLC/VLC,DC method over the FLCIVLC method depends on the image content.Using the same simulation format and channel noise as in the previous section, Figure5.7 is obtained by the FLCIVLC, DC, 16x16 sync blocks method. For comparison reasons,Figure 5.8 shows the image “Lena” obtained by the VLC, DC, 16x16 sync blocks method.We observe that, with our FLC/VLC, DC, I 6x 16 sync blocks hybrid method, the number ofvisible errors is reduced by one-half from that of the VLC, DC, 16x16 sync blocks method.Table 5.2 shows the compression ratios obtained by these methods. The compression ratioof our hybrid FLCIVLC, DC, I 6x 16 sync blocks method improves the compression ratio to14.14 :1 (Figure 5.7). This ratio is considerably better than the 12.60: 1 ratio obtained by theDigiCipher’s VLC method (Table 5.2). Thus, the presence of our FLC method increases the115ChapterS A NOISE RESISTANT SCHEME FOR HDTV SYSTEMS AND FULL-MOTIONMULTIMEDIA WHICH USES A FIXED AND A VARIABLE LENGTH CODING METHODnoise-resistance of the system while it balances the bit rate increase caused by the additionof the header-codewords.Image Method Compression ratioLena VLC (DigiCipher) 12.60: 1VLC, actual DC 12.43 : 1VLC, actual DC, 16x16 sync blocks 12.00: 1FLC, VLC, actual DC, 16x16 sync blocks 14.14: 1Mandril VLC (DigiCipher) 6.40: 1VLC, actual DC 6.24: 1VLC, actual DC, 16x16 sync blocks 6.12 : 1FLC, VLC, actual DC, 16x16 sync blocks 11.02: 1Hockey VLC (DigiCipher) 16.62: 1VLC, actual DC 16.45 : 1VLC, actual DC, 16x16 sync blocks 15.70: 1FLC, VLC, actual DC, 16x16 sync blocks 16.60: 1Table 5.2. Compression ratios of “Lena”, “Mandril” and “Hockey Player” obtainedby VLC and different combinations of our coding and synchronization methods.116ChapterS A NOISE RESISTANT SCHEME FOR HDTV SYSTEMS AND FULL-MOTIONMULTIMEDIA WHICH USES A FIXED AND A VARIABLE LENGTH CODING METHODFigure 5.7. Image obtained by our hybrid FLC/VLC, DC, 16x16sync blocks method at 15 dB SNR. Compression ratio = 14.14 1.Figure 5.8. Image obtained by the VLC, DC, 16x16 sync blocks method at 15 dB SNR. Compression ratio = 12.00: 1.117ChapterS A NOISE RESISTANT SCHEME FOR HDTV SYSTEMS AND FULL-MOTIONMULTIMEDIA WHICH USES A FIXED AND A VARIABLE LENGTH CODING METHODFor the image “Mandril” the compression ratio becomes 11.02 : 1 if our hybridFLCIVLC, DC, 16x16 sync blocks method is used.Figure 5.9 shows the image “Hockey Player” obtained by the same FLC/VLC, DC,16x16 sync blocks method. Again, we observe a considerable improvement in image qualityover that obtained by the FLC/VLC method (Figure 5.6). Moreover, even though thisimage represents the case with the smallest number of FLC-coded 8x8 blocks, the obtainedcompression ratio is 16.60: 1, equal to that obtained by the original DigiCipher (Table 5.2).Performance evaluations over a large set of images have shown that, on average, using ourhybrid FLC/VLC, DC, 1 6x 16 sync blocks method increases the compression rate by a valuegreater or equal to the decrease caused by adding the header-codewords in the 16x16 syncblocks synchronization scheme.Figure 5.9. Image obtained by our hybrid FLCIVLC, DC, I 6x 16sync blocks method at 15 dB SNR. Compression ratio = 16.60 1.118ChapterS A NOISE RESISTANT SCHEME FOR HDTV SYSTEMS AND FULL-MOTIONMULTIMEDIA WHICH USES A FIXED AND A VARIABLE LENGTH CODING METHODFinally, we expand our results to the inter-frames of a video sequence. In the case ofinter-frames, the number of 8x8 blocks coded by PLC depends on the degree of motionbetween consecutive frames; areas with significant motion result in large residual differencesand thus are more likely to be coded by PLC. Since image areas with a considerable degreeof motion are more sensitive to errors, using PLC has the advantage of providing betterprotection to these areas than to the rest of the frame. At 15 dB SNR channel noiseFigures 5.10 and 5.11, respectively, show the reference frame and the fifth frame fromthis reference obtained by the original DigiCipher HDTV system. Figure 5.12 shows thereference frame obtained by our hybrid FLC/VLC, DC, 16x16 sync blocks method. The fifthframe obtained by our latter method which utilizes inter-frame compression and provides theinter-frame synchronization at the 64x16 pixel sync blocks level, is shown in Figure 5.13.As is expected, the increase in noise-resistance provided by the actual DC coding method,the header-codewords, and our PLC method results in a significant reduction in the size andnumber of the error-corrupted regions in the frames. We conclude that the combination ofour FLC and VLC proposed methods yields a robust scheme with excellent noise-resistanceperformance and which significantly improves the visual quality of the decompressed frameswithout altering the overall transmission rate.119ChapterS A NOISE RESISTANT SCHEME FOR HDTV SYSTEMS AND FULL-MOTIONMULTIMEDIA WHICH USES A FIXED AND A VARIABLE LENGTH CODING METHOD’Figure 5.11. Fifth frame from the reference frame Figure 5.10 obtained by DigiCipher at channel SNR = 15 dB.Figure 5.10. Reference image obtained by DigiCipher at channel SNR = 15 dB.120ChapterS A NOISE RESISTANT SCHEME FOR HDTV SYSTEMS AND FULL-MOTIONMULTIMEDIA WHICH USES A FIXED AND A VARIABLE LENGTH CODING METHODFigure 5.12. Reference image obtained by our hybrid FLC/VLC, DC, I 6x1 6 sync blocks method at channel SNR = 15 dB.Figure 5.13. Fifth frame from the reference frame Figure 5.12 obtained by ourhybrid FLCJVLC, DC, 16x16 sync blocks method at channel SNR = 15 dB.121ChapterS A NOISE RESISTANT SCHEME FOR HDTV SYSTEMS AND FULL-MOTIONMULTIMEDIA WHICH USES A FIXED AND A VARIABLE LENGTH CODING METHOD5.4 SUMMARYFor still and full-motion video color images we propose a coding method which utilizesa hybrid fixed-length coding (FLC) and variable-length coding (VLC) compression scheme.The DCT coefficients of each 8x8 block of the image are encoded by either the FLC orthe VLC methods depending upon which of the two gives better compression. This methodimproves the system’s compression performance while it increases, on average, the overallerror resistance. To further improve the noise—resistance performance of the system, wecombine this hybrid method with our actual DC coding method proposed in Chapter 2 andthe synchronization scheme (presented in Chapter 3) which uses 16x16 sync blocks forthe reference frames and 64x16 sync blocks for the inter-frames. The resulting schemesignificantly improves the error resistance characteristics of the system without altering theoverall data transmission rate.122Chapter 6CONCLUSIONS AND RECOMMENDATIONSThe desired reduction in the huge bandwidth required for the transmission of digitalHDTV and full-motion multimedia images leads to an unfortunate increase in the errorsensitivity of the system. To protect the system from the effects of noise which may affectthe transmitted bits, all the presently proposed HDTV systems (currently forming the GrandAlliance) employ error correction as well as schemes to protect the synchronization of thetransmitted data. Even with these measures, error propagation and data desynchronizationremain a problem, resulting in sudden picture degradation as the signal-to-noise ratio dropsbelow a certain threshold value.Our objective was to offer solutions to the above problems, thus improving the pictureperformance of the proposed HDTV systems in the presence of noise, without deterioratingthe other desirable qualities of the system, namely the compression ratio and the high qualitycompressed pictures.We met this objective by developing three modification schemes for the presentlyproposed HDTV compression systems and synchronization methods. These modificationsconstitute:1) a new scheme for coding the actual values of the DC terms of DCT coefficientsinstead of their differences,2) a new synchronization method that uses 16x16 synchronization blocks for the referenceframes and Mx 16 synchronization blocks for the inter-frames, and123Chapter 6 CONCLUSIONS AND RECOMMENDATIONS3) a new fixed length compression method which codes the DCT coefficients of 8x8pixel blocks of the picture.Coding the actual values of the DC terms eliminates the error propagation problem arisingfrom coding the differences of these terms. The actual DC coding method we developedincreases the compression ratio only slightly. The new synchronization scheme we proposedrestricts the effects of any bit error to a small block of the picture. This scheme, however,results in an increase in the transmission rate of the system. To compensate, we modifiedthe compression scheme using the fixed length coding method we developed in Chapter4. The modified scheme achieves better compression ratio by encoding each 8x8 block ofDCT coefficients by either our fixed length coding method or the presently proposed variablelength coding method, depending which yields the better compression rate. The resultingmodified methods remain of a variable length coding nature, but provide excellent error-resistance performance and significantly improve the picture quality in the presence of noise,without altering the overall transmission rate of the system. Performance evaluations haveshown that, by using the proposed modifications, the signal-to-noise ratio at which the HDTVpicture starts to deteriorate is reduced by at least 3 dB. After that, the degradation of thepicture is considerably more graceful than that of the proposed systems, thus eliminating theabrupt picture loss characteristic of compressed digital video services.Of the above proposed modifications, the second modification (i.e., the synchronizationscheme) is the only one which increases the compression rate. If only our 1St and 3rdmodifications are introduced, the resulting compression ratio is improved over that of theoriginally proposed HDTV schemes by approximately 20 %.124Chapter 6 CONCLUSIONS AND RECOMMENDATIONSThe fixed length encoding scheme we developed in Chapter 4 may be used to eithermodify the existing compression schemes, as mentioned above, or may stand as a compressionscheme on its own. This scheme has extremely high error resistance and gives high qualitypictures. Because of its robustness to noise, this method can be combined with higher ordermodulation schemes to reduce the overall transmission rate. This combination is ideal forencoding video sequences such as sports programs which contain fast motion.In this work we have provided a solution to the error sensitivity problem inherent incompressed digital video systems, a crucial problem facing the emerging multimedia servicestoday. However, it is clear that we are witnessing only the beginning of a rapidly evolvingnew industry which is opening new areas of research with exciting opportunities for furtherinvestigations and applications. In the following section, we discuss opportunities for furtherresearch and technical refinements which are worthwhile pursuits.6.1. TOPICS FOR FUTURE STUDY6.1 .A. Improving the Compression Performanceof our Fixed Length Coding MethodIn Chapter 4, we proposed a new compression scheme which uses codewords of fixedlengths to compress the different DCT coefficients. Quantization of the DCT coefficients isobtained by applying a quantization table weighted by a quality factor (Q). The quality factorused was equal to 3 since this value provides high quality decompressed images. The fixedsize of the codewords of our scheme depends on the size of the DCT coefficients and thus onthe weighted quantization table. A more intelligent scheme would adjust the fixed size of thecodewords based on the quality factor used for each 8x8 pixel block. The ability to optimize125Chapter 6 CONCLUSIONS AND RECOMMENDATIONSthe size of the codewords as a function of the magnitude of the quantized coefficients wouldresult in better compression ratios than those obtained by our fixed length coding method.6.1.B. Using our Fixed Length Coding Scheme to Compressthe Karhunen-Loève Transform CoefficientsIn Section 4.2, we presented a fixed length method which encodes the positive, negative,and zero terms of the transform coefficients separately and we used this method to compressthe DCT coefficients. The same method could also be applied to the coefficients of othertransforms, such as the Karhunen-Loève Transform and wavelets. In each such application,a new partitioning scheme must first be derived for grouping the transform coefficients intoregions, which can then be efficiently compressed by our fixed length coding method.Preliminary tests using the Karhunen-Loève Transform have shown very promisingresults. The compression ratio obtained by applying our fixed length coding method onthe Karhunen-Loève Transform (KLT) coefficients is 15.37 1. This ratio is better than the9.14 :1 obtained by AMBTC and the 11.11 :1 obtained by our fixed length coding methodwhen applied on the DCT coefficients. Figures 6.1 and 6.2 show the images obtainedby KLT and AMBTC, respectively. For comparison reasons, Figures 6.3 and 6.4 show thedifference of these pictures and Figures 6.1 and 6.2, respectively. We observe that the pictureperformance obtained by the fixed length KLT is slightly worse than that of DCT but betterthan that of AMBTC. Further study of this method is necessary, including an evaluation ofits noise-resistance performance, before we can draw any final conclusions about the overallperformance of this fixed length compression scheme.126Chapter 6 CONCLUSIONS AND RECOMMENDATIONSFigure 6.1. Image obtained by the fixed length KLT method. Compression ratio 15.37 : 1.Figure 6.2. Image obtained by AMBTC. Compression ratio 9.14 : 1.127Chapter 6 CONCLUSIONS AND RECOMMENDATIONSFigure 6.3. Difference image of Figure 6.1.Figure 6.4. Difference image of Figure 6.2.128Chapter 6 CONCLUSIONS AND RECOMMENDATIONS6.1.C. Compression of DCT Coefficients Using FractalsModern fractal geometry was introduced in the late seventies and since then it hasbecome a powerful tool in statistics, physics and texture analysis. While fractals can begenerated by very simple algorithms, they are known to be capable to produce visuallycomplex pictures. Recently, efforts to model digital images using the properties of self-similarity and redundancy present only in fractal objects proved successful. Fractal—basedencoding has shown very strong promise, with picture quality and compression performancecomparable to those of the JPEG compression. The principle behind fractal—based coding isthat real images consist of similar regions at different orientations and scales and, thus, theycan be represented as collections of transformations. Such regions are shown in Figure 6.5.Figure 6.5. Similar regions in image of “Eleni” at different scales and orientations.129Chapter 6 CONCLUSIONS AND RECOMMENDATIONSThe length of the fractal encoding process and the compression ratios obtained by thismethod highly depend on the complexity of the image and the degree of similarity betweenthe different regions. In fact, images that consist of blocks of similar patterns have very fastencoding speed and yield very high compression ratios. Thus, if we were able to representany given image as a collection of identical regions, then fractal encoding of the new imagewould be very fast and the compression ratio very high. This observation opens the doorto an exciting area of research where fractals could be used to compress the quantized DCTcoefficients of the pixel blocks of the image. The image of the discrete cosine transformof any block of a picture consists of regions of similar patterns, i.e., each DCT block hassome large values in the upper left corner with a lot of zero coefficients scattered aroundthe rest of the block. Because of this similarity, these blocks could be compressed by thefractal coding method much faster and much more efficiently than the corresponding blocksof the original image.Preliminary tests of this method have shown strong promise for success. Using fractalcoding to compress the DCT coefficients instead of the actual image improved the compression ratios by more than 100 %, depending on the complexity of the original image. Inaddition, the encoding time was improved by about 75 % over that required for the compression of the actual image. Unfortunately, although our fractal code was able to produce veryhigh quality decompressed images, when applied on the original images (see Figure 6.6), itcould not preserve the values of the DCT coefficients with the same accuracy. As a result,the decompressed images obtained in the latter case were not of the same quality. Furtherinvestigation of this approach is necessary. The preliminary results we obtained could beinherent in the fractal code we used. Other fractal codes with different region geometries130Chapter 6 CONCLUSIONS AND RECOMMENDATIONScould be considered. It seems extremely likely that a combination of a more flexible fractalcoding method with a different size of DCT blocks could produce the necessary accuracyfor the decompressed DCT coefficients, and thus result in compression ratios significantlyhigher than those obtained by the presently known techniques.Figure 6.6. Decompressed image of “Eleni” obtained by fractal coding. The compression ratio of the luminance componentis 6.2 1 which is slightly higher than the 5.8 : I obtained by JPEG (for approximately the same RMSE in both cases).131Bibliography[1] J. A. Adam, “Interactive Multimedia,” IEEE Spectrum, Vol. 30, No. 3, pp. 23, Mar. 1993.[2] J. A. Adam, “Multimedia: Applications, Implications,” IEEE Spectrum, Vol. 30, No. 3,pp. 24—31, Mar. 1993.[3] Advanced Digital Television— System Description. Submitted to Working Party 1 byDavid Sarnoff Research Center and Philips Laboratories, January 20, 1992.[4] D. Anastassiou and M. Vitterli, “Television by the Bit,” IEEE Systems and DevicesMagazine, Vol. 7, No 1, pp. 16—21, Jan. 1991.[5] P. H. Mg, P. A. Ruetz, and D. Auld, “Video compression expands,” IEEE Spectrum,Vol. 28, No. 10, pp. 16—19, Oct. 1991.[6] M. Barbero, H. Hofmann, and N. D. Wells, “DCT source coding and currentimplementations for FIDTV,” EBU Technical Review, No. 251, pp. 22—33, Spring 1992.[7] M. Barbero, S. Cucchi, and M. Stroppiana, “A Bit-Rate Reduction System for IIDTVTransmission,” IEEE Transactions on Circuits and Systems for Video Technology, Vol.1, No. 1, pp. 4—13, Mar. 1991.[8] C. Basile, A. P. Cavallerano, and D. Teichner, “Baseband Video Processing and theTransmission of HDTV Signals,” IEEE Transactions on Circuits and Systems for VideoTechnology, Vol. 1, No. 1, pp. 113—124, Mar. 1991.[9] K. B. Benson and D.G. Fink, “HDTV, Advanced Television for the 1990s,” New York:McGraw Hill, 1991.132[10] F. W. Campell, “The Human Eye as an Optical Filter,” iEEE Proceedings, Vol. 56,No. 6, pp. 1009—1014, June 1968.[11] CCDC HDTV System. Submitted to Working Party I by MiT on behalf of the AmericanTelevision Alliance, April 3, 1992.[12] M. Chelehmal, “Transmission of Digital HDTV — Part 2,” Communications Technology,pp. 22, 48—52, Dec. 1992.[13] W. Chen and W. K. Pratt, “Scene Adaptive Coding,” IEEE Transactions onCommunications, Vol. COM-32, No. 3, pp. 225—232, Oct. 1984.[14] T. R. Chesley, “Testing compressed digital video signals: A case study,” CommunicationsTechnology, pp. 28, 46—48, May 1991.[15] B. Cole, “Multimedia: The Technology Framework,” IEEE Spectrum, Vol. 30, No. 3,pp. 32—39, Mar. 1993.[16] M. Cominetti, A. Morello, and M. Visintin, “Wide RE-band digital HDTV emissionsystems — Performance of advanced channel coding and modulation techniques”, EBUTechnical Review, No. 251, pp. 4—19, Spring 1992.[17] E. J. Deip and 0. R. Mitchell, “Image compression using block truncation coding,” IEEETransactions on Communications, Vol. COM-27, No. 9, pp. 1335—1342, Sept. 1979.[18] DigiCipher HDTV System Description. Submitted to Working Party I by GeneralInstrument Corporation on behalf of the American Television Alliance, Aug. 22, 1991.133[19] “Digital Compression and Coding of Continuous-tone Still Images”, Part I, Requirementsand Guidelines ISO/IEC DIS Draft International Standard 10918—1, Oct. 1991.[20] Digital Spectrum Compatible — Technical Details. Submitted to Working Party 1 byZenith and AT&T, Sept. 23, 1991.[21] Y. C. Faroudja, “NTSC and Beyond,” IEEE Transactions on Conswner Electronics, Vol.34, No. 1, pp. 166—176, Feb. 1988.[22] T. 3. Ferguson and J. H. Rabinowitz, “Self-Synchronizing Huffman Codes,” IEEETransactions on Information Theory, Vol. IT-30, No. 4, pp. 687—693, July 1984.[23] G. Gilder, “Into the Telecosm,” Harvard Business Review, pp. 150—161, Mar.-April 1991.[24] R. C. Gonzalez and P. Wintz, “Digital Image Processing,” second edition, AddidonWesley, 1987.[25] G. Hirtz, B. Bader, M. Maier, B. Tenconi, and U. E. Kraus, “Symmetrical Deflectionfor Future IDTVIHDTV Receivers,” IEEE Transactions on Consumer Electronics, Vol.39, No. 3, pp. 225—233, Aug. 1993.[26] R. Hopkins, “Digital HDTV Broadcasting,” IEEE Transactions on Broadcasting, Vol.37, No 4, pp 123—127, Dec 1991[27] IEEE Transactions on Broadcasting— Special Report, “Federal CommunicationsCommission Advanced Television System Recommendation — FCC AdvisoryCommittee on Advanced Television Service,” Vol 39, No 1, Mar 1993[28] T. Kinoshita, T. Nakahashi, and M. Maruyama, “Variable-Bit-Rate HDTV CODEC with134ATM-Cell-Loss Compensation,” IEEE Transactions on Circuits and Systems for VideoTechnology, Vol. 3, No. 3, PP. 230—236, June 1993.[29] A. K. Jam, “Image Data Compression: A Review,” Proceeding of the IEEE, Vol. 69,No. 3, pp. 349—385, Mar. 1981.[30] R. K. Jurgen, “Digital Video,” IEEE Spectrum, Vol. 29, No. 3, pp. 24—30, Mar. 1992.[31] R. K. Jurgen, “The challenges of digital HDTV”JEEE Spectrum, Vol. 30, No. 3, pp.28—30, 71—73, April 1991.[32] B. 3. Lechner, “Testing HDTV Terrestrial Broadcasting Systems,” IEEE Transactions onBroadcasting, Vol. 37, No. 4, pp. 148—151, Dec. 1991.[33] S. Lee, S. Kim, J. Kim, K. Lee, and K. Jang, “Modified a Posteriori Mode Decisionfor HD-MAC System,” IEEE Transactions on Consumer Electronics, Vol. 39, No. 3,Aug. 1993.[34] A. Leger, M. Mitchell, and Y. Yamazaki, “Still picture compression algorithmsevaluated for international standardization,” IEEE Proceedings of GLOBECOM ‘88,pp. 1028—1032, Nov. 1988.[35] M. D. Lema and 0. R. Mitchell, “Absolute Moment Block Truncation Coding and ItsApplication to Color Images,” IEEE Transactions on Communications, Vol. COM-32,No. 10, Pp. 1148—1157, Oct. 1984.[36] L. W. Lockwood, “General Instrument’s HDTV proposal,” Communications Technology,PP. 112—120, Aug. 1990.135[37] L. W. Lockwood, “The Zenith and AT&T all-digital proposal,” CommunicationsTechnology, pp. 64-72, May 1991.[381 A. C. P. Loui and M. L. Liou, “High-Resolution Still-Image Transmission Based onCCITT H.261 Codec,” IEEE Transactions on Circuits and Systemsfor Video Technology,Vol. 3, No. 2, pp. 164-168, April 1993.[39] J. C. McKinney, “HDTV Approaches the End Game,” IEEE Transactions onBroadcasting, Vol. 37, No. 4, pp. 121—122, Dec. 1991.[40] J. C. Maxted and J. P. Robinson, “Error Recovery for Variable Length Codes,” IEEETransactions on Infonnation Theory, Vol. IT-31, No. 6, pp. 794—801, Nov. 1985.[41] J. Mau, E. Bourguignant, and H. Amor, “Sub-band source coding for HDTV,” EBUTechnical Review, No. 251, pp. 31 11, Spring 1992.[42] W. A. Mostert, “Putting HDTV to the test,” Communications Technology, pp. 72—77,Oct. 1988.[43] Motion Picture Expert Group 2, Recommendation H.262, ISOIIEC 138 18—2, CommitteeDraft, “Generic Coding of Moving Pictures and Associated Audio,” Nov. 1993.[44] Motion Picture Expert Group 4 — Application Notes, ISO/IEC JTC1/SC29/WG1 1MPEG4 93, “Coding of Moving Pictures and Associated Audio,” Dec. 1993.[45] P. Nasiopoulos, R. K. Ward, and D. J. Morse, “Adaptive Compression Coding,” IEEETransactions on Communications, Vol. 39, No. 8, pp. 12451254, Aug. 1991.[46] P. Nasiopoulos, R. K. Ward, D. P. Bouras, and P. T. Mathiopoulos, “HDTV Picture136Performance Under Noisy Conditions — Analysis and Measures for Improvement”revision submitted to the IEEE Transactions on Circuits and Systems for VideoTechnology.[47] P. Pancha and M. E. Zarki, “Bandwidth-Allocation Schemes for Variable-Bit-Rate MPEGSources in ATM Networks,” IEEE Transactions on Circuits and Systems for VideoTechnology, Vol. 3, No. 3, pp. 190—198, June 1993.[481 K. C. Pohlmann, “CD-Formats: Applications,” J. Audio Engineering Society, Vol. 36,No. 4, pp. 25 1—282, April 1988.[49] W. K. Pratt, “Digital Image Processing,” second edition, New York: J. Wiley & SonsInc., 1991.[50] T. Pratt and C. W. Bostian, “Satellite Communications,” New York: J. Wiley & SonsInc., 1986.[51] J. G. Proakis, “Digital Communications,” New York:McGraw Hill, 1989.[52] R. Pordan, “U.S. Cable Labs —MPEG2 Application Notes,” Nov. 1993.[53] D. Ranada, “Error-Correction Myths Exploded,” High Fidelity, Vol. 37, No. 10, pp.45—50, Oct. 1987.[54] C. Robbins, “Digital video for CATV,” Communications Technology, pp. 26, 40—44,May 1991.[55] G. Robinson, “HDTV Today,” Communications Technology, pp. 20—21, 11-16, Dec.1992.137[56] K. M. Rose and A. Heiman, “Enhancement of One-Dimensional Variable-Length DPCMImages Corrupted by Transmission Errors,” IEEE Transactions on Communications, Vol.37, No. 4, pp. 373—379, April 1989.[57] M. H. Sherif, D. 0. Bowker, G. Bertocci, B. A. Orford, and G. A. Mariano, “Overviewand Performance of CCITT/ANSI Embedded ADPCM Algorithms,” IEEE Transactionson Communications, Vol. 41, No. 2, pp. 391—399, Feb. 1993.[58] B. Skiar, “Digital Communications, Fundamentals and Applications,” New Jersey:Prentice Hall, 1988.[59] R. Simonetti, A. P. Filisan, S. Carrato, G. Ramponi, and G. Sicuranza, “A Deinterlacerfor IQTV Receivers and Multimedia Applications,” IEEE Transactions on ConsumerElectronics, Vol. 39, No. 3, pp. 234—240, Aug. 1993.[60] SPW, COMDISCO® Systems, Inc., 919 E. Hillsdale Blvd. Foster City, CA 94404.[61] SS/WP-1 Analysis Task Force — Questionnaire and Answers: DigiCipher HDTV System,Aug. 1991.[62] I. Taminati, H. Harasaki, and T. Nishitani, “A Real-Time HDTV Signal Processor:HD-VSP,” IEEE Transactions on Circuits and Systems for Video Technology, Vol. 1, No.1, pp. 35—41, Mar. 1991.[63] C. K. Tanner, “Advanced TV status report,” Communications Technology, pp. 16, 58—60,80, Aug. 1990.[64] Technical Critique of Advanced Television Research Consortium’s ADTV System.138Submitted to FCC Advisory Committee on Advanced Television Service by the WP-1Analysis Task Force, Jan. 1992.[65] Technical Critique of General Instrument’s DigiCipher HDTV system. Submitted toFCC Advisory Committee on Advanced Television Service by the WP-1 Analysis TaskForce, Aug. 1991.[66] L. J. Thorpe, “HDTV and Film — Issues of Video Signal Dynamic Range,” SMPTEJournal, pp. 780—795, Oct. 1991.[67] G. H. Robinson, “A Cable Perspective on Digital Transmission,” CommunicationsTechnology, pp. 22—38, May 1991.[68] G. K. Wallace, “Digital Image and Video Standards,” Communications of the ACM, Vol.34, No. 1, Pp. 31—44, April 1991.[69] K. I. Werner, “The flat panel’s future,” IEEE Spectrum, Vol. 30, No. 11, PP. 27—31,Nov. 1993.[70] J. Weiss and Doug Schremp, “Putting data on a diet,” IEEE Spectrum, Vol. 30, No. 8,pp. 36—39, Aug. 1993.[711 Y. Yashima and K. Sawada, “An Extrapolative-Interpolative Prediction Coding Methodfor HDTV Signal,” IEEE Transactions on Communications, Vol. 38, No. 10, pp.1779—1785, Oct. 1990.[72] J. M. Younse, “Mirrors on a chip,” IEEE Spectrum, Vol. 30, No. 11, pp. 27—3 1, Nov.1993.139Appendix ABit Error Rate PerformanceThe bit error rate performance of our computer simulated communication link is shownin the following figure. The simulated error rate results were obtained with Monte Carlocounting techniques. The performance of uncoded 16—QAM is also included for comparison,together with its theoretically calculated [511 upper bound.Performance evaluations have shown that at a bit error rate of lO-, which correspondsto approximately 15 dB SNR, the picture quality of the system deteriorates abruptly.100______ ______ ______ ______ ______ ______ ______ ______..2—110 \-——-- --—--“ ‘‘4.-—-——-\\ \-3‘10‘‘‘‘‘‘L‘ ‘‘-410itiitiZiZttt0 5 10 15 20SNR (dB)Uncoded bound (theoretical)Uncoded ———0———Reed-Solomon (116,106)Figure A.1. Reed-Solomon (116,106) coded versus uncoded 16—QAM.140Appendix BPartitioning of DCT Coefficients into RegionsOur objective is to preserve the coefficients near the DC term as accurately as possible.We know that weighted coefficients near the DC term are expected to have larger absolutevalues than the ones further. Table B.1 shows the grey values of a typical 8x8 pixel blockof a picture (a) and the resulting “weighted” DCT coefficients (b). Please notice that manyof the DCT coefficient values are equal to zero specially the high frequency components.209 185 116 67 72 81 71 72 256 64 10 -1 -1 0 1 0218 206 167 97 68 79 73 79 -54 21 17 0 -1 0 0 0223 213 195 131 72 77 64 80 2 -13 4 6 -1 0 0 0216 213 208 165 99 85 90 89 -2 1 -4 3 2 0 0 0214 215 213 194 148 105 97 98 -1 -2 1 0 0 0 0 0215 214 217 209 194 158 119 111 -1 0 0 0 0 0 0 0213 211 213 214 213 198 166 137 0 0 0 0 0 0 0 0209 213 213 210 214 212 204 189 0 0 0 0 0 0 0 0(a) (b)Table B. 1. Grey values of an 8x8 pixel block (a) and the resulting weightedDCT coefficients (b) with weights of Table 2.1 a and quality factor Q = 3.Assume there are p coefficients to be quantized by AMBTC. To achieve our objective let us denote the coefficients with values greater than or equal to the mean valueby x L L • L and the coefficients with values smaller than the mean byp 1 5 qXS’XS’...’XS.Obviously, r + q = p.To preserve XL we need to minimize (b—XL),141i.e., _(b XL) = 0. (B.1)Substituting equation (4.3) in the above equation we obtain+XL)=0 (B.2):: (B.3)[x+2xL+_rxyxSxL]x(B.4)=0.qSubstituting X= —x in (B.4) we eventually obtain[xLxL]=o (B.5)If x L, is chosen to satisfy (B.5), i.e.,(B.6)then the error in (b — x L, ) 2 can be shown to be[xLxL]2 (B.7)142Let us consider the following cases:A. When only one coefficient is greater than,i.e., q = 1, then equation (B.7) is alwayssatisfied. Therefore, if only one term is greater than or equal to the mean value then theerror in its vector quantization is zero and the term is reproduced exactly.B. When only two coefficients x L, and x L are greater than , i.e., q = 2, equation (B.7)is satisfied whenXL +XLXL (B.8)which is true only when XL = L In this case, the error in quantizing XL and xis equal to zero.x L does not satisfy (B.8), then the error in quantization is[XL L]2 (B.9)for each XL, and x Lr Thus, the closer X L, and X L in value the smaller the errorin representing each one of them.C. Whenq=3wehavex,x andxL onlygreaterthanF.Ifx =XL =XL3,then the error in quantization is zero for each of XL, 23L and X L3•If x L XL L XL , then the error in X L is2 312 (XL+XL)2j XL1 — 2 2 (B.1O)Thus the closer XL L to X L,’ the smaller the error in x L,• In general, the closerX L,’ x L and X L3 in value to each other the smaller the error in representing each.143Appendix CQuantization Levels for Negative DCT CoefficientsFor n negative coefficients, let x be the jth coefficient. Then the sample mean is, x <0 (C.1)n n. nand the sample first absolute central moment is=_x x <0 (C.2)(A.2) and (A.1) are rewritten as1— 1 (C.3)forx forx forx> forx>n = > x + x <0 (C.4)forx forx,1> 2 2Assume q is the number of pixels with values greater than or equal to , equation(A.3) becomesn= q — x + n — x—(n— q) (C.5)forx< 2 forx.which is rewritten asq F — x (C.6)forx,1144and if we define-y as f-, then(C.7)The two quantization levels at the decoder end, a and b, should preserve the momentsgiven by (A.1) and (A.2). Thus we can writen=x =qb+(n—q)a (C.8)and=x=— b) + (n — q)(a—) (C.9)Solving (A.8) and (A.9) for the unknowns a and b we obtainb forx < (C.1O)n q ni na + forx >F (C.11)Ii fl n—q lii fl145Appendix DBit Size of FLC Coefficients and Locations for Q = 3Luminance BlocksI Region 1I dc coefficient I 2nd coefficient I 3rd coefficientnumber of bits 8 6 + 1 for sign I 6 + 1 for signlarger absolute absolute centralquantization level of moment of dominantnon-dominant group group4 I 6number of bitsRegion 5 - Only if Q > 3.0coefficients of dominant location of first location of secondgroup coefficient coefficient3+lforsign I 4 IChrominance BlocksReiion 1dc coefficient I 2nd coefficientnumber of bits I 8 + 1 for sign 6 + 1 for signRegion 2dominant mean of dominant larger absolute absolute centralgroup group quantization level of moment of dominantidentification non-dominant group groupnumber of bits 1 3 3 5number of bitsRegions 2, 3 & 4dominant mean of dominantgroup groupidentificationI 4146Region 3coefficients of dominant location of first location of secondgroup coefficient coefficientnumber of bits 3 + 1 for sign 4 5147Appendix EList of AcronymsADTV Advanced Digital TelevisionAMBTC Absolute Moment Block Truncation CodingBTC Block Truncation CodingCCDC Channel Compatible DigiCipherCCITT Consulting Committee on International Telegraph and TelephoneDCT Discrete Cosine TransformDSC-HDTV Digital Spectrum Compatible High Definition TelevisionEOB End of BlockFCC Federal Communications CommitteeFEC Forward Error CorrectingFIR Finite Impulse ResponseFLC Fixed length codingHD-MAC High Definition Multiplexed Analog ComponentHDTV High Definition TelevisionJPEG Joint Photographic Experts GroupMPEG Motion Pictures Experts GroupMUSE Multiple Sub-Nyquist Sampling EncodingNTSC National Television Systems CommitteeQ Quality FactorQAM Quadrature amplitude modulationRGB Red Green BlueRMSE Root mean square errorRS Reed-SolomonSNR Signal to noise ratioVLC Variable length codingY, U, V Luminance and Chrominance signals148
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Error resistant schemes for all-digital high definition...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Error resistant schemes for all-digital high definition television Nasiopoulos, Panagiotis 1994
pdf
Page Metadata
Item Metadata
Title | Error resistant schemes for all-digital high definition television |
Creator |
Nasiopoulos, Panagiotis |
Date Issued | 1994 |
Description | The picture quality of digital HDTV in the presence of bit errors in the transmission channel is addressed in this thesis. New coding and data synchronization schemes which improve the performance of the picture quality are subsequently developed. I first analyze the causes of the different kinds of digital picture impairments which may arise when the compression schemes proposed by the present HDTV systems are used. All these compression schemes are Discrete Cosine Transform (DCT) based. The picture quality performance is found to suffer mostly from the proposed differential coding of the DC terms of the DCT coefficients and from the variable length coding used. Due to the differential coding of the DC terms a bit error in one of these terms will propagate to consecutive bits. The use of variable length coding, i.e., coding the different DCT terms by words of different lengths, results in the synchronization problem where the received bits do not correspond anymore to the originally intended information. I develop a new method which codes the actual values of the DC terms instead of their differences. This solves the error propagation problem without altering the overall compression ratio of the system. To solve the synchronization problem, I present a new synchronization method which restricts the effects of any bit error to a block of the picture whose size is much smaller than those presently proposed by the HDTV systems. By modifying the originally proposed schemes for HDTV with my proposed DC term encoding and synchronization schemes, the signal-to-noise ratio at which the HDTV picture suddenly deteriorates is deferred by 2.5 to 3 dB. This has a special advantage when higher order modulation transmission schemes are used. Using higher order modulation improves the bit transmission rate but increases the system’s susceptibility to noise. I then develop a novel fixed length coding method which compresses each DCT coefficient by a codeword of a fixed length. Fixed length coding methods do not suffer from the error propagation and synchronization problems inherent in the variable length coding methods. Thus, my method is extremely resistant to errors, produces high quality pictures and is easier to implement. However, it does not improve the compression ratio. It is, thus, an ideal candidate for compressing video sequences with fast motion, such as sports, where the high compression ratios obtained by the motion compensation schemes are not attainable due to the fast motion. Finally, a hybrid method that modifies the originally proposed HDTV schemes using the three above proposed methods is presented. The three modifications involve the use of the fixed length coding method, the actual DC coding method and the synchronization scheme I developed. These modifications significantly improve the picture performance of the system in the presence of noise and do not alter the overall data transmission rate. |
Extent | 8778817 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-04-10 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0064809 |
URI | http://hdl.handle.net/2429/7025 |
Degree |
Doctor of Philosophy - PhD |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 1994-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_1994-894407.pdf [ 8.37MB ]
- Metadata
- JSON: 831-1.0064809.json
- JSON-LD: 831-1.0064809-ld.json
- RDF/XML (Pretty): 831-1.0064809-rdf.xml
- RDF/JSON: 831-1.0064809-rdf.json
- Turtle: 831-1.0064809-turtle.txt
- N-Triples: 831-1.0064809-rdf-ntriples.txt
- Original Record: 831-1.0064809-source.json
- Full Text
- 831-1.0064809-fulltext.txt
- Citation
- 831-1.0064809.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0064809/manifest