3D Object Processing 3DObjectProcessing:Compression,IndexingandWatermarking. EditedbyJ.-L.Dugelay, A.BaskurtandM.Daoudi 2008JohnWiley&Sons,Ltd.ISBN:978-0-470-06542-6 3D Object Processing Compression, Indexing and Watermarking Edited by Jean-Luc Dugelay InstitutEure´com,France Atilla Baskurt INSALyon,CNRSLIRIS, France Mohamed Daoudi TELECOM Lille1,CNRSLIFL, France Copyright2008 JohnWiley&SonsLtd,TheAtrium,SouthernGate,Chichester, WestSussexPO198SQ,England Telephone(+44)1243779777 Email(forordersandcustomerserviceenquiries):[email protected] VisitourHomePageonwww.wileyeurope.comorwww.wiley.com AllRightsReserved.Nopartofthispublicationmaybereproduced,storedinaretrievalsystemor transmittedinanyformorbyanymeans,electronic,mechanical,photocopying,recording,scanning orotherwise,exceptunderthetermsoftheCopyright,DesignsandPatentsAct1988orunderthe termsofalicenceissuedbytheCopyrightLicensingAgencyLtd,90TottenhamCourtRoad,London W1T4LP,UK,withoutthepermissioninwritingofthePublisher.RequeststothePublishershould beaddressedtothePermissionsDepartment,JohnWiley&SonsLtd,TheAtrium,SouthernGate, Chichester,WestSussexPO198SQ,England,[email protected],orfaxedto(+44) 1243770620. Designationsusedbycompaniestodistinguishtheirproductsareoftenclaimedastrademarks.All brandnamesandproductnamesusedinthisbookaretradenames,servicemarks,trademarksor registeredtrademarksoftheirrespectiveowners.ThePublisherisnotassociatedwithanyproductor vendormentionedinthisbook. Thispublicationisdesignedtoprovideaccurateandauthoritativeinformationinregardtothesubject mattercovered.ItissoldontheunderstandingthatthePublisherisnotengagedinrendering professionalservices.Ifprofessionaladviceorotherexpertassistanceisrequired,theservicesofa competentprofessionalshouldbesought. OtherWileyEditorialOffices JohnWiley&SonsInc.,111RiverStreet,Hoboken,NJ07030,USA Jossey-Bass,989MarketStreet,SanFrancisco,CA94103-1741,USA Wiley-VCHVerlagGmbH,Boschstr.12,D-69469Weinheim,Germany JohnWiley&SonsAustraliaLtd,42McDougallStreet,Milton,Queensland4064,Australia JohnWiley&Sons(Asia)PteLtd,2ClementiLoop#02-01,JinXingDistripark,Singapore129809 JohnWiley&SonsCanadaLtd,6045FreemontBlvd,Mississauga,Ontario,L5R4J3,Canada Wileyalsopublishesitsbooksinavarietyofelectronicformats.Somecontentthatappears inprintmaynotbeavailableinelectronicbooks. LibraryofCongressCataloging-in-PublicationData 3Dobjectprocessing:compression,indexing,andwatermarking/editedbyJean-LucDugelay, AtillaBaskurt,MohamedDaoudi. p.cm. Includesbibliographicalreferencesandindex. ISBN978-0-470-06542-6 (cloth) 1.Imageprocessing–Digitaltechniques.2.Three-dimensionalimaging. 3.Digitalimages–Watermarking.4.Imagecompression.I.Dugelay,Jean-Luc. II.Baskurt,Atilla,1960-III.Daoudi,Mohamed,Ph.D. TA1637.A1442008 621.36(cid:1)7–dc22 2008003728 BritishLibraryCataloguinginPublicationData AcataloguerecordforthisbookisavailablefromtheBritishLibrary ISBN978-0-470-06542-6(HB) Typesetin10.5/13TimesbyLaserwordsPrivateLimited,Chennai,India PrintedandboundinGreatBritainbyTJInternational,Padstow,Cornwall Contents About the Contributors vii Introduction 1 1 Basic Background in 3D Object Processing 5 GuillaumeLavoue´ 1.1 3D Representation and Models 5 1.2 3D Data Source 28 1.3 3D Quality Concepts 34 1.4 Summary 39 References 40 2 3D Compression 45 GuillaumeLavoue´,FlorentDupont,AtillaBaskurt 2.1 Introduction 45 2.2 Basic Review of 2D Compression 46 2.3 Coding and Scalability Basis 48 2.4 Direct 3D Compression 51 2.5 Compression Based on Approximation 70 2.6 Normative Aspect: MPEG-4 76 2.7 Conclusion 77 2.8 Summary 78 2.9 Questionsand Problems 79 References 80 3 3D Indexing and Retrieval 87 StefanoBerretti,MohamedDaoudi,AlbertoDelBimbo,TarikFilaliAnsary, PietroPala,JulienTierny,Jean-PhillippeVandeborre 3.1 Introduction 87 vi Contents 3.2 Statistical Shape Retrieval 96 3.3 Structural Approaches 114 3.4 Transform-based Approaches: Spin Images 120 3.5 View-based Approach 123 3.6 Normative Aspect: MPEG-7 133 3.7 Summary 134 References 135 4 3D Object Watermarking 139 JihaneBennour,Jean-LucDugelay,EmmanuelGarcia, NikosNikolaidis 4.1 Introduction 139 4.2 Basic Review of Watermarking 140 4.3 Watermarking Principles Applied to 3D Objects 144 4.4 A Guided Tour of 3D Watermarking Algorithms 153 4.5 Concluding Remarks 172 4.6 Summary 175 4.7 Questionsand Problems 176 References 180 Conclusion 185 Index 191 About the Contributors Tarik Filali Ansary received a BE degree from Ecole Marocaine des Sci- ences de l’Inge´nieur, Morocco, in 2002, and an MS degree from the Univer- sity of Sciences and Technologies of Lille (USTL), France, in 2003, both in Computer Science. Hereceived a PhD in2006 from theInstitut National des Te´le´communications, France, and at USTL with the FOX-MIIRE Research Group at the LIFL (UMR USTL/CNRS 8022), a research laboratory in the computer science field of the USTL. His principal research interests include 3D content-based retrieval, multimedia indexing, and retrieval from content. Email: tarik.fi[email protected]. Atilla Baskurt was born in Ankara, Turkey, in 1960. He received his BS degree in 1984, MS in 1985 and PhD in 1989, all in Electrical Engineer- ing from INSA of Lyon, France. From 1989 to 1998, he was Maˆıtre de Confe´rences at INSA of Lyon. Since 1998, he has been Professor in Elec- trical and Computer Engineering, first at the University Claude Bernard of Lyon, and now at INSA of Lyon. Since 2003, he has been the Chair of the Telecommunication Department. Professor Baskurt leads the research activities of two teams at the LIRIS Research Laboratory: the IMAGINE team and the M2DisCo team. These teams work on image and 3D data analysis and segmentation for image compression, image retrieval, shape detection and identification. His technical research and experience include digital image processing, 2D–3D data analysis, compression, retrieval and watermarking, especially for multimedia applications. He is Charge´ de Mis- sion on Information and Communication Technologies (ICT) at the French Research Ministry. Email: [email protected]/[email protected]. Jihane Bennour received her engineering degree from CPE (Lyon, France) in 2004 and in parallel she obtained an MS degree in Image Signal Vision viii About theContributors from the University of St-E´tienne (France). She worked for six months in 2004 at INRIA (Sophia Antipolis, France) with the ORION team on the generation of 3D animations from scenario models. In October 2004 she started her PhD thesis in the Image and Video Group for Multimedia Com- munications and Applications at the Institut Eure´com under the guidance of Professor Jean-Luc Dugelay. Her research interest is 3D object watermark- ing. She was formerly involved in the FR-RNRT SEMANTIC-3D project and the European Ecrypt project. Email: [email protected]. Stefano Berretti received a doctoral degree in Electronics Engineering and aPhDinComputerEngineeringandCommunicationsfrom theUniversityof Florence, Italy, in 1997 and 2001, respectively. In 2000, he received a post- laurea degree in Multimedia Content Design from the Master in Multimedia of the University of Florence. Since 2002, he has been Assistant Professor at the University of Florence, where he teaches operating systems. Stefano Berretti also teaches database systems for the Master’s degree in Multimedia of the University of Florence. His current research interests are focused mainly on content modeling, retrieval and indexing of images and 3D object databases. Email: [email protected]fi.it. Mohamed Daoudi is Professor of Computer Science in Institut TELECOM; TELECOM-Lille1 and LIFL (UMR USTL/CNRS 8022). He received his PhDinComputerEngineeringfromtheUniversityofLille1(USTL),France, in 1993 and Habilitation a` Diriger des Recherches (HDR) from the Uni- versity of Littoral, France, in 2000. He was the founder and head of the MIIRE Research Group of LIFL from 2000 to 2004. His research inter- ests include pattern recognition, image processing, invariant representation of images and shapes, 3D analysis and retrieval and, more recently, 3D face recognition. He has published more than 80 papers in refereed journals and proceedingsofinternationalconferences. HeservedasaProgram Committee member for the International Conference on Pattern Recognition (ICPR) in 2004 and the International Conference on Multimedia and Expo (ICME) in 2004 and 2005. He is a frequent reviewer for IEEE Transactions on Pattern Analysis and Machine Intelligence and for Pattern Recognition Letters. His research has been funded by ANR, RNRT, European Commission grants. Email: [email protected]. Alberto Del Bimbo is Professor of Computer Engineering and the Director oftheMaster’s degreeinMultimediaoftheUniversityofFlorence, Italy.He About the Contributors ix wastheDirectoroftheDepartmentofSystemsandInformation,from1997to 2000andtheDeputyRectorforResearchandInnovationTransferoftheUni- versity of Florence from 2000 to 2006. From 2007 he has been the President of the Foundation for Research and Innovation, promoted by the University of Florence. His scientific interests are pattern recognition, image databases, human–computer interaction and multimedia applications. He has published over 230 papers in some of the most distinguished scientific journals and presented at international conferences, and is the author of the monograph Visual Information Retrieval, on content-based retrieval from image and video databases, published by Morgan Kaufmann in 1999. From 1996 to 2000, he was the President of the IAPR Italian Chapter, and, from 1998 to 2000, Member at Large of the IEEE Publication Board. He was the General Chair of IAPR ICIAP’97, the International Conference on Image Analysis and Processing, IEEE ICMCS’99, the International Conference on Multi- media Computing and Systems, AVIVDiLib’05, the International Workshop on Audio-Visual Content and Information Visualization, and VMDL07, the International Workshop on Visual and Multimedia Digital Libraries, and was on the board of many other primary scientific conferences. He is Associate Editor of Pattern Recognition, Journal of Visual Languages and Comput- ing, Multimedia Tools and Applications, Pattern Analysis and Applications and International Journal of Image and Video Processing, and was Asso- ciate Editor of IEEE Transactions on Multimedia and IEEE Transactions on Pattern Analysis and Machine Intelligence. Email: [email protected]fi.it. Jean-Luc Dugelay (PhD 1992, Member of the IEEE 1994, Senior Member 2002) joined the Institut Eure´com (Sophia Antipolis) in 1992, where he is currently a professor in charge of image and video research and teaching activities in the Department of Multimedia Communications. His research interests are in the area of multimedia signal processing and communica- tions, including security imaging (i.e. watermarking and biometrics) and facial image analysis. He contributed to the first book on watermarking (Information hiding techniques for steganography and digital watermark- ing, Artech House, 1999). He is an author or co-author of more than 150 papers that have appeared in journals or proceedings, 3 book chapters and 3 international patents. He has given several tutorials on digital watermark- ing (co-authored with F. Petitcolas from Microsoft Research, Cambridge) at major conferences (ACM Multimedia, October 2000, Los Angeles, and Sec- ond IEEE Pacific-Rim Conference on Multimedia, October 2001, Beijing). Hehas beenaninvitedspeaker and/ormemberoftheProgram Committeeof x About theContributors several scientificconferences andworkshops related todigitalwatermarking. He was technical co-chair and organizer of the Fourth Workshop on Mul- timedia Signal Processing, Cannes, October 2001. His group is involved in severalnationalandEuropeanprojectsrelatedtodigitalwatermarking(RNRT Aquamars and Semantic-3D, IST Certimark). Professor Dugelay served as associateeditorforseveraljournalsandiscurrentlytheEditorinChiefofthe EURASIP Journal on Image and Video Processing. He is currently a mem- ber of several Technical Committees of the IEEE Signal Processing Society. Email. [email protected]. Florent Dupont received his BS and MS degrees in 1990, and his PhD in 1994, from INSA in Lyons, France. Since 1998, he has been Associate Professor.In2001,hejoinedtheLIRISLaboratory(UMR5205CNRS)inthe University Claude Bernard of Lyon. His research interest mainly concerns 3D digital image processing, 3D compression and discrete geometry. He is involved in the M2Disco research team which aims at proposing new combinatorial, discrete and multiresolution models to analyze and manage various types of data such as images, 3D volumes and 3D meshes. Email: [email protected]. Emmanuel Garcia obtained his MSc from Ecole Polytechnique, France, in 1998,andanMScfromEcoleNationaleSupe´rieuredesTe´le´communications, France, in 2000, and his Ph.D. from Universite´ de Nice–Sophia Antipolis, France, in 2004, on the subject ‘Texture-based watermarking of 3D video objects’. Since 2005 he has been employed as an image processing expert at Infoterra France. His research interests concern image processing and com- putervision,nowappliedtophotogrammetry,cartographyandcitymodeling. Email: [email protected]. Guillaume Lavoue´ has an Engineering Degree in Electronic, Signal Pro- cessing and Computer Science from CPE-Lyon (France), an MSc in Image Processing from the University Jean Monnet of St-E´tienne (France) and a PhD in Computer Science from the University Claude Bernard of Lyon (France). From February to April 2006, he was a postdoctoral fellow at the Signal Processing Institute (EPFL) in Switzerland. Since September 2006, he has been Associate Professor at the French engineering university INSA of Lyon. He is involved in the M2Disco team from the LIRIS Laboratory (UMR 5205 CNRS). His research interests focus on 3D model analysis and processing, including compression, watermarking, geometric modeling and 2D/3D recognition. Email: [email protected]. About the Contributors xi Nikos Nikolaidis received his Diploma of Electrical Engineering in 1991 and PhD in Electrical Engineering in 1997, both from the Aristotle Univer- sity of Thessaloniki, Greece. From 1992 to 1996 he served as a teaching assistant in the Departments of Electrical Engineering and Informatics at the same university. From 1998 to 2002 he was a postdoctoral researcher and teaching assistant at the Department of Informatics, Aristotle University of Thessaloniki. He is currently Assistant Professor in the same department. Dr Nikolaidis is the co-author of the book 3-D Image Processing Algorithms (John Wiley & Sons, Ltd, 2000). He has co-authored 7 book chapters, 26 journal papers and 87 conference papers. He currently serves as Associate EditorontheInternationalJournalofInnovativeComputingInformationand Control, the International Journal of Innovative Computing Information and ControlExpressLetters and the EURASIP JournalonImageandVideoPro- cessing. His research interests include computer graphics, image and video processing and analysis, copyright protection of multimedia and 3D image processing. Dr Nikolaidis is a Member of the IEEE and EURASIP. Email: [email protected]. Pietro Pala graduated in Electronics Engineering from the University of Florence, Italy, in 1994. From the same university, he received a PhD in Information and Telecommunications Engineering in 1997. Presently, he is Associate Professor of Computer Engineering at the University of Florence where he teaches database management systems and image and video pro- cessing and analysis. He also teaches multimedia systems for the Master’s degreeinMultimediaContentDesignoftheUniversityofFlorence.Hismain scientific and research interests include pattern recognition, image and video databases and multimedia information retrieval. Email: [email protected]fi.it. Julien Tierny received an MSc degree (summa cum laude) in Computer Science from Lille University (USTL) along with an engineering degree from TELECOM-Lille1 in 2005. He is currently a PhD candidate within the Computer Science Laboratory of the University of Lille (LIFL, UMR USTL/CNRS 8022). He is also a teaching assistant in the Computer Sci- ence Department of the University of Lille. His research interests include shape modeling, shape similarity estimation, geometry processing and their applications. Email: [email protected]. Jean-Philippe Vandeborre received his MS degree in 1997 and PhD in Computer Science in 2002 from the University of Sciences and Technolo- gies of Lille (USTL), France. Currently, he is Associate Professor of the