Image and Signal Processing: 3rd International Conference, ICISP 2008, Cherbourg-Octeville, July 1-3, 2008, Proceedings

Lecture Notes in Computer Science Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen

Editorial Board David Hutchison Lancaster University, UK Takeo Kanade Carnegie Mellon University, Pittsburgh, PA, USA Josef Kittler University of Surrey, Guildford, UK Jon M. Kleinberg Cornell University, Ithaca, NY, USA Alfred Kobsa University of California, Irvine, CA, USA Friedemann Mattern ETH Zurich, Switzerland John C. Mitchell Stanford University, CA, USA Moni Naor Weizmann Institute of Science, Rehovot, Israel Oscar Nierstrasz University of Bern, Switzerland C. Pandu Rangan Indian Institute of Technology, Madras, India Bernhard Steffen University of Dortmund, Germany Madhu Sudan Massachusetts Institute of Technology, MA, USA Demetri Terzopoulos University of California, Los Angeles, CA, USA Doug Tygar University of California, Berkeley, CA, USA Gerhard Weikum Max-Planck Institute of Computer Science, Saarbruecken, Germany

5099

Abderrahim Elmoataz Olivier Lezoray Fathallah Nouboud Driss Mammass (Eds.)

Image and Signal Processing 3rd International Conference, ICISP 2008 Cherbourg-Octeville, France, July 1 - 3, 2008 Proceedings

13

Volume Editors Abderrahim Elmoataz Olivier Lezoray Université de Caen Basse-Normandie GREYC UMR CNRS 6072 ENSICAEN 6 Bd. Maréchal Juin 14050 Caen, France E-mail:{abderrahim.elmoataz-billah, olivier.lezoray}@unicaen.fr Fathallah Nouboud Université de Québec à Trois-Rivières C.P. 500 Trois-Rivières G9A 5H7, Québec, Canada E-mail: [email protected] Driss Mammass Université IbnZohr BP.8106 Hay Dakhla, Agadir Marocco E-mail: [email protected]

Library of Congress Control Number: 2008929562 CR Subject Classification (1998): I.4, I.5, I.2.10, I.2.6, I.3.5, F.2.2 LNCS Sublibrary: SL 6 – Image Processing, Computer Vision, Pattern Recognition, and Graphics ISSN ISBN-10 ISBN-13

0302-9743 3-540-69904-X Springer Berlin Heidelberg New York 978-3-540-69904-0 Springer Berlin Heidelberg New York

This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. Springer is a part of Springer Science+Business Media springer.com © Springer-Verlag Berlin Heidelberg 2008 Printed in Germany Typesetting: Camera-ready by author, data conversion by Scientific Publishing Services, Chennai, India Printed on acid-free paper SPIN: 12319916 06/3180 543210

Preface

ICISP 2008, the International Conference on Image and Signal Processing, was the third ICISP conference, and was held in Cherbourg-Octeville, Normandy, France. Historically, ICISP is a conference resulting from the actions of researchers of Canada, France and Morocco. Second and first editions of ICISP were held in Agadir, Morocco in 2003 and 2001. ICISP 2008 was sponsored by EURASIP (European Association for Image and Signal Processing) and IAPR (International Association for Pattern Recognition). The response to the call for papers for ICISP 2008 was encouraging. From 193 full papers submitted, 70 were finally accepted (48 oral presentations, and 22 posters). The review process was carried out by the Program Committee members; all are experts in various image and signal processing areas. Each paper was reviewed by at least two reviewers, and also checked by the conference Co-chairs. The quality of the papers in these proceedings is attributed first to the authors, and second to the quality of the reviews provided by the experts. We would like to thank the authors for responding to our call, and we thank the reviewers for their excellent work. We were very pleased to be able to include in the conference program keynote talks by four world-renowned experts: Joachim Weickert, Full Professor of Mathematics and Computer Science at Saarland University, Germany, where he heads the Mathematical Image Analysis Group; Godfried T. Toussaint, Professor Emeritus at the School of Computer Science and the Centre for Interdisciplinary Research in Music Media and Technology at McGill University, Montreal, Quebec, Canada; Driss Aboutajdine, Full Professor at the Science Faculty of Rabat University, Morocco; and David Tschumperl´e, permanent CNRS researcher in the Image group of the GREYC research laboratory, Caen, France. We would like to thank Amal Mahboubi, the web master of the conference for maintaining the Web pages and Agn`es Zannier for her administrative assistance. We would also like to thank the members of the Local Committee for their advice and help. We are also greteful to Springer’s editorial staff for supporting this publication in the LNCS series. Finally, we were very pleased to welcome all the participants to this conference. For those who did not attend, we hope this publication provides a good view into the research presented at the conference, and we look forward to meeting you at the next ICISP conference. April 2008

Abderrahim Elmoataz Olivier Lezoray Fathallah Nouboud Driss Mammass

ICISP 2008 – International Conference on Image and Signal Processing

General Chair Abderrahim Elmoataz Universit´e de Caen Basse-Normandie, France [email protected]

General Co-chair Fathallah Nouboud Universit´e du Qu´ebec `a Trois-Rivi`eres, Qu´ebec, Canada [email protected]

Program Committee Chair Olivier Lezoray Universit´e de Caen Basse-Normandie, France [email protected]

Program Committee Co-chair Driss Mammass Universit´e Ibn Zohr, Morocco driss [email protected]

Webmaster Amal Mahboubi Universit´e de Caen Basse-Normandie, France [email protected]

Conference Secretary Agn`es Zannier GREYC CNRS UMR 6072 [email protected]

VIII

Organization

Sponsoring Institutions Institut Universitaire de Technologie Cherbourg Manche, France Universit´e de Caen Basse-Normandie, France ENSICAEN, France Centre National de la Recherche Scientifique, France Centre National de la Recherche Scientifique, D´el´egation Normandie, France Conseil R´egional de Basse-Normandie, France Conseil G´en´eral de la Manche, France Communaut´e Urbaine de Cherbourg, France ´ Pˆ ole Transactions Electroniques S´ecuris´ees, France

Local Organizing Committee S. Bougleux L. Brun Y. Chahir C. Charrier J. Fadili Z. Lakhdari A. Mahboubi P. Makany S. Schpp V.-T. Ta

Ceremade, Universit´e Paris Dauphine, France Ensicaen, France Universit´e de Caen Basse-Normandie, France Universit´e de Caen Basse-Normandie, France Ensicaen, France Universit´e de Caen Basse-Normandie, France Universit´e de Caen Basse-Normandie, France Universit´e de Caen Basse-Normandie, France Universit´e de Caen Basse-Normandie, France Universit´e de Caen Basse-Normandie, France

Program Committee T. Adali J.M. Aroza A. Bela¨ıd M. Bellafkih B. Boufama A. Chalifour W.-K. Cham L. Chen D. Chiadmi L. Cohen B. Coll J. Crespo F. Deschenes T. Deserno F. Escolano A. Evans D. Gorodnichy M. Gurcan

University of Maryland Baltimore County, USA Universidad de Granada, Spain Universit´e Nancy 2, France INPT - Rabat, Morocco Universit´e de Windsor, Canada Universit´e du Qu´ebec `a Trois-Rivi`eres, Canada Chinese University of Hong Kong, China Ecole Centrale de Lyon, France EMI-Rabat, Morocco Ceremade, Universit´e Paris Dauphine, France Universitat de les Illes Balears, Spain Universidad Polit´ecnica de Madrid, Spain Universit´e du Qu´ebec en Outaouais, Canada Aachen University of Technology, Germany University of Alicante, Spain University of Bath, UK National Research Center, Canada Ohio State University, USA

Organization

R. Harba S. Jehan-Bresson T. Jiang Z. Kato M.L. Kherfi D.-S. Kim W. Kropatsch D. Laurendeau D. L´evesque R. Malgouyres M. Melkemi S. Metari A. Mitiche M. Nikolova G. Peyr´e I. Pitas F. Preteux O. Roudies E. Rubio Royo H. Sahli A. Sbihi B. Smolka J.-L. Starck A. Torsello E. Uchino M. Vento L. Wang D. Zhang D. Ziou

Ecole Polytechnique d’Orl´eans, France ENSICAEN, France The Chinese Academy of Sciences, China University of Szeged, Hungary Universit´e du Qu´ebec `a Trois-Rivi`eres, Canada Hanyang University, Seoul, Korea Vienna University of Technology, Austria Universit´e Laval, Qu´ebec, Canada Universit´e de Sherbrooke, Canada Universit´e Clermont-Ferrand, France Universit´e Haute Alsace, France Universit´e de Sherbrooke, Canada Inrs-Energie, Canada CMLA ENS Cachan, France Ceremade, Universit´e Paris Dauphine, France University of Thessaloniki, Greece INT - Evry, France EMI - Rabat, Morocco Universidad Las Palmas Gran Canaria, Spain Vrije Universiteit Brussel, Belgium Universit´e Ibn Tofail - K´enitra, Morocco Silesian University of Technology, Poland CEA, France University of Venice, Italy Yamaguchi University, Japon University of Salermo, Italy University of Melbourne, Australia Honk Kong Polytechnic University ,China Universit´e Sherbrooke, Canada

IX

Table of Contents

Image Filtering Discrete Pulse Transform of Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Roumen Anguelov and Inger Fabris-Rotelli

1

Constrained Unsharp Masking for Image Enhancement . . . . . . . . . . . . . . . Radu Ciprian Bilcu and Markku Vehvilainen

10

Discrete Wavelet Diffusion for Image Denoising . . . . . . . . . . . . . . . . . . . . . . Kashif Rajpoot, Nasir Rajpoot, and J. Alison Noble

20

Dynamic Color Texture Modeling and Color Video Decomposition Using Bounded Variation and Oscillatory Functions . . . . . . . . . . . . . . . . . . Mathieu Lugiez, Michel M´enard, and Abdallah El-Hamidi

29

Reinstating Floyd-Steinberg: Improved Metrics for Quality Assessment of Error Diffusion Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sam Hocevar and Gary Niger

38

A Neuro Fuzzy Model for Image Compression in Wavelet Domain . . . . . . Vipula Singh, Navin Rajpal, and K. Srikanta Murthy

46

Image Segmentation A People Counting System Based on Dense and Close Stereovision . . . . . Tarek Yahiaoui, Cyril Meurie, Louahdi Khoudour, and Fran¸cois Cabestaing Topology-Preserving Discrete Deformable Model: Application to Multi-segmentation of Brain MRI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sanae Miri, Nicolas Passat, and Jean-Paul Armspach A Real Time Human Detection System Based on Far Infrared Vision . . . Yannick Benezeth, Bruno Emile, H´el`ene Laurent, and Christophe Rosenberger

59

67 76

Computer Vision Uniqueness Filtering for Local Feature Descriptors in Urban Building Recognition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Giang Phuong Nguyen and Hans Jørgen Andersen

85

Dynamic Human Fatigue Detection Using Feature-Level Fusion . . . . . . . . Xiao Fan, Bao-Cai Yin, and Yan-Feng Sun

94

XII

Table of Contents

Real Time Monocular Depth from Defocus . . . . . . . . . . . . . . . . . . . . . . . . . . Jean-Vincent Leroy, Thierry Simon, and Fran¸cois Deschenes

103

Dynamic Skin Detection in Color Images for Sign Language Recognition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Michal Kawulok

112

Depth Estimation by Finding Best Focused Points Using Line Fitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Aamir Saeed Malik and Tae-Sun Choi

120

Improved Phase Correlation Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Javed Ahmed and M. Noman Jafri

128

A New Approach to Estimate Fractal Dimension of Texture Images . . . . Andr´e R. Backes and Odemir M. Bruno

136

Biomedical Applications Digital Signal Processing Techniques for Gene Finding in Eukaryotes . . . Mahmood Akhtar, Eliathamby Ambikairajah, and Julien Epps

144

A CAD System for Long-Bone Segmentation and Fracture Detection . . . Martin Donnelley, Greg Knowles, and Trevor Hearn

153

Comparison of Image Restoration Methods for Bioluminescence Imaging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sma¨ıl Akkoul, Roger Ledee, Remy Leconge, Christophe Leger, Rachid Harba, Sabrina Pesnel, St´ephanie Lerondel, Alain Lepape, and Luis Vilcahuaman Texture-Based Multiscale Segmentation: Application to Stromal Compartment Characterization on Ovarian Carcinoma Virtual Slides . . . Nicolas Signolle, Benoˆıt Plancoulaine, Paulette Herlin, and Marinette Revenu

163

173

Combination of Image Registration Algorithms for Patient Alignement in Proton Beam Therapy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Rachid Belaroussi and Guillaume Morel

183

Speech Signal Processing Based on Wavelets and SVM for Vocal Tract Pathology Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . P. Kukharchik, I. Kheidorov, E. Bovbel, and D. Ladeev

192

Feature Extraction Pair Correlation Integral for Fractal Characterization of Three-Dimensional Histograms from Color Images . . . . . . . . . . . . . . . . . . . . Julien Chauveau, David Rousseau, and Fran¸cois Chapeau-Blondeau

200

Table of Contents

XIII

Accelerating Integral Histograms Using an Adaptive Approach . . . . . . . . . Thomas M¨ uller, Claus Lenz, Simon Barner, and Alois Knoll

209

Volume Estimation of Small Particles Using Three-Dimensional Reconstruction from Multiple Views . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Eduardo Castillo-Castaneda and Christelle Turchiuli

218

A Multivariate Hit-or-Miss Transform for Conjoint Spatial and Spectral Template Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Jonathan Weber and S´ebastien Lef`evre

226

Blur Insensitive Texture Classification Using Local Phase Quantization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ville Ojansivu and Janne Heikkil¨ a

236

An Algorithm to Determine the Chromaticity Under Non-uniform Illuminant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sivalogeswaran Ratnasingam and Steve Collins

244

Transients Detection in the Time-Scale Domain . . . . . . . . . . . . . . . . . . . . . . V. Bruni and D. Vitulano

254

SIFT Based Ball Recognition in Soccer Images . . . . . . . . . . . . . . . . . . . . . . Marco Leo, Tiziana D’Orazio, Paolo Spagnolo, Pier Luigi Mazzeo, and Arcangelo Distante

263

Evaluation Protocol for Localization Metrics: Application to a Comparative Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Baptiste Hemery, H´el`ene Laurent, Christophe Rosenberger, and Bruno Emile

273

Pattern Recognition Classification of Proteomic Signals by Block Kriging Error Matching . . . Tuan D. Pham, Dominik Beck, Miriam Brandl, and Xiaobo Zhou

281

Grip-Pattern Recognition in Smart Gun Based on Likelihood-Ratio Classifier and Support Vector Machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Xiaoxin Shang and Raymond N.J. Veldhuis

289

Chirplet Transform Applied to Simulated and Real Blue Whale (Balaenoptera Musculus) Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mohammed Bahoura and Yvan Simard

296

Illumination Invariant Face Recognition Under Various Facial Expressions and Occlusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ¨ Tiwuya H. Faaya and Onsen Toygar

304

XIV

Table of Contents

A Version of the FastICA Algorithm Based on the Secant Method Combined with Simple Iterations Method . . . . . . . . . . . . . . . . . . . . . . . . . . . Doru Constantin and Luminita State

312

SVM-Based Face Recognition Using Genetic Search for Frequency-Feature Subset Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Aouatif Amine, Mohammed Rziza, and Driss Aboutajdine

321

Graph-Based Representations A Path Following Algorithm for Graph Matching . . . . . . . . . . . . . . . . . . . . Mikhail Zaslavskiy, Francis Bach, and Jean-Philippe Vert

329

Statistically Valid Graph Representations of Scale-Space Geometry . . . . . Tomoya Sakai and Atsushi Imiya

338

Hierarchical Matching Using Combinatorial Pyramid Framework . . . . . . . Luc Brun and Jean-Hugues Pruvot

346

Motion Detection and Estimation Multi-cue Facial Feature Detection and Tracking . . . . . . . . . . . . . . . . . . . . . Jingying Chen and Bernard Tiddeman

356

Body Language Based Individual Identification in Video Using Gait and Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Y. Pratheepan, P.H.S Torr, J.V. Condell, and G. Prasad

368

Human Hand Gesture Recognition Using Motion Orientation Histogram for Interaction of Handicapped Persons with Computer . . . . . . . . . . . . . . . Maryam Vafadar and Alireza Behrad

378

3D Human Motion Reconstruction Using Video Processing . . . . . . . . . . . . Nadiya Roodsarabi and Alireza Behrad

386

New Interfaces Personal Recognition Using Single-Sensor Multimodal Hand Biometrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Andreas Uhl and Peter Wild

396

Face Tracking for Spatially Aware Mobile User Interfaces . . . . . . . . . . . . . Jari Hannuksela, Pekka Sangi, Markus Turtinen, and Janne Heikkil¨ a

405

Markerless Augmented Reality Using Image Mosaics . . . . . . . . . . . . . . . . . . Pietro Azzari, Luigi Di Stefano, Federico Tombari, and Stefano Mattoccia

413

Table of Contents

XV

Retracted: A Novel Text-Independent Speaker Verification System Using Ant Colony Optimization Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421 Shahla Nemati, Reza Boostani, and Mohammad Davarpanah Jazi Image Retrieval: Color and Texture Combining Based on Query-Image . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ilya Markov and Natalia Vassilieva Markerless Outdoor Localisation Based on SIFT Descriptors for Mobile Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Frank Lorenz Wendt, St´ephane Bres, Bruno Tellez, and Robert Laurini

430

439

Document Processing Off-Line Arabic Handwritten Characters Recognition Based on a Hidden Markov Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . M. Amrouch, M. Elyassa, A. Rachidi, and D. Mammass

447

Watermarking Based on the Density Coefficients of Faber-Schauder Wavelets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mohamed El hajji, Hassin Douzi, and Rachid Harba

455

Arabic Handwritten Characters Classification Using Learning Vector Quantization Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mohamed A. Ali

463

A Complete Pyramidal Geometrical Scheme for Text Based Image Description and Retrieval . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Guillaume Joutel, V´eronique Eglin, and Hubert Emptoz

471

Local Orientation Extraction for Wordspotting in Syriac Manuscripts . . . P. Bilane, S. Bres, and H. Emptoz

481

Signal Processing A Procedure for Efficient Generation of 1/f β Noise Sequences . . . . . . . . . Youcef Ferdi and Abdelmalik Taleb-Ahmed

490

Design and Implementation of an Image CoProcessor . . . . . . . . . . . . . . . . . R. Ebrahimi Atani, S. Mirzakuchaki, and S. Ebrahimi Atani

498

Wavelet-Packet Identification of Dynamic Systems with Coloured Measurement Noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Henrique Mohallem Paiva and Roberto Kawakami Harrop Galv˜ ao

508

Comparison of the Cross Deleted Wigner Representation and the Matching Pursuit Distribution (Via Adaptive Signal Decomposition) . . . S. Ghofrani and D.C. McLernnon

516

XVI

Table of Contents

Mean Weight Behavior of Coupled LMS Adaptive Systems Applied to Acoustic Feedback Cancellation in Hearing Aids . . . . . . . . . . . . . . . . . . . . . Yasm´ın Montenegro M. and Jos´e C.M. Bermudez

527

Sound Localization Based on Excitation Source Information for Intelligent Home Service Robots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Keun-Chang Kwak

536

Voicing Detection in Noisy Speech Signal . . . . . . . . . . . . . . . . . . . . . . . . . . . A¨ıcha Bouzid and Noureddine Ellouze

544

Coherent Synchronization of a Chaotic Communication System Based on a QAM-4 Transmitter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Roxana Burghelea, Jean Philippe Mangeot, Fr´ed´eric Launay, Patrick Coirault, and Safwan El Assad Joint Multiple Target Tracking and Classification Using Controlled Based Cheap JPDA-Multiple Model Particle Filter in Cluttered Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Zahir Messaoudi, Abdelaziz Ouldali, and Mourad Oussalah

552

562

Correlation, Independance and Inverse Modeling . . . . . . . . . . . . . . . . . . . . . V. Vigneron

570

A New Approach for Reducing Embedding Noise in Multiple Bit Plane Steganography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Arijit Sur, Piyush Goel, and Jayanta Mukhopadhyay

580

Region-Based Wavelet-Packet Adaptive Algorithm for Sparse Response Identification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Odair A. Noskoski and Jos´e C.M. Bermudez

588

Simulation Method of SAR Raw Echo for Urban Scene . . . . . . . . . . . . . . . Yingxi Zheng, Bo Zhou, Zhulin Zhong, and Ming Lv

596

Underwater Passive Location Technology Using Dummy Time-Reversal Mirror . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Xueli Sheng, Xizhong Bao, Junying Hui, and Guolong Liang

605

Multifractal Analysis on the Sphere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Emilie Koenig and Pierre Chainais

613

Erratum A Novel Text-Independent Speaker Verification System Using Ant Colony Optimization Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Shahla Nemati, Reza Boostani, and Mohammad Davarpanah Jazi

E1

Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

623

Discrete Pulse Transform of Images Roumen Anguelov and Inger Fabris-Rotelli* Department of Mathematics and Applied Mathematics University of Pretoria Pretoria 0002, South Africa [email protected], [email protected]

Abstract. The Discrete Pulse Transform (DPT) of images is defined by using a new class of LULU operators on multidimensional arrays. This transform generalizes the DPT of sequences and replicates its essential properties, e.g. total variation preservation. Furthermore, the discrete pulses in the transform capture the contrast in the original image on the boundary of their supports. Since images are perceived via the contrast between neighbour pixels, the DPT may be a convenient new tool for image analysis. Keywords: LULU, discrete pulse transform, total variation preservation.

1

Introduction

One of the powerful ideas resulting from the theory of the LULU operators for sequences, developed by Carl Rohwer during the last two decades or so, is the Nonlinear Multiresolution Analysis based on a Discrete Pulse Transform (DPT), [8]. A DPT maps a bi-infinite sequence ξ = (..., ξ−1 , ξ0 , ξ1 , ξ2 , ...) onto an infinite vector DP T (ξ) = (D1 (ξ), D2 (ξ), ...) (1) where Dn (ξ) is a sequence consisting of well separated discrete block pulses with support n. In a recent work by the authors the definition of the LULU operators was extended from sequences to multidimensional arrays, namely, functions on Zd , d > 1. This development opened the opportunity of developing the DPT for functions on Zd by using iterative application of the generalized LULU operators, similar to the one-dimensional case. In this paper we consider the DPT of images. Let us denote by A(Z2 ) the set of all functions defined on Z2 which have finite support. A grey scale image is a function f ∈ A(Z2 ) such that the support of f is a finite rectangular subset Ω of Z2 . The DPT of a function f ∈ A(Z2 ) is a vector of the form DP T (f ) = (D1 (f ), D2 (f ), ..., DN (f ))

(2)

which is finite due to the finite support of f . Here N is the number of pixels in γ(n)  the image and Dn (f ) = φns , the functions φns , s = 1, ..., γ(n), being discrete s=1 A. Elmoataz et al. (Eds.): ICISP 2008, LNCS 5099, pp. 1–9, 2008. c Springer-Verlag Berlin Heidelberg 2008 

2

R. Anguelov and I. Fabris-Rotelli

pulses with support of size n, n = 1, ..., N . In this context a discrete pulse is a function φ ∈ A(Z2 ) which is zero everywhere except on a connected set V , where it is constant. The set V is called the support of the pulse φ and we write V = supp(φ). The value of φ on V is shortly called the value of the pulse. If the value of φ is positive then φ is an up-pulse, if it is negative, φ is a down-pulse. Via the DPT we represent a function f ∈ A(Z2 ) as a sum of pulses f=

N  n=1

Dn (f ) =

N γ(n)  

φns ,

(3)

n=1 s=1

where the supports of the pulses are either disjoint or nested. Furthermore, we show that, similar to the DPT of sequences, the decomposition (3) preserves the total variation of f , that is, we have T V (f ) =

N  n=1

T V (Dn (f )) =

N γ(n)  

T V (φns ) .

(4)

n=1 s=1

The total variation is an important characteristic of an image and has been successfully used in noise removal procedures, e.g. [3], [13]. The equalities in (4) show that the decomposition (3) does not create artificial variation, i.e. noise. We should further remark that the pulses in (3) have also a more direct meaning, namely, the contrast in the original image at the boundary of the support of any pulse is at least as much as the value of that pulse.

2

LULU Theory

The LULU operators on multidimensional arrays are defined in [1] by using the morphological concept of connection, [15,16], which characterizes the connected subsets of the domain. The set of connected sets appropriate for images is usually defined via a neighbor relation on the domain. More precisely, a set C ⊆ Z2 is called connected if for any two pixels p, q ∈ C there exists a set of pixels {p1 , p2 , ..., pk } ⊆ C such that each pixel is neighbour to the next one, p is neighbour to p1 and pk is neighbour to q. It was shown in [1] that if the neighbor relation is reflexive, symmetric, shift invariant and includes the pairs of consecutive points both vertically and horizontally, then the collection C of all connected sets on Z2 is a morphological connection suitable for the LULU operators. The neighbour relations typically considered for images, e.g. as in Figure 1, satisfy these basic requirements. Given a point x ∈ Z2 and n ∈ N we denote by Nn (x) the set of all connected sets of size n + 1 which contain a point x, that is, Nn (x) = {V ∈ C : x ∈ V, card(V ) = n + 1} . Then the basic LULU operators are defined as follows.

(5)

Discrete Pulse Transform of Images

j

j

3

j

i

i

i

Fig. 1. Neighbours of the pixel (i, j)

Definition 1. Let f ∈ A(Z2 ) and n ∈ N. Then Ln (f )(x) = Un (f )(x) =

max min f (y), x ∈ Z2 ,

(6)

max f (y), x ∈ Z2 .

(7)

V ∈Nn (x) y∈V

min

V ∈Nn (x) y∈V

The operators in Definition 1 were given in [1] as a generalization of the operators Ln and Un for sequences. However, it should be noted that these are actually the well known morphological operators of area opening and area closing (section 4.4.2, [17]) considered in a new setting, namely, the LULU theory [8,12]. It was shown in [1] that these operators are smoothers and separators (Chapter 1, [8]). Furthermore, they form, under composition, a four element totally ordered semigroup - the so called LULU semi-group [12,11] - and we have L n ≤ Un ◦ L n ≤ L n ◦ U n ≤ U n .

(8)

The smoothing effect of the operators, Ln , Un , on a function f ∈ A(Z2 ) is described in terms of the concepts of local minimum and local maximum sets. Definition 2. Let V ∈ C. A point x ∈ / V is called adjacent to V if V ∪{x} ∈ C. The set of all points adjacent to V is denoted by adj(V ). Definition 3. A connected subset V of Z2 is called a local maximum set of f ∈ A(Z d ) if max f (y) < min f (x) . y∈adj(V )

x∈V

Similarly V is a local minimum set if min f (y) > max f (x) .

y∈adj(V )

x∈V

Then the action of Ln and Un on f ∈ A(Z2 ) can be described in terms of the following properties, [1]: A1 The application of Ln (Un ) removes local maximum (minimum) sets of size smaller or equal to n.

4

R. Anguelov and I. Fabris-Rotelli

A2 The operator Ln (Un ) does not affect the local minimum (maximum) sets directly in the sense that such sets may be affected only as a result of the removal of local maximum (minimum) sets. However, no new local minimum sets are created where there were none. This does not exclude the possibility that the action of Ln (Un ) may enlarge existing local maximum (minimum) sets or join two or more local maximum (minimum) sets of f into one local maximum (minimum) set of Ln (f ) (Un (f )). A3 Ln (f ) = f (Un (f ) = f ) if and only if f does not have local maximum (minimum) sets of size n or less. In analogy with the respective concept for sequences we introduce the concept of n-monotonicity for functions in A(Z2 ). Definition 4. Function f ∈ A(Z2 ) is called (locally) n-monotone if the size of all local minimum or local maximum sets of f is larger then n. It follows from A1–A3 that for every f ∈ A(Z2 )

3

(Ln ◦ Un )(f ) is n-monotone

(9)

(Un ◦ Ln )(f ) is n-monotone

(10)

(Ln ◦ Un )(f ) = (Un ◦ Ln )(f ) = f ⇐⇒ f is n-monotone

(11)

Discrete Pulse Transform

The Discrete Pulse Transform (2) for a function f ∈ A(Z2 ) is obtained via iterative application of the operators Ln , Un with n increasing from 1 to N . For a given n, the sequencing of Ln and Un does not affect the properties of (2) stated in the Introduction. However, it introduces bias towards up-pulses or down-pulses. This issue will be given particular attention later. For now let Pn denote either the composition Ln ◦ Un or the composition Un ◦ Ln and let Qn = Pn ◦ Pn−1 ◦ ... ◦ P2 ◦ P1 . In the general theory of Mathematical Morphology, Qn is known as an alternating sequential filter (see Section 8.3 [17]). However, here are interested in the portions of the image which are filtered out by the application of Pn , n = 1, 2, ..., N . Indeed, we ultimately obtain QN (f ), which is a constant function containing no information about the original image except possibly the general level of illumination. The rest of the information carried by f is in the layers peeled off. More precisely, we have f = (id − P1 )(f ) + ((id − P2 ) ◦ Q1 )(f ) + ((id − P3 ) ◦ Q2 )(f ) + ... +((id − PN −1 ) ◦ QN −2 )(f ) + ((id − PN ) ◦ QN −1 )(f ) + QN (f ) , (12) where id denotes the identity operator. Let us note that a similar iterative application of area opening and area closing operators is used by Acton and Mukherjee for image classification. In [2], filtering is for selected values of n and instead of the layers of peeled off portions the authors keep record of filtered images at every scale (this would be Qn (f ) in the notation adopted here). While the approach

Discrete Pulse Transform of Images

5

in [2] is adequate for the classification methods derived there, the decomposition (12) contains much more information. It is also easy to apply, not least, due to the fact that it gives a representation of f in terms of discrete pulses. Indeed, we show next that (12) is a DPT decomposition of the form (3) by proving that each term is a sum of pulses of certain size. This result is obtained in the next two theorems. Theorem 1. Let f ∈ A(Z2 ) be (n − 1)-monotone. Then a) b) c) d)

(id − Ln )(f ) is a sum (id − Un )(f ) is a sum (id − Un ◦ Ln )(f ) is a (id − Ln ◦ Un )(f ) is a

of disjoint up-pulses of size n; of disjoint down-pulses of size n; sum of disjoint pulses of size n; sum of disjoint pulses of size n.

Proof. a) Consider x ∈ Z2 such that (id − Ln )(f )(x) > 0. By property A1 there exists a local maximum set V of f such that x ∈ V and card(V ) ≤ n. Since f is (n − 1)-monotone it does not have local maximum sets of size smaller then n. Therefore card(V ) = n and f is constant on V . Moreover, we have (id − Ln )(f )(y) = 0, y ∈ adj(V ). Indeed, if (id − Ln )(f )(y) > 0 for some y ∈ adj(V ) then y belongs to a local maximum set W of f and card(W ) ≤ n. However, any local maximum set containing y must contain V as well. Thus, card(W ) ≥ n + 1. This is a contradiction. So we have that the support of (id − Ln )(f ) is a union of disjoint connected sets of size n, i.e.   supp (id − Ln )(f ) = V1 ∪ V2 ∪ ... ∪ Vρ(n) , where Vs ∈ C and card(Vs ) = n for s = 1, 2, ..., ρ(n) and Vs1 ∩Vs2 = ∅ for s1 = s2 . Let (id − Ln )(f )(x) = αs for x ∈ Vs . Then 

ρ(n)

(id − Ln )(f ) =

φns ,

s=1

where φns is pulse with support Vs and value αs . The proof of b) is similar. The proof of c) follows from a) and b) by using that id − Ln ◦ Un = id − Ln + (id − Un ) ◦ Ln . Similar argument holds for d). Theorem 2. Let the operators Pn and Qn be as in (12). Then for every n = 1, ..., N we have that Dn (f ) = ((id − Pn ) ◦ Qn−1 )(f ) is a sum of pulses of the form γ(n)  Dn (f ) = φns , s=1

where card(supp(φns )) = n and supp(φns1 ) ∩ supp(φns2 ) = ∅ for s1 = s2 . Moreover, the supports of all pulses φns , s = 1, ..., γ(n), n = 1, ..., N are either disjoint or nested, that is, (supp(φn1 s1 ) ∩ supp(φn2 s2 ) = ∅, n1 ≤ n2 ) =⇒ supp(φn1 s1 ) ⊆ supp(φn2 s2 ) . (13)

6

R. Anguelov and I. Fabris-Rotelli

Proof. Let n ∈ {2, ..., N }. The function Qn−1 (f ) = Pn−1 (Qn−2 (f )) is (n − 1)monotone due to (9)–(10). Then it follows from Theorem 1 that (id−Pn )(Qn−1 (f ) is a sum of pulses of size n. For n = 1 the function f is trivially 1-monotone and hence (id − P1 )(f ) is a sum of pulses of size 1. Note that here we may have Pn = Un ◦ Ln and obtain the result by item c) in Theorem 1, or use item d) if Pn = Ln ◦ Un . Due to (9)–(10) the sequencing of Lk and Uk in the operator Pk for k < n also does not matter. Hence it remains to prove (13). Let supp(φn1 s1 ) ∩ supp(φn2 s2 ) = ∅. It follows from the construction of the pulses in the proof of Theorem 1 that the functions Qn (f ) and Pn+1 (Qn (f )), n ≥ n1 , are constants on the set supp(φn1 s1 ). Furthermore, the set supp(φn2 s2 ) is a local maximum set or a local minimum set of either Qn2 −1 (f ) or Pn2 (Qn2 −1 (f )). Then by the definition of local maximum and local minimum sets it follows that supp(φn1 s1 ) ⊂ supp(φn2 s2 ). As mentioned earlier the sequencing of the operators Ln and Un in Pn results in bias towards up-pulses or down-pulses. The operator Fn , called a floor operator given by Fn = Pn ◦ Pn−1 ◦ ... ◦ P2 ◦ P1 where Pn = Un ◦ Ln , is biased towards uppulse. This means that for any particular size the up-pulses are extracted before the down pulses. Similarly the operator Cn , called a ceiling operator given by Cn = Pn ◦ Pn−1 ◦ ... ◦ P2 ◦ P1 where Pn = Ln ◦ Un , is biased towards down-pulses. A DPT using Fn will generally have more up-pulses and fewer down-pulses compared to DPT using Cn . It is important to realize that the bias extremes will differ for different original images due to their size and contrast so interpretation should be relative to the current image. The alternating bias separators Zn+ and Zn− (see [4] and references therein) are given by:  Ln+1 Un+1 Zn− if n is even − Zn+1 = Un+1 Ln+1 Zn− if n is odd  Ln+1 Un+1 Zn+ if n is odd + Zn+1 = Un+1 Ln+1 Zn+ if n is even Using the order in the LULU semi-group (8) it is easy to see that Fn ≤ Zn± ≤ Cn . We should note that if f ∈ A(Z2 ) is such that Fn = Cn , n = 1, ..., N , then f has a unique DPT decomposition of the form (12). Finally we discuss the total variation preservation property (4). There are several different concepts used for total variation of a function of multidimensional argument in literature. For a function f ∈ A(Z2 ) we define the total variation as T V (f ) =

∞ 

∞ 

(|f (i + 1, j) − f (i, j)| + |f (i, j + 1) − f (i, j)|) .

(14)

i=−∞ j=−∞

It was proved in [1] that the operators Ln and Un are total variation preserving. Furthermore, the composition of total variation preserving operators is also total variation preserving. Therefore the decomposition (3) obtained via (12) preserves the total variation, i.e. (4) holds.

Discrete Pulse Transform of Images

7

Table 1. Bias Percentages (×10−3 ) between Fn , Cn , Zn+ and Zn−

Cn Fn Zn+ Zn−

Cn Fn Zn+ Zn− 0 0.2609 0.2269 0.0340 0.2609 0 0.0340 0.2269 0.2269 0.0340 0 0.2610 0.0340 0.2269 0.2610 0

The decomposition of the original image can be done using Fn , Cn , Zn+ or Zn− . While it is possible that these lead to different results it is seldom significantly observable in practice. For example, the percentage bias between the operators, when applied to the image (a) in Figure 2, is given in Table 1.

4 4.1

Illustrative Examples A Partial Reconstruction

Consider image (a) in Figure 2. We wish to extract the boat as a feature and remove the background water. We consider any feature not part of the boat as

(a)

(b)

(c)

(d)

Fig. 2. (a) Original image; (b) Pulses of size up to 80; (c) Pulses of size from 81 to 4000; (d) Pulses of size larger than 4000

8

R. Anguelov and I. Fabris-Rotelli

noise. The images (b) - (d) in Figure 2 are partial reconstructions, see [1], of the original. We can consider (b) as the microfeatures e.g. noise, (c) as the mediumsized features and (d) as the large features. We see that pulses of size up to 80 represent the water, pulses from 81 to 4000 the boat and pulses larger than 4000 represent larger noise patterns. 4.2

Identifying Pulses of Interest

In Figure 3 the pulses of size 100 to 300 with relative luminosity greater than 1 represent the solar glint on the waves (see image (b) in Figure 3) and they are emphasized in image (c) by giving them all black borders. So we are able to extract the small solar glint patches from the image and can subsequently reconstruct the image without them. The pulses of size 1501 to 2500 are the pulses corresponding to the boat (as seen in image (d) of Figure 3).

(a)

(b)

(c)

(d)

Fig. 3. (a) Original image; (b) Pulses of size 100 to 300 with relative luminosity greater than 1; (c) Borders of the pulses of size 100 to 300 with relative luminosity greater than 1 superimposed on the original image; (d) Pulses of size larger than 1501 to 2500

Discrete Pulse Transform of Images

9

References 1. Anguelov, R., Plaskitt, I.: A Class of LULU Operators on Multi-Dimensional Arrays, Technical Report UPWT2007/22, University of Pretoria (2008), http://arxiv.org/abs/0712.2923 2. Acton, S.T., Mukherjee, D.P.: Scale Space Classification Using Area Morphology. IEEE TRansactions on Image Processing 9(4) (2000) 3. Chambolle, A., Lions, P.-L.: Image recovery via total variation minimization and related problems. Numerische Mathematik 76, 167–188 (1997) 4. du Toit, J.P.: The Discrete Pulse Transform and Applications, Masters Thesis, Univeristy of Stellenbosch (2007) 5. Epp, S.S.: Discrete Mathematics with Applications. International Thomson Publishing (1995) 6. Laurie, D.P., Rohwer, C.H.: The discrete pulse transform. SIAM J. Math. Anal. 38(3) (2007) 7. Matheron, G.: Filters and lattices, in Image Analysis and Mathematical Morphology. In: Serra, J. (ed.) Theoretical Advances, ch. 6, vol. II, pp. 115–140. Academic Press, London (1988) 8. Rohwer, C.H.: Nonlinear Smoothing and Multiresolution Analysis, Birkh¨ auser (2000) 9. Rohwer, C.H.: Variation reduction and LULU-smoothing. Quaestiones Mathematicae 25, 163–176 (2002) 10. Rohwer, C.H.: Fully trend preserving operators. Quaestiones Mathematicae 27, 217–230 (2004) 11. Rohwer, C.H., Wild, M.: Natural Alternatives for One Dimensional Median Filtering. Quaestiones Mathematicae 25, 135–162 (2002) 12. Rohwer, C.H., Wild, M.: LU LU Theory, Idempotent Stack Filters, and the Mathematics of Vision of Marr. Advances in imaging and electron physics 146, 57–162 (2007) 13. Rudin, L.I., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60, 259–268 (1992) 14. Serra, J.: Image Analysis and Mathematical Morphology. Academic Press, London (1982) 15. Serra, J.: Image Analysis and Mathematical Morphology. In: Serra, J. (ed.) Theoretical Advances, vol. II. Academic Press, London (1988) 16. Serra, J.: A lattice approach to image segmentation. Journal of Mathematical Imaging and Vision 24, 83–130 (2006) 17. Soille, P.: Morphological Image Analysis. Springer, Heidelberg (1999)

Constrained Unsharp Masking for Image Enhancement Radu Ciprian Bilcu and Markku Vehvilainen Nokia Research Center, Visiokatu 1, 33720, Tampere, Finland [email protected], [email protected] http://research.nokia.com/~bilcu

Abstract. In this paper we present a cost-effective solution for combined de-noising and sharpening of digital images. Our method combines the unsharp masking and sigma filtering techniques through a regularization mechanism thus ensuring effective noise reduction and edge enhancement in the processed image. We describe our method in detail and we analyze the proposed implementation through extensive experiments done in various scenarios. Due to its low computational complexity the proposed method is well suited for mobile implementations. Keywords: Image sharpening, de-noising, unsharp masking.

1

Introduction

Digital photography has gained an increased interest, in the mobile devices industry, during the last decade. It is a common fact nowadays that mobile devices, such as mobile phones and PDA’s, are equipped with digital cameras able to capture images and video clips. Due to their specific hardware limitations the quality of the captured images are not yet at the level of the SLR (single-lens reflex) cameras. The resolution of the imaging sensors, used in the cameraphones increases, but the total sensor size is limited, which decreases the active area of a sensor pixel. As a consequence, the captured images have a lower signal to noise ratio. Miniaturization and cost limitations enforce the use of lower quality optical systems in the cameraphones compared with the ones used in the SLR cameras. This very often introduces blur in the captured images and video clips. The low signal to noise ratio and the optical blur are probably the most important distortions that must be corrected by an imaging chain designed to be implemented in cameraphones. A very large amount of research has been done in the field of image de-noising and sharpening in order to address these two important problems and various solutions have been proposed in the open literature. Mobile devices possess a very limited processing power and contain several applications that must run in parallel which decreases even more the resources allocated for image processing tasks. As a consequence, there is a large interest in the development of low complexity image processing solutions suitable for mobile implementations. A. Elmoataz et al. (Eds.): ICISP 2008, LNCS 5099, pp. 10–19, 2008. c Springer-Verlag Berlin Heidelberg 2008 

Constrained Unsharp Masking for Image Enhancement

11

In this paper we propose a cost effective solution to the problem of combined de-noising and sharpening of digital images. Our proposed method combines the sigma filtering and unsharp masking (USM), through a simple regularization step, to accomplish both noise reduction and edge enhancement. The reason why we have selected these two techniques is due to their relatively good performances obtained at a very low computational cost. The paper is organized as follows: in Section 2 several related existing sharpening methods are briefly reviewed. In Section 3 we introduce our proposed approach and we illustrate its functionality through simple experiments done on synthetic images. In Section 4 we show the results of our method obtained for real images and Section 5 concludes the paper.

2

Existing Approaches

The problem of image sharpening has been extensively studied and many approaches have been proposed in the open literature. Bilateral filter have been used in [13] to implement a combined method for sharpening and de-noising. The novelty of this method consists in the introduction of an offset term in the range filter part of the bilateral filter. This offset is adapted to the local characteristics of the input image such that the behavior of the algorithm changes from smoothing to edge enhancement according to the local characteristics of the image. Although its good performances, this algorithm needs some optimization of the parameters which is done by training on a set of images. Image sharpening has been implemented also by means of fuzzy networks [10], using methods modeling the human visual system [6], by non-linear filtering in transform domain [7] or using diffusion filtering [3], to mention a few. Although their good performance, the above mentioned approaches have some characteristics that makes them to be quite difficult to be implemented in low power devices. For instance the method in [10] make use of 2 fuzzy networks connected in parallel and have longer processing time compared with other approaches. The nonlinear methods from [6] and [7], despite their excellent performance, have also relatively large computational complexity. The coupled shock-diffusion filtering method from [3] is expected to have also a long processing time since it is an iterative process. Despite its simplicity, the unsharp masking technique [9] provides relatively good performance in enhancing the image sharpness thus representing a good alternative for practical implementations. In the unsharp masking technique the high frequency content of the input image is emphasized as depicted in Fig. 7. According to this figure the input image is filtered by a high-pass filter (the dotted block denoted as HPF). The high-pass filtered image IH (i, j) is then multiplied by a constant parameter λ and added to the input image. There are several possibilities to implement the HPF filter. We should mention here that Fig. 7 suggests to implement the HPF filtering as the difference between the input image and its smoothed version (the output of the low-pass filter LPF). Equally well this operation can be implemented by a single high-pass convolution kernel [9]. Despite its simplicity and good performance, in many applications, the unsharp masking technique has two main drawbacks. First of all the noise present

12

R.C. Bilcu and M. Vehvilainen

in the input image is amplified due to the presence of the high-pass filter. While this might not be visually disturbing in image regions with high activity (large number of edges), on smooth image areas noise amplification can give unpleasant visual distortions. Another disadvantage of the unsharp masking technique is the presence of the overshooting artifacts. This is due to a too large amplification of the high contrast areas. Among several solutions, proposed to eliminate or at least reduce these two disadvantages, the adaptive unsharp masking shown to be very effective [9]. The main idea of this method is to use a variable parameter λ which is adaptive to the image local contrast. In this manner the regions with medium contrast are enhanced more while the smooth regions and those with high contrast are less enhanced. However, in [9], modification of λ is done by means of an adaptive filter which implies matrix inversion and increased number of parameters to setup. Another way to reduce the overshooting in the unsharp masking is to introduce clipping of the overshoots to the nearest local extremes [11], [8]. Some of the techniques that integrates clipping necessitate edge detection in order to be able to locate the position of the overshoots. In this paper we show that clipping not only the edge pixels, but every pixels from the image, one could obtain both de-noising and edge sharpening. We propose a modified processing scheme that combines sigma smoothing, unsharp masking and clipping to reach our goals.

3

Proposed Approach

In this section we describe our proposed method for combined de-noising and sharpening. In order to introduce our method we start from the block diagram Binary test image

One line of the input image

Result of USM and clipping

Result of USM

240

240

240

220

220

220

200

200

200

180

180

180

160

160

160

140

140

140

120

120

120

100

100

100

80

80

60 0

10

20

30

40

50

60

80

60 0

10

20

30

40

50

60

60 0

10

20

30

40

50

60

Fig. 1. Test image Fig. 2. One line from Fig. 3. Enhanced by Fig. 4. Result after test image clipping USM

One line of the input noisy image

Result of USM

350

350

300

300

250

250

200

200

150

150

100

100

50 0 0

50

10

20

30

40

50

60

Fig. 5. One noisy line from test image

0 0

10

20

30

40

50

60

Fig. 6. Enhanced by USM

Constrained Unsharp Masking for Image Enhancement

13

Fig. 7. Block diagram of the unsharp Fig. 8. Block diagram of the cascaded demasking noising and sharpening with clipping

Fig. 9. Block diagram of the in- Fig. 10. Block diagram of integrated de-noising tegrated de-noising and sharpening and sharpening with clipping without clipping

of the USM depicted in Fig. 7. Due to the presence of the high-pass filter (HPF) the processed image IO (i, j) might contain overshooting distortions around sharp edges. This effect is illustrated in Fig. 2 and Fig. 3. In Fig. 2 one line from the binary image of Fig. 1 is shown and in Fig. 3 the result of USM is depicted. These overshooting distortions can be eliminated by clipping them to the extreme values from their neighborhood as shown in Fig. 4. Now lets look to the case of noisy input images. To this end in Fig. 5 the same line of the binary image, with added zero mean Gaussian noise, is shown. In Fig. 6 we show the enhanced output using USM. One can notice, from this figure, the overshooting and noise amplification effects. Analyzing the plots from Fig. 5 and Fig. 6, we can observe that clipping would not be very effective in the noisy case. Indeed, the local extremes around overshoots are affected by the input noise and clipping them using the noisy local extremes could introduce artifacts. From this observation we can conclude that clipping would be more effective if it is made according to a noise-free version of the input image instead of the original noisy one. As a consequence we modify the block diagram of the USM with clipping as shown in Fig. 10. Moreover instead of clipping only edge pixels we perform clipping for all image pixels. Clipping is done according to the smoothed image IF (i, j). In this manner in smooth areas the noise level from the processed image is limited to the level of the remaining noise in IF (i, j). As a consequence, the noise in the output image will be at most equal with the noise level from IF (i, j) and the edges of IO (i, j) will be enhanced without overshooting.

14

R.C. Bilcu and M. Vehvilainen Original image

Input image

Combined den. sharrp. and clipp.

Combined den. sharp. no clipp.

USM

Cascaded den. sharp. and clipp.

Fig. 11. From left to right and up to bottom (part of the images): Original image, noisy blurred input image, the result of the implementation from Fig. 10, the result of the implementation from Fig. 9, the result of USM (Fig. 7), the result of the implementation from Fig. 8

According to Fig. 10, the flow of our proposed algorithm is as follows: 1. Compute the image IF (i, j) by smoothing the input image I(i, j). The smoothing process should retain as many image details as possible while reducing the input noise. Due to its simple implementation we have selected for this step the sigma filtering method [4]. Other more complex image de-noising methods can be implemented as well if there is enough computational power available (see for instance [1] and the references therein). 2. Compute the image IH (i, j) by high-pass filtering of the input image I(i, j). This can be done by convolving I(i, j) with a high pass kernel g(k, l). IH (i, j) = (I ⊗ g) (i, j)

(1)

Another alternative to obtain IH (i, j) is to compute it as the difference between the original image I(i, j) and its low-pass version IL (i, j) as follows: IH (i, j) = I(i, j) − IL (i, j), IL (i, j) = (I ⊗ h) (i, j). with h(i, j) being a low pass filtering kernel.

(2)

Constrained Unsharp Masking for Image Enhancement Input image

Combined den. sharp. and clipp.

USM

Cascaded den. sharp. and clipp.

15

Fig. 12. From left to right and up to bottom (part of the images): original image captured by a cameraphone, the result of the implementation from Fig. 10, the result of USM (Fig. 7), the result of the method shown in Fig. 8

3. Add the enhanced high-pass image IH (i, j) to the de-noised image IF (i, j): IS (i, j) = If (i, j) + λIH (, j).

(3)

where λ is a constant parameter controlling the strength of sharpening. 4. Clipping the enhanced image IS (i, j) according to the local extremes from IF (i, j): ⎧ ⎨ IS (i, j) if IS (i, j) ∈ [M IN, M AX] , IO (i, j) = M IN if IS (i, j) < M IN, ⎩ M AX if IS (i, j) > M AX.

(4)

16

R.C. Bilcu and M. Vehvilainen Input image

Result proposed

Input image

Result proposed

Fig. 13. Original image captured by a cameraphone (left column) and the result of the implementation from Fig. 10 (right column)

The M IN and M AX values are obtained from a T × T rectangular window ΩT ×T centered at position i, j in IF (i, j). Another alternative implementation is depicted in Fig. 8. However there are differences between the method illustrated in Fig. 10 and the method depicted in Fig. 8. In the first method the high-pass filtered image IH (i, j) is computed from the input image while in Fig. 8 it is computed from the de-noised image IF (i, j). De-noising will smooth also some details of the image such that cascading denoising and USM as in Fig. 8 those details might not be enough enhanced. On the contrary, the details that would be smoothed in the de-noising process are still enhanced in Fig. 10 due to the fact that IH (i, j) is obtained from the original image. Since the output IO (i, j) is obtained by adding the enhanced high frequency content to the de-noised image IF (i, j), in both methods, some under enhancement of small details can be expected. However, in implementation shown in Fig. 10 this effect is somehow reduced due to the fact that IH (i, j) is computed from the input image. Anyway, both implementations have the same computational complexity and they perform similar in most of the cases.

Constrained Unsharp Masking for Image Enhancement

Input image

Result proposed

Input image

Result proposed

17

Fig. 14. Original image captured by a cameraphone (left column) and the result of the implementation from Fig. 10 (right column)

4

Experiments and Results

In this section we present experimental results showing the performance of our proposed approach on gray scale and color digital images. We have performed extensive experiments to verify the behavior of our new method on several well known test images as well as on images captured with cameraphones and dedicated digital cameras. The image data-base, which we have used in our experiments, contains more than 80 gray scale and color images captured with different imaging devices. In the first set of experiments, presented here, the 8 bit image Lena was first 2 blurred using a Gaussian kernel with σG = 1 and then a zero mean Gaussian 2 distributed noise with variance σn = 25 was added to it. In Fig. 11 the processed images by the methods described in Fig. 7, Fig. 8, Fig. 9 and Fig. 10 are shown. We can see that both implementations from Fig. 8 and Fig. 10 enhance the image sharpness without increasing the noise level. This is due to the clipping mechanism that is applied to all image pixels. As expected, the USM method and the implementation from Fig. 9 suffers from noise amplification and overshooting.

18

R.C. Bilcu and M. Vehvilainen

Input image

Result proposed

Input image

Result proposed

Fig. 15. Original image captured by a cameraphone (left column) and the result of the implementation from Fig. 10 (right column)

In the second set of experiments, several 8 bit digital color images, captured by different cameraphones and dedicated digital cameras, have been processed by the same enhancement methods and the results are shown in Fig. 12, Fig. 13, Fig. 14 and Fig. 15. Again we can see that our proposed methods ensure more pleasant visual results with enhanced edges, reduced noise and no overshoots also for digital color images. The sigma filter, used in our approach, necessitates the knowledge of the noise variance. In our implementation we have used the method from [2] to estimate the noise variance.

5

Conclusions

In this paper we have introduced a noise reduction and sharpening method suitable for mobile implementations. In our method we combined the sigma de-noising and the unsharp masking techniques through a simple clipping mechanism. We have seen that if clipping is done for all image pixels and not only for over enhanced edges the noise level in the processed image can be reduced

Constrained Unsharp Masking for Image Enhancement

19

together with increasing the edge sharpness. The proposed method can be combined with other existing approaches that adaptively adjusts the strength of sharpening based on the local image activity. Further developments in this direction as well as better clipping alternatives are currently under consideration and the results will be published elsewhere.

References 1. Bilcu, R.C., Vehvilainen, M.: A Novel Decomposition Scheme for Image De-noising. In: IEEE Int. Conf. on Ac. Speech and Sig. Proc., pp. 577–580 (2007) 2. Bilcu, R. C., Vehvilainen, M.: A New Method for Noise Estimation in Images. IEEE Int. Work. on Nonlin. Sig. and Im. Proc. (2005) 3. Fu, S., Ruan, Q., Wang, W.: A Coupled Shock-Diffusion Filter for Image Enhancement. In: IEEE Int. Conf. on Sig. Proc., pp. 16–20 (2006) 4. Lee, J.S.: Digital Image Smoothing and the Sigma Filter. Comp. Graph. Im. Proc. 24, 255–269 (1983) 5. Lukac, R., Plataniotis, K.: N.: Cost-Effective Sharpening of Single-Sensor Camera Images. In: IEEE Int. Conf. on Multimedia and Expo., pp. 829–832 (2006) 6. Matz, S.C., Figueiredo, R.J.P.: A Nonlinear Image Contrast Sharpening Approach Based on Munsell’s Scale. IEEE Trans. on Im. Proc. 15(4), 900–909 (2006) 7. Mitra, K.S., Yu, T.-H.: Nonlinear Filters for Image Sharpening and Smoothing. IEEE Int. Conf. on Syst. Eng, 241–244 (1991) 8. Ojo, O., Kwaaitaal-Spassova, A., An Algorithm, T.G.: for Integrated Noise Reduction and Sharpness Enhancement. IEEE Trans. on Cons. El. 46(3), 474–480 (2000) 9. Polesel, A., Ramponi, G., Mathews, V.G.: Image Enhancement via Adaptive Unsharp Masking. IEEE Trans. on Im. Proc. 9(3), 505–510 (2000) 10. Russo, F.: An Image Enhancement Technique Combining Sharpening and Noise Reduction. IEEE Trans. on Instr. and Measur. 51(4), 824–828 (2002) 11. Rieder, P., Scheffer, G.: New Concepts on Denoising and Sharpening of Video Signals. IEEE Trans. on Cons. El. 47(3), 666–671 (2001) 12. Vehvilainen, M., Yrjanainen, J.: Circuit Arrangement to Accentuate the Sharpness and Attenuate the Noise of a Television Image. European Patent EP95101009 (1994) 13. Zhang, B., Allebach, J.: P.: Adaptive Bilateral Filter for Sharpness Enhancement and Noise Removal. In: IEEE Int. Conf. on Im. Proc., pp. VI417–VI420 (2007) 14. Wang, Q., Ward, R., Zou, J.: Contrast Enhancement for Enlarged Images Based on Edge Sharpening. IEEE Int. on Im. Proc. (2005)

Discrete Wavelet Diffusion for Image Denoising Kashif Rajpoot1, Nasir Rajpoot2, and J. Alison Noble1 1

Department of Engineering Science, University of Oxford, UK Department of Computer Science, University of Warwick, UK {kashif, noble}@robots.ox.ac.uk, [email protected] 2

Abstract. Nonlinear diffusion, proposed by Perona-Malik, is a well-known method for image denoising with edge preserving characteristics. Recently, nonlinear diffusion has been shown to be equivalent to iterative wavelet shrinkage, but only for (1) Mallat-Zhong dyadic wavelet transform and (2) Haar wavelet transform. In this paper, we generalize the equivalence of nonlinear diffusion to non-linear shrinkage in the standard discrete wavelet transform (DWT) domain. Two of the major advantages of the standard DWT are its simplicity (as compared to 1) and its potential to benefit from a greater range of orthogonal and biorthogonal filters (as compared to both 1 and 2). We also extend the wavelet diffusion implementation to multiscale. The qualitative and quantitative results shown for a variety of images contaminated with noise demonstrate the promise of the proposed standard wavelet diffusion.

1 Introduction A common problem with image or video signals is the contamination with undesired noise. This poses problems both for visual quality and automated analysis. Many automated analysis operations (e.g., segmentation, edge detection) are highly sensitive to the noise. It is often desirable to remove or suppress the noise by means of a preprocessing operation. Many denoising methods consider noise as either highfrequency content or outlier, potentially confusing the edges with noise and smoothing them during the process of noise removal. Edges are important features containing structural information that should be preserved. Nonlinear diffusion, initially proposed by Perona-Malik [1], is a popular iterative method for noise removal that attempts to perform edge-preserving smoothing. During the last decade or so, the discrete wavelet transform (DWT) has also been shown [2] to be a highly successful way of signal denoising, as it effectively separates signal and noise in the wavelet domain. The DWT based denoising, termed also as wavelet shrinkage, works by thresholding (often, nonlinearly) the wavelet coefficients before reconstructing the denoised signal from wavelet decomposition coefficients. One of the problems with wavelet shrinkage is that it results in valleys around edges (termed as ringing artifacts) which can be reduced by cycle spinning [3], at the cost of increased computational and storage complexity. Recently, it was shown [4, 5] that a single step of nonlinear diffusion can be considered equivalent to a single shrinkage iteration of coefficients of Mallat-Zhong dyadic wavelet transform (MZ-DWT) [6]. In other words, it is possible to perform the A. Elmoataz et al. (Eds.): ICISP 2008, LNCS 5099, pp. 20–28, 2008. © Springer-Verlag Berlin Heidelberg 2008

Discrete Wavelet Diffusion for Image Denoising

21

diffusion in the wavelet domain such that the benefits of both the techniques could be combined. Nonlinear diffusion begins with an edge estimate, typically obtained through a gradient operator, which may be badly influenced by the noise present in the image. It is believed that the edge estimate in the wavelet domain is much less sensitive to noise due to its characteristics of better low- and high-frequency separation. However, MZ-DWT is an uncommon variant of standard DWT and is not commonly utilized. It has its own subband filtering framework and a set of wavelet filters, which are usually derived from the derivative of a smoothing function (e.g., cubic spline). Moreover, MZ-DWT may not be able to benefit from the great variety of orthogonal and biorthogonal wavelet filters. In another work, the diffusivity function of nonlinear diffusion is shown [7] to have equivalence with Haar wavelet shrinkage. Again, the work is restricted only to the use of Haar wavelet filter. In this paper, we combine the power of nonlinear diffusion and wavelet shrinkage and generalize their equivalence by establishing a relationship between the standard DWT and nonlinear diffusion. The generalization enables one to perform diffusion filtering utilizing the wavelet coefficients obtained from standard DWT, which is simple and commonly used in image processing research. Thus, one can take advantages of both popular denoising methods – wavelets and nonlinear diffusion – in a single wavelet diffusion framework. We hope that this work will make the wavelet diffusion more widely usable while offering the use of a range of wavelet filters. This paper is organized as follows: next section establishes the relationship between DWT and nonlinear diffusion after briefly introducing them. Section 3 provides experimental details and presents some qualitative and quantitative results. The paper finishes with a brief discussion of results, conclusions and future directions.

2 Discrete Wavelet Diffusion We present a brief overview of Perona-Malik nonlinear diffusion and DWT and later show the equivalence between the two frequently used denoising techniques. 2.1 Nonlinear Diffusion The nonlinear diffusion filtering operation is governed by the following nonlinear partial differential equation (PDE): ,

,

.

,

(1)

where , is the initial noisy image at time and the solution of the above PDE iteratively yields a filtered version which can be considered as the denoised image. In the above, , is the diffusion coefficient controlling the diffusion amount and is typically described by a diffusivity function of the form: ,

|

,

1

| 1

|

,

|

(2)

22

K. Rajpoot, N. Rajpoot, and J.A. Noble

where | , | is the edge estimate at pixel , , usually approximated by a gradientmagnitude operator, and is the edge threshold parameter. The diffusivity function | | is a nonnegative monotonically decreasing function and, depending upon the value of the edge threshold , encourages homogenous regions with reduced noise while preserving the edges. The nonlinear diffusion PDE of (1) can be expanded to: ,

,

.

,

,

.

,

(3)

substituting the time-derivative of , by its forward difference and discretizing: , , ∆ , . , , . , ∆ Let Δ 1 and replacing , , as defined in (2) above, with 1 , , we obtain: 2 1

,

,

2

,

2

2

, (4)

,

.

,

,

.

,

Usually, , is initialized by , , , where , is the original noisy image. The solution to the above equation yields a denoised image after a certain number of iterations. 2.2 Discrete Wavelet Transform (DWT) Wavelets offer a simple and elegant framework for simultaneous time-frequency and multiresolution analysis. In wavelet analysis, a function is decomposed into a superposition of dilated and scaled versions of a mother wavelet basis function. The decomposition highlights interesting features in the wavelet domain which are often not visible in the spatial domain. In DWT, an image is filtered into four subbands at each resolution and the low frequency subband is further filtered through an iterative process to provide the multiresolution representation. Here, we give an overview of the fast implementation of the discrete wavelet transform (DWT) [8]. The forward wavelet transform (FDWT) operation (termed also as decomposition or analysis) is given by: , , , ,

, , , ,

(5)

where , is the given image, denotes the convolution operation, and and are one-dimensional low-pass and high-pass decomposition filters, respectively. The image is decomposed into four subbands; denotes the low-frequency approximation subband and , , , denotes the high-frequency subband at scale and being one of the horizontal ( ), vertical ( ), or diagonal ( ) orientations.

Discrete Wavelet Diffusion for Image Denoising

23

The original image can be reconstructed through the inverse wavelet transform (IDWT) operation (termed also as reconstruction or synthesis): ,

,

, ,

(6)

,

where and are the one-dimensional low-pass and high-pass reconstruction filters and derived as conjugate or dual of the decomposition filters and depending upon whether the filters are orthogonal or biorthogonal, respectively. Assuming that the original image , is part of the scale-space such that the wavelet coefficients can be manipulated after decomposition, the original image and the reconstructed image can be considered as , and , , respectively. Using this convention and writing the analysis and synthesis operations in joint form: ,

,

,

,

, , ,

, , ,

, , ,

(7)

where , , is the separable convolution of , with . Transforming the above equation into Fourier domain, we get: ,

,

,

,

.

.

,

.

,

,

.

,

.

,

,

.

,

.

,

,

.

,

.

,

,

.

,

.

,

,

.

,

.

.

(8)

, ,

.

It is obvious from (9) that the perfect reconstruction (i.e., guaranteed through inverse wavelet transform if, .

and

.

1

,

,

(9)

,

) is (10)

which is usually the case for conventionally used orthogonal and biorthogonal filters (e.g., Haar, Daubechies, and Coiflet). 2.3 Wavelet Diffusion In this section, we show that the standard discrete wavelet transform can be considered as having the same form as a single discrete step (4) of nonlinear diffusion. Equation (4) can be transformed into Fourier domain: , , , , 1 ̂ , , (11) 2 1 ̂ , , 2

24

K. Rajpoot, N. Rajpoot, and J.A. Noble

substituting 1 ̂

and 1

.

,

,

,

,

,

,

̂ , we obtain:

,

2.

1.

.

,

.

̂

.

̂

. .

,

(12)

,

̂

.

,

Taking the inverse Fourier transform of the above equation: 1

,

,

1

, ,

,

2

.

,

.

,

.

,

(13)

interestingly, the perfect reconstruction condition (10) is also satisfied in this case by considering the values from the above substitutions, .

.

.

.

1

(14)

Thus equations (12), (13), and (14) have equivalence with (8), (7), and (10), respectively. It is, therefore, deduced from this relationship of the nonlinear diffusion and DWT that wavelet based diffusion works in three steps: (i) wavelet decomposition into low-frequency subband ( ) and high-frequency subbands ( ); (ii) regularization of high-frequency coefficients ( ) by multiplication with a function ; i.e., (iii) wavelet reconstruction from low-frequency subband ( ) and regularized highfrequency subbands ( ). The regularization step multiplies the high-frequency wavelet coefficients by the regularization coefficient , 1 , where , is

Fig. 1. Two-level wavelet diffusion

Discrete Wavelet Diffusion for Image Denoising

25

the aforementioned nonnegative monotonically decreasing diffusivity function and , is the wavelet domain edge estimate for pixel , at scale . This process of discrete wavelet diffusion is illustrated in Fig. 1. It must be noted that the wavelet diffusion operation can be considered as an iterative wavelet shrinkage [2] process.

3 Experimental Results and Discussion In this work, we used the undecimated discrete wavelet transform (UDWT) though DWT is also a possible option. The wavelet filter used was Haar and decomposition level was restricted to four, after initial experimentation with 1 to 5 decomposition levels. Further investigations on the use of decimated discrete wavelet transform, finding the appropriate number of decomposition levels, and the choice of optimal wavelet filter are left for future work. The diffusivity function employed is the one proposed by Weickert et al. [9]:

,

3.315

1

,

1,

,

0

,

,

0

(15)

which is used to derive the regularization function . The edge estimate , is approximated by the modulus of the high-frequency wavelet subbands at each scale (i.e., each scale has its own edge estimate) and is computed by: ,

,

,

,

(16)

A common value of edge threshold in (15) was used at all scales. The images were acquired from the “standard” test image collection of [10]. We used a multiscale approach for wavelet diffusion, in comparison to [4], by considering each approximation subband at a particular decomposition level as an independent image and high-frequency wavelet subbands of each level were diffused for noise removal. This lead to fewer iterations (about 5 on average) required for denoising in comparison to the single-scale diffusion of [4] which took nearly 20 or more iterations. We experimented with different values for , the results of which are not shown (due to lack of space) where the noisy images were polluted with additive Gaussian noise of signal-to-noise-ratio (SNR) of 10dB and 15dB . Some visual results for denoising with the proposed wavelet diffusion, Wiener filtering and conventional nonlinear diffusion are presented in Fig. 2. Our results with varying the values of edge threshold are in line with the results of [4] and, in general, with the conventional nonlinear diffusion. It indicates that a higher value of takes lesser number of iterations to reach the best results but it is prone to oversmooth the image (rather than preserving the edges) in a few iterations. In contrast, a smaller value of takes a higher number of iterations to provide the best results but it usually avoids the oversmoothing effect. Moreover, the diffusion process should stop after a fixed

K. Rajpoot, N. Rajpo oot, and J.A. Noble

Noisy

Original

26

15.49dB & 0.73

16.00dB & 0.32

21.08dB & 0.65

22.74dB & 0.73

22.89dB & 0.74

22.08dB & 0.76

24.48dB & 0.76

24.81dB & 0.84

22.13dB & 0.79

24.43dB & 0.80

24.30dB & 0.87

Wavelet diffusion

Anisotropic diffusion

Wiener filtering

15.02dB & 0.33

Fig. 2. Visual, SNR, and SSIM M results (Anisotropic Diffusion and Wavelet Diffusion: 𝜆 = 30 and iterations = 3 ; Anisotropiic Diffusion: Time-step = 0.5 and Weickert diffusivity functtion; Wiener filtering: 3x3 window))

Discrete Wavelet Diffusion for Image Denoising

27

number of iterations or it may actually degrade the image quality by oversmoothing effect. However, according to the authors’ knowledge, there is currently no mechanism to determine the best number of diffusion iterations required (either in wavelet based or in conventional non-linear diffusion methods). In addition, we can deduce from these results that a higher value of provides good results when the amount of noise is high. Fig. 2 shows the visual and quantitative results of the proposed wavelet diffusion and compares these with the results of Wiener filtering and conventional nonlinear diffusion in terms of visual quality, SNR, and structural similarity index measure (SSIM) [11]. Apparently, the SNR values of Wiener filtering and nonlinear diffusion for these images are close to the wavelet diffusion results but the visual quality and SSIM values (in the range of 0 to 1) indicate that the results with the proposed method have superior edge preservation, region homogeneity, and similarity to the original image. It was found in [11] that SNR may give flawed measure of image quality as it is not sensitive to the structure (e.g., edges) in an image. It is evident that wavelet diffusion method either provides comparable or favourable results than both Wiener filtering and Weickert nonlinear diffusion. We experimented with a range of parameter values and chose those values, specified in Fig. 2, that produced optimal results with the given set of images.

4 Conclusions In this paper, we have proposed a generalization of the wavelet diffusion for use with the discrete wavelet transform. We demonstrated that a single discrete step of nonlinear diffusion can be considered as equivalent to the DWT decomposition, highfrequency subbands regularization, and reconstruction. We showed also that the wavelet diffusion can operate in multiscale. Image denoising results of the proposed method compared with Wiener filtering and conventional nonlinear diffusion showed that the technique is promising. Moreover, the method smoothes the noise while preserving the important structures such as edges. Further investigations could be done in the use of DWT instead of UDWT, the number of wavelet decomposition levels, the wavelet bases, number of diffusion iterations, comparison with MZ-DWT based diffusion, and using varying threshold value for different scale. This may require looking for an automatic method of threshold computation.

References [1] Perona, P., Malik, J.: Scale Space and Edge Detection Using Anisotropic Diffusion. IEEE Transactions on Pattern Analysis and Machine Intelligence 12, 629–639 (1990) [2] Donoho, D.L., Johnstone, I.M.: Ideal Spatial Adaptation by Wavelet Shrinkage. Biometrika 81, 425–455 (1994) [3] Coifman, R.R., Donoho, D.: Translation-Invariant Denoising. In: Antoine, A., Oppenheim, G. (eds.) Wavelets in Statistics, pp. 125–150. Springer, New York (1995) [4] Shih, A.C.-C., Liao, H.-Y.M., Lu, C.-S.: A New Iterated Two-Band Diffusion Equation: Theory and Its Applications. IEEE Transactions on Image Processing (2003)

28

K. Rajpoot, N. Rajpoot, and J.A. Noble

[5] Yue, Y., Croitoru, M.M., Bidani, A., Zwischenberger, J.B., Jr., J.W.C.: Nonlinear Multiscale Wavelet Diffusion for Speckle Suppression and Edge Enhancement in Ultrasound Images. IEEE Transactions on Medical Imaging 25, 297–311 (2006) [6] Mallat, S., Zhong, S.: Characterization of Signals from Multiscale Edges. IEEE Transactions on Pattern Analysis and Machine Intelligence 14, 710–732 (1992) [7] Mrazek, P., Weickert, J., Steidl, G.: Diffusion-Inspired Shrinkage Functions and Stability Results for Wavelet Denoising. International Journal of Computer Vision 64, 171–186 (2005) [8] Mallat, S.: A Wavelet Tour of Signal Processing. Academic Press, MA (1998) [9] Weickert, J.: Anisotropic Diffusion in Image Processing. Stuttgart, Germany: Teubner (1998) [10] http://www.imageprocessingplace.com [11] Wang, Z., Bovik, A.C., Sheikh, H.R., Simoncelli, E.P.: Image Quality Assessment: From Error Visibility to Structural Similarity. IEEE Transactions on Image Processing 13, 600– 612 (2004)

Dynamic Color Texture Modeling and Color Video Decomposition Using Bounded Variation and Oscillatory Functions Mathieu Lugiez1,3 , Michel M´enard1,3 , and Abdallah El-Hamidi2,3 1

L3i - Universit´e de La Rochelle MIA - Universit´e de La Rochelle F´ed´eration PRIDES: Pˆ ole r´egional de Recherche en Images, Donn´ees et Syst`emes 2

3

Abstract. Dynamic, or temporal, texture is a spatially repetitive, timevarying visual pattern that forms an image sequence with a certain temporal stationarity. Important tasks are thus the detection, segmentation and perceptual characterization of Dynamic Texture (DT). Following recent work, color image decomposition appears as a good way to reach these different aims, however, to our best knowledge, no proposed model is currently able to deal with temporal aspect, inherent to color image sequences. The major contribution of this paper is to adapt static decomposition model to time aspect in order to deal with videos and color image sequences. In this paper we propose an extended decomposition model which splits a video into two components, a first one containing geometrical information, the structure of the sequence and a second one dynamic color texture and noise. Examples for color video decomposition and characterization of real dynamic present in texture component will be presented.

1 1.1

Introduction Motivation

A new issue in texture analysis is its extension to the temporal domain, a field known as Dynamic Texture (DT) analysis. In DT, the notion of self-similarity central to conventional image textures is extended to the spatiotemporal domain. DT are typically result from processes such as of water flows, smoke, fire, a flag blowing in the wind, a moving escalator, or a walking crowd. Important tasks are thus the detection, segmentation and perceptual characterization of dynamic textures. The ultimate goal is to be able to support video queries based on the recognition of the actual natural and artificial dynamic texture processes. Following recent work, color image decomposition into geometrical and texture components appears as a good way to reach this aim in extracting meaningful information, i.e texture component, independently of geometrical information. In this way, we propose to extend spatial color decomposition model to spatiotemporal domain, and attempt to highlight time influence present in video to characterize dynamic texture. To the best of our knowledge, no such time adaptation is currently available. A. Elmoataz et al. (Eds.): ICISP 2008, LNCS 5099, pp. 29–37, 2008. c Springer-Verlag Berlin Heidelberg 2008 

30

1.2

M. Lugiez, M. M´enard, and A. El-Hamidi

Overview of the Paper

The aim of this work is to extend a model, which decompose color image into two components, a first one containing geometrical structure U and a second one V, holding textural information and noise. So, we aim to deal with color image sequences in extending to time existing reliable model. Moreover, through decomposition of texture component, we attempt to determinate time impact, showing up dynamicity present in sequences, which will be suit for future work on dynamic texture. In the first place of this paper we introduce the extended minimization functional problem and the associate discrete framework in which we place ourself and which is an appropriate one in image sequence processing. In a second part we present the extended time decomposition model and subsequently its color implementation and choice of parameters. Then, in the last part, we show some significant results and attempt to present time weight in dynamic texture extraction through color image sequence.

2

Time Extension of Decomposition Model

Decomposing an image into meaningful component appears as one of major aims in recent development in image processing. The first goal was image restoration and demising; but following the ideas of Yves Meyer, in total variation minimization framework of L. Rudin, S. OSher and E. Fatemi, image decomposition into geometrical and oscillatory (i.e texture) component appears as usefull and very interesting way in computer vision and image analysis. There is a very large literature and recent advances on image decomposition models, image regularization and texture extraction and modelling. So, we only cite, among many others, most recent works which we appear like most relevant and usefull paper. In this way, reader can refer to the work of Stark et al. [1], Aujol et al. [2], [3], Aujol and Chambolle [4], Aujol and Ha Kang [5] and Vese and Osher [6], [7], [8] to cover the most recent and relevant advances. 2.1

Decomposition Model and Functional Spaces

In order to decompose image sequences in suitable components we propose to extend the Osher-Vese [8] color decomposition model. Their approach derived from Meyer decomposition model [9]. Its rely on space of functions of bounded variation, BV and Banach space, G. Authors propose to minimize the following discretized functional:



inf (u,v)∈BV ×G/f =u+v

F (u, v) =

|∇u| + λvG



(1)

BV is a good space to model functions with discontinuities along lines and curves, that can represent and preserve edges in an image. For the reader convenience we recall here its definition [10]:

Dynamic Color Texture Modeling and Color Video Decomposition

31

Definition 1. BV (Ω) is the subspace functions u ∈ L1 (Ω) such that the following quantity, called the total variation of u, is finite:





J(u) = sup

u(x)div(ξ(x))dx

(2)

Ω

such that ξ ∈ Cc1 (Ω, R2 ), ||ξ||L∞ (Ω) ≤ 1 In order to improve representation of oscillating patterns, Meyer in [9] has introduced the Banach space, G, which modeling signals with large oscillations, in particular textures and noise. A function belonging to G may have large oscillations and nevertheless have a small norm. Thus the norm on G is well-adapted to capture the oscillations of a function in an energy minimization method. We recall here the definition of G: Definition 2. G is the Banach space composed of the distributions f which can be written f = ∂1 g1 + ∂2 g2 = div(g) with g1 and g2 in L∞ (Ω). On G, the following norm is associate:



vG = inf gL∞ (Ω,R2 ) /v = div(g), g = (g1 , g2 ), |g(x)| =

2.2



(|g1 |2 + |g2 |2 )(x)



(3)

Spatiotemporal Structure and Discretization

To take into account the spatiotemporal structure, we consider a video as an 3-D image [11], i.e a volume, so that we can apply 2-D image algorithms extended to the 3-D case. We assume that we have a given image sequence f ∈ L2 (Ω), where Ω is an open and bounded domain on R3 , with Lipschitz boundary. In order to recover u and v from f , we propose: – An extended discrete version of gradient vector |∇u| given by:



(∇u)i,j,k = (∇u)1i,j,k , (∇u)2i,j,k , (∇u)3i,j,k (∇u)1i,j,k = (∇u)2i,j,k

=

(∇u)3i,j,k

=

ui+1,j,k − ui,j,k 0

if i < N if i = N

ui,j,k − ui,j+1,k 0

if j < N if j = N

ui,j,k − ui,j,k−1 0

if k < N if k = N





(4)

– An extended discrete total variation definition: J(u) = (∇u)1i,j,k + (∇u)2i,j,k + α(∇u)3i,j,k

(5)

we introduce the α constant to maintain homogeneity between space and time component. It’s mainly for numerical implementation, to avoid discretization problem due to quantization step, which be different along space and time dimension. In practice, we often set it to one, but user can adapt it to less, more or in function of frame per second, or quickness of movement present in sequence, to ensure most reliability and homogeneity.

32

M. Lugiez, M. M´enard, and A. El-Hamidi

– An adapted definition of G, inspired by [8] for the vector case, extended to the third dimension: Definition 3. Let G denote the Banach space consisting of all generalized vector-valued functions v (x, y, t) = (vR (x, y, t), vG (x, y, t), vB (x, y, t)) which can be written as: v (x, y, t) = (div gR , div gG , div gB ) ∞

(6)

g1,c , g2,c , g3,c ∈ L (R ), c = R, G, B , 3

∞ induced by the norm v∗ defined as the lower bound  of all L norms of func 2 2 2 tions |g |, where |g| = |gR |2 + |gG |2 + |gB |2 = c=R,G,B ((g1,c ) + (g2,c ) + (g3,c ) ),

and where the infinitum is computed over all decompositions (6) of v .

3

Description of the Extended Decomposition Model

For the reader convenience we only use, by now, useful indices in our formulas to avoid overloaded notation, so we will use c indices to denote color channel (c ∈ R, G, B) and 1, 2 and 3 exponents to represent the dimension to which objects belong. 3.1

Description of the Model

We propose the following minimization problem inspired by (6) and [8], for each color channel:



inf

Gp (u, g1 , g2 , g3 ) =

u,g1 ,g2 ,g3

|∇u| + λ



|f − u − ∂x g1 − ∂y g2 − ∂t g3 |2 dxdydt +μ

  (



g12 + g22 + g32 )p dxdydt

1 p

(7)

where λ, μ are tuning parameters (see next section for more useful details). Let reintroduce that u = (uR , uG , uB ), and gi = (gi,R , gi,G , gi,B ), i ∈ {1, 2, 3}. Formally minimizing the above energy equation with respect to u, g1 , g2 , g3 , yields the following Euler-Lagrange equation for each color channel: 1 u = f − ∂x g1 − ∂y g2 − ∂t g3 + div 2λ



μ(

g12 + g22 + g32 )1−p (



μ(

g12 + g22 + g32 )



μ(

g12 + g22 + g32 )



 1−p (

 1−p (

g12 + g22 + g32 )p−2 g1 = 2λ

g12 + g22 + g32 )p−2 g2 = 2λ

g12 + g22 + g32 )p−2 g3 = 2λ

∂ ∂x

∂ ∂y

∂ ∂t

∇u  |∇u| (8)

2 2 2 (u − f ) + ∂xx g1 + ∂xy g2 + ∂xt g3



(9) 2 2 2 (u − f ) + ∂yx g1 + ∂yy g2 + ∂yt g3



(10) 2 2 2 (u − f ) + ∂xt g1 + ∂yt g2 + ∂tt g3



(11)

Dynamic Color Texture Modeling and Color Video Decomposition

33

To simplify the presentation, let us introduce the notation:



g12 + g22 + g32 )1−p (

H(g1 , g2 , g3 ) = (

3.2



g12 + g22 + g32 )p−2

Numerical Implementation

For the reader convenience, we present here a numerical scheme to solve our minimization problem. So to solve equations (8) to (11) we use a semi-implicit finite differences scheme and an iterative algorithm, based on fixed point iteration [6]. We got, in order to compute gradient: •

|∇u| = |∇u|i,j,k =



ui+1 − ui−1 2  uj+1 − uj−1 2  uk+1 − uk−1 2 + + 2h 2h 2h

(12)

so, belong first dimension (x) we got:

  |∇u|i+  |∇u|i−

1 ,j,k 2

1 ,j,k 2

= =

 

ui+1 −u h u−ui−1 h

2  u +

j+1 −uj−1

2  u +

2  u +

2h

2

k+1 −uk−1

2  u 2h

i−1,j+1 −ui−1,j−1

+

2h

i−1,k+1 −ui−1,k−1

2

2h

(13)

in the same way, we compute gradient belong y and t dimension. We are now in position to introduced complete numerical scheme to solving Euler-Lagrange equations: n+1

u



1

= 1+

1 3λh2

 ∗ f − ∂

1

|∇| i+ 1 2

+

1

|∇| i− 1 2

+

1 x g1 − ∂y g2 − ∂t g3 + 3λh2

1

|∇| j+ 1 2

 

un i+1 |∇|i+ 1

+

2

g1n+1 = n+1

g2

=

g3n+1 =



3λ μH(g1n , g2n , g3n ) +

6λ h2

3λ μH(g1n , g2n , g3n )



∂x un − ∂x f + n

+

6λ h2

3λ μH(g1n , g2n , g3n ) +

6λ h2



1

+

|∇| j− 1 2

un i−1 |∇|i− 1

2

g1ni+1

+

+

+

1

|∇| k+ 1 2

un j+1 |∇|j+ 1

g1ni−1

h2 2

n

∂y u − ∂y f + ∂xy g1 +

+

2

g2n

j+1

+

(14)

1

|∇| k− 1 2

un j−1 |∇|j− 1

+

2

un k+1 |∇|k+ 1 2

+

un k−1 |∇|k− 1

2 2 + ∂xy g2n + ∂xt g3n

+ g1n

j−1

h2

2 2 n ∂t un − ∂t f + ∂xt g1n + ∂yt g2 +

g3n

k+1

2

+ g3n

2

(15) (16)



n

+ ∂yt g3

 

(17)



k−1

h2

(18) (19)

where h denote the discrete step space, so in practice we set h = 1 in our algorithm, moreover in furtherance of time computing, we always use the most recent computed values. For the initialization of parameters we set: u0 = f , g10 = ∂x f −1 √ √ 2 ∂y f 2 √ 2 ∂t f 2 , g20 = −1 and g30 = −1 3λ 3λ 3λ 2 2 2 2 2 ∂x f +∂y f +∂t f

∂x f +∂y f +∂t f

∂x f +∂y f +∂t f

34

3.3

M. Lugiez, M. M´enard, and A. El-Hamidi

Choice of Parameters

To obtain week regularization, we use parameters as: λ = 0.1, μ = 0.1 and we compute about 20 iterations. For strong regularization we got: λ = 0.005, μ = 0.005 iterated 50 times. So, for classic decomposition we use parameters as: λ = 0.01, μ = 0.01 iterated 20 times. For all results present in the next section we computed our decomposition on 8 images treated simultaneously as one block, but our algorithm is able to deal with bigger image block to catch lower frequences and wider range of time oscillating patterns.

4

Numerical Results and Time Component

All images and results are compute from DynTex, the dynamic texture database [12] which provide a large and diverse database of high-quality dynamic textures. Dyntex sequences come from natural scene presenting a wide variety of moving process as flowing water, leaves blowing in wind, walking crowd... Such diversity grants user to identify and emphasize a lot of aspects in testing purpose. For more details, demonstration sequence, wider range of results and for a presentation of similar color image sequences decomposition, relying on different approaches in the same framework [13], please consult this URL: http://perso. univ-lr.fr/mlugiez. 4.1

Static vs. Dynamic Decomposition

In order to prove that our dynamic decomposition method show more significant result than a static decomposition, we present a comparison between two

Fig. 1. From left to right, the geometrical component, U, in classic color decomposition (top) and its texture and noise component V (bottom). The original image (center and top), the difference between static and dynamic V component (center and bottom). Then our new dynamic decomposition components (right).

Dynamic Color Texture Modeling and Color Video Decomposition

35

Fig. 2. From left to right, the geometrical component, U, in classic color decomposition (top) and its texture and noise component V (bottom). The original image (center and top), the difference between static and dynamic V component (center and bottom). Then our new dynamic decomposition components (right).

Fig. 3. From left to right, the geometrical component, U, in classic color decomposition (top) and its texture and noise component V (bottom). The original image (center and top), the time influence g3 part of V component (center and bottom). Then our new dynamic decomposition components (right).

36

M. Lugiez, M. M´enard, and A. El-Hamidi

Fig. 4. From left to right, the geometrical component, U, in classic color decomposition (top) and its texture and noise component V (bottom). The original image (center and top), the time influence g3 part of V component (center and bottom). Then our new dynamic decomposition components (right).

methods (static and dynamic decomposition are both computed with same classic parameters). We can easily see that time impact in result, water in Fig.1 is well regularized and fluid aspect is well represent in the V component. In Fig. 2 we can clearly see the reenforcement of moving cars texture without that static part and objects present in sequence are taken into account. Moreover the regularization is more robust to illumination and movement constrain. Moreover, if user tunes parameters to obtain stronger regularization, our algorithm is able to catch wider waves in spatiotemporal texture component: see the circumference of fountain in Fig. 1, more regularized (in U component) than wider waves. It’s a matter of deep in spatiotemporal texture extraction, which our algorithm is able to deal with. 4.2

Time Impact in Our Decomposition

We present, in Fig. 3, a part of a decomposed sequence of flowing water under wood bridge. We can see the static aspect of U component, regularized in space and in time, seems to be freezed, although texture component, V, present a real dynamic, strengthened by time influence. Only moving things or objects presenting dynamicity are taken in account in the third part of V component (i.e g3 ). In Fig. 4 we can distinctly see time influence, reed’s branch oscillating under water flow is clearly highlight, waves present in basin’s fountain are well regularized in U component, water dynamicity is totaly catch as texture. We can clearly see that is due to the third part of texture component, movement information is well captured in this component.In this way we obtain the dynamicity present

Dynamic Color Texture Modeling and Color Video Decomposition

37

in video through oscillations along time dimension. These results will be usefull for future work on dynamic texture characterization.

References 1. Starck, J.L., Elad, M., Donoho, D.L.: Image decomposition via the combination of sparse representations and a variational approach. IEEE Trans. Image Processing 14(10), 1570–1582 (2005) 2. Aujol, J.F., Aubert, G., Feraud, L.B., Chambolle, A.: Image decomposition into a bounded variation component and an oscillating component. Journal of Mathematical Imaging and Vision 22(1), 71–88 (2005) 3. Aujol, J.F., Gilboa, G., Chan, T., Osher, S.: Structure-texture image decomposition - modeling, algorithms, and parameter selection. International Journal of Computer Vision 67(1), 111–136 (2006) 4. Aujol, J.F., Chambolle, A.: Dual norms and image decomposition models. International Journal of Computer Vision 63(1), 85–104 (2005) 5. Aujol, J.F., Kang, S.H.: Color image decomposition and restoration. J. Visual Communication and Image Representation 17(4), 916–928 (2006) 6. Vese, L.A., Osher, S.J.: Modeling textures with total variation minimization and oscillating patterns in image processing. J. Sci. Computing 19, 553–572 (2003) 7. Vese, L.A., Osher, S.J.: Image denoising and decomposition with total variation minimization and oscillatory functions. Journal of Mathematical Imaging and Vision 20(1-2), 7–18 (2004) 8. Vese, L.A., Osher, S.: Color texture modeling and color image decomposition in a variational-PDE approach. In: SYNASC, pp. 103–110. IEEE Computer Society, Los Alamitos (2006) 9. Meyer, Y.: Oscillating patterns in image processing and nonlinear evolution equations. University Lecture Series, vol. 22, American Mathematical Society, Providence, RI, The fifteenth Dean Jacqueline B. Lewis memorial lectures (2001) 10. Ambrosio, L., Fusco, N., Pallara, D.: Functions of bounded variation and free discontinuity problems. Oxford Mathematical Monographs. Oxford Mathematical Monographs. Clarendon Press, Oxford (2000) 11. Aubert, G., Kornprobst, P.: Mathematical Problems in Image Processing: Partial Differential Equations and the Calculus of Variations, 2nd edn. Applied Mathematical Sciences, vol. 147. Springer, Heidelberg (2006) 12. P´eteri, R., Huskies, M., Fazekas., S.: Dyntex: A comprehensive database of dynamic textures (2005), http://www.cwi.nl/projects/dyntex/ 13. Lugiez, M., M´enard, M., El-Hamidi, A.: Spatiotemporal extension of color decomposition model and dynamic color structure-texture extraction (2008)

Reinstating Floyd-Steinberg: Improved Metrics for Quality Assessment of Error Diffusion Algorithms Sam Hocevar1 and Gary Niger2 1

Laboratoire d’Imagerie Bureautique et de Conception Artistique 14 rue de Plaisance, Paris, France 2 143 Rolloffle Avenue, Tarzana, California 91356 [email protected], gary [email protected]

Abstract. In this contribution we introduce a little-known property of error diffusion halftoning algorithms which we call error diffusion displacement. By accounting for the inherent sub-pixel displacement caused by the error propagation, we correct an important flaw in most metrics used to assess the quality of resulting halftones. We find these metrics to usually highly underestimate the quality of error diffusion in comparison to more modern algorithms such as direct binary search. Using empirical observation, we give a method for creating computationally efficient, image-independent, model-based metrics for this quality assessment. Finally, we use the properties of error diffusion displacement to justify Floyd and Steinberg’s well-known choice of algorithm coefficients. Keywords: halftoning, error diffusion, image quality, human visual system, color quantization.

1

Introduction

Image dithering is the process of reducing continuous-tone images to images with a limited number of available colours. Applications vary tremendously, from laser and ink-jet printing to display on small devices such as cellphones, or even the design of banknotes. Countless methods have been published for the last 40 years that try to best address the problem of colour reduction. Comparing two algorithms in terms of speed or memory usage is often straightforward, but how exactly a halftoning algorithm performs quality-wise is a far more complex issue, as it highly depends on the display device and the inner workings of the human eye. Though this document focuses on the particular case of bilevel halftoning, most of our results can be directly adapted to the more generic problem of colour reduction.

2

Halftoning Algorithms

The most ancient halftoning method is probably classical screening. This highly parallelisible algorithm consists in tiling a dither matrix over the image and A. Elmoataz et al. (Eds.): ICISP 2008, LNCS 5099, pp. 38–45, 2008. c Springer-Verlag Berlin Heidelberg 2008 

Reinstating Floyd-Steinberg: Improved Metrics

39

using its elements as threshold values. Classical screening is known for its structural artifacts such as the cross-hatch patterns caused by Bayer ordered dither matrices [1]. However, modern techniques such as the void-and-cluster method [2], [3] allow to generate screens yielding visually pleasing results. Error diffusion dithering, introduced in 1976 by Floyd and Steinberg [4], tries to compensate for the thresholding error through the use of feedback. Typically applied in raster scan order, it uses an error diffusion matrix such as the following one, where x denotes the pixel being processed:   1  − x 7  16  3 5 1  Though efforts have been made to make error diffusion parallelisable [5], it is generally considered more computationally expensive than screening, but carefully chosen coefficients yield good visual results [6]. Model-based halftoning is the third important algorithm category. It relies on a model of the human visual system (HVS) and attempts to minimise an error value based on that model. One such algorithm is direct binary seach (DBS) [10], also referred to as least-squares model-based halftoning (LSMB) [16]. HVS models are usually low-pass filters. Nasanen [9], Analoui and Allebach [10] found that using Gaussian models gave visually pleasing results, an observation confirmed by independent visual perception studies [11]. DBS yields halftones of impressive quality. However, despite efforts to make it more efficient [12], it suffers from its large computational requirements and error diffusion remains a more widely used technique.

3

Error Diffusion Displacement

Most error diffusion implementations parse the image in raster scan order. Boustrophedonic (serpentine) scanning has been shown to cause fewer visual artifacts [7], but other, more complex processing paths such as Hilbert curves [8] are seldom used as they do not improve the image quality significantly. Intuitively, as the error is always propagated to the bottom-left or bottomright of each pixel (Fig. 1), one may expect the resulting image to be slightly translated. This expectation is confirmed visually when rapidly switching between an error diffused image and the corresponding DBS halftone. This small translation is visually innocuous but we found that it means a lot in terms of error computation. A common way to compute the error between an image hi,j and the corresponding binary halftone bi,j is to compute the mean square error between modified versions of the images, in the form: E(h, b) =

(||v ∗ hi,j − v ∗ bi,j ||2 )2 wh

(1)

where w and h are the image dimensions, ∗ denotes the convolution and v is a model for the human visual system.

40

S. Hocevar and G. Niger

Fig. 1. Floyd-Steinberg error diffusion direction in raster scan (left) and serpentine scan (right)

To compensate for the slight translation observed in the halftone, we use the following error metric instead: (||v ∗ hi,j − v ∗ tdx,dy ∗ bi,j ||2 )2 (2) wh where tdx,dy is an operator which translates the image along the (dx, dy) vector. By design, E0,0 = E. A simple example can be given using a Gaussian HVS model: Edx,dy (h, b) =

v(x, y) = e

x2 +y2 2σ2

(3)

Finding the second filter is then straightforward: (v ∗ tdx,dy )(x, y) = e

(x−dx)2 +(y−dy)2 2σ2

(4)

Experiments show that for a given image and a given corresponding halftone, Edx,dy has a local minimum almost always away from (dx, dy) = (0, 0) (Fig. 2). Let E be an error metric where this remains true. We call the local minimum Emin : Emin (h, b) = min Edx,dy (h, b) dx,dy

(5)

For instance, a Floyd-Steinberg dither of Lena with σ = 1.2 yields a per-pixel mean square error of 3.67 × 10−4 . However, when taking the displacement into account, the error becomes 3.06 × 10−4 for (dx, dy) = (0.165, 0.293). The new, corrected error is significantly smaller, with the exact same input and output images. Experiments show that the corrected error is always noticeably smaller except in the case of images that are already mostly pure black and white. The experiment was performed on a database of 10,000 images from common computer vision sets and from the image board 4chan, providing a representative sampling of the photographs, digital art and business graphics widely exchanged on the Internet nowadays [13]. In addition to the classical Floyd-Steinberg and Jarvis-Judice-Ninke kernels, we tested two serpentine error diffusion algorithms: Ostromoukhov’s simple error diffusion [15], which uses a variable coefficient kernel, and Wong and Allebach’s optimum error diffusion kernel [14]:

Reinstating Floyd-Steinberg: Improved Metrics

41

-1 -0.5 0 dy 0.5

1.5 1 0.7 0.52 0.42 0.35 0.31

1 -1

-0.5

0

0.5

1

dx Fig. 2. Mean square error for the Lena image. v is a simple 11×11 Gaussian convolution kernel with σ = 1.2 and (dx, dy) vary in [−1, 1] × [−1, 1]

raster Floyd-Steinberg raster Ja-Ju-Ni Ostromoukhov optimum kernel

E × 104 3.7902 9.7013 4.6892 7.5209

Emin × 104 3.1914 6.6349 4.4783 6.5772

We clearly see that usual metrics underestimate the quality of error-diffused halftones, especially in raster scan. Algorithms such as direct binary search, on the other hand, do not suffer from this bias since they are designed to minimise the very error induced by the HVS model.

4

An Image-Independent Corrected Quality Metric for Error-Diffused Halftones

We have seen that for a given image, Emin (h, b) is a better and fairer visual error measurement than E(h, b). However, its major drawback is that it is highly computationally expensive: for each image, the new (dx, dy) values need to be calculated to minimise the error value. Fortunately, we found that for a given raster or serpentine scan error diffusion algorithm, there was often very little variation in the optimal (dx, dy) values (Fig. 3 and 4). For each algorithm, we choose the (dx, dy) values at the histogram peak and we refer to them as the algorithm’s displacement, as opposed to the image’s displacement for a given algorithm. We call Ef ast (h, b) the error computed at (dx, dy). As Ef ast does not depend on the image, it is a lot faster to compute than Emin , and as it is statistically closer to Emin , we can expect it to be a better error estimation than E:

42

S. Hocevar and G. Niger -0.1 0 0 0.2 dy

dy

0.1 0.4

0.2 0.6 0.3 0.8 0.4 -0.1

0

0.1

0.2

0.3

0.4

0

0.2

dx

0.4

0.6

0.8

dx

-0.1 -0.05 0 0.05 0.1 0.15 0.2 0.25 0.3

-0.1 0 0.1 dy

dy

Fig. 3. Error diffusion displacement histograms for the raster Floyd-Steinberg (left) and raster Jarvis, Judis and Ninke (right) algorithms applied to a corpus of 10,000 images

0.2 0.3 0.4 0.5 0.6

-0.2

-0.1

0

0.1

0.2

-0.3 -0.2 -0.1

0

0.1 0.2 0.3

dx dx Fig. 4. Error diffusion displacement histograms for the Ostromoukhov (left) and optimum kernel (right) algorithms applied to a corpus of 10,000 images

raster Floyd-Steinberg raster Ja-Ju-Ni Ostromoukhov optimum kernel

5

E × 104 3.7902 9.7013 4.6892 7.5209

Emin × 104 3.1914 6.6349 4.4783 6.5772

dx 0.16 0.26 0.00 0.00

dy 0.28 0.76 0.19 0.34

Ef ast × 104 3.3447 7.5891 4.6117 6.8233

Using Error Diffusion Displacement for Optimum Kernel Design

We believe that our higher quality Emin error metric may be useful in kernel design, because it is the very same error that admittedly superior yet computationally expensive algorithms such as DBS try to minimise.

Reinstating Floyd-Steinberg: Improved Metrics

43

Our first experiment was a study of the Floyd-Steinberg-like 4-block error diffusion kernels. According to the original authors, the coefficients were found ”mostly by trial and error” [4]. With our improved metric, we now have the tools to confirm or infirm Floyd and Steinberg’s initial choice. 1 We chose to do an exhaustive study of every 16 {a, b, c, d} integer combination. We deliberately chose positive integers whose sum was 16: error diffusion coefficients smaller than zero or adding up to more than 1 are known to be unstable [17], and diffusing less than 100% of the error causes important loss of detail in the shadow and highlight areas of the image. We studied all possible coefficients on a pool of 3,000 images with an error metric E based on a standard Gaussian HVS model. Emin is only given here as an indication and only E was used to elect the best coefficients:

Fig. 5. Halftone of Lena using serpentine error diffusion (left) and the optimum coef1 ficients 16 {7, 4, 5, 0} (right) that improve on the standard Floyd-Steinberg coefficients in terms of visual quality for the HVS model used in section 3. The detail (bottom) shows fewer structure artifacts using optimum coefficients.

44

S. Hocevar and G. Niger

rank 1 2 5 18 ...

coefficients 7360 8350 7351 6352 ...

E × 104 4.65512 4.65834 4.68588 4.91020 ...

Emin × 104 3.94217 4.03699 3.79556 3.70465 ...

The exact same operation using Emin as the decision variable yields very different results. Similarly, E is only given here as an indication: rank 1 2 15 22 ...

coefficients 6352 7351 7360 8350 ...

Emin × 104 3.70465 3.79556 3.94217 4.03699 ...

E × 104 4.91020 4.68588 4.65512 4.65834 ...

Our improved metric allowed us to confirm that the original Floyd-Steinberg coefficients were indeed amongst the best possible for raster scan. More im1 portantly, using E as the decision variable may have elected 16 {7, 3, 6, 0} or 1 {8, 3, 5, 0}, which are in fact poor choices. 16 1 For serpentine scan, however, our experiment suggests that 16 {7, 4, 5, 0} is a better choice than the Floyd-Steinberg coefficients that have nonetheless been widely in use so far (Fig. 5).

6

Conclusion

We have disclosed an interesting property of error diffusion algorithms allowing to more precisely measure the quality of such halftoning methods. Having showed that such quality is often underestimated by usual metrics, we hope to see even more development in simple error diffusion methods. Confirming Floyd and Steinberg’s 30-year old ”trial-and-error” result with our work is only the beginning: future work may cover more complex HVS models, for instance by taking into account the angular dependance of the human eye [18]. We plan to use our new metric to improve all error diffusion methods that may require fine-tuning of their propagation coefficients.

References 1. Bayer, B.: Color imaging array. U.S. patent 3,971,065 (1976) 2. Ulichney, R.A. (Digital Equipment Corporation), Void and cluster apparatus and method for generating dither templates. U.S. patent 5,535,020 (1992)

Reinstating Floyd-Steinberg: Improved Metrics

45

3. Ancin, H., Bhattacharjya, A., Shu, J. (Seiko Epson Corporation), Void-and-cluster dither-matrix generation for better half-tone uniformity. U.S. patent 6,088,512 (1997) 4. Floyd, R.W., Steinberg, L.: An adaptive algorithm for spatial grey scale. Proceedings of the Society of Information Display 17, 75–77 (1976) 5. Metaxas, P.: Optimal Parallel Error-Diffusion Dithering. In: Color Imaging: DeviceIndep. Color, Color Hardcopy, and Graphic Arts IV, Proc. SPIE, vol. 3648, pp. 485–494 (1999) 6. Kite, T.D.: Design and Quality Assessment of Forward and Inverse Error-Diffusion Halftoning Algorithms. PhD thesis, Dept. of ECE, The University of Texas at Austin, Austin, TX (August 1998) 7. Ulichney, R.: Digital Halftoning. MIT Press, Cambridge (1987) 8. Velho, L., Gomes, J.: Digital halftoning with space-filling curves. In: Computer Graphics (Proceedings of SIGGRAPH 1991), vol. 25(4), pp. 81–90 (1991) 9. Nasanen, R.: Visibility of halftone dot textures. IEEE Trans. Syst. Man. Cyb. 14(6), 920–924 (1984) 10. Analoui, M., Allebach, J.P.: Model-based halftoning using direct binary search. In: Proc. of SPIE/IS&T Symp. on Electronic Imaging Science and Tech., San Jose, CA, February 1992, pp. 96–108 (1992) 11. McNamara, A.: Visual Perception in Realistic Image Synthesis. Computer Graphics Forum 20(4), 211–224 (2001) 12. Bhatt, et al.: Direct Binary Search with Adaptive Search and Swap, http://www. ima.umn.edu/2004-2005/MM8.1-10.05/activities/Wu-Chai/halftone.pdf 13. moot, http://www.4chan.org/ 14. Wong, P.W., Allebach, J.P.: Optimum error-diffusion kernel design. In: Proc. SPIE, vol. 3018, pp. 236–242 (1997) 15. Ostromoukhov, V.: A Simple and Efficient Error-Diffusion Algorithm. In: Proceedings of SIGGRAPH 2001, in ACM Computer Graphics, Annual Conference Series, pp. 567–572 (2001) 16. Pappas, T.N., Neuhoff, D.L.: Least-squares model-based halftoning. In: Proc. SPIE, Human Vision, Visual Proc., and Digital Display III, San Jose, CA, February 1992, vol. 1666, pp. 165–176 (1992) 17. Eschbach, R., Fan, Z., Knox, K.T., Marcu, G.: Threshold Modulation and Stability in Error Diffusion. Signal Processing Magazine 20(4), 39–50 (2003) 18. Sullivan, J., Miller, R., Pios, G.: Image halftoning using a visual model in error diffusion. J. Opt. Soc. Am. A 10, 1714–1724 (1993)

A Neuro Fuzzy Model for Image Compression in Wavelet Domain Vipula Singh1, Navin Rajpal2, and K. Srikanta Murthy3 1 Research Scholar GGSIPU, New Delhi Assistant Professor ECE dept PESIT Bangalore [email protected] 2 Professor GGSIPU, New Delhi 3 Professor IS Dept PESIT Bangalore

Abstract. Image compression forms the backbone for several applications such as storage of images in a database, picture archiving, TV and facsimile transmission, and video conferencing. Compression of images involves taking advantage of the redundancy in data present within an image. This work evaluates the performance of an image compression system based on fuzzy vector quantization, wavelet based sub band decomposition and neural network. Vector quantization is often used when high compression ratios are required. The implementation consists of three steps. First, image is decomposed into a set of sub bands with different resolution corresponding to different frequency bands. Different quantization and coding schemes are used for different sub bands based on their statistical properties. At the second step, the wavelet coefficients corresponding to lowest frequency band are compressed by differential pulse code modulation (DPCM) and the coefficients corresponding to higher frequency bands are compressed using neural network. The result of the second step is used as input to fuzzy vector quantizer. Image quality is compared objectively using mean squared error and PSNR along with the visual appearance. The simulation results show clear performance improvement with respect to decoded picture quality as compared to other image compression techniques.

1 Introduction Interest in digital image compression techniques, dates back to a few decades ago. Here we are concerned with minimizing the number of bits required to represent an image primarily for achieving information transmission and storage efficiency. All image compression algorithms strive to remove statistical redundancy and exploit perceptual irrelevancy while reducing the amount of data as much as possible. Over the last few decades researches have proposed many competing techniques such as prediction coders, transform coders, vector quantizers, trellis-coded quantizers and fractal image representation. However, due to the nature of each scheme every algorithm has its own advantages and disadvantages. Among all these schemes, however, the discrete cosine transform used in the JPEG standard has the advantage that it is well understood and it is quite mature. On the other hand vector quantization is a more recently developed technique. VQ performance is directly proportional to the codebook size and the vector size According to Shannon’s rate distortion theory A. Elmoataz et al. (Eds.): ICISP 2008, LNCS 5099, pp. 46–58, 2008. © Springer-Verlag Berlin Heidelberg 2008

A Neuro Fuzzy Model for Image Compression in Wavelet Domain

47

larger vectors would result in better VQ performance. However, with increased vector size the required codebook size also increases, and that in-turn results in an exponential increase in encoding complexity. Consequently, for practical purposes one should limit the vector size despite the fact that better VQ performance is theoretically possible. To date, VQ techniques used in image compression may be classified into two broad categories, based on either a hard or soft decision in a membership function, namely, K-means and Fuzzy K-mean. The K-means algorithm is the most popular minimization technique using a descent algorithm. It is simple to implement but it depends strongly on the selection of the initial codebook. It is based on hard decisions and ignores the possibility that the training vector may belong to a different cluster. Artificial neural networks are receiving renewed attention in many fields where high computation rates are required. In the field of image processing applications can be found in concurrent parallel processing structures, in the recognition of characters or 2-D patterns, in some 2-D signal processing tasks and more recently in data compression for image coding systems. Recent advances in signal processing tools such as wavelets opened up a new horizon in sub band image coding. Studies in wavelets showed that the wavelet transform exhibits the orientation and frequency selectivity of images [1-3]. Image coding using wavelets has been attempted by Antonini et al. [1], who used biorthogonal wavelets to obtain a set of bi-orthogonal sub bands. Woods and O’Neil [4] extended sub band decomposition to two-dimensional (2-D) signals and proposed a method for QMF design that eliminates possible aliasing error due to non ideal sub band filters. The original image was decomposed at different scales or sub bands of frequency using Mallat’s pyramidal architecture [2], in which horizontal and vertical orientations are considered preferential. After the image was decomposed, the wavelet coefficients were vector quantized producing a set of multi-resolution codebooks. Averbuch et al. [5] proposed a similar image compression approach that combines pyramidal wavelet decomposition and vector quantization. In order to improve the quality of the reconstructed images, they used higher bit rate per pixel for shapes found to be more important. Codebook design is an essential process in lossy image compression techniques based on vector quantization [6-8]. Paliwal et al [9] modified the K mean algorithm for vector quantization for fast convergence without affecting the optimality of the codebook. Kadono et al [10] combined wavelet transform and vector quantization on color images. Based on the concept of fuzzy sets, Ruspini [25] developed the first fuzzy clustering algorithm. Dunn [26] considered an alternative formulation of the clustering process and proposed the fuzzy k-means algorithm. Bezdek [27] extended Dunn's formulation and produced a family of fuzzy k-means algorithms, which includes Dunn's original algorithm as a special case. Sasazaki et al [28] suggested to use local fractal dimension to design a codebook and used fuzzy k means algorithm to group the training vectors into clusters. Recently, artificial neural networks [l1] are increasingly being examined and considered as possible solutions to problems and for application in many fields where high computation rates are required [12]. People have proposed several kinds of image compression methods [13]. The typical image compression methods are based on back propagation network [14-15]. The number of neurons in the hidden layer should be smaller than the number of units in the input and output layers. The image

48

V. Singh, N. Rajpal, and K.S. Murthy

is compressed in the hidden layers. However, the compression results are generally worse than traditional approaches [ 16-17]. Improved results probably cannot be achieved unless neural networks are incorporated directly into a state-of-the-art framework. Most successful modern coding techniques are built around filter banks [18-19]. There is evidence that the use of neural networks can improve the performance of sub band coders. Neural networks have been used to find vector quantization maps for wavelet coefficients [20], and recently Burges et al. [21] showed that preprocessing the detail coefficients using neural network DPCM reduced both the entropy of these bands and the length of the coded stream. The main objective of this paper is to develop a Neuro-Fuzzy network based on wavelet transform and report its application to Image compression. The paper is organized as follows: Section 2 briefly reviews filter bank concepts for image compression and section 3 introduces the background necessary to define the desired input-output relations that are required to train the neural network with back propagation. Section 4 describes the fuzzy k means algorithm for vector quantization, and Section 5 presents an implementation of the image compression algorithm. Section 6 reports sample simulation results and section 7 provides concluding remarks.

2 Wavelet Transform Wavelet transforms are multi resolution decompositions that can be used to analyze signals and images. They describe a signal by the power at each scale and position. Edges can be located very effectively in the wavelet transform domain. For image processing applications, one can use the hierarchical wavelet decomposition by Mallat [2]. The L and H filters are applied to the image in both the horizontal and vertical directions, and the filter outputs sub sampled by a factor of two, generating three orientation selective high-pass sub bands, HH, LH, HL, and a low-pass sub band LL. The process is then repeated on the LL band to generate the next level of the decomposition, and so on. As shown in Fig. 1, one octave of decomposition leads to four sub bands. Therefore, seven sub bands are obtained by iterating two times of such decomposition as shown in fig 2. The low-resolution version of the image is fed

Fig. 1. First stage of a discrete wavelet transform; The image is divided into 4 sub bands using separable filters

A Neuro Fuzzy Model for Image Compression in Wavelet Domain

49

Fig. 2. Two stages of pyramidal decomposition leading to 7 octave sub bands

back to the input to produce one low-resolution version of the image and six sub bands which contain image details. The wavelet decomposition is an alternative representation of images. To compress an input image data using transform, we have to decide which coefficients to send and how many bits to encode them. Our compression algorithm consists of taking the low pass subband in full, and then deciding which coefficients within the remaining subbands to keep. Hence, the basic idea is this: the smaller the support of the wavelet, the less nonzerowavelet coefficients will correspond to an edge, so the more efficient will be our compression scheme.

3 Neural Network for Image Compression In this section, we briefly review the basic idea of using a back propagation network to achieve image compression. A number of researchers [14-15] have shown that multilayer perceptron networks are able to learn a transform for reducing signal redundancy, and are capable of learning a reverse transform to recover the information (with some degradation) from a more compact (compressed) form of representation. In a multilayer configuration, the outputs of the units in one layer form the inputs to the next layer. The inputs to the first layer are considered as the network

Fig. 3. A multi layered neural network

50

V. Singh, N. Rajpal, and K.S. Murthy

inputs, and outputs of the last layer are the network outputs. The weights of the network are usually computed by training the network using the backpropagation algorithm. The backpropagation algorithm is a supervised learning algorithm which performs a surface to arrive at a gradient descent on a squared error energy minimum. The key to the use of this method on a multilayer perceptron is the calculation of error values for the hidden units by propagating the network. The network shown in Fig. 3 has N input nodes, K hidden layer nodes (K