THREE-DIMENSIONAL TRANSFORM ENCODING AND BLOCK QUANTIZATION OF STILL COLOUR AND MONOCHROME MOVING PICTURES by Andre" Soubigou Inge"nieur de l'Ec o l e Nationale de 1'Aviation C i v i l e , Orly, France, 196 7. Ingenieur specialise* de l ' E c o l e Nationale Supe*rieure de 1'Ae"ronautique, P a r i s , France, 1968. M.A.Sc. (E.E.), Universite Laval, Quebec, P.Q., 1971. A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in the Department of E l e c t r i c a l Engineering We accept this t h e s i s as conforming to the required standard Research Supervisor Members of the Committee Members of the Department of E l e c t r i c a l Engineering The University of B r i t i s h Columbia In p r e s e n t i n g t h i s t h e s i s in p a r t i a l f u l f i l m e n t o f the r e q u i r e m e n t s f< an advanced degree at the U n i v e r s i t y of B r i t i s h C o l u m b i a , I agree tha the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s t u d y . I f u r t h e r agree t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y p u rposes may be g r a n t e d by the Head o f my Department o r by h i s r e p r e s e n t a t i v e s . I t i s u n d e r s t o o d t h a t c o p y i n g o r p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l not be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . Department o f b LccrHlCftt htVC^fi/kt'/ZtNCj The U n i v e r s i t y o f B r i t i s h Columbia 2075 Wesbrook Place Vancouver, Canada V6T 1W5 ABSTRACT A bandwidth compression scheme for d i g i t a l colour images using three-dimensional Fourier transform encoding and block q u a n t i z a t i o n i s investigated. The brightness U(x,y,X) of a colour p i c t u r e i s considered as a three-dimensional function of the s p a t i a l dimensions x,y and the wavelength dimension X. A set of colour pictures has been sampled. The study of the second order s t a t i s t i c s of the data i n d i c a t e s various models f o r the autocorrelation function, depending on the type of p i c t u r e . A separable exponential model i s shown to provide a reasonable f i t to s t r o n g l y corre-l a t e d data having v e r t i c a l and h o r i z o n t a l features. When those features are not present a non-separable exponential model provides a b e t t e r f i t . Many experimental r e s u l t s of the three-dimensional F o u r i e r transform encoding and block quantization of colour p i c t u r e s are presented. The e f f e c t s of the sub-picture bize and the average number of b i t s per p i c t u r e element (b.p.p.e.) are considered; 2.75 b.p.p.e. seems s u f f i c i e n t to reproduce a reasonably good q u a l i t y p i c t u r e . The use of the separable model i s shown to y i e l d r e s u l t s close to the optimum p o s s i b l e at low b i t rates, although the model f a i l s to c l o s e l y p r e d i c t the s i g n a l - t o - n o i s e r a t i o of the reconstructed p i c t u r e . It i s shown that a non-separable model y i e l d s b e t t e r p r e d i c t i o n , at -considerable computational expense, but i t does not s i g n i f i c a n t l y improve the a c t u a l performance. An adaptive system i s also considered. The e f f e c t of d i g i t a l channel errors on three-dimensional trans-form encoded p i c t u r e s i s i n v e s t i g a t e d . i i The application of three-dimensional transform encoding for monochrome time-varying pictures is also considered. Fourier and Hadamard transformations are shown to yield similar results for the specific set of pictures used in our study. Included in the thesis is a summary of results and suggestions for further work. i i i TABLE OF CONTENTS Page I. INTRODUCTION 1.1 Motivation 1 1.2 Review of Relevant Work by Others 2 1.3 Scope of the Thesis 4 1.4 Outline of the Thesis 5 II. COLOR IMAGE PROCESSING SYSTEM 2.1 Scanning Equipment 7 2.1.1 Flying Spot Scanner - Phosphor 7 2.1.2 Fil t e r s 9 2.1.3 Photomultiplier 10 2.2 Scanning Process 10 2.3 Display Process , 10 2.4 Original Image Data 13 III. DATA STATISTICS 3.1 Introduction . . 15 3.2 First Order Statistics 15 3.3 Second Order Statistics 19 3.3.1 Introduction 19 3.3.2 Estimation of Pictures Statistics . . . . 21 3.4 Choice of a Model 24 3.5 Non-separable Model 28 3.5.1 Non-separability in the Spatial Dimensions 28 3.5.2 Separability of the Spatial and Colour Dimensions 31 i v ; Page 3.6 Double-exponential Model 33 3.7 Conclusion 36 IV. THEORY OF TRANSFORM ENCODING 4.1 Introduction . . . 39 4.2 Theory of Three-dimensional Fourier Transform Encoding 41 4.3 Performance of a Three-dimensional Transform Processing System . . . . . . . . . . 44 V. QUANTIZATION OF THE FOURIER SAMPLES 5.1 Introduction 48 5.2 Statistics of the Fourier Samples . . . . . . . . 48 5.3 -Bit Allocation 52 5.4 Quantization . . . 53 5.4.1 Estimation of the Quantization Error . . . 54 5.4.2 Importance of the Quantization Error . . . 54 5.4.3 S/N Ratio as a Function of the Number of b.p.p.e. 55 5.4.4 S/N Ratio as a Function of the Sub-picture size 56 5.5 Conclusion - Simulation Technique . . . . . . . . 56 VI. THREE-DIMENSIONAT TRANSFORM ENCODING OF COLOUR PICTURES 6.1 Introduction 61 6.2 Experimental Results Obtained Using Various Sub-Picture Sizes and Various Numbers of Bits Per Picture Element (b.p.p.e.) . 6 4 6.2.1 Sub-picture Size 6 x 6 x 6 . . . 64 6.2.2 Sub-picture Size 8 x 8 x 6 . . . . . . . . 65 6.3 Discussion of the Results . . . . . . . . . . . 78 v Page V I I . EFFECTS OF IMPROVED QUANTIZATION, BETTER DATA MODELLING, ADAPTIVE PROCESSING, AND DIGITAL CHANNEL ERRORS ON COLOUR PICTURES 7.1 I n t r o d u c t i o n 89 7.2 M o d i f i c a t i o n o f t h e Q u a n t i z e r o f t h e P i c t u r e D.C. F o u r i e r Component . . . 89 7.3 A t t e m p t s t o Improve P e r f o r m a n c e by Use o f a More P r e c i s e Model 93 7.3.1 N o n - s e p a r a b l e M o d e l . . 93 7.3.2 D o u b l e - e x p o n e n t i a l Model 97 7.3.3 P r o c e s s i n g U s i n g t h e A c t u a l V a r i a n c e s o f the F o u r i e r Samples 97 7.4 A d a p t i v e P r o c e s s i n g f o r Improved P e r f o r m a n c e . . 102 7.5 E f f e c t o f d i g i t a l c h a n n e l e r r o r s . . . . . . . . 108 7.6 D i s c u s s i o n o f R e s u l t s 114 V I I I . THREE-DIMENSIONAL TRANSFORM ENCODING OF MONOCHROMATIC MOVING PICTURES 8.1 I n t r o d u c t i o n . . . 119 8.2 D a t a Base and D a t a S t a t i s t i c s . . . . . . . . . 119 8.3 E x p e r i m e n t a l R e s u l t s . . . . . . . . 123 8.4 C o n c l u s i o n . 125 IX. CONCLUSION 9.1 Summary o f R e s u l t s 128 9.2 S u g g e s t i o n s f o r F u t u r e R e s e a r c h ". . . . . . . . 130 v i Page APPENDIX A: Some sta t i s t i c s of source data and histograms of intensity levels for the pictures GARDEN3, FACE, HOUSE, TEST PATTERN, BUILDING 132 APPENDIX B: Various correlation coefficients 139 APPENDIX C: Some examples of the b i t allocation of the Fourier samples 148 APPENDIX D: Histograms of Fourier samples for the picture FACE . 154 REFERENCES 15 8 v i i LIST. OF ILLUSTRATIONS Figure Page 2.1 Experimental arrangement used to scan 8 2.2 Tentative spectral energy distribution of LP203 phosphor 8 2.3 F i l t e r s transmission characteristics 11 2.4 Photomultiplier sensitivity 11 2.5 Experimental arrangement used to display 12 2.6 Original colour images 14 |3.1 Histograms of intensity levels for each colour plane and for the entire picture for the picture GARDEN1 . . 17 ,3.2 Histograms of intensity levels and Maxwell distribution 18 3.3 Mean and Standard deviation of the brightness as a function of the spatial dimension x 20 3.4 Mean of the brightness as a function of the wavelength for each picture and averaged over the six pictures 20 3.5 Correlation coefficient in the spatial direction X for the pictures GARDEN1 and GARDEN3 . , . 22 3.6 Correlation coefficient in the spatial direction Y for the pictures GARDEN1 and GARDEN3 23 3.7 Correlation coefficient in the wavelength direction X for the pictures GARDEN1 and GARDEN3 . 25 3.8 Comparative f i t of separable and non-separable models to diagonal spatial correlation coefficients for the pictures GARDEN 1 and GARDEN3 . . . 29 3.9 Comparative f i t of separable and non-separable models to diagonal spatial correlation coefficients for the pictures FACE and HOUSE 30 3.10 Correlation coefficient in the direction X-X and separable model for the pictures GARDEN1, GARDEN3 and FACE 32 v i i i Page 3.11 Comparative f i t of the single-exponential model and the double-exponential model in the spatial directions for the picture GARDEN1 34 3.12 Comparative f i t of the single-exponential model and the double-exponential model in the spatial directions for the picture GARDEN3 35 3.13 Comparative f i t of the non-separable and separable double exponential models in the diagonal sps t i a l direction for the pictures GARDEN1 and GARDEN3 . . . . 37 4.1 Transform encoding system . . 39 4.2 S/N ratio as a function of the number of transmitted samples for various transform encoding systems . . . . 47 5.1 Histograms of Fourier samples for the picture GARDEN1 . 50 5.2 Histograms of Fourier samples for the picture GARDEN1 . 51 5.3 Quantization of the Fourier samples 52 5.4 S/N ratio as a function of the average number of b.p.p.e. for various transform encoding systems 57 5.5 S/N ratio as a function of the sub-picture size . . . . 58 5.6 Three-dimensional transform encoding system . . . . . . 59 6.1 Various estimations of the S/N ratio 62 6.2 Transform processed pictures. Only the D.C. component was used to reconstruct the picture. Sub-picture size 6 x 6 x 6 (a) GARDEN1, (b) FACE, (c) TEST PATTERN . . . 63 6.3 Transform processed pictures. Sub-picture size 6 x 6 x 6 1 b.p.p.e. 66 6.4 Transform processed pictures. Sub-picture size 6 x 6 x 6 2 b.p.p.e. . . . . . . . . . . . . . 67 6.5 Transform processed pictures. Sub-picture size 6 x 6 x 6 3 b.p.p.e. 68 6.6 Transform processed pictures. Sub-picture size 8 x 8 x 6 1 b.p.p.e. 75 6.7 Transform processed pictures. Sub-picture size 8 x 8 x 6 2 b.p.p.e 76 ix Page 6.8 Transform processed pictures. Sub-picture size 8 x 8 x 6 3 b.p.p.e 77 6 . 9 S/N ratio as a function of the average number of b.p.p.e. for a 6 x 6 x 6 sub-picture size 82 6.10 S/N ratio as a function of the average number of b.p.p.e. for a 8 x 8 x 6 sub-picture size 83 6.11 S/N ratio as a function of the number of transmitted samples (no quantization) for an 8 x 8 x 6 sub-picture size. The number of transmitted samples for 1,2 and 3 b.p.p.e. is indicated 86 6.12 Absolute difference signal between processed and original pictures. Sub-picture size 16 x 16 x 6. 2 b.p.p.e. (a) GARDEN1, (b) FACE, (c) TEST PATTERN 88 7.1 Modification of the Fourier D.C. component quantizer . . 90 7.2 Transform processed pictures. Sub-picture size 16 x 16 x 6. 2.75 b.p.p.e. Adapted quantizer 92 7.3 S/N ratio as a function of the number of transmitted samples (1) predicted by the variances estimated from the simple model (2) predicted by the normalized actual variances for a 16 x 16 x 6 sub-picture size. The S/N measured for 2.75 b.p.p.e. are shown 94 7.4 Comparison between S/N ratios, as a function of the number of transmitted samples, predicted by the variances estimated from the separable model and the non-separable model and the actual normalized variances. Sub-picture size 8 x 8 x 6 . Picture GARDEN1 . . . . . . . . . . . . 96 7.5 S/N ratio as a function of the number of transmitted samples predicted by the variances estimated from the .single exponential model, the double exponential model and the actual normalized variances. Sub-picture size 1 6 x 16 x 6. Pictures GARDEN 1 and GARDEN3 . . . . . . . . 98 7 .6 Pictures processed using the adapted quantizer for the D . C . component, 2.75 b.p.p.e. and for each picture, the [ actual variances of the samples of the Fourier transform of the picture • 99 • 7 . 7 Estimated values of the correlation parameters a, 3 and Y over 16 x 16 x 6 sub-pictures for the picture FACE . . 103 7.8 Perspective p l o t s of the c o r r e l a t i o n parameters a, 8 and y estimated over 16 x 16 x 6 sub-pictures f o r the p i c t u r e FACE . . . . . 105 7.9 (a) Transformed p i c t u r e FACE 2.75 b.p.p.e. (b) Transformed p i c t u r e FACE 2.75 b.p.p.e. Adaptive processing . . . . . . . . 107 7.10 Transmission of transform encoded p i c t u r e s over a noisy channel . . . . . . . . . . . . 109 7.11 E f f e c t of d i g i t a l channel errors on 3 b.p.p.e. three-dimensional transform encoded p i c t u r e s ; per d i g i t error p r o b a b i l i t y p £= 0.01 . . 110 7.12 E f f e c t of d i g i t a l channel errors on PCM transmitted o r i g i n a l data; p e r - d i g i t error p r o b a b i l i t y p e = 0.01 . 113 7.13 (a) (b) Two-dimensional Hadamard transformed p i c t u r e s , (c) (d) Two dimensional Fourier transformed p i c t u r e s , (e ) ( f ) Three-dimensional F o u r i e r transformed p i c t u r e s 2 .75 b.p.p.e 116 7.14 Three-dimensional Fourier transform p i c t u r e FACE 16 x 16 x 6, 1.0, 1.5 and 2.0 b.p.p.e. . . . . . . . . 118 8.1 O r i g i n a l data SCENE1. Eight consecutive frames taken at 24 frames per second, quantized to 8 b i t s . 256 x 256 elements 120 8.2 C o r r e l a t i o n c o e f f i c i e n t along the s p a t i a l dimensions f o r SCENE1 ( F i g . 8.1) and least-square f i t of the exponential mode 1 . . . 121 8.3 C o r r e l a t i o n c o e f f i c i e n t along the time dimension of SCENE1 ( F i g . 8.1) and least-square f i t of the exponential model . . . 122 8.4 S/N r a t i o as a function of the number of transmitted samples for the Hadamard and the Fourier transforms f o r the SCENE1 from the estimated variances and from the ac t u a l normalized variances. The actual S/N r a t i o f o r 8 b.p.p.e. (539 samples) i s shown and compared to the r e s u l t s predicted by the actual variances, the quantization being taken i n t o account . . . . . . . . . 124 8.5 Eight frames of SCENE1 ( F i g 8.1) three-dimensional F o u r i e r transformed using an average of 1 b.p.p.e. per frame . 126 8.6 Eight frames of SCENE1 ( F i g . 8.1) three-dimensional Hadamard transformed using an average of 1 b.p.p.e. per frame . . . . . . . . . . . . . . . . . 127 x i Page A.l Histograms of intensity levels for each colour plane and for the entire picture for the picture GARDEN3 134 A.2 Histograms of intensity levels for each colour plane and for the entire picture for the picture FACE 135 A.3 Histograms of intensity levels for each colour plane and for the entire picture for the picture HOUSE 136 A.4 Histograms of intensity levels for each colour plane and for the entire picture for the picture TEST PATTERN . . '. 137 A. 5 Histograms of intensity levels for each colour plane and for the entire picture for the picture BUILDING . . . . 138 B. l Correlation coefficient in the X direction for the pictures FACE and HOUSE 140 B.2 Correlation coefficient in the X direction for the pictures TEST PATTERN and BUILDING . 141 . B...3 Correlation coefficient in .the Y . . d i r e c t i o n . f o x the pictures FACE and HOUSE 142 B.4 Correlation coefficient in the Y direction for the pictures TEST PATTERN and BUILDING 143 1.5 Correlation coefficient in the X direction for the pictures FACE and HOUSE . . . . . . . 144 B.6 Correlation coefficient in the X direction for the pictures TEST PATTERN and BUILDING . . . . . . . . . . . , 145 B.7 Comparative f i t of separable and non-separable model to estimated diagonal spatial correlation coefficient for the pictures TEST PATTERN and BUILDING . 146 B.8 Correlation coefficient in the wavelength direction, assuming stationarity, for the pictures HOUSE,.TEST PATTERN and BUILDING . . . . . . . . . . . . 147 D.1 Histograms of Fourier samples for the picture FACE . . . 155 D.2 Histograms of Fourier samples for the picture FACE . . . 156 LIST OF TABLES Table Page 2.1 Definition of wavelengths 9 3.1 Correlation parameters a, 8 and y and closeness of exponential model f i t to observed data 27 3.2 Comparative closeness of the f i t of a separable model and a non-separable model in the diagonal spatial direction 31 3.3 Comparative closeness of the f i t of a separable and a non-separable model in the x-X direction 33 3.4 Comparative closeness of the f i t of the single-exponential and double-exponential models in the spatial directions and correlation parameters for the pictures GARDEN1 and GARDEN3 36 5.1 Quantization errors as a function of the number of bits for uniform and non-uniform optimum quantizers . . 54 5.2 S/N ratio -as -a function of -the -average number of b.o.p.e. with and without quantization 55 6.1 S/N predicted and computed when only the D.C. component was transmitted . . . . . 64 6.2 Bit allocation for the picture GARDEN1 for 1, 2 and 3 b.p.p.e. and for a 6x6x6 sub-picture size 69 6.3 Bit allocation for the picture FACE for 1, 2 and 3 b.p.p.e. and for a 6x6x6 sub-picture size 70 6.4 Estimated and actual normalized variances of the Fourier samples transmitted for 3 b.p.p.e. for the picture GARDEN1, sub-picture size 6x6x6 . . . . . . 71 6.5 Estimated and actual normalized variances of the Fourier samples transmit; :ed for 3 b..p.p.e. for the picture FACE, Sub-picture size 6x6x6 72 6.6 Bit allocation for the picture GARDEN1 for 1, 2 and 3 b.p.p.e. and for an 8x8x6 sub-picture size 73 6.7 Bit allocation for the picture FACE for 1, 2 and 3 b.p.p.e. and for an 8x8x6 sub-picture size 74 6.8 Rank of (a) estimated, (b) actual variances of the Fourier samples for the picture FACE and a 6x6x6 sub-picture size . . . . . . . . . 79 x i i i Page 6.9 Ratio of estimated variances to actual normalized variances for the picture GARDEN1 and for a 6x6x6 sub-picture size . . 81 6.10 Normalized difference between (S/N) predicted by actual variances and computed without quantization of the oomponents . . . . . . . . 84 6.11 Normalized difference between actual S/N ratio and S/N ratio predicted from the estimated variances of the Fourier samples 85 6.12 Normalized difference between computed S/N ratio and S/N ratio predicted by actual variances 87 7.1 S/N ratios in the 16x16x16 case, using the adapted quantizer and 2.75 b.p.p.e., and normalized difference between computed S/N ratio and S/N ratio predicted by actual variances . . . . . . . . . . . . . . . . . . . . . . 91 7.2 Measured S/N ratio obtained when the pictures are processed using the variances estimated from the simple exponential model (2.75 b.p.p.e., 16x16x16). Measured S/N ratio ob-tained when the pictures are processed using the actual variances of the Fourier samples (2.75 b.p.p.e., 16x16x16) . 97 7.3 Bit allocations obtained (a) by using the estimated variances, (b) by using the actual variances of the Fourier samples i n the plane w = 1 101 7.4 Distribution of the categories of sub-pictures i n the picture FACE . 106 7.5 Average correlation parameters for each category of sub-picture for the picture FACE . 106 7.6 S/N ratios obtained by transmitting 3 b.p.p.e. transform encoded pictures on a noisy BSC channel 109 7.7 Mean-square errors and S/N ratio due to channel noise on ( the PCM transmission of the original data 112 A.l Mean and Standard deviation of the brightness of the source pictures . . . . . . . . . . . . . . . 132 A.2 Mean and Standard deviation of the brightness for each X^. . 133 xiv ACKNOWLEDGEMENT I would like to thank my supervisor, Dr. R.W. Donaldson, for his encouragement and assistance during the course of this thesis. I also wish to thank Mr. D. Wasson for his comments and suggestions during the preparation of the manuscript. My thanks also go to Mr. M. Koombes for his technical assistance and to Mrs. V. Walker for her efficient typing of the thesis. I also wish to acknowledge the financial assistance received from the Canada Council. xv ' : • I INTRODUCTION 1.1 M o t i v a t i o n Because o f t h e g r o w i n g need f o r image t r a n s m i s s i o n and s t o r a g e and b e c a u s e o f v e r y r a p i d advances i n h a r d w a r e and s o f t w a r e t e c h n o l o g y , i n t e r e s t i n s o p h i s t i c a t e d d i g i t a l image p r o c e s s i n g t e c h n i q u e s has grown c o n s i d e r a b l y d u r i n g r e c a n t y e a r s . I n p a r t i c u l a r , i n t e r e s t i n c o l o u r images o r t i m e - v a r y i n g images i s r a p i d l y i n c r e a s i n g . E a r l y redundancy r e d u c t i o n t e c h n i q u e s made use o f c o r r e l a t i o n s between p i c t u r e e l e m e n t s o f one l i n e o f monochrome s t i l l p i c t u r e s . Two-d i m e n s i o n a l p r o c e s s i n g t e c h n i q u e s w h i c h used c o r r e l a t i o n s i n b o t h h o r i -z o n t a l and v e r t i c a l d i r e c t i o n s were t h e n i n v e s t i g a t e d . A s t i l l c o l o u r p i c t u r e U ( x , y , X ) , where U i s t h e image i n t e n s i t y , i s a f u n c t i o n o f t h r e e v a r i a b l e s ; x and y a r e t h e s p a t i a l v a r i a b l e s and X i s the l i g h t w a v e l e n g t h ( c o l o u r ) . A b l a c k and w h i t e t i m e v a r y i n g p i c t u r e i s a t h r e e -d i m e n s i o n a l p r o c e s s U(x,y , t ) ; t i s t h e t i m e d i m e n s i o n . I t i s known t h a t t h e c o r r e l a t i o n between c o n s e c u t i v e frames o f a s e t o f t i m e - v a r y i n g p i c t u r e s i s i m p o r t a n t , t h e same remark i s t r u e f o r a d j a c e n t c o l o u r p l a n e s o f a c o l o u r p i c t u r e sampled i n t h e c o l o u r d i m e n s i o n . E f f i c i e n t c o d i n g o f s u c h p i c t u r e s w o u l d make u s e o f c o r r e l a t i o n s i n t h e t h i r d d i m e n s i o n (X o r t ) . A most p r o m i s i n g scheme i n terms o f b a n d w i -ith r e d u c t i o n i s t r a n s f o r m e n c o d i n g , w h i c h was i n t r o d u c e d r e l a t i v e l y r e c e n t l y . R e s u l t s o b t a i n e d on t w o - d i m e n s i o n a l d a t a h ave been p u b l i s h e d . T r a n s f o r m e n c o d i n g o f t h r e e - d i m e n s i o n a l d a t a , a l t h o u g h d i s c u s s e d , has n o t r e a l l y been i n v e s -t i g a t e d . The p u r p o s e o f t h i s t h e s i s i s t o c o n s i d e r t h r e e - d i m e n s i o n a l t r a n s f o r m c o d i n g o f c o l o u r s t i l l p i c t u r e s , as w e l l as t i m e - v a r y i n g monochrome moving p i c t u r e s . . 2. 1.2 Reviews of Relevant Work by Others: This section summarizes relevant progress to date in picture coding. Performance i s assessed i n terms of the average number of bits per picture element (b.p.p.e.) necessary to reconstruct a "good quality" picture. For the sake of comparison, standard PCM transmission of a monochromatic picture requires approximately 7 b.p.p.e. II]. PCM trans-mission of the Y, I and Q components of a colour picture requires 14 b.p.p.e. [2], The DPCM transmission of monochromatic pictures requires approximately 3 to 4 b.p.p.e. [3] and for colour pictures 4 to 5 b.p.p.e. [4]. v The concept of linear transformation and block quantization was introduced by Huang and fTchultheiss 15]. Typical results of the application of this technique to monochromatic pictures have been reported by Habibi and Wintz [6]. They used the Karhunen-Loeve, Fourier and Hadamard transformations and block quantization. As few as 0.5 b.p.p.e. with the Karhunen-Loeve transformation were used for a strongly correla-ted picture; 2 b.p.p.e. were required for the other transformations and a more general type of data. Wintz has summarized in [7] a l l published results on transform encoding of monochromatic data up to July 1972. The conclusion was that for a moderate detail monochrome picture, approximately 2 b.p.p.e. seem to be required for the two-dimensional transform encoding. i Gronneman [2] investigated the effect of low-pass f i l t e r i n g on the three basic components of a colour picture, reaching an average of 5.5 b.p.p.e. Pratt [8,9] applied two-dimensional transform encoding on three basic components of a colour picture (R,G,B or Y,I,Q or others). 3. In a very s p e c i f i c case, using the Karhunen-Loeve transformation and threshold sampling on the Y component and the Hadamard transformation on I and Q components, he used as few as 1.75 b.p.p.e. For the more e a s i l y implemented Four i e r and Hadamard transformations, 3.75 b.p.p.e. were used. More recently P r a t t [10] employed the Slant transform, using 3 b.p.p.e. The use of the c o r r e l a t i o n e x i s t i n g i n the t h i r d dimension was inv e s t i g a t e d by P r a t t [9], who proposed the replacement of the R,G,B components with Karhunen-Loeve components to obtain an optimum energy compaction. However, no estimation i n terms of b.p.p.e. required, was done. Rubinstein and Limb i n [11],[12], i n v e s t i g a t e d the s t a t i s t i c a l dependence between three components of colour video s i g n a l s . They reported as few as 0.25 to 0.5 b i t s per luminance sample to code the chrominance s i g n a l s . To our knowledge, the only r e s u l t s of the a c t u a l a p p l i c a t i o n of three-dimensional encoding were published by P.J. Ready and P.A. Wintz 113]. They proposed the use of the Karhunen-Loeve three-dimensional transform encoding f o r m u l t i s p e c t r a l imagery data. Their published r e -s u l t s show that the three-dimensional system allows a reduction by approximately h a l f of the data r a t e , compared to the two-dimensional system f o r the same s u b j e c t i v e l y acceptable d i s t o r t i o n and f o r the set of p i c t u r e s they used. To our knowledge no r e s u l t s on the three-dimen-s i o n a l transform encoding other than i n the above-mentioned references [9, 13] have been published to date. The e f f e c t of d i g i t a l channel e r r o r s on the PCM transmission of p i c t u r e s received some atten t i o n . T.S. Huang and M.T. Chikhaoui [14] compared the e f f e c t of a d d i t i v e Gaussian noise and BSC d i g i t a l channel errors r e s u l t i n g i n the same S/N r a t i o , on monochromatic p i c t u r e s . Observers preferred the d i g i t a l e rrors when the S/N r a t i o exceeded 15 dB. 4. For a lower S/N ratio the picture transmitted over a noisy BSC channel were considered of lower quality. Pratt [9,15] studied the effect of d i g i t a l channel errors on the PCM transmission of various colour compo-nents. He concluded that the least damage occurs when R,G,B components are used. Wintz [7] published some results on the subjective effect of d i g i t a l channel errors on transform encoding of monochromatic pictures. No experimental results have been published concerning the effect of d i g i t a l channel errors on three-dimensional transform encoded pictures. 1.3 Scope of the Thesis The transform encoding process operates in the following way. The source data is transformed by a linear transformation. Some trans-form samples are rejected according to a quality criterion, those retained are quantized, digitized and either transmitted or stored. These opera-tions are based on the a-priori estimated s t a t i s t i c s of the transform samples. The received samples are D/A converted and inverse transformed to yield a reconstructed version of the original picture. This thesis considers three-dimensional transform encoding. Many experimental results are presented. Colour pictures w i l l be used as source data for most of the experiments and time varying pictures for a smaller number. It i s an almost s t r i c t l y mathematical study of colour pictures, in the sense that almost complete abstraction of the human observer i s made, up to the point where the pictures are displayed for subjective assessment. Abstraction is made of the theory of tristimulus human vision. The colour dimension w i l l be sampled through non over-lapping f i l t e r s , the number of which are a r b i t r a r i l y chosen. It is clear, however, that the results can be adapted to three-component colour p i c t u r e s . I t i s important to note that the recording colour films and supposedly the author, who made the subjective evaluation, have t r i s -timulus p r o p e r t i e s . The Signal-to-Noise r a t i o (S/N) pr o p o r t i o n a l to the logarithm of the normalized mean square e r r o r between processed and o r i g i n a l p i c t u r e i s used as the primary q u a l i t y c r i t e r i o n , i n the sense that a processed p i c t u r e r e s u l t i n g i n a higher S/N r a t i o i s assumed to be of better subjective q u a l i t y . In general, subjective q u a l i t y seems to be a monotonically increasing function of the S/N r a t i o . The Fourier transformation w i l l be used i n the processing of colour p i c t u r e s because of easy implementation. Since the Hadamard trans-formation operates only on tensors whose dimensions are a power of two, i t w i l l not be applied to colour p i c t u r e s i n t h i s thesis since the dimension of the blocks i n the colour dimension i s 6. Emphasis w i l l be on the p r e d i c t i o n of the performance of the transform encoding process. This p r e d i c t i o n i s based on the s t a t i s t i c a l model used f o r a three-dimensional p i c t u r e . 1.4 Outline of the Thesis In chapter 2, the colour image data a c q u i s i t i o n system i s described. The c h a r a c t e r i s t i c s of the equipment used i n the d i g i t i z a t i o n process are defined. The o r i g i n a l colour source data used i n the the s i s i s presented. Chapter 3 i s devoted to the measurements of the s t a t i s t i c s of the o r i g i n a l data. F i r s t and second order s t a t i s t i c s are estimated. Some models of the auto c o r r e l a t i o n function of three-dimensional colour p i c t u r e s are presented. 6 . In chapter 4, the theory of three-dimensional F o u r i e r transform encoding i s presented. Using a simple s t a t i s t i c a l model f o r a three-dimensional p i c t u r e , performance i s estimated and compared to that of a two-dimensional transform encoding system. Chapter 5 considers the problem of quantization of the Fouri e r samples. The b i t a l l o c a t i o n algorithm i s chosen and the quantizers are ; chosen on the basis of the s t a t i s t i c s of the Fouri e r samples. The quan-t i t a t i v e e f f e c t of quantization i s evaluated and performance i s , from then on, evaluated as a S/N r a t i o function of the average number of b i t s per p i c t u r e element. In chapter 6, many experimental r e s u l t s on the three-dimensional Fourier transform encoding of colour p i c t u r e s are presented. T h e e f f e c t of using various .sub-picture s i z e s and b.p.p.e, i s considered. In chapter 7, ways to improve the performance and the mathema-t i c a l p r e d i c t i o n of the performance of the Fouri e r transform encoding system are presented. An adaptive system i s in v e s t i g a t e d . The e f f e c t of d i g i t a l channel errors i s studied. In chapter 8 , the r e s u l t s are applied to time varying mono-chromatic p i c t u r e s . Fourier and Hadamard transformations are compared. F i n a l l y , chapter 9 contains a summary of the r e s u l t s obtained and some recommendations f o r future research. 7. I I COLOR IMAGE PROCESSING SYSTEM The d i g i t a l color image data was obtained from a c o l o r trans-parency sampled along two s p a t i a l dimensions and one c o l o r dimension. In order to be able to define the q u a l i t y of the o r i g i n a l data i t i s necessary to define the type of equipment used i n the d i g i t i z a t i o n process. 2.1 Scanning Equipment: The scanning system i s represented on F i g . 2.1. 2.1.1 F l y i n g Spot Scanner - Phosphor: A computer c o n t r o l l e d f l y i n g spot scanner displays a s p a t i a l g r i d of 256 x 256 points. With the s e t t i n g used, 7 l i n e s per m i l l i m e t e r were scanned on the o r i g i n a l s l i d e . A higher s p a t i a l r e s o l u t i o n i s p o s s i -b l e , but was avoided because of the increase i n the time required for the transform encoding process. The s i z e of the spot was kept to the minimum po s s i b l e . The brightness of the spot was kept low enough to prevent the appearance of a halo s u f f i c i e n t l y l a r ge to increase the spot s i z e . '~ The s p e c t r a l energy d i s t r i b u t i o n of the type 203 phosphor i s shown i n F i g . 2.2. To our knowledge, t h i s phosphor was the c l o s e s t a v a i l -able approximation to white; white implies a f l a t s p e c t r a l energy d i s t r i -bution. The energy emitted i n the low frequency (red) part of the v i s i b l e spectrum seems to be very low. A Nova Computer controls the scanner through a 12 b i t D/A i n t e r f a c e . The f l y i n g spot scanner i t s e l f i s manufactured by Constantine Engineering Laboratories Company, Mahwah, N.J. 8 . D/ CONVE A RTER DEFLE CIRCU CTION ITS MINICOMPUTER PROGRAM---i CRT NOVA A/D CONVERTER Transparency Filter PHOTOMULTIPUER Lens U Lens 12 F i g . 2 . 1 Experimental arrangement used to scan 2.1.2 F i l t e r s : A set of interference f i l t e r s No. 6469 manufactured by Optics Technology Inc., Palo A l t o , C a l i f o r n i a , was used f o r quantization along the wavelength dimension. This s et included 6 low-pass and 6 high-pass f i l t e r s with c u t - o f f frequencies separated by 50 nm. Combinations of these f i l t e r s allow formation of 6 band-pass f i l t e r s whose transmission c h a r a c t e r i s t i c s appear i n F i g . 2.3. The number of sampling points i n the color dimension was f i x e d by the a v a i l a b i l i t y of the set of f i l t e r s and the photomultiplier s e n s i t i v i t y . A higher number of f i l t e r s would have decreased the energy i n each sampled band. The brightness of the spot would have had to be increased, r e s u l t i n g i n an increased halo which would have decreased the s p a t i a l r e s o l u t i o n . The transmission c h a r a c t e r i s t i c s of the f i l t e r s , since they are of interference type, depends somewhat on the angle of the i n c i d e n t l i g h t . Therefore, the f i l t e r s are s i t u a t e d i n the system at a place where the aiigle of incident l i g h t with the axis i s small. I t i s important to note that the f i l t e r s are s i t u a t e d i n the system at the same place, whether the system i s used to scan or to di s p l a y . Throughout the t h e s i s , wavelengths are defined as i n Table 2.1. . Wavelength Number COLOR Wavelength Range, nanometers XI V i o l e t 400-450 X2 Blue 450-500 .... X3 Green 500-550 X4 Yellow 550-600 X5 Orange 600-650 X6 Red 650-700 Table 2.1 D e f i n i t i o n of Wavelengths 10. 2.1.3 Photomultiplier: An RCA type S - l photomultiplier was used. I t s s e n s i t i v i t y appears i n F i g . 2.4. 2.2 Scanning Process: A g r i d of 256 x 256 points was displayed on the f l y i n g spot scanner tube. Each point was focused through a c o l o r f i l t e r and lens L l ( F i g . 2.1) onto the transparency. Lens L2 focused the point from the transparency onto the f r o n t surface of the photomultiplier. The photo-m u l t i p l i e r output was integrated, sampled, quantized to 8 b i t s and stored on IBM compatible magnetic tape. Because of the p a r t i c u l a r responses of the phosphor and photo-m u l t i p l i e r ( F i g . 2.2 and F i g . 2.4), the response of the system was not i d e n t i c a l i n each color. Consequently a blank transparency was scanned through the color f i l t e r g i v i n g the highest response (550 nm - 600 nm) , using the maximum poss i b l e brightness s e t t i n g without s a t u r a t i o n . This data was stored on tape. Six Ektachrome transparencies were then scanned, and the blank p i c t u r e data was used to restore each c o l o r plane. To scan one color plane and store i t on tape required approximately 10 seconds. 2.3 Display Process: The data was displayed using the system i n F i g . 2.5. For each c o l o r plane, each point displayed was i n t e n s i f i e d f o r a time s u f f i c i e n t to compensate f o r the n o n - f l a t response of the phosphor. The o r i g i n a l r e s u l t s were recorded on Ektachrome c o l o r f i l m f o r • - .43 s l i d e s . Kodak paper hardcopies are shown i n t h i s t h e s i s . These hard-copies should be viewed at a distance of approximately 6 to 10 times t h e i r . s i z e . 90-80-: 70-60 50-c CL> O h N .8 .18 40' c JO 20' 10 XI \ / A5 /'"•>, Kl A3 f N . / ^ - ^ \ l •\ A " \ J X b 1 1 1 1 T 1 1 , 1 \ < ' ii : i . 1 1 1 1 1 1 1 1 1 1 ! ' • i • • i ' i i i i i .... , 1 1 1 1 1 1 1 1 1 I 1 1 i i i i i t i i i l I i ti 1 1 1 1 1 1 | 1 | 1 ' ; s ! « ! J J i • 1 I 1 1 1 1 1 1 1 1 i • i • I 1 i i i » 1 / i .' i j 1 i i \ 1 1 1 f 1 1 1 1/ » i » » » / \ \ V \ 1 / / / / / / f X * \ / \ \ \ 350 400 450 500 550 600 650 700 nanometers Fig. 2.3 Filters transmission characteristics. 300 400 500 600 700 nanometers Fig. 2.4 Photomultiplier sensitivity. D/A CONVERTER DEFLECTION CIRCUITS XEROGRAM MINICOMPUTER NOVA /7/ter Film N lens Z.7 Fig. 2.5 Experimental arrangement used to display a picture ts) 13. 2.4 O r i g i n a l Image Data: F i g . 2.6 shows hard copies of s i x images which were scanned and then displayed. These pictures were chosen f o r the following reasons: Pictures 2.6 a) and 2.6 b) (Gardens) provide high s p a t i a l d e t a i l and areas having s p e c i f i c narrow bands of c o l o r s . P i c t u r e 2.6 c) (Face) i s low i n s p a t i a l d e t a i l . A face i s frequently used as reference because i t i s the most l i k e l y to be transmitted over a picturephone, and f o r evaluation of f l e s h tone r e n d i t i o n . P i c t u r e s 2.6 d) and 2.6 f) (House and Building) have low color d e t a i l , constant blue sky and high regular s p a t i a l d e t a i l . P i c t u r e 2.6 e) (Test Pattern) w i l l be used as a t e s t f o r color q u a l i t y of processed p i c t u r e s . This set of p i c t u r e s can be considered as being of "good q u a l i t y " , compared to previously published c o l o r data, f o r the following reasons: i ) I t provides a large v a r i e t y of data, i i ) S p a t i a l r e s o l u t i o n i s very good. Small d e t a i l s are present, i i i ) Some pictures have very contrasted areas: very b r i g h t parts which are very close to dark pa r t s , i v ) Color r e n d i t i o n , although i t may appear to lack of s a t u r a t i o n , i s very close to n a t u r a l c o l o r s . The o r i g i n a l s l i d e s from which the p i c t u r e s appearing i n t h i s t h e s i s are hardcopied are of b e t t e r q u a l i t y than the copies. 14.a Throughout the thesis, experimental results w i l l be presented in the following way. PICTURE a) PICTURE c) PICTURE e) PICTURE b) PICTURE d) PICTURE f) Fig. 2.6 a) GARDEN1 b) GARDEN3 c) FACE d) HOUSE e) TEST PATTERN f) BUILDING V ORIGINALS 15. I l l DATA STATISTICS 3.1 Introduction The importance of knowing the f i r s t and second order s t a t i s t i c s of the data, i n the s p e c i f i c case of transform encoding, i s explained below. The t h e o r e t i c a l study of transform encoding i n the following chapter w i l l provide a d d i t i o n a l motivation. The f i r s t order s t a t i s t i c s of the brightness of the p i c t u r e pro-vide important information concerning the most important transform sample, namely, the D.C. component. A minimum mean square error transform encoding scheme requires the knowledge of the second order s t a t i s t i c s of the data to be processed. Even f o r a sub-optimum transformation, f i l t e r i n g and quanti-zation of the transformed data samples requires knowledge of the second order s t a t i s t i c s . 3.2 F i r s t Order S t a t i s t i c s : The source data i s a three-dimensional d i s c r e t e process U(x,y , X ) where x and y are the s p a t i a l dimensions, X the.colour or wavelength d i -mension and U i s the brightness. The frequency of occurrence f v (u) of i each l e v e l of brightness f o r each X^ was estimated as follows: (3.1) N = 256 where M^^(u) i s the number of times that the brightness U equals the value u f o r X = X ^ . The frequency of occurrence of the brightness f ( u ) , f o r the en t i r e p i c t u r e was also computed: 6 f(u) = [ I f x . ( u ) ] /6.0 (3.2) i = l 1 16. (u) and f(u) are di s c r e t e functions. For s i m p l i c i t y of presen-t a t i o n , only t h e i r envelopes are shown i n F i g . 3.1 f o r the p i c t u r e GARDEN1 and i n Appendix A for, the rest of the data ( F i g . A1-A5) . I t i s important to have a model for the frequency d i s t r i b u t i o n of the brightness of the p i c t u r e . As i t w i l l be shown i n the next chapter, the D.C. component of the Fourier transform of each block has a d i s t r i b u t i o n s i m i l a r to that of the brightness of the o r i g i n a l data. This component i s the most important, i n the sense of the mean square er r o r between processed and o r i g i n a l p i c t u r e . Others [16,17], have assumed the frequency d i s t r i b u t i o n of the brightness to be uniform or Gaussian, at l e a s t f o r monochromatic p i c t u r e s . The Gaussian d i s t r i b u t i o n was rejected by us because i t would represent an u n r e a l i s t i c a l l y higher p r o b a b i l i t y f o r very low l e v e l s of brightness (and negative l e v e l s ) . For most of our pictu r e s the d i s t r i b u t i o n was observed to be s i m i l a r to a Maxwell d i s t r i b u t i o n with density function x 2 f l > 0 f « ( u ) = ^rVf"x2e u<*> w h e r e u<*> ={o^ x < o ( 3 * 3 ) This s i m i l a r i t y of (3.3) to the data is. apparent i n F i g . 3.2 where the frequency of occurrence of brightness l e v e l s f o r the p i c t u r e s GARDEN1 and HOUSE i s compared with that of a Maxwell d i s t r i b u t i o n . The Maxwell d i s t r i b u t i o n was pre f e r r e d to a d i s t r i b u t i o n l i k e the Rayleigh d i s t r i b u t i o n , because of the shape of the curve at the o r i g i n . Very dark parts are very improbable, which i s not w e l l modelled by a Rayleigh d i s -t r i b u t i o n . The Maxwell d i s t r i b u t i o n has the advantage that i t can be defined by one parameter, a. Mean and variance are dependent; when the mean increases the variance increases, as with the source data. Unfor-tunately, f o r p i c t u r e s l i k e HOUSE or TEST PATTERN high l e v e l s of brightness 17. F i g . 3.1 Histograms of i n t e n s i t y l e v e l s f o r each colour plane and f o r the e n t i r e p i c t u r e f o r the p i c t u r e GARDEN1 18. GARDEN1 B I V 64.0 isa.D INTENSITY LEVEL 256.0 HOUSE B ' W 64.0 128.0 INTENSITY LEVEL 258.0 S >-o UJ ZD o UJ— MRXWELL DISTRIBUTION 3.0 64.0 128.0 192.0 INTENSITY LEVEL 25B.0 MAXWELL DISTRIBUTION T r 3.0 G O 128.0 192.3 INTENSITY LEVEL 1 256.0 Fig. 3.2 Histograms of i n t e n s i t y l e v e l s and Maxwe?l d i s t r i b u t i o n . 19. are somewhat more probable than predicted by a Maxwell distribution having the same variance as the data. (See Appendix A). 3.3 Second Order Sta t i s t i c s: 3.3.1 Introduction: In order to analytically study various picture coding algorithms i t i s virtu a l l y imperative to use a wide-sense stationary model for the source data. Wide-sense stationarity implies, for instance, that the f i r s t order st a t i s t i c s and the correlation function of the data should not depend on the spatial dimension x. Fig. 3.3 shows the estimated mean n^.(x) (3.4) as a function of x for each X^ averaged over the six pictures, and the estimated standard deviation a-y (x) (3.5) of the brightness i V x ) = S i , ! ! V ' ^ i ) <3-*> k-1 j=l , M N 2 i 1 m k=l j-1 1 (3.5) N = 256, M = 6. is the brightness of the k t h picture. Considering the colour dimension, the following mean of the brightness as a function of X averaged over the six pictures i s shown in Fig. 3.4 (curve denoted AV). - M N N n(*> r^r I I I Ufc (Xi.yj . x ) (3.6) k=l j=l i=l Those parameters (3.4, 3.5, 3.6), measured on a limited set of 6 samples pictures, are relatively constant. Considering the fact that a colour processing system i s l i k e l y to process a great variety of different pic-tures, the assumption of stationarity becomes acceptable. In the present study, the processing system w i l l be adapted to a specific type of picture, the type being defined by the correlation 2 0 . o.o ENSEMBLE AVERAGE —I : 1 64.0 12a.o X DIMENSION -1 192.0 —1 256.0 0.0 ENSEMBLE AVERAGE T 64.0 128.0 X DIMENSION T : 1 192.0 256.0 F i g . 3 .3 Mean and Standard de v i a t i o n of the brightness as a function of the s p a t i a l dimension x -1 1 r 375.0 425.0 475.0 525.0 WAVELENGTH Fig. 3.4 Mean of the brightness as a function of the wavelength f o r each p i c t u r e and averaged over the s i x p i c t u r e s . 21. along the three dimensions x, y and X. Each p i c t u r e of the source data s e t constitutes one sample of a type of p i c t u r e . E r g o d i c i t y w i l l be assumed and the s t a t i s t i c s f o r the type of p i c t u r e w i l l be deducted from that sample. In F i g . 3.4, the average of the brightness as a function of X f o r each p i c t u r e i s shown. I t must be noted that i n some p i c t u r e s some colours are more predoiAinant than other colours (blue i n the sky of p i c -ture HOUSE for instance). . . 3.3.2 Estimation of Picture S t a t i s t i c s : The following c o r r e l a t i o n c o e f f i c i e n t s between consecutive p i c t u r e elements, along the s p a t i a l dimensions were f i r s t estimated as follows: N N I I Ax,Ay,AX a x - j 1 i = l where: [ U ( X i + Ax, Y j + Ay, X k) - n ^ ] (3.7) n x = f z f f u ( X i , y j , x k ) (3.8) k j = l i = l i N N and: _ ? _ 1 Ak N 1-1 i = l (3.9) F i g . 3.5 shows: p f o r Ay = 0, Ax = 0,1,2,...,14 f o r X = X j , X 2 , X 3 , . . . , X g f o r the picture GARDEN1 and GARDEN3. F i g . 3.6 shows: p f o r A x = 0, Ay = 0,1,2,...,14 f o r X = X j , X 2 , X 3 , . . . , X g f o r the same p i c t u r e s . The same functions f o r the re s t of the p i c t u r e s appear i n Figs. B1-B4 i n Appendix B. Except f o r the p i c t u r e BUILDING which i s mainly blue, t h i s c o r r e l a t i o n c o e f f i c i e n t i s r e l a t i v e l y indepen-dent of X. F i g . 3.6 Correlation coefficient in the spatial direction Y for the pictures GARDEN1 and GARDEN3 24. The following c o r r e l a t i o n c o e f f i c i e n t , along the colour dimen-si o n , was then estimated as follows: 1 1 N N PXi, AX = a ~ N2" I I [ U ( x 1 > y j , X k ) - n X k ] [ U ( x ,y.,X k + A x) A k » A A ° X k Xk+AX N i = l j = l J i J ~ n X k + A x l < 3' 1 0> where a n a o"xk a r e defined i n 3.8 and 3.9 r e s p e c t i v e l y . This c o e f f i -c i e n t (3.10) i s p l o t t e d on F i g . 3.7 f o r AX = 1,2,..., 5 f o r X^ = Xj ,X2,X3,...,X^ f o r the pic t u r e s GARDEN1 and GAEDEN3. The r e s t of the data appears i n F i g s . B5,6 i n Appendix B. This c o r r e l a t i o n c o e f f i c i e n t depends very much on X. Pictures having very s p e c i f i c colours, such as the TEST PATTERN and the BUILDING have a low-co r r e l a t i o n c o e f f i c i e n t . For the r e s t of the p i c t u r e s , the c o r r e l a t i o n c o e f f i c i e n t i n the colour dimension i s r e l a t i v e l y high. One can a n t i c i p a t e bandwith reduction by use of e f f e c t i v e source coding techniques. 3.4 Choice of a Model: Previous experiments [6,18] have l e d to the adoption of a Gaussian f i r s t - o r d e r Markov f i e l d as a model f o r monochromatic p i c t o r i a l data. This model i s a t t r a c t i v e because of i t s a n a l y t i c s i m p l i c i t y . On the assumption that the p i c t o r i a l process i s s t a t i o n a r y and f i r s t - o r d e r Markovian, which means that the s t a t i s t i c s of a s p e c i f i c point depend only on the preceding point, and i f , moreover, i t i s Gaussian, then the auto-c o r r e l a t i o n function i s exponential, and the measured c o r r e l a t i o n f u n c t i o n looks d e f i n i t i v e l y exponential. Consequently the following model f o r the auto c o r r e l a t i o n function was used f o r monochromatic p i c t u r e s by Habibi and Wintz [6] and f o r monochromatic components of a colour p i c t u r e Y,I,Q or R,G,B [19]. R^ Y(Ax,Ay) - exp(-a|Ax|)exp(-BI Ay I) (3.11) 25. 26. S e p a r a b i l i t y , which means that the c o r r e l a t i o n f u n c t i o n can be expressed i n the following way i s another u s e f u l feature: R ^Ax.Ay) = (Ax) . R^Ay) (3.12) The closeness of the f i t of t h i s model and the s e p a r a b i l i t y w i l l be d i s -cussed i n the next s e c t i o n . Considering the colour dimension, i f the pict u r e s are assumed to be s t a t i o n a r y , the data shows that the auto-c o r r e l a t i o n function ca:. be considered of exponential type. (See F i g s . 3.10, B.8) Consequently, the following model f o r the a u t o c o r r e l a t i o n function of a colour p i c t u r e was adopted. R^Y^Ax.Ay.AA) == exp(-a|Ax|). exp (-13 | Ay | ) . exp(- Y|AX|) (3.13) The parameters a ,B,Y were estimated by l e a s t square f i t t i n g each exponential function i n the above expression, to the computed po i n t s . Results appear i n Table 3.1. The closeness of the f i t i s expressed by the number C: C = -10 log (e 2) (3.14) where e 2 i s the mean square e r r o r between computed points and f i t t e d curve; the l a r g e r C, the better the f i t . The best f i t i s p l o t t e d on the graphs of F i g s . 3.5, 3.6, 3.7 and on F i g s . B l , B2, B3, B4, B5, B6 i n Appendix B. 2 7 . Gl G3 H TP CORRELATION PARAMETER 0.088 0.191 0.106 0.064 0.111 0.079 0.048 0.047 0.069 0.054 0.042 0.071 0.018 0.017 0.173 0.085 0.069 0.166 23.86 23.55 15.96 23.04 22.38 17.93 29.35 31.56 29.70 27.18 31.53 19.43 35.49 46.69 12.66 15.36 19.43 13.41 Table 3.1 C o r r e l a t i o n parameters a, 8 and y and closeness of exponential model f i t to observed data. The v a l i d i t y of the above model can be challenged f o r the following reasons: 1) S e p a r a b i l i t y implies that the autocorrelation f u n c t i o n decreases more r a p i d l y i n the diagonal d i r e c t i o n than along the other s p a t i a l dim-ensions. A p r i o r i , t his does not seem to be reasonable, since the choice of s p a t i a l d i r e c t i o n s would seem to be a r b i t r a r y . However, i n many pi c t u r e s , the horizon, manmade and n a t u r a l l y occurring objects coincide with h o r i z o n t a l and v e r t i c a l p i c t u r e d i r e c t i o n s . 28. 2) The f i t to the computed points in the spatial directions is not very close in some cases. The actual correlation function of weakly corre-lated data seems to decrease faster than the exponential f i t for small displacements and more slowly for large displacements. This is p a r t i -cularly true for the pictures GARDEN1, GARDEN3 and BUILDING where a and g are larger than 0 . 0 6 . For the other 3 pictures the f i t t e d curves are closer to the computed points. In the following, different models w i l l be considered. 3.5 Non-Separable Model: For the remainder of the thesis,' a colour picture w i l l be con-sidered as a stationary process. Correlation coefficients w i l l be con-sidered as independent of X. For any displacement Ax, Ay or AX, the average (over X) correlation coefficient w i l l be considered. 3.5.1 Non-Separability in the Spatial Dimensions: The following correlation coefficient along the spatial diago-nal direction was estimated as follows: N N PAL = 'o^W I ^ { [U(x i,y j,X)- n][U(x i + AL, y j + AL,X)-n]} (3.15) i=l j=l where a and r\ are the standard deviation and mean of the brightness of the picture. Table 3.2 shows the closeness of the f i t of the two follow-ing models to the actual data. p = e~«|Ax| e-g|Ay| ( S e p a r a b i e ) (3.16) Ax, Ay PAx,Ay = e-((a.Ax)2 + ( 3.Ay ) 2 ) ± ( N o n _ s e p a r a b l e ) (3.17) The curves are shown in Fig. 3.8 for pictures GARDEN1 and GARDEN3, Fig. 3.9 for pictures FACE and HOUSE and i n Appendix B (Fig. B7) for the pic-tures TEST PATTERN and BUILDING. VO Fig. 3 . 8 Comparative f i t of separable and non-separable models to diagonal spatial correlation coefficients for the pictures GARDEN1 and GARDEN3, Fig. 3.9 Comparative f i t of separable and non-separable models to diagonal spatial correlation coefficients for the pictures FACE and HOUSE. 31. Closeness C Separable Non-separable Model Model Gl 19.53 24.24 G3 24.05 23.05 F 20.81 38.47 H 25.71 23.48 TP 28.03 19.92 B 22.56 16.78 Table 3.2: Comparative closeness of the f i t C(3.14) of a separable model and a non-separable model i n the diagonal s p a t i a l d i r e c t i o n . The non-separable model's f i t i s better only f o r the pict u r e s GARDEN1 and FACE. A l l of the other p i c t u r e s have many h o r i z o n t a l and v e r t i c a l patterns which make the c o r r e l a t i o n c o e f f i c i e n t higher i n those d i r e c t i o n s than i n the diagonal .direction. 3.5.2 S e p a r a b i l i t y of the s p a t i a l and colour dimensions: Some examples of the following c o r r e l a t i o n c o e f f i c i e n t (3.18) aru p l o t t e d on F i g . 3.10. N N p A x A X = o^N2" E I '.UU(x 1,y j , X ) - n ] [ U ( x i + Ax.y X+AX)-n]} (3.18). * i = l j = i for AX varying from 0 to 5 and f o r d i f f e r e n t values of the parameter Ax for the pictures GARDEN1, GARDEN3 and FACE, a 2 i s the variance of the brightness of the p i c t u r e . The closeness of a separable model (3.19) it. compared to the closeness of a non-separable model (3.20) i n Table 3.3. The separable function i s p l o t t e d on F i g . 3.10. = e-a|Ax| e-y|AX| ,-((aAx) 2+( YAX) 2)* pAx,AX 6 pAx,AX = 6 (3.19) (3.20) 33. Ax GARDEN1 Ax GARDEN3 Ax FACE SEPARABLE NON-SEPARABLE SEPARABLE NON-SEPARABLE SEPARABLE NON-SEPARABLE 0 29.93 29.93 0 31.65 31.65 0 32.61 32.61 1 28.09 26.53 3 25.67 24.00 1 31.07 29.64 3 26.81 20.16 6 27.39 25.06 3 31.57 24.46 6 30.34 22.46 10 22.60 31.56 6 32.84 22.51 14 21.87 27.59 12 32.47 24.32 Table 3.3: Comparative closeness of the f i t of a separable model and a non-separable model i n the x-A d i r e c t i o n . For the pi c t u r e FACE, the separable model i s always best. For the other two pictures the f i t of the non-separable model becomes bet t e r f o r large values of the s p a t i a l displacement (Ax > 6). 3.6 Double-Exponential Model: I t can be noted that the actual s p a t i a l c o r r e l a t i o n decreases f a s t e r than predicted by the separable exponential model f o r small d i s -placements and more slowly f o r l a r g e r displacements. This i s p a r t i c u l a r l y true f o r weakly cor r e l a t e d p i c t u r e s l i k e GARDEN1 and GARDEN3. (See F i g s . 3.11, 3.12). For GARDEN1 and GARDEN3 i t was po s s i b l e to obtain a b e t t e r f i t to the measured values, using the following models: PAx,Ay = ( e " a i | A x | + e"°2' A x' ) . ( e " 6 1 ' A y ' + e" 3* 1 A y 1)/4.0 (3.21) ; (Separable) o = ( e - K a l - A x > 2 + ( B l - A y > 2 ^ * + e ^ K a 2 - A x ) 2 + ( B 2 . A y ) 2 ] * w 2 0 Ax,Ay '' ' (Non-separable) (3.22) These models w i l l be re f e r r e d to as the double-exponential models. The closeness of the f i t of the separable model to the data i s compared i n Table 3.4 to the closeness of the f i t of the s i n g l e exponential model. The two models are pl o t t e d i n Fig s . 3.11, 3.12. I I 1 I I 1 1 a l 1 1 I 1 1 1 1 . 0 0 j ) 4.0 6.0 6.0 10.0 12.0 14.0 0.0 2.0 4.0 6.0 8.0 13.0 12.0 14.0 X DISPLACEMENT Y DISPLACEMENT Fig . 3.11 Comparative f i t of the single exponential model and the double exponential model in the spatial directions for the picture GARDENl 0.0 T 2.0 GARDENS A ESTIMATED FROM DATA - i 1— r 4.0 6.0 e.o X DISPLACEMENT 10.0 12.0 1 M.O GRRDEN3 A ESTIMATED FROM DATA 2.0 1 : r 4.0 G.O s.o Y DISPLACEMENT F i g . 3.12 Comparative f i t of the s i n g l e exponential model and the double exponential model i n the s p a t i a l d i r e c t i o n s f o r the picture GARDEN3 4*3 36. GARDEN1 GARDEN3 X Single Exponential Model 24.55 24.77 a = 0.088 a = 0.064 Double Exponential Model 37.58 36.05 ai = 0.286 a 2 = 0.021 ai = 0.229 a 2 = 0.003 Y Single Exponential MnHpl 24.32 25.57 0 = 0.191 8 = 0.111 Double Exponential Model 40.28 43.02 B 2 = 0.535 B 2 = 0.091 8 1 = 0.308 8 2 = 0.040 Table 3.4 Comparative closeness of the f i t of the s i n g l e -exponential and double-exponential models i n the s p a t i a l d i r e c t i o n s and c o r r e l a t i o n parameters f o r the p i c t u r e s GARDEN1 and GARDEN3 The non-separable double exponential model (3.22), provides an excelle n t f i t to the measured diagonal c o r r e l a t i o n f u nction of the p i c t u r e 'GARDENING = 43.24, compared to C = 29.38 f o r the separable double exponential model (see F i g . 3.13). For the p i c t u r e GARDEN3, there i s no s i g n i f i c a n t d i f f e r e n c e , C = 23.37 f o r the separable model, C = 22.83 f o r the non-separable model. 3.7 Conclusion The problem of choosing even a second order s t a t i s t i c a l model f o r a three-dimensional colour p i c t u r e i s d i f f i c u l t . I t appears that there are d i f f e r e n t types of colour p i c t u r e s . The simple separable c o r r e l a t i o n func-t i o n of exponential type i s a t t r a c t i v e because of i t s s i m p l i c i t y and i t w i l l be used f o r the mathematical study of our p i c t u r e coding algorithms. A more complex non-separable model provides a b e t t e r f i t to some pic t u r e s lacking of v e r t i c a l or h o r i z o n t a l features. For weakly c o r r e l a t e d data a model composed of the sum of exponentials c l o s e l y f i t s the data i n 0.0 GARDEN1 -r 2.0 i i r 4.0 6.0 8.0 X-Y DISPLACEMENT 10.0 12.0 H.O GRRDEN3 -—i 1 1 i 2.0 4.0 6.0 6.0 X-Y DISPLflCEMFNT 10.0 -1— 12.0 -1 14.0 Fig 3 13 Comparative f i t of the non-separable and separable double-exponential models in the spat ial diagonal direction for the pictures G A R D E N 1 and G A R D E N 3 . 38. the s p a t i a l dimensions. The i m p l i c a t i o n of using these more so p h i s t i c a t e d models on the transform encoding system w i l l be studied l a t e r i n t h i s t h e s i s . 39. IV THEORY OF TRANSFORM ENCODING 4.1 Introduction A general transform encoding system can be represented as shown i n F i g . 4.1. The source data i s transformed. Some transform domain sam-ples are then rejected i n accordance with some q u a l i t y c r i t e r i o n . The remaining samples are then d i g i t i z e d , transmitted or stored, D/A converted and then inverse transformed. SOURCE T RECONSTRUCTED PICTURE <£ DATA REDUCTION QUANTIZER COMMUNICATION CHANNEL OR DIGITAL STORAGE MEDIUM NOISE ERROR F i g . 4.1 Transform encoding system. " A n optimum transform encoding system, i n the sense of mean-square er r o r between processed p i c t u r e and o r i g i n a l p i c t u r e , has two main objectives [7]: 1) To provide uncorrelated samples that can be i n d i v i d u a l l y coded. 2) To pack the maximum po s s i b l e energy i n t o a reduced number of samples so that e f f i c i e n t reduction can be applied i n the transform domain. The Karhunen-Loeve transformation achieves the two goals mentioned above. Unfortunately, the computational algorithms are slow. The Fourier transform has been i n v e s t i g a t e d f o r the transmission of monochromatic pictures [6, 8,20 ] » and f o r the transmission of the 40. three components of a colour p i c t u r e [8]. Fast computational algorithms of the Fourier transform e x i s t [21,22]. J . P e a r l i n [23] demonstrated that, at long block length, the Fourier transform approximates the o p t i -mum Karhunen-Loeve transform i n performance. The Hadamard transform has been applied to the same type of data [24],[25]. Its main advantage i s an even f a s t e r computational algorithm. T h e o r e t i c a l l y i t performs b e t t e r than the F o u r i e r transform i n s p e c i f i c s i t u a t i o n s [26]. Since i t operates only on tensors whose dimensions must be a power of two, and since the s i z e of the blocks i n the colour dimension i s 6 i n t h i s t h e s i s , the Hadamard transform w i l l not be considered i n the present study of colour p i c t u r e s . However, i t s p o s s i b i l i t i e s i n the case of time-varying monochromatic p i c t u r e s , w i l l be investigated. Both the Fourier and Hadamard transforms are non-optimum i n that they do not always y i e l d uncorrelated samples. .Recently the Slant transform [10] has been introduced because i t seems to be more c l o s e l y f i t t e d to the s p a t i a l c h a r a c t e r i s t i c s of an image. Pratt [ 9 ] , introduced the idea of three-dimensional transform encoding by suggesting the replacement of the RGB components of a colour p i c t u r e by optimum Karhunen-Loeve components and then applying 2 dimensional transform encoding on each component. However, no extensive experimenta-t i o n has ever been done using the high c o r r e l a t i o n e x i s t i n g between colour planes for transform encoding. In t h i s chapter, the theory of three-dimensional F o u r i e r trans-form encoding w i l l be studied. The performance w i l l be analyzed and com-pared with the t h e o r e t i c a l performance of a two-dimensional Fourier trans-form encoding scheme. 41. F i l t e r i n g and quantization of the transform domain samples are l i k e l y to a f f e c t the q u a l i t y of the reconstructed p i c t u r e . These problems w i l l be considered i n the next chapter. 4.2 Theory of Three-dimensional Fourier Transform Encoding: To transform a three-dimensional d i s c r e t e tensor u(x,y,A) i s to decompose i t on a set of basis functions <j>, which, i n the case of the Fourier transform, are: *kim(x'y'x) = NTM" e x p ( _ ^? ( k x + w- e xp(- m X ) = N7M [ c o s ^ F + fy + f x ) 1 S I N 2 7 R ( - N X + i y + s x )] (4.1) where i = f-1 and N , M are the dimensions of the process ( N x N x M ) and k, £ = 0,1, . . . , N-1 and m = 0,1 M - l Consequently a tensor can be wri t t e n as: N-1 N-1 M - l u(x,y,X) = J I I \ l m ' \ l m (*,y*A) . (4.2) k=0 Z-0 m=0 where N-1 N-1 M - l V m = I I I U< X' y> X )'*kAm ( x ' ? ' X ) ( * - 3 ) x=0 y=0 X=0 If only nj.n2.m2 of the Fourier samples are kept, the recon-s t r u c t e d tensor w i l l be: nj-1 n ^ - l mi-1 u*(x,y,X) = J t I W W X > y ' X ) ( 4 ' 4 ) k=0 1=0 m=0 and the mean square error between o r i g i n a l and reconstructed tensor w i l l be: 1 N-1 N-1 M - l E 2 = N ^ ? E { I I I [u(x,y,X) - u*(x,y,X)] 2} x=0 y=0 X=0 42. N-1 N-1 M-l - £ - E { I I I Iu 2(x,y,X) - 2u(x,y,X).u*(x,y,X) x=0 y=0 X=0 + u* 2(x,y,X)]> r^-1 n 2 - l mj-1 - 4 ^ ( 0 . 0 . 0 ) - ^ E ! lg . ^ ( x . y . » » (4.5) In (4.5), ^(Ax,Ay,AX) i s the a u t o c o r r e l a t i o n function of the process u(x,y,X), u* 2(x,y,X) = u*(x,y,X).u*(x,y,X) and from (4.4): n j - l n 2 - l mj-1 u* 2(x,y,X) = I J I (x.y.X). k=0 1=0 m=0 n - 1 n„-l m^-1 j l l V)l'm'-\£m ( x- y' X ) ( 4 ' 6 ) k'=0 JL'=0 m'=0 Since the are orthogonal functions n j - l n 2 - l m-,.-l nz~^ mi~^-I I t u* 2(x,y,X) = I I I u 2 k £ m (4.7) x=0 y=0 X=0 k=0 £=0 m=0 Thus, (4.5) becomes: e 2 = W 0 ' 0 ' 0 ) " ra t X \ ° 2kAm '^ k=0 £=0 m=0 n 2 - l n 2 - l m 1-l (4.8) where _ o 2 \ •°klm = E { U k£m } The mean square e r r o r i s equal to the variance of the o r i g i n a l p i c t u r e minus the sum of the variances of the non r e j e c t e d F o u r i e r samples. In (4.8), vL^£m i s a, complex number. The variance of a complex number i s equal to the sum of the variances of i t s r e a l part and i t s imaginary part. The r e a l part of * s : 43. N-1 N-1 M-l W ak £ m = A. I I I u(x,y,A).cos 2TT ( | x + f y + | | x ) (4.9) x=0 y=0 X=0 where A = ^ R and i f a.,2 denotes the variance of the real part: N-1 N-1 N-1 N-1 M-l M-l . ° R 2 = A 2 I I I I I I cos 2 i ( | x + | y + | X ) . x=0 x'=0 y=0 y'=0 X=0 X'=0 cos 2T T ( | x* + | y ' + g X,).R(x,x*,y>y',X,X') (4.10) where R(x,x',y,y',X,X') = E{u(x,y,X).u(x',y',X')}. In the preceding chapter the following model was adopted: R(x,x«,y,y',X,X') = e^'*"*'!. e ^ ^ ' ' I . e"Y | X-A' [ ( 4 > u ) Using the following notations: N-1 N-1 P± (z,6,N) =1 I cos 2TT(±-(Z ± z'^.e" 0' 2 Z 1 (4.12) 1 z=0 z'=0 V and N-1 N-1 . . , | 0± (z,6,N) = I I sin 27r(i(z ± z')).e"° | z" z 1 (4.13) 1 „ =n „»=n . w N-1 = 1 I z 0 z' 0O R 2 and Oj 2 can be written as (4.14) °IZ = 2 P M ' ( B + A ) ( 4 ' 1 5 ) where A = P+Ca,x,N) .P+(B,y ,N) .P+(Y,X,M) - Q+(a,x,N) .Q+(8 ,y ,N) . P+(Y ,X ,M) . - 0+(a,x,N).P+(B,y,N).Q+(Y,X,M) - P+(a,x,N).Q+(8,y,N).0+(Y,X,M) (4.16) 44. and B = Pk(a,x,N).p-(g,y,N).p-(Y,X,M) - Qk(cx,x,N).Q-(g,y,N).p-(Y,X,M) - Q~(a,x,N).p-(B,y,N).Q-(Y,X,M) - Pr(a,x,N).Q-:(S,y,N).Q-(Y,X,M) (4.17) x. m From equation 4.8, i t is clear that reduction w i l l be applied in the transform domain by keeping only the n^ x n 2 x Fourier samples whose variances are the largest. In order to assess the performance of the trans-form encoding system, these variances must be computed from (4.10) or (4.14, 4.15, 4.16) and (4.17). These equations are rather complex and would require much computer time to calculate. The fact that the chosen model is separable and the Fourier transform is unitary allows the computa-tion of the variances to be executed in a much faster way. For one dimen-sion (or each dimension of the three-dimensional process) the vector of variances can be obtained from the diagonal of the transform of the covar-iance matrix. Variances for the three-dimensional process are then obtained by the multiplication of the three vectors. 4.3 Performance of a Three-dimensional Transform Processing System: This section indicates the performance that can be achieved by a three-dimensional transform processing system. It would be interesting to know how fast the mean square error decreases as the number of trans-mitted samples increases, and how much better is a three-dimensional pro-cessing system than a two-dimensional processing system operating on the same data. In the remainder of the thesis, the signal-to-noise ratio, S/N, w i l l be used as a measurement of processed picture quality: S/N dB = -10 log e 2 (4.18) 45. e2 where e 2 = i s the normalised mean square e r r o r between the o r i g i n a l and processed p i c t u r e , e 2 i s the actual mean square e r r o r and a 2 the variance of the o r i g i n a l p i c t u r e . The S/N r a t i o as a function of the number of transmitted samples for d i f f e r e n t values of the parameters a, 8, y and d i f f e r e n t s i z e s of pictures i s shown on F i g . 4.2. Two ways to assess the improvement from two-dimensional to three-dimensional processing are as follows: 1) The s p a t i a l dimensions of the p i c t u r e are constant. A two-dimen-s i o n a l system processing M separate N x N p i c t u r e s can be compared with a three-dimensional system processing one M x N x N p i c t u r e . In t h i s case the complexity of the processor increases i n the sense that the second sys-tem i s processing a l a r g e r number of elements at a time. 2) The complexity of the processor i s constant or more p r e c i s e l y , the t o t a l number of samples to be transformed i s constant. A two-dimensional system processing an N x N p i c t u r e can be compared to a three-dimensional system processing an N l x N l x M p i c t u r e where N x N = N l x N l x M. For example, considering the processing of time varying monochro-matic p i c t u r e s , a two-dimensional system would process separately each frame, and a three-dimensional system would process several frames together. The f i r s t case ( d i f f e r e n t complexity) i s shown on F i g . 4.2(a). The S/N r a t i o as a function of the number of samples i s p l o t t e d f o r a = B =0.06 (average value f o r the data) and f o r d i f f e r e n t values of y and f o r N = 8 and M = 6. This case would apply to 6 consecutive frames of a time varying process. Curve (1) represents the S/N r a t i o f o r a two-dimensional p i c t u r e (8 x 8) and curve (2) the S/N r a t i o f o r s i x i d e n t i c a l p i c t u r e s (same a and 8) transmitted using a two-dimensional Fourier transform encoding system. 46. The performance of a three-dimensional system processing an 8 x 8 x 6 p i c -ture i s shown for d i f f e r e n t values of y. For y< = 0.0 a l l frames are i d e n t i c a l , t h i s curve corresponds with curve (1). For y i n f i n i t e the curve corresponds to curve (2). Since there i s no c o r r e l a t i o n i n the t h i r d dim-ension, there i s no advantage i n using a three-dimensional transform pro-cessing system. The second case (same complexity) i s shown on F i g . 4.2(b). The performance of a two-dimensional system processing a 16 x 16 pi c t u r e i s compared with the performance of a three-dimensional system processing an 8 x 8 x 4 p i c t u r e for d i f f e r e n t values of y and f o r the same value of a and 8 (0.06). For an average value of the c o r r e l a t i o n parameters a , B and y, a S/N r a t i o of about 20 dB i s reached by transmitting as l i t t l e as a quarter of the t o t a l number of the Fourier samples. 30 dB i s reached by using approximately a.half of the Fourier samples. . , Even when the c o r r e l a t i o n i n the t h i r d dimension i s low (y = 0.18 fo r instance) the gain i n S/N r a t i o from a two-dimensional system to a three-dimensional system processing the same data exceeds 2 dB. Improve-ment increases as y decreases. The gain i s 8 dB f o r y = 0.03 when the S/N r a t i o f o r the two-dimensional case i s 20 dB. 48 V QUANTIZATION OF THE FOURIER SAMPLES 5.1 Introduction Any c o r r e l a t i o n among the F o u r i e r samples obtained from the t r a n s -formation of a p i c t u r e w i l l be ignored; thus each transform sample w i l l be considered i n d i v i d u a l l y . The variances of the Fourier samples obtained from the model aut o c o r r e l a t i o n function (4.15, 4.16) are very, d i v e r s e , i t would be i n e f f i c i e n t to use the same quantizer f o r each sample. In t h i s chapter the quantizer used i n our experiments w i l l be defined on the basis of the s t a t i s t i c s of the F o u r i e r samples. The b i t a l l o c a t i o n scheme w i l l then be considered. For the remainder of the the-s i s "optimum" means "optimum i n the sense of the mean square e r r o r " , and the abbreviation b.p.p.e. stands f o r " b i t s per p i c t u r e element". 5.2 S t a t i s t i c s of the F o u r i e r samples Optimum quantization of the F o u r i e r samples requires knowledge of t h e i r amplitude p r o b a b i l i t y d i s t r i b u t i o n s . A l l the Fourier samples are expected to be Gaussian, according to the c e n t r a l l i m i t theorem. The frequency d i s t r i b u t i o n of some of the most important Fourier samples ( i . e . , the ones having the l a r g e s t variances) i s shown i n F i g . 5.1 and F i g . 5.2 f o r the p i c t u r e GARDEN1 segmented i n t o 8 x 8 x 6 sub-pictures. The same data f o r the p i c t u r e FACE appears i n Appendix D. On these graphs ZR(u,v,w) represents the r e a l part and ZI(u,v,w) the imaginary part of the element Z(u,v,w) i n the transform domain. The following f a c t s were noted: 1) ZR(1,1,1) i s the D.C. component. (ZI(1,1,1) = 0.0) I t r e -presents the average brightness of the p i c t u r e i n a small area. As long as the s i z e of the sub-picture i s small, the frequency d i s t r i b u t i o n of the D.C. component can be expected to be s i m i l a r to the frequency d i s t r i -49. bution of the brightness of the picture i t s e l f ( i . e . Maxwell distribution). Compare Fig. 5.2(a) and Fig. 3.2. 2) Most of the other samples Fig. 5.1(b) to (f) and Fig. 5.3 (a) to (c) are typically Gaussian, with zero-mean, as expected. 3) Some Fourier samples related to the colour dimension, i.e. those with w > 1, Fig. 5.2(d) to ( f ) , although they have, i n general, a b e l l shaped distribution, do not have a zero mean. The corresponding am-plitude and phase of these Fourier samples have a non zero mean. An ex-planation of this characteristic is the fact that, i n a l l pictures, some colours are predominant, consequently for many picture elements, the brightness, as a function of the wavelength A , has a similar shape and the Fourier transform of each of these brightness functions has similar Fourier components. The mean of these samples i s very small, however, and could be taken into account in the processing system. 4) For a l l the other samples with smaller variances, not re-presented here, the Gaussian shape was found to be more evident. In the present study, optimum non-uniform Max quantizers [27] w i l l be used, adapted to a Maxwell distribution for the D.C. component and to a Gaussian distribution for a l l other components (Fig. 5.3). The quantization levels up to 7 bits were computed for a Gaussian and a Max-well distribution according to the method outlined in [27]. 5 0 . Fig. 5.1 Histograms of Fourier samples for the picture GARDEN1 51. ZI t*. .2.1) fa) n ^ r ^ — ^ , — T ^ - < S.O -30.0 -15.0 ( O . O o J ( 15.0 30.0 o.o 5. 2RC1.3.1) s e \ j .-•O.0 -30.0 I X 1 0 3 ) Z K 1 . 3 . 1 ) e M Z R C l . 1 . 2 ) (d) -«5.0 -30.0 -15.0 " 0.0,, , 150 mo2 I 30.0 « . 0 6 Z I U . 1 . 2 ) re; 1.0 -30.0 -15.0 ( 0 . 0 O J ( 15.0 30.0 -O.0. Z R C l . 1 . 3 ) Jo^ -3O.0 -15.0 ( 0 . 0 Q J f 15.0 3O.0 « . 0 Fig. 5.2 Histograms of Fourier samples for the picture GARDEN1 52. DC. Component MAX QUANTIZER MAXWELL k °1 MAX QUANTIZER GAUSS. . MAX QUANTIZER GAUSS T i g . 5.3 Quantization of the Fourier samples 5.3 B i t A l l o c a t i o n : The problem of assigning M b i t s to n samples z^ of unequal variances a? was f i r s t considered by Huang and Schullheiss [5]'. They a r r i v e d at the conclusion that using an optimum Max quantizer and assum-i n g uncorrelated Gaussian samples, then the optimum number of b i t s bj for the j t h quantizer f o r the component of variance a? i s given "approximately" by the following expression: b j * f + 21n2 < l n ° 2 + W j l n ° i 2 > C 5' 1) •I b 3 = M j = l (5.2) Some t r i a l and e r r o r i s required to f i n d the optimum b i t assign-ment . iKurtenbach and Wintz [28], using an optimum uniform Max quantizer, proposed the -following.algorithm: 1) Compute the bj numbers: 2 • „ 9 1 j n l n l O j n l (5.3) f o r j = 1,..., n 53. n 2) If £ b. ^ M, arbitrarily adjust some of the m according to j-1 J 3 the following rules: a) I f M < ^ b , take the b. corresponding to the largest j such j=l J 3 t h a t b. > 1 and replace i t by b. - 1. j J n b) If M > I b . , take the m. corresponding to the smallest j such j=l J 3 t h a t b. = b_ and replace i t by b. + 1. J J Habibi and Wintz [6] used this last algorithm for monochromatic pictures. Equations (5.1) and (5.3) are very similar (1/2.In2 =0 .72, 2/lnlO = 0.86). However, the second algorithm wi l l assign relatively more bits to samples of large variances and fewer bits to samples of small variances. This effect has been reported to be beneficial to the subjec-tive quality of pictures [7]. The second algorithm (5.3) wi l l be used in this thesis and the following restriction wi l l be added: i f any b.. > 7, then set b_. = 7 since 7 bits have been reported sufficient to code the brightness for the PCM transmission of pictures [1]. I t is important to note that in applying the bit allocation algorithm (5.3), a l l variances estimated from the model are included. A l l transform samples which were allocated 0 bits were then deemed to be ^excluded by the data reduction system as shown in Fig. 4.1 5.4 Quantization: I n this section the effect of quantization on the total S/N ratio wi l l be studied. The number of bits assigned to each sample is given by the algorithm outlined in the preceding section. 54. 5.4.1 Estimation of the Quantization Error: The total error of the system, considering an errorless channel, i s equal to the sum of the reduction error (computed in the preceding chapter), and the quantization error [29]. The quantization error e 2^ can be obtained from [27] for the optimum non-uniform and uniform quantizers. An alternative is to use the following mathematical function which models the quantization error as a function of the number of b i t s . e 2 = o? 10 " b J / 2 (5.4) q i where a 2 is the variance of the sample and b.= is the number of bits assigned to the same sample. This function was proposed by Wintz and Kurtenbach [28] and used by Habibi and Wintz [6] to model the quantization error of an op-timum uniform Max quantizer. From the results published in [27], i t i s actually best fit t e d to the non-uniform quantizer as shown i n Table 5.1. NUMBER OF BITS N QUANTIZATION ERROR UNIFORM QUANTIZATION ERROR NON-UNIFORM N i o " 2 1 0.3634 0.3634 0.3162 2 0.1188 0.1175 0.1000 3 0.0374 0.0345 0.0316 4 0.0115 0.0095 0.0100 5 0.0034 0.0025 0.0031 Table 5.1 Quantization errors as a function of the number of bits for uniform and non-uniform optimum quantizers. Equation (5.4) w i l l be used in the present study to predict the quantiza-tion error. 5.4.2 Importance of the Quantization error: Using the characteristics of the picture FACE (a = 0.048, 0 = 0.047, y = 0.069), the predicted effect of quantization on the total S/N ratio is shown in Table 5.2. 55. N NUMBER S/N RATIO S/N RATIO BPPE TRANSMITTED NO QUANTIZATION QUANTIZATION SAMPLES dB dB 0.25 3 6.49 6.31 0.5 5 7.78 7.77 0.75 8 9.51 9.12 1.00 10 9.92 9.91 1.50 16 12.59 12.35 2.00 31 14.74 14.68 3.00 37 17.68 17.53 4.00 53 19.73 19.44 5.00 75 22.14 21.18 Table 5.2 S/N ratio as a function of the average number of b.p.p.e. with and without quantization. Sub-picture: 8 x 8 x 6. The effect of quantization i s very small. The loss in S/N ratio caused, by quantization is less than 4.5% of what the S/N ratio is without quantization. For large numbers of b.p.p.e. the loss i n S/N ratio due to quantization is l i k e l y to increase. This comes from the fact that the b i t allocation algorithm (Section 5.3) operates in the following way: - i t assigns a large number of bits (7,6) to the samples with large variances in a l l cases, consequently the quantization error on those samples is negligible (less than 0.1%); - for a large average number of b.p.p.e., a smaller number of bits (3,2) i s assigned to a large number of samples with smaller variances, causing a larger quantization error in these samples. 5.4.3 S/N Ratio as a Function of the Number of b.p.p.e.: The S/N ratio as a function of the average number of b.p.p.e. can now be obtained. In Fig. 5.4, the variation of the S/N ratio, as a function of the average number of b.p.p.e. , i s shown for various cases. 56. a) A three-dimensional system processing an 8 x 8 x 6 p i c t u r e i s compared to a two-dimensional system processing the same data. b) A three-dimensional system processing an 8 x 8 x 4 p i c t u r e i s compared to a two-dimensional system processing a 16 x 16 p i c t u r e . I t i s seen that the gain i n S/N r a t i o from the two-dimensional system to the three-dimensional varies between 2 dB f o r y = 0.12, F i g . 5.4(b) and 9 dB for y = 0.03 i n F i g . 5.4(a) and for a r e a l i s t i c number of b.p.p.e. 2,3. De t a i l s on the computations used to obtain the curves i n F i g . 5.4 can be found i n Appendix C. 5.4.4 S/N Ratio as a Function of the Sub-picture Size: The v a r i a t i o n of the S/N r a t i o as a function of the sub-picture s p a t i a l dimensions, for various values of the average number of b.p.p.e., f o r a = 8 = 0.06 and f o r various values of y> i s shown on F i g . 5.5. - For small s i z e s , 4 x 4 x 6 to 8 x 8 x 6 the S/N r a t i o increases r a p i d l y with i n c r e a s i n g s i z e . - Above 8 x 8 x 6 , and for more than 2 b.p.p.e., the gain i n S/N f o r l a r g e r s i z e i s very small. 5.5 Conclusion - Simulation Technique: In the next chapter, the influence of some parameters on the performance of the three-dimensional transform encoding system represented i n F i g . 5.6, w i l l be studied. The system was simulated i n the following way. The picture was d i g i t i z e d and stored on tape ( F i g . 2.1), and then segmented into smaller sub-pictures. Each sub-picture was Fast Fourier transformed [31]. Given ct, 8 and y, which represent a type of p i c t u r e , a set of variances was computed (4.14)(4.15) at the transmitter and at the receiver. Some Fourier samples were rejected according to an a p r i o r i f i x e d average number of b.p.p.e. The remaining samples were quantized as o u t l i n e d i n the preceding s e c t i o n and transmitted or stored using a F i g . 5.4 S/N r a t i o a f u n c t i o n of t h e average number o f b.p.p.e. f o r v a r i o u s t r a n s f o r m e n c o d i n g systems. 58. Fig. 5.5 S/N ratio as a function of the sub-picture size Z(UjVyW) n^xm samples FOURIER TRANSFORM REDUCTION BIT ALLOCATION (<n xm samples) MAX QUANTIZER MAXWELL MAX QUANTIZER GAUSS (FOURIER \ [TRANSFORM) D/A CONVERSION Z(u,y,w) DIGITAL COMMUNICATION, CHANNEL CR STORAGE MEDIUM NOISE Fig. 5.6 Three-dimensional transform encoding system 60. natural binary code. In the receiver, using the same set of variances as in the transmitter, the bits were converted to Fourier samples. The inverse Fourier transform of the sub-picture was taken and stored on tape. The completed picture was displayed using the system of Fig. 2.5. An adaptive system which estimates a, 6 and y for each sub-picture, sends these estimates to the Reduction-Bit Allocation device and transmits them to the receiver along with the Fourier samples w i l l be studied i n Chapter 7. 61 VI THREE-DIMENSIONAL TRANSFORM ENCODING OF COLOUR PICTURES 6.1 Introduction In t h i s chapter, the r e s u l t s of various experiments on transform encoded colour pictures are d e t a i l e d , and the following points discussed: 1) The q u a l i t y of the processed p i c t u r e as a function of the sub-pi c t u r e s i z e and the average number of b.p.p.e. 2) The a b i l i t y of the model (exponential a u t o c o r r e l a t i o n function) to p r e d i c t transform encoding system performance. Three d i f f e r e n t measurements of the er r o r between the processed and the o r i g i n a l p i c t u r e (S/N r a t i o ) w i l l be used i n th i s chapter. They are the following (see F i g . 6.1): 1) "The estimated S/N r a t i o computed from the estimated variances", was defined i n Chapter 4. Assuming that the p i c t u r e i s a s t a t i o n a r y pro-cess, a model f o r the autocorrelation function was chosen. Using t h i s model, a set of estimated variances of the transform samples was created. This set of variances was then used to estimate the erro r ( F i g . 6.1(a)). 2) Since the transform p i c t u r e was a v a i l a b l e , i t was p o s s i b l e to compute the actu a l variances of the transform samples, and i f the p i c t u r e i s assumed s t a t i o n a r y , then Eq. 4.8 gives the "estimated S/N r a t i o computed from the actual variances". ( F i g . 6.1(b)). 3) Once the p i c t u r e was processed, i t was p o s s i b l e to "compute the S/N r a t i o " by computing the mean square d i f f e r e n c e between o r i g i n a l and processed p i c t u r e . ( F i g . 6.1(c)). A simple experiment was performed, which gives an example of the three kinds of measurements which have j u s t been defined. Each of the s i x pictu r e s were segmented in t o 6 x 6 x 6 sub-pictures. Each sub-picture was 62. STATIONNARY MODEL SET OF ESTIMATED VARIANCES OF ESTIMATED ERROR OF PICTURE P TRANSFORM • SAMPLES • (a) P FOURIER SET OF ACTUAL VARIANCES OF FOURIER SAMPLES ESTIMATED TRANSFOR-MATION ERROR (b) P COMPLETE FOURIER TRANSF. P COMPUTED ENCODING PROCESS ERROR fc) F i g . 6.1 Various estimations of the S/N r a t i o . Fourier transformed and only the D.C. component was retained. In the r e s u l t i n g inverse transformed p i c t u r e each sub-picture i s replaced by i average brightness (Fig. 6.2(a)-(b)-(c)). The three following measure-ments are l i s t e d i n Table 6.1 o^ 2: Normalized variance of the D.C. component estimated from stationary exponential model f o r the au t o c o r r e l a t i o n function (a 2 < 1) A (S/N) A = -10 log (1.0 - a A 2 ) 63.a F i g . 6.2 Transform processed pictures. Only the D.C. component was used to reconstruct the picture. Sub-picture size: 6 x 6 x 6 (a) G A R D E N 1 , (b) FACE, (c) TEST PATTERN 64. a 2 : Normalized variance of the D.C. component, a c t u a l l y B • computed from the Fourier transform ( C Tg 2 < 1) (S/N) B = -10 l o g (1.0 - a B 2 ) (S/N) p : S/N r a t i o a c t u a l l y computed from the processed p i c t u r e . p (S/N) A ° B 2 (S/N) B (S/N) c Gl 0.5041 3.05 0.5291 3.27 2.49 G3 0.6271 4.28 0.6647 4.74 3.53 F 0.7354 5.77 0.7859 6.69 5.33 H 0.7315 5.71 0.7273 5.64 5.66 TP 0.735 7 5.77 0.7339 5.74 5.79 B 0.5618 3.58 0.5123 3.11 2.-8 Table 6.1 S/N predicted and computed when only the D.C. component was transmitted. (S/N) , (S/N) and (S/N) are the three S/N r a t i o s that w i l l be computed In t h i s chapter. 6.2 Experimental Results Obtained Using Various Sub-picture Sizes and Various Numbers of B i t s Per Picture Element (B.P.P.E.): 6.2.1 Sub-pictures 6 x 6 x 6 In the following pages, the experimental r e s u l t s obtained by processing pictures segmented in t o 6 x 6 x 6 sub-pictures and encoded using 1, 2 and 3 b.p.p.e. are presented i n F i g s . 6.3, 6.4, 6.5. The reader should view these and other processed pi c t u r e s at a distance of approxi-mately 25 inches. The viewing distance i s i n f a c t an important determinant of subjective q u a l i t y . More data concerning the processing of the p i c t u r e s GARDEN! and FACE i s provided. Tables 6.2 and 6.3 show the b i t a l l o c a t i o n s f o r 1,2 and 3 b.p.p.e. In Tables 6.4 and .6.5 the normalized variances of the transmitted samples (a) estimated from the exponential model, (b) computed on the actual 65. Fourier transform, are shown. The format i n which the data i s presented i s explained i n Appendix C. 6.2.2 Sub-pictures 8 x 8 x 6 : The same experiments were performed using 8 x 8 x 6 sub-pictures. The b i t a l l o c a t i o n s f o r the p i c t u r e GARDEN1 and FACE are presented i n Tables 6.6 and 6.7 for 1, 2 and 3 b.p.p.e. The processed pi c t u r e s are shown i n F i g s . 6.6,6.7,6.8. 66. a Fig. 6.3 Transform processed pictures Sub-picture size: 6 x 6 x 6 1 b.p.p.e. 67.a Fig. 6.4 Transform processed pictures Sub-picture size: 6 x 6 x 6 2 b.p.p.e. 67.b 6 8 . a 'Fig. 6.5 Transform processed pictures Sub-picture size: 6 x 6 x 6 3 b.p.p.e. 68.b Table 6.2 Bit allocation for the picture GARDEN1 for 1,2, and 3 b.p.p.e. and for a 6 x 6 x 6 sub-picture size. Table 6.3 Bit allocation for the picture FACE for 1,2, for a 6 x 6 x 6 sub-picture size. CARDEX1 ESTIMATED VARIANCES V \ 1 2 3 4 1 1 2 3 4 5 6 0.5041 0.0275 0.0404 0.0140 0.0096 0.0178 0.0119 0.0186 0.0019 0.0022 0.0024 0.0017 0.0063 0.0040 0.0077 2 1 2 3 4 5 6 0.0145 0.0224 0.0023 0.0027 0.0029 0.0021 0.0012 3 1 2 3 4 5 6 0.0076 0.0049 .* 1 2 3 4 5 6 0.0094 5 1 2 3 4 5 6 6 1 2 3 4 5 6 0.0013 GARDEN1 ACTUAL VARIANCES W \ 1 2 3 4 1 1 2 • 3 4 5 6 0.5291 0.0221 0.0367 0.0091 0.0043 0.0078 0.0072 0.0122 0.0044 0.0051 0.0063 0.0048 0.0030 0.0017 0.0029 2 1 2 3 4 5 6 0.0209 0.0144 0.001.6 0.0023 0.0025 0.0017 0.0008 3 1 2 3 4 5 6 0.0027 0.0014 4 1 2 3 4 5 6 0.0013 5 1 2 3 4 5 6 6 1 2 3 4 5 6 0.0014 Table 6.4 Estimated and actual normalized variances of the Fourier samples transmitted for 3 b.p.p.e. for the picture GARDEN1. Sub-picture size: 6 x 6 x 6 . FACE ESTIMATED VARIANCES V \ 1 2 3 4 1 1 2 . 3 4 5 6 0.7354 0.0090 0.0145 0.0048 0.0030 0.0059 0.0092 0.0148 0.0049 0.0031 0.0060 2 1 2 3 4 5 6 0.0134 0.0213 0.0006 0.0007 0.0006 3 1 2 3 4 5 6 0.0071 0.0045 4 1 2 3 4 5 6 0.0087 5 1 2 3 4 5 6 6 1 2 3 4 5 6 0.0007 FACE ACTUAL VARIANCES W \ 1 2 3 4 1 1 2 3 4 5 6 0.7859 0.0044 0.0086 0.0023 0.0009 0.0024 0.0061 0.0121 0.0031 0.0011 0.0030 2 1 2 3 4 5 6 0.0066 0.0240 0.0003 0.0004 0.0008 3 1 2 3 4 5 6 0.0052 0.0032 4 1 2 3 4 5 6 0.0021 5 1 2 3 4 5 6 6 1 2 3 4 5 6 0.0006 i Table 6.5 Estimated and actual normalized variances of the Fourier samples transmitted for 3 b.p.p.e. for the picture FACE. Sub-picture size: 6 x 6 x 6 . N3 Table 6.6 Bit allocation for the picture GARDEN1 for 1, 2 and 3 b.p.p.e an 8 x 8 x 6 sub-picture size. Table 6.7 Bit allocation for the picture FACE for 1, 2 and 3 b.p.p.e. and an 8 x 8 x 6 sub-picture size. 7 5 . a rFig. .6.6 Transform processed pictures Sub-picture size: 8 x 8 x 6 1 b.p.p.e. 76.a Fig, 6 .7 Transform processed pictures Sub-picture size: 8 x 8 x 6 2 b.p.p.e. i 76.b 7 7 . a Fig. 6.8 Transform processed .pictures Sub-picture size: 8 x 8 x 6 3 b.p.p.e. 77 .b 78. 6 . 3 Discussion of the Results: From the results presented in the preceding pages, the following conclusions can be drawn: 1) It seems that approximately 2 b.p.p.e. is a lower l i m i t necessary to transmit with acceptable f i d e l i t y the colour pictures in the set used in this thesis. In the preceding experiments bright areas in particular were poorly transmitted. As shown in the following chapter the subjective quality and S/N ratio of the processed pictures can be :.mproved by modify-ing the quantizer of the D.C. component. 2) For most of the pictures, the relative ordering of the actual variances of the Fourier samples was relatively well predicted by the exponential model. Table 6.8(a) shows the order of the estimated variances ranked by decreasing values and Table 6.8(b) the same data for the actual variances, for the picture FACE. Thus, the simple exponential model can be used to decide which Fourier samples are to be transmitted. 3) By inspection of the tables of variances i t can be seen that the . variances estimated from the exponential model d i f f e r from the actual variances. Table 6.9 shows the following ratio: Estimated variances of the Fourier samples 1 N R = — :: : z : — : :;—' (, O . i.) Actual variances of the Fourier samples w V U 1 2 3 4 1 1 6 3 12 15 10 2 7 4 27 26 61 45 66 53 1 3 13 16 62 46 84 31 82 91 4 11 65 54 83 90 80 5 52 56 77 89 6 23 28 51 55 1 5 2 21 19 48 30 57 38 2 22 20 92 99 108 115 131 128 3 50 32 110 118 154 146 184 161 2 59 40 130 129 183 162 187 174 5 35 44 126 102 155 147 170 179 6 IS 25 97 94 106 116 122 134 1 9 14 47 29 75 68 72 85 2 49 31 104 112 148 140 182 159 3 76 70 151 142 200 190 209 203 74 87 181 160 208 204 207 214 5 64 79 153 144 191 196 1 98 212 6 35 43 103 113 136 163 168 175 1 8 58 37 71 86 67 2 60 39 132 127 185 157 189 172 3 73 88 186 158 210 202 205 216 >\ 4 69 188 173 206 215 201 5 167 180 19 7 213 6 121 135 166 178 1 33 41 63 78 2 124 100 149 141 3 152 143 192 195 5 4 169 176 199 211 5 137 164 193 194 6 105 114 150 139 1 17 24 34 42 2 98 95 107 117 3 109 119 138 165 6 123 133 171 177 5 111 120 156 145 6 96 93 125 101 (a) Table 6.8 Rank of (a) estimated, (b) for the picture FACE and a w V U 1 2 3 H 1 1 6 3 10 16 n 2 8 4 23 21 76 42 69 56 3 13 17 82 39 130 97 118 140 1 4 12 74 51 151 146 58 5 41 48 90 168 6 15 20 36 46 1 5 2 19 18 53 45 55 59 2 25 33 66 62 124 136 101 107 3 72 73 125 129 145 179 105 114 2 4 104 83 132 172 195 187 199 167 5 94 63 110 119 150 141 159 149 6 27 32 37 35 61 64 103 115 1 7 9 29 30 100 77 126 86 2 34 40 95 93 153 188 163 143 3 78 108 157 139 186 215 189 209 3 4 109 102 165 166 208 204 216 192 5 99 68 155 131 203 185 198 207 6 44 31 91 89 121 122 169 181 1 14 50 38 113 133 54 2 98 92 116 88 135 170 211 182 3 137 117 14-1 160 184 201 197 180 u 4 49 19u 200 214 210 70 5 196 194 212 213 6 128 123 154 148 1 28 26 80 60 2 75 67 111 161 3 144 120 175 205 5 4 174 171 206 202 5 176 152 162 177 6 79 84 96 106 1 22 24 43 52 2 85 81 112 87 3 127 178 156 164 6 4 173 193 191 183 5 138 142 158 134 6 57 65 71 47 (b) actual variances of the Fourier samples 6 x 6 x 6 sub-picture size. 80. f o r the p i c t u r e GARDEN1 segmented into 6 x 6 x 6 sub-pictures. On the average the D.C. component i s predicted w i t h i n 10% of i t s actual value. The next 25 variances, ordered by decreasing values, are overestimated; these correspond to the most important samples. The remaining variances are underestimated, but the corresponding Fourier samples would not be transmitted f o r 3 b.p.p.e. or l e s s . Consequently the S/N r a t i o p r e d i c t e d by the variances estimated from the exponential model w i l l be too la r g e . F i g . 6.9 shows the v a r i a t i o n of the three S/N r a t i o s (see F i g . 6.1) as function of the average number of b.p.p.e. f o r a 6 x 6 x 6 sub-picture s i z e . The same data for an 8 x 8 x 6 sub-picture s i z e i s shown i n F i g . 6.10. I f a p i c t u r e i s assumed s t a t i o n a r y , and processed using the b i t a l l o c a t i o n algorithm defined i n Section 5.3, then the maximum S/N r a t i o r e a l i z a b l e i s the one predicted by the actual variances. To v e r i f y t h i s hypothesis, the pictures have been processed without quantization, trans-m i t t i n g only the samples recommended for 1, 2 or 3 b.p.p.e. The r e s u l t i n g S/N r a t i o i s compared i n Table 6.10 with the one predicted by the actu a l variances of the Fourier samples. In t h i s table the s i m i l a r i t y between S/N r a t i o s i s evaluated by the measure: • I ( S / N ) Computed - ( S / N W c t e d l D = x 100 (6.2) . X ^ b 7 ^ P r e d i c t e d The p r e d i c t i o n i s excellent and predicted values are within 10% of the computed value and with i n 2% i n 75 per cent of the experiments. Conse-quently the S/N r a t i o p r e d i c t e d by the actu a l variances of the Fourier samples w i l l be considered as the upper l i m i t obtainable. 81. ff \ u 1 2 3 A v \ l 1 . 9 5 I 1 . 6 5 1 . 5 3 2 . 0 9 2 . 3 9 i 2 . 6 3 ; 2 1 . 2 5 1 . 1 0 . 4 3 . 4 4 . 5 9 . 5 8 . 6 2 . 7 9 T 3 1 . 5 4 2 . 2 4 . 4 9 . 5 0 . 5 4 . 5 3 . 7 0 . 5 4 X 2 . 3 0 ! . 6 5 . 7 6 . 7 0 . 5 3 . 6 9 5 . 4 0 . 4 0 . 5 2 . 4 6 6 . 3 8 . 3 6 . 5 2 . 5 2 1 . 6 9 j 1 . 5 6 2 . 0 7 1 . 4 8 1 . 3 4 1 . 2 8 1 . 6 C I 1 . 1 2 2 1 . 4 6 1 . 1 7 . 3 9 . 3 5 . 2 6 . 2 2 . 1 5 . 1 5 3 1 . 4 5 1 . 5 2 . 2 5 . 2 0 . 1 2 . 1 2 . 0 7 . 0 9 ti . 8 9 | 1 . 9 2 . 1 6 . 1 9 . 0 7 . 11 . 0 6 . 0 8 . 9 5 I 1 . 1 7 . 1 5 . 1 4 . 0 8 . 0 9 . 0 7 . 0 7 6 1 . 1 5 1 . 2 1 . 2 4 • 2 7 . 1 8 . 1 9 . 1 6 . 11 1 2 . 8 1 3 . 6 2 . 9 0 i ! 1 . 4 5 . 6 7 . 8 4 . 8 4 . 4 4 2 . 6 5 . 8 5 . 1 1 . 1 0 . 0 8 . 0 9 . 0 7 . 10 3 . 3 7 . 5 0 . 0 4 . 0 4 . 0 3 . C 4 . 0 3 . 0 4 3 . 6 1 . 4 7 . 0 4 . 0 6 . 0 2 . 0 3 . 0 3 . 0 2 5 . 5 7 . 3 5 . 0 5 . 0 6 . 0 4 • C 4 . 0 3 . 0 2 6 . 9 9 . 7 2 . 1 6 . 1 5 . 1 0 . 0 9 . 0 8 . 0 7 1 1 7 . 2 8 I . 6 8 1 i 1 . 0 8 . 4 5 . 3 6 . 4 3 2 1 . 4 4 ~ 2 . ~ 4 5 . 1 5 . 1 7 . 0 6 . 0 8 . 0 5 . 0 7 3 " " . 8 5 • . 7 0 . 0 5 . 0 7 . 0 2 . C 3 . 0 3 . 0 2 4 . 6 9 . 0 4 . 0 6 . 0 2 . 0 2 . 0 2 5 . 0 6 . 0 5 . 0 3 . 0 2 6 . 1 4 . 1 0 . 0 7 . 0 5 1 1 . 3 1 i I i . 9 7 . 7 5 . 4 3 2 . 0 9 . 1 1 . 0 6 . 0 7 3 . 0 5 . 0 5 . 0 3 . 0 3 5 A . 0 6 . 0 4 . 0 3 . 0 2 5 . 0 7 . 0 5 . 0 4 . 0 4 6 . 1 7 . 1 6 . 0 9 . 1 1 1 . 9 5 . 7 2 . 5 2 . 5 7 2 . 1 5 . 1 6 . 1 0 . 0 8 3 . 1 1 . 1 0 . 0 6 . 0 6 6 A . 1 6 . 1 1 . 0 7 . 0 6 5 . 1 4 . 1 4 . 0 7 . 0 8 6 . 1 7 . 1 9 . 1 0 . 1 2 Table 6.9 Ratio of estimated variances to actual normalized variances for the picture GARDEN1 and for a 6 x 6 x 6 sub-picture size. 8 2 . GARDEN 1 CXGXG —1 1— 1.0 2.0 N B.P.P.E. 3.0 cn 0_ ex-ec 0.0 GARDEN3 6X6X6 —i 1— 1.0 2.0 N B.P.P.E. -1 3.0 COMPUTED FROM ACTUAL VARIANCES FROM ESTIMATED VARIANCES F A C E 6X6X6 —l 1 1 1.0 2.0 3.0 N B.P.P.E. oo o 2o cr-" cc 0.0 HOUSE 6X0X6 —1 1— 1.0 2.0 N B.P.P.E. 3.0 TST PTN 6X6X6 —I 1— 1.0 2.0 N B.P.P.E. — i 3.0 CO a r-o. e n -ce cn 0.0 BUILDING 6X6X6 - T 1— l.C 2.0 N B.P.P.E. 3.0 F i g . 6.9 S/N r a t i o s (as defined i n F i g . 6.1) as a function of the average number of b.p.p.e. f o r a 6 x 6 x 6 sub-picture s i z e . 83. G A R D E N ] 8X8X6 I 1— 1.0 2.0 N B . P . P . E . FACE 8X8X6 —1 3.0 N. —1 1 1 1.0 2.0 3.0 N B . P . P . E . CO o cr-0.0 CO on-ce <n GARDEN3 8X0X6 —1 1— 1.0 2.0 N B . P . P . E . H O U S E 8X8X6 1 1 1 0.0 1.0 2.0 3.0 N B . P . P . E . COMPUTED FROM ACTUAL VARIANCES - i FROM 3"° ESTIMATED VARIANCES 1ST PTN 8X8X6 I 1— 1.0 2.0 N B . P . P . E . — i 3.0 ca a So to 0.0 B U I L D I N G 8X6X6 I 1— 1.0 2.0 N B . P . P . E . -1 3.0 . 6.10 S/N r a t i o s (as defined i n F i g . 6.1) as a function of the average number of b.p.p.e. f o r an 8 x 8 x 6 sub-pi c t u r e s i z e . 8 4 . N b.p.p.e. (S/N) A r a t i o dB predicted by actual variances (S/N) B r a t i o dB computed No quantization D l |(S/N) A - (S/N) B| (S/N) A Gl G3 F H • TP B 1 5.93 7.27 10.20 9.31 13.85 7.59 5.74 7.20 10.11 9.37 13.79 8.30 3.2 0.96 0.88 0.64 0.43 9.35 Gl G3 F H TP B 2 7.71 8.89 11.99 11.62 16.07 9.59 7.71 8.84 11.94 11.61 15.92 10.13 0.0 0.56 0.42 0.09 0.93 5.63 Gl G3 F H TP B 3 9.11 9.99 13.64 13.11 18.01 10.71 8.96 9.80 13.29 12.98 17.67 11.13 1.65 1.9 2.56 0.99 1.89 3.92 Table 6.10 Normalized d i f f e r e n c e between (S/N) pre d i c t e d by ac t u a l variances and computed without quanti-zation of the components. The "goodness" of the p r e d i c t i o n of the S/N r a t i u using the variances estimated using the simple exponential model can now be evaluated by the measure T>2' 1 ^ ^ E s t i m a t e d Variances " ( S / N ) A c t u a l Variances! ,c o\ D = 100 x — ~~~—— \°'iJ 2 ( S / N ) A c t u a i Variances D£ i s presented i n Table 6.11 as a function of the average number of b.p.p.e. Measure increases with i n c r e a s i n g number of b.p.p.e. The S/N r a t i o as a function of the number of transmitted samples (no quanti-zation) i s shown i n F i g . 6.11, f o r a l l p i c t u r e s using an 8 x 8 x 6 sub-p i c t u r e s i z e . The number of samples N transmitted f o r 1, 2 and 3 b.p.p.e. i s shown on the same graphs. 85. 6 x 6 x 6 Gl G3 F H TP B 8 x 8 x 6 Gl G3 F H TP B 1 b.p.p.e. 5.80 6.66 7.59 2.42 6.16 11.18 13.99 12.10 0.0 5.15 3.53 3.95 2 b.p.p.e, 35.6 33.21 9.27 13.58 143.49 14.09 31.51 36.22 20.43 25.30 2.67 15.43 3 b.p.p.e, 38.53 46.95 28.45 33.59 139.16 28.63 33.69 44.84 24.70 30.28 6.83 24.46 Table 6.11 Normalized d i f f e r e n c e between act u a l S/N r a t i o and S/N r a t i o p redicted from the estimated variances of the Fourier samples. The poor p r e d i c t i o n of the S/N r a t i o i s not the only disadvantage r e s u l t i n g from the use of the simple exponential model based on s t a t i o n a r i t y . The quantizers make use of the estimated variances. I f the estimated variances are i n c o r r e c t , then the quantization e r r o r i s l i k e l y to be increased. 4) The di f f e r e n c e between computed S/N r a t i o and the maximum S/N r a t i o t h e o r e t i c a l l y obtainable cannot be explained s o l e l y by ad d i t i o n of quantization. As was shown i n Section 5.4.2, the e f f e c t of quantization should be very small. The measure D^: n 3 = I ( S / N )Computed " ( S / N ) A c t u a l Variances! x 1 0 0 ( 6 . 4 ) ( S / N ) A c t u a l Variances i s shown i n Table 6.12 f o r the 8 x 8 x 6 case. The main source of e r r o r i s the poor transmission of very b r i g h t areas. The d i f f e r e n c e s i g n a l i s shown i n F i g . 6.12(a)-(b)-(c) f o r a 16 x 16 x 6 s i z e and 2.0 b.p.p.e. 400.0 "I 400.0 Fig. 6.11 S/N ratio as a function of the number of transmitted samples (no quantization) for an 8 x 8 x 6 sub-picture size. The number of transmitted samples for 1,2 and 3 b.p.p.e. is indicated. 87. 3 1 b.p.p.e. 2 b .p .p .e. 3 b.p.p.e, Gl 12.27 25.94 30.18 G3 28.61 31.15 33.93 F 41.66 44.62 51.31 H 17.29 22.20 26.46 TP 10.18 13.81 17.32 B 1.84 6.46 10.17 Table 6.12 Normalized d i f f e r e n c e between computed S/N r a t i o and S/N r a t i o predicted by ac t u a l variances. 5) As predicted i n s e c t i o n 5.4.4, f o r the same number of b.p.p.e. the S/N i s higher f o r the l a r g e r sub-picture s i z e 8 x 8 x 6 than f o r 6 x 6 x 6 . 6) In the rest of the thesis a 16 x 16 x 6 sub-picture s i z e w i l l b used. The upper t h e o r e t i c a l l i m i t i n S/N r a t i o due to i n c r e a s i n g sub-pic t u r e s i z e ( F i g . 5.5) w i l l be assumed to have been reached. 88.a Fig. 6.12 Absolute difference signal between processed and original pictures. Sub-picture size: 16 x 16 x 6 2 b.p.p.e. (a) GARDEN1, (b) FACE, (c) TEST PATTERN 8 8 .b 89 VII EFFECTS OF IMPROVED QUANTIZATION, BETTER DATA MODELLING, ADAPTIVE PROCESSING AND DIGITAL CHANNEL ERRORS ON COLOUR -PICTURES 7.1 Introduction This chapter deals with the following four items: 1) Improvement in the S/N ratio and in the subjective quality of the processed pictures was obtained by modifying the quantizer of the D.C. component. 2) Prediction of the S/N ratio could be made more, accurate by using a model for the autocorrelation function that would yield a set of estimated variances of the Fourier samples identical to the actual variances. The us a of a better model was studied. 3) The parameters a, 8 and y of the model autocorrelation function have heretofore been obtained using correlation coefficients estimated over the entire picture; there parameters were then used to process every sub-picture. An adaptive system would estimate the parameters a, 8 and y for each sub-picture and transmit these parameters to the receiver along with the Fourier samples. A simpler adaptive system which classified the sub-pictures into a limited number of categories was investigated. 4) The effect of d i g i t a l channel errors on the transmission of the Fourier samples has been investigated. 7.2 Modification of the Quantizer of the Picture D.C. Fourier Component: For a Maxwell distribution, very bright areas are improbable (Figs. 3,2, 7.1), and the optimum Max quantizer chooses levels closer to the average brightness in order to minimise the quantization error. The D.C. component of the Fourier sample is not perfectly modelled by a Maxwell distribution, 90. some very bright areas are responsible for very high, values of the D.C. component. In order to process these areas properly, a new quantizer for the D.C. component was devised to ensure that the maximum values w i l l be correctly transmitted. The highest 64 levels of the D.C. quantizer were empirically linearly scaled so that the highest quantization level ensures the correct transmission of the highest possible value of the D.C. Fourier component for that set of pictures. This quantizer w i l l be referred to as the "adapted modified quantizer". Fig. 7.1 summarizes this operation for a 16 levels quantizer. MAXIMUM OUTPUT LEVEL OF MODIFIED QUANTIZER QUANTIZER INPUT Fig. 7.1 Modification of the Fourier D.C. component quantizer. 91. The six pictures were processed with this new quantizer, a 16 x 16 x 6 sub-picture size and an average of 2.75 b.p.p.e. (Fig. 7.2). The subjective quality of those pictures was improved significantly, The various numerical results are shown in Table 7.1, with the measure D^ D 3 = I Computed " ( S / N ) A c t u a l Variances 1 x 1 0 0 ( 7 - 1 ) (S/N) A c t u a-^ variances S/N ratio from estimated variances S/N ratio from actual variances S/N ratio computed D3 Gl 9.91 8.99 8.31 7;5 G3 12.16 10.28 9.39 8.65 F 15.11 13.92 12.38 11.06 H 15.10 13.49 12.79 5.19 TP 18.32 18.96 17.93 5.43 B 11.37 10.97- 10.77 1.82 Table 7.1 S/N ratios in the 16 x 16 x 6 case, using the adapted quantizer and 2.75 b.p.p.e., and nor-malized difference between computed S/N ratio and S/N ratio predicted by the actual variances. The normalized difference between -,he computed S/N ratio and the maximum S/N ratio estimated from the actual variances i s significantly smaller than in previous experiments (compare with Table 6.12). The subjectively unpleasant characteristics were caused by sub-pictures of high c o n t r a c t , including the collar in FACE, some parts of the bridge in GARDEN3 and some sub-pictures in TEST PATTERN. The subjectively unpleasant effects are due to the f i l t e r i n g of steep gradient of the variation of the brightness. In order to test the adapted quantizer, two typical pictures were processed without quantizing the D.C. component. From (5.4) the error due to the quantization of the D.C. component should not exceed: 92.a Fig. 7.2 Transform processed pictures Sub-picture size: 16 x 16 x 6 2.75 b.p.p.e. Adapted quantizer 93. where a z is the variances of the D.C. component. For the two pictures chosen: GARDEN1 ay2 = 0.5291 e 2 = 0.00017 HOUSE a* = 0.7273 E j 2 = 0.00023 Therefore, the effect on the global error should be very small. Suppressing the quantization of the D.C. component increased the S/N ratio by 0.01 dB for the picture GARDEN1 and by 0.02 dB for the picture HOUSE. It can be concluded that the new quantizer is properly adapted to the data. 7.3 Attempts to Improve Performance by Use of a More precise Model: Fig. 7.3 represents the variation of the S/N ratio as a function of the number of transmitted samples in the 16 x 16 x 6 case, (1) predicted by the estimated variances obtained using the simple exponential model, (2) predicted by the actual normalized variances. The S/N ratio predicted by the estimated variances i s considerably higher. The improvement of the prediction of the S/N ratio, by looking' for an estimated set of variances closer to the true variances of the Fourier samples, i s considered in this section. A few experiments showed that there was no simple function R(u,v,w) such that oa2(u,v,w) = R(u,v,w) . ae2(u,v,w) (7.2) for a l l pictures. In (7.2) aa2 represents the actual variances and a g 2 the estimated variances. 7.3.1 Non-separable model: It i s reasonable to expect a better prediction from a function 94. 0.0 20.0 « . 0 63.0 80.0 10O.O 130.0 141.0 1S0.0 tt 1X10' I Fig. 7.3 S/N ratios as a function of the number of transmitted samples (1) predicted by the variances estimated from the simple model, (2) predicted by the normalized actual variances for a 16x16x16 sub- picture size. The S/N measured for 2.75 b.p.p.e. are shown. 95. which models the autocorrelation function more c l o s e l y than does the simple separable exponential model. In Section 3.5, i t was noted that a non-separable model provided a c l o s e r f i t to the computed au t o c o r r e l a t i o n function i n the diagonal d i r e c t i o n , i n the two cases GARDEN1 and FACE. In the same sect i o n i t was noted that, for the colour dimension, the f i t of the non-separable model was b e t t e r for large s p a t i a l displacements. Consequently, i t was deemed important to study the set of variances computed from the non-separable model. The computer time involved i n the computation of the var-iances of the Fourier samples i s considerably l a r g e r than i n previous experiments (Sect. 4.2). For the separable model, f o r an 8 x 8 x 6 sub-picture i t took les s than 1 minute of C.P.U. time on the IBM 370/168 to compute the 384 variances. With the non-separable model i t takes about 25 seconds per variance. Even a very e f f i c i e n t program mould requires at l e a s t 2 hours to compute a l l of the variances. For a 16 x 16 x 6 p i c t u r e s i z e the simula-t i o n would become p r o h i b i t i v e l y expensive. For that reason, only the var-iances from the f i r s t 64 samples whose actual variances are the highest were computed. The S/N r a t i o p redicted by t h i s model for the p i c t u r e GARDEN1 i s compared, i n F i g . 7.4, to the S/N r a t i o p redicted by the actual variances, and the S/N r a t i o predicted by the separable model. One can conclude that the f i r s t ten variances are not so accurately estimated as when a separable model i s used. Also, the variances of higher rank samples are smaller than those estimated using the separable model. Consequently, the predicted S/N r a t i o i s smaller and very close to that predicted by the actual variances. The main disadvantage of the non-separable model i s the time involved i n the computation of the variances. 96. C 3 Fig. 7.4 Comparison between S/N ratios, as a function of the number of transmitted samples, predicted by the var-iances estimated from the separable model and the non-separable model and the actual normalized variances. Sub-picture size 8x8x6. Picture GARDEN1. 97. 7.3.2 Double Exponential Model: A better f i t to the computed autocorrelation function was obtained, for the weakly correlated pictures GARDEN1 and GARDEN3, using a sum of two exponentials (section 3.6). The S/N ratio predicted by this model i s compared in Fig. 7.5, to the S/N ratio predicted by the separable model. The prediction i s not significantly improved.by use of the double exponential model. 7.3.3 Processing Using the Actual Variances of the Fourier Samples: Since the actual set of variances of the Fourier samples, com-puted on each transformed picture, i s theoretically the best set available, i t was important to process each picture using those variances computed from the Fourier transform of the picture i t s e l f instead of those estimated from the model's autocorrelation function. The results are presented on Fig. 7.6 for 2.75 b.p.p.e. Table 7.2 compares the S/N ratio obtained in this experiment to the one obtained when the estimated var-iances were used. (S/N) A (S/N) B Gl 8.32 8.59 G3 9.39 9.25 F 12.38 12.20 H 12.77 13.31 TP 17.93 17.72 B 10.78 10.95 Table 7.2 (S/N)^: Measured S/N ratio obtained when the pictures are processed using the variances estimated from the simple exponential model (2.75'b.p.p.e., 16 x 16 x 6). (S/N)^: Measured S/N ratio obtained when the pictures are processed using the actual variances of the Fourier samples (2.75 b.p.p.e. 16 x 16 x 6). 98. 0 a zo.o IO.O eo.o ro.o IOO.O 170.0 ln.o 160.0 N 1X10' ) Fig. 7.5 S/N ratios as a function of the number of transmitted samples predicted by the variances estimated from the single exponential model, the double exponential model and the actual normalized variances. Sub-picture size 16x16x16. Pictures GARDEN1 and GARDEN3. Fig. 7.6 Pictures processed using the adapted quantizer for the D.C. component, 2.75 b.p.p.e. and for each picture, the actual variances of the samples of the Fourier -transform of the picture Sub-picture size 16 x 16 x 6. 100. Using the actual rather than the estimated variances yielded a better S/N ratio in 3 cases (GARDEN1, HOUSE, BUILDING). For the three other pictures there was a slight degradation. There was no noticeable difference in the subjective quality of the pictures processed using either model. For a l l six pictures, use of the actual variances was found to have the disadvantage of requiring the transmission of a larger number of Fourier samples, according to the algorithm defined in Section 5.3. For example for the picture GARDEN3, Table 7.3 compares the bit allocations using the estimated variances and the actual variances. In the case where actual variances are used, i t is seen that a large number of samples has to be transmitted using a very low number of bits (1,2). 101. u V 1 2 3 4 5 6 7 8 9 1 7 7 7 6 7 6 6 6 6 5 5 5 5 5 6 6 2 7 7 7 6 5 5 5 5 4 4 4 4 4 4 0 4 0 4 3 7 7 5 5 4 4 0 3 0 0 0 0 0 0 0 0 0 0 4 7 7 5 5 0 4 0 0 0 0 0 0 0 0 0 0 0 0 5 6 6 4 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 6 6 4 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 6 6 4 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 6 5 4 4 0 0 0 0 0 0 0 0 ._o 0 0 0 0 9 6 4 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 4 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 4 4 0 0 0 0 0 0 0 0 0 0 0 0 12 4 4 0 0 0 0 0 0 0 0 0 0 0 0 13 4 4 0 0 0 0 0 0 0 0 0 0 0 0 14 5 5 4 0 0 0 0 0 0 0 0 0 0 0 15 5 5 4 4 4 0 0 0 0 0 0 0 0 0 16 7 6 5 5 5 5 4 4 4 4 4 4 0 4 T o t a l : 92 samples u V 1 2 J 4 5 6 1 8 9 1 7 5 5 4 4 3 3 2 2 2 2 2 1 2 1 2 2 6 6 5 5 4 3 3 3 2 2 2 2 1 1 1 1 1 1 3 4 5 4 4 3 3 2 2 2 2 1 1 1 1 1 1 1 1 4 4 4 3 3 3 3 2 2 1 1 1 1 0 1 0 0 0 1 5 3 3 3 2 2 2 1 2 1 1 0 1 1 0 0 0 0 0 6 3 3 2 2 2 1 1 1 1 1 1 0 1 0 0 0 0 0 7 3 2 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 8 3 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 9 3 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 10 1 1 1 1 1 1 0 1 0 0 0 0 0 0 11 2 2 1 1 1 1 1 1 0 1 0 0 0 0 12 2 2 2 1 1 1 1 1 1 1 0 0 0 0 13 2 2 2 2 2 1 1 1 1 1 0 1 0 0 14 3 3 2 2 2 2 1 1 1 1 1 1 1 0 15 4 4 3 3 2 2 2 2 1 1 1 1 1 1 16 5 4 4 4 3 3 2 2 1 2 1 1 1 1 T o t a l : 177 samples Table 7.3 B i t a l l o c a t i o n s obtained (a) by using the estimated variances, (b) by using the actual variances of the Fourier samples i n the plane w = 1. 102. 7.4 Adaptive Processing for Improved Performance; Two typical adaptive systems are described elsewhere [20,31}. Anderson [20] transmitted for each sub-picture a number of Fourier samples proportional to the variance of the brightness of the sub-picture. Tasto and Wintz [31] classified the sub-pictures i n three categories depending on the amount of details and the average brightness of the sub-pictures. In the present study the parameters a, 3 and y have been estimated over the entire picture. It i s l i k e l y that they are not repre-sentative of a l l regions of the picture. Some parts of the picture of constant brightness and colour do not require as many bits as highly detailed areas. An adaptive system would take those variations into account, attach a set of parameters a, 3, y to each.sub-picture, or group sub-pictures into categories. Such a system was investigated by us. Each sub-picture was considered as an independent picture and the parameters a, 3 and y were estimated as in Chapter 2. Some results are presented for the picture FACE: In Fig. 7.7, two scatter plots (a versus 3 and y versus a) show the following characteristics: i ) a large number of sub-pictures have high values for ct, 3 and y (larger than 0.5), i i ) the rest of the sub-pictures are grouped in two clusters, one where a > 3, the other where 3 > a. Similar results were obtained for the other pictures. 103. XXX XX X X X X 0.0 0.5 :.s 2.0 ALPHA X X x x X X X X X X >K X X X X X x X X * XXv x x x X X £ X X X X X X x 0.0 o.s I— 1.0 t.S 2.0 ALPHA i— 2.S -1 3.0 X X X X X x Fig. 7.7 E s t i m a t e d v a l u e s o f t h e c o r r e l a t i o n p a r a m e t e r s a , g and y o v e r 1 6 x 1 6 x 1 6 s u b - p i c t u r e s f o r t h e p i c t u r e FACE. ( 1 ) , ( 2 ) and (3) r e p r e s e n t t h e c a t e g o r i e s i n w h i c h t h e s u b - p i c t u r e s a r e c l a s s i f i e d as d e f i n e d on page 1 0 4 . 104. Three perspective plots of the parameters a, 3 and y of the sub-pictures at their corresponding position in the original picture are represented in Fig. 7.8. By comparing these plots with the original picture (Fig. 2.6c) the following facts can be noted: i) high values of the parameters a, 3 and y come from the same sub-pictures, or at least from the same areas of the picture. i i ) the areas weakly correlated (high parameters) are mostly dark areas. Such areas are very noisy and should not require accurate coding. The f i l t e r i n g effect caused by the processing should not affect the sub-jective quality of the picture. In conclusion, for the particular picture considered, three different kinds of sub-pictures were considered (see Fig. 7.7). 1) sub-pictures with horizontal features 2) sub-pictures with vertical features 3) noisy and dark sub-pictures. Each category was defined according to the following rules: 1) Category 1: a < 3 , 3<1.0, 3 < 0.25/a 2) Category 2: 3 < a, a < 1.0, 3 < 0.25/a 3) Category 3: a l l the other sub-pictures. Since category 3 represents mainly the noisy or dark areas, a smaller number of b.p.p.e. was assigned to code those areas. This opera-tion allowed the allocation of a higher number of b.p.p.e. for other areas. For the picture FACE, the distribution of sub-pictures cate-gories were as follows (Table 7.4); 105. Fig. 7.8 Respective plots of the correlation parameters a, B and y estimated over 16x16x16 sub-pictures for the picture FACE. 106. 1 3 1 1 3 1 1 2 1 2 3 1 3 1 3 3 1 2 1 1 1 1 1 2 1 3 1 1 3 1 3 3 2 2 2 2 2 2 3 3 1 3 1 1 3 3 3 3 1 2 1 3 2 1 3 3 1 3 1 1 3 3 3 3 3 1 1 3 2 2 2 2 3 3 1 1 1 3 3 3 3 1 1 3 3 3 3 3 3 3 1 3 1 3 3 3 2 2 2 3 3 2 2 2 3 2 2 3 3 3 3 3 3 3 1 3 3 1 2 1 3 1 1 1 3 3 3 3 3 1 1 3 3 1 2 1 3 1 1 3 1 1 3 3 1 1 1 3 3 1 1 1 1 2 1 1 1 1 3 3 ' 2 2 2 3 3 3 1 1 1 1 1 1 1 1 2 1 1 1 3 3 3 3 3 1 1 1 1 1 2 2 2 1 1 3 3 3 3 3 3 3 2 2 3 3 2 2 3 1 1 1 3 1 2 2 3 2 3 2 1 1 3 2 2 1 2 1 2 2 1 1 2 1 1 1 1 1 3 3 3 2 2 2 2 2 1 2 2 2 1 1 1 1 3 3 3 3 Table 7.4 Distribution of the categories of sub-pictures in the picture FACE. There are 99 sub-pictures in category 1, 56 in category 2 and 101 i n category 3. The correlation parameters averaged in each category are l i s t e d in Table 7.5. CATEGORY NUMBER 1 2 3 a 0.118 0.561 2.54 3 0.565 0.155 3.47 Y 0.151 0.133 2.74 Table 7.5 Average correlation parameters for each category of sub-picture, for the picture FACE. 3.25 b.p.p.e. were allocated to each sub-picture in categories 1 and 2. 2.00 b.p.p.e. were allocated to each sub-picture in category 3. This gave an average of 2.75 b.p.p.e., plus a very small number of bits to transmit the category of the sub-picture to the receiver. The picture FACE, processed this way i s shown on Fig. 7.9(b) and i s to be compared with the same picture processed normally as i n 107.a Fig. 7.9 (a) Transform processed picture 2.75 b.p.p.e. 16 x 16 x 6 (a) Transform processed picture 2.75 b.p.p.e. 16 x 16 x 6 Adaptive process 108. Chapter 6 ( F i g . 7.9 (a)) with the same number of b.p.p.e. The measured S/N r a t i o i s s l i g h t l y lower, 12.27 dB, compared to 12.37 dB i n the f i r s t case, but the subjective q u a l i t y i s improved i n the contrasted areas .around the c o l l a r of the s h i r t , and the use of a high number of b.p.p.e. -on some sub-pictures suppressed the edge e f f e c t [32]-The implementation complexity of such a system would be c o n s i -derable. I f the non adaptive system can be r e l a t i v e l y e a s i l y set up to process a c e r t a i n kind of p i c t u r e , the adaptive system has to estimate the c o r r e l a t i o n parameters of each sub-picture before processing. Methods are published i n [33]. An output b u f f e r i s also required to give uniform transmission rate. 7.5 E f f e c t of D i g i t a l Channel Errors on Performance: I t can be shown that a d d i t i v e white noise i n the frequency domain i s equivalent to a d d i t i v e white noise i n the time domain of the same power, i n terms of image degradation[34]. Also, i t can be argued that frequency-domain quantization i s l e s s damaging on a subjective basis than time-domain quantization [34]. I t has been thought by some [24,35] that, p o s s i b l y , channel e r r o r s of any type are l e s s d i s r u p t i v e to subjective q u a l i t y when occuring i n the frequency domain than i n the time domain. With t h i s i s s u e i n mind and i n order to a s c e r t a i n the v u l n e r a b i l i t y to noise of the source coding system we studied here, the experiments described below were conducted. The system represented i n F i g . 7.10 has been simulated. .The p i c t u r e s were three-dimensional transform encoded. An average of 3 b.p.p.e. was used, which provides reconstructed p i c t u r e s of reasonable q u a l i t y . A r e l a t i v e l y high value of the error p r o b a b i l i t y , . „pe=0..01,. was chosen i n order to emphasize the e f f e c t of channel noise. 109. Quant NOISY CHANNEL F i g . 7.10 Transmission of transform encoded pi c t u r e s over a noisy channel. The p i c t u r e s processed with the above system are shown i n F i g . 7.11. The S/N r a t i o s of the 3 b.p.p.e. transform encoded p i c t u r e s , with and without d i g i t a l channel e r r o r s , are l i s t e d i n Table 7.6. Transform encoded pict u r e s 3 b.p.p.e. S/N dB S/N dB E r r o r l e s s Channel Channel Errors Gl 8.92 6.28 G3 9.46 5.62 F 12.38 10.22 H 13.45 7.27 TP 17.85 10.38 B 11.10 7.44 Table 7.6 S/N r a t i o s obtained by transmitting 3 b.p.p.e. transform encoded p i c t u r e s over a noisy BSC channel. F o r t h i s experiment, the average l o s s i n S/N r a t i o due to d i g i t a l channel errors was approximately 4 dB. In order to assess the r e l a t i v e influence of each transform sample, i t w i l l be assumed that t h e e f f e c t of channel errors on each Fourier samples can be evaluated p Fourier Filtering Transform P 110.a Fig. 7.11 Effect of d i g i t a l channel errors on 3 b.p.p.e. three-dimensional Fourier transform encoded pictures; per-digit error probability pe=0.01. Sub-picture size: 16 x 16 x 6. 110.b 1 1 1 . separately. The l o s s i n S/N r a t i o i s expected to depend on the variance of the sample and the number of quantization used to transmit that sample. A few experiments were performed on the p i c t u r e GARDEN1. The S/N r a t i o (4.18) of a 3 b.p.p.e. transform encoded p i c t u r e was 8.92 dB. I t became 6.28 dB with the d i g i t a l channel errors where p g = 0.01. I f the noise was suppressed on a l l the Fourier samples except the D.C. component, the new S/N r a t i o was 7.30 dB which represents a l o s s of 1.62 dB due to the D.C. component. I f the noise was suppressed on a l l Fourier samples except the f i r s t i n the h o r i z o n t a l d i r e c t i o n : ZR(2,1,1) + j ZI(2,1,1) the S/N r a t i o became 8.75 dB which represents a l o s s of 0.17 dB. The l o s s i n S/N r a t i o due to d i g i t a l channel errors i s v i r t u a l l y independent of the average number of b.p.p.e. used i n the transmission. In any s i t u a t i o n , whatever the average number of b.p.p.e., the most important samples are to be transmitted using a large number of b i t s and they are responsible f o r most of the e r r o r . A few experiments on some pictures showed that f o r 1, 2 or 3 b.p.p.e. the l o s s i n S/N r a t i o due to channel errors can be considered constant. Subjectively, the erroneous transmission of the D.C. component i s undoubtedly very damaging. Very b r i g h t or very dark sub-pictures are very noticeable. The e f f e c t of channel errors on high frequency compo-nents i s l e s s damaging. The subjective e f f e c t of such p e r i o d i c noise depends on the frequency of the noise, the s i z e of the sub-pictures, the viewing distance. I t must be remembered that p & = 0.01 i s a very high value for an e r r o r p r o b a b i l i t y . The use of e r r o r detecting codes would become p a r t i c u l a r l y e f f i c i e n t In the case of transform encoding e s p e c i a l l y i f they are applied on the few transform samples with high variances. 112. For reference, an example of the subjective degradation caused by d i g i t a l channel errors i n the time-domain i s shown i n F i g . 7.12. The o r i g i n a l p i c t u r e s were PCM transmitted over a noisy BSC channel with an e r r o r p r o b a b i l i t y of 0.01. In t h i s case, i t must be noted that the b i t rate i s very high: 48 b.p.p.e. I f the p r o b a b i l i t y d i s t r i b u t i o n of the b r i g h t -ness i s uniform or symmetrical with respect to the mean, the mean square e r r o r e 2 due to channel noise i s [361: (7.3) *where N i s the number of b i t s i n each codeword and p g the e r r o r p r o b a b i l i t y . For N = 8 and p g = 0.01, (7.3) gives e 2 = 218.45. The brightness p r o b a b i l i t y d i s t r i b u t i o n s f o r the pi c t u r e s used i n t h i s thesis do not s a t i s f y exactly the conditions f o r the v a l i d i t y of (7.3). However as shown i n Table 7.7, ac t u a l measurements of e 2 y i e l d e d r e s u l t s which f i t t e d (7.3) almost p e r f e c t l y . BSC p. = 0.01 e (S/N) dB Gl 223.66 5.82 G3 224.15 4.16 F 223.55 7.00 H 221.66 10.52 TP 222.57 13.55 B 228.80 6.71 "Table 7.7 Mean square e r r o r and s i g n a l to noise r a t i o due to d i g i t a l e rrors on the PCM transmission of the o r i g i n a l data. Some considerations on the subjective e f f e c t of such noise can be found elsewhere [14,15]. 113.a Fig. 7.12 Effect of d i g i t a l channel errors on •PCM transmitted original data; per-digit error probability p e=0.01. 114. 7.6 Discussion of Results: From a l l the preceding experiments, the following conclusions can be drawn: 1) The use of the s p e c i a l quantizer more adapted to the s t a t i s t i c s of the D.C. component of the Fourier transform increased considerably the subjective q u a l i t y of the processed p i c t u r e . 2) For some pict u r e s i t i s p o s s i b l e to obtain a more accurate pre-d i c t i o n of the mathematical performance by using a non-s-aparable model fo r the c o r r e l a t i o n function. Unfortunately the simulation i s very expensive. One must remember, from Chapter 6, that the simple exponen-t i a l model provides a set of variances allowing the choice of the most important Fourier samples as w e l l as the b i t a l l o c a t i o n which gives a near optimum S/N r a t i o (within 10% f o r 2.75 b.p.p.e). 3) Using the actual variances of the Fourier samples f o r deciding on the quantization of the Fourier samples l e d to a s l i g h t l y l a r g e r S/N r a t i o (gain of 0.2 dB) for h a l f of the p i c t u r e s . The use of a more so p h i s t i c a t e d model f o r the a u t o c o r r e l a t i o n function would not increase s i g n i f i c a n t l y the q u a l i t y of the processed p i c t u r e s . 4) An adaptive system transmitting more information to the r e c e i v e r on the p a r t i c u l a r area of the p i c t u r e which i s being processed seems to improve somewhat the subjective q u a l i t y of processed high-contrasted sub-pictures. The system i s , however, much more complex. The s t a t i s t i c s of the data must be l o c a l l y estimated before processing. 115. 5) D i g i t a l channel errors are very damaging to the subjective q u a l i t y of the transform encoded p i c t u r e s . The threshold p r o b a b i l i t y of err o r under which the subjective e f f e c t i s not damaging has to be found. The l o s s i n S/N r a t i o i s r e l a t i v e l y independent of the number of b.p.p.e. used to trans-mit the p i c t u r e . Since most of the subjective e f f e c t i s due to the erroneous transmission of the D.C. component, there i s no noticeable s h i f t i n the colour.. 6) The r e s u l t s obtained a f t e r the processing of the same data on a two-dimensional processing system was a v a i l a b l e from an e a r l i e r study [19]. Y,I and Q planes were processed through two-dimensional F o u r i e r and Hadamard transform encoding systems. Optimum Max quantizers adapted to a Gaussian d i s t r i b u t i o n and the b i t a l l o c a t i o n (5.3) were used. Eight b i t s were a l l o c a t e d to the D.C. component of the Y plane. Some r e s u l t s are compared i n F i g . 7.13 with the same p i c t u r e s FACE and HOUSE processed by our three-dimensional transform encoding system using the same number of b.p.p.e. (2.75 b.p.p.e., 2.0 b.p.p.e. f o r the Y plane, 0.375 b.p.p.e. f o r the I and Q planes) and the same s p a t i a l sub-picture s i z e . The three-dimensional Fourier process y i e l d e d s i g n i f i c a n t l y higher q u a l i t y p i c t u r e than the two-dimensional Fourier transform process. The s p a t i a l : d e t a i l s r e n d i t i o n i n the two-dimensional Hadamard transformed p i c t u r e s i s s i m i l a r to that of the three-dimensional processed p i c t u r e s . In some -conditions, the three-dimensional Hadamard transforming may y i e l d b e t t e r r e s u l t s than the three-dinensional Fourier transforming. The Hadamard transform i s b e t t e r suited to process the p i c t u r e s of the same type than the H O U S E . A two-dimensional system i s more complex than the three-dimensional system i n the sense that i t requires two processors: one adapted to the Y component, and one adapted to the I and Q components 116. a F i g . 7.13 (a)(b) Two-dimensional Hadamard transformed pictures 2.75 b.p.p.e. (Y: 2.00 b.p.p.e., I,Q: 0.375 b.p.p.e.) 16 x 16 (c)(d) Two-dimensional Fourier transformed pictures 2.75 b.p.p.e. (Y: 2.00 b.p.p.e., I,Q: 0.375 b.p.p.e.) 16 x 16 (e)(f) Three-dimensional Fourier transformed pictures 2.75 b.p.p.e. 16 x 16 x 6 116*1> 1 1 7 . (which have, in general, the same s t a t i s t i c s ) . 7) It is likely that some pictures could be transmitted using fewer than 2 b.p.p.e. For instance for the picture FACE, the 2 b.p.p.e. pic-ture yields reasonably good subjective quality. (Fig. 7.14-c). It must be recalled that those pictures are to be viewed at a distance of about 25 inches. In the same Figure, the pictures FACE transmitted with 1.0 and 1.5 b.p.p.e. are presented. 8) The "bad quality" of the processed pictures is mainly inherent to spatial dimensions. Besides a hardly noticeable loss in saturation, the colour of processed pictures is not modified so as to be subjectively damaging (for 2.75 b.p.p.e). In order to improve the transmission of the information pertaining to the spatial dimensions, without increasing the average number of b.p.p.e., the following experiments were performed. The set of estimated variances computed from the model were modified so that algorithm (5.3) allocated relatively more bits to the Fourier samples pertaining to the spatial dimensions. A new set c: variances al2(u,v,w) was created in the following way: o,2(u,v,w) = a2(u,v,w)/k (7.1) where: a2(u,v,w) is the original set of variances. k = l for w = 1 k = kj for w = 2,6 k = k 2 for w = 3,5 k = k 3 for w = 4 and k.3 > k£ • > kj > 1 This operation decreased the values of the estimated variances for large values of w. Various values of k}, k 2 , k 3 were tried. The loss i n colour saturation of pictures processed using the new b i t allocation, was not j u s t i f i e d by a non significant gain i n spatial detail rendition. Simple attempts to enhance the colour of such pictures did not lead to any satisfy results. 118.a Fig. 7.14 Three-dimensional Fourier transform processed picture FACE: 16 x 16 x 6. (a) 1.0 b.p.p.e. (b) 1.5 b.p.p.e. (c) 2.0 b.p.p.e. 119 VIII THREE-DIMENSIONAL TRANSFORM ENCODING OF MONO- CHROMATIC MOVING PICTURES 8.1 Introduction: Study of time varying monochromatic pictures has been limited mainly because of the large amount of storage required i f interframe en-coding is considered. Some attention has been given 'o the transmission of the difference signal and to refreshing techniques [37]. However, corre-lation between several frames has not been fully exploited. One expects the correlation between picture elements in the frame-to-frame time dimen-sion to be very high, especially in the case of the typical picturephone head and shoulder view of a person. The Walsh/Hadamard transformation was not used by us for the processing of colour pictures since the dimension in the wavelength direction was not a power of two. For time varying pictures the number of frames is arbitrary. The simplicity of implementation of the Hadamard transform makes i t the more, likely to be used in practical systems [38]. The algorithm used in this study to compute the three-dimensional Hadamard transform was extended from the method outlined in [26]. 8.2 Data Base and Data Statistics; 0. Jensen 139] obtained several samples of time varying imagery data. Eight consecutive frames of his data, shown in Fig. 8.1, were ran-domly chosen, (SCENE1 in Fig. 8.1). The third dimension is now time and as in chapter 2, correlation coefficients were estimated and the simple exponential model was least square fitted to the estimated points to obtain the parameters a, 3 and y. Results are plotted in Figs. 8.2, 8.3. The following parameters were obtained: a = 0.056 3=0.045 y =0.189 120. a Fig. 8.1 Original data SCENE1. Eight consecutive frames taken at 24 frames per second, quantized to 8 b i t s . 256 x 256 elements. 120. b SCENE 1 RLPHR= 0.056 o.o 7.0 4.0 6.0 8.0 X DISPLACEMENT 10.0 12.0 14.0 I o o SCENE 1 BETR= 0.045 F1 = • F2 = CD F 4 = 4 -F5=X fl> = <r> 0.0 - 1 — 2.0 1— 4.0 -1 6.0 -1— 8.0 I 10.0 —T 12.0 -1 14.0 / DISPLACEMENT Fig. 8.2 Correlation coefficient along the spatial dimensions for SCENE1 (Fig. 8.1) estimated on 6 frames (F1.F2,...,F6) and least-square f i t of the exponential model. -5.0 DISPLACEMENT SCENE1 GRMMR= 0.189 Fig. 8.3 Correlation coefficient along the time-dimension of SCENE1 (Fig. 8.1) estimated on 6 frames (F1.F2,...,F6) and least-square f i t of the exponential model. 123. It can be noted that in this case, the estimated correlation coefficients are much less dependent on time than were the correlation coefficients on A for colour pictures. 8.3 Experimental Results: Fig. 8.4 shows the S/N ratio as a function of the number of transmitted transform samples. In theory, from the estimated variances, the Fourier and the Hadamard transform should yield the same S/N ratio for that specific set of frames. From the actual variances of the transform samples, the Fourier transform should give better results. The eight frames were transformed and the transform samples quantized using the quantizers designed for the colour pictures. Results appear in Fig. 8.5 for the Fourier transform and in Fig. 8.6 for the Hadamard transform. For the eight frames, 8 b.p.p.e (.1 b ..p .p. e. per frame) were used. It i s very d i f f i c u l t to assess the subjective quality of the processed pictures. One must remember that those pictures should be viewed at a distance of approximately 25 inches at a rate of approximately 24 frames per second. There seems to be no noticeable difference in the qua-l i t y of the pictures processed using either transform. The S/N ratio actually measured at 1 b.p.p.e. per frame i s 10.99 dB for the Fourier transform and 10.91 dB for the Hadamard transform. For 8 b.p.p.e. and for the Fourier transform, 539 transform samples are transmitted with the following b i t allocation: 33 samples with 7 bits 43 samples with 6 bits 70 samples with 5 bits 134 samples with 4 bits 191 samples with 3 bits 68 samples with 2 bits 124. S/N RATIO SCENE 1 16X16X8 'ROM PROCESSED PICTURES ~4H\ • VFROM ACTUAL VARIANCES <JFJ WITH QUANTIZATION j 8BPPE FROM A&WAL R1ANQES (.NO QUANTIZATION) 204.8 Fig. 8.4 S/N ratio as a function of the number of transmitted samples for the Hadamard and the Fourier transforms for the SCENE1 (Fig. 8.1) from the estimated variances and from the normalized actual variances. The actual S/N ratio for 8 b.p.p.e. (5 39 samples) i s shown and compared to the results predicted by the actual variances, the quantization being taken into account. 1 2 5 . These values are almost identical for the Hadamard transform. For such a high number of samples transmitted with a small number of b i t s , the effect of quantization i s more important. Equation 5.4 predicts a S/N ratio of 15.6 dB for the Fourier transform and 13.9 dB for the Hadamard transform. However, the main reason why actual results are not closer to the maximum obtainable S/N ratio is due to the fact that, for that set of frames and for such a high number uf transmitted transform samples, the simple expo-nential model does not predict properly the ranking of the actual variances. Consequently a high number of samples with high variances are rejected or transmitted with less bits . To really assess the quality of the processed pictures, a large number of frames would have to be processed, displayed and projected. It seems that fewer than 1 b.p.p.e. per frame w i l l be sufficient to transmit highly correlated data such as a head and shoulder view of a person. Digital channel errors could be very damaging on transform pro-cessed time varying pictures. In PCM transmitted pictures, an error is vis i b l e only during one frame, and the frequency of the projection should decrease the subjective effect of such errors. In a transform encoding system, an erroneous sub-picture would be apparent for a number of frames equal to the dimension of the blocks in the time dimension. 8.4 Conclusion: More experiments are required to ful l y assess the subjective quality of transform encoded time varying monochromatic pictures. The easily implemented Hadamard transformation could be used, since i t yielded similar results to those of the Fourier transform for the particular set of frames used in this thesis. 126. a Fig. 8.5 Eight frames of SCENE 1 (Fig. 8.1) three-dimensional Fourier transformed using an average of 1 b.p.p.e. per frame. 126.b 127.a Fig. 8.6 Eight frames of SCENE 1 (Fig. 8.1) three-dimensional Hadamard transformed using an average of 1 b.r-P«e. per frame. 127. b 128 IX CONCLUSION 9.1 Summary of Results A colour picture was considered as a three-dimensional process U(x,y,A); U the brightness i s a function of the spatial dimensions x, y, and of the wavelength A. A set of six "high quality" colour pictures was digitized. 256 x 256 points were sampled in the spatial dimensions and 6 points in the wavelength dimension. The study of the st a t i s t i c s of this data showed that the choice of a model for the autocorrelation function depends strongly on the type of data. 1) The following non-separable function provides a reasonable f i t to the autocorrelation funct:on of weakly correlated data lacking of horizontal or vertical features. RAx,Ay,AA = ( e xP{"K ajAx) 2 + ( f^Ay) 2 + (yAA)2]*} + exp{-[(a 2Ax) 2 + ( B 2Ay) 2 + (yAA) 2]^})/2.0 (9.1) 2) If the data i s highly correlated in the spatial dimensions a single parameter suffices to define the model i n the spatial direction. The function, RAx,Ay,AA = exp[-((aAx) 2 + ($Ay)2)^].exp(-y|AA| ) (9.2) provided a reasonable f i t to the typical head and shoulder view of a person. 3) The following separable model RAx,Ay,AA = exP(~aIAx|).exp(-£|Ay|).exp(-y|AA|) (9.3) 129. provides a reasonable f i t to strongly correlated data having v e r t i c a l or horizontal features. If the data is weakly correlated in the spatial dimensions with vertical or horizontal features, then the following model provides a closer f i t : RAx Ay AA = [exp (-04 | Ax| ) + exp (-ct2 | Ax| ) ] [exp (-gj1 Ay [ ) + exp ( -0 2 I Ay[)].exp(-YIAAI)/4.0 (9.4) Experiments on the three-dimensional Fourier transform encoding of the above defined colour pictures were performed. The variances estimated using '-he model for the autocorrelation function were used to assign the number of bits and to adapt the quantization to each of the Fourier samples. The following conclusions can be drawn: 1) In block quantization the incorrect transmission of very bright areas i s subjectively very damaging. It i s very important to properly adapt the quantizer of the D.C. Fourier component. 2) For colour pictures which use fewer than 3 b.p.p.e. the single exponential separable model (9.3) orders the Fourier samples in terms of variances, but does not accurately predict the S/N. 3) A more complex model (9.1) providing a better f i t to the autocorrelation function gives a better prediction of the S/N but seems not to significantly im_rove either the S/N or the subjective quality of the reconstructed picture. 4) An average number of 2.75 b.p.p.e. yields a reasonably good reconstructed picture. Colour rendition is good. The only unpleasant characteristics came from highly contrasted areas. 130. 5) The subjective quality of highly contrasted areas was somewhat improved by adapting the process to the area. The sub-pictures were classified in categories representing the direction of strong correla-tion. 6) The effect of d i g i t a l channel errors on transform encoding i s very damaging, and virtually independent on the average number of b.p.p.e. used to transmit the picture. There is no noticeable s h i f t i n the colour of the noisy picture. 7 ) In the experiments performed by us on time-varying monochroma-t i c pictures, the Fourier transformation should theoretically yield significantly better results than the Hadamard transformation for our set of pictures. However, experiments and subjective viewing indicated that the two transforms give very similar results. It was found that for a large number of transmitted samples the transform samples are not always properly ordered by the single exponential model (9 .3) . 9 . 2 Suggestions for Future Research 1) A one-to-one relationship between S/N ratio and subjective quality remains to be found for three-dimensional pictures (colour or monochromatic time-varying). 2 ) For the Fourier transformation, instead of transmitting the real and imaginary part of a Fourier component i t i s possible to trans-mit i t s phase and amplitude. In this case, i t may net be necessary to code the amplitude with as many bits as the phase. However, the effect of d i g i t a l channel errors might be more damaging. 3) The same process as the one used in this thesis can be applied to the RGB tristimulus components. 131. 4) The subjective effect of di g i t a l channel errors on the three-dimensional transform encoded picture, as a function of the per-digit error probability, needs further study. The subjective effect of channel errors w i l l be transform dependent. 5) It seems that for time-varying monochromatic pictures i t i s necessary to transmit a large number of transformed samples. In such a case, the prediction of the rank of the variances of the transform samples becomes more important and i t might be necessary to use a more complex model. 6 ) From [ 2 1 ] , the two-dimensional Hadamard transformation yielded better results than the two-dimensional Fourier transformation on colour pictures. Using a three-dimensional Hadamard transformation may yie l d better results than the three-dimensional Fourier transformation for some types of pictures. APPENDIX A Some s t a t i s t i c s of source data and histograms of i n t e n s i t y l e v e l s f o r the pict u r e s GARDEN3, FACE, HOUSE, TEST PATTERN, BUILDING. n a Gl 40.37 28.67 G3 37.59 24.17 F 42.36 33.43 H 75.54 49.99 TP 98.31 71.05 B 52.06 32.31 Table A . l Mean and Standard deviation of the brightness of the source p i c t u r e s . 133. n A i aX-Ai 3 0 . 8 0 1 7 . 2 8 X2 3 5 . 6 6 2 1 . 4 7 Gl A 3 3 7 . 0 1 2 6 . 2 5 A H 4 1 . 9 6 3 2 . 0 2 A5 4 2 . 3 4 3 6 . 5 0 Afi 5 4 . 4 4 2 8 . 2 4 Al 3 8 . 0 2 1 8 . 0 1 X2 3 9 . 0 1 2 2 . 7 4 G3 A 3 3 0 . 5 9 2 3 . 8 6 X^ 3 3 . 9 4 2 6 . 3 0 A5 3 4 . 0 4 2 7 . 1 9 Afi 4 9 . 9 2 2 0 . 8 4 Al 4 5 . 3 5 2 6 . 3 7 X2 4 6 . 4 7 3 6 . 1 1 V A 3 3 6 . 1 1 3 6 . 3 3 r Xif 3 1 . 5 0 3 2 . 3 6 A5 3 7 . 1 - 3 4 . 6 3 Afi 5 7 . 5 9 2 6 . 4 1 Al 7 7 . 9 6 4 2 . 0 6 X2 9 8 . 4 9 5 5 . 6 7 H A 3 8 3 . 2 6 5 7 . 0 4 A H 6 8 . 1 0 5 3 . 3 9 A5 6 0 . 0 5 4 5 . 9 6 AR 6 5 . 4 9 3 0 . 7 6 Al 7 3 . 0 5 5 6 . 5 4 X2 9 9 . 5 3 7 3 . 9 1 TP A 3 1 0 2 . 7 7 7 8 . 1 2 A4 1 0 0 . 1 6 7 7 . 3 7 A5 1 0 8 . 5 3 7 2 . 6 5 * G 1 0 5 . 8 4 5 8 . 6 1 Al 6 0 . 4 7 2 9 . 9 0 X 2 7 7 . 4 1 4 0 . 7 5 B A 3 5 2 . 2 1 3 0 . 6 4 A H 3 6 . 0 8 2 4 . 3 6 A5 3 6 . 2 8 2 4 . 8 9 Afi 4 9 . 9 1 1 8 . 3 1 Table A.2 Mean and Standard Deviation of the brightness for each X^. 134. F i g . Al Histograms of i n t e n s i t y l e v e l s f o r each colour plane and f o r the e n t i r e p i c t u r e f o r the p i c t u r e GARDEN3. 135. 255.0 INTENSITY LEVEL INTENSITY LEVEL 255.0 F i g . A2 Histograms of Intensity l e v e l s f o r each colour plane and f o r the en t i r e p i c t u r e f o r the p i c t u r e FACE. 136. F i g . A 3 Histograms of i n t e n s i t y l e v e l s f o r each colour plane and f o r the e n t i r e p i c t u r e f o r the p i c t u r e H O U S E . • 137. INTENSITY LEVEL INTENSITY LEVEL Fig. A4 Histograms of intensity levels for each colour plane and for the entire picture for the picture T E S T P A T T E R N . 138. BUILDING VIOLET BLUE 0.0 64.0 128.0 INTENSITY LEVEL 192.0 1 256.0 11 i D z U J CC ZD (_) O o i O o o BUILDING ?ELL0V 0.0 64.0 ' 128.0 INTENSITY LEVEL - | 192.0 256.0 BUILDING ORANGE RED r 0.0 64.0 128.0 INTENSITY LEVEL 192.0 255.0 1 : — r 64.0 128.0 INTENSITY LEVEL 192.0 256.0 Fig. A5 Histograms of intensity levels for each colour plane a n d for the entire picture for the picture BUILDING. 139. APPENDIX B 1. Estimated correlation coefficient along the spatial dimensions for the pictures FACE, HOUSE, TEST PATTERN and BUILDING (3.7) and least square f i t of the exponential model. Figs. B l , B2, B3, B4. 2. Estimated correlation coefficient along the wavelength dimension for the pictures FACE, HOUSE, TEST PATTERN and BUILDING (3.10), and least square f i t of the exponential model. Figs. B5, B6. 3. Comparative f i t of separable and Non-separable model to estimated diagonal spatial correlation coefficient for pictures TEST PATTERN and BUILDING. Fig. B7. 4 . Correlation coefficient in the wavelength dimension, assuming station-arity, for the pictures HOUSE, TEST PATTERN and BUILDING. 144. 145. Fig. B6 Correlation coefficient in the A direction for the pictures TEST PATTERN and BUILDING. F i g . B7 Comparative f i t of separable and non-separable model to estimated diagonal s p a t i a l c o r r e l a t i o n c o e f f i c i e n t f o r the pictures TEST PATTERN and BUILDING. ON Fig. B8 Correlation coefficient in the wavelength direction, assuming stationarity, for the pictures HOUSE, TEST PATTERN and BUILDING. i—1 148. APPENDIX C Some Examples o f the B i t A l l o c a t i o n o f the F o u r i e r Samples. The p u r p o s e o f t h i s a p p e n d i x i s t o g i v e a few examples o f the b i t a l l o c a t i o n schemes computed i n c h a p t e r 5. I t i s u s e f u l , f i r s t , t o become f a m i l i a r w i t h t h e n o t a t i o n and f o r m a t o f t h e r e s u l t s . F i r s t , c o n s i d e r a t w o - d i m e n s i o n a l 4 x 4 p i c t u r e : a l l a12 a13 a l 4 a21 a22 a23 a2k a31 a32 a33 a3k a 4 l a42 ai+3 a H H where the a^j a r e the v a l u e s o f the b r i g h t n e s s f o r t h e p i c t u r e element a t x-= i and y •= j . The -Fas?: - F o u r i e r t r a n s f o r m o f t h i s p i c t u r e y i e l d s 16 complex numbers: Z R n + J Z I 1 1 Z R 1 2 + J Z I l 2 Z R 1 3 + J z I l 3 Z R 1 2 " J Z I 1 2 Z R 2 1 + j z i 2 1 Z R 2 2 + j ^ I 2 2 Z R 2 3 + J Z I 2 3 - 3 Z I 2 2 Z R3 i + J Z I 3 1 Z R 3 2 + J Z I 3 2 Z R 3 3 + J Z I 3 3 Z R 3 2 " J Z I 3 2 + J Z I 4 i Z R ^ 2 + j Z I ^ Z R H 3 + 3 z I H 3 Z R ^ 2 - J Z I 4 2 The above m a t r i x has i n f a c t 32 numbers. T a k i n g i n t o a c c o u n t t h a t some complex numbers a r e c o n j u g a t e s y m m e t r i c o f o t h e r numbers, o r ar e r e a l , t h e 16 u s e f u l r e m a i n i n g numbers a r e as f o l l o w s : ZRn ZR 1 2 + j Z I 1 2 Z R 1 3 ZR 2i + j Z I 2 1 Z R 2 2 + j Z I 2 2 Z R 2 3 + j Z I 2 3 ZR 3 1 ZR 3 2 + j Z I 3 2 ZR 3 3 ZRi»2 + j Z I 1 + 2 In t h i s t h e s i s , t h e r e s u l t s w i l l be p r e s e n t e d as shown above. A s i m i l a r r e p r e s e n t a t i o n w i l l be use d i n t h e t h r e e - d i m e n s i o n a l c a s e . F o r 149, a 4 x 4 x 4 picture the results would be presented as follows Z R i n (ZR + JZD121 ZR131 ( Z R + jZI)ii2 (ZR + JZD122 ( Z R + JZD132 (ZR + j Z I ) 1 4 2 Z R l l 3 (ZR + j Z I ) 123 ZR133 ZR + j Z I ) 2 n Z R 3 1 1 ZR + j Z I ) 2 2 1 ( Z R + 3 Z I)3 2 1 ZR + j Z I ) 2 3 i Z R 3 3 1 ZR + j Z I ) 2 1 t l ZR + J Z I ) 2 1 2 (ZR + J Z D 3 1 2 ZR + j Z I ) 2 2 2 (ZR + J Z D 3 2 2 ZR + j Z I ) 2 3 2 (ZR + j Z I ) 3 3 2 ZR + j Z I ) 2 i f 2 ( Z R + j Z I ) 3 i t 2 ZR + j Z I ) 2 i 3 Z R 3 1 3 ZR + j Z I ) 2 2 3 (ZR + j Z I ) 3 2 3 ZR + j Z I ) 2 3 3 Z R 3 3 3 ZR + j Z I ) 2 t t 3 ZR + j Z I ) 2 1 t t ZR + j Z I ) 2 2 4 ZR + J Z D 2 3 4 ZR + j Z I ) ^ Number of samples 16 24 16 Total: 64 The bit allocation for the various picture formats used in chapter 5 for a = 3 = y = 0.06 and for 3 b.p.p.e. are as follows: 1) Single 8 x 8 frame: 150. V \^ 1 2 3 4 5 1 7 44 00 00 3 2 44 00 00 00 00 3 03 00 00 00 00 4 00 00 00 00 00 5 3 00 00 00 0 6 00 00 00 7 00 00 00 8 00 00 00 The above represents 32 bits per frame, 192 bits per 6 frames and 3 b.p.p.e., since there are 8 x 8 = 64 picture elements. 2) The following table represents the bit allocation i n the case of the three-dimensional processing of an 8 x 8 x 6 picture. 1 5 1 . w \ u 1 2 3 4 5 Numbe r v \ o f b i t s 1 7 77 66 65 6 2 77 44 0 3 00 0 0 3 6 6 0 3 00 00 0 0 1 4 65 00 0 0 0 0 0 0 T O O X 5 6 00 0 0 0 0 0 I z Z 6 0 0 00 0 0 7 30 0 0 0 0 8 5 4 30 0 0 1 77 44 00 00 0 0 2 44 0 0 0 0 00 0 0 3 0 0 00 0 0 0 0 0 0 o 4 0 0 00 0 0 00 00 Z 5 00 0 0 0 0 0 0 0 0 J O 6 00 00 0 0 00 0 0 7 0 0 0 0 0 0 00 00 8 4 4 0 0 0 0 00 00 1 66 0 0 0 0 0 0 0 0 2 0 3 00 00 00 0 0 3 00 0 0 00 0 0 00 o 4 0 0 00 0 0 0 0 00 ^ H J 5 00 0 0 0 0 0 0 00 Xo 6 0 0 00 0 0 0 0 00 7 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 1 6 0 0 0 0 00 0 2 00 0 0 0 0 0 0 00 3 0 0 0 0 0 0 0 0 0 0 A 4 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 6 0 0 0 0 00 7 0 0 0 0 0 0 8 0 0 0 0 0 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 3 0 0 0 0 0 0 C 4 0 0 0 0 0 0 n J 5 0 0 0 0 0 0 u 6 0 0 0 0 00 7 0 0 0 0 00 8 0 0 0 0 0 0 1 4 4 0 0 0 0 2 00 0 0 0 0 3 0 0 0 0 0 0 4 0 0 0 0 0 0 o u 5 0 0 0 0 0 0 o 6 0 0 0 0 00 7 0 0 0 0 0 0 8 0 0 0 0 0 0 T o t a l : 192 152. 3) Bit allocation for a single 16 x 16 frame. There are 192 bits per frame, 0.75 b.p.p.e. per frame. 1 2 3 4 5 6 7 8 9 1 7 66 55 44 44 43 43 43 4 2 66 44 33 22 01 00 00 00 00 3 55 33 00 00 00 00 00 00 00 4 44 22 00 00 00 00 00 00 00 5 44 02 00 00 00 00 00 00 00 6 43 00 00 00 00 00 00 00 00 7 43 00 00 00 00 00 00 00 00 8 43 00 00 00 00 00 00 00 00 9 4 00 00 00 00 00 00 00 0 10 00 00 00 00 00 00 00 11 00 00 00 00 00 00 00 12 00 00 00 00 00 00 00 13 00 00 00 00 00 00 00 14 22 00 00 00 00 00 00 15 33 00 00 00 00 00 00 16 44 33 22 00 00 00 00 In chapters 4 and 5, 4 consecutive frames were to be processed (comparison of 16 x 16 with 8 x 8 x 4 ) which represents an average of 4 x 0.75 = 3 b.p.p.e. 153. 4) Processing of an 8 x 8 x 4 p i c t u r e : 192 b i t s are to be transmitted f o r 64 p i c t u r e elements f o r an average number of 3 b.p.p.e. W 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 _8_ 1 2 3 4 5 6 7 _8_ 1 2 3 4 5 6 7 8 7 67 55 54 5 66 44 13 00 00 00 33 44 6 34 00 00 0 67 44 03 00 00 00 30 44 44 00 00 00 00 00 00 00 34 00 00 00 00 00 00 00 44 00 00 00 00 00 00 00 55 03 00 00 00 00 00 30 33 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 30 00 00 00 00 00 00 00 54 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 5 00 00 00 0 00 00 00 00 00 00 00 00 0 00 00 00 00 Number of b i t s 109 38 34 11 T o t a l : 192 APPENDIX D Histograms of Fourier samples for the p i c t u r e FACE 155. Fig. D . l H i s t o g r a m s o f F o u r i e r samples f o r t h e p i c t u r e FACE. 156. Z I U .2.1) fa) -f - " i—•——sn 1 t r -« .D -30.0 -15.0 0.0 , 15.0 30.0 45.0 (XIO2 J -45.0 -30.0 Z R U .3.1) (b) p-30.0 <S.O 21(1.3.1) (c) 7 1 rJU i > v — n r ^ s - e . j -m.o- -is.o o.o, is.o 1X10' ) 30.0 <5.0 i 1 r--45.0 -30.0 ZR(1.1 .2) ill fd) ZKl .1.2) fe) -«S .O -30.0 -15.0 0.0 „ 15.0 30.0 (X10 J 1 Z R C l . 1 . 3 ) ff) -e.o -30.0 30.0 43.0. Fig. D.2 Histograms of Fourier samples for the picture FACE. 157. o" 21(1.1.3) £ «M 8 o" J 1 1 1 r a ^ — " 1 r GARDEN1 -1S.0 0 .0 , . 15.0 (X10 J ) Z K l . l .3) FACE 1 -15.0 0 . 0 , 15.0 IX102 ) Fig. D.3 Histograms of Fourier samples. 1 5 8 . REFERENCES 1 . T.S. Huang, O.J. Tretiak, B. Prasada and Y. Yamaguchi, "Design Considerations in PCM Transmission of Low-Resolution Monochrome S t i l l Pictures", Proc. IEEE, Vol. 55, No. 3, pp. 331-335, March 1967. 2 . U.F. Gronneman, "Coding Color Pictures", Tech. Report 422, M.I.T., June 1964. 3 . A. Habibi, "Comparison of nth-Order DPCM Encoder With Linear Transformations and Block Quantization Techniques", IEEE Trans. Comm. Tech., Vol. COM-19, No. 6, pp. 948-956, Dec. 1971. 4. J.O. Limb, C.B. Rubinstein and K.A. Walsh, "Digital Coding of Color Picturephone Signals by Element-Differential Quantization", IEEE Trans. Comm. Tech., Vol. COM-19, No. 6, pp. 992-1005, Dec. 1971. 5. J.J.Y Huang and P.M. Schultheiss, "Block Quantization of Correlated Gaussian Random Variables", IEEE Trans. Comm. Syst., Vol. CS-11, pp. 289-296, Sept. 1963. 6. A. Habibi and P.A. Wintz, "Image Coding by Linear Transformation and Block Quantization", IEEE Trans. Comm. Tech., Vol. COM-19, No. 1, pp. 50-62, Feb. 1971. 7. P.A. Wintz, "Transform Picture Coding", Proc. IEEE, Vol. 60, No. 7, pp. 809-819, July 1972. 8. W.K. Pratt, "Spatial Transform Coding of Color Images", IEEE Trans. Comm. Tech., Vol. COM-19, No. 6, pp. 980-992, Dec. 1971. 9. W.K. Pratt, "Digital Color Image Coding and Transmission", USCEE Report 403, Univ. of Southern California, June 1971. 1 0 . W.K. Pratt, W.H. Chen and L.R. Welch, "Slant Transform Image Coding", IEEE Trans. Comm., Vol. COM-22, No. 8, pp. 1075-1093, Aug. 1974. 1 1 . C.B. Rubinstein and J.O. Limb, " S t a t i s t i c a l Dependence Between Components of a Differentially Quantized Color Signal", IEEE Trans. Comm., Vol. COM-20, No. 5, pp. 890-899, Oct. 1972. 1 2 . J.O. Limb and C.B. Rubinstein, "Plateau Coding of the Chrominance Component of Color Picture Signals", IEEE Trans. Comm, Vol. COM-22, No. 6 , pp. 812-820, June 1974. 1 3 . P.J. Ready and P.A. Wintz, "Information Extraction, SNR Improvement and Data Compression in Multispectral Imagery", IEEE Trans. Comm, Vol. COM-21, No. 10, pp. 1123-1130, Oct. 1973. 159. 14. T.S. Huang and M.T. Chikhaoui, "The E f f e c t of BSC on PCM P i c t u r e Q u a l i t y " , IEEE Trans. Info. Theory, V o l . IT-13, No. 2, pp. 270-273, A p r i l 1967. 15. W.K. P r a t t , "Binary Symmetric Channel E r r o r E f f e c t s on PCM Color Image Transmission", IEEE Trans. Info. Theory, V o l . IT-18, No. 5, pp. 636-643, Sept. 1972. 16. E.R. Kretzmer,. " S t a t i s t i c s of T e l e v i s i o n S i g n a l s " , B e l l Syst. Tech. Journal, V o l . 31, p. 763, July 1952. 17. W.F. Schreiber, "The Measurement of Third Order P r o b a b i l i t y D i s t r i b u t i o n of T e l e v i s i o n Signals", IRE Trans. Info. Theory, Vol. IT-2, pp. 94-105, Sept. 1956. 18. L.E. Franks, "A Model f o r the Random Video Process", B e l l Syst. Tech. Journal, pp. 609-630, A p r i l 1966. 19. C A . Seecheran, "Colour Image Coding Using Linear Transformation and Block Quantization", M.A.Sc. Thesis, E.E. , U.B.C., June 1974. 20. G.B. Anderson and T. Huang, "Piecewise F o u r i e r Transformation f o r P i c t u r e Bandwidth Compression", IEEE Trans. Comm. Tech. V o l . COM-19, No. 2, pp. 133-140, A p r i l 1971. 21. E.O. Brigham and R.E. Morrow, "The Fast Fourier Transform", IEEE Spectrum, Vol. 4, pp. 63-70, Dec. 1967. 22. W.T. Cochran and J.W. Cooley, "What i s the Fast Fo u r i e r Transform?" Proc. IEEE, V ol. 55, No. 10, pp. 1664-1674, Oct. 1967. 23. J . Pearl-, "On Coding and F i l t e r i n g Stationary Signals by Discrete Fourier Transforms", IEEE Trans. Info. Theory, Corresp., V o l . IT-19, pp. 229-232, March 1973. 24. W.K. P r a t t , J . Kane and H.C. Andrews, "Hadamard Transform Image Coding", Proc. IEEE, V ol. 57, No. 1, pp. 58-68, Jan. 1969. 25. H.F. Harmuth, "A Generalized Concept of Frequency and Some App l i c a t i o n s " , IEEE Trans. Info. Theory, V ol. IT-14, No. 3, pp. 375-382, May 1968. 26* A.J. B a i l l i e , "A T h e o r e t i c a l Study of Transform P i c t u r e Coding Systems and an Investigation of a New Measure of D i s t o r t i o n i n Processed Images", M.A.Sc. Thesis, U.B.C., 1973. 27. J . Max, "Quantizing f o r Minimum D i s t o r t i o n " , IRE Trans. Info. Theory, Vol. IT-6, pp. 7-12, March 1960. 160. 28. P.A. Wintz and A.J. Kurtenbach, "Waveform e r r o r c o n t r o l i n PCM Telemetry", IEEE Trans. Info. Theory, V o l . IT-14, pp. 650-661, Sept. 1968. 29. R.E. Totty and G.C. Clark, "Reconstruction E r r o r i n Waveform Trans-mission", IEEE Trans. Info. Theory, Corresp., V o l . IT-13, pp. 336-338, A p r i l 1967. 30. E. Froese, "Discrete Fourier Transformations", UBC Fourt, Computing Centre, UBC, Jan". 1970. 31. M. Tasto and P.A. Wintz, "Image Coding by Adaptive Block Quantization", IEEE Trans. Comm. Tech., V o l . COM-19, No. 6, pp. 957-971, Dec. 1971. 32. M. Tasto and P.A. Wintz, "Note on the E r r o r S i g n a l of Block Quantizers", IEEE Trans. Comm.i Concise Paper, pp. 216-219, March 1973. 33. A. Habibi and P.A. Wintz, "Estimation of C o r r e l a t i o n Functions by Stochastic Approximation", IEEE Trans. Aerosp. E l e c t r . Syst., V o l . AES-8, No. 3, pp. 327-337, May 1972. • 34. G.B. Anderson and T.S. Huang, "Frequency-Domain Image E r r o r s " , Pattern Recognition, Pergamon Press, V o l . 3, pp. 185-196, 1971. 35. E.J. C l a i r e , "Bandwidth Reduction i n Image Transmission", Communications Conference, S e a t t l e , pp. 39-8, 39-15, 1973. 36. I.T. Young and J.C. Mott-Smith, "On Weighted PCM", IEEE Trans. Info. Theory, Corresp., Vol. IT-11, pp. 596-597, Oct. 1965. 3 7 . B.G. 'Haskell, F.W. Haunts and J.C. Candy, "Interframe Coding of Videotelephone P i c t u r e s " , Proc. IEEE, Vol. 60, No. 7, pp. 793-800, July 1972. 38. T. Fukinuki and M. Miyata, "Intraframe Image Coding by Cascaded Hadamard Transforms", IEEE Trans. Comm., Vo l . COM-21, No. 3 pp. 175-180, March 1973. 39. 0. Jensen, "Implementation of an Experimental F a c i l i t y and Modelling Study f o r Time Varying Images", M.A.Sc. Thesis, E.E. , U.B.C, Sept. 1973.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Three-dimensional transform encoding and block quantization...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Three-dimensional transform encoding and block quantization of still colour and monochrome moving pictures Soubigou, André 1975
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Three-dimensional transform encoding and block quantization of still colour and monochrome moving pictures |
Creator |
Soubigou, André |
Publisher | University of British Columbia |
Date Issued | 1975 |
Description | A bandwidth compression scheme for digital colour images using three-dimensional Fourier transform encoding and block quantization is investigated. The brightness U(x,y,λ) of a colour picture is considered as a three-dimensional function of the spatial dimensions x,y and the wavelength dimension λ. A set of colour pictures has been sampled. The study of the second order statistics of the data indicates various models for the autocorrelation function, depending on the type of picture. A separable exponential model is shown to provide a reasonable fit to strongly correlated data having vertical and horizontal features. When those features are not present a non-separable exponential model provides a better fit. Many experimental results of the three-dimensional Fourier transform encoding and block quantization of colour pictures are presented. The effects of the sub-picture bize and the average number of bits per picture element (b.p.p.e.) are considered; 2.75 b.p.p.e. seems sufficient to reproduce a reasonably good quality picture. The use of the separable model is shown to yield results close to the optimum possible at low bit rates, although the model fails to closely predict the signal-to-noise ratio of the reconstructed picture. It is shown that a non-separable model yields better prediction, at -considerable computational expense, but it does not significantly improve the actual performance. An adaptive system is also considered. The effect of digital channel errors on three-dimensional transform encoded pictures is investigated. The application of three-dimensional transform encoding for monochrome time-varying pictures is also considered. Fourier and Hadamard transformations are shown to yield similar results for the specific set of pictures used in our study. Included in the thesis is a summary of results and suggestions for further work. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-02-05 |
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.0100060 |
URI | http://hdl.handle.net/2429/19708 |
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 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1975_A1 S69.pdf [ 17.9MB ]
- Metadata
- JSON: 831-1.0100060.json
- JSON-LD: 831-1.0100060-ld.json
- RDF/XML (Pretty): 831-1.0100060-rdf.xml
- RDF/JSON: 831-1.0100060-rdf.json
- Turtle: 831-1.0100060-turtle.txt
- N-Triples: 831-1.0100060-rdf-ntriples.txt
- Original Record: 831-1.0100060-source.json
- Full Text
- 831-1.0100060-fulltext.txt
- Citation
- 831-1.0100060.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}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0100060/manifest