Volume 6, No. 4, August 1994
`
`
`
`
`
`
`
`
`_
`
`ea)
`
`nie
`
`ria
`
`:
`
`BSENTGnelesccine
`
`:
`
`ISSN 0923-5965
`
`6(4) 281-378 (1994)
`
`
`
`
`
`
`
`
`IMAG
`
`COMMUNICAT
`
`Papers
`
`
`
`CONTENTS
`
`
`
`
`
`.
`
`
`
`
`
`
`
`
`
`
`
`
`A publication of the European Association for Signal Processing (EURASIP)
`
`J.P. Fillard, J.M. Lussert, M. Castagné and H. M'timet
`
`
`
`
`
`
`
`
`
`Fourier phase shift location estimation of unfocused optical point spread functions
`
`
`
`
`
`
`
`
`
`
`R.-J, Chen and B.-C. Chieu
`
`
`
`
`
`A fully adaptive DCT based color image sequence coder.
`
`
`
`
`
`
`
`
`A. Neri, G. Russo and P. Talone
`
`
`
`
`
`
`
`Inter-block filtering and downsampling in DCT domain .....
`
`
`
`
`
`
`
`
`J.-H. Moon and J.-K. Kim
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`On the accuracy and convergence of 2-D motion models using minimum MSE motion estimation -
`M.W. Mak and W.G. Allen
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`A lip-tracking system based on morphological processing and block matching techniques.
`S. Chang, C.-W. Jen and C.L, Lee
`
`
`
`
`
`
`
`A motion detection scheme for motion adaptive pro-scan conversion .
`
`
`
`
`
`
`
`
`
`Z. Sivan and D. Malah
`
`
`
`
`
`Change detection and texture analysis for image sequence coding
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`.
`.
`
`
`Announcement
`
`.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Theory. Techniques & Applications
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 1 of 18
`
`GOOGLE EXHIBIT 1006
`
`

`

`Guest Editors
`S.A. Benton (MIT, USA)
`G. De Haan (Philips, The Netherlands)
`T. Fujii (NTT, Japan)
`
`
`J. Guichard (CNET, France)
`
`
`
`
`J. Hamasaki (Univ Tokyo, Japan)
`
`
`
`
`
`
`J. Johann (Deutsche Bundespost, Germany)
`
`
`
`
`T. Kurita (NHK, Japan)
`
`
`
`
`D. LeGall (C-Cube, USA)
`
`
`
`
`
`B. Liu (Princeton Univ, USA)
`
`
`
`
`G. Morrison (BT Labs, United Kingdom)
`
`
`
`
`S. Okubo (NTT, Japan)
`
`
`
`T. Omachi (NEC, Japan)
`
`
`
`
`W.Verbiest (Belgium)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Imaging Technology
`
`Display Technology
`VLSI Processorsfor
`Image Communications
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`TV and Advanced TV
`Broadcasting
`image Storage and Retrieval
`Graphic Arts
`
`
`
`
`Electronic Printing
`
`
`
`
`
`
`
`
`SIGNAL PROCESSING
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`IMAGE COMMUNICATION
`
`
`Theory, Techniques & Applications
`
`
`A publication of the European Association for Signal Processing (EURASIP)
`
`
`
`
`Editor-in-Chief
`C.N. Judice (Bellcore, USA)
`Leonardo CHIARIGLIONE
`J.-K. Kim (KAIST, South Korea)
`
`
`
`
`
`
`
`Centro Studi e Laboratori
`A.B. Lippman (MIT, USA)
`H.G. Musmann (Univ. Hannover, Germany)
`Telecommunicazioni (CSELT)
`
`
`
`
`
`
`D. Nasse (CCETT, France)
`Via Guglielmo Reiss-Romoli, 274
`
`
`
`
`
`
`
`1-10148 Torino, Italy
`A. Netravali (ATT, USA)
`
`
`
`
`
`
`
`
`Telephone:
`(11) 2286 120
`Y. Ninomiya (NHK, Japan)
`
`
`
`
`
`Telefax: (11) 2286 299
`D. Pearson (Univ. Essex, United Kingdom)
`
`
`
`
`
`
`H. Seguin (CNET. France)
`Editorial Board
`
`
`
`
`
`
`
`L. Stenger (FI/DBP, Germany)
`
`
`
`
`
`
`J. Biemond (Univ. Delft, The Netheriands)
`
`
`H. Tominaga (Waseda Univ., Japan)
`
`
`
`
`
`
`
`
`
`G. Boerger (HHI, Germany)
`M. Vetterli (Columbia Univ., USA)
`E. Dubois (Univ. Quebec, Canada)
`
`
`
`
`L.T. Wu (ITRI, Taiwan)
`
`
`
`
`
`B. Girod (K6In, Germany)
`H. Yasuda (NTT, Japan)
`
`
`
`
`
`
`
`
`H. Harashima(Univ. Tokyo, Japan)
`
`
`
`
`
`
`
`
`
`
`
`
`
`IMAGE COMMUNI-
`
`
`
`
`Editorial Policy. SIGNAL PROCESSING:
`
`
`
`
`
`
`
`
`CATION is an international journal for the developmentof the
`theory and practice of image communication. Its primary objec-
`tives are the following:
`
`
`
`
`
`To present a forum for the advancement of the theory and
`
`
`
`
`
`
`
`
`
`practice of image communication.
`
`
`
`
`
`
`
`
`- To stimulate cross-fertilization between areas similar in nature
`
`
`
`
`which havetraditionally been separated, for example, various
`
`
`
`
`
`
`
`
`
`
`aspects of visual communications and information systems.
`
`
`
`
`- To contribute to a rapid information exchange between the
`
`
`
`
`
`
`
`industrial and academic environments.
`
`
`
`
`
`
`
`The editorial policy and the technical content of the journal are
`
`
`
`
`
`
`
`the responsibility of the Editor-in-Chief and the Editorial Board
`
`
`
`
`
`
`
`
`The Journal
`is self-supporting from subscription income and
`
`
`
`
`contains a minimum amount of advertisements. Advertisements
`
`
`
`
`
`
`
`
`
`
`are subjectto the prior approvalof the Editor-in-Chief. The journal
`
`
`
`
`
`
`
`
`
`welcomescontributions from every country in the world.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Scope. SIGNAL PROCESSING: IMAGE COMMUNICATION pub-
`
`
`
`
`
`
`
`
`
`
`
`lishes articles relating to aspects of the design, implementation
`
`
`
`
`
`
`
`
`and use of image communication systems.
`SIGNAL PROCESSING: IMAGE COMMUNICATION features orig-
`
`
`
`
`
`inal research work, tutorial and review articles, and accounts of
`
`
`
`
`
`
`
`
`practical developments
`
`
`
`
`
`
`
`
`
`Subjects. Subject areas covered by the journal include:
`
`
`
`
`
`
`
`
`TV, HDTV and 3D-TV systems
`Image Transmission
`
`
`Visual Science
`Interactive Image
`
`Image Coding Communication
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`© 1994 Elsevier Science B.V. All right reserved
`
`
`
`
`
`
`
`Nopart of this publication may bereproduced, stored in a retrieval system or transmitted in any form or by any means. electronic, mechanical, photocopying, recording or
`otherwise, without the prior permission of the publisher, Elsevier Science B.V,. Copyright and Permissions Department, P.O. Box 521, 1000 AM Amsterdam, The Netherlands
`Special regulations for authors. Upon acceptance of an article by the journal, the author(s) will be asked to transfer copyright of the article to the publisher. This transter will
`
`
`
`
`
`
`
`
`ensure the widest possible dissemination of information
`
`Speciai regulations for readers in the USA. This journal has been registered with the Copyright Clearance Center, Inc. Consent is given for copying of articles for personal or
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`internal use, or for the personal use of specific clients. This consentis given on the condilion that the copier pays through the Center the per-copytee stated in the code on the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`first page of eacharticle for copying beyond that permitted by Sections 107 or 108 of the US Copyright Law. The appropriate lee should be forwarded with a copy ofthe first
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`page ofthe article to the Copyright Clearance Center. Inc., 27 Congress Street, Salem, MA 01970, USA.
`If no code appears in an article, the author has not given broad consent
`
`
`
`
`
`
`
`to copy and p&rmission to copy must be obtained directly trom the author. The fees indicated on thefirst page of an article in this issue will apply retroactively to ail articles
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`published in the journal, regardless of the year of publication. This consent does not extend to other kinds ofcopying. such as for general distribution, resale, advertising and
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`promotion purposes, or for creating new collective works. Special written permission must be obtained from the publisher for such copying.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`No responsibility is assumed by the Publisher for any injury and/or damage to persons or property as a matter of products Habilty, negligence or otherwise, or from any use
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`or operation of any methods. products, instructions or ideas conlained in the material herein
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Althoughall advertising material is expected to conform to ethical standards. inciusion in this publication does not constitute a guarantee or endorsementof the quality or
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`value of such product or of the claims made of it by its manufacturer.
`,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`@ The paperusedin this publication meets the requirements of ANSI/NISO 239.48-1992 (Permanence of Paper).
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`0923-5965/94/$07.00
`Printed in The Netherlands
`Published 6 times a year
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 2 of 18
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Membership and Subscription Information.
`SIGNAL PROCESSING:
`IMAGE COMMUNICATION (ISBN 0923-
`5965) is published in one volume(six issues) a year. For 1994
`Voiume 6 is scheduled for publication. Subscription prices are
`
`
`
`
`available upon request from the publisher. Subscriptions are
`
`
`
`
`
`accepted on a prepaid basis only and are entered on a calendar
`
`
`
`
`
`
`
`
`
`
`
`
`year basis. Issues are sent by surface mail exceptto the following
`
`
`
`
`
`
`
`
`
`countries, where air delivery (SAL
`Surface Air Lifted) is
`
`
`
`
`
`
`
`
`ensured: Argentina, Australia, Brazil, Canada, Hong Kong, India,
`
`
`
`
`
`
`
`
`
`
`
`
`Israel, Japan, Malaysia, Mexico, New Zealand, Pakistan, People’s
`
`
`
`
`
`
`
`
`
`
`
`
`Republic of China, Singapore, South Africa, South Korea, Taiwan,
`
`
`
`
`
`
`
`
`
`Thailand, USA. For the rest of the world, airmail charges are
`
`
`
`
`
`
`
`
`available upon request. Claims for missing issues will be honour-
`
`
`
`
`
`
`
`
`ed free of charge if made within six monthsafter the publication
`
`
`
`
`
`
`
`
`
`date of the issues Mail orders and inquiries to: Elsevier Science
`
`
`
`
`
`
`
`
`
`
`
`B.V., Journals Department, P.O, Box 211, 1000 AE Amsterdam,
`
`
`
`
`
`
`
`
`
`The Netherlands. For full membership information of the Associ-
`
`
`
`
`
`
`
`
`
`
`
`ation, possibly combined witha. subscription at a reduced rate,
`
`
`
`
`
`
`
`
`
`
`please contact: EURASIP. P.O Box 134, CH-1000 Lausanne 13,
`
`
`
`
`
`
`
`
`
`
`Switzerland
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 2 of 18
`
`

`

`
`
`
`Signal Processing: IMAGE COMMUNICATION
`
`
`
`
`
`
`Volume 6, No. 4, August 1994
`
`
`
`CONTENTS
`
`
`
`Papers
`
`
`
`.
`
`
`
`
`
`
`
`
`
`
`:
`J.P. Fillard, J.-M. Lussert, M. Castagne and H. M'timet
`
`
`
`
`
`
`
`
`
`
`
`Fourier phaseshift location estimation of unfocused optical point spread functions... .
`
`
`
`
`
`R.-J. Chen and B.-C. Chieu
`
`
`
`
`
`
`
`
`
`A fully adaptive DCT based color image sequence coder.....................
`
`
`
`
`
`
`
`A. Neri, G. Russo and P. Talone
`
`
`
`
`
`
`
`
`Inter-block filtering and downsampling in DCT domain ...................4,
`
`
`
`
`
`J.-H. Moon and J.-K. Kim
`
`
`
`
`
`
`
`
`
`
`
`
`
`On the accuracy and convergence of 2-D motion models using minimum MSE motion
`
`
`estimation ©6
`
`
`
`
`
`M.W. Mak and W.G. Allen
`
`
`
`
`
`
`
`
`
`
`A lip-tracking system based on morphological processing and block matching
`
`
`techniques.
`20.
`
`
`
`
`
`
`
`S. Chang, C.-W. Jen and C.L. Lee
`
`
`
`
`
`
`
`
`
`A motion detection scheme for motion adaptive pro-scan conversion .............
`
`
`
`
`
`Z. Sivan and D. Malah
`
`
`
`
`
`
`
`
`
`Change detection and texture analysis for image sequence coding. ..............
`
`
`281
`
`
`289
`
`303
`
`
`
`319
`
`
`
`335
`
`
`
`349
`
`
`
`357
`
`
`
`
`
`
`
`
`
`Announcement ....0...
`
`377
`
`a complete checklist with each diskette. Additional copies of the guide and the checklist are available from the publisher
`
`
`Authors may now accompanytheir manuscripts with texts in electronic form
`
`
`
`
`
`
`
`
`
`
`
`
`Please see the notes on the inside back cover and the guide at the back of the issue. Authors are requested to submit
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ANNOUNCEMENT
`
`
`Page 3 of 18
`
`Page 3 of 18
`
`

`

`may be protected byCopyright law (Title 17 U.S. Code)
`
`
`
` Signal Processing:
`
`
`
`
`
`
`
`
`
`SIGNAL PROCESSING:
`
`
`
`
`IMAGE
`COMMUNICATION
`
`
`
`
`
`
`
`Image Communication 6 (1994) 303-317
`
`
`
`
`
`
`
`
`
`Inter-block filtering and downsampling in DCT, domain!
`
`
`
`
`
`
`
`
`
`
`
`
`
`A. Neri®, G. Russo”, P. Talone”’*
`
`* University of ‘Rome LI’, Rome, Italy
`
`
`
`
`
`
`
`
`> Fondazione Ugo Bordoni, Via B. Castiglione 59, 00142 Rome, Italy
`
`
`
`
`
`
`
`
`
`
`Received 16 December 1992
`
`
`
`
`
`
`
`
`Abstract
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The extensive use ofdiscrete cosine transform (DCT) techniques in image coding suggests the investigation on filtering
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`and downsampling methods directly acting on the DCT domain. As DCT image transforms usually operate on blocks, it
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`is useful that the DCTfiltering techniques preserve the block dimension. In this context the present paper first revises the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`intra-block filtering techniques to enlightenthe limitations implied by small block dimensions. To overcomethe artefacts
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`introduced bythis methodand tosatisfy the filtering design constraints which are usually defined in the Fourier domain,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`inter-block techniques are developed starting from the implementation of FIR filtering. Inter-block schemes do not
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`exhibit any limitation but their computational cost has to be taken into account. In addition, hybrid techniques, using
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`variable length FIR filters after the discard of low order DCT coefficients, are introduced to increase the computational
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`efficiency; in this case, the introduced aliasing has to be kept at tolerable values. The amount of the tolerable aliasing
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`strictly depends on the subsequent operations appliedto the filtered and downsampled image. The numerical examples
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`reported could forma basis for error estimation and evaluation oftrade-off between performance and computational
`
`complexity.
`
`
`
`
`
`
`
`
`
`
`
`
`Key words: Discrete cosine transform; Block operation; Filtering; Downsampling
`
`
`
`
`1. Introduction
`
`
`
`
`
`
`
`
`
`
`Filtering and downsampling of image signals are
`
`
`
`
`
`
`basic operations normally performed in image pro-
`
`cessing.
`
`
`
`
`
`
`+39-6-54803460, Fax
`
`
`
`
`*Corresponding author. Tel:
`
`
`
`
`54804404
`
`in the framework of the
`'This work has been carried out
`
`
`
`
`
`
`
`
`
`
`
`agreement between Fondazione Bordoni and the Italian PT
`
`
`
`
`
`
`
`Administration.
`
`
`
`+ 39-6-
`
`
`
`
`0923-5965/94/$7.00 © 1994 Elsevier Science B.V. All rights reserved
`
`
`
`
`
`
`
`SSDI 0923-5965(93)00017-D
`
`
`
`
`
`
`
`
`
`
`
`
`
`This is, for instance, the case of spatial scalabil-
`
`
`
`
`
`
`
`
`ity (e.g, MPEG High 1440x1152 = CCIR 601
`
`
`
`
`
`
`
`
`
`
`
`720 x 576 = MPEG SIF 352x288 [2,6] and
`
`
`
`
`
`
`
`
`JPEG Progressive Hierarchical Mode [7]) as well
`
`
`
`
`
`
`as of chrominance downsampling (e.g. CCIR
`
`
`
`
`
`
`4:4:4 > CIR 4:2:2 => MPEG 4:2:0 [2,6]).
`
`
`
`
`
`Filtering and downsampling are usually carried
`
`
`
`
`
`
`
`
`
`
`out in the space domain by means ofFIR filters.
`
`
`
`
`
`
`
`
`However, the extensive use of DCTtechniquesin
`
`
`
`
`
`
`
`
`image coding suggested the investigationon filter-
`
`
`
`
`
`
`ing and downsampling directly in the transformed
`
`
`
`
`
`
`(DCT) domain. As DCTimagetransforms usually
`
`
`
`
`
`
`Page 4 of 18
`
`

`

`304
`
`
`
`A. Neri et al.; Signal Processing:
`
`
`
`
`
`
`
`Image Communication 6 (1994) 303-317
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`operate on square blocks of smal] dimension (8, 16),
`
`
`
`
`
`DCToperations are usually intra-block oriented.
`
`In particular, the above mentioned operations can
`
`
`
`
`
`
`be realized as matrix products [1, 5,810, 12, 13].
`
`
`
`
`
`
`
`
`
`
`The possibility to combine into a unique oper-
`
`
`
`
`
`
`
`
`ator (acting on spatial or
`transformed blocks)
`
`
`
`
`
`
`a series of block operations such as direct and
`
`
`
`
`
`
`
`
`inverse transforms, intra-blockfiltering and down-
`
`
`
`
`
`
`
`sampling was demonstratedin [1].
`
`
`
`
`The matrix based operations allow to directly
`
`
`
`
`
`
`produce
`
`— the DCTtransform ofa filtered or downsampled
`
`
`
`
`
`
`
`image from the original image,
`
`
`
`
`the DCT transform ofa filtered or downsampled
`
`
`
`
`
`
`
`image from its DCT,
`
`
`
`
`~ a filtered or downsampled image from its DCT.
`
`
`
`
`
`
`
`This paper presents a brief review of the intra-
`
`
`
`
`
`
`
`
`
`block filtering methods in DCT domain and dis-
`
`
`
`
`
`
`
`cusses their performance.
`
`
`
`
`
`
`
`
`
`Then,-in order to overcomethe intra-block tech-
`nique drawbacks, an inter-block filtering method
`
`
`
`
`
`and some hybrid techniques are presented and dis-
`
`
`
`
`
`
`
`cussed. The use of an inter-block techniqueis neces-
`
`
`
`
`
`
`
`
`
`sary to satisfy the filtering design constraints which
`
`
`
`
`
`
`
`are usually defined in the Fourier domain.
`
`
`
`
`
`
`
`
`All the above-mentioned techniques are present-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ed in a context that aims at preserving the trans-
`formed block dimension; this means that, manipu-
`
`
`
`
`
`
`
`
`
`lating image blocks of N x N pixels, a transformed
`
`
`
`
`
`
`
`
`
`kN xhN macroblock is considered as a set of (hk)
`
`
`
`
`
`
`transformed blocks of dimension N x N and not as
`
`
`
`
`
`
`
`
`
`
`a single kN x hN transformed block.
`
`
`
`
`
`
`The paper is organized as follows. Sections 2
`
`
`
`
`
`
`
`
`and 3 report a concise review of some basic con-
`
`
`
`
`
`
`
`
`
`
`cepts and definitions regarding spatial filtering,
`
`
`
`
`
`downsampling and DCT transform. Moreover, no-
`
`
`
`
`
`
`tation used in the following description is introduc-
`
`
`
`
`
`
`
`
`ed. In Section 4 a method to perform spatial down-
`
`
`
`
`
`
`
`
`
`
`sampling in DCT domain is presented. Section
`
`
`
`
`
`
`5 presents a review of‘the intra-block filtering tech-
`
`
`
`
`
`niques in DCT domain andillustrates their perfor-
`
`
`
`
`
`
`
`
`
`mance. In Section 6, an inter-block filtering tech-
`
`
`
`
`
`
`nique is proposed and its properties are discussed.
`
`
`
`
`
`
`
`
`Finally, in Section 7, hybrid methods to increase
`
`
`
`
`
`
`the computational efficiency of the inter-block
`
`
`
`
`
`technique are suggested and their performance are
`
`
`
`
`
`
`
`
`
`
`
`
`
`directly derived from the results illustrated in Sec-
`
`tions 5 and 6.
`
`
`
`
`-
`
`Page 5 of 18
`
`2. Spatial filtering and downsampling
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Imagefiltering is usually carried out in the space
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`domain by means of FIR filters. Simple methods
`
`
`
`
`
`
`
`
`
`based on pixel averaging are reported in [6,7].
`
`
`
`
`
`
`
`The well established FIR design techniques allow
`
`
`
`
`
`
`
`to easily satisfy the frequencyfiltering constraints.
`As a matter of fact,
`these constraints are usually
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`given in terms of templates in the Fourier domain.
`For instance,
`the template for insertion loss/fre-
`
`
`
`
`
`
`
`quency characteristic of the CCIR recommended
`
`
`
`
`
`
`
`
`
`low-passfilter for the 4:4:4 > 4:2:2 format con-
`
`
`
`
`
`
`version is reported in [2].
`
`
`
`
`A usual method to perform spatial bidimensional
`
`
`
`
`
`
`
`
`2:1 downsampling on an imageis to serially oper-
`
`
`
`
`
`
`
`ate on columns and on rows.
`
`
`
`
`
`
`
`
`Executing a 2:1 column downsampling on
`
`
`
`
`
`
`
`
`a N x2N block [g] meansessentially to assemble
`
`
`
`
`
`
`
`
`
`
`an N x N matrix with the odd columnsof[g].
`
`
`
`
`
`
`
`
`The assembly must be preceded by a low-pass
`
`
`
`
`
`
`
`filter on [g] rows to reduce aliasing effects on the
`
`
`
`
`
`
`
`
`
`
`downsampled image.
`
`
`Similarly, a 2:1 row downsampling on a 2N x N
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`block [g] means to assemble an N x N matrix with
`
`the odd rowsof [gq].
`
`
`
`
`
`
`
`
`
`
`
`
`
`Obviously the choice of odd columns or rowsis
`
`
`
`
`
`
`
`
`a conventional matter; the operations on the even
`componentsare totally equivalent.
`
`
`
`
`
`
`
`
`
`
`3. DCT operator
`
`
`
`
`
`
`
`Let g;; be the ij-element of the N x N image block
`
`
`
`
`
`
`
`
`
`
`
`{g] and G,,
`the uv-element of the NxN_ two-
`
`
`
`
`
`
`
`dimensional DCT [G].
`
`
`
`As well known, G,, has the following expression
`
`
`
`
`
`
`
`[11]:
`
`
`
`
`
`
`
`
`c(u)e(v) Xo! Xo!
`(2i + lun
`
`
`i=0 3, ,
`2N
`
`Gy, = 2 ———
`gi; Cos ——————
`
`
`
`
`
`
`
`
`
`
`(27 + lox
`IN
`x COS
`5 ————_,
`
`
`
`
`
`
`(1)
`1
`
`where
`
`
`
`c(u), c(v) =
`
`
`
`
`
`
`
`1/,/2,
`
`1,
`
`if uv=0,
`
`
`
`
`otherwise,
`
`
`
`
`
`u,v =0,...
`
`
`
`
`
`»N—1.
`
`Page 5 of 18
`
`

`

`A. Neri et al./ Signal Processing: Image Communication 6 (1994) 303-317
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`305
`
`
`Cv} x [2]
`
`
`Malis operaioe
`
`
`
`
`
`2 vertical adjacent
`
`
`
`DCT blocks
`
`
`
`
`= Bs1 DCT block
`
`
`
`
`
`
`
`
`[ wen | x
`
`
`2 horizontal adjacent
`
`
`DCTblocks
`
`
`
`S
`
`N
`
`
`
`>
`
`
`
`
`
`
`Matrix operator
`
`
`
`
`[ni]
`
`1 DCT biock
`
`
`
`
`
`
`
`
`
`Applying the two-dimensional [DCT transform
`
`
`
`[tt] to the matrix [G],
`the element g,; can be
`
`
`
`
`
`
`
`
`
`
`
`expressed as
`
`
`
`*
`
`(2)
`
`
`
`
`
`
`
`
`
`
`2i+ jun
`2 N-1N-1
`=H X » c(u)c(v)Gy, cos e i
`
`
`
`
`
`
`
`
`
`
`j + leon
`
`
`* COS SN
`
`
`
`
`=2
`
`
`
`
`
`
`ij=0,...,N— 1.
`
`
`
`
`
`
`
`
`
`Fig. 1. DCT rowor column downsampling.
`
`
`
`
`
`
`
`
`
`
`
`Eqs. (1) and (2) may be, respectively, written in
`matrix notation as
`
`
`
`
`
`(the subscript s indicates the row or column down-
`
`
`
`
`
`
`
`sampled blocks):
`
`
`
`
`
`(G]=(T] [9] (7]'.
`
`
`
`
`(9]=(7T]‘ (G] [7].
`
`
`
`
`
`
`
`(3)
`
`
`(4)
`
`
`
`
`
`
`
`
`
`
`
`
`where [7] is the Nx N DCT transform matrix
`
`
`
`
`
`
`
`that
`{11]. The DCT unitary property assures
`
`
`([7]~' =[7]" where [7]' meansthe transposeof.
`
`
`
`
`
`
`
`
`[T].
`
`
`
`
`
`
`
`
`
`In the following of this work we will use lower-
`
`
`
`
`
`
`
`
`case letters to indicate variables in the spatial do-
`
`
`
`
`
`
`
`
`
`main, and capitalletters for variables in the DCT or
`DFT domain.
`
`
`
`
`
`
`
`
`
`
`
`4. The 2:1 downsampling in DCT domain
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`As mentioned in Section 2, column and row
`downsampling are separately considered. First col-
`
`
`
`
`
`
`
`
`
`
`
`umn downsampling will be illustrated.
`
`
`
`
`
`
`In the present section a downsampling operator
`
`
`
`
`
`
`
`equivalent to the one operating a spatial row down-
`
`
`
`
`
`
`
`
`
`
`sampling, but acting on two N x N 2D-DCTblocks
`
`will be examined. Obviously, a horizontal down-
`
`
`
`
`
`
`sampling operator acting on 1D-DCTs could be
`
`
`
`
`
`
`derived in a similar way; however, we focus our
`
`
`
`
`
`
`
`
`
`attention on the 2D case because the 2D-DCT
`
`
`
`
`
`
`
`
`
`defined by Eq. (3) is more frequently applied in
`
`
`
`
`
`
`
`
`
`image coding.
`
`
`
`
`
`
`
`
`
`
`In any case, the operator produces one DCT
`
`block as shownin Fig. 1.
`
`
`
`
`
`
`Column downsampling can be obtained just by
`
`
`
`
`
`
`applying the same operator in its transposed form.
`
`
`
`
`
`
`
`
`The 2:1 downsampling performed on a couple of
`
`
`
`
`
`
`
`adjacent N x N blocks [[g"’] | [g* !)]] can be ex-
`
`
`
`
`
`
`
`
`
`
`pressed (in space domain) in the following manner
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 6 of 18
`
`fo"), = (lo II i916]
`
`
`
`
`= (foIi fe" TCS),
`
`
`
`
`where [g'""*')], is the downsampled N x N block
`
`
`
`
`
`
`
`
`
`
`
`
`
`and [S] is a 2NxN downsampling matrix oper-
`ator defined as follows:
`
`
`
`
`
`
`(5)
`
`
`
`
`1
`
`
`[S] =
`
`0 0 0
`
`
`
`00 0 0
`
`
`
`
`
`0! 0
`
`
`
`00 0
`
`
`
`
`
`
`00 1
`
`
`
`0000 -:
`
`
`
`
`
`
`00 0
`
`
`
`0
`
`0
`
`0
`
`1
`
`0
`
`
`0
`
`
`
`
`
`
`
`0
`
`0
`
`0
`
`0
`
`0
`
`-
`
`
`
`
`0 0
`
`0 0
`
`
`
`
`
`
`
`
`
`l
`
`
`
`
`
`
`
`
`
`The [S] operator performs the odd columns
`
`
`
`
`
`
`
`
`
`discard. From Egg.(3) and (5), the 2D-DCT trans-
`
`
`
`
`form of [g'""* J, is
`
`
`
`
`
`
`
`
`
`Corr}, = (TULEg PUES IE)!
`
`=(TIlo" lg? PNETs1 |
`
`
`
`
`
`
`x (TSI!
`
`
`
`= [1G] (6° U7 IS IUTT
`
`
`
`
`
`
`
`
`(6)
`
`Page 6 of 18
`
`

`

`306
`
`
`
`A. Neri et al./ Signal Processing: Image Communication 6 (1994) 303-317
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`where [7,] is a 2Nx2Nblock DCT transform
`
`
`
`
`
`
`
`matrix defined as follows:
`
`
`
`
`
`
`
`
`-[ioy cri}
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Hence, Eq. (6) can be rewritten as
`
`
`
`
`
`[o™"""}, = [C61\(6"* 9]10F
`
`
`
`where
`
`
`(F]=(T. S17)".
`
`
`(7)
`
`(8)
`
`
`
`
`
`
`
`
`
`
`
`
`[F] is a 2N x N operator which can be applied
`to a couple of consecutive DCT transformed N x N
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`blocks to obtain a single N x N transformed block
`
`
`
`
`
`
`of the horizontal 2:1 downsampled image.
`
`
`
`
`
`
`
`
`Considering the row downsampling, it
`is easily
`shown that the required operatoris just the trans-
`
`
`
`
`
`
`
`
`
`
`pose of [F ].
`
`
`
`
`
`
`
`
`
`5. Intra-block filtering in DCT domain
`
`
`
`
`
`
`has the following DCT transform [3]:
`
`
`Yo, j) = Xc(i,j) A(t),
`
`
`
`
`
`
`
`
`
`
`j= —N, -N+1,..,N—-—2,N—1;
`
`
`
`
`
`
`
`(11)
`
`
`
`
`
`
`
`
`
`
`
`
`
`where Y-(i,j) and X¢(i,j) are the Nx N DCT
`
`
`
`
`
`
`
`
`
`symmetrically extended to the [ —N,...,N —1;
`
`
`
`
`
`
`
`
`
`
`—N,...5 N—1]
`range as defined in
`[3] of
`
`
`
`
`
`
`
`the sequences y and x respectively, while H-(i, j)
`
`
`
`
`
`
`
`
`
`the bidimensional DFT of the filter impulse
`is
`
`
`response.
`
`
`
`
`
`Ideal low-pass filtering in horizontal direction
`
`
`
`
`
`
`correspondsto a frequency operator H(i, j) of the
`
`
`following type:
`
`
`
`
`,
`
`
`
`
`Hy(i,j) =
`
`
`
`(tJ)
`
`
`‘0 otherwise.
`
`
`1, —-W.<j<M,
`
`
`
`;
`
`
`
`
`
`
`
`
`
`
`
`
`
`(11),
`Based on the sequences product of Eq.
`a simple intra-block low-passfiltering operator in
`
`
`
`
`
`
`
`DCT domain can be written in matrix form as
`
`
`
`
`
`
`
`
`
`
`
`follows [1]:
`
`
`
`CY] =(X](P),
`
`
`
`(12)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`As mentioned in Section 2, to reduce aliasing
`
`
`
`
`
`
`effects on the downsampled image, the downsamp-
`
`
`
`
`
`
`
`
`ling operation must be preceded by a low-pass
`
`
`
`filtering on [g].
`
`
`
`
`
`
`Intra-block filtering in DCT domain has been
`investigated in [3,8] where a filter is derived via the
`
`
`
`
`
`
`
`
`convolution-multiplication property of the circular
`
`
`
`
`
`
`
`
`
`
`
`convolution in space domain that can be sum-
`where [/] is a W, x W, unity matrix.
`
`
`
`
`
`
`
`marized as follows.
`
`
`
`
`
`Intra-block filtering operation defined by (12)
`
`
`
`
`
`
`
`
`
`
`
`
`Givenafilter with symmetrical impulse response
`and column downsampling defined in Section 4 can
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`hfi,j) (with==hGj)=AC —i fp =hAG1-—p=
`
`
`
`
`
`
`
`
`
`
`
`
`
`be combined in a unique 2N x N operatoracting in
`
`
`
`
`
`
`
`
`
`
`h(i —i, | — j)) and a real sequence x, the 2D circu-
`the DCT domain on a couple of transformed
`
`
`
`
`
`
`
`
`lar convolution
`
`
`blocks, thus giving the DCT block:
`
`
`
`
`
`
`
`
`
`
`[oe**")], = ([6"""]|(6[2],
`whee 8 ;
`
`[0] =(P2)(72](S](T] -.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`where [X ] and [ Y] are the N x N DCT of x and },
`
`
`
`
`
`
`
`
`
`respectively, and [P] is the following N x N matrix:
`
`=| fo a
`ft (0)
`
`
`
`
`
`
`
`
`
`
`
`y(n, k) = &(n, k)*h(n,k),
`
`
`
`
`
`
`
`
`
`
`on, k =0,1,2,...,N—1,
`
`(9)
`
`where X(n, k) is the 2D symmetrical sequence de-
`
`
`
`
`
`
`
`
`fined by
`
`
`
`
`
`
`
`(13)
`
`
`
`(14)
`
`
`
`
`
`
`
`
`
`njk =0,1,2,...,N—1;
`x(n, k)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`k=0,1,2,...,.N—l, n= —N, -N4+1l,..., -1;
`_}x(—1—17,k)
`
`
`
`Rn, ky =
`
`
`
`
`
`
`
`
`
`
`
`
`
`n=0,1,2,...,.N—-l k= —-N, -N#1,..., -1;
`x(n, —1—k)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`x(-—l—n, —-l1—k) nk= —-N, -N41,..., -1;
`
`
`
`
`(10)
`
`
`
`Page 7 of 18
`
`Page 7 of 18
`
`

`

`A. Neri et al./ Signal Processing: Image Communication 6 (1994) 303-317
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`307
`
`
`
`
`
`
`
`
`In order to illustrate this effect better,
`
`
`
`
`
`
`
`
`express the filter output in DFT domain:
`
`
`
`
`let us
`
`
`
`
`
`[Yprt] = [Xper] [DFT 16] (T2)- [Pz]
`
`
`
`
`
`
`
`x(T,][DFTi6]
`
`
`
`|,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`x, = cog]Oo"Due + 6 n=0,...,N.
`
`
`Xn = \ = c(m,)cos@,
`
`
`Xnem, =— [comsin @2,sin ease
`
`
`
`
`
`(2n + l)mnos =0,...,N.
`
`
`
`
`
`
`
`IN.”
`
`and
`
`
`
`
`(Pa i ot
`
`s,_[CP]
`[0]
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`in the vertical
`It could be easily shown that,
`
`
`
`
`
`
`
`
`
`filtering and row downsampling case, the N x 2N
`
`
`
`
`
`
`
`
`
`operatoris just the transpose of [Q ].
`
`
`
`
`
`
`5.1. Performance
`
`
`
`
`For real images, each N x N imageblock is not
`
`
`
`
`
`
`
`
`approximated by using Eq. (10) written for N/2
`
`
`
`
`
`
`
`instead of N.
`
`
`
`
`
`In particular for small N, expressions (11) and
`
`
`
`
`
`
`
`
`
`(12) cannot be considered approximations of the
`
`
`
`
`
`spatial circular convolution (9),
`
`
`
`
`To understand better the behaviour of the [P]
`
`
`
`
`
`
`
`
`
`
`
`
`
`operator, let us consider a monodimensionalsingle
`
`
`
`
`
`
`
`
`tone with variable phase shift #, centred at fre-
`
`
`quency (m,(1/2N)):
`
`
`
`
`
`
`
`
`7
`
`
`
`
`(2n + l)myn
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`By definition, its one-dimensional DCTis
`
`
`
`
`
`
`
`
`2
`
`
`
`
`
`
`
`
`
`
`
`>
`
`N-1
`
`
`
`
`
`
`
`
`
`
`9.
`
`
`
`
`
`
`
`
`
`)
`
`
`
`
`
`
`
`
`
`
`
`
`The previous expressions show that the X,, coef-
`
`
`
`
`
`
`ficients depend on the input sequence phase ¢ with
`
`
`
`
`
`
`
`
`sinusoidallaw.
`
`
`
`Discarding the coefficient X,,, corresponds to
`
`
`
`
`
`
`
`completely deleting the x sequence onlyif the initial
`
`
`
`
`
`
`
`
`
`
`phase is zero while,
`in the other cases (@ #0;
`
`
`
`
`
`
`
`
`
`
`
`Xm em, #9), only a part of x is deleted. Thus, this
`
`
`
`
`
`
`
`
`operation producesvisible aliasing due to the addi-
`
`
`
`
`
`
`
`
`tional frequency components introduced in the re-
`
`
`
`
`
`
`constructed signal. We remark that aliasing can be
`
`
`
`
`
`
`
`
`
`
`generated even from in-band signals (m, < W,)
`
`
`
`
`
`
`
`since they usually exhibit non-zero high order
`
`
`
`
`
`
`
`
`(m, > W,) DCTcoefficients.
`
`
`
`
`
`
`
`Page 8 of 18
`
`
`
`
`
`
`
`
`
`where [Xprr] and [ Yprr] are the 2N points input
`
`and output DFTs, respectively; {7,] and [P,] are
`
`
`
`
`
`
`
`
`
`defined in Sections 3 and 4 while matrix [DFT>, ] is
`
`
`
`
`
`
`
`
`
`
`
`the 2N points DFT transform matrix defined in
`
`
`
`
`
`
`
`
`[4]. The 2N points extension is necessary to mapall
`
`
`
`
`
`
`
`
`
`the DCT components in the DFT domain [5] for
`
`
`
`
`
`
`
`
`
`a blocksize of N.
`
`
`
`
`
`
`
`In Figs. 2 and 3 two examples of the output
`
`
`
`
`
`
`
`spectra [ Yprr] for both in-band and out-bandsig-
`
`
`
`
`
`
`
`
`nals are reported for N = 8. It comesclear that the
`
`
`
`
`
`
`
`
`
`
`
`[P] operator in DCT domainis not equivalent to
`
`
`
`
`
`
`
`a sharp low-pass filter in the DFT domain.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The precise mapping, in DCT domain,of a gen-
`eric DFT block operation, correspondingto a spa-
`
`
`
`
`
`
`
`
`tial circular convolution, was carried out in [5].
`
`
`
`
`
`
`
`
`
`
`
`Nevertheless, all the filtering techniques above
`are based on intra-block operators and, for this
`
`
`
`
`
`
`
`reason, they do not correspond to a spatial linear
`
`
`
`
`
`
`
`
`convolution. As a consequence,
`the block tech-
`
`
`
`
`
`
`
`niquesare nothelpful in the usualfilter design task
`
`
`
`
`
`
`
`
`
`
`
`
`when the performancesare assigned in the Fourier
`
`
`
`
`
`
`
`
`
`domain.
`
`Strictly speaking, the matrix product techniques
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`should not be namedfiltering when applied, in the
`
`real cases, to adjacent signal blocks. As noted in [1]
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`a matrix product corresponds to a shift variant
`
`
`
`
`
`
`linear operation; consequently, it cannot be repres-
`ented by meansofa transfer function.
`
`
`
`
`
`
`Whenthe input signal is not a DCT frequency
`
`
`
`
`
`
`
`
`
`and the matrix operator is applied to a long se-
`
`
`
`
`
`
`
`
`
`quence of blocks, the method of analysis proposed
`
`
`
`
`
`
`
`
`
`in [1] can be applied.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the input assumes
`In fact,
`if this is the case,
`
`
`
`
`
`
`
`
`
`a different phase in each block and the long-term
`spectrum is phase independent.
`
`
`
`
`The number of output components produced by
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`an input tone is equal to the block size N. Their
`
`position in the baseband spectrum can be deter-
`
`
`
`
`
`
`mined as function of the input frequency f.
`
`
`
`
`
`
`
`
`
`
`Let A be the distance of f from the nearest DCT
`
`
`
`
`
`
`
`
`
`frequency DCT,,. Then the output components are
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 8 of 18
`
`

`

`A. Neri et al. | Signal Processing.
`
`
`
`
`
`
`
`
`Image Communication6 ( 1994) 303-317
`
`
`
`
`
`
`
`
`0 dB
`
`-0,2 dB
`
`-0.8 dB
`
`-1.6 dB
`
`-40
`
`= 27/5
`=3nl10
`
`