Google Inc.
`GOOG 1028
`IPR of US Pat. No. 7,974,339
`
` 1
`
`

`
`IMAGE and VIDEO
`
`COMPRESSION
`
`for MULTIMEDIA
`
`ENGINEERING
`
`T
`Fundamentals,
`Algorithms, and Standards
`
`2
`
`

`
`IMAGE PROCESSING SERIES
`Series Editor: Phillip A. Laplante
`
`Forthcoming Titles
`
`Adaptive Image Processing: A Computational Intelligence
`Perspective
`Ling Guan, Hau-San Wong, and Stuart William Perry
`Shape Analysis and Classification: Theory and firactice
`Luciano da Fontoura Costa and Roberto Marcondes Cesar, Ir.
`
`3
`
`

`
`IMAGE and VIDEO
`
`COMPRESSION
`
`for MULTIMEDIA
`
`ENGINEERING
`
`Fundarnentais,
`Algorithms, and Standards
`
`Yun Q. Shi
`New Iersey Institute of Technology
`Newark, N]
`
`Huifang Sun
`
`Mitsubishi Electric Information Technology Center
`America Advanced Television Laboratory
`New Providence, N]
`
`CEC Press
`
`Boca Raton London New York Washington, D.C.
`
`4
`
`

`
`Library of Congress Cataloging-in-Publication Data
`
`Shi, Yun Q.
`Image and video compression for multimedia engineering : fundamentals, algorithms, and
`standards /Yun Q. Shi, Huifang Sun.
`p.
`cm.
`Includes bibliographical references and index.
`ISBN 0-8493-3491-8 (allc. paper)
`1.Multimedia systems. 2. Image compressions. 3. Video compression.
`1. Sun, I-luifnag.
`II. Title.
`QA76.575.S555 1999
`006.7—dc21
`
`99-047137
`CIP
`
`This book contains information obtained from authentic and highly regarded sources. Reprinted material is
`quoted with permission, and sources are indicated. A wide variety of references are listed. Reasonable efforts
`have been made to publish reliable data and information, but the author and the publisher cannot assume
`responsibility for the validity of all mateéals or for the consequences of their use.
`
`Neither this book not any part may be reproduced or transmitted in any form or by any means, electronic or
`mechanical, including photocopying, microfilming, and recording, or by any information storage or retrieval
`system, without prior permission in writing from the publisher.
`
`The consent of CRC Press LLC does not extend to copying for general distribution, for promotion, for creating
`new works, or for resale. Specific permission must be obtained in writing from CRC Press LLC for such
`copying.
`
`Direct all inquiries to CRC Press LLC, 2000 N.W. Corporate Blvd., Boca Raton, Florida 33431.
`
`Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used
`only for identification and explanation, without intent to infringe.
`
`Figures and tables from ISO reproduced with the permission of the International Organization for Standard-
`ization. These standards can be obtainedfrom any member boa? or directly from the Central Secretariat, ISO,
`Case postale 56, 1211 Geneva 20, Switzerland.
`
`© 2000 by CRC Press LLC
`
`No claim to original U.S. Government works
`International Standard Book Number 0-8493-3491-8
`Library of Congress Card Number 99-047137
`Printed in the United States of America
`2 3 4 5 6 7 8 9 0
`Printed on acid-free paper
`
`5
`
`

`
`Preface
`
`It is well known that in the 19605 the advent of the semiconductor computer and the space program
`swiftly brought the field of digital image processing into public focus. Since then the field has
`experienced rapid growth and has entered into every aspect of modern technology. Since the early
`1980s, digital image sequence processing has been an attractive research area because an image
`sequence, as a collection of images, may provide more information than a single image frame. The
`increased computational complexity and memory space required for image sequence processing
`are becoming more attainable. This is due to more advanced, achievable computational capability
`resulting from the continuing progress made in technologies, especially those associated with the
`VLSI industry and information processing.
`In addition to image and image sequence processing in the digitized domain, facsimile trans-
`mission has switched from analog to digital since the 1970s. However, the concept of high definition
`television (HDTV) when proposed in the late 1970s and early 1980s continued to be analog. This
`has since changed. In the U.S., the first digital system proposal for HDTV appeared in 1990. The
`Advanced Television Standards Committee (ATSC), formed by the television industry, recom-
`mended the digital HDTV system developed jointly by the seven Grand Alliance members as the
`standard, which was approved by the Federal Communication Commission (FCC) in 1997. Today’s
`worldwide prevailing concept of HDTV is digital. Digital television (DTV) provides the signal that
`can be used in computers. Consequently, the marriage of TV and computers has begun. Direct
`broadcasting by satellite (DBS), digital video disks (DVD), video—on-demand (VOD), video games,
`and other digital video related media and services are available now, or soon will be.
`As in the case of image and video transmission and storage, audio transmission and storage
`through some media have changed from analog to digital. Examples include entertainment audio
`on compact disks (CD) and telephone transmission over long and medium distances. Digital TV
`signals, mentioned above, provide another example since they include audio signals. Transmission
`and storage of audio signals through some other media are about to change to digital. Examples
`of this include telephone transmission through local area and cable TV.
`Although most signals generated from various sensors are analog in nature, the switching from
`analog to digital is motivated by the superiority of digital signal processing and transmission over
`their analog counterparts. The principal advantage of the digital sigcal is its robustness against
`various noises. Clearly, this results from the fact that only binary digits exist in digital format and
`it is much easier to distinguish one state from the other than to handle analog signals.
`Another advantage of being digital is case of signal manipulation. Ic addition to the development
`of a variety of digital signal processing techniques (including image, video, and audio) and specially
`designed software and hardware that may be well known, the following development is an example
`of this advantage. The digitized irzformation format,
`i.e.,
`the bitstream, often in a compressed
`version, is a revolutionary change in the video industry that enables many manipulations which
`are either impossible or very complicated to execute in analog format. For instance, video, audio,
`and other data can be first compressed to separate bitstreams and then combined to form a signal
`bitstream, thus providing a multimedia solution for many practical applications. Information from
`different sources and to different devices can be multiplexed and demultiplexed in terms of the
`bitstreara. Bitstream conversion in terms of bit rate conversion, resolution conversion, and syntax
`
`conversion becomes feasible. In digital video, content-based coding, retrieval, and manipulation
`and the ability to edit video in the compressed domain become feasible. All system—timing signals
`
`6
`
`

`
`in the digital systems can be included in the bitstream instead of being transmitted separately as
`in traditional analog systems.
`The digital format is well suited to the recent development of modern telecommunication
`structures as exemplified by the Internet and World Wide Web (WWW). Therefore, we can see that
`digital computers. consumer electronics (including television and video games), and telecommu-
`nications networks are combined to produce an information revolution. By combining audio, video,
`and other data, multimedia becomes an indispensable element of modern life. While the pace and
`the future of this revolution cannot be predicted, one thing is certain:
`this process is going to
`drastically change many aspects of our world in the next several decades.
`One of the enabling technologies in the information revolution is digital data compression,
`since the digitization of analog signals causes data expansion. In other words, storage and/or
`transmission of digitized signals require more storage space and/or bandwidth than the original
`analog signals.
`The focus of this book is on image and video compression encountered in multimedia engi-
`neering. Fundamentals, algorithms, and standards are the three emphases of the book. It is intended
`to serve as a senior/graduate—level text. Its material is sufficient for a one-semester or one-quarter
`graduate course on digital image and video coding. For this purpose, at the end of each chapter
`there is a section of exercises containing problems and projects for practice, and a section of
`references for further reading.
`Based on this book, a short course entitled “Image and Video Compression for Multimedia,”
`was conducted at Nanyang Technological University, Singapore in March and April, 1999. The
`response to the short course was overwhelmingly positive.
`
`7
`
`

`
`
`
`Contents
`
`Section I Fundamentais
`
`Introduction
`Chapter 11
`1.]
`Practical Needs for Image and Video Compression ............................................................... ..4
`
`1.2 Feasibility o1'1mage and Video Compression .................................................................. ..4
`Statistical Redundancy ............................................................................................. ..4
`1.2.1
`
`Psychovisual Redundancy ............................................................................... ..9
`1.2.2
`
`1.3 Visual Quality Measurement .......................................................................................... ..18
`1.3.1
`Subjective Quality Measurement .............................................................................. ..19
`1.3.2 Objective Quality Measurement ......................................................................... ..2O
`
`In1‘ormation Theory Results ......................................................................................... ..24
`
`Entropy ............................................................................................................. ..24
`1.4.1
`1.4.2 Shann0n’s Noiselcss Source Coding Theorem ......................................................... ..25
`1.4.3
`Shann0n’s Noisy Channel Coding Theorem ............................................................ ..26
`1.4.4
`Shannon’s Source Coding Theorem ......................................................................... ..27
`1.4.5
`Information Transmission Theorem .......................................................................... ..27
`Summary ............................................................................................................... ..27
`1.5
`1.6 Exercises ................................................................................................................ ..28
`References ...................................................................................................................................... ..28
`
`
`
`1.4
`
`
`
`111 ,
`
`Quantization
`Chapter 2
`2.1 Quantization and the Source Encoder .................................................................................. ..
`2.2 Uniform Quantization ....................................... ..
`2.2.1 Basics ...................................... ..
`
`
`
`2.2.2 Optimum Uniform Quantizer....
`2.3 Nonuniform Quantization ............................................................................................... ..40
`2.3.1 Optimum (Nonuniform) Quantization ................................................................ ..42
`2.3.2 Companding Quantization .................................................................................. ..43
`2.4 Adaptive Quantization .................................................................................................... ..45
`2.4.1
`‘Forward Adaptive Quantization .......................................................................... ..47
`2.4.2 Backward Adaptive Quantization ............................................................................. ..48
`2.4.3 Adaptive Quantization with a One-Word Memory .................................................. ..48
`2.4.4
`Switched Quantization .............................................................................................. ..48
`2.5
`PCM ...................................................................................................................................... ..49
`2.6
`Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..50
`
`2.7 Exercises ................................................................................................................ ..52
`
`References ...................................................................................................................................... ..52
`
`
`
`Differentiai Coding
`Chapter 3
`3.1
`Introduction to DPCM .......................................................................................................... ..55
`3.1.1
`Simple Pixel-to—Pixe1 DPCM...
`....................................................................... ..55
`3.1.2 General DPCM Systems ........................................................................................... ..58
`3.2 Optimum Linear Prediction .................................................................................................. ..6O
`
`
`
`8
`
`

`
`,
`
`I
`1
`
`5’1 _1
`5_1_2
`5_1_3
`5_1_4
`52 Huffnm
`J
`5.21
`522 ]
`5.3 Modifie
`5.11
`J
`532 I
`533 (
`534 1
`5_4 Amhme
`54.]
`I
`5_4_2
`I
`5.43
`I
`5.4_4
`1
`5_4_5
`I
`Summat
`
`5.5
`
`5.6 Exorcist
`R5l‘CT9“C95
`
`Chapter 6
`6.] Markov
`6.1.1
`1
`6.1.2
`I
`6.1.3
`I
`
`6.2 Run-Lei
`6.2.1
`1
`6.2.2
`2
`6.2.3
`I
`6.3 Digital 1
`6.4 Dictiona
`6.4.1
`I
`6.4.2
`C
`6.4.3
`P
`6.4.4
`5
`
`I
`6.4.5
`Internati
`6.5.1
`1.
`6.5.2
`I
`Summar
`
`6.5
`
`6.6
`
`6.7 Exercise
`References.....
`
`'
`Section I‘
`
`Chapter 7
`7 I
`Imroducl
`72 Scqucmi
`
`Formulation ............................................................................................................... ..60
`3.2.1
`3.2.2 Orthogonality Condition and Minimum Mean Square Error................................... ..6l
`3.2.3
`Solution to Yu1e—Walker Equations ........................................................................... ..62
`
`Some Issues in the Implementation of DPCM ............................................................... ..62
`3.3.1 Optimum DPCM System ....................................................................................... ..62
`3.3.2
`1-D, 2-D, and 3-D DPCM .................................................................................. ..63
`3.3.3 Order of Predictor ..................................................................................................... ..64
`3.3.4 Adaptive Prediction ................................................................................................... ..64
`3.3.5 Effect 01' Transmission Errors ....................................................................... ..65
`3.4 Delta Modulation ...................................................................................................... ..65
`3.5
`Interlrame Differential Coding ....................................................................................... ..68
`3.5.1 Conditional Replenishment ....................................................................................... ..68
`3.5.2
`3-D DPCM ................................................................................................................ ..69
`3.5.3 Motion-Compensated Predictive Coding .................................................................. ..7l
`Information-Preserving Differential Coding......................................................................... ..7l
`3.6
`Summary ................................................................................................................... ..72
`3.7
`3.8 Exercises . . . . . . . . . . . . . . . . . . . . . . .
`. . . . . . . . ..73
`References ...................................................................................................................................... ..73
`
`
`
`
`
`3.3
`
`
`
`Tiransfmrm Coding
`Chapter 4
`4.1
`Introduction ........................................................................................................................... ..75
`4.1.1 Hotelling Transform .................................................................................................. ..75
`4.1.2
`Statistical Interpretation ............................................................................................ ..77
`4.1.3 Geometrical Interpretation .................................................................................. ..78
`
`4.1.4 Basis Vector Interpretation ......................... ..
`
`4.1.5
`Procedures of Transform Coding ............... ..
`4.2 Linear Transforms ................................................................................................................. ..8O
`
`2-D Image Transformation Kernel ........................................................................... ..80
`4.2.1
`4.2.2 Basis [mage Interpretation ........................................................................................ ..83
`4.2.3
`Subimage Size Selection ........................................................................................... ..84
`4.3 Transforms of Particular Interest . . . . . . . .
`. . . . . . . . . . .
`. . .
`. . . . . . . . . . . . . . . . . .
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . ..84
`4.3.1 Discrete Fourier Transform (DPT)
`................................................. ..85
`4.3.2 Discrete Walsh Transform (DWT) ............................................................ ..86
`4.3.3 Discrete Hadamard Transform (DHT) ...................................................................... ..87
`4.3.4 Discrete Cosine Transforin (DCT) ........................................................................... ..88
`4.35
`Performance Comparison .......................................................................... ..92
`4.4 Bit Allocation ........
`.............................................................................................. ..95
`
`
`
`
`
`4.5
`
`. ..95
`. . . .
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`. .
`Zonal Coding . . . . . . . . .
`4.4.1
`4.4.2 Threshold Coding ...................................................................................................... ..96
`Some Issues ......................................................................................................................... ..l02
`4.5.1
`Effect of Transmission Errors ................................................................................. ..102
`4.5.2 Reconstruction Error Sources ................................................................................. ..102
`
`....l03
`4.5.3 Comparison Between DPCM and TC .............. ..
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..103
`4.5.4 Hybrid Coding . . . . . . .
`. .
`. . . . . . . . . . . . . . . . . . .
`. . . . . . . . . . . . . . . . . ..l03
`Summary . . . . . . . . . . . . . .
`. . . . . . . .
`. . . . .
`.
`.
`4.6
`4.7 Exercises .............................................................................................................................. ..l05
`References .................................................................................................................................... ..106
`
`
`
`Variable-Length Coding: Information Theory Results (II)
`Chapter 5
`5.1
`Some Fundamental Results ................................................................................................. ..107
`
`
`
`9
`
`

`
`5.1.1 Coding an Information Source ............................................................................... ..107
`5.1.2 Some Desired Characteristics............
`.................................... .108
`
`5.1.3 Discrete Memoryless Sources ........................................................................... ..1l1
`5.1.4 Extensions of :1 Discrete Memoryless Source ........................................................ ..l 12
`5.2 Huffman Codes ................................................................................................................... ..114
`
`5.2.1 Required Rules for Optimum Instantaneous Codes ............................................... .,1 14
`5.2.2 Huffman Coding Algorithm .................................................................................... ..1 15
`5.3 Modified Huffman Codes ....................................................................................... ..1 17
`
`. , . . . . . . . . . . . . . . . . . . .
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..117
`5.3.1 Motivation . . . . . . . . . . . . . . . . . .
`
`5.3.2 Algorithm .................................................................................................... ..118
`5.3.3 Codcbook Memory Requirement ........................................................................... ..1 18
`5.3.4 Bounds on Average Codeword Length ................................................................... ..11‘)
`5.4 Arithmetic Codes ................................................................................................................ ..119
`5.4.1
`Limitations of Huffman Coding ............................................................................. .. 120
`
`Principle of Arithmetic Coding ........................................................................ ..12()
`5.4.2
`Implementation Issues ............................................................................................. ..125
`5.4.3
`5.4.4 History ..................................................................................................................... .. 126
`5.4.5 Applications ............................................................................................................ .. 127
`5.5
`Summary ............................................................................................................................. .. 127
`
`5.6 Exercises ........................................................................................................................ .. 128
`References .................................................................................................................................... .. 129
`
`Run-Length and Dictionary Coding: Information Theory Results (III)
`Chapter 6
`6.1 Markov Source Model ........................................................................................................ .. 131
`6.1.1 Discrete Markov Source ......................................................................................... ..131
`6.1.2 Extensions of a Discrete Markov Source ............................................................... ..133
`
`6.1.3 Autoregressive (AR) Model .................................................................................... ..133
`6.2 Run—Length Coding (RLC) ................................................................................................. .. 134
`
`1-D Run-Length Coding ................................................................................... ..134
`6.2.1
`2-D Run-Length Coding ......................................................................................... .. 135
`6.2.2
`6.2.3 Effect of Transmission Error and Uncompressed Mode ........................................ .. 138
`1 6.3 Digital Facsimile Coding Standards ................................................................................... ..139
`6.4 Dictionary Coding ............................................................................................................... ..140
`6.4.1
`Formulation of Dictionary Coding ......................................................................... ..140
`6.4.2 Categorization o1'Dictionary-P>ased Coding Techniques ....................................... .. 140
`6.4.3
`Parsing Strategy ...................................................................................................... .. 141
`6.4.4 Sliding Window (LZ77) Algorithms.....
`6.4.5 LZ78 Algorithms ..................................................................................................... .. 145
`International Standards for Lossless Still Image Compression ......................................... ..149
`6.5.1
`l.osS1css Bilevel Still Image Compression ............................................................. ..150
`6.5.2 Lossless Multilevel Still Image Compression ........................................................ .. 150
`Summary ...................................................................................................................... ..
`....151
`6.6
`6.7 Exercises ............................ ..
`References .................................................................................................................................... ..153
`
`
`
`6.5
`
`Section II Still Image Compression
`
`.... ..107
`
`Still Image Coding Standard: JPEG
`Chapter 7
`7.1
`Introduction ......................................................................................................................... ..157
`
`7.2
`
`Sequential DCT-Based Encoding Algorithm ...................................................................... ..159
`
`
`
`10
`
`

`
`10.6 Mot
`10.6
`10.6
`10.6
`10.6
`Suir
`10.7
`10.8 Exei
`References
`
`Chapter 11‘
`11.1 Non
`11.2 Matt
`11.3
`Sear
`11.3
`11.3
`11.3
`11.3
`11.3
`11.3
`11.3
`11.4 Matt
`11.5
`Limi
`11.6 New
`11.6.
`11.6.
`11.6.
`11.6.
`Sum‘
`11.7
`Exert
`11.8
`References.
`
`Chapter 12
`12.1
`Prob.
`12.2 Desc
`12.2.
`12.2.
`12.2.
`12.2.-
`12.2..
`12.2.:
`12.2.‘
`12.3 Netra
`12.3.
`12.3.1
`12.3.1
`12.3.2
`12.4 Other
`12.4.1
`12.4.2
`12.4.2
`12.4.4
`
`Progressive DCT-Based Encoding Algorithm .................................................................. ..163
`7.3
`
`Lossless Coding Mode ................................................................................................ ..164
`7.4
`Hierarchical Coding Mode.................................................................................................. 166
`7.5
`Summary ........................................................................................................................... ..l67
`7.6
`Exercises ............................................................................................................................ .. 167
`7.7
`References .................................................................................................................................... .. 167
`
`8.2
`
`Wavelet Transform for Image Coding
`Chapter 8
`8.1
`Review of the Wavelet Transform .................................................................................... ..169
`8.1.1
`Definition and Comparison with Short-Time Fourier Transform ...................... ..169
`8.1.2
`Discrete Wavelet Transform ................................................................................ .. 172
`Digital Wavelet Transform for Image Compression ........................................................ ..174
`8.2.1
`Basic Concept 01' Image Wavelet Transform Coding ......................................... .. 174
`
`Embedded Image Wavelet Transform Coding Algorithms...
`............. ..176
`8.2.2
`
`8.3 Wavelet Transform for JPEG—2000....................................................................... .. 179
`
`Introduction of JPEG—2()00 ........................................................................... ..179
`8.3.1
`8.3.2
`Verification Model of JPEG-2000 ....................................................................... ..l80
`Summary ........................................................................................................................... ..l82
`8.4
`Exercises ............................................................................................................................ ..182
`8.5
`References .................................................................................................................................... ..183
`
`Nonstandard Image Coding
`Chapter 9
`9.1
`Introduction ...................................................................................................................... ..185
`9.2
`Vector Quantization ........................................................................................................... ..1 86
`9.2.1
`Basic Principle of Vector Quantization ............................................................... ..186
`9.2.2
`Several Image Coding Schemes with Vector Quantization ................................ ..189
`9.2.3
`Lattice VQ for Image Coding ............................................................................. .. 191
`Fractal Image Coding ........................................................................................ ..193
`9.3.1 Mathematical Foundation . . . . . . . . . . . . . . . . . . . . . . . .
`. . . . . . . . . . . . . . . . . .. 193
`9.3.2
`IFS-Based Fractal Image Coding ........................................................................ ..195
`9.3.3
`Other Fractal Image Coding Methods ................................................................ ..197
`
`9.4 Model-Based Coding .................................................................................................... ..l97
`9.4.1
`Basic Concept ...................................................................................................... .. 197
`Image Modeling .................................................................................. ..198
`9.4.2
`
`Summary ................................................................................................................. .. 198
`9.5
`Exercises ................................................ ..
`.................... ..198
`9.6
`References ................................................................................................................................. ..199
`
`
`
`9.3
`
`
`
`Section III Motion Estimation and Compression
`
`Chapter 10 Motion Analysis and Motion Compensation
`10.1
`Image Sequences ......................................................................................................... ..203
`
`Interframe Correlation ................................................................................................. ..205
`10.2
`
`
`Frame Replenishment .................................................................................................... ..208
`10.3
`10.4 Motion-Compensated Coding ........................................................................................... ..209
`10.5 Motion Analysis .......................................................................................................... ..211
`
`10.5.1 Biological Vision Perspective ..................................................................... ..212
`10.5.2 Computer Vision Perspective .................................................................. ..2l2
`
`10.5.3 Signal Processing Perspective .......................................................................... ..2l3
`
`
`
`11
`
`

`
`10.6 Motion Compensation for Image Sequence Processing .................................................. ..2l4
`10.6.1 Motion-Compensated Interpolation .................................................................... ..214
`10.6.2 Motion-Compensated Enhancement ................................................................... ..215
`10.6.3 MotionACompensated Restoration ........................................
`............................. ..217
`10.6.4 Motion-Compensated Down-Conversion ............................................................ ..2l7
`
`....2l7 10.8 Exerciscs....10.7 Summary ............................................................................... .. ....................................... .218
`
`References .................................................................................................................................... ..219
`
`
`
`Chapter 11
`
`Block Matching
`
`11.1 Nonoverlapped, Equally Spaced, Fixed Size, Small Rectangular Block Matching ........ ..22l
`1 1.2 Matching Criteria .............................................................................................................. ..222
`1 1.3
`Searching Procedures ............................. ..
`....224
`1 1.3.1
`Full Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`. . . . . . . . . ..224
`
`
`
`. . . . . . . . . ..224
`2-D Logarithm Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`11.3.2
`1 1.3.3 Coarse-Fine Three-Step Search ........................................................................... ..226
`11.3.4 Conjugate Direction Search ................................................................................ ..226
`1 1.3.5 Subsampling in the Correlation Window ............................................................ ..227
`1 1.3.6 Multiresolution Block Matching ...........................................