Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Three-dimensional transform encoding and block quantization of still colour and monochrome moving pictures Soubigou, André 1975

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

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

THREE-DIMENSIONAL TRANSFORM ENCODING  AND  BLOCK QUANTIZATION OF STILL COLOUR AND MONOCHROME MOVING PICTURES  by  Andre" Soubigou Inge"nieur de l ' E c o l e N a t i o n a l e de 1 ' A v i a t i o n O r l y , F r a n c e , 196 7. I n g e n i e u r s p e c i a l i s e * de l ' E c o l e N a t i o n a l e de 1'Ae"ronautique, P a r i s , France, 1968.  Civile,  Supe*rieure  M.A.Sc. ( E . E . ) , U n i v e r s i t e L a v a l , 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 a c c e p t t h i s t h e s i s as conforming required  Research  to the  standard  Supervisor  Members o f the Committee  Members o f the Department o f E l e c t r i c a l Engineering The U n i v e r s i t y o f B r i t i s h Columbia  In p r e s e n t i n g an the  thesis  in p a r t i a l  advanced degree at the U n i v e r s i t y Library  I further for  this  shall  agree  scholarly  make i t f r e e l y that permission  h i s representatives.  of  this  written  thesis  of B r i t i s h  available  gain  copying o f this  shall  that  b LccrHlCftt  The  of British  University  n o t be a l l o w e d w i t h o u t  2075 Wesbrook Place Vancouver, Canada V6T 1W5  htVC^fi/kt'/ZtNCj Columbia  thesis  copying or p u b l i c a t i o n  permission.  Department o f  I agree tha  by t h e Head o f my D e p a r t m e n t o r  I t i s understood  f o r financial  Columbia,  f o r r e f e r e n c e and s t u d y .  for extensive  p u r p o s e s may be g r a n t e d  by  f u l f i l m e n t o f t h e r e q u i r e m e n t s f<  my  ABSTRACT  A bandwidth compression three-dimensional investigated.  scheme f o r d i g i t a l  F o u r i e r t r a n s f o r m encoding  c o l o u r images u s i n g  and b l o c k q u a n t i z a t i o n i s  The b r i g h t n e s s U(x,y,X) o f a c o l o u r p i c t u r e i s c o n s i d e r e d  as a t h r e e - d i m e n s i o n a l wavelength dimension  f u n c t i o n of the s p a t i a l dimensions x,y  second o r d e r s t a t i s t i c s  The  study o f  e x p o n e n t i a l model i s shown to p r o v i d e a r e a s o n a b l e l a t e d d a t a h a v i n g v e r t i c a l and h o r i z o n t a l f e a t u r e s . are not p r e s e n t a non-separable Many e x p e r i m e n t a l  A  separable  f i t to s t r o n g l y c o r r e When those  features  e x p o n e n t i a l model p r o v i d e s a b e t t e r  and b l o c k q u a n t i z a t i o n of c o l o u r p i c t u r e s a r e  presented.  e f f e c t s o f the s u b - p i c t u r e b i z e and t h e average number o f b i t s  to reproduce The  a reasonably  good q u a l i t y  picture.  to the optimum p o s s i b l e at low b i t r a t e s , a l t h o u g h  results close  the model f a i l s  to  the s i g n a l - t o - n o i s e r a t i o of the r e c o n s t r u c t e d p i c t u r e .  I t i s shown t h a t a n o n - s e p a r a b l e -considerable computational a c t u a l performance.  The  per  b.p.p.e. seems s u f f i c i e n t  use o f the s e p a r a b l e model i s shown t o y i e l d  closely predict  fit.  r e s u l t s o f the t h r e e - d i m e n s i o n a l F o u r i e r  p i c t u r e element (b.p.p.e.) a r e c o n s i d e r e d ; 2.75  the  the  of the data i n d i c a t e s v a r i o u s models f o r the  a u t o c o r r e l a t i o n f u n c t i o n , depending on the type o f p i c t u r e .  The  the  X.  A set o f c o l o u r p i c t u r e s has been sampled.  transform encoding  and  model y i e l d s b e t t e r p r e d i c t i o n , at  expense, but i t does n o t s i g n i f i c a n t l y  improve  An a d a p t i v e system i s a l s o c o n s i d e r e d .  e f f e c t of d i g i t a l channel e r r o r s  form encoded p i c t u r e s i s i n v e s t i g a t e d .  ii  on t h r e e - d i m e n s i o n a l  trans-  The application of three-dimensional transform encoding f o r monochrome time-varying pictures i s also considered.  Fourier and  Hadamard transformations are shown to y i e l d s i m i l a r r e s u l t s f o r the s p e c i f i c set of pictures used i n our study. Included i n the thesis i s a summary of r e s u l t s and suggestions for further work.  iii  TABLE OF CONTENTS Page I.  II.  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  COLOR IMAGE PROCESSING SYSTEM 2.1  III.  Scanning Equipment  7  2.1.1  Flying Spot Scanner - Phosphor  7  2.1.2  Filters  9  2.1.3  Photomultiplier  2.2  Scanning Process  2.3  Display Process  2.4  O r i g i n a l Image Data  10 10 ,  10 13  DATA STATISTICS 3.1  Introduction  . .  15  3.2  F i r s t Order S t a t i s t i c s  15  3.3  Second Order S t a t i s t i c s  19  3.3.1  Introduction  19  3.3.2  Estimation of Pictures S t a t i s t i c s  . . . .  21  3.4  Choice of a Model  24  3.5  Non-separable Model  28  3.5.1  Non-separability i n the S p a t i a l Dimensions  28  3.5.2  Separability of the S p a t i a l and Colour Dimensions  31  iv  ;  IV.  Page 3.6  Double-exponential Model  33  3.7  Conclusion  36  THEORY OF TRANSFORM ENCODING 4.1  Introduction  4.2  Theory of Three-dimensional Fourier Transform Encoding  41  Performance of a Three-dimensional Transform Processing System . . . . . . . . . .  44  4.3  V.  . . .  39  QUANTIZATION OF THE FOURIER SAMPLES 5.1  Introduction  48  5.2  Statistics of the Fourier Samples . . . . . . . .  48  5.3 -Bit Allocation 5.4  5.5 VI.  Quantization  52 . . .  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  Conclusion - Simulation Technique . . . . . . . .  56  THREE-DIMENSIONAT TRANSFORM ENCODING OF COLOUR PICTURES 6.1  Introduction  6.2  Experimental Results Obtained Using Various SubPicture Sizes and Various Numbers of Bits Per Picture Element (b.p.p.e.)  6.3  61  . 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  Discussion of the Results v  . . . . . . . . . . .  78  Page  VII.  EFFECTS OF IMPROVED QUANTIZATION, BETTER DATA MODELLING, A D A P T I V E PROCESSING, AND D I G I T A L CHANNEL ERRORS ON COLOUR PICTURES 7.1  Introduction  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  A t t e m p t s t o I m p r o v e P e r f o r m a n c e b y Use o f a M o r e P r e c i s e Model  93  7.3.1  Non-separable  . .  93  7.3.2  Double-exponential  Model  97  7.3.3  Processing Using  7.3  Model  the Actual Variances o f  the F o u r i e r Samples  VIII.  IX.  97  7.4  Adaptive P r o c e s s i n g f o r Improved Performance  7.5  Effect of d i g i t a l  7.6  Discussion of Results  channel e r r o r s  . .  . . . . . . . .  102 108 114  THREE-DIMENSIONAL TRANSFORM ENCODING OF MONOCHROMATIC MOVING P I C T U R E S 8.1  Introduction  . .  8.2  Data Base and Data S t a t i s t i c s  8.3  Experimental Results  8.4  Conclusion  . . . . . . . .  . . . . . . .  .  119  .  119  .  123  .  125  CONCLUSION 9.1  Summary o f R e s u l t s  9.2  Suggestions  128  f o r Future Research  vi  ". . . . . . .  .  130  Page 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 levels f o r the pictures GARDEN3, FACE, HOUSE, TEST PATTERN, BUILDING  132  APPENDIX B:  Various correlation c o e f f i c i e n t s  139  APPENDIX C:  Some examples of the b i t a l l o c a t i o n of the Fourier samples  148  Histograms of Fourier samples f o r the picture FACE .  154  APPENDIX D: REFERENCES  15 8  vii  LIST. OF ILLUSTRATIONS  Figure  Page  2.1  Experimental arrangement used to scan  8  2.2  Tentative spectral energy d i s t r i b u t i o n of LP203 phosphor  8  2.3  F i l t e r s transmission c h a r a c t e r i s t i c s  11  2.4  Photomultiplier s e n s i t i v i t y  11  2.5  Experimental arrangement used to display  12  2.6  O r i g i n a l colour images  14  |3.1  Histograms of i n t e n s i t y l e v e l s for each colour plane and for the e n t i r e picture for the picture GARDEN1 . . 17  ,3.2  Histograms of i n t e n s i t y l e v e l s and Maxwell d i s t r i b u t i o n 18  3.3 3.4  Mean and Standard deviation of the brightness as a function of the s p a t i a l dimension x  20  Mean of the brightness as a function of the wavelength for each picture and averaged over the s i x pictures  20  3.5  Correlation c o e f f i c i e n t i n the s p a t i a l d i r e c t i o n X for the pictures GARDEN1 and GARDEN3 . , . 22  3.6  Correlation c o e f f i c i e n t i n the s p a t i a l d i r e c t i o n Y f o r the pictures GARDEN1 and GARDEN3 23  3.7  Correlation c o e f f i c i e n t i n the wavelength d i r e c t i o n X for the pictures GARDEN1 and GARDEN3 .  25  Comparative f i t of separable and non-separable models to diagonal s p a t i a l correlation c o e f f i c i e n t s for the pictures GARDEN 1 and GARDEN3 . . .  29  Comparative f i t of separable and non-separable models to diagonal s p a t i a l correlation c o e f f i c i e n t s for the pictures FACE and HOUSE  30  Correlation c o e f f i c i e n t i n the d i r e c t i o n X-X and separable model for the pictures GARDEN1, GARDEN3 and FACE  32  3.8  3.9  3.10  viii  Page 3.11  Comparative f i t of the single-exponential model and the double-exponential model i n the s p a t i a l directions f o r the p i c t u r e GARDEN1  34  Comparative f i t of the single-exponential model and the double-exponential model i n the s p a t i a l directions f o r the picture GARDEN3  35  Comparative f i t of the non-separable and separable double exponential models i n the diagonal s p s t i a l d i r e c t i o n for the pictures GARDEN1 and GARDEN3 . . . .  37  4.1  Transform encoding system . .  39  4.2  S/N r a t i o as a function of the number of transmitted samples f o r various transform encoding systems . . . .  47  5.1  Histograms of Fourier samples f o r the picture GARDEN1 .  50  5.2  Histograms of Fourier samples for the p i c t u r e GARDEN1 .  51  5.3  Quantization of the Fourier samples  52  5.4  S/N r a t i o as a function of the average number of b.p.p.e. for various transform encoding systems 57  5.5  S/N r a t i o as a function of the sub-picture s i z e . . . .  58  5.6  Three-dimensional  59  6.1  Various estimations of the S/N r a t i o  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  Transform processed pictures. 1 b.p.p.e.  66  3.12  3.13  6.3 6.4  transform encoding system . . . . . .  Transform processed pictures. 2 b.p.p.e.  6.5  6.6  Sub-picture s i z e Sub-picture s i z e  6 x 6 x 6 6 x 6 x 6  . . . . . . . . . . . . .  Transform processed p i c t u r e s . 3 b.p.p.e.  Sub-picture s i z e  Transform processed pictures.  Sub-picture s i z e  6 x 6 x 6 68 8 x 8 x 6  1 b.p.p.e. 6.7  67  75  Transform processed pictures. 2 b.p.p.e  ix  Sub-picture s i z e  8 x 8 x 6 76  Page 6.8  6.9 6.10  6.11  6.12  Transform processed pictures. Sub-picture s i z e 3 b.p.p.e  8 x 8 x 6 77  S/N r a t i o 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  82  S/N r a t i o as a function of the average number of b.p.p.e. f o r a 8 x 8 x 6 sub-picture s i z e  83  S/N ratio as a function of the number of transmitted samples (no quantization) for an 8 x 8 x 6 sub-picture s i z e . The number of transmitted samples for 1,2 and 3 b.p.p.e. i s indicated  86  Absolute difference signal between processed and o r i g i n a l 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  7.2  Transform processed p i c t u r e s . Sub-picture s i z e 16 x 16 x 6. 2.75 b.p.p.e. Adapted quantizer  92  S/N r a t i o 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 s i z e . The S/N measured for 2.75 b.p.p.e. are shown  94  Comparison between S/N r a t i o s , 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.3  7.4  7.5  7.6 [ •7.7  . . 90  S/N r a t i o 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 s i z e 1 6 x 16 x 6. Pictures GARDEN 1 and GARDEN3 . . . . . . . . 98 Pictures processed using the adapted quantizer for the D . C . component, 2.75 b.p.p.e. and for each p i c t u r e , the actual variances of the samples of the Fourier transform of the p i c t u r e •  99  Estimated values of the c o r r e l a t i o n parameters a, 3 and Y over 16 x 16 x 6 sub-pictures for the picture FACE . . 103  7.8  7.9  7.10  7.11  P e r s p e c t i v e p l o t s o f the c o r r e l a t i o n parameters a, 8 and y e s t i m a t e d o v e r 16 x 16 x 6 s u b - p i c t u r e s f o r the p i c t u r e FACE . . . . . (a) (b)  Transformed Transformed processing  p i c t u r e FACE p i c t u r e FACE  2.75 2.75  105  b.p.p.e. b.p.p.e. Adaptive . . . . . . . .  T r a n s m i s s i o n of t r a n s f o r m encoded p i c t u r e s over a n o i s y c h a n n e l . . . . . . . . . . . .  109  E f f e c t of d i g i t a l c h a n n e l e r r o r s on 3 b.p.p.e. 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 encoded p i c t u r e s ; per d i g i t e r r o r 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 c h a n n e l e r r o r s on PCM t r a n s m i t t e d o r i g i n a l data; p e r - d i g i t e r r o r p r o b a b i l i t y p = 0.01 e  7.13  7.14  8.1  8.2  8.3  8.4  8.5  8.6  107  .  113  (a) (b) Two-dimensional Hadamard t r a n s f o r m e d p i c t u r e s , (c) (d) Two d i m e n s i o n a l F o u r i e r t r a n s f o r m e d 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  Three-dimensional 16 x 16 x 6, 1.0,  118  F o u r i e r t r a n s f o r m p i c t u r e FACE 1.5 and 2.0 b.p.p.e. . . . . . . . .  O r i g i n a l d a t a SCENE1. E i g h t c o n s e c u t i v e frames taken a t 24 frames p e r second, q u a n t i z e d to 8 b i t s . 256 x 256 elements  120  C o r r e l a t i o n c o e f f i c i e n t a l o n g the s p a t i a l dimensions f o r SCENE1 ( F i g . 8.1) and l e a s t - s q u a r e f i t of the e x p o n e n t i a l mode 1 . . .  121  C o r r e l a t i o n c o e f f i c i e n t a l o n g the time dimension of SCENE1 ( F i g . 8.1) and l e a s t - s q u a r e f i t o f the e x p o n e n t i a l model . . .  122  S/N r a t i o as a f u n c t i o n of the number o f t r a n s m i t t e d samples f o r the Hadamard and the F o u r i e r t r a n s f o r m s f o r the SCENE1 from the e s t i m a t e d v a r i a n c e s and from the a c t u a l n o r m a l i z e d v a r i a n c e s . The a c t u a l S/N r a t i o f o r 8 b.p.p.e. (539 samples) i s shown and compared t o the r e s u l t s p r e d i c t e d by the a c t u a l v a r i a n c e s , the q u a n t i z a t i o n b e i n g taken i n t o account . . . . . . . . .  124  E i g h t frames of SCENE1 ( F i g 8.1) t h r e e - d i m e n s i o n a l F o u r i e r t r a n s f o r m e d u s i n g an average of 1 b.p.p.e. p e r frame .  126  E i g h t frames of SCENE1 ( F i g . 8.1) t h r e e - d i m e n s i o n a l Hadamard t r a n s f o r m e d u s i n g an average o f 1 b.p.p.e. p e r frame . . . . . . . . . . . . . . . . .  127  xi  Page A.l  A.2 A.3 A.4 A. 5 B. l B.2 . B...3 B.4 1.5  B.6 B.7  B.8  Histograms of i n t e n s i t y l e v e l s f o r each colour plane and for the entire picture f o r the picture GARDEN3  134  Histograms of i n t e n s i t y l e v e l s f o r each colour plane and for the entire picture for the picture FACE  135  Histograms of i n t e n s i t y l e v e l s f o r each colour plane and for the entire picture f o r the picture HOUSE  136  Histograms of i n t e n s i t y l e v e l s for each colour plane and for the entire picture f o r the picture TEST PATTERN . . '.  137  Histograms of i n t e n s i t y l e v e l s f o r each colour plane and for the entire picture f o r the picture BUILDING . . . .  138  Correlation c o e f f i c i e n t i n the X d i r e c t i o n for the pictures FACE and HOUSE  140  Correlation c o e f f i c i e n t i n the X d i r e c t i o n f o r the pictures TEST PATTERN and BUILDING .  141  Correlation c o e f f i c i e n t i n .the Y . . d i r e c t i o n . f o x the pictures FACE and HOUSE  142  Correlation c o e f f i c i e n t i n the Y d i r e c t i o n f o r the pictures TEST PATTERN and BUILDING  143  Correlation c o e f f i c i e n t i n the X d i r e c t i o n f o r the pictures FACE and HOUSE . . . . . . .  144  Correlation c o e f f i c i e n t i n the X d i r e c t i o n f o r the pictures TEST PATTERN and BUILDING . . . . . . . . . . . ,  145  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 .  146  Correlation c o e f f i c i e n t i n the wavelength d i r e c t i o n , assuming s t a t i o n a r i t y , f o r the pictures HOUSE,.TEST PATTERN and BUILDING . . . . . . . . . .  . .  147  D.1  Histograms of Fourier samples f o r the picture FACE  . . .  155  D.2  Histograms of Fourier samples f o r the picture FACE  . . .  156  LIST OF TABLES Table  Page  2.1  Definition of wavelengths  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  Comparative closeness of the f i t of a separable and a non-separable model in the x - X direction  33  Comparative closeness of the f i t of the singleexponential and double-exponential models in the spatial directions and correlation parameters for the pictures GARDEN1 and GARDEN3  36  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  Bit allocation for the picture GARDEN1 for 1, 2 and 3 b.p.p.e. and for a 6x6x6 sub-picture size  69  Bit allocation for the picture FACE for 1, 2 and 3 b.p.p.e. and for a 6x6x6 sub-picture size  70  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  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  Bit allocation for the picture GARDEN1 for 1, 2 and 3 b.p.p.e. and for an 8x8x6 sub-picture size  73  Bit allocation for the picture FACE for 1, 2 and 3 b.p.p.e. and for an 8x8x6 sub-picture size  74  Rank of (a) estimated, (b) actual variances of the Fourier samples for the picture FACE and a 6x6x6 sub-picture size . . . . . . . . .  79  3.3 3.4  5.1  6.2 6.3 6.4  6.5  6.6 6.7 6.8  9  xiii  Page 6.9  Ratio of estimated variances to actual normalized variances f o r the p i c t u r e GARDEN1 and f o r a 6x6x6 sub-picture s i z e . . 81  6.10  Normalized difference between (S/N) predicted by a c t u a l variances and computed without quantization of the oomponents . . . . . . . .  84  Normalized d i f f e r e n c e between actual S/N r a t i o and S/N r a t i o predicted from the estimated variances of the Fourier samples  85  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 actual variances  87  S/N r a t i o s i n the 16x16x16 case, using the adapted quantizer and 2.75 b.p.p.e., and 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 actual variances . . . . . . . . . . . . . . . . . . . . . .  91  6.11  6.12 7.1  7.2  Measured S/N r a t i o 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 r a t i o obtained when the pictures are processed using the actual variances of the Fourier samples (2.75 b.p.p.e., 16x16x16) . 97  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  7.4  D i s t r i b u t i o n of the categories of sub-pictures i n the picture FACE  7.5  Average c o r r e l a t i o n parameters f o r each category of sub-picture f o r the p i c t u r e FACE .  7.6  7.7 (  101 . 106 106  S/N r a t i o s obtained by transmitting 3 b.p.p.e. transform encoded pictures on a noisy BSC channel  109  Mean-square errors and S/N r a t i o due to channel noise on the PCM transmission of the o r i g i n a l data  112  A.l  Mean and Standard deviation of the brightness o f the source pictures . . . . . . . . . . . . . . . 132  A.2  Mean and Standard deviation o f the brightness f o r each X^. . 133  xiv  ACKNOWLEDGEMENT  I would l i k e to thank my supervisor, Dr. R.W. Donaldson, f o r h i s encouragement and assistance during the course of this t h e s i s .  I  also wish to thank Mr. D. Wasson f o r h i s comments and suggestions during the preparation of the manuscript.  My thanks also go to Mr. M. Koombes  for h i s technical assistance and to Mrs. V. Walker f o r her e f f i c i e n t typing of the thesis. I also wish to acknowledge the f i n a n c i a l assistance received from the Canada Council.  xv  ': •  I 1.1  INTRODUCTION  Motivation Because of the  and b e c a u s e o f v e r y  g r o w i n g n e e d f o r image t r a n s m i s s i o n and  r a p i d a d v a n c e s i n h a r d w a r e and  interest i n sophisticated digital  software  technology,  image p r o c e s s i n g t e c h n i q u e s  considerably during recant years.  storage  has  grown  In p a r t i c u l a r , i n t e r e s t i n colour  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 techniques b e t w e e n p i c t u r e e l e m e n t s o f one dimensional z o n t a l and  l i n e o f monochrome s t i l l  processing techniques vertical  made u s e  of c o r r e l a t i o n s pictures.  w h i c h used c o r r e l a t i o n s i n both  d i r e c t i o n s were then  investigated.  A still  Twohori-  colour  p i c t u r e U(x,y, X ) , where U i s the 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 are  wavelength (colour). dimensional the  process  t h e s p a t i a l v a r i a b l e s and  A b l a c k and w h i t e U ( x , y ,t) ; t i s 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  pictures i s important,  time time  X i s the  light  varying picture i s a dimension.  three-  I t i s known  frames o f a s e t of  time-varying  t h e same r e m a r k i s t r u e f o r a d j a c e n t  of a c o l o u r p i c t u r e sampled i n the c o l o u r dimension.  that  colour  Efficient  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  planes  coding  dimension  (X o r t ) . A most p r o m i s i n g transform encoding,  scheme i n t e r m s o f b a n d w i -ith  w h i c h was  o b t a i n e d on two-dimensional of three-dimensional tigated.  The  this  recently.  d i s c u s s e d , has  Results  Transform  not  thesis i s to consider  of c o l o u r s t i l l  monochrome m o v i n g p i c t u r e s .  relatively  d a t a have been p u b l i s h e d .  data, although  purpose of  transform coding  introduced  reduction i s  encoding  r e a l l y been i n v e s -  three-dimensional  p i c t u r e s , a s w e l l as .  time-varying  2. 1.2  Reviews of Relevant Work by Others: This section summarizes relevant progress to date i n p i c t u r e  coding.  Performance i s  assessed i n terms of the average number of b i t s  per picture element (b.p.p.e.) necessary to reconstruct a "good q u a l i t y " picture. For the sake of comparison, standard PCM transmission of a monochromatic p i c t u r e 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 l i n e a r transformation was introduced by Huang and fTchultheiss 15].  and block  quantization  T y p i c a l r e s u l t s 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 f o r a strongly c o r r e l a ted p i c t u r e ; 2 b.p.p.e. were required f o r the other transformations a more general type of data.  and  Wintz has summarized i n [7] a l l published  r e s u l t s on transform encoding of monochromatic data up to J u l y 1972. The conclusion was that f o r a moderate d e t a i l monochrome p i c t u r e , approximately 2 b.p.p.e. seem to be required f o r the two-dimensional transform encoding. i  Gronneman  [2] investigated the e f f e c t of low-pass f i l t e r i n g  on the three basic components of a colour p i c t u r e , reaching an average of 5.5  b.p.p.e.  P r a t t [8,9] applied two-dimensional transform encoding  on three basic components of a colour p i c t u r e (R,G,B or Y,I,Q or others).  3. In a v e r y s p e c i f i c case, u s i n g the Karhunen-Loeve t r a n s f o r m a t i o n and t h r e s h o l d sampling  on t h e Y component  and t h e Hadamard t r a n s f o r m a t i o n on  I and Q components, he used as few as 1.75 b.p.p.e. implemented F o u r i e r and Hadamard t r a n s f o r m a t i o n s ,  F o r t h e more e a s i l y  3.75 b.p.p.e. were  More r e c e n t l y P r a t t [10] employed the S l a n t t r a n s f o r m ,  used.  u s i n g 3 b.p.p.e.  The use o f 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 i n v e s t i g a t e d by P r a t t [ 9 ] , who proposed the replacement o f the  R,G,B  components w i t h Karhunen-Loeve components t o o b t a i n an optimum  energy  compaction. done.  However, no e s t i m a t i o n i n terms o f b.p.p.e. r e q u i r e d , was  R u b i n s t e i n and Limb i n [ 1 1 ] , [ 1 2 ] , 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 t h r e e components o f c o l o u r v i d e o s i g n a l s . as few as 0.25 signals.  t o 0.5 b i t s p e r luminance sample to code the chrominance  To our knowledge, the o n l y r e s u l t s o f the a c t u a l a p p l i c a t i o n o f  three-dimensional 113].  encoding were p u b l i s h e d by P . J . Ready and P.A. W i n t z  They proposed the use o f t h e Karhunen-Loeve  t r a n s f o r m encoding  f o r m u l t i s p e c t r a l imagery d a t a .  s u l t s show t h a t t h e t h r e e - d i m e n s i o n a l approximately  three-dimensional Their published r e -  system a l l o w s a r e d u c t i o n by  h a l f o f the data r a t e , compared to the t w o - d i m e n s i o n a l  system f o r the same s u b j e c t i v e l y a c c e p t a b l e o f p i c t u r e s they used.  d i s t o r t i o n and f o r the s e t  To our knowledge no r e s u l t s on t h e 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 encoding [9,  They r e p o r t e d  o t h e r than i n the above-mentioned r e f e r e n c e s  13] have been p u b l i s h e d to date. The e f f e c t o f d i g i t a l  channel  o f p i c t u r e s r e c e i v e d some a t t e n t i o n .  e r r o r s on the PCM  T.S. Huang and M.T.  compared the e f f e c t o f a d d i t i v e Gaussian  transmission Chikhaoui  n o i s e and BSC d i g i t a l  [14]  channel  e r r o r s 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 p r e f e r r e d the d i g i t a l  e r r o r s when t h e S/N r a t i o exceeded 15  dB.  4. For a lower S/N  r a t i o the p i c t u r e transmitted over a noisy BSC  were considered of lower q u a l i t y .  channel  Pratt [9,15] studied the e f f e c t of  d i g i t a l channel errors on the PCM transmission of various colour components.  He concluded that the l e a s t damage occurs when R,G,B  are used.  components  Wintz [7] published some r e s u l t s on the subjective e f f e c t of  d i g i t a l channel errors on transform encoding of monochromatic p i c t u r e s . No experimental results have been published concerning the e f f e c t 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 i n the following way.  The source data i s transformed by a l i n e a r transformation.  Some trans-  form samples are rejected according to a q u a l i t y c r i t e r i o n , those retained are quantized, d i g i t i z e d and e i t h e r transmitted or stored.  These opera-  tions are based on the a - p r i o r i 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 y i e l d a reconstructed version of the o r i g i n a l p i c t u r e . This thesis considers three-dimensional transform encoding. Many experimental results are presented. as source data f o r most of the experiments a smaller number.  Colour pictures w i l l be used and time varying pictures f o r  I t i s an almost s t r i c t l y mathematical  study of colour  p i c t u r e s , i n the sense that almost complete abstraction of the human observer i s made, up to the point where the pictures are displayed f o r subjective assessment. human v i s i o n .  Abstraction i s made of the theory of t r i s t i m u l u s  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 r e s u l t s can be adapted to three-component  colour pictures. and  colour  films  s u p p o s e d l y t h e author, who made the s u b j e c t i v e e v a l u a t i o n , have  tris-  timulus  I t i s important to note that the recording  properties. The  Signal-to-Noise  ratio  (S/N) p r o p o r t i o n a l t o t h e l o g a r i t h m  o f the n o r m a l i z e d mean s q u a r e e r r o r between p r o c e s s e d and o r i g i n a l p i c t u r e i s used as t h e p r i m a r y q u a l i t y c r i t e r i o n , i n t h e sense t h a t 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 t o b e o f  better subjective quality.  s u b j e c t i v e q u a l i t y seems t o be a  monotonically  In general,  i n c r e a s i n g f u n c t i o n o f t h e S/N r a t i o .  The  Fourier transformation  w i l l be used i n t h e p r o c e s s i n g o f  c o l o u r p i c t u r e s because o f easy i m p l e m e n t a t i o n . formation  o p e r a t e s o n l y on t e n s o r s  Since  t h e Hadamard  whose dimensions a r e a power o f two, i t  w i l l n o t be a p p l i e d t o c o l o u r p i c t u r e s i n t h i s t h e s i s s i n c e of the b l o c k s  trans-  the dimension  i n the c o l o u r dimension i s 6.  Emphasis w i l l be on t h e p r e d i c t i o n o f t h e performance o f t h e transform  encoding process.  T h i s p r e d i c t i o n i s b a s e d on t h e s t a t i s t i c a l  model used f o r a t h r e e - d i m e n s i o n a l 1.4  O u t l i n e o f the Thesis I n c h a p t e r 2,  described.  t h e c o l o u r image d a t a a c q u i s i t i o n system i s  The c h a r a c t e r i s t i c s o f t h e equipment used i n t h e d i g i t i z a t i o n  process are defined. is  picture.  The o r i g i n a l c o l o u r s o u r c e d a t a used i n t h e t h e s i s  presented. Chapter 3 i s devoted t o t h e measurements o f t h e s t a t i s t i c s o f  the o r i g i n a l d a t a .  First  and second o r d e r  statistics  are estimated.  Some models o f the a u t o c o r r e l a t i o n f u n c t i o n o f t h r e e - d i m e n s i o n a l pictures are presented.  colour  6 .  In c h a p t e r 4, encoding  i s presented.  the t h e o r y o f t h r e e - d i m e n s i o n a l F o u r i e r t r a n s f o r m U s i n g a s i m p l e s t a t i s t i c a l model f o r a t h r e e -  d i m e n s i o n a l p i c t u r e , performance i s e s t i m a t e d and compared t o t h a t o f a two-dimensional t r a n s f o r m e n c o d i n g  system.  Chapter 5 c o n s i d e r s the problem of q u a n t i z a t i o n o f t h e F o u r i e r samples.  The b i t a l l o c a t i o n a l g o r i t h m i s chosen and the q u a n t i z e r s a r e ;  chosen on t h e b a s i s o f t h e s t a t i s t i c s o f t h e F o u r i e r samples. titative effect  The quan-  o f q u a n t i z a t i o n i s e v a l u a t e d and performance i s , from  then on, e v a l u a t e d as a S/N r a t i o f u n c t i o n o f t h e average  number o f b i t s  p e r p i c t u r e element. In c h a p t e r 6, many e x p e r i m e n t a l r e s u l t s on t h e t h r e e - d i m e n s i o n a l F o u r i e r t r a n s f o r m encoding of  o f colour p i c t u r e s are presented.  T h e effect  u s i n g v a r i o u s .sub-picture s i z e s and b.p.p.e, i s c o n s i d e r e d . In c h a p t e r 7, ways t o improve t h e performance and t h e mathema-  t i c a l p r e d i c t i o n o f the performance o f t h e F o u r i e r t r a n s f o r m system a r e p r e s e n t e d . of  An a d a p t i v e system i s i n v e s t i g a t e d .  encoding The e f f e c t  d i g i t a l channel e r r o r s i s s t u d i e d . In c h a p t e r 8 , t h e r e s u l t s a r e a p p l i e d t o time v a r y i n g mono-  chromatic p i c t u r e s .  F o u r i e r and Hadamard t r a n s f o r m a t i o n s a r e compared.  F i n a l l y , c h a p t e r 9 c o n t a i n s a summary o f the r e s u l t s o b t a i n e d and some recommendations f o r f u t u r e r e s e a r c h .  7.  II  The parency  COLOR IMAGE PROCESSING SYSTEM  d i g i t a l c o l o r image d a t a was  sampled a l o n g two  o b t a i n e d from a c o l o r t r a n s -  s p a t i a l dimensions  and one  c o l o r dimension.  In  o r d e r to be a b l e to d e f i n e the q u a l i t y of the o r i g i n a l d a t a i t i s n e c e s s a r y to  d e f i n e the type of equipment used i n the d i g i t i z a t i o n 2.1  Scanning The  2.1.1  Equipment:  s c a n n i n g system i s r e p r e s e n t e d on F i g .  F l y i n g Spot  x 256 p o i n t s .  With the s e t t i n g used,  were scanned on the o r i g i n a l s l i d e . ble,  but was  displays a  7 l i n e s per m i l l i m e t e r  A higher s p a t i a l resolution i s p o s s i -  The  s i z e o f the spot was  The b r i g h t n e s s o f the s p o t was  kept  to the minimum  k e p t low enough t o p r e v e n t  appearance of a h a l o s u f f i c i e n t l y l a r g e t o i n c r e a s e the s p o t '~ The  s p e c t r a l energy  shown i n F i g . 2.2. able approximation  d i s t r i b u t i o n o f the type 203  To our knowledge, t h i s phosphor was to white; white  bution.  The energy  spectrum  seems to be very  implies a f l a t  e m i t t e d i n the low  frequency  The  the  size.  phosphor i s  the c l o s e s t  s p e c t r a l energy  avail-  distri-  (red) p a r t of the  visible  low.  A Nova Computer c o n t r o l s the s c a n n e r interface.  spatial  avoided because o f the i n c r e a s e i n the time r e q u i r e d f o r the  t r a n s f o r m encoding p r o c e s s . possible.  2.1.  Scanner - Phosphor:  A computer c o n t r o l l e d f l y i n g s p o t s c a n n e r g r i d o f 256  process.  f l y i n g s p o t scanner i t s e l f  through  a 12 b i t  i s manufactured by  E n g i n e e r i n g L a b o r a t o r i e s Company, Mahwah, N.J.  D/A  Constantine  8.  MINICOMPUTER  PROGRAM--  A/D  D/ A CONVERTER  CONVERTER  NOVA  Transparency  DEFLECTION CIRCUITS  Filter -i CRT  PHOTOMULTIPUER  Lens U  Lens 12  F i g . 2 . 1 Experimental arrangement used to scan  2.1.2  Filters: A s e t o f i n t e r f e r e n c e f i l t e r s No. 6469 manufactured by O p t i c s  Technology I n c . , P a l o A l t o , C a l i f o r n i a , was used f o r q u a n t i z a t i o n the  wavelength dimension.  T h i s s e t i n c l u d e d 6 low-pass and 6 h i g h - p a s s  f i l t e r s w i t h c u t - o f f f r e q u e n c i e s s e p a r a t e d by 50 nm. these f i l t e r s  along  a l l o w f o r m a t i o n o f 6 band-pass  c h a r a c t e r i s t i c s appear i n F i g . 2.3.  Combinations o f  f i l t e r s whose  transmission  The number o f s a m p l i n g p o i n t s i n the  c o l o r dimension was f i x e d by the a v a i l a b i l i t y o f the s e t o f f i l t e r s the  photomultiplier sensitivity.  A h i g h e r number o f f i l t e r s  d e c r e a s e d the energy i n each sampled band.  would  and have  The b r i g h t n e s s o f the s p o t  would have had t o be i n c r e a s e d , r e s u l t i n g i n an i n c r e a s e d h a l o which would have d e c r e a s e d the s p a t i a l  resolution.  The t r a n s m i s s i o n c h a r a c t e r i s t i c s o f t h e f i l t e r s , s i n c e they a r e of  interference  type, depends somewhat on t h e a n g l e o f the i n c i d e n t  T h e r e f o r e , the f i l t e r s aiigle o f i n c i d e n t t h a t the f i l t e r s the  light.  a r e s i t u a t e d i n t h e system a t a p l a c e where the  l i g h t w i t h the a x i s i s s m a l l .  I t i s important t o note  a r e s i t u a t e d i n t h e system a t t h e same p l a c e ,  whether  system i s used t o s c a n o r t o d i s p l a y . Throughout the t h e s i s , wavelengths  a r e d e f i n e d as i n T a b l e  2.1. . Wavelength Number  XI X2 X3 X4 X5 X6  COLOR  Violet Blue Green Yellow Orange Red  T a b l e 2.1  Wavelength Range,  400-450 450-500 500-550 550-600 600-650 650-700  ....  D e f i n i t i o n o f Wavelengths  nanometers  10. 2.1.3  Photomultiplier: An RCA  type S - l p h o t o m u l t i p l i e r was  used.  Its sensitivity  appears i n F i g . 2.4. 2.2  Scanning P r o c e s s : A g r i d o f 256 x 256 p o i n t s was  s c a n n e r tube. (Fig.  2.1)  Each p o i n t was  d i s p l a y e d on the f l y i n g s p o t  f o c u s e d through a c o l o r f i l t e r  onto the t r a n s p a r e n c y .  and l e n s L l  Lens L2 f o c u s e d the p o i n t from the  t r a n s p a r e n c y onto the f r o n t s u r f a c e o f the p h o t o m u l t i p l i e r . m u l t i p l i e r output was on IBM  i n t e g r a t e d , sampled,  compatible magnetic  The  quantized to 8 b i t s  ( F i g . 2.2  and  and  and F i g . 2 . 4 ) , the response o f the system was  i d e n t i c a l i n each c o l o r . through the c o l o r f i l t e r  C o n s e q u e n t l y a b l a n k t r a n s p a r e n c y was g i v i n g the h i g h e s t response  (550 nm  s t o r e d on tape.  one  used t o r e s t o r e each c o l o r p l a n e .  c o l o r p l a n e and s t o r e i t on tape r e q u i r e d a p p r o x i m a t e l y 10 2.3  not  - 600 nm) ,  S i x Ektachrome t r a n s p a r e n c i e s were then  and the b l a n k p i c t u r e d a t a was  photo-  scanned  u s i n g the maximum p o s s i b l e b r i g h t n e s s s e t t i n g w i t h o u t s a t u r a t i o n . d a t a was  stored  tape.  Because o f the p a r t i c u l a r responses o f the phosphor multiplier  photo-  This scanned, To s c a n  seconds.  Display Process: The d a t a was For  d i s p l a y e d u s i n g the system i n F i g . 2.5.  each c o l o r p l a n e , each p o i n t d i s p l a y e d was  intensified for  a time s u f f i c i e n t t o compensate f o r the n o n - f l a t response o f the  phosphor.  The o r i g i n a l r e s u l t s were r e c o r d e d on Ektachrome c o l o r f i l m f o r •  slides.  Kodak paper h a r d c o p i e s a r e shown i n t h i s t h e s i s .  c o p i e s s h o u l d be viewed . size.  - .43  These  hard-  a t a d i s t a n c e o f a p p r o x i m a t e l y 6 t o 10 times  their  90-  XI  80-  : 70-  1  c  1  h  .8  50-  1 1  ,  ....  1 1 1 1 1 11 1 1 1 1 1  .18 40' c  JO 20' f  10 /  /  1 1 1 1 1  1  1  / f  350  f  1 1 1, 1 1 1 1 1 1 I 1 1 | 1 | ' 1 i 1  1  CL> O 60 N  Kl A3  /'"•>,  /  400  T  i  /  /  450  N  1 1' 1 1 1! 1•• 1i 1 1 ii 1 1 1 ;! • i i  ^  -  .  ^  / \ l  \  < ii  •  •\ "A\ J  1/ X  500  '  i  ii i i  il iI ii ti •  J  J  !  i »  i.  i  «  1  X b  :  ' i • i i t  s I  A5  \ /  i  1 /  i i  » »  »  i »  1 I1 .' i j i /  \\  \  V  \  \/  \  *  550  600  650  \  \  700  nanometers Fig. 2.3 F i l t e r s transmission  300  400  500  600  characteristics.  700  nanometers Fig. 2.4 Photomultiplier  sensitivity.  MINICOMPUTER  XEROGRAM  D/A  CONVERTER  NOVA  DEFLECTION CIRCUITS  /7/ter  N  Film  l e n s 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  then d i s p l a y e d .  shows h a r d c o p i e s  These p i c t u r e s were chosen f o r the  P i c t u r e s 2.6 d e t a i l and  o f s i x images which were scanned  a)  and  2.6  b)  following  in spatial detail.  A face i s frequently  because i t i s the most l i k e l y t o be for evaluation (House and  transmitted  of f l e s h tone r e n d i t i o n .  Building)  have low  regular s p a t i a l d e t a i l .  e)  P i c t u r e 2.6  used as  d)  and  2.6  c o n s t a n t b l u e sky  c)  reference  over a picturephone,  P i c t u r e s 2.6  color detail,  P i c t u r e 2.6  reasons:  (Gardens) p r o v i d e h i g h s p a t i a l  areas h a v i n g s p e c i f i c narrow bands o f c o l o r s .  (Face) i s low  and  f)  and  ( T e s t P a t t e r n ) w i l l be  and  high  used as  a  t e s t f o r c o l o r 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  compared to p r e v i o u s l y i) ii) iii)  can be  published  considered  as b e i n g o f "good q u a l i t y " ,  c o l o r d a t a , f o r the  I t p r o v i d e s a l a r g e v a r i e t y of  following  reasons:  data,  S p a t i a l r e s o l u t i o n i s v e r y good.  S m a l l d e t a i l s are  Some p i c t u r e s have v e r y c o n t r a s t e d  areas:  present,  very b r i g h t  parts  which are v e r y c l o s e to dark p a r t s , iv)  Color  r e n d i t i o n , a l t h o u g h i t may  i s v e r y c l o s e to n a t u r a l  colors.  The  appear to l a c k o f  saturation,  o r i g i n a l s l i d e s from w h i c h  the p i c t u r e s a p p e a r i n g i n t h i s t h e s i s are h a r d c o p i e d are o f q u a l i t y than the  copies.  better  14.a  Throughout the thesis, experimental results w i l l be presented i n the following way.  PICTURE a)  PICTURE b)  PICTURE  PICTURE  c)  d)  PICTURE  PICTURE  e)  F i g . 2.6  f)  a) GARDEN1 b) GARDEN3 c) FACE d) HOUSE e) TEST PATTERN f) BUILDING  V  ORIGINALS  15.  Ill 3.1  Introduction The  of The  DATA STATISTICS  importance  o f knowing the f i r s t  t h e d a t a , i n the s p e c i f i c  and second  case o f t r a n s f o r m e n c o d i n g ,  t h e o r e t i c a l study o f t r a n s f o r m e n c o d i n g  order  statistics  i s e x p l a i n e d below.  i n the f o l l o w i n g c h a p t e r  will  provide additional motivation. The v i d e important  first  order s t a t i s t i c s  o f the b r i g h t n e s s o f the p i c t u r e  i n f o r m a t i o n c o n c e r n i n g the most i m p o r t a n t  namely, the D.C.  component.  A minimum mean square  scheme r e q u i r e s the knowledge o f t h e second be p r o c e s s e d .  transform  sample,  transform  encoding  order s t a t i s t i c s  o f the d a t a t o  Even f o r a sub-optimum t r a n s f o r m a t i o n , f i l t e r i n g and q u a n t i -  z a t i o n o f the t r a n s f o r m e d order  error  pro-  d a t a samples r e q u i r e s knowledge o f the second  statistics. 3.2  First The  Order  source  Statistics:  data i s a three-dimensional d i s c r e t e process  where x and y are the s p a t i a l  dimensions,  mension and U i s t h e b r i g h t n e s s .  U(x,y,X)  X t h e . c o l o u r or wavelength d i -  The f r e q u e n c y  of occurrence  f  v  (u) o f  i each l e v e l  o f b r i g h t n e s s f o r each X^ was e s t i m a t e d as f o l l o w s :  (3.1) N = 256 where M^^(u) i s the number o f times  t h a t the b r i g h t n e s s U e q u a l s  the v a l u e  u f o r X = X^. The  frequency  e n t i r e p i c t u r e was a l s o  of occurrence  o f the b r i g h t n e s s f ( u ) , f o r the  computed:  6 f(u)  = [ I i=l  f . ( u ) ] /6.0 x  1  (3.2)  16. (u) and f ( u ) a r e d i s c r e t e f u n c t i o n s . t a t i o n , o n l y t h e i r envelopes  For s i m p l i c i t y  of presen-  a r e 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 r e s t o f the d a t a ( F i g . A1-A5) . I t i s important  to have a model f o r the f r e q u e n c y  the b r i g h t n e s s o f the p i c t u r e .  distribution of  As i t w i l l be shown i n the n e x t  chapter,  the D.C. component o f the F o u r i e r t r a n s f o r m o f each b l o c k has a d i s t r i b u t i o n similar  t o t h a t o f the b r i g h t n e s s o f t h e o r i g i n a l d a t a .  the most i m p o r t a n t ,  i n the sense o f the mean square  T h i s component i s  e r r o r between p r o c e s s e d  and o r i g i n a l p i c t u r e . Others  [16,17], have assumed the frequency  b r i g h t n e s s t o be u n i f o r m o r G a u s s i a n , The  Gaussian  at least  distribution  f o r monochromatic p i c t u r e s .  d i s t r i b u t i o n was r e j e c t e d by us because i t would r e p r e s e n t  an u n r e a l i s t i c a l l y h i g h e r p r o b a b i l i t y (and n e g a t i v e  f o r v e r y low l e v e l s  of brightness  levels).  F o r most o f o u r p i c t u r e s t h e d i s t r i b u t i o n was o b s e r v e d similar  o f the  t o be  t o a Maxwell d i s t r i b u t i o n w i t h d e n s i t y f u n c t i o n x  f  «  (u)  =  ^rVf"  x2e  fl  2  <*>  u  T h i s s i m i l a r i t y o f (3.3) where the frequency  w h e r e  >0  <*> ={o^x < o  u  t o the d a t a i s . apparent  of occurrence o f brightness l e v e l s  ( 3  *  3 )  i n F i g . 3.2  f o r the p i c t u r e s  GARDEN1 and HOUSE i s compared w i t h t h a t o f a Maxwell d i s t r i b u t i o n . Maxwell d i s t r i b u t i o n was p r e f e r r e d t o a d i s t r i b u t i o n  like  the R a y l e i g h  d i s t r i b u t i o n , because o f the shape o f the curve a t the o r i g i n . p a r t s are v e r y improbable, tribution.  which i s n o t w e l l modelled  The  Very  by a R a y l e i g h  dark dis-  The Maxwell d i s t r i b u t i o n has the advantage t h a t i t can be  d e f i n e d by one parameter, a .  Mean and v a r i a n c e a r e dependent; when t h e  mean i n c r e a s e s the v a r i a n c e i n c r e a s e s , as w i t h the s o u r c e d a t a . t u n a t e l y , f o r p i c t u r e s l i k e HOUSE o r TEST PATTERN h i g h l e v e l s  Unfor-  of brightness  17.  Fig.  3.1  Histograms o f i n t e n s i t y l e v e l s f o r each c o l o u r p l a n e and f o r the e n t i r e p i c t u r e f o r t h e p i c t u r e GARDEN1  18.  GARDEN1  MRXWELL DISTRIBUTION B I V  S  >-o UJ ZD o UJ—  64.0  isa.D  256.0  INTENSITY LEVEL  3.0  64.0  128.0  INTENSITY LEVEL  192.0  25B.0  HOUSE  MAXWELL DISTRIBUTION B ' W  64.0  128.0  INTENSITY LEVEL  F i g . 3.2  258.0  Histograms of i n t e n s i t y  3.0  GO  T  128.0  INTENSITY LEVEL  r  192.3  l e v e l s and Maxwe?l d i s t r i b u t i o n .  1 256.0  19. are somewhat more probable than predicted by a Maxwell d i s t r i b u t i o n having the same variance as the data. (See Appendix A). 3.3  Second Order S t a t i s t i c s :  3.3.1  Introduction:  In order to a n a l y t i c a l l y study various p i c t u r e coding algorithms i t i s v i r t u a l l y imperative to use a wide-sense s t a t i o n a r y model f o r the source data.  Wide-sense s t a t i o n a r i t y implies, f o r instance, that the f i r s t  order s t a t i s t i c s and the c o r r e l a t i o n function of the data should not depend on the s p a t i a l dimension x.  F i g . 3.3 shows the estimated mean n^.(x) (3.4)  as a function of x f o r each X^ averaged over the s i x p i c t u r e s , and the estimated standard deviation a-y (x) (3.5) of the brightness i  V  x  )  =  S i , k-1 ! !j = lV ' ^ i ) ,  1  N  m  = 256,  M  <-*> 3  N  2  k=l j-1  i  (3.5)  1  M = 6.  i s the brightness of the k  th picture.  Considering the colour dimension,  the following mean of the  brightness as a function of X averaged over the s i x pictures i s shown i n F i g . 3.4 (curve denoted AV). M N N n(*> r^r  I  I  I  Ufc ( X i . y j . x )  (3.6)  k=l j = l i = l Those parameters (3.4, 3.5, 3.6), measured on a l i m i t e d s e t of 6 samples p i c t u r e s , are r e l a t i v e l y constant.  Considering the f a c t that a colour  processing system i s l i k e l y to process a great v a r i e t y of d i f f e r e n t p i c tures, the assumption of s t a t i o n a r i t y becomes acceptable. In the present study, the processing system w i l l be adapted to a s p e c i f i c type of p i c t u r e , the type being defined by the c o r r e l a t i o n  20.  ENSEMBLE  ENSEMBLE  AVERAGE  AVERAGE  o.o  —I 64.0  :  —1  -1  1 12a.o  192.0  0.0  256.0  128.0  :  192.0  Mean and Standard d e v i a t i o n o f t h e b r i g h t n e s s as a f u n c t i o n of t h e s p a t i a l dimension x  375.0  Fig. 3.4  64.0  X DIMENSION  X DIMENSION  Fig. 3.3  T  T  -1  425.0  1  475.0  WAVELENGTH  r  525.0  Mean o f the b r i g h t n e s s as a f u n c t i o n o f t h e wavelength p i c t u r e and averaged over t h e s i x p i c t u r e s .  f o r each  1 256.0  21. a l o n g the three  dimensions x, y and X.  Each p i c t u r e o f the s o u r c e  s e t c o n s t i t u t e s one sample o f a type o f p i c t u r e . assumed and the s t a t i s t i c s that  data  E r g o d i c i t y w i l l be  f o r the type o f p i c t u r e w i l l be deducted  from  sample. In F i g . 3.4, the average o f the b r i g h t n e s s  f o r each p i c t u r e i s shown. colours  are more predoiAinant  Estimation The  of X  I t must be n o t e d t h a t i n some p i c t u r e s  some  than o t h e r c o l o u r s  t u r e HOUSE f o r i n s t a n c e ) . 3.3.2  as a f u n c t i o n  ..  of P i c t u r e  following  ( b l u e i n the sky o f p i c -  Statistics:  c o r r e l a t i o n c o e f f i c i e n t s between  p i c t u r e elements, a l o n g the s p a t i a l dimensions were f i r s t follows:  N Ax,Ay,AX  a  x  I  j 1i = l [U(  n =  where:  x  fz  f  i _ ? _ 1 A  k  f  u(  X i  ,  y j  X i  + Ax,  Y j  + Ay, X ) - n ^ ] k  ,x )  (3.7)  (3.8)  k  j=l i=l  k  and:  e s t i m a t e d as  N  I  -  consecutive  N  N  N  (3.9) 1-1 i = l  F i g . 3.5 shows: p f o r Ay = 0, Ax = 0,1,2,...,14 f o r the p i c t u r e GARDEN1 and GARDEN3. p  forAx=  The same f u n c t i o n s  appear i n F i g s . B1-B4 i n Appendix B. which i s mainly b l u e , dent o f X.  Fig.  0, Ay = 0,1,2,...,14  f o r the same p i c t u r e s .  for X = Xj,X2,X3,...,Xg 3.6 shows:  for X =  Xj,X ,X ,...,Xg 2  3  f o r the r e s t o f the p i c t u r e s  E x c e p t f o r t h e p i c t u r e BUILDING  this correlation coefficient i s relatively  indepen-  Fig.  3.6  Correlation coefficient  i n the s p a t i a l d i r e c t i o n Y for the pictures GARDEN1 and GARDEN3  24.  The f o l l o w i n g c o r r e l a t i o n c o e f f i c i e n t , a l o n g  the c o l o u r  dimen-  s i o n , was then e s t i m a t e d as f o l l o w s : 1 P  X i , AX » A  k  A  1  a ~ °X X +AX  =  A  k  N  N  I I [U(x i=l j=l  N" 2  N  k  1 > y j J  , X ) - n ] [ U ( x ,y.,X i J k  X k  ~ X Axl  3  k +  a  n  o"x  a  a  r  e  k  cient  defined  i n 3.8 and 3.9 r e s p e c t i v e l y .  x  This  10  coeffi-  (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 , X 2 , X 3 , . . . , X ^  f o r the p i c t u r e s GARDEN1 and GAEDEN3. F i g s . B5,6 i n Appendix B. on X. and  A )  <' >  n  where  +  k  P i c t u r e s having very  The r e s t o f the d a t a appears i n  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 depends v e r y much s p e c i f i c c o l o u r s , such as t h e TEST PATTERN  the BUILDING have a l o w - c o 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 o f 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 c o l o u r dimension i s r e l a t i v e l y h i g h . One can a n t i c i p a t e bandwith r e d u c t i o n by use of e f f e c t i v e s o u r c e coding  techniques.  3.4  Choice o f a Model: Previous  experiments  [6,18] have l e d t o the a d o p t i o n o f 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 data.  pictorial  T h i s model i s a t t r a c t i v e because o f i t s a n a l y t i c s i m p l i c i t y .  the assumption t h a t the p i c t o r i a l p r o c e s s i s s t a t i o n a r y and  On  first-order  Markovian, which means t h a t the s t a t i s t i c s o f a s p e c i f i c p o i n t depend on t h e p r e c e d i n g  only  p o i n t , and i f , moreover, i t i s G a u s s i a n , then t h e a u t o -  correlation function i s exponential, looks d e f i n i t i v e l y exponential.  and t h e measured c o r r e l a t i o n f u n c t i o n  Consequently t h e f o l l o w i n g model f o r the  a u t o c o r r e l a t i o n f u n c t i o n was used f o r monochromatic p i c t u r e s by H a b i b i Wintz [6] and f o r monochromatic components o f a c o l o u r p i c t u r e Y,I,Q o r R,G,B  [19]. R^ (Ax,Ay) Y  - exp(-a|Ax|)exp(-BI Ay I)  (3.11)  and  25.  26. S e p a r a b i l i t y , which means t h a t  the c o r r e l a t i o n f u n c t i o n can be  e x p r e s s e d i n the f o l l o w i n g way i s a n o t h e r u s e f u l R^Ax.Ay) = The c l o s e n e s s  feature:  (Ax) . R ^ A y )  (3.12)  o f 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  cussed i n the next s e c t i o n .  Considering  the c o l o u r  dis-  dimension, i f the  p i c t u r e s a r e assumed t o be s t a t i o n a r y , t h e d a t a shows t h a t t h e a u t o c o r r e l a t i o n f u n c t i o n ca:. be c o n s i d e r e d 3.10,  of exponential  type.  (See F i g s .  B.8) Consequently, the f o l l o w i n g model f o r t h e a u t o c o r r e l a t i o n  f u n c t i o n o f a c o l o u r p i c t u r e was  adopted.  R ^ Y ^ A x . A y . A A ) == exp(-a|Ax|). exp (-13 | Ay | ) . exp(- |AX|) Y  The parameters a , B , Y exponential Results  were e s t i m a t e d by l e a s t square f i t t i n g each  f u n c t i o n i n the above e x p r e s s i o n ,  appear i n T a b l e 3.1.  (3.13)  The c l o s e n e s s  t o the computed  points.  o f the f i t i s e x p r e s s e d by the  number C: C = -10 l o g ( e )  (3.14)  2  where e  2  i s the mean square e r r o r between computed p o i n t s  c u r v e ; the l a r g e r C, the b e t t e r  the f i t .  The b e s t  and  fitted  f i t i s p l o t t e d on t h e  graphs o f 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 .  CORRELATION PARAMETER  Gl  0.088 0.191 0.106  23.86 23.55 15.96  G3  0.064 0.111 0.079  23.04 22.38 17.93  0.048 0.047 0.069  29.35 31.56 29.70  H  0.054 0.042 0.071  27.18 31.53 19.43  TP  0.018 0.017 0.173  35.49 46.69 12.66  0.085 0.069 0.166  15.36 19.43 13.41  T a b l e 3.1  C o r r e l a t i o n parameters a, 8 and y and c l o s e n e s s o f e x p o n e n t i a l model f i t t o observed d a t a .  The v a l i d i t y o f the above model can be c h a l l e n g e d f o r t h e following 1)  reasons: S e p a r a b i l i t y implies that the a u t o c o r r e l a t i o n f u n c t i o n decreases  more r a p i d l y i n the d i a g o n a l d i r e c t i o n than a l o n g t h e o t h e r s p a t i a l dimensions.  A priori,  t h i s does n o t seem t o be r e a s o n a b l e , s i n c e t h e c h o i c e  o f s p a t i a l d i r e c t i o n s would seem t o be a r b i t r a r y .  However, i n many  p i c t u r e s , the h o r i z o n , manmade and n a t u r a l l y o c c u r r i n g o b j e c t s c o i n c i d e w i t h 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 i n the s p a t i a l d i r e c t i o n s i s not  very close i n some cases.  The actual c o r r e l a t i o n function of weakly corre-  lated data seems to decrease f a s t e r than the exponential displacements and more slowly for large displacements.  f i t for small This i s p a r t i -  c u l a r l y 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, d i f f e r e n t models w i l l be 3.5  considered.  Non-Separable Model: For the remainder of the thesis,' a colour picture w i l l be con-  sidered as a stationary process. sidered as independent of X.  C o r r e l a t i o n c o e f f i c i e n t s w i l l be con-  For any displacement Ax, Ay or AX,  average (over X) c o r r e l a t i o n c o e f f i c i e n t w i l l be 3.5.1  Non-Separability  the  considered.  i n the S p a t i a l Dimensions:  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 s p a t i a l diagon a l d i r e c t i o n was P  AL  =  'o^W  estimated as follows:  N N I ^ { [U(x ,y ,X)- ][U(x i=l j=l i  j  n  + AL,  i  yj  + AL,X)-n]}  (3.15)  where a and r\ are the standard deviation and mean of the brightness the p i c t u r e .  Table 3.2  shows the closeness  of the f i t of the two  of  follow-  ing models to the actual data. p  P  = ~«|Ax| -g|Ay| e  Ax, Ay  Ax,Ay  =  e  e  S  e  -((a.Ax)2 + ( . A y ) 2 ) ± ( 3  The curves are shown i n F i g . 3.8 3.9  (  p  a  N o n  r  _  a  b  i  e  s e p a r  )  able)  (3.17)  f o r pictures GARDEN1 and GARDEN3, F i g .  for pictures FACE and HOUSE and i n Appendix B ( F i g . B7)  tures TEST PATTERN and BUILDING.  (3.16)  f o r the p i c -  VO  Fig. 3 . 8 Comparative f i t of separable and non-separable models to 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 s for the pictures GARDEN1 and GARDEN3,  Fig. 3.9  Comparative f i t of separable and non-separable models to diagonal s p a t i a l correlation c o e f f i c i e n t s for the pictures FACE and HOUSE.  31.  C  Closeness Separable Model  Non-separable Model  19.53 24.05 20.81 25.71 28.03 22.56  24.24 23.05 38.47 23.48 19.92 16.78  Gl G3 F H TP B  T a b l e 3.2:  Comparative c l o s e n e s s o f the f i t C(3.14) of a s e p a r a b l e model and a n o n - s e p a r a b l e model i n the d i a g o n a l s p a t i a l d i r e c t i o n .  The non-separable GARDEN1 and FACE.  model's f i t i s b e t t e r o n l y f o r the p i c t u r e s  A l l o f the o t h e r 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 p a t t e r n s 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 h i g h e r i n those d i r e c t i o n s than i n t h e d i a g o n a l . d i r e c t i o n . 3.5.2  S e p a r a b i l i t y o f t h e s p a t i a l and c o l o u r  dimensions:  Some examples o f the f o l l o w i n g c o r r e l a t i o n c o e f f i c i e n t  (3.18)  a r u p l o t t e d on F i g . 3.10. N p  AxAX *  f o r AX  =  o^N " 2  N  E  I  '.UU(x ,y , X ) - n ] [ U ( x 1  j  Ax.y X+AX)-n]}  i +  (3.18).  i=l j=i  v a r y i n g from 0 t o 5 and f o r d i f f e r e n t v a l u e s o f the parameter Ax  f o r the p i c t u r e s GARDEN1, GARDEN3 and FACE,  a  2  i s the v a r i a n c e o f the  b r i g h t n e s s o f the p i c t u r e . The  c l o s e n e s s o f a s e p a r a b l e model (3.19) it. compared t o the  closeness o f a non-separable  model (3.20) i n T a b l e 3.3.  The s e p a r a b l e  f u n c t i o n i s p l o t t e d on F i g . 3.10. =  p  Ax,AX  p  Ax,AX  e  -a|Ax| -y|AX|  (3.19)  e  6  ,-((aAx) +( AX) )* 2  2  Y  =  6  (3.20)  33.  Ax  GARDEN1  0 1 3  6  14  Ax  SEPARABLE  NONSEPARABLE  29.93 28.09 26.81 30.34 21.87  29.93 26.53 20.16 22.46 27.59  T a b l e 3.3:  GARDEN3 SEPARABLE  NONSEPARABLE  31.65 25.67 27.39 22.60  31.65 24.00 25.06 31.56  0 3 6 10  FACE  Ax  SEPARABLE  NONSEPARABLE  32.61 31.07 31.57 32.84 32.47  32.61 29.64 24.46 22.51 24.32  0 1 3 6 12  Comparative c l o s e n e s s o f the f i t o f a s e p a r a b l e model and a non-separable model i n the x-A d i r e c t i o n .  For t h e p i c t u r e FACE, t h e s e p a r a b l e model i s always b e s t . the o t h e r two p i c t u r e s the f i t o f the n o n - s e p a r a b l e f o r l a r g e v a l u e s o f the s p a t i a l d i s p l a c e m e n t 3.6  Double-Exponential I t can be noted  For  model becomes b e t t e r  (Ax > 6 ) .  Model:  t h a t the a c t u a l 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 p r e d i c t e d by the s e p a r a b l e e x p o n e n t i a l model f o r s m a l l d i s placements and more s l o w l y f o r l a r g e r d i s p l a c e m e n t s .  This i s p a r t i c u l a r l y  t r u e f o r weakly c o r 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 p o s s i b l e to o b t a i n a b e t t e r f i t t o t h e measured v a l u e s , u s i n g t h e f o l l o w i n g models: P  Ax,Ay  =  (e"  a  i  |  A  x  + e"°2' ' ).(e" ' ' + e" *  |  A x  6 1  A y  3  1 A  y 1  )/4.0  (3.21)  ;  (Separable) o = (e-K lAx,Ay a  A x  >  2 +  ( l- y> ^* B  A  2  + e^  K a 2  -  A x ) 2 +  ( 2.Ay) ]*w '' ' B  (Non-separable)  2  2  0  (3.22)  These models w i l l be r e f e r r e d t o as the d o u b l e - e x p o n e n t i a l models.  The c l o s e n e s s o f the f i t o f the s e p a r a b l e model t o the d a t a i s  compared i n Table 3.4 t o the c l o s e n e s s o f the f i t o f the s i n g l e e x p o n e n t i a l model.  The two models a r e p l o t t e d i n F i g s . 3.11, 3.12.  I  00  Fig.  j)  3.11  I  4.0  X  1  6.0  DISPLACEMENT  I  6.0  I  10.0  1  12.0  1  14.0  a l  0.0  1  2.0  1  4.0  Y  I  6.0  1  8.0  DISPLACEMENT  1  13.0  1  12.0  Comparative f i t of the single exponential model and the double exponential model i n the s p a t i a l directions for the picture GARDENl  1.  14.0  GRRDEN3  GARDENS  A ESTIMATED FROM DATA  A ESTIMATED FROM DATA  0.0  Fig.  T  2.0  3.12  -i 4.0 X  1— r 6.0 e.o DISPLACEMENT  10.0  12.0  1 M.O  2.0  1 4.0 Y  : r G.O s.o DISPLACEMENT  Comparative f i t of t h e s i n g l e e x p o n e n t i a l model and the double e x p o n e n t i a l model i n the spatial directions  f o r the p i c t u r e  GARDEN3  4*3  36.  GARDEN3  GARDEN1  X  Y  Single Exponential Model  24.55 a = 0.088  24.77 a = 0.064  Double Exponential Model  37.58 a i = 0.286 a = 0.021  36.05 ai = 0.229 a = 0.003  Single Exponential  24.32 0 = 0.191  8  25.57 = 0.111  40.28 B = 0.535 B = 0.091  81 8  43.02 = 0.308 = 0.040  2  MnHpl  Double Exponential Model  T a b l e 3.4  The  2  2  2  2  Comparative c l o s e n e s s o f t h e f i t o f t h e s i n g l e e x p o n e n t i a l and d o u b l e - e x p o n e n t i a l models i n t h e 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  non-separable  double  e x p o n e n t i a l model (3.22), p r o v i d e s an  e x c e l l e n t f i t t o the measured d i a g o n a l c o r r e l a t i o n f u n c t i o n o f t h e p i c t u r e 'GARDENING = 43.24, compared t o C = 29.38 f o r t h e s e p a r a b l e double model ( s e e F i g . 3.13).  exponential  F o r t h e p i c t u r e GARDEN3, t h e r e 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 s e p a r a b l e model, C = 22.83 f o r t h e n o n - s e p a r a b l e model. 3.7  Conclusion The problem o f c h o o s i n g even a second o r d e r s t a t i s t i c a l  a three-dimensional different  colour p i c t u r e i s d i f f i c u l t .  types o f c o l o u r p i c t u r e s .  model f o r  I t appears t h a t t h e r e a r e  The s i m p l e s e p a r a b l e c o r r e l a t i o n  func-  t i o n o f e x p o n e n t i a l type i s a t t r a c t i v e because o f 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 t h e m a t h e m a t i c a l study o f o u r p i c t u r e c o d i n g A more complex non-separable  algorithms.  model p r o v i d e s a b e t t e r f i t t o some  pictures lacking of v e r t i c a l or horizontal features.  F o r weakly  d a t a a model composed o f t h e sum o f e x p o n e n t i a l s c l o s e l y f i t s  correlated  the data i n  GRRDEN3  GARDEN1  0.0  -r  2.0  i 4.0  i 6.0  r 8.0  X-Y DISPLACEMENT  10.0  12.0  H.O  —i 2.0  1 4.0  1 6.0  i 6.0  -  10.0  -1— 12.0  X-Y DISPLflCEMFNT  Fig  3 13  Comparative f i t of the non-separable and separable double-exponential models i n the s p a t i a l diagonal d i r e c t i o n for the pictures G A R D E N 1 and G A R D E N 3 .  -1 14.0  38.  the  spatial  dimensions.  The the  i m p l i c a t i o n o f u s i n g t h e s e more s o p h i s t i c a t e d models on  t r a n s f o r m encoding system w i l l be s t u d i e d  later i n this  thesis.  39. IV 4.1  THEORY OF TRANSFORM ENCODING  Introduction A g e n e r a l t r a n s f o r m e n c o d i n g system can be r e p r e s e n t e d as shown  i n F i g . 4.1.  The source d a t a i s t r a n s f o r m e d .  p l e s a r e then r e j e c t e d i n accordance remaining and  Some t r a n s f o r m domain sam-  w i t h some q u a l i t y c r i t e r i o n .  The  samples a r e then d i g i t i z e d , t r a n s m i t t e d o r s t o r e d , D/A c o n v e r t e d  then i n v e r s e  SOURCE  transformed.  DATA REDUCTION  T  QUANTIZER  COMMUNICATION CHANNEL OR DIGITAL STORAGE MEDIUM  RECONSTRUCTED PICTURE <£  NOISE ERROR F i g . 4.1 " A n  Transform  encoding  optimum t r a n s f o r m encoding  system.  system, i n the sense o f mean-  square e r r o r between p r o c e s s e d 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 p r o v i d e u n c o r r e l a t e d samples t h a t can be i n d i v i d u a l l y  2)  To pack the maximum p o s s i b l e energy  coded.  i n t o a reduced number o f  samples so t h a t e f f i c i e n t r e d u c t i o n can be a p p l i e d i n the t r a n s f o r m domain. The Karhunen-Loeve t r a n s f o r m a t i o n a c h i e v e s the two g o a l s mentioned above.  U n f o r t u n a t e l y , the c o m p u t a t i o n a l The  a l g o r i t h m s a r e slow.  F o u r i e r t r a n s f o r m has been i n v e s t i g a t e d f o r the t r a n s m i s s i o n  of monochromatic p i c t u r e s  [6, 8,20 ] » and f o r the t r a n s m i s s i o n o f t h e  40. t h r e e components of a c o l o u r p i c t u r e [ 8 ] . of  the F o u r i e r t r a n s f o r m e x i s t  [21,22].  Fast computational  algorithms  J . P e a r l i n [23] demonstrated  t h a t , a t l o n g b l o c k l e n g t h , the F o u r i e r t r a n s f o r m approximates the mum  Karhunen-Loeve t r a n s f o r m i n p e r f o r m a n c e . The  data  Hadamard t r a n s f o r m has been a p p l i e d to the same type o f  [24],[25].  algorithm.  I t s main advantage i s an even f a s t e r  computational  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 t r a n s f o r m  in specific situations  [26].  Since i t operates  dimensions must be a power o f two, the c o l o u r dimension be  opti-  i s 6 i n this  o n l y on t e n s o r s whose  and s i n c e the s i z e o f the b l o c k s i n t h e s i s , the Hadamard t r a n s f o r m w i l l  c o n s i d e r e d i n the p r e s e n t s t u d y of c o l o u r p i c t u r e s .  possibilities  not  However, i t s  i n the case o f t i m e - v a r y i n g monochromatic p i c t u r e s , w i l l  investigated.  Both the F o u r i e r and Hadamard transforms  be  a r e non-optimum  i n t h a t they do not always y i e l d u n c o r r e l a t e d samples. .Recently the S l a n t t r a n s f o r m it  [10] has been i n t r o d u c e d because  seems t o be more c l o s e l y f i t t e d t o the s p a t i a l c h a r a c t e r i s t i c s o f  an  image. Pratt  [ 9 ] , i n t r o d u c e d the i d e a o f t h r e e - d i m e n s i o n a l  encoding by s u g g e s t i n g  the replacement  of the RGB  p i c t u r e by optimum Karhunen-Loeve components and t r a n s f o r m encoding  on each component.  transform  components o f a c o l o u r then a p p l y i n g 2  However, no e x t e n s i v e  dimensional  experimenta-  t i o n has e v e r been done u s i n g the h i g h c o r r e l a t i o n e x i s t i n g between c o l o u r planes  f o r transform  encoding.  In t h i s c h a p t e r , the t h e o r y o f t h r e e - d i m e n s i o n a l form encoding w i l l be s t u d i e d .  The performance w i l l be  a n a l y z e d and  p a r e d w i t h the t h e o r e t i c a l performance o f a two-dimensional form encoding  scheme.  Fourier transcom-  Fourier trans-  41. F i l t e r i n g and q u a n t i z a t i o n o f the t r a n s f o r m domain samples a r e likely  to a f f e c t the q u a l i t y of the r e c o n s t r u c t e d p i c t u r e .  w i l l be c o n s i d e r e d i n t h e next 4.2  These problems  chapter.  Theory o f T h r e e - d i m e n s i o n a l  F o u r i e r Transform  To t r a n s f o r m a t h r e e - d i m e n s i o n a l  Encoding:  d i s c r e t e t e n s o r u(x,y,A) i s t o  decompose i t on a s e t o f b a s i s f u n c t i o n s <> j , w h i c h , i n t h e case o f the F o u r i e r transform, a r e :  *kim ' ' (x  y  NTM"  =  x)  e  N7M  =  x  [  p  c  (  o  _  s  ^?  (kx  w-  +  ^F  +  fy  e x  f  +  p(-  x  )  m  1  S  X  I  N  )  2  7  R  (  - N  X  i  +  y  s ] x)  +  (4.1) i = f-1  where  and N , M a r e t h e dimensions o f the p r o c e s s  ( N x N x M ) and  k, £ = 0,1, . . . , N-1 and  m = 0,1  Consequently  M - l  a t e n s o r can be w r i t t e n a s : N-1 N-1 M - l  u(x,y,X) = J I I \ k=0 Z-0 m=0  l  m  ' \  l  m  (*,y*A)  .  (4.2)  where N-1 N-1 M - l V m  If  I I I < ' > '*kAm x=0 y=0 X=0  =  U  X  y  X)  ( x  '?'  X )  (  *-  o n l y nj.n2.m2 o f the F o u r i e r samples a r e k e p t ,  3 )  the recon-  s t r u c t e d tensor w i l l be: n j - 1 n ^ - l mi-1 u*(x,y,X) = J k=0 and  the mean square 1  E 2  =  N ^ ?  E  {  t  I  1=0 m=0  W  W  X  >  y  '  X  )  (  4  '  4  )  e r r o r between o r i g i n a l and r e c o n s t r u c t e d t e n s o r w i l l be: N-1 N-1 M - l I I I [u(x,y,X) - u * ( x , y , X ) ] } x=0 y=0 X=0 2  42.  N-1 N-1 M-l -£-E{ I I I Iu (x,y,X) - 2u(x,y,X).u*(x,y,X) x=0 y=0 X=0 + u* (x,y,X)]> 2  2  r ^ - 1 n - l mj-1 2  -4^(0.0.0) - ^ E !  In ( 4 . 5 ) , the p r o c e s s  l  .^(x. .»»  g  (4.5)  y  ^(Ax,Ay,AX)  i s the a u t o c o r r e l a t i o n f u n c t i o n o f  u(x,y,X),  u * ( x , y , X ) = u*(x,y,X).u*(x,y,X) 2  and  from ( 4 . 4 ) : n j - l n - l mj-1 2  u* (x,y,X) = 2  I k=0  J I 1=0 m=0  n-1  n„-l m^-1  j k'=0  l l V)l'm'-\£m - ' JL'=0 m'=0  S i n c e the nj-l I x=0  (x.y.X).  (x  are orthogonal  y  X)  (  4  '  6  )  functions  n - l m-,.-l z~^ i~^I t u* (x,y,X) = I I I y=0 X=0 k=0 £=0 m=0 n  m  2  u  2  2 k  £  m  (4.7)  Thus, (4.5) becomes: n - l n - l m -l 2  e2  where  2  1  = W'^ ' ' ) " r a tk=0 £=0 X m=0 \ 0  _  •°klm  0  2  o = E  0  {  U  ° kAm 2  (4.8)  \  k£m  }  The mean square e r r o r i s e q u a l t o the v a r i a n c e o f the o r i g i n a l p i c t u r e minus the sum o f the v a r i a n c e s o f t h e 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 v a r i a n c e o f a complex  number i s e q u a l t o the sum o f the v a r i a n c e s o f i t s r e a l p a r t and i t s imaginary  part.  The r e a l p a r t o f  *  s:  43. a k  £  m  = A.  where A =  N-1 N-1 M-l W I I I u(x,y,A).cos 2TT ( | x + f x=0 y=0 X=0  y +||x)  (4.9)  ^  and i f a., R denotes the variance of the r e a l part: 2  N-1 N-1 °  2 R  = A  2  N-1 N-1 M-l M-l . I I I I cos 2 i ( | x x=0 x'=0 y=0 y'=0 X=0 X'=0  I  I  cos 2 T T ( | x* + | y '  + g  +  |y  +  | X ) .  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:  e ^ ^ ' ' I . "Y | X-A' [  R(x,x«,y,y',X,X') = e^'*"*'!.  e  (  4  >  u  )  Using the following notations: P± 1  N-1 N-1 (z,6,N) =1 I cos 2TT(±-(Z ± z ' ^ . e " ' z=0 z'=0 V 0  2  Z  (4.12)  1  and 0± 1  N-1 N-1 N-1 . . , | (z,6,N) == I1 II s i n 27r(i(z ± z ' ) ) . e " ° " „ n „»=n z=0 z'=0 . |z  z  1  (4.13)  w  =  OR  2  and O j  2  can be written as  (4.14)  °I where  Z  =  2PM '  ( B  +  A )  (  4  '  1  5  )  A = P+Ca,x,N) .P+(B,y ,N) .P+( ,X,M) Y  - Q+(a,x,N) .Q+(8 ,y ,N) . P+( ,X ,M) Y  .  - 0+(a,x,N).P+(B,y,N).Q+( ,X,M) Y  - P+(a,x,N).Q+(8,y,N).0+( ,X,M) Y  (4.16)  44. and B = P (a,x,N).p-(g,y,N).p-( ,X,M) k  Y  - Q (cx,x,N).Q-(g,y,N).p-( ,X,M) k  Y  - Q~(a,x,N).p-(B,y,N).Q-( ,X,M) Y  - Pr(a,x,N).Q-:(S,y,N).Q-(Y,X,M) x. m  (4.17)  From equation 4.8, i t i s clear that reduction w i l l be applied i n the transform domain by keeping only the n^ x n variances are the largest.  x  2  Fourier samples whose  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 c a l c u l a t e .  The fact that the chosen  model i s separable and the Fourier transform i s unitary allows the computation of the variances to be executed i n 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 covariance matrix. by  Variances for the three-dimensional process are then obtained  the m u l t i p l i c a t i o n 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. to know how  I t would be i n t e r e s t i n g  fast the mean square error decreases as the number of trans-  mitted samples increases, and how much b e t t e r i s a three-dimensional processing system than a two-dimensional  processing system operating on the  same data. In the remainder of the t h e s i s , the signal-to-noise r a t i o , w i l l be used as a measurement of processed picture q u a l i t y : S/N dB = -10 log e  2  (4.18)  S/N,  45. e2 where e  2  =  i s the n o r m a l i s e d mean square  processed p i c t u r e ,  e  2  e r r o r between the o r i g i n a l  i s the a c t u a l mean square  o f the o r i g i n a l p i c t u r e .  The  S/N  ratio  e r r o r and a  the v a r i a n c e  2  as a f u n c t i o n o f the number of  t r a n s m i t t e d samples f o r d i f f e r e n t v a l u e s of the parameters a, 8, y d i f f e r e n t s i z e s o f p i c t u r e s i s shown on F i g . Two  and  and  4.2.  ways to a s s e s s the improvement from  two-dimensional  to t h r e e -  d i m e n s i o n a l p r o c e s s i n g are as f o l l o w s : 1)  The  s p a t i a l dimensions  of the p i c t u r e are c o n s t a n t .  s i o n a l system p r o c e s s i n g M s e p a r a t e N x N p i c t u r e s can be  compared w i t h  t h r e e - d i m e n s i o n a l system p r o c e s s i n g one M x N x N p i c t u r e . the complexity o f the p r o c e s s o r i n c r e a s e s i n the sense tem i s p r o c e s s i n g a l a r g e r number o f elements at a 2)  The  A two-dimen-  In t h i s  a  case  t h a t the second  sys-  time.  complexity o f the p r o c e s s o r i s c o n s t a n t or more p r e c i s e l y ,  t o t a l number of samples to be  transformed  system p r o c e s s i n g an N x N p i c t u r e can be  i s constant.  A  the  two-dimensional  compared to a t h r e e - d i m e n s i o n a l  system p r o c e s s i n g 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, c o n s i d e r i n g the p r o c e s s i n g o f time v a r y i n g monochrom a t i c p i c t u r e s , a two-dimensional and  a t h r e e - d i m e n s i o n a l system would p r o c e s s s e v e r a l frames t o g e t h e r . The  The  system would p r o c e s s s e p a r a t e l y each frame,  S/N  first  case  ( d i f f e r e n t complexity)  i s shown on F i g . 4 . 2 ( a ) .  r a t i o as a f u n c t i o n of the number o f samples i s p l o t t e d  B =0.06 (average v a l u e f o r the data) N = 8 and M = 6.  and  for a =  f o r d i f f e r e n t values of y  and f o r  T h i s case would a p p l y t o 6 c o n s e c u t i v e frames o f a  time  varying process. Curve (1) r e p r e s e n t s the S/N (8 x 8) and  curve  (2) the S/N  ratio  ratio  f o r a two-dimensional  for six identical pictures  8) t r a n s m i t t e d u s i n g a two-dimensional  picture  (same a  F o u r i e r transform encoding  and  system.  46.  The performance o f a t h r e e - d i m e n s i o n a l system p r o c e s s i n g an 8 x 8 x 6 p i c t u r e i s shown f o r d i f f e r e n t identical,  this  corresponds  v a l u e s o f y.  F o r y< = 0.0 a l l frames a r e  curve corresponds w i t h c u r v e  t o curve  (1).  For y i n f i n i t e  ( 2 ) . S i n c e t h e r e i s no c o r r e l a t i o n  the curve  i n the t h i r d  dim-  e n s i o n , there i s no advantage i n u s i n g a 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 p r o c e s s i n g system. The  second  case  (same c o m p l e x i t y )  performance o f a two-dimensional  i s shown on F i g . 4 . 2 ( b ) .  The  system p r o c e s s i n g a 16 x 16 p i c t u r e i s  compared w i t h t h e performance o f a t h r e e - d i m e n s i o n a l system p r o c e s s i n g an 8 x 8 x 4 and  picture for different  8 (0.06). F o r an average  a S/N r a t i o of  v a l u e s o f y and f o r the same v a l u e o f a  value of the c o r r e l a t i o n  o f about 20 dB i s reached by t r a n s m i t t i n g as l i t t l e  the t o t a l number o f the F o u r i e r samples.  approximately . ,  parameters a , B and  as a q u a r t e r  30 dB i s reached by u s i n g  a . h a l f o f the F o u r i e r samples.  Even when the c o r r e l a t i o n  f o r i n s t a n c e ) the g a i n i n S/N r a t i o  i n the t h i r d  dimension  from a two-dimensional  i s low (y = 0.18 system t o a  t h r e e - d i m e n s i o n a l system p r o c e s s i n g t h e same d a t a exceeds 2 dB. ment i n c r e a s e s as y d e c r e a s e s . ratio  y,  f o r the two-dimensional  Improve-  The g a i n i s 8 dB f o r y = 0.03 when the S/N case i s 20 dB.  48  V 5.1  QUANTIZATION OF THE  FOURIER SAMPLES  Introduction Any  formation  c o r r e l a t i o n among the F o u r i e r samples o b t a i n e d  o f a p i c t u r e w i l l be  considered  individually.  ignored;  The  variances  thus each t r a n s f o r m  inefficient  to use  the same q u a n t i z e r  I n t h i s c h a p t e r the q u a n t i z e r  a r e very, d i v e r s e , i t  f o r each sample.  used i n our  considered.  be  obtained  experiments w i l l  d e f i n e d on the b a s i s o f the s t a t i s t i c s o f the F o u r i e r samples. a l l o c a t i o n scheme w i l l t h e n be  trans-  sample w i l l  o f the F o u r i e r samples  from the model a u t o c o r r e l a t i o n f u n c t i o n (4.15, 4.16) would be  from the  For  The  be bit  the remainder of the  s i s "optimum" means "optimum i n the sense o f the mean square e r r o r " ,  theand  the a b b r e v i a t i o n 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 o f the F o u r i e r  samples  Optimum q u a n t i z a t i o n o f the F o u r i e r samples r e q u i r e s knowledge o f 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 . are e x p e c t e d to be  Gaussian, according  to the  A l l the F o u r i e r samples central limit  theorem.  The  frequency d i s t r i b u t i o n of some o f the most i m p o r t a n t F o u r i e r samples  (i.e.,  the ones h a v i n g the l a r g e s t v a r i a n c e s )  5.2  i s shown i n F i g . 5.1  f o r the p i c t u r e GARDEN1 segmented i n t o 8 x 8 x 6 d a t a f o r the p i c t u r e FACE appears i n Appendix D. represents  the r e a l p a r t  Z(u,v,w) i n the  presents  transform  and  sub-pictures. On  Fig. The  same  t h e s e graphs ZR(u,v,w)  ZI(u,v,w) the i m a g i n a r y p a r t o f the  element  domain.  The  f o l l o w i n g f a c t s were n o t e d :  1)  ZR(1,1,1) i s the D.C.  the average b r i g h t n e s s  as the s i z e of the s u b - p i c t u r e the D.C.  and  component. (ZI(1,1,1) = 0.0)  of the p i c t u r e i n a s m a l l a r e a .  It reAs  long  i s s m a l l , the f r e q u e n c y d i s t r i b u t i o n o f  component can be e x p e c t e d t o be  s i m i l a r t o the  frequency  distri-  49. bution of the brightness o f the picture i t s e l f ( i . e . Maxwell  distribution).  Compare F i g . 5.2(a) and F i g . 3.2. 2)  Most of the other samples F i g . 5.1(b) to (f) and F i g . 5.3  (a) to (c) are t y p i c a l l y Gaussian, with zero-mean, as expected. 3)  Some Fourier samples related to the colour dimension, i . e .  those with w > 1, F i g . 5.2(d) to ( f ) , although they have, i n general, a b e l l shaped d i s t r i b u t i o n , 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 c h a r a c t e r i s t i c i s the fact that, i n a l l p i c t u r e s , some colours are predominant, consequently f o r many p i c t u r e elements, the brightness, as a function of the wavelength A , has a s i m i l a r shape and the Fourier transform of each of these brightness functions has s i m i l a r Fourier components.  The mean of these samples i s very small, however,  and could be taken into account i n the processing system. 4)  For a l l the other samples with smaller variances, not r e -  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 d i s t r i b u t i o n f o r the D.C. component and to a Gaussian d i s t r i b u t i o n f o r a l l other components ( F i g . 5.3).  The  quantization l e v e l s up to 7 b i t s were computed f o r a Gaussian and a Maxw e l l d i s t r i b u t i o n according to the method outlined i n [27].  50.  F i g . 5.1  Histograms of Fourier samples f o r the picture GARDEN1  51.  ZI t*. .2.1)  5  .  2RC1.3.1)  s  e  fa)  \ j  n S.O  ^  r  ^  -30.0  —  ^  -15.0  (  , O.OoJ  — T ^ - <  15.0  (  30.0  .-•O.0  -30.0  IX10  o.o  )  3  ZRCl.1.2)  ZK1.3.1)  e  (d)  M -«5.0  -30.0  -15.0  " 0.0,,  mo  2  ,  F i g . 5.2  -15.0  (  0.0  «.0  re;  6  -30.0  30.0  ZRCl.1.3)  ZIU.1.2)  1.0  150  I  O J  (  15.0  30.0  -O.0.  Jo^  -3O.0  -15.0  (  0.0  Q J  f  15.0  3O.0  «.0  Histograms of Fourier samples f o r the picture GARDEN1  52. DC. Component  MAX  QUANTIZER  MAXWELL  MAX  k  °1  QUANTIZER  GAUSS.  MAX  .  QUANTIZER  GAUSS  Tig. 5.3  5.3  Q u a n t i z a t i o n o f the F o u r i e r samples  B i t Allocation: The problem of a s s i g n i n g M b i t s  v a r i a n c e s a? was f i r s t  t o n samples z^ o f unequal  c o n s i d e r e d by Huang and S c h u l l h e i s s [5]'. They  a r r i v e d a t the c o n c l u s i o n t h a t u s i n g an optimum Max q u a n t i z e r and assuming  u n c o r r e l a t e d Gaussian  samples, then  the optimum number o f b i t s b j f o r  the j t h q u a n t i z e r f o r the component of v a r i a n c e a? i s g i v e n by  "approximately"  the f o l l o w i n g e x p r e s s i o n : b  j *f  +  < ° l n  21n2  •I  b  3  2 +  W j  l n  °i > 2  C') 5  1  (5.2) =  M  j=l Some t r i a l  and e r r o r i s r e q u i r e d to f i n d  the optimum b i t a s s i g n -  ment . iKurtenbach  and W i n t z [ 2 8 ] , u s i n g an optimum u n i f o r m Max  p r o p o s e d the - f o l l o w i n g . a l g o r i t h m :  1)  for  Compute  the b j numbers:  j  2 •„ lnlO  n  j = 1,..., n  9  j  1 n  l  (5.3)  quantizer,  53.  2)  If  n  £ j-1  b. ^ M, arbitrarily adjust some of the m according to J  3  the following rules: a)  If 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  b)  J n 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)  2/lnlO = 0.86).  and (5.3)  are very similar (1/2.In2 = 0 . 7 2 ,  However, the second algorithm w i 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) w i l l be used in this thesis and the following restriction w i 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 transmission of pictures  PCM  [1].  I t is important to note that in applying the b i t allocation algorithm (5.3), a l l variances estimated from the model are included.  All  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 w i l l be studied.  The number of bits assigned to each sample is given  b y the algorithm outlined in the preceding section.  54. 5.4.1  Estimation of the Quantization E r r o r : The t o t a l error of the system, considering an e r r o r l e s s channel,  i s equal to the sum of the reduction error (computed i n the preceding chapter), and the quantization e r r o r [29]. be obtained  The quantization e r r o r e ^ can 2  from [27] f o r the optimum non-uniform and uniform  quantizers.  An alternative i s to use the following mathematical function which models the quantization error as a function of the number of b i t s . e  where a  2  2  = o? 10 " q i  b  J  /  (5.4)  2  i s the variance of the sample and b.= i s the number of b i t s  to the same sample.  assigned  This function was proposed by Wintz and Kurtenbach [28]  and used by Habibi and Wintz [6] to model the quantization e r r o r of an optimum uniform Max quantizer.  From the r e s u l t s published i n [27], i t i s  actually best f i t t e d to the non-uniform quantizer as shown i n Table 5.1. NUMBER OF BITS N 1 2 3 4 5  Table 5.1  Equation  QUANTIZATION ERROR UNIFORM 0.3634 0.1188 0.0374 0.0115 0.0034  QUANTIZATION ERROR NON-UNIFORM 0.3634 0.1175 0.0345 0.0095 0.0025  N io"  2  0.3162 0.1000 0.0316 0.0100 0.0031  Quantization errors as a function of the number of b i t s f o r uniform and non-uniform optimum quantizers.  (5.4) w i l l be used i n the present study to p r e d i c t the quantiza-  tion error. 5.4.2  Importance of the Quantization e r r o r : Using the c h a r a c t e r i s t i c s of the picture FACE (a = 0.048, 0 =  0.047, y = 0.069), the predicted e f f e c t of quantization on the t o t a l S/N r a t i o i s shown i n Table 5.2.  55.  N BPPE  NUMBER TRANSMITTED SAMPLES  0.25 0.5 0.75 1.00 1.50 2.00 3.00 4.00 5.00  3 5 8 10 16 31 37 53 75  Table 5.2  S/N RATIO NO QUANTIZATION dB  S/N RATIO QUANTIZATION dB  6.49 7.78 9.51 9.92 12.59 14.74 17.68 19.73 22.14  6.31 7.77 9.12 9.91 12.35 14.68 17.53 19.44 21.18  S/N r a t i o as a function of the average number of b.p.p.e. with and without quantization. Sub-picture: 8 x 8 x 6.  The e f f e c t of quantization i s very small.  The loss i n S/N  r a t i o caused, by quantization i s less than 4.5% of what the S/N r a t i o i s without quantization.  For large numbers of b.p.p.e. the loss i n S/N  r a t i o due to quantization i s l i k e l y to increase. that the b i t a l l o c a t i o n algorithm  This comes from the fact  (Section 5.3) operates i n the following  way: - i t  assigns a large number of b i t s (7,6) to the samples with large  variances i n a l l cases, consequently the quantization error on those samples i s n e g l i g i b l e (less than 0.1%); - f o r a large average number of b.p.p.e., a smaller number of b i t s (3,2) i s assigned  to a large number of samples with smaller  variances,  causing a larger quantization error i n these samples. 5.4.3  S/N Ratio as a Function of the Number of b.p.p.e.: The S/N r a t i o as a function of the average number of b.p.p.e.  can now be obtained.  In F i g . 5.4, the v a r i a t i o n of the S/N r a t i o , as a  function of the average number of b.p.p.e. , i s shown for various  cases.  56.  a)  A three-dimensional  system p r o c e s s i n g an 8 x 8 x 6 p i c t u r e i s  compared to a two-dimensional b)  A three-dimensional  system p r o c e s s i n g the same d a t a . system p r o c e s s i n g an 8 x 8 x 4  compared to a two-dimensional  system p r o c e s s i n g a 16 x 16  I t i s seen t h a t the g a i n i n S/N  r a t i o from the  system to the t h r e e - d i m e n s i o n a l v a r i e s between 2 dB 5.4(b) and 9 dB  f o r y = 0.03  o f b.p.p.e. 2,3. i n F i g . 5.4  S/N The  found  a = 8 =  two-dimensional  f o r y = 0.12,  i n Appendix  Fig.  f o r a r e a l i s t i c number curves  C.  R a t i o as a F u n c t i o n of the S u b - p i c t u r e S i z e :  v a r i a t i o n o f the S/N  s p a t i a l dimensions, for  picture.  D e t a i l s on the computations used to o b t a i n the  can be  5.4.4  i n F i g . 5.4(a) and  picture is  0.06  ratio  as a f u n c t i o n o f the s u b - p i c t u r e  f o r v a r i o u s v a l u e s of the average number o f b.p.p.e.,  and  f o r v a r i o u s v a l u e s o f y>  - For s m a l l s i z e s , 4 x 4 x 6  i s shown on F i g .  to 8 x 8 x 6  the S/N  5.5.  ratio increases  r a p i d l y with i n c r e a s i n g s i z e . for  Above 8 x 8 x 6 ,  and  f o r more than 2 b.p.p.e., the g a i n i n  l a r g e r s i z e i s very s m a l l . 5.5  Conclusion - Simulation In the n e x t  Technique:  c h a p t e r , the i n f l u e n c e o f some parameters on  performance o f the t h r e e - d i m e n s i o n a l i n F i g . 5.6, way.  S/N  The  w i l l be s t u d i e d .  p i c t u r e was  digitized  The  system was  and s t o r e d on  segmented i n t o s m a l l e r s u b - p i c t u r e s . transformed  [31].  Given  a s e t of v a r i a n c e s was the r e c e i v e r .  transform encoding  ct, 8 and y,  system  represented  s i m u l a t e d i n the f o l l o w i n g tape  ( F i g . 2.1),  Each s u b - p i c t u r e was  and  w h i c h r e p r e s e n t a type o f p i c t u r e ,  Some F o u r i e r samples were r e j e c t e d a c c o r d i n g t o an a The  then  Fast F o u r i e r  computed (4.14)(4.15) at t h e t r a n s m i t t e r and  f i x e d average number of b.p.p.e.  the  remaining  as o u t l i n e d i n the p r e c e d i n g s e c t i o n and  at priori  samples were q u a n t i z e d  transmitted or s t o r e d using a  Fig.  5.4  S/N r a t i o a f u n c t i o n o f t h e a v e r a g e 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 encoding systems.  58.  F i g . 5.5  S/N  r a t i o as a function of the sub-picture  size  MAX QUANTIZER  Z(UjVyW)  n^xm  samples  MAXWELL  BIT  FOURIER REDUCTION  ALLOCATION  TRANSFORM  MAX  (<n  xm  QUANTIZER  samples)  GAUSS  DIGITAL (FOURIER  D/A  \  CONVERSION  [TRANSFORM)  COMMUNICATION, CHANNEL  CR  STORAGE MEDIUM  Z(u,y,w) F i g . 5.6  Three-dimensional transform encoding system  NOISE  60.  natural binary code.  In the receiver, using the same set of variances as  i n the transmitter, the b i t s 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 F i g . 2.5. An adaptive system which estimates a, 6 and y f o r each sub-picture, sends these estimates to the Reduction-Bit A l l o c a t i o n 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 c h a p t e r , the r e s u l t s o f v a r i o u s experiments  on t r a n s f o r m  encoded c o l o u r p i c t u r e s are d e t a i l e d , and the f o l l o w i n g p o i n t s d i s c u s s e d : 1)  The q u a l i t y o f the p r o c e s s e d p i c t u r e as a f u n c t i o n o f the sub-  p i c t u r e s i z e and the average number o f b.p.p.e. 2)  The a b i l i t y o f the model ( e x p o n e n t i a l a u t o c o r r e l a t i o n f u n c t i o n )  to p r e d i c t  t r a n s f o r m encoding  system performance.  Three d i f f e r e n t measurements o f the e r r o r between the p r o c e s s e d and t h e 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 t h i s  chapter.  They  are the f o l l o w i n g (see F i g . 6.1): 1)  "The e s t i m a t e d S/N r a t i o computed from t h e e s t i m a t e d v a r i a n c e s " ,  was d e f i n e d i n Chapter  4.  Assuming t h a t the p i c t u r e i s a s t a t i o n a r y  c e s s , a model f o r the a u t o c o r r e l a t i o n f u n c t i o n was chosen.  Using  pro-  this  model, a s e t o f e s t i m a t e d v a r i a n c e s o f the t r a n s f o r m samples was c r e a t e d . T h i s s e t o f v a r i a n c e s was then used 2)  to estimate  the e r r o r  ( F i g . 6.1(a)).  S i n c e the t r a n s f o r m 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 a c t u a l v a r i a n c e s o f the t r a n s f o r m 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 g i v e s the " e s t i m a t e d S/N r a t i o from the a c t u a l v a r i a n c e s " . 3)  computed  ( F i g . 6.1(b)).  Once the p i c t u r e was p r o c e s s e d , i t was p o s s i b l e t o "compute the  S/N r a t i o " by computing t h e mean square processed p i c t u r e .  d i f f e r e n c e between o r i g i n a l and  (Fig. 6.1(c)).  A s i m p l e experiment  was performed,  w h i c h g i v e s an example o f the  t h r e e k i n d s o f measurements which have j u s t been d e f i n e d . p i c t u r e s were segmented i n t o 6 x 6 x 6  sub-pictures.  Each o f the s i x  Each s u b - p i c t u r e was  62.  STATIONNARY MODEL  SET OF ESTIMATED VARIANCES OF  OF PICTURE P  TRANSFORM • SAMPLES  ESTIMATED ERROR  (a)  •  P  SET OF ACTUAL VARIANCES OF FOURIER SAMPLES  FOURIER TRANSFORMATION  ESTIMATED ERROR  (b)  COMPLETE FOURIER TRANSF. ENCODING PROCESS  P  P  COMPUTED ERROR  fc)  F i g . 6.1  F o u r i e r transformed  V a r i o u s e s t i m a t i o n s o f the S/N  and o n l y the D.C. component was r e t a i n e d .  r e s u l t i n g inverse transformed average b r i g h t n e s s  Normalized  2  I n the  p i c t u r e each s u b - p i c t u r e i s r e p l a c e d by i  (Fig. 6.2(a)-(b)-(c)).  ments a r e l i s t e d i n T a b l e o^ :  ratio.  The t h r e e f o l l o w i n g measure-  6.1  v a r i a n c e o f the D.C. component  estimated  from s t a t i o n a r y e x p o n e n t i a l model f o r the a u t o c o r r e l a t i o n function (S/N)  A  (a < 1) A 2  = -10 l o g (1.0 - a  2 A  )  63.a  F i g . 6.2  Transform processed p i c t u r e s . Only the D.C. component was used to reconstruct the p i c t u r e . Sub-picture s i z e : 6 x 6 x 6 (a) G A R D E N 1 , (b) FACE, (c) TEST PATTERN  64. a  2  B  :  Normalized •  variance  o f the D.C. component,  computed from the F o u r i e r t r a n s f o r m ( g C T  (S/N)  B  (S/N)  p  = -10 l o g (1.0 - a :  (S/N) 0.5041 0.6271 0.7354 0.7315 0.735 7 0.5618  T a b l e 6.1  (S/N)  , (S/N)  In t h i s  < 1)  )  S/N r a t i o a c t u a l l y computed from the p r o c e s s e d  p Gl G3 F H TP B  2 B  2  actually  3.05 4.28 5.77 5.71 5.77 3.58  A  °B  2  0.5291 0.6647 0.7859 0.7273 0.7339 0.5123  (S/N)  B  3.27 4.74 6.69 5.64 5.74 3.11  (S/N)  picture.  c  2.49 3.53 5.33 5.66 5.79 2.-8  S/N p r e d i c t e d and computed when o n l y the D.C. component was t r a n s m i t t e d .  and (S/N)  a r e the t h r e e S/N r a t i o s  t h a t w i l l be computed  chapter.  6.2  E x p e r i m e n t a l R e s u l t s Obtained  Using Various Sub-picture S i z e s  and V a r i o u s Numbers o f B i t s P e r P i c t u r e Element 6.2.1  Sub-pictures  (B.P.P.E.):  6 x 6 x 6  In t h e f o l l o w i n g pages, t h e e x p e r i m e n t a l p r o c e s s i n g p i c t u r e s segmented i n t o 6 x 6 x 6  r e s u l t s o b t a i n e d by  s u b - p i c t u r e s and encoded u s i n g  1, 2 and 3 b.p.p.e. are p r e s e n t e d i n F i g s . 6.3, 6.4, 6.5.  The r e a d e r  s h o u l d view these and o t h e r p r o c e s s e d p i c t u r e s a t a d i s t a n c e o f a p p r o x i m a t e l y 25 i n c h e s .  The v i e w i n g d i s t a n c e i s i n f a c t an i m p o r t a n t  determinant  of s u b j e c t i v e q u a l i t y . More d a t a c o n c e r n i n g the p r o c e s s i n g o f the p i c t u r e s GARDEN! and FACE i s p r o v i d e d . T a b l e s 6.2 and 6.3 show the b i t a l l o c a t i o n s 3 b.p.p.e. samples  f o r 1,2 and  I n T a b l e s 6.4 and .6.5 the n o r m a l i z e d v a r i a n c e s o f the t r a n s m i t t e d  (a) e s t i m a t e d from the e x p o n e n t i a l model, (b) computed on the a c t u a l  65.  F o u r i e r t r a n s f o r m , a r e shown.  The format  i n which t h e d a t a i s p r e s e n t e d i s  e x p l a i n e d i n Appendix C. 6.2.2  Sub-pictures The  8 x 8 x 6 :  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 a r e p r e s e n t e d i n T a b l e s 6.6 and 6.7 f o r 1, 2 and 3 b.p.p.e. in Figs.  6.6,6.7,6.8.  The p r o c e s s e d p i c t u r e s  are shown  66. a  Fig. 6.3  Transform processed pictures Sub-picture s i z e : 6 x 6 x 6 1 b.p.p.e.  67.a  F i g . 6.4  Transform processed pictures Sub-picture s i z e : 6 x 6 x 6 2 b.p.p.e.  67.b  68.a  'Fig. 6.5  Transform processed pictures Sub-picture s i z e : 6 x 6 x 6 3 b.p.p.e.  68.b  Table 6.2  B i t a l l o c a t i o n for the picture GARDEN1 for 1,2, for a 6 x 6 x 6 sub-picture s i z e .  and 3 b.p.p.e. and  Table 6.3  B i t a l l o c a t i o n for the picture FACE for 1,2, for a 6 x 6 x 6 sub-picture size.  CARDEX1  V  \  1 0.5041 0.0275 0.0140 0.0178  1 2 3 4 5 6  0.0145 0.0023  0.0029  0.0021  0.0076  0.0049  3  1 2 3 4 5 6  0.0094  .*  1 2 3 4 5 6  5  1 2 3 4 5 6  6  1 2 3 4 5 6  2  0.0404 0.0096  0.0119 0.0019  4  3  2  1 2 3 4 5 6  1  GARDEN1  ESTIMATED VARIANCES  0.0186 0.0022  0.0063  0.0040  W  0.0077  0.0224 0.0027  2  0.5291 0.0221 0.0091 0.0078  0.0367 0.0043  1 2 3 4 5 6  0.0209 0.001.6  0.0144 0.0023  0.0025  0.0017  0.0027  0.0014  3  1 2 3 4 5 6  0.0013  4  1 2 3 4 5 6  5  1 2 3 4 5 6  6  1 2 3 4 5 6  0.0017 0.0012 2  0.0013  Table 6.4  1  1 2 • 3 4 5 6  1 0.0024  \  ACTUAL VARIANCES  0.0072 0.0044  0.0063  3 0.0122 0.0051  0.0030  4 0.0017  0.0048 0.0008  0.0014  Estimated and actual normalized variances of the Fourier samples transmitted for 3 b.p.p.e. f o r the picture GARDEN1. Sub-picture s i z e : 6 x 6 x 6 .  0.0029  FACE  \  V  1  1  1 2 . 3 4 5 6  0.7354 0.0090 0.0048 0.0059  0.0134  2  1 2 3 4 5 6  FACE  ESTIMATED VARIANCES  2  0.0092  3 0.0148  0.0145 0.0030  0.0213 0.0006  0.0049  4 0.0031  W  0.0071  3  0.0087  4  1 2 3 4 5 6  5  1 2 3 4 5 6  6  1 2 3 4 5 6  1  0.7859 0.0044 0.0023 0.0024  0.0066  2  1 2 3 4 5 6  0.0052  3  1 2 3 4 5 6  0.0021  4  1 2 3 4 5 6  5  1 2 3 4 5 6  6  1 2 3 4 5 6  0.0006  0.0045  0.0007  Table 6 . 5  1  1 2 3 4 5 6  0.0060  0.0007  1 2 3 4 5 6  \  ACTUAL VARIANCES  2  0.0061  4  3  0.0121  0.0031  0.0011  0.0030  0.0086 0.0009  0.0240 0.0003  0.0008  0.0004 0.0032  0.0006  i  Estimated and actual normalized variances of the Fourier samples transmitted for 3 b.p.p.e. f o r the picture FACE. Sub-picture size: 6 x 6 x 6 .  N3  Table 6.6  B i t a l l o c a t i o n 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  B i t a l l o c a t i o n f o r the picture FACE for 1, 2 and 3 b.p.p.e. and an 8 x 8 x 6  sub-picture size.  75.a  r  Fig. .6.6  Transform processed pictures Sub-picture s i z e : 8 x 8 x 6 1 b.p.p.e.  76.a  Fig, 6 . 7  Transform processed pictures Sub-picture s i z e : 8 x 8 x 6 2 b.p.p.e.  i  76.b  77.a  F i g . 6.8  Transform processed .pictures Sub-picture s i z e : 8x8x6 3 b.p.p.e.  77.b  78.  6.3  Discussion of the Results: From the results presented i n the preceding pages, the following  conclusions can be drawn: 1)  I t seems that approximately 2 b.p.p.e. i s a lower l i m i t  necessary  to transmit with acceptable f i d e l i t y the colour pictures i n the set used i n this thesis.  In the preceding experiments  were poorly transmitted.  bright areas i n p a r t i c u l a r  As shown i n the following chapter the subjective  quality and S/N r a t i o of the processed pictures can be .mproved by :  ing the quantizer of the D.C. 2)  modify-  component.  For most of the pictures, the r e l a t i v e ordering of the actual  variances of the Fourier samples was exponential model.  r e l a t i v e l y w e l l predicted by the  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 Table 6.9  variances.  R  =  shows the following r a t i o :  Estimated variances of the Fourier samples — :: : z : — : :;—' Actual variances of the Fourier samples  1 N  (, O . i.)  w  1  V 1 2 3 4 5 6  6  3 26 46 54 56 28  12 61 84 83 77 51  15 45 31 90 89 55  10 66 82 80  1  48 108 154 183 155 106  30 115 146 162 147 116  57 131 184 187 170 122  9 49 76 74 64 35  14 31 70 87 79 43  47 104 151 181 153 103  29 112 142 160 144 113  75 148 200 208 191 136  68 140 190 204 196 163  72 182 209 207 1 98  58 132 186 188 167 121  37 127 158 173 180 135  71 185 210 206 19 7 166  86 157 202 215 213 178  67 189 172 205 216 201  1 2 3 4 5 6  33 124 152 169 137 105  41 100 143 176 164 114  63 149 192 199 193 150  78 141 195 211 194 139  1 2 3  17 98 109 123 111 96  24 95 119 133 120 93  34 107 138 171 156 125  42 117 165 177 145 101  1 2 3 4 5 6  5 6  8  60 73 69  39  88  (a)  1  U  38 128 161 174 179 134  85 159 203 214 212 168 175  2  6 23 82 74 41 15  3 21 39 51 48 20  10 76 130 151 90 36  16 42 97 146 168 46  n 69 56 118 140 58  2 33 73 83 63 32  19 66 125 132 110 37  18 62 129 172 119 35  53 124 145 195 150 61  45 136 179 187 141 64  55 101 105 199 159 103  6  7 34 78 109 99 44  9 40 108 102 68 31  29 95 157 165 155 91  30 93 139 166 131 89  100 153 186 208 203 121  77 188 215 204 185 122  126 86 163 143 189 209 216 192 198 207 169 181  1 2 3 4  14 98 137 49  92 117  50 116 1419u 196 128  38 88 160 200 194 123  113 135 184 214 212 154  133 170 201 210 213 148  54 211 182 197 180 70  1 2 3 4  5  1 2 3 4  5  6  3  u  1 2 3 4  5  5  6  5  1 2 3 4  5 6  6  H  3  2  1  8  4 17  25 72 104 94 27  5  13 12  6  19 99 118 129 102 94  5 6  V  53 91  21 92 110 130 126 97  5 6  5  6 27 62 65 52 23  w  2 20 32 40 44 25  1 2 3  >\  4 16  4  5 22 50 59 35 IS  1 2 3 2  1 7 13 11  3  2  1  U  1 2 3 4  5  6  1  26 28 67 75 144 120 174 171 176 152 79 84  80 60 111 161 175 205 206 202 162 177 96 106  24 81 178 193 142 65  52 43 87 112 156 164 191 183 158 134 47 71  22 85 127 173 138 57  59 107 114 167 149 115  (b)  Table 6.8 Rank of (a) estimated, (b) actual variances of the Fourier samples for the picture FACE and a 6 x 6 x 6 sub-picture size.  80. f o r t h e p i c t u r e GARDEN1 segmented i n t o 6 x 6 x 6  sub-pictures.  On t h e  average the D.C. component i s p r e d i c t e d w i t h i n 10% o f i t s a c t u a l v a l u e . The  next 25 v a r i a n c e s , o r d e r e d by d e c r e a s i n g v a l u e s , a r e o v e r e s t i m a t e d ;  these are  correspond  t o t h e most important  underestimated,  but the c o r r e s p o n d i n g  t r a n s m i t t e d f o r 3 b.p.p.e. o r l e s s . by  samples.  the v a r i a n c e s e s t i m a t e d  The r e m a i n i n g  variances  F o u r i e r samples would n o t be  C o n s e q u e n t l y the S/N r a t i o p r e d i c t e d  from the e x p o n e n t i a l model w i l l b e too l a r g e .  F i g . 6.9 shows the v a r i a t i o n o f the t h r e e S/N r a t i o s  (see F i g . 6.1) as  f u n c t i o n o f the average number o f b.p.p.e. f o r a 6 x 6 x 6 s u b - p i c t u r e size.  The same data f o r an 8 x 8 x 6 s u b - p i c t u r e 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 p r o c e s s e d a l l o c a t i o n a l g o r i t h m d e f i n e d i n S e c t i o n 5.3, then  the maximum S/N r a t i o  r e a l i z a b l e i s t h e one p r e d i c t e d by t h e a c t u a l v a r i a n c e s . hypothesis,  t h e p i c t u r e s have been p r o c e s s e d w i t h o u t  To v e r i f y  v a r i a n c e s o f the F o u r i e r samples.  this  quantization, trans-  m i t t i n g o n l y the samples recommended f o r 1, 2 o r 3 b.p.p.e. S/N r a t i o i s compared i n T a b l e 6.10 w i t h  using the b i t  The r e s u l t i n g  t h e one p r e d i c t e d by the a c t u a l  In t h i s  t a b l e the s i m i l a r i t y  between  S/N r a t i o s i s e v a l u a t e d by t h e measure:  D  .  •  I  (  =  S  /  N  )  Computed -  X  ^  b 7  (  S  /  N  W c t e d l  x 100  (6.2)  ^Predicted  The p r e d i c t i o n i s e x c e l l e n t and p r e d i c t e d v a l u e s  a r e w i t h i n 10% o f the  computed v a l u e and w i t h i n 2% i n 75 p e r cent o f t h e e x p e r i m e n t s . quently  Conse-  t h e S/N r a t i o p r e d i c t e d by 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 w i l l be c o n s i d e r e d  as t h e upper l i m i t  obtainable.  81.  ff  \  u  1  2  v\  3  A  1  l  .95 I 1 .25  2 T  3  1.10 2 . 24  1.54  X  2.30  5  !  6  .69 j 1 .46 1.45 .89 |  2  3  6  .95 1.15  1  2.81  2 3  5 6  4  "  7.28 1.44 ".85 .69  5 6  1  2  3  5  A 5 6  1  2  6  2.  1.56 1.17 1.52 1.92 1.17 1.21  2.07 .39 .25 .16 .15 .24  1.48 . 35 .20 . 19 . 14 •27  1. 34 .26 . 12 .07 .08 . 18  3.62 .85 .50 .47 .35 .72  3  A 5 6  Table 6.9  I  i  .90 .11 .04 .04 .05 . 16  1  1 3  I  .65 .37 .61 .57 .99  3  2  1.53 .44 .50 .76 .40 .36  09 .59  .54 . 70 .52 .52  2 . 39 .58 . 53 .53 .46 .52  2.63 .62 .70 .69  i ;  . .  79 54  1  1 ti  1.65 .43 .49 .65 .40 .38  !  1.28 .22 .12  I  1  .12 . 15 .09 . 08 . 07  .09 .19  .6C .15 .07 .06 .07 . 16  .06 .15  .67 .08 .03 .02 .04 . 10  .84 .0 9 .C4 . 0 3 • C4 .09  .84 .07 .0 3 .03 .03 .08  . 44 . 10 . 04 . 02 .02 .07  1.08 .17 .07 .06 .05 .10  .45 .06 .02 .02 .03 .07  . 36 .08 .C3 .02 .02 .05  .43 .05 .03 .02  .07 . 02  .97 .11 .05 .04 .05 .16  .75 .06 .03 .03 .04 .09  .43 .07 .03 .02 .04 .11  .72 .16 .10 .11 .14 .19  .52 .10 .06 .07 .07 .10  .57 .08 .06 .06 .08 .12  1.45 .10 .04 .06  . 11  . 11  1  ~2.~45 • .70  .68 .15 .05 .04 .06 . 14  1.31 .09 .05 .06 .07 .17  .95 .15 .11 .16 .14 .17  i  i I i  Ratio of estimated variances to actual normalized variances for the picture GARDEN1 and for a 6 x 6 x 6 sub-picture s i z e .  82.  GARDEN 1  GARDEN3 6X6X6  CXGXG  COMPUTED  cn  0_ exec  —1 1.0  1— 2.0  N B.P.P.E.  FROM ACTUAL VARIANCES  0.0  3.0  —i 1.0  1— 2.0  -1 3.0  FROM ESTIMATED VARIANCES  N B.P.P.E.  HOUSE  FACE 6X6X6  6X0X6  oo o  2o cr-" cc  —l 1.0  1 2.0  1 3.0  0.0  N B.P.P.E.  —1 1.0  1— 2.0  N B.P.P.E.  TST PTN  3.0  BUILDING  6X6X6  6X6X6  CO  a  r-o.  ence  cn  —I 1.0  1— 2.0  N B.P.P.E.  Fig.  6.9  —i  3.0  0.0  -T l.C  1— 2.0  N B.P.P.E.  3.0  S/N r a t i o s (as d e f i n e d i n F i g . 6.1) as a f u n c t i o n of the average number o f b.p.p.e. f o r a 6 x 6 x 6 sub-picture s i z e .  83.  GARDEN3  GARDEN] 8X8X6  8X0X6  CO  o  COMPUTED  crFROM ACTUAL VARIANCES  I 1— 1.0 2.0 N B.P.P.E.  —1 3.0  0.0  FACE  —1 1— 1.0 2.0 N B.P.P.E.  -i "° 3  FROM ESTIMATED VARIANCES  HOUSE 8X8X6  8X8X6  CO  on-  ce  <n  N.  —1 1 1.0 2.0 N B.P.P.E.  1 3.0  0.0  1ST PTN  1 1 1.0 2.0 N B.P.P.E.  1 3.0  BUILDING 8X6X6  8X8X6  ca a  So to  I 1— 1.0 2.0 N B.P.P.E.  . 6.10  —i  3.0  0.0  I 1— 1.0 2.0 N B.P.P.E.  -1 3.0  S/N r a t i o s (as d e f i n e d i n F i g . 6.1) as a f u n c t i o n o f the average number o f b.p.p.e. f o r an 8 x 8 x 6 s u b picture size.  84.  D  N b.p.p.e.  Gl G3 F H • TP B  ( S / N ) r a t i o dB p r e d i c t e d by actual variances A  1  Gl G3 F H TP B  2  Gl G3 F H TP B  3  T a b l e 6.10  ( S / N ) r a t i o dB computed No q u a n t i z a t i o n B  |(S/N)  A  l -  (S/N) | B  (S/N)  A  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  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  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  Normalized d i f f e r e n c e between (S/N) p r e d i c t e d by a c t u a l v a r i a n c e s and computed w i t h o u t q u a n t i z a t i o n o f the components.  The "goodness" o f the p r e d i c t i o n o f the S/N r a t i u u s i n g the v a r i a n c e s estimated  u s i n g the s i m p l e  e x p o n e n t i a l model can now be e v a l u a t e d by t h e  measure T>2'  D  1^ ^ E s t i m a t e d = 100 x —  Variances " ( / ) A c t u a l Variances! S  ~~~— (S/N)  2  D£ i s p r e s e n t e d  A c t u a  i  ,c o\  N  —  \°'iJ  Variances  i n T a b l e 6.11 as a f u n c t i o n o f the average number o f  b.p.p.e. Measure S/N r a t i o  i n c r e a s e s w i t h i n c r e a s i n g number o f b.p.p.e.  The  as a f u n c t i o n o f the number o f t r a n s m i t t e d samples (no q u a n t i -  z a t i o n ) i s shown i n F i g . 6.11, f o r a l l p i c t u r e s u s i n g an 8 x 8 x 6 s u b picture size.  The number o f samples N t r a n s m i t t e d f o r 1, 2 and 3 b.p.p.e.  i s shown on the same graphs.  85.  6 x 6 x 6  8 x 8 x 6  1 b.p.p.e.  2 b.p.p.e,  3 b.p.p.e,  5.80 6.66 7.59 2.42 6.16 11.18  35.6 33.21 9.27 13.58 143.49 14.09  38.53 46.95 28.45 33.59 139.16 28.63  13.99 12.10 0.0 5.15 3.53 3.95  31.51 36.22 20.43 25.30 2.67 15.43  33.69 44.84 24.70 30.28 6.83 24.46  Gl G3 F H  TP B  Gl G3 F H  TP B  T a b l e 6.11  The  Normalized d i f f e r e n c e between a c t u a l S/N r a t i o and S/N r a t i o p r e d i c t e d from the e s t i m a t e d v a r i a n c e s o f the F o u r i e r samples.  poor p r e d i c t i o n of t h e S/N r a t i o i s n o t the o n l y  r e s u l t i n g from the use o f t h e simple The  disadvantage  e x p o n e n t i a l model based on s t a t i o n a r i t y .  q u a n t i z e r s make use o f the e s t i m a t e d v a r i a n c e s .  I f the estimated  v a r i a n c e s a r e i n c o r r e c t , then the q u a n t i z a t i o n e r r o r i s l i k e l y 4)  t o be i n c r e a s e d .  The d i f f e r e n c e between computed S/N r a t i o and t h e maximum S/N  r a t i o t h e o r e t i c a l l y o b t a i n a b l e cannot be e x p l a i n e d s o l e l y by a d d i t i o n o f quantization.  As was shown i n S e c t i o n 5.4.2, t h e e f f e c t o f q u a n t i z a t i o n  s h o u l d be v e r y s m a l l . n  3  = I  The measure D^: ( S / N )  Computed "  ( S / N )  A c t u a l Variances!  ( / )Actual S  N  i s shown i n T a b l e 6.12 f o r the 8 x 8 x 6 is  1  0  0  ( 6  . )  Variances  case.  the poor t r a n s m i s s i o n o f v e r y b r i g h t a r e a s .  shown i n F i g . 6 . 1 2 ( a ) - ( b ) - ( c )  x  The main s o u r c e  of error  The d i f f e r e n c e s i g n a l i s  f o r a 16 x 16 x 6 s i z e and 2.0  b.p.p.e.  4  400.0  "I 400.0  F i g . 6.11  S/N r a t i o as a function of the number of transmitted samples (no quantization) f o r an 8 x 8 x 6 sub-picture s i z e . The number of transmitted samples f o r 1,2 and 3 b.p.p.e. i s i n d i c a t e d .  87.  3 1 b.p.p.e. Gl G3  F H TP B  12.27 28.61 41.66 17.29 10.18 1.84  T a b l e 6.12  5)  As p r e d i c t e d  2 b .p .p .e. 25.94 31.15 44.62 22.20 13.81 6.46  3 b.p.p.e, 30.18 33.93 51.31 26.46 17.32 10.17  N o r m a l i z e d 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 p r e d i c t e d by actual variances.  i n s e c t i o n 5.4.4, f o r the same number o f b.p.p.e.  the S/N i s h i g h e r f o r the l a r g e r s u b - p i c t u r e  size 8 x 8 x 6  than f o r  6 x 6 x 6 . 6) used.  In the r e s t of the t h e s i s a 16 x 16 x 6 s u b - p i c t u r e The upper t h e o r e t i c a l l i m i t  size w i l l b  i n S/N r a t i o due to i n c r e a s i n g sub-  p i c t u r e s i z e ( F i g . 5.5) w i l l be assumed to have been r e a c h e d .  88.a  F i g . 6.12  Absolute difference s i g n a l between processed and o r i g i n a l p i c t u r e s . Sub-picture s i z e : 16 x 16 x 6 2 b.p.p.e. (a) GARDEN1, (b) FACE, (c) TEST PATTERN  88.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 i n the S/N  the processed pictures was  r a t i o and i n the subjective q u a l i t y of  obtained by modifying the quantizer of the  D.C.  component. 2)  Prediction of the S/N  r a t i o could be made more, accurate by  using  a model for the autocorrelation function that would y i e l d a set of estimated variances  of the Fourier samples i d e n t i c a l to the actual variances.  us a of a better model was 3)  The  studied.  The parameters a, 8 and y of the model autocorrelation function have  heretofore been obtained using c o r r e l a t i o n c o e f f i c i e n t s 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  Fourier  samples.  these parameters to the receiver along with the  A simpler adaptive system which c l a s s i f i e d the sub-pictures  limited number of categories was 4)  into a  investigated.  The e f f e c t 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 d i s t r i b u t i o n , very bright areas are improbable (Figs. 3,2,  7.1),  brightness  and the optimum Max  quantizer chooses l e v e l s closer to the average  i n order to minimise the quantization e r r o r .  The D.C.  component  of the Fourier sample i s not p e r f e c t l y modelled by a Maxwell d i s t r i b u t i o n ,  90. some very bright areas are responsible f o r very high, values of the D.C. component.  In order to process these areas properly, a new quantizer f o r  the D.C. component was devised to ensure that the maximum values w i l l be correctly transmitted.  The highest 64 l e v e l s of the D.C. quantizer were  empirically l i n e a r l y scaled so that the highest quantization l e v e l ensures the correct transmission of the highest possible value of the D.C. Fourier component f o r that set of p i c t u r e s . the "adapted modified quantizer".  This quantizer w i l l be r e f e r r e d to as  F i g . 7.1 summarizes this operation f o r  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 s i x pictures were processed with this new quantizer, a 16 x 16 x 6 subpicture size and an average of 2.75 b.p.p.e. ( F i g . 7.2). The subjective quality of those pictures was improved s i g n i f i c a n t l y , The various numerical results are shown i n Table 7.1, with the measure D^ D  3  = I  Computed " ( S / N ) (S/N)  S/N r a t i o from estimated variances Gl G3 F H TP B  9.91 12.16 15.11 15.10 18.32 11.37 Table 7.1  Actua  A c t u a l  Variances 1  x  1  0  (  0  7 - 1  )  - ^ variances  S/N r a t i o from actual variances 8.99 10.28 13.92 13.49 18.96 10.97-  S/N r a t i o computed 8.31 9.39 12.38 12.79 17.93 10.77  D  3  7;5 8.65 11.06 5.19 5.43 1.82  S/N r a t i o s i n the 16 x 16 x 6 case, using the adapted quantizer and 2.75 b.p.p.e., and normalized difference between computed S/N r a t i o and S/N r a t i o predicted by the actual variances.  The normalized difference between -,he computed S/N ratio and the maximum S/N r a t i o estimated from the actual variances i s s i g n i f i c a n t l y smaller than i n previous experiments  (compare with Table 6.12).  The subjectively unpleasant c h a r a c t e r i s t i c s were caused by subpictures of high c o n t r a c t , including the c o l l a r i n FACE, some parts of the bridge i n GARDEN3 and some sub-pictures i n TEST PATTERN.  The s u b j e c t i v e l y  unpleasant e f f e c t s are due to the f i l t e r i n g of steep gradient of the v a r i a t i o n of the brightness. In order to test the adapted quantizer, two t y p i c a l 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 s i z e : 16 x 16 x 6 2.75 b.p.p.e. Adapted quantizer  93.  where a  z  i s the variances of the D.C. component.  For the two pictures  chosen: GARDEN1  a  HOUSE  a*  2 y  = 0.5291  e  = 0.7273  E j = 0.00023  2  = 0.00017 2  Therefore, the e f f e c t on the g l o b a l error should be very small. Suppressing  the quantization of the D.C. component increased the S/N r a t i o  by 0.01 dB for the picture GARDEN1 and by 0.02 dB for the p i c t u r e HOUSE. I t can be concluded that the new quantizer i s properly adapted to the data. 7.3  Attempts to Improve Performance by Use of a More precise Model: Fig. 7.3  represents the v a r i a t i o n of the S/N r a t i o as a function  of the number of transmitted samples i n 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 estimated variances i s considerably higher.  The S/N r a t i o predicted by The improvement of the  prediction of the S/N r a t i o , by looking' for an estimated set of variances closer to the true variances of the Fourier samples, i s considered i n this section. A few experiments showed that there was no simple function R(u,v,w) such that o (u,v,w) = R(u,v,w) . a (u,v,w) 2  2  a  for a l l p i c t u r e s .  e  In (7.2) a  2  a  (7.2)  represents the actual variances and a  2 g  the  estimated variances. 7.3.1  Non-separable model: It i s reasonable  to expect a b e t t e r p r e d i c t i o n from a function  94.  0.0  20.0  «.0  63.0  80.0  tt  F i g . 7.3  10O.O  130.0  141.0  1S0.0  1X10' I  S/N r a t i o s 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 f o r a 16x16x16 sub- picture s i z e . The S/N measured f o r 2.75 b.p.p.e. are shown.  95. which models the  a u t o c o r r e l a t i o n f u n c t i o n more c l o s e l y  separable  exponential  separable  model p r o v i d e d  in  the d i a g o n a l  s e c t i o n i t was separable i t was  iances  In S e c t i o n  d i r e c t i o n , i n the  two  n o t e d t h a t , f o r the  model was  model.  3.5,  c o l o u r dimension, the  The  to s t u d y the s e t of v a r i a n c e s  computer time i n v o l v e d  For the s e p a r a b l e  Even a very  the IBM  For  from the f i r s t 64 The  S/N  and  the S/N  the  first  t o the S/N  r a t i o p r e d i c t e d by  ten variances  model i s used.  are not  8 x 8 x 6 sub-picture  The  and  For  very  seconds  x 6 picture size  a r e the  384 per  simula-  the  var-  t h i s model f o r the p i c t u r e GARDEN1  model.  of higher  One  the can  actual  variances,  conclude  that  separable  rank samples are s m a l l e r  C o n s e q u e n t l y , the p r e d i c t e d  c l o s e to t h a t p r e d i c t e d by  computation of the  i t took  highest  the  actual  variances.  than S/N  variances.  main disadvantage o f the n o n - s e p a r a b l e model i s the  i n v o l v e d i n the  varexperiments  the  that reason, only  r a t i o p r e d i c t e d by  model.  non-  at l e a s t 2 hours  so a c c u r a t e l y e s t i m a t e d as when a  those e s t i m a t e d u s i n g the s e p a r a b l e r a t i o i s smaller  Consequently,  370/168 t o compute the  the s e p a r a b l e  A l s o , the v a r i a n c e s  non-  computation o f the  samples whose a c t u a l v a r i a n c e s  compared, i n F i g . 7.4,  In the same  l a r g e r than i n p r e v i o u s  a 16 x 16  r a t i o p r e d i c t e d by  function  computed from the  e f f i c i e n t program mould r e q u i r e s  t i o n would become p r o h i b i t i v e l y e x p e n s i v e .  is  i n the  model, f o r an  to compute a l l of the v a r i a n c e s .  were computed.  non-  f i t of the  With the n o n - s e p a r a b l e model i t takes about 25  variance.  iances  FACE.  b e t t e r f o r large s p a t i a l displacements.  than 1 minute o f C.P.U. time on  variances.  noted that a  cases GARDEN1 and  o f the F o u r i e r samples i s c o n s i d e r a b l y  ( S e c t . 4.2).  i t was  simple  a c l o s e r f i t to the computed a u t o c o r r e l a t i o n  deemed i m p o r t a n t  separable  less  model.  than does the  time  96.  C3  F i g . 7.4  Comparison between S/N r a t i o s , 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 8x8x6. Picture GARDEN1.  97. 7.3.2  Double Exponential Model:  A better f i t to the computed autocorrelation function was obtained, f o r the weakly correlated pictures GARDEN1 and GARDEN3, using a sum of two exponentials (section 3.6).  The S/N r a t i o predicted by  this model i s compared i n F i g . 7.5, to the S/N r a t i o predicted by the separable model.  The prediction i s not s i g n i f i c a n t l y 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 p i c t u r e , i s t h e o r e t i c a l l y the best set a v a i l a b l e , 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. presented on F i g . 7.6 f o r 2.75 b.p.p.e. obtained i n this experiment  The r e s u l t s are  Table 7.2 compares the S/N r a t i o  to the one obtained when the estimated var-  iances were used.  (S/N) Gl G3 F H TP B Table 7.2  A  8.32 9.39 12.38 12.77 17.93 10.78  (S/N)  B  8.59 9.25 12.20 13.31 17.72 10.95  (S/N)^: Measured S/N r a t i o 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 r a t i o 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  N  F i g . 7.5  IOO.O  170.0  ln.o  160.0  1X10' )  S/N r a t i o s 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 s i z e 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 y i e l d e d a better S/N r a t i o i n 3 cases (GARDEN1, HOUSE, BUILDING). other pictures there was a s l i g h t degradation.  For the three  There was no noticeable  difference i n the subjective quality of the pictures processed e i t h e r model.  using  For a l l s i x p i c t u r e s , use of the actual variances was  found to have the disadvantage  of r e q u i r i n g the transmission of a l a r g e r  number of Fourier samples, according to the algorithm defined i n Section 5.3. For example f o r the p i c t u r e GARDEN3, Table 7.3 compares the b i t allocations using the estimated variances and the actual variances. In the case where actual variances are used, i t i s seen that a large number of samples has to be transmitted using a very low number of b i t s  (1,2).  101.  u V  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16  1 7 7 7 7 6 6 6 6 6  2  7 7 7 6 6 6 5  7 7 5 5 4 4 4 4 4 4 4 4 4 5 5 7  3 7 6 5 5 4 4 4 4 4 4 4 4 4 5 5 6  6 5 4 0 0 0 0 0 0 0 0 0 0 4 4 5  7 5 4 4 0 0 0 0 0 0 0 0 0 0 4 5  4 6 5 3 0 0 0 0 0 0 0 0 0 0 0 0 5  6 5 0 0 0 0 0 0 0 0 0 0 0 0 4 5  6  5 6 4 0 0 0 0 0 0 0 0 0 0 0 0 0 4  6 4 0 0 0 0 0 0 0 0 0 0 0 0 0 4  5 4 0 0 0 0 0 0 0 0 0 0 0 0 0 4  5 4 0 0 0 0 0 0 0 0 0 0 0 0 0 4  8  7 5 4 0 0 0 0 0  5 4 0 0 0 0 0  5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  ._o 0 0 0 0 0 0 0 4  0 0 0 0 0 0 0 4  9  6 4 0 0 0 0 0 0 0  0  6 0 0 0 0 0 0 0 0 0  0 0 0 0 0 4  T o t a l : 92  u V  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16  1 7 6 4 4 3 3 3 3 3  J  2  6 5 4 3 3 2 1  5 5 4 3 3 2 1 1 1 1 2 2 2 3 4 5  5 5 4 3 2 2 1 1 1 1 2 2 2 3 4 4  4 4 3 3 2 2 1 1 1 1 1 2 2 2 3 4  4 3 3 3 2 1 1 1 1 1 1 1 2 2 3 4  4 3 3 2 2 1 1 1 1 1 1 1 1 2 2 2 3  3 3 2 2 2 1 1 1 1 1 1 1 1 2 2 3  2 2 2 1 1 1 1 0 0 0 1 1 1 1 2 2  1  6  5 2 2 2 1 1 1 0 0 0 1 1 1 1 1 2 2  2 2 1 1 0 1 0 0 0 0 0 1 1 1 1 1  2 2 1 1 1 0 0 0 0 0 1 1 1 1 1 2  2 1 1 0 1 1 0 0 0 0 0 0 0 1 1 1  1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1  1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1  T o t a l : 177 T a b l e 7.3  samples  8 2 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1  4 0 0 0 0 0 0 0 0  9 2 1 1 0 0 0 0 0 1  1 1 1 0 0 0 0  samples  B i t a l l o c a t i o n s obtained (a) by u s i n g the e s t i m a t e d v a r i a n c e s , (b) by u s i n g the 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 i n the p l a n e w = 1.  102.  7.4  Adaptive Processing for Improved Performance; Two t y p i c a l 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] c l a s s i f i e d the sub-pictures i n three categories depending on the amount of d e t a i l s and the average brightness of the sub-pictures. In the present study the parameters a, 3 and y have been estimated over the e n t i r e p i c t u r e .  I t i s l i k e l y that they are not repre-  sentative of a l l regions of the p i c t u r e .  Some parts of the p i c t u r e of  constant brightness and colour do not require as many b i t s as highly detailed areas.  An adaptive system would take those v a r i a t i o n s i n t o  account, attach a set of parameters a, 3, y to each.sub-picture,  or group  sub-pictures i n t o 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 i n Chapter 2. Some results are presented  for the p i c t u r e FACE:  In F i g . 7.7, two s c a t t e r p l o t s (a versus  3 and y versus a)  show the following c h a r a c t e r i s t i c s : i)  a large number of sub-pictures have high values for ct, 3 and y  (larger than 0.5), ii)  the rest of the sub-pictures are grouped i n two c l u s t e r s , one  where a > 3, the other where 3 > a. S i m i l a r results were obtained for the other pictures.  103. XXX XX  X X  X  X >K  X  X  0.0  :.s  0.5  ALPHA  2.0  X  X  X X X X  X  X X X  X  x  Xx X X X  xx  X  X  xx  X X  x  X  X  Xx  £ X  *  0.0  o.s  X XXv  I— 1.0  X  X  t.S  2.0  ALPHA  Fig.  7.7  i— 2.S  -1 3.0  Estimated v a l u e s o f t h e c o r r e l a t i o n parameters 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 ) a n d (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 t h e i r corresponding p o s i t i o n i n the o r i g i n a l p i c t u r e are represented i n F i g . 7.8. By comparing these plots with the o r i g i n a l p i c t u r e ( F i g . 2.6c) the following facts can be i)  noted:  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. ii) areas.  the areas weakly correlated (high parameters) are mostly dark Such areas are very noisy and should not require accurate coding.  The f i l t e r i n g e f f e c t caused by the processing should not a f f e c t the subj e c t i v e quality of the picture. In conclusion, for the p a r t i c u l a r picture considered, three d i f f e r e n t kinds of sub-pictures were considered (see F i g . 7.7). 1)  sub-pictures with h o r i z o n t a l features  2)  sub-pictures with v e r t i c a l 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<  2)  Category 2:  3 < a,  a < 1.0,  3 < 0.25/a  3)  Category  a l l the other sub-pictures.  3:  0.25/a  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-  t i o n allowed the a l l o c a t i o n of a higher number of b.p.p.e. f o r other areas. For the picture FACE, the d i s t r i b u t i o n of sub-pictures categories were as follows (Table 7.4);  105.  F i g . 7.8  Respective plots of the c o r r e l a t i o n 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 22 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 121 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  D i s t r i b u t i o n of the categories of sub-pictures i n the picture FACE.  There are 99 sub-pictures i n category 1, 56 i n category 2 and 101 i n category 3.  The c o r r e l a t i o n parameters averaged i n each category  are l i s t e d i n Table 7.5.  CATEGORY NUMBER 1  Table 7.5  2  3  a  0.118  0.561  2.54  3  0.565  0.155  3.47  Y  0.151  0.133  2.74  Average c o r r e l a t i o n parameters f o r each category of sub-picture, f o r the picture FACE.  3.25 b.p.p.e. were allocated to each sub-picture i n categories 1 and 2.  2.00 b.p.p.e. were allocated to each sub-picture i n category 3.  This gave an average of 2.75 b.p.p.e., plus a very small number of b i t s to transmit the category of the sub-picture to the receiver. The picture FACE, processed this way i s shown on F i g . 7.9(b) and i s to be compared with the same picture processed normally as i n  107.a  F i g . 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 S/N  ( a ) ) w i t h the same number of b.p.p.e.  r a t i o i s s l i g h t l y lower, 12.27  dB,  compared to 12.37  c a s e , but the s u b j e c t i v e q u a l i t y i s improved i n the .around the c o l l a r o f the s h i r t , and -on  some s u b - p i c t u r e s s u p p r e s s e d The  derable.  implementation  I f the non  The  measured  dB i n the  first  c o n t r a s t e d areas  t h e use of a h i g h number o f b.p.p.e.  the edge e f f e c t  [32]-  c o m p l e x i t y o f s u c h a system would be  consi-  a d a p t i v e system can be r e l a t i v e l y e a s i l y s e t up  p r o c e s s a c e r t a i n k i n d o f p i c t u r e , the a d a p t i v e system has  to  to e s t i m a t e  the c o r r e l a t i o n parameters o f each s u b - p i c t u r e b e f o r e p r o c e s s i n g . Methods are p u b l i s h e d i n [33].  An output b u f f e r i s a l s o r e q u i r e d to  give uniform transmission rate. 7.5  E f f e c t of D i g i t a l Channel E r r o r s on Performance: I t can be shown t h a t a d d i t i v e w h i t e n o i s e i n the  frequency  domain i s e q u i v a l e n t t o a d d i t i v e w h i t e n o i s e i n the time domain of the same power, i n terms o f image d e g r a d a t i o n [ 3 4 ] . A l s o , i t can be  argued  that frequency-domain q u a n t i z a t i o n i s l e s s damaging on a s u b j e c t i v e b a s i s t h a n time-domain q u a n t i z a t i o n [ 3 4 ] . I t has been thought by some [24,35] t h a t , p o s s i b l y , c h a n n e l e r r o r s o f any type a r e l e s s to s u b j e c t i v e q u a l i t y  when o c c u r i n g i n t h e f r e q u e n c y domain than i n  the time domain. W i t h t h i s i s s u e i n mind and  i n o r d e r to a s c e r t a i n  v u l n e r a b i l i t y t o n o i s e o f t h e s o u r c e c o d i n g system we the experiments The  d e s c r i b e d below were  studied here,  has been s i m u l a t e d .  .The p i c t u r e s were 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 encoded. An  e  average  u s e d , w h i c h p r o v i d e s r e c o n s t r u c t e d 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 h i g h v a l u e of the e r r o r . „p =0..01,. was  the  conducted.  system r e p r e s e n t e d i n F i g . 7.10  of 3 b.p.p.e. was  disruptive  probability,  chosen i n o r d e r t o emphasize the e f f e c t o f c h a n n e l n o i s e .  109.  Fourier Transform Filtering  p  P  Quant  NOISY CHANNEL Fig.  7.10  T r a n s m i s s i o n o f t r a n s f o r m encoded p i c t u r e s over a n o i s y c h a n n e l .  The p i c t u r e s p r o c e s s e d w i t h the above system a r e shown i n F i g . 7.11. The S/N r a t i o s o f t h e 3 b.p.p.e. t r a n s f o r m encoded p i c t u r e s , w i t h and w i t h o u t  digital  channel e r r o r s , a r e l i s t e d  i n Table  7.6.  T r a n s f o r m encoded p i c t u r e s 3 b.p.p.e. S/N dB Errorless Channel Gl G3 F H TP B  T a b l e 7.6  8.92 9.46 12.38 13.45 17.85 11.10  6.28 5.62 10.22 7.27 10.38 7.44  S/N r a t i o s o b t a i n e d by t r a n s m i t t i n g 3 b.p.p.e. t r a n s f o r m encoded p i c t u r e s over a n o i s y BSC c h a n n e l .  F o r t h i s experiment,  t h e average  d i g i t a l c h a n n e l e r r o r s was a p p r o x i m a t e l y relative  S/N dB Channel Errors  l o s s i n S/N r a t i o due t o  4 dB. I n o r d e r t o a s s e s s t h e  i n f l u e n c e o f each t r a n s f o r m sample, i t w i l l be assumed  the effect  that  o f c h a n n e l e r r o r s on each F o u r i e r samples can be e v a l u a t e d  110.a  F i g . 7.11  E f f e c t of d i g i t a l channel three-dimensional Fourier pictures; p e r - d i g i t error Sub-picture s i z e : 16 x 16  errors on 3 b.p.p.e. transform encoded p r o b a b i l i t y p =0.01. x 6. e  110.b  1 1 1 .  s e p a r a t e l y . The  l o s s i n S/N  o f the sample and  S/N  ratio  ratio  to depend on the v a r i a n c e  the number of q u a n t i z a t i o n used to t r a n s m i t t h a t sample.  A few experiments were performed on the p i c t u r e GARDEN1.  The  (4.18) of a 3 b.p.p.e. t r a n s f o r m encoded p i c t u r e was  dB.  I t became 6.28 the n o i s e was  dB w i t h the d i g i t a l channel suppressed S/N  dB due  component.  to the D.C.  r a t i o was  samples e x c e p t the f i r s t j ZI(2,1,1) the S/N  e r r o r s where p  g  on a l l the F o u r i e r samples except  component, the new  0.17  i s expected  7.30  8.92  = 0.01. the  If  D.C.  dB which r e p r e s e n t s a l o s s of  I f the n o i s e was  suppressed  1.62  on a l l F o u r i e r  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) +  r a t i o became 8.75  dB w h i c h r e p r e s e n t s a l o s s o f  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 e r r o r s 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 t r a n s m i s s i o n . In any  s i t u a t i o n , whatever the average number o f b.p.p.e., the most  important  samples are to be  t r a n s m i t t e d u s i n g a l a r g e number o f b i t s  they are r e s p o n s i b l e f o r most o f the e r r o r .  A few e x p e r i m e n t s on some  p i c t u r e s showed t h a t f o r 1, 2 o r 3 b.p.p.e. the l o s s i n S/N channel e r r o r s can be  considered  very n o t i c e a b l e . nents  The  effect  i s l e s s damaging.  depends on the frequency viewing distance.  The  r a t i o due  t r a n s m i s s i o n of the D.C.  component  Very b r i g h t o r v e r y dark s u b - p i c t u r e s of channel  e r r o r s on h i g h f r e q u e n c y  s u b j e c t i v e e f f e c t of such p e r i o d i c  noise  o f the n o i s e , t h e s i z e o f the s u b - p i c t u r e s , the  I t must be  remembered t h a t p  &  = 0.01  i s a very high  use o f e r r o r d e t e c t i n g 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 o f t r a n s f o r m e n c o d i n g a p p l i e d on the few  are  compo-  v a l u e f o r an e r r o r p r o b a b i l i t y . The  to  constant.  S u b j e c t i v e l y , the erroneous i s undoubtedly v e r y damaging.  and  e s p e c i a l l y i f they  t r a n s f o r m samples w i t h h i g h v a r i a n c e s .  are  112.  For by  reference,  an example o f the s u b j e c t i v e  degradation  caused  d i g i t a l channel e r r o r s i n the time-domain i s shown i n F i g . 7.12.  o r i g i n a l p i c t u r e s were PCM t r a n s m i t t e d  over a noisy  The  BSC channel w i t h an  e r r o r p r o b a b i l i t y o f 0.01.  I n t h i s c a s e , i t must be n o t e d t h a t  i s very h i g h :  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 o f the b r i g h t -  48 b.p.p.e.  ness i s u n i f o r m o r s y m m e t r i c a l w i t h r e s p e c t error e  2  the b i t r a t e  t o the mean, the mean square  due t o c h a n n e l n o i s e i s [361:  (7.3) *where N i s the number o f b i t s i n each codeword and p For N = 8 and p  g  = 0.01, (7.3) g i v e s  d i s t r i b u t i o n s f o r the p i c t u r e s the  conditions  e  2  = 218.45.  2  H TP B  "Table 7.7  223.66 224.15 223.55 221.66 222.57 228.80  7.7,  (7.3) almost p e r f e c t l y .  p. = 0.01 e  dB  5.82 4.16 7.00 10.52 13.55 6.71  Mean square e r r o r and s i g n a l t o n o i s e r a t i o due t o d i g i t a l e r r o r s on t h e PCM t r a n s m i s s i o n o f the o r i g i n a l d a t a .  Some c o n s i d e r a t i o n s be  probability  However as shown i n T a b l e  (S/N)  G3 F  The b r i g h t n e s s  y i e l d e d r e s u l t s which f i t t e d  BSC  Gl  the e r r o r p r o b a b i l i t y .  used i n t h i s t h e s i s do n o t s a t i s f y e x a c t l y  f o r t h e v a l i d i t y o f (7.3).  a c t u a l measurements o f e  g  found elsewhere  [14,15].  on t h e s u b j e c t i v e  e f f e c t o f such n o i s e can  113.a  F i g . 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 =0.01. e  114.  7.6  D i s c u s s i o n of R e s u l t s : From a l l the p r e c e d i n g  can be  e x p e r i m e n t s , the f o l l o w i n g  conclusions  drawn:  1)  The  o f the D.C.  use o f the s p e c i a l q u a n t i z e r more adapted t o the s t a t i s t i c s component of the F o u r i e r t r a n s f o r m  s u b j e c t i v e q u a l i t y o f the p r o c e s s e d 2)  increased considerably  the  picture.  F o r some p i c t u r e s i t i s p o s s i b l e t o o b t a i n a more a c c u r a t e  pre-  d i c t i o n o f the mathematical performance by u s i n g a non-s-aparable model for  the c o r r e l a t i o n f u n c t i o n .  expensive.  One  a set of variances  t h a t the s i m p l e  exponen-  a l l o w i n g the c h o i c e o f the most  F o u r i e r samples as w e l l as the b i t a l l o c a t i o n w h i c h g i v e s  n e a r optimum S/N 3)  the s i m u l a t i o n i s v e r y  must remember, from Chapter 6,  t i a l model p r o v i d e s important  Unfortunately  Using  ratio  ( w i t h i n 10%  f o r 2.75  b.p.p.e).  the 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 f o r d e c i d i n g  on the q u a n t i z a t i o n of the F o u r i e r samples l e d to a s l i g h t l y l a r g e r ratio  ( g a i n o f 0.2  dB)  f o r h a l f o f the p i c t u r e s .  The  use  4)  An  the q u a l i t y o f the p r o c e s s e d  to the r e c e i v e r  on the p a r t i c u l a r a r e a o f the p i c t u r e w h i c h i s b e i n g p r o c e s s e d improve somewhat the s u b j e c t i v e q u a l i t y o f p r o c e s s e d The  o f the d a t a must be  before  seems t o  high-contrasted  system i s , however, much more complex. l o c a l l y estimated  increase  pictures.  a d a p t i v e system t r a n s m i t t i n g more i n f o r m a t i o n  sub-pictures.  S/N  o f a more  s o 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 f u n c t i o n would not significantly  a  processing.  The  statistics  115. 5)  D i g i t a l channel e r r o r s a r e v e r y damaging to the s u b j e c t i v e q u a l i t y  o f the t r a n s f o r m encoded p i c t u r e s .  The t h r e s h o l d p r o b a b i l i t y o f e r r o r  which the s u b j e c t i v e e f f e c t i s n o t damaging has t o be found. S/N r a t i o i s r e l a t i v e l y independent mit the p i c t u r e .  6)  of the number o f b.p.p.e. used  to t r a n s -  component,  erroneous  t h e r e i s no n o t i c e a b l e s h i f t i n the colour..  The r e s u l t s o b t a i n e d a f t e r the p r o c e s s i n g o f the same d a t a on  a two-dimensional [19].  The l o s s i n  S i n c e most o f the s u b j e c t i v e e f f e c t i s due to the  t r a n s m i s s i o n o f the D.C.  under  Y,I  p r o c e s s i n g system was  and Q p l a n e s were p r o c e s s e d  and Hadamard t r a n s f o r m e n c o d i n g  systems.  a v a i l a b l e from an e a r l i e r through  two-dimensional  Optimum Max  t o 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 b i t s were a l l o c a t e d t o the D.C.  study  Fourier  quantizers  adapted  (5.3) were used.  component o f the Y p l a n e .  Eight  Some r e s u l t s  are compared i n F i g . 7.13 w i t h the same p i c t u r e s FACE and HOUSE p r o c e s s e d by our 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 e n c o d i n g  system u s i n g t h e same number  o f b.p.p.e. (2.75 b.p.p.e., 2.0 b.p.p.e. f o r the Y p l a n e , 0.375 b.p.p.e. f o r the I and Q p l a n e s ) and the same s p a t i a l s u b - p i c t u r e s i z e .  The  three-dimensional F o u r i e r process y i e l d e d s i g n i f i c a n t l y higher p i c t u r e than t h e two-dimensional  Fourier transform process.  : d e t a i l s r e n d i t i o n i n the two-dimensional is  quality  The  Hadamard t r a n s f o r m e d  spatial  pictures  s i m i l a r t o t h a t of t h e t h r e e - d i m e n s i o n a l p r o c e s s e d p i c t u r e s .  I n some  - c o n d i t i o n s , the t h r e e - d i m e n s i o n a l Hadamard t r a n s f o r m i n g may y i e l d b e t t e r r e s u l t s than t h e t h r e e - d i n e n s i o n a l F o u r i e r t r a n s f o r m i n g . transform i s b e t t e r suited the  HOUSE.  to p r o c e s s t h e p i c t u r e s of the same type  A two-dimensional  than  system i s more complex than t h e t h r e e -  d i m e n s i o n a l system i n the sense adapted  The Hadamard  t h a t i t r e q u i r e s two p r o c e s s o r s : one  t o the Y component, and one adapted  t o 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>  117.  (which have, i n general, the same s t a t i s t i c s ) . 7)  I t i s l i k e l y that some pictures could be transmitted using fewer  than 2 b.p.p.e.  For instance for the p i c t u r e FACE, the 2 b.p.p.e. p i c -  ture y i e l d s reasonably  good subjective q u a l i t y .  ( F i g . 7.14-c).  I t must  be r e c a l l e d that those pictures are to be viewed at a distance of about 25 inches.  In the same Figure, the pictures FACE transmitted with  and 1.5 b.p.p.e. are 8)  1.0  presented.  The "bad q u a l i t y " of the processed pictures i s mainly inherent  to s p a t i a l dimensions.  Besides a hardly noticeable loss i n saturation,  the colour of processed pictures i s not modified so as to be s u b j e c t i v e l y damaging (for 2.75  b.p.p.e).  In order to improve the transmission of the  information pertaining to the s p a t i a l 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 r e l a t i v e l y more b i t s to the Fourier samples pertaining to the s p a t i a l dimensions. was  created i n the following  A new  set c: variances a (u,v,w) l2  way:  o (u,v,w) = a (u,v,w)/k ,2  where:  (7.1)  2  a (u,v,w) i s the o r i g i n a l set of variances. 2  k k k k  = l = kj = k = k 2  3  for for for for  This operation decreased values of w.  w w w w  = 1 = 2,6 = 3,5 = 4  and k.3 > k£ • > k j > 1  the values of the estimated variances f o r large  Various values of k}, k , k 2  3  were t r i e d .  The l o s s i n colour  saturation of pictures processed using the new b i t a l l o c a t i o n , was j u s t i f i e d by a non s i g n i f i c a n t gain i n s p a t i a l d e t a i l r e n d i t i o n .  not Simple  attempts to enhance the colour of such pictures did not lead to any s a t i s f y results.  118.a  Fig. 7.14  Three-dimensional Fourier transform processed picture FACE: 16 x 16 x 6. (a) (b) (c)  1.0 b.p.p.e. 1.5 b.p.p.e. 2.0 b.p.p.e.  119  VIII  THREE-DIMENSIONAL TRANSFORM ENCODING OF MONOCHROMATIC 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 encoding 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 dimension 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. arbitrary.  For time varying pictures the number of frames is  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.  following parameters were obtained: a = 0.056  3=0.045  y =0.189  The  120. a  F i g . 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. b  SCENE 1  SCENE 1 RLPHR= 0.056  BETR= 0.045  I  o o  F1 = • F2 = CD F 4 = 4 -  F5=X  fl> = <r>  o.o  7.0  4.0 X  Fig. 8.2  6.0  8.0  DISPLACEMENT  10.0  12.0  14.0  0.0  1—  -1— 2.0  4.0  /  -1  6.0  -1— 8.0  DISPLACEMENT  I  10.0  —T  12.0  Correlation c o e f f i c i e n t along the s p a t i a l dimensions for SCENE1 (Fig. 8.1) estimated on 6 frames (F1.F2,...,F6) and least-square f i t of the exponential model.  -1 14.0  SCENE1  GRMMR= 0.189  -5.0  F i g . 8.3  DISPLACEMENT  Correlation c o e f f i c i e n t 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 i n this case, the estimated c o r r e l a t i o n c o e f f i c i e n t s are much less dependent on time than were the c o r r e l a t i o n c o e f f i c i e n t s on A f o r colour pictures. 8.3  Experimental Results: F i g . 8.4  shows the S/N  transmitted transform samples.  r a t i o as a function of the number of  In theory, from the estimated variances,  the Fourier and the Hadamard transform should y i e l d the same S/N that s p e c i f i c set of frames.  ratio for  From the actual variances of the transform  samples, the Fourier transform should give better r e s u l t s . The eight frames were transformed and the transform samples quantized using the quantizers designed f o r the colour p i c t u r e s . appear i n F i g . 8.5 Hadamard transform.  for the Fourier transform and i n F i g . 8.6  Results  f o r the  For the e i g h t 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 q u a l i t y of the processed pictures.  One must remember that those pictures should be viewed  at a distance of approximately 25 frames per second.  inches at a rate of approximately  24  There seems to be no noticeable difference i n the qua-  l i t y of the pictures processed using e i t h e r transform. The S/N r a t i o actually measured at 1 b.p.p.e. per frame i s 10.99  dB for the Fourier transform and 10.91  dB f o r the Hadamard transform.  For 8 b.p.p.e. and for the Fourier transform, 539 transmitted with the following b i t a l l o c a t i o n : 33 43 70 134 191 68  samples samples samples samples samples samples  with with with with with with  7 6 5 4 3 2  bits bits bits bits bits bits  transform samples are  124.  S/N SCENE  RATIO 1  16X16X8  'ROM PROCESSED PICTURES 8BPPE ~4H\  • VFROM ACTUAL VARIANCES <JFJ WITH QUANTIZATION j  FROM A&WAL R1ANQES (.NO  QUANTIZATION)  204.8  Fig. 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 (Fig. 8.1) from the estimated variances and from the normalized actual variances. The actual S/N r a t i o f o r 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 i d e n t i c a l f o r the Hadamard transform.  For such a  high number of samples transmitted with a small number of b i t s , the e f f e c t of quantization i s more important.  Equation 5.4 predicts a S/N r a t i o of  15.6 dB f o r the Fourier transform and 13.9 dB f o r the Hadamard transform. However, the main reason why actual r e s u l t s are not closer to the maximum obtainable S/N r a t i o i s due to the fact that, f o r that set of frames and for such a high number uf transmitted transform samples, the simple expon e n t i a l 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 b i t s . To r e a l l y assess the q u a l i t y of the processed p i c t u r e s , a large number of frames would have to be processed, displayed and projected. I t seems that fewer than 1 b.p.p.e. per frame w i l l be s u f f i c i e n t to transmit highly correlated data such as a head and shoulder view of a person. D i g i t a l channel errors could be very damaging on transform processed time varying pictures.  In PCM transmitted p i c t u r e s , an error i s  v i s i b l e only during one frame, and the frequency of the projection should decrease the subjective e f f e c t of such errors.  In a transform encoding  system, an erroneous sub-picture would be apparent f o r a number of frames equal to the dimension of the blocks i n the time 8.4  dimension.  Conclusion: More experiments  are required to f u l l y assess the subjective  quality of transform encoded time varying monochromatic p i c t u r e s .  The  e a s i l y implemented Hadamard transformation could be used, since i t yielded s i m i l a r results to those of the Fourier transform f o r the p a r t i c u l a r set of frames used i n this thesis.  126. a  Fig. 8.5  Eight frames of SCENE 1 ( F i g . 8.1) threedimensional Fourier transformed using an average of 1 b.p.p.e. per frame.  126.b  127.a  F i g . 8.6  Eight frames of SCENE 1 ( F i g . 8.1) three-dimensional Hadamard transformed using an average of 1 b.r-P«e. per frame.  127. b  128  IX 9.1  CONCLUSION  Summary of Results A colour picture was considered  U(x,y,A); U the brightness and of the wavelength A. was d i g i t i z e d .  as a three-dimensional process  i s a function of the s p a t i a l dimensions x, y, A set of s i x "high q u a l i t y " colour pictures  256 x 256 points were sampled i n the s p a t i a l dimensions  and 6 points i n the wavelength dimension. The study of the s t 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 h o r i z o n t a l or v e r t i c a l Ax,Ay,AA  R  =  features.  ( P{"K a j A x ) ex  exp{-[(a Ax) 2  2)  2  2  + ( f^Ay) + (B Ay) 2  2  2  + (yAA) ]*} + 2  + (yAA) ]^})/2.0 2  (9.1)  I f the data i s highly correlated i n the s p a t i a l dimensions a  single parameter s u f f i c e s to define the model i n the s p a t i a l d i r e c t i o n . The  function, Ax,Ay,AA  R  provided  =  exp[-((aAx) + ($Ay) )^].exp(-y|AA| ) 2  2  (9.2)  a reasonable f i t to the t y p i c a l head and shoulder view of a  person. 3)  The following separable model  Ax,Ay,AA  R  =  ex  P(~ IAx|).exp(-£|Ay|).exp(-y|AA|) a  (9.3)  129.  provides  a reasonable f i t to strongly correlated data having v e r t i c a l  or h o r i z o n t a l features.  I f the data i s weakly correlated i n the s p a t i a l  dimensions with v e r t i c a l or horizontal features, then the following model provides R  Ax  Ay AA  a closer f i t : =  [exp  (-04  | Ax| ) + exp (-ct | Ax| ) ] [exp (-gj1 Ay [ ) + 2  e x p ( - 0 I Ay[)].exp(-YIAAI)/4.0  (9.4)  2  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 b i t s and to adapt the to each of the Fourier samples.  quantization  The following conclusions  can be  drawn: 1)  In block quantization the incorrect transmission of very  bright areas i s subjectively very damaging. properly adapt the quantizer of the D.C. 2)  I t i s very important to  Fourier component.  For colour pictures which use fewer than 3 b.p.p.e. the single  exponential separable model (9.3) orders the Fourier samples i n terms of variances, but does not accurately predict the 3)  S/N.  A more complex model (9.1) providing a better f i t to the  autocorrelation function gives a better p r e d i c t i o n of the S/N not to s i g n i f i c a n t l y im_rove e i t h e r the S/N  but seems  or the subjective q u a l i t y  of the reconstructed p i c t u r e . 4)  An average number of 2.75 b.p.p.e. y i e l d s a reasonably good  reconstructed p i c t u r e .  Colour rendition i s good.  c h a r a c t e r i s t i c s came from highly contrasted  areas.  The only unpleasant  130. 5)  The subjective q u a l i t y of highly contrasted areas was  improved by adapting the process to the area.  somewhat  The sub-pictures were  c l a s s i f i e d i n categories representing the d i r e c t i o n of strong c o r r e l a tion. 6)  The e f f e c t of d i g i t a l channel errors on transform encoding i s  very damaging, and v i r t u a l l y independent on the average number of b.p.p.e. used to transmit the p i c t u r e .  There i s no noticeable s h i f t  i n the colour of the noisy p i c t u r e . 7)  In the experiments performed by us on time-varying monochroma-  t i c p i c t u r e s , the Fourier transformation should t h e o r e t i c a l l y y i e l d s i g n i f i c a n t l y better results than the Hadamard transformation for our set of p i c t u r e s .  However, experiments and subjective viewing i n d i c a t e d  that the two transforms  give very s i m i l a r r e s u l t s .  I t was  found that  for a large number of transmitted samples the transform samples are not always properly ordered by the s i n g l e exponential model ( 9 . 3 ) . 9.2 1)  Suggestions for Future Research A one-to-one relationship between S/N  r a t i o and subjective  q u a l i t y remains to be found for three-dimensional  pictures (colour or  monochromatic time-varying). 2)  For the Fourier transformation, instead of transmitting the  r e a l and imaginary part of a Fourier component i t i s possible to transmit i t s phase and amplitude.  In t h i s case, i t may net be necessary  code the amplitude with as many b i t s as the phase.  to  However, the e f f e c t  of d i g i t a l channel errors might be more damaging. 3)  The same process as the one used i n this thesis can be applied  to the RGB tristimulus components.  131. 4)  The subjective e f f e c t of d i g i t a l channel errors on the three-  dimensional transform encoded p i c t u r e , as a function of the p e r - d i g i t e r r o r p r o b a b i l i t y , needs further study.  The subjective e f f e c t o f  channel errors w i l l be transform dependent. 5)  I t seems that f o r 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  better results than the two-dimensional pictures.  Hadamard transformation y i e l d e d Fourier transformation on colour  Using a three-dimensional Hadamard transformation may y i e l d  better results than the three-dimensional Fourier transformation f o r some types of pictures.  APPENDIX  A  Some s t a t i s t i c s o f s o u r c e d a t a and h i s t o g r a m s o f intensity  levels  TEST PATTERN,  f o r the p i c t u r e s GARDEN3, FACE, HOUSE,  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  T a b l e A . l Mean and Standard d e v i a t i o n o f the b r i g h t n e s s o f the s o u r c e p i c t u r e s .  133.  n  A Afi Al X A X^ A Afi Al X A  42.34  36.50  54.44  28.24  3  26.25 32.02  30.59  23.86  33.94  26.30  34.04  27.19  49.92  20.84  45.35  26.37  46.47  36.11  36.11  36.33  Xif  31.50  32.36  A Afi Al X A  37.1-  34.63  57.59  26.41  3  3  2  77.96  42.06  98.49  55.67  83.26  57.04  AH  68.10  53.39  A  60.05  45.96  3  5  AR  65.49  30.76  Al X A A A  73.05  56.54  99.53  73.91  102.77  78.12  100.16  77.37  108.53  72.65  *G  105.84  58.61  Al X A  60.47  29.90  77.41  40.75  52.21  30.64  AH  36.08  24.36  A Afi  36.28  24.89  49.91  18.31  2  3  4  5  2  3  5  Table A.2  37.01 41.96  18.01  5  B  21.47  22.74  2  TP  17.28  35.66  39.01  5  H  30.80  38.02  2  V r  X-  AH 5  G3  a  Ai X A 2  Gl  Ai  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 c o l o u r p l a n e 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.  INTENSITY LEVEL  INTENSITY LEVEL  255.0  255.0  F i g . A2  Histograms o f I n t e n s i t y l e v e l s f o r each c o l o u r p l a n e and f o r t h e e n t i r e p i c t u r e f o r t h e p i c t u r e FACE.  136.  Fig. A3  Histograms of i n t e n s i t y l e v e l s f o r each c o l o u r p l a n e and f o r t h e 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  F i g . A4  INTENSITY LEVEL  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 entire picture f o r the picture T E S T P A T T E R N .  138.  BUILDING  BUILDING VIOLET BLUE  ?ELL0V 11 i  D  z U J  CC  ZD  (_) Ooi O o  o 0.0  64.0  128.0  192.0  INTENSITY LEVEL  1 256.0  0.0  64.0  ' 128.0  INTENSITY LEVEL  -|  192.0  256.0  192.0  256.0  BUILDING ORANGE RED  r 0.0  64.0  128.0  INTENSITY LEVEL  192.0  255.0  1 64.0  : — r 128.0  INTENSITY LEVEL  F i g . A5 Histograms of i n t e n s i t y l e v e l s f o r each colour plane a n d f o r the entire picture f o r the picture BUILDING.  139. APPENDIX  B  1.  Estimated 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 the pictures FACE, HOUSE, TEST PATTERN and BUILDING (3.7) and l e a s t square f i t of the exponential model. Figs. B l , B2, B3, B4.  2.  Estimated c o r r e l a t i o n c o e f f i c i e n t along the wavelength dimension f o r 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 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 pictures TEST PATTERN and BUILDING. F i g . B7.  4.  Correlation c o e f f i c i e n t i n the wavelength dimension, assuming s t a t i o n a r i t y , f o r the pictures HOUSE, TEST PATTERN and BUILDING.  144.  145.  F i g . B6  Correlation c o e f f i c i e n t i n the A d i r e c t i o n f o r the pictures TEST PATTERN and BUILDING.  Fig.  B7  Comparative f i t o f s e p a r a b l e and non-separable model t o estimated d i a g o n a l s p a t i a l c o e f f i c i e n t f o r t h e p i c t u r e s TEST PATTERN and BUILDING.  correlation  ON  F i g . B8  Correlation c o e f f i c i e n t i n the wavelength direction, assuming s t a t i o n a r i t y , f o r the pictures HOUSE, TEST PATTERN and BUILDING.  i—  1  148.  APPENDIX  C  Some E x a m p l e s o f t h e B i t A l l o c a t i o n  The bit  purpose o f this  allocation  schemes computed i n c h a p t e r  First,  a^j  are  l l  x-= i and  16  complex numbers:  21  Z R  Z  R 3  The  y •= j .  J  +  n  i  format  Z I  J  +  J  21  31  Z I  I  Z  above m a t r i x  12  a  13  a  21  a  22  a  23  a  a  31  a  32  a  33  a  a  4l  a  42  4  i  Z R Z R  Z R  1  +  2  2  3  Z R ^  2  2  2  J Il2 Z  + j ^ I +  J Z I  16  numbers are  ZR i + j Z I ZR  HH  2  1  2  Z R  Z  thesis,  ZR  the  2  R 3  Z  3  R  3  H 3  +  J Il3  +  J Z I  z  I  2  1  Z R  J  +  3 IH3  Z  Z R  3  2  3  +  3  2  3  z  Taking  12  + jZI  1  2  ZR  2 2  + jZI  2  2  ZR  + jZI  3  2  ZR  31  3  2  13  Z R  Z R ^  2  into  element  picture  "  J  -  3 I 2  "  J  -  J Z I  Z I  yields  12  Z  2  Z  I  3  4  2  2  account  t h a t some real,the  as f o l l o w s :  32  2  A similar  3k  a  ZRi» + j Z I this  l4  symmetric o f o t h e r numbers, o r are  ZR  2  results.  4 x 4 picture:  32 n u m b e r s .  conjugate  ZRn  2  + j Z I ^  complex numbers a r e  In  o f the  first, to  o f the b r i g h t n e s s f o r the p i c t u r e  has i n fact  u s e f u l remaining  i+3  I t i s useful,  2k  a  a  examples o f the  The -Fas?: - F o u r i e r t r a n s f o r m o f t h i s  11  + jzi +  a  the v a l u e s  at  ZR  5.  consider a two-dimensional a  F o u r i e r Samples.  a p p e n d i x i s t o g i v e a few  become f a m i l i a r w i t h t h e n o t a t i o n a n d  where the  o f the  1 3  2 3  ZR  +  jZI  2  3  3 3  1 + 2  results w i l l  be presented  r e p r e s e n t a t i o n w i l l be used i n the  a s shown  three-dimensional  above.  case. F o r  149, a 4 x 4 x 4 picture the results would be presented as follows  ZR  ZR  i n  (ZR + JZD121  + jZI) n  ZR  2  ZR + j Z I ) 2 1 2  ZR  ZR131  + jZI) i 2 3  ZR +  jZI)  (  3  Z R  1  Number of samples  1  + 3  Z I  )321  2 1 t l  (ZR + j Z I ) i i 2  ZR + J Z I ) 1 2  (ZR + J Z D 3 1 2  (ZR + JZD122  ZR + j Z I ) 2 2  (ZR +  (ZR + JZD132  ZR + j Z I ) 3 2  (ZR + j Z I ) 3 2  (ZR  +  jZI)142  ZRll3 (ZR  2  2  2  ZR + j Z I ) i 2  f 2  ZR133  (ZR+jZI) i 3  ZR313  ZR  + jZI)  2  2  3  (ZR +  ZR + j Z I )  2  3  3  ZR  ZR +  jZI)  2 t t 3  ZR +  jZI)  2 1 t t  ZR +  jZI) 24  ZR +  JZD234  JZD322  24  3  ZR + j Z I ) i 3 2  + j Z I ) 123  16  ZR331  jZI)  3  t 2  2  3  16  3 3 3  2  ZR + j Z I ) ^  Total:  64  The bit allocation for the various picture formats used in chapter 5 for a = 1)  3 = y = 0.06 and for 3 b.p.p.e. are as follows:  Single 8 x 8  frame:  150.  V \^ 1 2 3 4 5 6 7 8  1 7 44 03 00 3  2  3  4  5  44 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  3 00 00 00 0  The above represents 32 b i t s per frame, 192 b i t s per 6 frames and 3 b.p.p.e., since there are 8 x 8 = 64 p i c t u r e elements. 2)  The following table represents the b i t a l l o c a t i o n i n the case  of the three-dimensional processing of an 8 x 8 x 6 picture.  151.  w  1  X  o  Z  o J  A  C  J  u  \ u v \  1  2  3  4  5  1  7  77  66  65  6  2  77  44  03  00  00  3  66  03  00  00  00  4  65  00  00  00  00  5  6  00  00  00  0  6  00  00  00  7  30  00  00  8  54  30  00  1  77  44  00  00  00  2  44  00  00  00  00 00  3  00  00  00  00  4  00  00  00  00  00  5  00  00  00  00  00  6  00  00  00  00  00  7  00  00  00  00  00  8  44  00  00  00  00  1  66  00  00  00  00  2  03  00  00  00  00  3  00  00  00  00  00  4  00  00  00  00  00  5  00  00  00  00  00  6  00  00  00  00  00  7  00  00  00  00  00  8  00  00  00  00  00 0  1  6  00  00  00  2  00  00  00  00  00  3  00  00  00  00  00  4  00  00  00  00  00  5  0  00  00  00  0  6  00  00  00  7  00  00  00  8  00  00  00 00  1  00  00  2  00  00  00  3  00  00  00  4  00  00  00  5  00  00  00  6  00  00  00  7  00  00  00  8  00  00  00 00  1  44  00  2  00  00  00  3  00  00  00  4  00  00  00  5  00  00  00  6  00  00  00  7  00  00  00  8  00  00  00  Numbe r of b i t s  TOO  IzZ  J O  ^ H  Xo  0  n u  o  o  Total:  192  152. 3)  B i t a l l o c a t i o n f o r a single 16 x 16 frame. There are 192  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16  b i t s per frame, 0.75  1  2  3  4  5  6  7  8  9  7 66 55 44 44 43 43 43 4  66 44 33 22 02 00 00 00 00 00 00 00 00 22 33 44  55 33 00 00 00 00 00 00 00 00 00 00 00 00 00 33  44 22 00 00 00 00 00 00 00 00 00 00 00 00 00 22  44 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00  43 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  43 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  43 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  4 00 00 00 00 00 00 00 0  In chapters 4 and 5,  4 consecutive frames were to be processed  (comparison of 16 x 16 with 8 x 8 x 4 ) 4 x 0.75  b.p.p.e. per frame.  = 3 b.p.p.e.  which represents an average of  153. 4)  P r o c e s s i n g o f an 8 x 8 x 4 192 b i t s  picture:  a r e to be t r a n s m i t t e d f o r 64 p i c t u r e elements f o r an  average number o f 3  b.p.p.e.  Number of b i t s  W 1 2 3 4 5 6 7 8  7 67 55 54 5  67 44 03 00 00 00 30 44  55 03 00 00 00 00 00 30  54 00 00 00 00 00 00 00  5  1 2 3 4 5 6 7 _8_  66 44 13 00 00 00 33 44  44 00 00 00 00 00 00 00  33 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  1 2 3 4 5 6 7 _8_  6 34 00 00 0  34 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  0 00 00 00 00  44 00 00 00 00 00 00 00  30 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  1 2 3 4 5 6 7 8  00 00 00 0  Total:  109  38  34  11  192  APPENDIX  D  Histograms o f F o u r i e r samples f o r the p i c t u r e FACE  155.  Fig.  D.l  Histograms of  F o u r i e r samples f o r the  picture  FACE.  156.  ZRU  Z I U .2.1)  (b)  fa)  -f -«.D  " i—•——sn  -30.0  1  0.0 ,2  -15.0  (XIO J  t  15.0  30.0  r 45.0  -45.0  p-  -30.0  30.0  fd)  (c)  i  -e.j  >v— -m.o-  n  r^  rJU  -is.o  ill  1  s  o.o, 1X10' )  is.o  ZKl  30.0  <5.0  i -45.0  1 -30.0  -30.0  -15.0  F i g . D.2  0.0 J„  (X10  1  15.0  r-  ZRCl.1.3)  .1.2)  fe)  -«S.O  <S.O  ZR(1.1.2)  21(1.3.1)  7  .3.1)  ff)  30.0  -e.o  -30.0  30.0  43.0.  Histograms of Fourier samples f o r the p i c t u r e FACE.  157.  o" 21(1.1.3) £  «M  GARDEN1 8 o"  1  1  1 -1S.0  J r  a  0.0,  (X10  ^ — "  J  )  . 15.0  1  r  Z K l . l .3)  FACE  -15.0  0.0,  1  15.0  IX10 ) 2  F i g . D.3  Histograms of Fourier samples.  158.  REFERENCES 1.  T.S. Huang, O.J. Tretiak, B. Prasada and Y. Yamaguchi, "Design Considerations i n PCM Transmission of Low-Resolution Monochrome S t i l l P i c t u r e s " , Proc. IEEE, V o l . 55, No. 3, pp. 331-335, March 1967.  2.  U.F. Gronneman, June 1964.  3.  A. Habibi, "Comparison of nth-Order DPCM Encoder With Linear Transformations and Block Quantization Techniques", IEEE Trans. Comm. Tech., V o l . COM-19, No. 6, pp. 948-956, Dec. 1971.  4.  J.O. Limb, C.B. Rubinstein and K.A. Walsh, " D i g i t a l Coding of Color Picturephone Signals by Element-Differential Quantization", IEEE Trans. Comm. Tech., V o l . 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., V o l . 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., V o l . COM-19, No. 1, pp. 50-62, Feb. 1971.  7.  P.A. Wintz, "Transform Picture Coding", Proc. IEEE, V o l . 60, No. 7, pp. 809-819, July 1972.  8.  W.K. P r a t t , " S p a t i a l Transform Coding of Color Images", IEEE Trans. Comm. Tech., V o l . COM-19, No. 6, pp. 980-992, Dec. 1971.  "Coding Color P i c t u r e s " , Tech. Report 422, M.I.T.,  9. W.K. P r a t t , " D i g i t a l Color Image Coding and Transmission", USCEE Report 403, Univ. of Southern C a l i f o r n i a , June 1971. 10.  W.K. Pratt, W.H. Chen and L.R. Welch, "Slant Transform Image Coding", IEEE Trans. Comm., V o l . COM-22, No. 8, pp. 1075-1093, Aug. 1974.  11.  C.B. Rubinstein and J.O. Limb, " S t a t i s t i c a l Dependence Between Components of a D i f f e r e n t i a l l y Quantized Color Signal", IEEE Trans. Comm., V o l . COM-20, No. 5, pp. 890-899, Oct. 1972.  12.  J.O. Limb and C.B. Rubinstein, "Plateau Coding of the Chrominance Component of Color Picture Signals", IEEE Trans. Comm, V o l . COM-22, No. 6 , pp. 812-820, June 1974.  13.  P.J. Ready and P.A. Wintz, "Information Extraction, SNR Improvement and Data Compression i n M u l t i s p e c t r a l Imagery", IEEE Trans. Comm, Vol. COM-21, No. 10, pp. 1123-1130, Oct. 1973.  159. 14.  T.S. Huang and M.T. C h i k h a o u i , "The E f f e c t o f BSC on PCM P i c t u r e Q u a l i t y " , IEEE Trans. I n f o . 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 , " B i n a r y Symmetric Channel E r r o r E f f e c t s on PCM C o l o r Image T r a n s m i s s i o n " , IEEE T r a n s . I n f o . 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 o f T e l e v i s i o n S i g n a l s " , B e l l S y s t . Tech. J o u r n a l , V o l . 31, p. 763, J u l y 1952.  17.  W.F. S c h r e i b e r , "The Measurement o f T h i r d Order P r o b a b i l i t y D i s t r i b u t i o n o f T e l e v i s i o n S i g n a l s " , IRE T r a n s . I n f o . Theory, V o l . I T - 2 , pp. 94-105, Sept. 1956.  18.  L.E. F r a n k s , "A Model f o r the Random V i d e o P r o c e s s " , B e l l S y s t . Tech. J o u r n a l , pp. 609-630, A p r i l 1966.  19.  C A . Seecheran, " C o l o u r Image Coding U s i n g L i n e a r T r a n s f o r m a t i o n and B l o c k Q u a n t i z a t i o n " , M.A.Sc. T h e s i s , E.E. , U.B.C., June 1974.  20.  G.B. Anderson and T. Huang, " P i e c e w i s e F o u r i e r T r a n s f o r m a t i o n f o r P i c t u r e Bandwidth Compression", IEEE T r a n s . 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 F a s t F o u r i e r T r a n s f o r m " , Spectrum, V o l . 4, pp. 63-70, Dec. 1967.  22.  W.T. Cochran and J.W. C o o l e y , "What i s t h e F a s t F o u r i e r P r o c . IEEE, V o l . 55, No. 10, pp. 1664-1674, O c t . 1967.  23.  J . Pearl-, "On Coding and F i l t e r i n g S t a t i o n a r y S i g n a l s by D i s c r e t e F o u r i e r Transforms", IEEE T r a n s . I n f o . Theory, C o r r e s p . , 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 T r a n s f o r m Image Coding", P r o c . IEEE, V o l . 57, No. 1, pp. 58-68, J a n . 1969.  25.  H.F. Harmuth, "A G e n e r a l i z e d Concept o f Frequency and Some A p p l i c a t i o n s " , IEEE T r a n s . I n f o . Theory, V o l . 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 o f T r a n s f o r m P i c t u r e Coding Systems and an I n v e s t i g a t i o n o f a New Measure o f D i s t o r t i o n i n P r o c e s s e d Images", M.A.Sc. T h e s i s , U.B.C., 1973.  27.  J . Max, " Q u a n t i z i n g f o r Minimum D i s t o r t i o n " , IRE T r a n s . I n f o . Theory, V o l . I T - 6 , pp. 7-12, March 1960.  IEEE  Transform?"  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 T e l e m e t r y " , IEEE T r a n s . I n f o . Theory, V o l . IT-14, pp. 650-661, Sept.  1968. 29.  R.E. T o t t y and G.C. C l a r k , " R e c o n s t r u c t i o n E r r o r i n Waveform T r a n s m i s s i o n " , IEEE T r a n s . I n f o . Theory, C o r r e s p . , V o l . IT-13, pp. 336338, A p r i l 1967.  30.  E . F r o e s e , " D i s c r e t e F o u r i e r T r a n s f o r m a t i o n s " , UBC F o u r t , Computing C e n t r e , UBC, Jan". 1970.  31.  M. T a s t o and P.A. Wintz, "Image Coding by A d a p t i v e B l o c k Q u a n t i z a t i o n " , IEEE T r a n s . Comm. Tech., V o l . COM-19, No. 6, pp. 957-971, Dec. 1971.  32.  M. T a s t o and P.A. W i n t z , "Note on t h e E r r o r S i g n a l o f B l o c k Q u a n t i z e r s " , IEEE T r a n s . Comm. C o n c i s e Paper, pp. 216-219, March 1973. i  33.  • 34.  A. H a b i b i and P.A. Wintz, " E s t i m a t i o n o f C o r r e l a t i o n F u n c t i o n s by S t o c h a s t i c A p p r o x i m a t i o n " , IEEE T r a n s . Aerosp. E l e c t r . S y s t . , V o l . AES-8, No. 3, pp. 327-337, May 1972. G.B. Anderson and T.S. Huang, "Frequency-Domain Image E r r o r s " , P a t t e r n R e c o g n i t i o n , Pergamon P r e s s , V o l . 3, p p . 185-196, 1971.  35.  E . J . C l a i r e , "Bandwidth R e d u c t i o n i n Image T r a n s m i s s i o n " , 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 T r a n s . I n f o . Theory, C o r r e s p . , V o l . IT-11, pp. 596-597, O c t . 1965.  37.  B.G. ' H a s k e l l , F.W. Haunts and J.C. Candy, " I n t e r f r a m e Coding o f V i d e o t e l e p h o n e P i c t u r e s " , P r o c . IEEE, V o l . 60, No. 7, pp. 793-800, J u l y 1972.  38.  T. F u k i n u k i and M. M i y a t a , " I n t r a f r a m e Image Coding by Cascaded Hadamard Transforms", IEEE T r a n s . Comm., V o l . COM-21, No. 3 pp. 175180, March 1973.  39.  0. Jensen, "Implementation o f an E x p e r i m e n t a l F a c i l i t y and M o d e l l i n g Study f o r Time V a r y i n g Images", M.A.Sc. T h e s i s , E.E. , U . B . C , S e p t .  1973.  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0100060/manifest

Comment

Related Items