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 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 Moshe Y. Vardi Rice University, Houston, TX, USA Gerhard Weikum Max-Planck Institute of Computer Science, Saarbruecken, Germany
4842
George Bebis Richard Boyle Bahram Parvin Darko Koracin Nikos Paragios Syeda-Mahmood Tanveer Tao Ju Zicheng Liu Sabine Coquillart Carolina Cruz-Neira Torsten Müller Tom Malzbender (Eds.)
Advances in Visual Computing Third International Symposium, ISVC 2007 Lake Tahoe, NV, USA, November 26-28, 2007 Proceedings, Part II
13
Volume Editors George Bebis, E-mail:
[email protected] Richard Boyle, E-mail:
[email protected] Bahram Parvin, E-mail:
[email protected] Darko Koracin, E-mail:
[email protected] Nikos Paragios, E-mail:
[email protected] Syeda-Mahmood Tanveer, E-mail:
[email protected] Tao Ju, E-mail:
[email protected] Zicheng Liu, E-mail:
[email protected] Sabine Coquillart, E-mail:
[email protected] Carolina Cruz-Neira, E-mail:
[email protected] Torsten Müller, E-mail:
[email protected] Tom Malzbender, E-mail:
[email protected]
Library of Congress Control Number: 2007939401 CR Subject Classification (1998): I.4, I.5, I.2.10, I.3.3, I.3.5, I.3.7, I.2.6, F.2.2 LNCS Sublibrary: SL 6 – Image Processing, Computer Vision, Pattern Recognition, and Graphics ISSN ISBN-10 ISBN-13
0302-9743 3-540-76855-6 Springer Berlin Heidelberg New York 978-3-540-76855-5 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 2007 Printed in Germany Typesetting: Camera-ready by author, data conversion by Scientific Publishing Services, Chennai, India Printed on acid-free paper SPIN: 12193011 06/3180 543210
Preface
It is with great pleasure that we welcome you to the Proceedings of the 3rd International Symposium on Visual Computing (ISVC 2007) held in Lake Tahoe, Nevada/California. ISVC offers a common umbrella for the four main areas of visual computing including vision, graphics, visualization, and virtual reality. Its goal is to provide a forum for researchers, scientists, engineers and practitioners throughout the world to present their latest research findings, ideas, developments, and applications in the broader area of visual computing. This year, the program consisted of 14 oral sessions, 1 poster session, 6 special tracks, and 6 keynote presentations. Following a very successful ISVC 2006, the response to the call for papers was almost equally strong; we received over 270 submissions for the main symposium from which we accepted 77 papers for oral presentation and 42 papers for poster presentation. Special track papers were solicited separately through the Organizing and Program Committees of each track. A total of 32 papers were accepted for oral presentation and 5 papers for poster presentation in the special tracks. All papers were reviewed with an emphasis on their potential to contribute to the state of the art in the field. Selection criteria included accuracy and originality of ideas, clarity and significance of results, and presentation quality. The review process was quite rigorous, involving two to three independent blind reviews followed by several days of discussion. During the discussion period we tried to correct anomalies and errors that might have existed in the initial reviews. Despite our efforts, we recognize that some papers worthy of inclusion may have not been included in the program. We offer our sincere apologies to authors whose contributions might have been overlooked. We wish to thank everybody who submitted their work to ISVC 2007 for review. It was because of their contributions that we succeeded in having a technical program of high scientific quality. In particular, we would like to thank the ISVC 2007 Area Chairs, the organizing institutions (UNR, DRI, LBNL, and NASA Ames), the industrial sponsors (Intel, DigitalPersona, Equinox, Ford, Siemens, Hewlett Packard, MERL, UtopiaCompression), the International Program Committee, the special track organizers and their Program Committees, the keynote speakers, the reviewers, and especially the authors that contributed their work to the symposium. In particular, we would like to thank Siemens,
VI
Preface
Hewlett Packard, and MERL who kindly offered three “best paper awards” this year. September 2007
ISVC 2007 Steering Committee and Area Chairs
Organization
ISVC 2007 Steering Committee Bebis George, University of Nevada, Reno, USA Boyle Richard, NASA Ames Research Center, USA Parvin Bahram, Lawrence Berkeley National Laboratory, USA Koracin Darko, Desert Research Institute, USA
ISVC 2007 Area Chairs Computer Vision Paragios Nikos, Ecole Centrale de Paris , France Syeda-Mahmood Tanveer, IBM Almaden, USA Computer Graphics Ju Tao, Washington University, USA Liu Zicheng, Microsoft Research, USA Virtual Reality Coquillart Sabine, INRIA, France Cruz-Neira Carolina, Louisiana Immersive Technologies Enterprise, USA Visualization M¨ uller Torsten, Simon Fraser University, Canada Malzbender Tom, Hewlett Packard Labs, USA Publicity Li Wenjing, STI Medical Systems, USA Local Arrangements Veropoulos Kostas, Desert Research Institute, USA Publications Wang Junxian, UtopiaCompression, USA
VIII
Organization
ISVC 2007 Keynote Speakers Mathieu Desbrun , California Institute of Technology, USA Kwan-Liu Ma, University of Califirnia, Davis, USA John Tsotsos, York University, Canada Mubarak Shah, University of Central Florida, USA Dimitris Metaxas, Rutgers University, USA Fatih Porikli, MERL, USA
ISVC 2007 International Program Committee Computer Vision (Area 1) Abidi Besma, University of Tennessee, USA Aggarwal J. K.,University of Texas, Austin, USA Agouris Peggy, George Mason University, USA Anagnostopoulos George, Florida Institute of Technology, USA Argyros Antonis, University of Crete , Greece Asari Vijayan, Old Dominion University, USA Basu Anup, University of Alberta, Canada Bebis George, University of Nevada at Reno, USA Belyaev Alexander, Max-Planck-Institut fuer Informatik, Germany Bhatia Sanjiv, University of Missouri-St. Louis, USA Bioucas Jose, Instituto Superior T´ecnico, Lisbon, Portugal Birchfield Stan, Clemson University, USA Boon Goh Wooi, Nanyang Technological University, Singapore Bourbakis Nikolaos, Wright State University, USA Brimkov Valentin, State University of New York, USA Cavallaro Andrea, Queen Mary, University of London, UK Chellappa Rama, University of Maryland, USA Chen Danny, University of Notre Dame, USA Darbon Jerome, LRDE EPITA, France Davis James, Ohio State University, USA Debrunner Christian, Colorado School of Mines, USA Duan Ye, University of Missouri-Columbia, USA El-Gammal Ahmed, University of New Jersey, USA Eng How Lung, Institute for Infocomm Research, Singapore Erol Ali, Ocali Information Technology, Turkey Fan Guoliang, Oklahoma State University, USA Foresti GianLuca, University of Udine, Italy Gandhi Tarak, University of California at San Diego, USA Georgescu Bogdan, Siemens, USA Hammoud Riad, Delphi Corporation, USA Harville Michael, Hewlett Packard Labs, USA He Xiangjian, University of Technology, Australia
Organization
Jacobs David, University of Maryland, USA Kamberov George, Stevens Institute of Technology, USA Kamberova Gerda, Hofstra University, USA Kakadiaris Ioannis, University of Houston, USA Kisacanin Branislav, Texas Instruments, USA Klette Reinhard, Auckland University, New Zeland Kollias Stefanos, National Technical University of Athens, Greece Komodakis Nikos, Ecole Centrale de Paris, France Kuno Yoshinori, Saitama University, Japan Lee Seong-Whan, Korea University, Korea Leung Valerie, Kingston University, UK Li Wenjing, STI Medical Systems, USA Liu Jianzhuang, The Chinese University of Hong Kong, Hong Kong Ma Yunqian, Honyewell Labs, USA Maeder Anthony, CSIRO ICT Centre, Australia Maltoni Davide, University of Bologna, Italy Maybank Steve, Birkbeck College, UK Medioni Gerard, University of Southern California, USA Metaxas Dimitris, Rutgers University, USA Miller Ron, Ford Motor Company, USA Mirmehdi Majid, Bristol University, UK Monekosso Dorothy, Kingston University, UK Mueller Klaus, SUNY Stony Brook, USA Mulligan Jeff, NASA Ames Research Center, USA Nait-Charif Hammadi, Bournemouth University, UK Nefian Ara, Intel, USA Nicolescu Mircea, University of Nevada, Reno, USA Nixon Mark, University of Southampton, UK Nolle Lars, The Nottingham Trent University, UK Ntalianis Klimis, National Technical University of Athens, Greece Pantic Maja, Imperial College, UK Papadourakis George, Technological Education Institute, Greece Papanikolopoulos Nikolaos, University of Minnesota, USA Parvin Bharam, Lawerence Berkeley National Lab, USA Pati Peeta Basa, Indian Institute of Science, India Patras Ioannis, Queen Mary University, London, UK Petrakis Euripides, Technical University of Crete, Greece Peyronnet Sylvain, LRDE/EPITA, France Pitas Ioannis, University of Thessaloniki, Greece Porikli Fatih, MERL, USA Prabhakar Salil, DigitalPersona Inc., USA Qian Gang, Arizona State University, USA Regazzoni Carlo, University of Genoa, Italy Remagnino Paolo, Kingston University, UK Ribeiro Eraldo, Florida Institute of Technology, USA
IX
X
Organization
Ross Arun, West Virginia University, USA Schaefer Gerald, Aston University, UK Shi Pengcheng, The Hong Kong University of Science and Technology, Hong Kong Salgian Andrea, The College of New Jersey, USA Samir Tamer, Ingersoll Rand Security Technologies, USA Sarti Augusto, DEI, Politecnico di Milano, Italy Scalzo Fabien, University of Nevada, Reno, USA Shah Mubarak, University of Central Florida, USA Singh Rahul, San Francisco State University, USA Skurikhin Alexei, Los Alamos National Laboratory, USA Sturm Peter, INRIA Rhˆ one-Alpes, France Su Chung-Yen, National Taiwan Normal University, Taiwan Sugihara Kokichi, University of Tokyo, Japan Sun Zehang, eTreppid Technologies, USA Teoh Eam Khwang, Nanyang Technological University, Singapore Thiran Jean-Philippe, EPFL, Switzerland Tobin Kenneth, Oak Ridge National Laboratory, USA Triesch Jochen, Frankfurt Institute for Advanced Studies, Germany Tsechpenakis Gabriel, University of Miami, USA Tsotsos John, York University, Canada Tubaro Stefano, DEI, Politecnico di Milano, Italy Velastin Sergio, Kingston University London, UK Veropoulos Kostas, Desert Research Institute, USA Verri Alessandro, Universita’ di Genova, Italy Wang Song, University of South Carolina, USA Wang Junxian, UtopiaCompression, USA Wang Yunhong, Chinese Academy of Sciences, China Webster Michael, University of Nevada, Reno, USA Wolff Larry, Equinox Corporation, USA Wong Kenneth, University of Hong Kong, Hong Kong Xiang Tao, Queen Mary, University of London, UK Xu Meihe, University of California at Los Angeles, USA Yau Wei-Yun, Institute for Infocomm Research, Singapore Yeasin Mohammed, Memphis University, USA Yi Lijun, SUNY at Binghampton, USA Yuan Chunrong, University of Tuebingen, Germany Zhang Yan, Delphi Corporation, USA
Computer Graphics (Area 2) Arns Laura, Purdue University, USA Baciu George, Hong Kong PolyU, Hong Kong Barneva Reneta, State University of New York, USA Bartoli Vilanova Anna, Eindhoven University of Technology, Netherlands
Organization
Belyaev Alexander, Max-Planck-Institut fuer Informatik, Germany Bilalis Nicholas, Technical University of Crete, Greece Bohez Erik, Asian Institute of Technology, Thailand Bouatouch Kadi, University of Rennes I, IRISA, France Brady Rachael, Duke University, USA Brimkov Valentin, State University of New York, USA Brown Ross, Queensland University of Technology, Australia Cheng Irene, University of Alberta, Canada Choi Min, University of Colorado at Denver, USA Cremer Jim, University of Iowa, USA Crosa Pere Brunet, Universitat Polit`ecnica de Catalunya, Spain Damiand Guillaume, SIC Laboratory, France Dingliana John, Trinity College, Ireland Fiorio Christophe, LIRMM, France Floriani Leila De, University of Maryland, USA Gaither Kelly, University of Texas at Austin, USA Geiger Christian, Duesseldorf University of Applied Sciences, Germany Grller Eduard, Vienna University of Technology, Austria Gu David, State University of New York at Stony Brook, USA Hadwiger Helmut Markus, VRVis Research Center, Austria Haller Michael, Upper Austria University of Applied Sciences, Austria Hamza-Lup Felix, Armstrong Atlantic State University, USA Hernandez Jose Tiberio, Universidad de los Andes, Colombia Hinkenjan Andre, Bonn-Rhein-Sieg University of Applied Sciences, Germany Huang Zhiyong, Institute for Infocomm Research, Singapore Julier Simon J., University College London, UK Kakadiaris Ioannis, University of Houston, USA Kamberov George, Stevens Institute of Technology, USA Klosowski James, IBM T.J. Watson Research Center, USA Kobbelt Leif, RWTH Aachen, Germany Lee Seungyong, Pohang Univ. of Sci. and Tech. (POSTECH), Korea Lok Benjamin, University of Florida, USA Loviscach Jorn, University of Applied Sciences, Bremen, Germany Martin Ralph, Cardiff University, UK Meenakshisundaram Gopi, University of California-Irvine, USA Mendoza Cesar, NaturalMotion Ltd., USA Metaxas Dimitris, Rutgers University, USA Monroe Laura, Los Alamos National Lab, USA Nait-Charif Hammadi, University of Dundee, Scotland Noma Tsukasa, Kyushu Institute of Technology, Japan Oliveira Manuel M., Univ. Fed. do Rio Grande do Sul, Brazil Pajarola Renato, University of Zurich, Switzerland Palanque Philippe, University of Paul Sabatier, France Pascucci Valerio, Lawrence Livermore National Laboratory, USA Pattanaik Sumanta, University of Central Florida, USA
XI
XII
Organization
Peters Jorg, University of Florida, USA Qin Hong, State University of New York at Stony Brook, USA Renner Gabor, Computer and Automation Research Institute, Hungary Sapidis Nickolas, Aegean University, Greece Sarfraz Muhammad, King Fahd University of Petroleum and Minerals, Saudi Arabia Schaefer Scott, Texas A&M University, USA Sequin Carlo, University of California-Berkeley, USA Shamir Arik, The Interdisciplinary Center, Herzliya, Israel Silva Claudio, University of Utah, USA Snoeyink Jack, University of North Carolina at Chapel Hill, USA Sourin Alexei, Nanyang Technological University, Singapore Teschner Matthias, University of Freiburg, Germany Umlauf Georg, University of Kaiserslautern, Germany Vinacua Alvar, Universitat Polit`ecnica de Catalunya, Spain Wald Ingo, University of Utah, USA Weinkauf Tino, ZIB Berlin, Germany Wylie Brian, Sandia National Laboratory, USA Ye Duan, University of Missouri-Columbia, USA Yin Lijun, Binghamton University, USA Yuan Xiaoru, University of Minnesota, USA
Virtual Reality (Area 3) Alca˜ niz Mariano, Technical University of Valencia, Spain Arns Laura, Purdue University, USA Behringer Reinhold, Leeds Metropolitan University UK Benesa Bedrich, Purdue University, USA Bilalis Nicholas, Technical University of Crete, Greece Blach Roland, Fraunhofer Institute for Industrial Engineering, Germany Boyle Richard, NASA Ames Research Center, USA Brega Jos Remo Ferreira, UNIVEM, PPGCC, Brazil Brown Ross, Queensland University of Technology, Australia Chen Jian, Brown University, USA Cheng Irene, University of Alberta, Canada Craig Alan, NCSA University of Illinois at Urbana-Champaign, USA Cremer Jim, University of Iowa, USA Crosa Pere Brunet, Universitat Polit`ecnica de Catalunya, Spain Encarnacao L. Miguel, Imedia Labs, USA Figueroa Pablo, Universidad de los Andes, Colombia Froehlich Bernd, University of Weimar, Germany Geiger Christian, Duesseldorf University of Applied Sciences, Germany Gupta Satyandra K., University of Maryland, USA Haller Michael, FH Hagenberg, Austria Hamza-Lup Felix, Armstrong Atlantic State University, USA
Organization
XIII
Harders Matthias, ETH Zuerich, Switzerland Hinkenjan Andre, Bonn-Rhein-Sieg University of Applied Sciences, Germany Julier Simon J., University College London, UK Klosowski James, IBM T.J. Watson Research Center, USA Liere Robert van, CWI, Netherlands Lindt Irma, Fraunhofer FIT, Germany Lok Benjamin, University of Florida, USA Molineros Jose, Teledyne Scientific and Imaging, USA Monroe Laura, Los Alamos National Lab, USA Muller Stefan, University of Koblenz, Germany Paelke Volker, Leibniz Universit¨ at Hannover, Germany Peli Eli, Harvard University, USA Qian Gang, Arizona State University, USA Reiners Dirk, University of Louisiana, USA Rizzo Albert, University of Southern California, USA Rodello Ildeberto, UNIVEM, PPGCC, Brazil Rolland Jannick, University of Central Florida, USA Santhanam Anand, MD Anderson Cancer Center Orlando, USA Sapidis Nickolas, Aegean University, Greece Schmalstieg Dieter, Graz University of Technology, Austria Sourin Alexei, Nanyang Technological University, Singapore Srikanth Manohar, Indian Institute of Science, India Stefani Oliver, COAT-Basel, Switzerland Varsamidis Thomas, University of Wales, UK Wald Ingo, University of Utah, USA Yu Ka Chun, Denver Museum of Nature and Science, USA Yuan Chunrong, University of Tuebingen, Germany Zachmann Gabriel, Clausthal University, Germany Zyda Michael, University of Southern California, USA
Visualization (Area 4) Apperley Mark, University of Waikato, New Zealand Arns Laura, Purdue University, USA Avila Lisa, Kitware, USA Balzs Csbfalvi, Budapest University of Technology and Economics, Hungary Bartoli Anna Vilanova, Eindhoven University of Technology, Netherlands Bilalis Nicholas, Technical University of Crete, Greece Brodlie Ken, University of Leeds, UK Brown Ross, Queensland University of Technology, Australia Chen Jian, Brown University, USA Cheng Irene, University of Alberta, Canada Crosa Pere Brunet, Universitat Polit`ecnica de Catalunya, Spain Doleisch Helmut, VRVis Research Center, Austria Duan Ye, University of Missouri-Columbia, USA
XIV
Organization
Encarnasao James Miguel, Imedia Labs, USA Ertl Thomas, University of Stuttgart, Germany Floriani Leila De, University of Maryland, USA Fujishiro Issei, Tohoku University, Japan Geiger Christian, Duesseldorf University of Applied Sciences, Germany Grller Eduard, Vienna University of Technology, Austria Goebel Randy, University of Alberta, Canada Hadwiger Helmut Markus, VRVis Research Center, Austria Hamza-Lup Felix, Armstrong Atlantic State University, USA Julier Simon J., University College London, UK Koracin Darko, Desert Research Institute, USA Liere Robert van, CWI, Netherlands Lim Ik Soo, University of Wales, UK Ma Kwan-Liu, University of California-Davis, USA Maeder Anthony, CSIRO ICT Centre, Australia Malpica Jose, Alcala University, Spain Masutani Yoshitaka, The University of Tokyo Hospital, Japan Melanon Guy, INRIA Futurs and CNRS UMR 5506 LIRMM, France Monroe Laura, Los Alamos National Lab, USA Mueller Klaus, SUNY Stony Brook, USA Paelke Volker, Leibniz Universit¨ at Hannover, Germany Preim Bernhard, Otto-von-Guericke University, Germany Rabin Robert, University of Wisconsin at Madison, USA Rhyne Theresa-Marie, North Carolina State University, USA Rolland Jannick, University of Central Florida, USA Santhanam Anand, MD Anderson Cancer Center Orlando, USA Scheuermann Gerik, University of Leipzig, Germany Shen Han-Wei, Ohio State University, USA Silva Claudio, University of Utah, USA Snoeyink Jack, University of North Carolina at Chapel Hill, USA Sourin Alexei, Nanyang Technological University, Singapore Theisel Holger, Max-Planck Institut f¨ ur Informatik, Germany Thiele Olaf, University of Mannheim, Germany Tory Melanie, University of Victoria, Canada Umlauf Georg, University of Kaiserslautern, Germany Viegas Fernanda, IBM, USA Viola Ivan, University of Bergen, Norway Wald Ingo, University of Utah, USA Wylie Brian, Sandia National Laboratory, USA Yeasin Mohammed, Memphis University, USA Yuan Xiaoru, University of Minnesota, USA Zachmann Gabriel, Clausthal University, Germany Zhukov Leonid, Caltech, USA
Organization
XV
ISVC 2007 Special Tracks Intelligent Algorithms for Smart Monitoring of Complex Environments Organizers Paolo Remagnino, DIRC, Kingston University, UK How-Lung Eng, IIR, Singapore Guoliang Fan, Oklahoma State University, USA Yunqian Ma, Honeywell Labs, USA Dorothy Monekosso, DIRC, Kingston University, UK Yau Wei Yun, IIR, Singapore
Object Recognition Organizers Andrea Salgian, The College of New Jersey, USA Fabien Scalzo, University of Nevada, Reno, USA Program Committee Boris Epshtein, The Weizmann Institute of Science, Israel Bastian Leibe, ETH Zurich, Switzerland Bogdan Matei, Sarnoff Corporation, USA Raphael Maree, Universit´e de Li`ege, Belgium Randal Nelson, University of Rochester, USA Justus Piater, Universit´e de Li`ege, Belgium Nicu Sebe, University of Amsterdam, Netherlands Bill Triggs, INRIA, France Tinne Tuytelaars, Katholieke Universiteit Leuven, Belgium
Image Databases Organizers Sanjiv K. Bhatia, University of Missouri-St. Louis, USA Ashok Samal, University of Missouri-St. Louis, USA Bedrich Benes, Purdue University, USA Sharlee Climer, Washington University in St. Louis, USA
XVI
Organization
Algorithms for the Understanding of Dynamics in Complex and Cluttered Scenes Organizers Paolo Remagnino, DIRC, Kingston University, UK Fatih Porikli, MERL, USA Larry Davis, University of Maryland, USA Massimo Piccardi, University of Technology Sydney, Australia Program Committee Rita Cucchiara, University of Modena, Italy Gian Luca Foresti, University of Udine, Italy Yoshinori Kuno, Saitama University, Japan Mohan Trivedi, University of California, San Diego, USA Andrea Prati, University of Modena, Italy Carlo Regazzoni, University of Genoa, Italy Graeme Jones, Kingston University, UK Steve Maybank, Birkbeck University of London, UK Ram Nevatia, University of Southern California, USA Sergio Velastin, Kingston University, USA Monique Thonnat, INRIA, Sophia Antipolis, France Tieniu Tan, National Lab of Pattern Recognition, China James Ferryman, Reading University, UK Andrea Cavallaro, Queen Mary, University of London, UK Klaus Diepold, University of Technology in Munich, Germany
Medical Data Analysis Organizers Irene Cheng, University of Alberta, Canada Guido Gortelazzo, University of Padova, Italy Kostas Daniilidis, University of Pennsylvania, USA Pablo Figueroa, Universidad de los Andes, Columbia Tom Malzbender, Hewlett Packard Lab., USA Mrinal Mandal, University of Alberta, USA Lijun Yin, SUNY at Binghamton, USA Karel Zuiderveld, Vital Images Inc., USA Program Committee Walter Bischof, University of Alberta, Canada Anup Basu, University of Alberta, Canada Paul Major, University of Alberta, Canada
Organization
XVII
Tarek El-Bialy, University of Alberta, Canada Jana Carlos Flores, University of Alberta, Canada Randy Goebel, University of Alberta, Canada David Hatcher, DDI Central Corp., USA Shoo Lee, iCARE, Capital Health, Canada Jiambo Shi, University of Pennsylvania, USA Garnette Sutherland, University of Calgary, Canada
Soft Computing in Image Processing and Computer Vision Organizers Gerald Schaefer, Nottingham Trent University, UK Mike Nachtegael, Ghent University, Belgium Lars Nolle, Nottingham Trent University, UK Etienne Kerre, Ghent University, Belgium
Additional Reviewers Leandro A. F. Ferndandes Erik Murphy-Chutorian Tarak Gandhi Florian Mannuss Daniel Patel Mark Keck
XVIII
Organization
Organizing Institutions and Sponsors
Table of Contents – Part II
Motion and Tracking II Visible and Infrared Sensors Fusion by Matching Feature Points of Foreground Blobs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Pier-Luc St-Onge and Guillaume-Alexandre Bilodeau
1
Multiple Combined Constraints for Optical Flow Estimation. . . . . . . . . . . Ahmed Fahad and Tim Morris
11
Combining Models of Pose and Dynamics for Human Motion Recognition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Roman Filipovych and Eraldo Ribeiro
21
Optical Flow and Total Least Squares Solution for Multi-scale Data in an Over-Determined System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Homa Fashandi, Reza Fazel-Rezai, and Stephen Pistorius
33
A Hardware-Friendly Adaptive Tensor Based Optical Flow Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Zhao-Yi Wei, Dah-Jye Lee, and Brent E. Nelson
43
Segmentation/Feature Extraction/Classification Image Segmentation That Optimizes Global Homogeneity in a Variational Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Wei Wang and Ronald Chung
52
Image and Volume Segmentation by Water Flow . . . . . . . . . . . . . . . . . . . . . Xin U. Liu and Mark S. Nixon
62
A Novel Hierarchical Technique for Range Segmentation of Large Building Exteriors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Reyhaneh Hesami, Alireza Bab-Hadiashar, and Reza Hosseinnezhad
75
Lip Contour Segmentation Using Kernel Methods and Level Sets . . . . . . . A. Khan, W. Christmas, and J. Kittler
86
A Robust Two Level Classification Algorithm for Text Localization in Documents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . R. Kandan, Nirup Kumar Reddy, K.R. Arvind, and A.G. Ramakrishnan Image Classification from Small Sample, with Distance Learning and Feature Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Daphna Weinshall and Lior Zamir
96
106
XX
Table of Contents – Part II
ST1: Intelligent Algorithms for Smart Monitoring of Complex Environments Comparison of Techniques for Mitigating the Effects of Illumination Variations on the Appearance of Human Targets . . . . . . . . . . . . . . . . . . . . . C. Madden, M. Piccardi, and S. Zuffi
116
Scene Context Modeling for Foreground Detection from a Scene in Remote Monitoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Liyuan Li, Xinguo Yu, and Weimin Huang
128
Recognition of Household Objects by Service Robots Through Interactive and Autonomous Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Al Mansur, Katsutoshi Sakata, and Yoshinori Kuno
140
Motion Projection for Floating Object Detection . . . . . . . . . . . . . . . . . . . . . Zhao-Yi Wei, Dah-Jye Lee, David Jilk, and Robert Schoenberger
152
Real-Time Subspace-Based Background Modeling Using Multi-channel Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bohyung Han and Ramesh Jain
162
A Vision-Based Architecture for Intent Recognition . . . . . . . . . . . . . . . . . . Alireza Tavakkoli, Richard Kelley, Christopher King, Mircea Nicolescu, Monica Nicolescu, and George Bebis
173
Shape/Recognition Combinatorial Shape Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ralf Juengling and Melanie Mitchell
183
Rotation-Invariant Texture Recognition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Javier A. Montoya-Zegarra, Jo˜ ao P. Papa, Neucimar J. Leite, Ricardo da Silva Torres, and Alexandre X. Falc˜ ao
193
A New Set of Normalized Geometric Moments Based on Schlick’s Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ramakrishnan Mukundan
205
Shape Evolution Driven by a Perceptually Motivated Measure . . . . . . . . . Sergej Lewin, Xiaoyi Jiang, and Achim Clausing
214
The Global-Local Transformation for Invariant Shape Representation . . . Konstantinos A. Raftopoulos and Stefanos D. Kollias
224
A Vision System for Recognizing Objects in Complex Real Images . . . . . Mohammad Reza Daliri, Walter Vanzella, and Vincent Torre
234
ST3: Image Databases RISE-SIMR: A Robust Image Search Engine for Satellite Image Matching and Retrieval . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sanjiv K. Bhatia, Ashok Samal, and Prasanth Vadlamani
245
Table of Contents – Part II
XXI
Content-Based Image Retrieval Using Shape and Depth from an Engineering Database . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Amit Jain, Ramanathan Muthuganapathy, and Karthik Ramani
255
Automatic Image Representation for Content-Based Access to Personal Photo Album . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Edoardo Ardizzone, Marco La Cascia, and Filippo Vella
265
Geographic Image Retrieval Using Interest Point Descriptors . . . . . . . . . . Shawn Newsam and Yang Yang
275
ST6: Soft Computing in Image Processing and Computer Vision Feed Forward Genetic Image Network: Toward Efficient Automatic Construction of Image Processing Algorithm . . . . . . . . . . . . . . . . . . . . . . . . Shinichi Shirakawa and Tomoharu Nagao
287
Neural Networks for Exudate Detection in Retinal Images . . . . . . . . . . . . . Gerald Schaefer and Edmond Leung
298
Kernel Fusion for Image Classification Using Fuzzy Structural Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Emanuel Aldea, Geoffroy Fouquier, Jamal Atif, and Isabelle Bloch
307
A Genetic Approach to Training Support Vector Data Descriptors for Background Modeling in Video Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Alireza Tavakkoli, Amol Ambardekar, Mircea Nicolescu, and Sushil Louis
318
Video Sequence Querying Using Clustering of Objects’ Appearance Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Yunqian Ma, Ben Miller, and Isaac Cohen
328
Learning to Recognize Complex Actions Using Conditional Random Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Christopher I. Connolly
340
Poster Intrinsic Images by Fisher Linear Discriminant . . . . . . . . . . . . . . . . . . . . . . Qiang He and Chee-Hung Henry Chu
349
Shape-from-Shading Algorithm for Oblique Light Source . . . . . . . . . . . . . . Osamu Ikeda
357
Pedestrian Tracking from a Moving Host Using Corner Points . . . . . . . . . Mirko Meuter, Dennis M¨ uller, Stefan M¨ uller-Schneiders, Uri Iurgel, Su-Birm Park, and Anton Kummert
367
XXII
Table of Contents – Part II
3D Reconstruction and Pose Determination of the Cutting Tool from a Single View . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Xi Zhang, Xiaodong Tian, Kazuo Yamazaki, and Makoto Fujishima
377
Playfield and Ball Detection in Soccer Video . . . . . . . . . . . . . . . . . . . . . . . . Junqing Yu, Yang Tang, Zhifang Wang, and Lejiang Shi
387
Single-View Matching Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Klas Nordberg
397
A 3D Face Recognition Algorithm Based on Nonuniform Re-sampling Correspondence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Yanfeng Sun, Jun Wang, and Baocai Yin
407
A Novel Approach for Storm Detection Based on 3-D Radar Image Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Lei Han, Hong-Qing Wang, Li-Feng Zhao, and Sheng-Xue Fu
417
A New Approach for Vehicle Detection in Congested Traffic Scenes Based on Strong Shadow Segmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ehsan Adeli Mosabbeb, Maryam Sadeghi, and Mahmoud Fathy
427
A Robust Method for Near Infrared Face Recognition Based on Extended Local Binary Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Di Huang, Yunhong Wang, and Yiding Wang
437
Surface Signature-Based Method for Modeling and Recognizing Free-Form Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . H.B. Darbandi, M.R. Ito, and J. Little
447
Integrating Vision and Language: Semantic Description of Traffic Events from Image Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Takashi Hirano, Shogo Yoneyama, Yasuhiro Okada, and Yukio Kosugi Rule-Based Multiple Object Tracking for Traffic Surveillance Using Collaborative Background Extraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Xiaoyuan Su, Taghi M. Khoshgoftaar, Xingquan Zhu, and Andres Folleco
459
469
A Novel Approach for Iris Recognition Using Local Edge Patterns . . . . . . Jen-Chun Lee, Ping S. Huang, Chien-Ping Chang, and Te-Ming Tu
479
Automated Trimmed Iterative Closest Point Algorithm . . . . . . . . . . . . . . . R. Synave, P. Desbarats, and S. Gueorguieva
489
Classification of High Resolution Satellite Images Using Texture from the Panchromatic Band . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mar´ıa C. Alonso, Mar´ıa A. Sanz, and Jos´e A. Malpica
499
Table of Contents – Part II
XXIII
Deriving a Priori Co-occurrence Probability Estimates for Object Recognition from Social Networks and Text Processing . . . . . . . . . . . . . . . Guillaume Pitel, Christophe Millet, and Gregory Grefenstette
509
3D Face Reconstruction Under Imperfect Tracking Circumstances Using Shape Model Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . H. Fang and N.P. Costen
519
A Combined Statistical-Structural Strategy for Alphanumeric Recognition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . N. Thome and A. Vacavant
529
The Multiplicative Path Toward Prior-Shape Guided Active Contour for Object Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Wei Wang and Ronald Chung
539
On Shape-Mediated Enrolment in Ear Biometrics . . . . . . . . . . . . . . . . . . . . Banafshe Arbab-Zavar and Mark S. Nixon
549
Determining Efficient Scan-Patterns for 3-D Object Recognition Using Spin Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Stephan Matzka, Yvan R. Petillot, and Andrew M. Wallace
559
A Comparison of Fast Level Set-Like Algorithms for Image Segmentation in Fluorescence Microscopy . . . . . . . . . . . . . . . . . . . . . . . . . . . Martin Maˇska, Jan Huben´ y, David Svoboda, and Michal Kozubek
571
Texture-Based Objects Recognition for Vehicle Environment Perception Using a Multiband Camera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Yousun Kang, Kiyosumi Kidono, Yoshikatsu Kimura, and Yoshiki Ninomiya
582
Object Tracking Via Uncertainty Minimization . . . . . . . . . . . . . . . . . . . . . . Albert Akhriev
592
Detection of a Speaker in Video by Combined Analysis of Speech Sound and Mouth Movement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Osamu Ikeda
602
Extraction of Cartographic Features from a High Resolution Satellite Image . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Jos´e A. Malpica, Juan B. Mena, and Francisco J. Gonz´ alez-Matesanz
611
Expression Mimicking: From 2D Monocular Sequences to 3D Animations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Charlotte Ghys, Maxime Taron, Nikos Paragios, Nikos Komodakis, and B´en´edicte Bascle Object Recognition: A Focused Vision Based Approach . . . . . . . . . . . . . . . Noel Trujillo, Roland Chapuis, Frederic Chausse, and Michel Naranjo
621
631
XXIV
Table of Contents – Part II
A Robust Image Segmentation Model Based on Integrated Square Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Shuisheng Xie, Jundong Liu, Darlene Berryman, Edward List, Charles Smith, and Hima Chebrolu
643
Measuring Effective Data Visualization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ying Zhu
652
Automatic Inspection of Tobacco Leaves Based on MRF Image Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Yinhui Zhang, Yunsheng Zhang, Zifen He, and Xiangyang Tang
662
A Mesh Meaningful Segmentation Algorithm Using Skeleton and Minima-Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Zhi-Quan Cheng, Kai Xu, Bao Li, Yan-Zhen Wang, Gang Dang, and Shi-Yao Jin
671
Fast kd -Tree Construction for 3D-rendering Algorithms Like Ray Tracing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sajid Hussain and H˚ akan Grahn
681
Phase Space Rendering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Andr´e Hinkenjann and Thorsten Roth
691
Automatic Extraction of a Quadrilateral Network of NURBS Patches from Range Data Using Evolutionary Strategies . . . . . . . . . . . . . . . . . . . . . John William Branch, Flavio Prieto, and Pierre Boulanger
701
ChipViz : Visualizing Memory Chip Test Data . . . . . . . . . . . . . . . . . . . . . . . Amit P. Sawant, Ravi Raina, and Christopher G. Healey
711
Enhanced Visual Experience and Archival Reusability in Personalized Search Based on Modified Spider Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . Dhruba J. Baishya
721
Probe-It! Visualization Support for Provenance . . . . . . . . . . . . . . . . . . . . . . Nicholas Del Rio and Paulo Pinheiro da Silva
732
Portable Projection-Based AR System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Jihyun Oh, Byung-Kuk Seo, Moon-Hyun Lee, Hanhoon Park, and Jong-Il Park
742
Adaptive Chrominance Correction for a Projector Considering Image and Screen Color . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sun Hee Park, Sejung Yang, and Byung-Uk Lee
751
Easying MR Development with Eclipse and InTml . . . . . . . . . . . . . . . . . . . Pablo Figueroa and Camilo Florez
760
Table of Contents – Part II
XXV
Unsupervised Intrusion Detection Using Color Images . . . . . . . . . . . . . . . . Grant Cermak and Karl Keyzer
770
Pose Sampling for Efficient Model-Based Recognition . . . . . . . . . . . . . . . . . Clark F. Olson
781
Video Segmentation for Markerless Motion Capture in Unconstrained Environments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Martin Cˆ ot´e, Pierre Payeur, and Gilles Comeau
791
Hardware-Accelerated Volume Rendering for Real-Time Medical Data Visualization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Rui Shen and Pierre Boulanger
801
Fuzzy Morphology for Edge Detection and Segmentation . . . . . . . . . . . . . . Atif Bin Mansoor, Ajmal S. Mian, Adil Khan, and Shoab A. Khan
811
Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
823
Visible and Infrared Sensors Fusion by Matching Feature Points of Foreground Blobs Pier-Luc St-Onge and Guillaume-Alexandre Bilodeau ´ LITIV, Department of Computer Engineering, Ecole Polytechnique de Montr´eal, P.O. Box 6079, Station Centre-ville Montr´eal (Qu´ebec), Canada, H3C 3A7 {pier-luc.st-onge,guillaume-alexandre.bilodeau}@polymtl.ca
Abstract. Foreground blobs in a mixed stereo pair of videos (visible and infrared sensors) allow a coarse evaluation of the distances between each blob and the uncalibrated cameras. The main goals of this work are to find common feature points in each type of image and to create pairs of corresponding points in order to obtain coarse positionning of blobs in space. Feature points are found by two methods: the skeleton and the Discrete Curve Evolution (DCE) algorithm. For each method, a featurebased algorithm creates the pairs of points. Blob pairing can help to create those pairs of points. Finally, a RANSAC algorithm filters all pairs of points in order to respect the epipolar geometrical constraints. The median horizontal disparities for each pair of blobs are evaluated with two different ground truths. In most cases, the nearest blob is detected and disparities are as accurate as the background subtraction allows.
1
Introduction
By watching a calibrated rectified stereo pair1 , a human visual system is able to reconstruct the scene in 3D. But if we use a camera for the visible spectrum and another for the infrared spectrum, images from both cameras have different colors and textures, and the human visual system is just not able to reconstruct the scene. Fortunately, a computer can do it with the proper image processing. In the recent years, infrared cameras are more affordable than ever [1]. By being more accessible, they are used in applications like video surveillance. In fact, while there could be some occlusions or false alarms in the visible spectrum, the infrared spectrum could possibly resolve these problems [2], [3]. While this is not the goal of the present research, it illustrates one of the advantages of combining visible and infrared informations. Another advantage is to exploit the two cameras to enable the evaluation of which person is farther and which person is closer. In a context of video surveillance, this could be very useful to identify and prevent crimes or strange behaviors. In the literature, some algorithms can create dense disparity maps from two visible rectified stereo images [4]. Some other algorithms use uncalibrated infrared stereo images to create a sparse or dense disparity map [1], [5]. Unfortunatly, these methods are not useful as the corresponding points are featured 1
There is a line by line correspondence in rectified stereo pairs.
G. Bebis et al. (Eds.): ISVC 2007, Part II, LNCS 4842, pp. 1–10, 2007. c Springer-Verlag Berlin Heidelberg 2007
2
P.-L. St-Onge and G.-A. Bilodeau
with different values in infrared and visible images. As an example, the Phase Congruency algorithm [6] may find reliable feature points in any type of images, but the pairing by correlation product fails to find enough good pairs of points in infrared and visible images. So, color invariant features are needed. Shah and al. ([7]) have used many types of moments to describe feature points of both types of images. While this may work, their method also requires that the stereo pair have minimal disparity, so it is not very useful for the current research. In the case of our research, both cameras are uncalibrated2 . Nevertheless, they have to look approximately at the same vanishing point3 , and they must have about the same up vector and field of view. The cameras are distanced by at least half a meter to get significant differences between disparities. By convention for the rest of the paper, the left and right images are the visible and infrared images respectively. All images are scaled to a resolution of 640x480 after a correction of the lens distortion. The foreground blobs are obtained by a Temporal Averaging algorithm like the one in [8]. Shadows are eliminated as much as possible in the left image. Finally, blobs smaller than 256 pixels of area are deleted. The remaining blobs are the input of our method. The proposed method finds two types of color invariant feature points in each foreground blob: from an approximated skeleton (section 2) and from a simplified implementation of the Discrete Curve Evolution process (section 3). Then, feature points are further described in order to allow the pairing with a correspondence matrix comparing all possible pairs of feature points of the same type (sections 2.2 and 3.2). These are the main contributions of the paper. The outliers are filtered with two successive algorithms presented in section 4: the blob pairs determined with the pairs of points, and a specialized RANSAC algorithm. The calculation of all blobs’ disparity from all remaining pairs of points is defined in section 5. Section 6 contains the experiment details and the results. Finally, the paper ends with our conclusions and suggested improvements.
2
The Skeleton
2.1
Feature Points
In a skeleton interpreted as a tree, the feature points are the vertices that are not connected by two edges (see figure 1). Here are the steps to extract the feature points in each foreground blob: 1. In the blob, delete all holes that are smaller than N pixels of area; 2. Approximate the contour of the blob with the Douglas-Peucker algorithm4 [9]. This algorithm has only one parameter: the accuracy (in pixels); 3. Draw the approximated blob in white on a black binary image; 4. Apply a distance transform [10] on the white region of the binary image; 2 3 4
The internal and external parameters of the stereo system are unknown. In practice, the cameras must look at the same farthest object in the scene. This algorithm, like many others, is already implemented in OpenCV.
Visible and Infrared Sensors Fusion
3
⎛
5.
6. 7. 8.
⎞ −1 −1 −1 With the convolution product, apply the filter ⎝ −1 8 −1 ⎠ on the distance −1 −1 −1 transform result; Apply a threshold to get the first feature points; Use the Prim’s algorithm [11] to get the minimum spanning tree of the complete graph made of all first feature points; In the minimum spanning tree, keep all vertices that do not have two edges.
By default, the accuracy parameter of the Douglas-Peucker algorithm is 2.5 pixels, the parameter N is about 250, and the threshold is about 4. Figure 1 gives an example of the feature points found in each image.
Fig. 1. Two skeletons in the left and right images. The dark grey dots are all points found after the thresholding. The big light grey points are the feature points. The black lines bind the feature points to their neighbors.
2.2
Feature Points Description
All found feature points must be described in order to make pairs of similar points from the stereo images. The pairs are determined with a correspondence matrix containing the totalScores of each possible pair of feature points. Of course, the corresponding points are the ones that have the highest totalScores. The totalScore metric is the sum of four individual metrics that we have defined: totalScore = scoreDist + scoreEucl + scoreEdge + scoreAngl .
(1)
Here is the description of each metric: – By normalizing the distance-transformed blobs to values from zero to one5 , each feature point is described according to its relative distance rd from itself to its blob’s contour. So, the first metric is scoreDist = −|rdl − rdr | , 5
(2)
All values in the distance-transformed image are scaled linearly to values from zero to one.
4
P.-L. St-Onge and G.-A. Bilodeau
where rdl and rdr are the relative distances of the points in a candidate pair. Of course, l means left image, and r means right image. – Being given that the two images have the same size, it is possible to evaluate the distance between the two points. The second metric is the sigmoid scoreEucl =
1 1+
e−3+6d/D
,
(3)
where d is the Euclidean distance in pixels between the two points, and D is the length in pixels of the diagonal of the images. – In the minimum spanning tree, each point in the pair has one or many edges. The number of edges of the left and the right points are nbl and nbr respectively. So, the third metric is 2 if (nbl ≥ 3) = (nbr ≥ 3) scoreEdge = . (4) 0 if not – For each point in a candidate pair, all point’s edges are oriented from the point to its neighbor vertex in its minimum spanning tree. Then, the left point’s oriented edges are compared to the right point’s oriented edges in a correspondence matrix. In this matrix, the score is the cosinus of the angle between two compared edges. The largest is the cosinus, the most the two edges correspond. Being the set of corresponding edges Pe , the fourth metric for the candidate pair of feature points is p∈Pe cos θp , (5) scoreAngl = max(nbl , nbr ) where θp is the angle between the two edges in the pair p.
3 3.1
Discrete Curve Evolution Feature Points
We use the Discrete Curve Evolution (DCE) algorithm described in [12] to keep the most significant points of the contour of each foreground blob. At each iteration of the DCE, instead of removing the complete set Vmin (P i ) from V ertices(P i ) (see [12]), we remove only one vertex v ∈ Vmin (P i ). In this way, we can control how much vertices we want to keep in the final contour. We did not implement the topology preserving DCE process, because we wanted the code to be as simple and fast as possible. The final contours usually have no bad loops. The external contours end with 33 vertices at most (by default). The internal contours for holes larger than 256 pixels of area end with 13 vertices at most (by default). Figure 2 gives an example of the feature points found in each image.
Visible and Infrared Sensors Fusion
5
Fig. 2. Simplified contour of blobs in the left and right images. The black dots are all points found by our DCE implementation.
3.2
Feature Points Description
For the DCE algorithm, the totalScore metric is defined differently: totalScore = scoreK + scoreEucl + scoreAngl .
(6)
As defined in [12], the relevance measure is K(β, l1 , l2 ) =
βl1 l2 , l1 + l2
(7)
where β is the external angle, and li is the length of the ith edge. The metric scoreK is defined as: −|Kl − Kr |
, scoreK = 2 (8) Kl + Kr2 if Kl2 + Kr2 > 0 1 if not where Kl and Kr are the relevance measures of the left and right points respectively. The metrics scoreEucl and scoreAngl are the same as in section 2.2.
4 4.1
Filtering the Pairs of Points Blob Pairs Filter with Centroids
Until now, the previous methods only match points by comparing all points of the left image to the points of the right image. Of course, there are outliers that match points from two foreground blobs that do not correspond. In order to avoid these outliers, we classify each pair of points in bins representing all possible pairs of corresponding blobs; this is another correspondence matrix, and the score is the number of pairs of points. Then, it is quite easy to identify the most probable pairs of blobs. Finally, those pairs of blobs are used to compute again the pairs of points. In fact, not only is there a correspondence matrix
6
P.-L. St-Onge and G.-A. Bilodeau
of totalScores for each pair of blobs, but we can add another metric to both totalScores in sections 2.2 and 3.2. This is done by these steps: 1. Align the left and right blobs according to their centroid; 2. Compute the new displacement d˜ between the left and right points; 3. Align the left and right blobs in order to get the minimal bounding box that contains them; 4. If the horizontal displacement of d˜ in absolute is less than a quarter of the width of the minimal bounding box, than add 1.0 to the totalScore. 5. If the vertical displacement of d˜ in absolute is less than a quarter of the height of the minimal bounding box, than add 1.0 to the totalScore. By using this additional metric, we are able to get rid of some outliers that may link, for example, the head of a person to his foot (see figure 4). This is why the adaptive thresholds for d˜ are the quarter of the maximal width and height of both corresponding blobs. Finally, d˜ is not used in equation 3. 4.2
Epipolar Geometrical Constraint
According to [1], the epipolar geometrical constraint is represented by the equation 9, where F is the fundamental matrix, xl = (xl , yl , 1)T is a left point and xr = (xr , yr , 1)T is the corresponding right point. xTr F xl = 0
(9)
Even after applying the blob pairs filter, there are still outliers. It is almost impossible to find a fundamental matrix F such that the equation 9 stays true for all pairs of points. Fortunately, a specialized RANSAC algorithm6 can eliminate those outliers while accepting matric products that are not exactly zero [13]. The remaining pairs of points can be used to compute the blobs’ disparity in order to evaluate the relative distance between the blobs and the cameras.
5
Blobs’ Disparity
For each known pair of blobs, all its pairs of feature points are grouped together. Within a group of pairs of points, one must compute the median horizontal displacement. At this stage, there are still some outliers. This is why it is preferable to use the median instead of the mean value. Because the up vector and the field of view of both cameras are about the same, it is more interesting to focus on the horizontal displacement instead of the complete vectorial displacement. Finally, the absolute value of the median horizontal displacement is the blob pair’s disparity value. The figure 3 is an example of a final render. 6
We used the implementation in OpenCV. The default maximum distance is 2.0, and the default confidence level is 0.9.
Visible and Infrared Sensors Fusion
7
Fig. 3. A final output with all filtered pairs of points. Darker blobs are farther than pale blobs.
6 6.1
Experimentation Experiments
The first test evaluates the effect of the filters described in section 4. Then, the other tests evaluate the pairs of points with two types of ground truths: – The first type contains identification number(s) (ID) for each significant blob at each four frames of each video. For each stereo images, the corresponding blobs have the same ID. If one significant blob is merged with another blob, the final foreground blob gets two IDs. Then, if this blob separates, the two resultant blobs get the proper unique ID. If two people are merged in one blob (identified with two IDs) in one image and if they are separated in the other image (one ID for each blob), this makes two pairs of blobs. With this type of ground truth, we are able to classify the pairs of blobs found with our correspondence matrix (see section 4.1): valid pairs, bad pairs (false positives) and missing pairs (false negatives). – The second type contains informations about the distance between each blob and the left camera. The information is a relative distance without any unit. This type of ground gruth is only used to know which blob is farther than the other: it is not yet used to know how accurate are the disparities computed at section 5. The metric is then computed with the following steps: 1. 2. 3. 4. 5.
Put each blob’s disparity in the vector α ; Put each blob’s ground truth relative distance in the vector β ; Do the scalar product γ1 = −α · β ; Sort values in α and in β, and redo the scalar product γ2 = −α · β ; The metric is then κ = γ1 − γ2 .
8
P.-L. St-Onge and G.-A. Bilodeau
The negative sign for γi values is because the disparity values are high when the blobs are close to the camera. If κ is zero, then the order of blobs is perfect. If κ is negative, then it only tells that our program have the wrong estimation of which blob is closer. Finally, all tests are done by using thresholds and parameters proposed earlier in the paper. The sources are two videos of 210 frames, but we have only tested one stereo pair out of four (53 stereo pairs including the first one). The videos are recorded from a Sony DFWSX910 visible camera and a FLIR A40V infrared camera. These cameras are synchronized at 7.5 fps. 6.2
Results
The figure 4 shows the effects of applying the blob pairs filter and the epipolar geometrical constraint. It can be noted that the blob pairs filter helps to avoid coarse errors of pairing. While the RANSAC algorithm filters many outliers, it also gets rid of some inliers: we still have to find the right parameters for this algorithm. Anyway, many of the outliers are caused by the unreliable background subtraction. With a better background subtractor, we expect to get better results. For the following results, both filters are used.
a)
b)
c)
Fig. 4. Visual results when merging all found feature points from the skeleton and the DCE algorithms. In a), no filter is used. In b) and c), the blob pairs filter is activated. Only in c), the RANSAC algorithm is activated. In all three cases, our method properly detects that the two people are not close to each other.
Table 1 shows the results with the first type of ground truth. Most of valid blob pairs have been found, so they are usable in the blob pairs filter. The bad or missing blob pairs are caused by the imperfect background subtraction (figure 5a) or by merged blobs (figure 5c). The skeleton algorithm does slightly less blob pairs errors than the DCE algorithm, probably because the DCE algorithm is more sensitive to the noise in the contour of blobs in the visible images. All these errors could be resolved by a better background subtraction or by a segmentation like in [7]. For the second type of ground truth, we have used each algorithm (skeleton and DCE) alone and then together. For each of these three cases, we got only two wrong ordering for all 53 stereo pairs. All three cases have failed on the
Visible and Infrared Sensors Fusion
9
same stereo pair when both actors are about at the same distance from both cameras. The second error of each case is in different stereo pairs, and is due to their respective outliers (see figure 5b) and the random behavior of the RANSAC algorithm. This is why more tests have to be done to evaluate the accuracy of the disparities. Nevertheless, the examples of figure 4 show that our method is already able to say that the two people are not close to each other, and we are confident that the program is generally able to find which blob is the closest to the cameras. Table 1. For each algorithm, the total number of found, valid, bad and missing pairs of blobs Algorithm Found Valid Bad Missing Skeleton 60 58 2 4 DCE 62 57 5 5
a)
b)
c)
Fig. 5. Visual results of some anomalies. In a), the left actor’s blob was cut in two during the background subtraction; the DCE algorithm and the blob pairs filter retained the smallest piece of blob. In b), too much outliers caused a wrong ordering. In c), the merged blobs caused a missing blob pair.
7
Conclusion
In this work, we address the problem of stereo vision with a visible camera and an infrared camera. We have proposed two methods to find feature points from the foreground blobs: the skeleton and the Discrete Curve Evolution process. The pairs of points have been chosen with a set of metrics for each type of feature point. We have successfully filtered some outliers with the blob pairs. While the RANSAC algorithm needs to be adjusted, it already removes some outliers. Even if the proposed method is not as precise as a dense 3D reconstruction, we are able to identify which blob is the closest to the cameras. In future works, we want to use better background subtraction algorithms. We also want to test all possible parameters to assess the performance of the proposed methods. Of course, other types of feature points will be implemented and tested. Finally, the accuracy of blob disparities has to be tested with a third type of ground truth.
10
P.-L. St-Onge and G.-A. Bilodeau
Acknowledgments We would like to thank the Canadian Foundation for Innovation (CFI) and the Fonds qu´eb´ecois de la recherche sur la nature et les technologies (FQRNT) for their support with a grant and a scholarship respectively.
References 1. Hajebi, K., Zelek, J.S.: Sparse disparity map from uncalibrated infrared stereo images. In: CRV 2006. Proceedings of the 3rd Canadian Conference on Computer and Robot Vision, pp. 17–17 (2006) 2. Jones, G.D., Hodgetts, M.A., Allsop, R.E., Sumpter, N., Vicencio-Silva, M.A.: A novel approach for surveillance using visual and thermal images, 9/1–919 (2001) 3. Ju, H., Bhanu, B.: Detecting moving humans using color and infrared video. In: MFI 2003. Multisensor Fusion and Integration for Intelligent Systems, pp. 228–233 (2003) 4. Zitnick, C.L., Kanade, T.: A cooperative algorithm for stereo matching and occlusion detection. IEEE Transactions on Pattern Analysis and Machine Intelligence 22(7), 675–684 (2000) 5. Hajebi, K., Zelek, J.S.: Dense surface from infrared stereo. In: WACV 2007. Workshop on Applications of Computer Vision, pp. 21–21 (2007) 6. Kovesi, P.: Phase congruency: A low-level image invariant. Psychological Research 64(2), 136–148 (2000) 7. Shah, S., Aggarwal, J.K., Eledath, J., Ghosh, J.: Multisensor integration for scene classification: an experiment in human form detection, vol. 2, pp. 199–202 (1997) 8. Shoushtarian, B., Bez, H.E.: A practical adaptive approach for dynamic background subtraction using an invariant colour model and object tracking. Pattern Recognition Letters 26(1), 5–26 (2005) 9. Douglas, D.H., Peucker, T.K.: Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica: The International Journal for Geographic Information and Geovisualization 10(2), 112–122 (1973) 10. Borgefors, G.: Distance transformations in digital images. Computer Vision, Graphics, and Image Processing 34(3), 344–371 (1986) 11. Cheriton, D., Tarjan, R.E.: Finding minimum spanning trees. SIAM Journal on Computing 5(4), 724–742 (1976) 12. Latecki, L.J., Lakamper, R.: Polygon Evolution by Vertex Deletion. In: Nielsen, M., Johansen, P., Olsen, O.F., Weickert, J. (eds.) Scale-Space Theories in Computer Vision. LNCS, vol. 1682, Springer, Heidelberg (1999) 13. Fischler, M.A., Bolles, R.C.: Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM 24(6), 381–395 (1981)
Multiple Combined Constraints for Optical Flow Estimation Ahmed Fahad and Tim Morris School of Computer Science, The University of Manchester Manchester, M13 9PL, UK
[email protected],
[email protected]
Abstract. Several approaches to optical flow estimation use differential methods to model changes in image brightness over time. In computer vision it is often desirable to over constrain the problem to more precisely determine the solution and enforce robustness. In this paper, two new solutions for optical flow computation are proposed which are based on combining brightness and gradient constraints using more than one quadratic constraint embedded in a robust statistical function. Applying the same set of differential equations to different quadratic error functions produces different results. The two techniques combine the advantages of different constraints to achieve the best results. Experimental comparisons of estimation errors against those of wellknown synthetic ground-truthed test sequences showed good qualitative performance.
1 Introduction Many methods for computing optical flow have been proposed over the years, concentrating on the accuracy and density of velocity estimates. Variational optic flow methods belong to the best performing and best understood methods. The energy functional can be designed in such a way that it preserves motion boundaries, is robust under noise or invariant to illumination changes, it handles large displacements and adapts to occlusion or mismatches. Differential methods allow optic flow estimation based on computing spatial and temporal image derivatives and can be classified into techniques that minimize local or global energy functions. Both methods attempt to overcome the ill-posedness due to the aperture problem where computing the optic flow component is only possible in the direction of intensity gradient, i.e. normal to image edges. Therefore, differential methods use smoothing techniques and smoothness assumptions. Local techniques use spatial constancy assumptions, e.g. in the case of the Lucas-Kanade method [1]. Global techniques supplement the optic flow constraint with a regularizing smoothness, e.g. Horn and Schunck [2]. Combining the different smoothing effects of local and global methods provides the robustness of local methods with the full density of global methods [3]. Extending the optic flow brightness constancy assumption by a gradient constancy assumption yields excellent results at the expense of extra computation [4, 5, 6] G. Bebis et al. (Eds.): ISVC 2007, Part II, LNCS 4842, pp. 11–20, 2007. © Springer-Verlag Berlin Heidelberg 2007
12
A. Fahad and T. Morris
compared to the combined local-global method. Other constancy assumptions are possible, such as the constancy of the Hessian or the Laplacian [7], that reveal certain advantages in comparison to the brightness constancy assumption. The data term of the energy function usually embeds the constancy assumption in a quadratic norm that is nonlinear with respect to motion components. Since this causes problems when minimizing the energy function, first order Taylor expansion is often used to linearize the expression and make solution easier. However, the linear approximation is accurate only if the image gradient changes linearly along the displacement and fails in the presence of large displacements. Coarse-to-fine strategies or multiresolution approaches [3, 8, 9] overcome this limitation by incrementally refining the optic flow from a coarse scale to a finer scale. The coarse scale motion is used to warp the original sequence before going to the next finer level, resulting in a hierarchy of small displacement problems at each level. The final result is obtained by a summation of all motion increments and is more accurate. To compute optical flow robustly, outliers should be penalized less severely. Therefore, robust statistical formulation makes the recovered flow field less sensitive to assumption violations by replacing the quadratic penalizer by nonquadratic penalizers [3, 7, 10, 11]. Although this leads to nonlinear optimization problems, they give better results at locations with flow discontinuities. Currently, the most popular regularizers of optical flow estimation are the variational based isotropic or anisotropic smoothness operators where the latter considers discontinuities at the motion boundaries [12]. Finally, spatiotemporal approaches use the information of an additional dimension to consider spatiotemporal smoothness operators by simply replacing 2D Gaussian convolution with 3D spatiotemporal Gaussian convolution. Spatiotemporal versions of the Horn and Schunck and Combined Local Global (CLG) methods have been proposed [3, 13] where the energy functions are extended by including temporal data (3D). Thus the minimization is understood in a spatiotemporal way over more than two frames. In general, experiments showed that extending the energy function with temporal data obtaining a spatiotemporal formulation give better results than spatial ones [13] because of the additional denoising in the temporal dimension. Over-constraining the optical flow problem allows more precise determination of a solution. Moreover, it uses redundant information to enforce robustness with respect to measurement noise. Constraints can be obtained using several approaches by either applying the same equation to multiple points or defining multiple constraints for each image point [14]. The latter can be obtained by applying a set of differential equations [15] or applying the same set of equations to different functions which are related to image brightness. In this paper, section 2 discusses the main optical flow constraints involved in local and global optic flow approaches and the use of higher image derivatives. Section 3 proposes a novel variational approach that integrates the gradient constraint into different error functions which can be minimized with numerical methods. Based on the results, we extend in section 4 the method with brightness constraint to allow for more competition between the constraints and the use of multiple robust functions. Then section 5 presents mulitresolution techniques that implement warping to correct the original sequence before going to the next finer level by creating a sophisticated hierarchy of equations with excellent error reduction properties. Qualitative experiments using a number of synthetic and real image sequences are presented in section 6 and a summary concludes the paper.
Multiple Combined Constraints for Optical Flow Estimation
13
2 Optical Flow Constraints In this section we derive our variational model for the combined constancy assumptions. Since its formulation is essentially based on the variational optic flow methods we start by giving a short review. Let us consider some image sequence I(x,y,t), where (x,y) denotes the location within a rectangular image domain Ω and t ∈ [0,T ] denotes time. Many differential methods for optic flow are based on the optical flow constraint (OFC) assumption that the brightness values of image objects do not change over time, i.e. constancy of the brightness value:
I (x + u , y + v , t + 1) = I (x , y , t ) ,
I x u + I y v + I t = 0,
(1)
where the displacement u(x,y,t), v(x,y,t) is called the optic flow. For small displacements, we may perform a first order Taylor expansion yielding the optic flow constraint where subscripts denote partial derivatives. In order to cope with the aperture problem (the single OFC equation is not sufficient to uniquely compute the two unknowns u and v), Lucas and Kanade [1] assumed that the unknown optic flow vector is constant within some neighbourhood of size ρ and introduced an equation that can be solved if the system matrix is invertible. Unlike the Lucas-Kanade method which is local, Horn and Schunck [2] introduced a global method that adds a regularization constraint to the energy function to determine the unknown u and v, E HS (u ,v ) =
∫ ( (I
xu
)
+ I y v + I t )2 + α (| ∇u |2 + | ∇v |2 ) dxdy
Ω
(2)
α>0 is a regularization parameter. At locations where no reliable flow estimate is
possible i.e. with the gradient | ∇I |≈ 0 , the regularizer | ∇u |2 + | ∇v |2 fills in information from the neighbourhood which results in completely dense flow fields. The CLG method [3] complements the advantages of both approaches, benefiting from the robustness of local methods with the density of global approaches: E CLG (u ,v ) =
∫ ( K ρ *(I
Ω
xu
)
+ I y v + I t ) 2 + α (| ∇u |2 + | ∇v |2 ) dxdy
(3)
The method also proved robust with respect to parameter variations. Variational methods require the minimization of an energy functional, which, from the discretization of the Euler-Lagrange equations, results in linear or non-linear systems of equations. The large sparse system of equations is minimized iteratively using Gauss-Seidel or Successive Over Relaxation SOR methods. Although the brightness constancy assumption works well, it cannot deal with either local or global changes in illumination. Other constancy assumptions such as the gradient constancy assumption (which assumes the spatial gradients of an image sequence to be constant during motion) are applied [5, 6]. A global change in illumination affects the brightness values of an image by either shifting or scaling or both. Shifting the brightness will not change the gradient; scaling affects the magnitude of the gradient vector but not its direction.
14
A. Fahad and T. Morris
I xx u + I xy v + I xt = 0,
I yx u + I yy v + I yt = 0.
(4)
It is to be noted that the grey value and gradient constancy assumptions yield good results; other higher order constancy assumptions may be applied. One choice including second order derivatives is the Hessian. Not all constancy assumptions based on derivatives perform equally well, neither are they well-suited to estimate different types of motion.
3 Variant Gradient Constraint Formulation The gradient constraint produces two equations with the two unknowns of the optical flow in the spatial domain. Reformulating equation 3 using the gradient constraint produces two energy functions, equations (5) and (6) (we only show the data constraint without the regularization for brevity). One function (eq. (5)) penalizes each data constraint with a quadratic error, and the other one (eq. (6)) penalizes both data constraints with one quadratic error,
∫
(5)
∫
(6)
E data (u ,v ) = (I xx u + I xy v + I xt ) 2 + (I yx u + I yy v + I yt ) 2 dxdy Ω
E data (u ,v ) = ((I xx + I yx )u + (I xy + I yy )v + I xt + I yt ) 2 dxdy Ω
Table 1. shows the results of using both equations to process the Yosemite sequence that has ground truth. The results show that using equation (6) generates results with a smaller average angular error (AAE, which is defined below by equation 14). However, re-formulating the equations by replacing the quadratic error terms by nonquadratic penalizers, where outliers are penalized less severely, produced different results. The reformulated expressions are equations (7) and (8) with their AAE results presented in Table 1.
∫ (
)
∫ (
)
E data (u ,v ) = ψ 1 (I xx u + I xy v + I xt )2 + (I yx u + I yy v + I yt )2 dxdy Ω
E data (u ,v ) = ψ 1 ((I xx + I yx )u + (I xy + I yy )v + I xt + I yt ) 2 dxdy Ω
(7)
(8)
where ψ1(s2) and ψ2(s2) are nonquadratic penalisers. Using these to process the Yosemite sequence gave the results presented in Table 1. We notice equation (7) gave less AAE than equation (8). Furthermore, we analyze the optical flow generated for each pixel looking for smaller angular errors. Figure 1(a) shows two different colours, light and dark gray. Light gray regions represent where equation (7) generated smaller
Multiple Combined Constraints for Optical Flow Estimation
15
angular error than equation (8) and vice versa for dark regions. Obviously, the two energy functions produced different results and neither of them has produced a smaller angular error for all pixels. An explanation for this behaviour can be given as follows. Let us denote e1 to be the error from the x-derivative (Ix) constancy constraint and e2 to be the error from the y-derivative (Iy) constancy. At locations where e1 and e2 are quite small, the smoothing constraint becomes more important making flow fields more regularized which can be noticed in cloudy regions of the sequence having very small gradients. Since e12 + e 22 ≤ (e1 + e 2 )2 for all e1 and e2 both negative and non-negative, thus using one quadratic error gives higher error values making the regularization less important in cloudy regions with very small gradients. On the other hand, balancing between e1 and e2 in equation (7) allows both gradient constancy errors to compete for the best flow field. Hence, it would be interesting to construct a hybrid data constraint that constitutes the best features of the two constraints. Therefore, we propose a new energy function that combines the gradient constraint equations using more than one penalizer, equation (9),
∫ (
)
E data (u ,v ) = ψ 1 (I xx u + I xy v + I xt )2 + (I yx u + I yy v + I yt )2 +
∫ (
ψ 1 ((I xx + I yx )u + (I xy + I yy )v + I xt + I yt ) 2
(9)
)
The new energy function benefits from balancing between the two penalizers. Table 1. Comparison between the different combination of brightness and gradient data constraints used in the energy functions applied to the cloudy Yosemite sequence. The table shows the average angular error between the ground truth and the computed direction of motion.
Frame 6 7 8 9 10
Eq.(5) 6.98 6.43 6.48 6.85 6.56
Eq.(6) 6.71 6.24 6.28 6.65 6.37
Eq.(7) 5.86 5.35 5.35 5.46 5.55
Eq.(8) 6.14 5.67 5.67 5.77 5.87
Eq.(10) 5.54 5.26 5.26 5.37 5.46
Eq.(11) 6.04 5.62 5.62 5.72 5.82
4 A Combined Brightness-Gradient Constraint The previous approaches used only the gradient constancy assumptions. Brox. [5] introduced competition between the brightness constancy and the gradient constancy that produced the best optical flow results by delaying the linearization of constraints. He applied methods from robust statistics where outliers are penalized less severely: E data (u ,v ) =
∫ψ (( I (x +w ,t + 1) − I (x ,t ) ) 1
Ω
2
)
+ γ ( ∇I (x + w , t + 1) − ∇I (x , t ) ) dxdy 2
(10)
16
A. Fahad and T. Morris
Reformulating equation (10) by penalizing both brightness and gradient constancy constraints using one quadratic error and using robust statistics we find, E data (u ,v ) =
∫ψ (( I (x +w ,t + 1) − I (x ,t ) + γ∇I (x +w ,t + 1) − γ∇I (x ,t ) ) ) 2
(11)
1
Ω
Table 1 shows the results of applying both equations to process the Yosemite sequence and comparing the results to the ground truth. The results show a smaller average angular error (AAE) for equation (10) maintaining all other parameters constant. However, figure 1 shows two different regions where small angular errors are found, and no method produced a globally smaller angular error. Therefore, to benefit from the advantages of both energy functions we propose a hybrid data constraint that combines both brightness and gradient constancy constraints,
∫ (
)
E (u ,v ) = ψ 1 BC 2 + γ GCx 2 + γ GCy 2 + (BC + γ GCx + γ GCy ) 2 + Ω
∫ αψ (| ∇u | 2
Ω
2
)
+ | ∇v |2 dxdy
(12)
BC = I x u + I y v + I t , GxC = I xx u + I xy v + I xt , GyC = I yx u + I yy v + I yt
where γ is constant. We notice in the new energy function the competition between three data constancy terms. This competition allows the optical flow field that reaches the minimum by fitting the brightness constancy, the gradient constancy and both brightness and gradient constancy such that each constancy term has one quadratic error.
5 Nonquadratic Implementation and Multiresolution Approach At locations with flow discontinuities, the constancy assumption model for motion analysis may not be capable of determining the optical flow uniquely, especially in homogenous areas or where there are outliers caused by noise, occlusions, or other violations of the constancy assumption. Moreover, the smoothness assumption does not respect discontinuities in the flow field. In order to capture locally non-smooth motion [3, 10] and data outliers [6, 12], it is possible to replace the quadratic penalizer with a nonquadratic penalizer in the energy function. We use a function proposed by [3] where the bias that a particular measurement has on the solution is proportional to the derivative of the penalizer function ψ i (s 2 ) = 2βi 1 + s 2 / βi2 , where the βi arescaling parameters. The energy functional now is not solved using linear optimization methods and is regarded as a nonlinear optimization problem.
Multiple Combined Constraints for Optical Flow Estimation
17
Fig. 1. (a) Light gray areas represent equation (7) holding smaller angular error and dark areas equation (8) holding smaller angular error. (b) The same results for equation (10) and (11).
(
)
(
)
2 2 0 = div ⎛⎜ψ 2' ∇u + ∇v ∇u ⎞⎟ − ⎝ ⎠ 1 ' 2 2 2 2 ψ 1 BC + γ GCx + γ GCy + ( BC + γ GCx + γ GCy ) ( J 11u + J12v + J13 ) ,
α
(
)
2 2 0 = div ⎛⎜ψ 2' ∇u + ∇v ∇v ⎞⎟ − ⎝ ⎠ 1 ' 2 2 2 2 ψ 1 BC + γ GCx + γ GCy + ( BC + γ GCx + γ GCy ) ( J 21u + J 22v + J 23 ) .
α
(
)
(13)
where, 2 2 J 11 = I x2 + I xx + I yx + (I x + I xx + I yx )2
J 12 = J 21 = I x I y + I xx I xy + I yx I yy + (I x + I xx + I yx )(I y + I xy + I yy ). 2 2 J 22 = I y2 + I xy + I yy + (I y + I xy + I yy )2
J 13 = I x I t + I xx I xt + I yx I yt + (I x + I xx + I yx )(I t + I xt + I yt ) J 23 = I y I t + I xy I xt + I yy I yt + (I y + I xy + I yy )(I t + I xt + I yt )
Since we consider linearizing the constancy assumptions, multiscale focusing or multiresolution strategies are required for large motions. These techniques incrementally compute the optic flow based on a sophisticated coarse to fine strategy [3, 9, 11] where the coarsest scale resolution is refined. Then the coarse scale motion is used to warp the original sequence before continuing to the next finer level. This is different from using the estimated flow at the coarse level as initialization for the next finer level which only speeds up the convergence. The final displacement is the sum of all the motion displacement computed at each level, so called motion increments.
6 Experiments In this section, we present the results of testing our algorithm on a variety of synthetic image sequences. Comparisons of our results with the previously reported results are made to demonstrate the performance of our algorithm. We evaluate the
18
A. Fahad and T. Morris
algorithm using the Yosemite sequence with cloudy sky obtained from ftp://ftp.csd.uwo.ca/pub/vision. We compare the average angular error defined by Barron et al. [8] with respect to the ground truth flow field, ⎛ u cue + v cv e + 1 Angular Error = arccos ⎜ ⎜ 2 2 2 2 ⎝ (uc + v c + 1)(u e + v e + 1)
⎞ ⎟ ⎟ ⎠
(14)
where (uc,vc) denotes the correct flow, and (ue,ve) is the estimated flow. Table 2 shows the results of combined gradient constraint using two quadratic errors in equation (9) which reflect better results than using only the gradient constraint with one quadratic error as in Table 1. The reason for this is that the gradient constancy is invariant under brightness changes. This behaviour agrees with the theoretical consideration of Papenberg et al. [7] where higher order terms are superior in areas where illumination changes (the sky region). We fix all the parameters for all energy functions except for the robust function parameters β1 and β2 to values in the range between 1×10-4 5×10-2. Table 2. Average angular errors computed for the cloudy Yosemite sequence for five different frames using two flow computations. Std. Dev.: standard Deviation of AAE.
Yosemite# 6 7 8 9 10
Eq. (9) 5.36 4.85 4.85 4.95 5.05
Std. Dev. 7.30 6.76 6.76 6.74 6.78
Eq.(12) 5.28 4.73 4.72 4.83 4.93
Std. Dev. 7.30 6.73 6.73 6.71 6.75
Table 3. Average angular errors for the Office sequence under varying amounts of added noise. The combined Local-Global approach into the data functions ameliorates the effect of noise, the noise still affects the gradient constraint.
σn 0 5 10 20
Yosemite with Cloud AAE STD 4.82° 6.73° 5.51° 7.74° 6.89° 8.63° 11.59° 11.26°
Office AAE STD 3.20° 4.20° 3.80° 4.39° 4.77° 4.86° 7.09° 6.42°
In another experiment we studied the effect of noise on the robustness of the equations. We added white Gaussian noise to the synthetic Yosemite and Office sequence (www.cs.otago.ac.nz/research/vision/). We can observe in Table 3 that the flow computations using the method suffered a little when severely degraded by Gaussian noise since the functional contains higher order terms. Therefore, in the future, we intend to delay the linearization of the data constraints to avoid such degradation.
Multiple Combined Constraints for Optical Flow Estimation
19
(a)
(b)
(c)
(d)
(e)
(f)
Fig. 2. (a) Frame 8 of the Yosemite sequence with clouds. (b) Ground truth between frame 8 and 9 for the sequence with clouds. (c) Computed flow field by equation 12 for the sequence with clouds. (d) Frame 8 of the Office sequence. (e) Ground truth (f) Computed flow field by equation 12.
7 Conclusion In this paper, we have introduced a combination of constancy assumptions for optic flow computation under local global smoothing effects. The new energy functional data term contains brightness and gradient constancy assumptions. While each of these concepts has before proved its use, we have shown that their combination into different quadratic errors and under smoothing regimes delivers better results. A full multigrid strategy avoids local minima and helps improve the convergence of the solution to a global minimum. We further showed that the improved results come at the price of being more sensitive to noise.
20
A. Fahad and T. Morris
References 1. Lucas, B.D., Kanade, T.: An iterative image registration technique with an application to stereo vision. In: Proceedings of Seventh International Joint Conference on Artificial Intelligence, pp. 674–679 (1981) 2. Horn, B.K.P., Shunck, B.G.: Determining optical flow. Artificial Intelligence 17, 185–203 (1981) 3. Bruhn, A.e., Weickert, J.: Lucas/kanade meets horn/schunck: Combining local and global optic flow methods. International Journal of Computer Vision 16, 211–231 (2005) 4. Uras, S., Girosi, F., Verri, A., Torre, V.: A computational approach to motion perception. Biological Cybernetics 60, 79–87 (1988) 5. Brox, T., Bruhn, A.e., Papenberg, N., Weickert, J.: High accuracy optical flow estimation based on a theory for warping. In: Pajdla, T., Matas, J(G.) (eds.) ECCV 2004. LNCS, vol. 3024, pp. 25–36. Springer, Heidelberg (2004) 6. Rabcewicz, A.: Clg method for optical flow estimation based on gradient constancy assumption. In: International Conference on PDE-Based Image Processing and Related Inverse Problems, pp. 57–66. Springer, Heidelberg (2005) 7. Papenberg, N., Bruhn, A., Brox, T., Didas, S., Weickert, J.: Highly accurate optic flow computation with theoretically justified warping. International Journal of Computer Vision 67, 141–158 (2006) 8. Odobez, J.M., Bouthemy, P.: Robust multiresolution estimation of parametric motion models. International Journal of Visual Communication and Image Representation 6, 348– 365 (1995) 9. Memin, E., Perez, P.: Dense estimation and object-based segmentation of the optical flow with robust techniques. IEEE Transactions on Image Processing 7, 703–719 (1998) 10. Bab-Hadiashar, A., Suter, D.: Robust optic flow computation. International Journal of Computer Vision 29, 59–77 (1998) 11. Black, M.J., Anandan, P.: The robust estimation of multiple motions: Parametric and piecewise-smooth flow fields. Computer Vision and Image Understanding 63, 75–104 (1996) 12. Xiao, J., Cheng, H., Sawhney, H., Rao, C., Isnardi, M.: Bilateral filtering-based optical flow estimation with occlusion detection. In: Leonardis, A., Bischof, H., Pinz, A. (eds.) ECCV 2006. LNCS, vol. 3951, pp. 211–224. Springer, Heidelberg (2006) 13. Barron, J.L., Fleet, D.J., Beauchemin, S.S.: Performance of optical flow techniques. International Journal of Computer Vision 12, 43–77 (1994) 14. Tistarelli, M.: Multiple constraints to compute optical flow. IEEE Transactions on Pattern Analysis and Machine Intelligence 18, 1243–1250 (1996) 15. Bimbo, A.D., Nesi, P., Sanz, J.L.C.: Optical flow computation using extended constraints. IEEE Transactions on Image Processing 5, 720–732 (1996)
Combining Models of Pose and Dynamics for Human Motion Recognition Roman Filipovych and Eraldo Ribeiro Computer Vision and Bio-Inspired Computing Laboratory Department of Computer Sciences Florida Institute of Technology Melbourne, FL 32901, USA {rfilipov,eribeiro}@fit.edu http://www.cs.fit.edu/∼ eribeiro
Abstract. We present a novel method for human motion recognition. A video sequence is represented with a sparse set of spatial and spatialtemporal features by extracting static and dynamic interest points. Our model learns a set of poses along with the dynamics of the sequence. Pose models and the model of motion dynamics are represented as a constellation of static and dynamic parts, respectively. On top of the layer of individual models we build a higher level model that can be described as “constellation of constellation models”. This model encodes the spatial-temporal relationships between the dynamics of the motion and the appearance of individual poses. We test the model on a publicly available action dataset and demonstrate that our new method performs well on the classification tasks. We also perform additional experiments to show how the classification performance can be improved by increasing the number of pose models in our framework.
1
Introduction
Recognizing human actions from videos is of relevance to both the scientific and industrial communities. Humans usually perform actions by means of a number of articulated complex motions. Consequently, creating effective computational models for human motion representation is a crucial but challenging task required to all action recognition algorithms. Despite significant efforts by the computer vision community, action recognition is still an open problem. In general, approaches to human motion recognition work by analyzing the dynamic information of image sequences. Recently, the use of spatial-temporal features has been demonstrated to be an affective tool for motion recognition [18,16]. Additionally, the importance of static information [17] combined with recent advances in probabilistic constellation models [15] have also been demonstrated. In this paper, we focus ourselves on the problem of learning representational models for human motion recognition. More specifically, we propose a Bayesian probabilistic framework that allows for integrating both static and dynamic information. Here, our main contribution is to present a principled solution to the G. Bebis et al. (Eds.): ISVC 2007, Part II, LNCS 4842, pp. 21–32, 2007. c Springer-Verlag Berlin Heidelberg 2007
22
R. Filipovych and E. Ribeiro
human motion recognition problem by combining data of different nature within a single probabilistic integration framework while allowing for computationally efficient learning and inference algorithms. This is accomplished by combining constellation models “tuned” to recognize specific human poses with a constellation model of the motion’s spatial-temporal data to form a single human motion model. Our resulting method can be characterized as a “constellation of constellation models” that combines pose recognition and motion dynamics recognition into a single framework. We demonstrate the effectiveness of the proposed method on a series of motion classification experiments along with a comparison with a recently published motion recognition approach. The results show that our model offers promising classification performance on an established human action dataset. The remainder of this paper is organized as follows. In Section 2, we comment on the literature related to the problem addressed in this paper. Section 3 describes the details of our action recognition framework. In Section 4, we describe experimental results of our method on an established human action database. Finally, Section 5 presents our conclusions and directions for future investigation.
2
Related Work
Approaches to human motion recognition can be grouped into data-driven and model-based methods. Data-driven approaches operate directly on the data. For example, Dollar et al. [7] perform action classification in the space of extracted spatial-temporal features using a support vector machine classifier. Leo et al. [13] describe an unsupervised clustering algorithm for motion classification based on histograms of binary silhouette’s horizontal and vertical projections. These methods are computationally efficient and achieve good classification performance. However, data-driven methods may be inadequate in most realistic scenarios, primarily because local image features are typically highly ambiguous. On the other hand, model-based approaches explicitly include higher-level knowledge about the data by means of a previously learned model. Despite their computational and mathematical elegance, the performance of model-based approaches strongly depends on both the choice of the model and the availability of prior information about the data at hand. Additionally, in the absence of prior information about the models’ structure, the learning task is often intractable. Graphical models represent a suitable solution to this problem as they allow for efficient learning and inference techniques while simultaneously providing a span of models with rich descriptive power. For example, Boiman and Irani [3] propose a graphical Bayesian model for motion anomaly detection. The method describes the motion data using hidden variables that correspond to hidden ensemble in a database of spatial-temporal patches. Niebles et al. [14] create a generative graphical model where action category labels are present as latent variables.
Combining Models of Pose and Dynamics
23
Recently, there has been considerable development in part-based classification methods that model the spatial arrangement of object parts [9,8,5]. These methods are inspired by the original ideas proposed by Fischler and Elschlager [11]. For example, Fergus et al. [9] proposed a fully-connected part-based probabilistic model for object categorization. The approach is based on the constellation model proposed in [4]. Unfortunately, the complexity of the model learning and inference often increases drastically as the number of parts increases. A solution to this problem is to select model structures that allow for both optimal classification performance and tractable learning and inference. In this paper, we propose a method that combines a set of partial motion models into a global model of human motion. Each partial model is a constellation model [4] of a relatively simple yet descriptive structure that describes either the motion dynamics or a specific pose of the motion cycle. The partial models are combined within a Bayesian framework to form a final human motion model that encodes spatial-temporal relationships between the partial models. Here, models are learned from a set of labeled training examples. The key difference between ours and other approaches such as the one described in [15] is that in our framework poses and motion dynamics are modeled explicitly.
3
Our Method
In this section, we present our human motion recognition framework. The goal of our approach is twofold. First, we aim at combining the static information provided by the pose images with the video’s spatial-temporal information to obtain an integrated human motion model. Secondly, we will use this integration model for the classification of human motion sequences. We accomplish these goals by approaching the human motion recognition problem as a probabilistic inference task. An overview of our approach is illustrated in Figure 1. Next, we introduce our probabilistic integration framework followed by a description of the learning and classification procedures. 3.1
Integrating Human Pose and Motion Dynamics
We commence by defining the main components of our model. A video sequence V of human motion can be considered to be the variation of a specific human pose as a function of time. Let P = {P1 , . . . , PK } represent a discrete set of K poses sampled from the space of all possible poses that are representative of a specific human motion type, where K is a small number, usually much smaller than the number of frames in the video sequence. Let M represent the spatial-temporal information extracted from the video sequence. This information describes temporal variations in the image frames, and can be obtained from measurements such as optical flow and spatial-temporal features. Additionally, let X represent simultaneously a particular spatial-temporal configuration of pose and human motion dynamics.
24
R. Filipovych and E. Ribeiro
Fig. 1. Diagram of our approach. An illustrative example of “dynamics two-pose” model. Temporally-aligned extracted motion cycles form the training set (a). For each partial pose model a set of frames corresponding to the same time instance are selected (b, c). The images are preprocessed and the interest subregions are extracted. In the case of dynamics partial model, the spatial-temporal features are extracted using the detector from [7] (d). The partial models’ parameters are estimated independently. These models are then combined to form a global model (e). (Note: The extracted and learned subregions displayed in the chart do not present the actual subregions, as in our implementation the dimensionality of the input subregions is reduced using PCA).
Combining Models of Pose and Dynamics
25
Probabilistically, the likelihood of observing a particular video sequence given that a human motion is at some spatial-temporal location can be represented by the distribution p(V|X ). From the Bayes’ theorem, we obtain: p(X |V)
∝ p(V|X ) p(X ) ∝
p(P|X ) p(M|X )
p(X )
poses
dynamics
spatial-temporal
appearance
appearance
configuration
(1)
We further assume that the appearance of both pose and dynamics are statistically independent. This assumption allows us to factorize the likelihood function in Equation 1 into two components. Accordingly, we introduce the variables P and M to indicate that the human motion information in the video is represented by a set of static poses and dynamic information, respectively. Our integration model of pose and motion dynamics is inspired by the part-based object factorization suggested by Felzenszwalb and Huttenlocher [8]. The underlying idea in our factorization is that the spatial-temporal arrangement of parts can be encoded into the prior probability distribution while the likelihood distribution encodes the appearance. In this paper, we focus ourselves on the combination of human motion dynamics with both the appearance and the spatial-temporal configuration of the pose models. Spatial-Temporal Prior Model. The prior distribution in Equation 1 is described as follows. We begin by assuming that each pose Pi from P can be subdivided into a number of non-overlapping subregions such that Pi = (i) (i) (i) (i) (i) (i) {(a1 , x1 ), . . . , (aNP , xNP )}, where the components of each pair (aj , xj ) i i represent the local appearance a and the spatial-temporal location x of the subregion j for the model of pose Pi , respectively. Here, NPi is the total number of subregions for the pose Pi . While a pose conveys only two-dimensional spatial information, the temporal position of the pose in the video sequence serves as the temporal coordinate of the parts’ locations. Similarly, the dynamic information required by our model can be represented by a sparse set of spatial-temporal (M) (M) (M) (M) features [7,12]. Accordingly, let M = {(a1 , x1 ), . . . , (aNM , xNM )} be a set of spatial-temporal interest features where NM is the number of features in M. The pose models and the dynamics model are the partial models used in our integration framework. The creation of these models is described next. For simplicity, we model both pose and dynamic information using directed acyclic star graphs. This is similar to the part-based object model suggested by Fergus et al. [10]. Here, a particular vertex is assigned to be a landmark vertex (i) (i) (ar , xr ) for the pose Pi . A similar landmark vertex assignment is done for the (M) (M) dynamics model, (ar , xr ). The remaining vertices within each model are conditioned on the corresponding landmark vertex. Figure 1(b) and Figure 1(c) show examples of the partial model graphs for pose while Figure 1(d) shows a graph of the partial model for the motion dynamics. Finally, we build another structural layer on top of the pose models and the motion dynamics model. In this layer, the spatial locations of the partial models are the locations of the
26
R. Filipovych and E. Ribeiro
corresponding landmark image subregions. The global structural layer is built by conditioning the landmark vertices of the pose model graphs on the landmark vertex of the dynamics model graph. In this way, we obtain a multi-layered tree-structured model, which is the global model of human motion used in our method. The graph in Figure 1(e) illustrates our partial models’ integration concept. Here, the arrows in the graph indicate the conditional dependence between the connected vertices. Accordingly, the joint distribution for the partial models’ spatial interaction can be derived from the graphical model shown in Figure 1(e), and is given by: (2) p(x(i) |x(M) ) p(X ) = p(x(M) ) Pi ∈P where x(i) is the spatial-temporal configuration of the pose Pi , and x(M) is the spatial-temporal configuration of the dynamics model. The probability distributions that compose Equation 2 are:
) p(x(M) ) = p(x(M) r
(M)
p(xj
|x(M) ) r
(3)
(i)
(4)
j=r (M) p(x(i) |x(M) ) = p(x(i) ) r |xr
p(xj |x(i) r )
j=r
It should be noted that the dependence between the partial models is based solely on their spatial-temporal configuration within the global model. This follows from our assumption that the partial models are statistically independent with respect to their appearance. Next, we describe the appearance likelihood component of Equation 1 for both pose and motion dynamics. Appearance Model. Under the appearance independence assumption, the appearance likelihood of the pose Pi can be written as the product of the probabilities of its subregions (i.e., parts): NPi
p(Pi |X ) =
(i)
(i)
p(aj |xj )
(5)
j
Similarly, in our motion dynamics model, the appearance likelihood is given by: p(M|X ) =
N M
(M)
p(aj
(M)
|xj
)
(6)
j
As a result, the likelihood term in Equation 1 becomes: p(V|X ) = p(P|X ) p(M|X ) =
Pi K N
i
j
NMi (i)
(i)
p(aj |xj ) ×
(M)
p(aj
(M)
|xj
)
(7)
j
Next, we describe the parameters estimation step (i.e., learning) of our model as well as the motion classification procedure.
Combining Models of Pose and Dynamics
3.2
27
Learning and Classification of Human Motions
Learning. In the learning stage, the parameters of our model are estimated from a set of training video sequences. The factorization in Equation 2 and Equation 7 allows for the learning process to be performed in a modular fashion given a set of training videos {V 1 , . . . , V L }. We restrict each of the training videos to contain exactly one full motion cycle (e.g., two steps of the walking motion). Additionally, we temporally align motion cycles extracted from the training sequences such that they start and finish with the same pose. To obtain the pose training data, we first normalize the length of the sequences to be within the [0, 1] time interval. Then, we extract the corresponding frames from the normalized sequences for a specific time instant. Consequently, in the case of periodic motion, the frames corresponding to the time instants 0 and 1 will contain the same pose translated in time (and, for some motions, also in 2D space). Figure 2 shows an example of the aligned walking cycles. In the figure, the frames correspond to the normalized time slices t = 0, t = 0.25, t = 0.5, t = 0.75, and t = 1. The aligned sequences serve as the input to the dynamic model learning algorithm. The learning procedure is divided into two main steps.
Fig. 2. Examples of segmented and normalized walking sequences, and background images. Frames for normalized time slices: t = 0, t = 0.25, t = 0.5, t = 0.75 and t = 1.
First, the algorithm estimates the parameters for each of the partial models. Secondly, the parameters representing the spatial-temporal configuration of the global model are determined. The learning steps of our algorithm are detailed next. For simplicity, the probabilities in our model are represented by Gaussian densities. Learning step 1 - Learning the parameters of the partial models. In this step, the parameters of the partial models for pose and motion dynamics are estimated. We begin by modeling the probabilities of subregion locations in Equation 2 using Gaussian joint probability distributions. Fortunately, it can be shown that the conditional distributions relating independent Gaussian distributions are also Gaussian [1]. As a result, the conditional densities in Equations 3 and 4
28
R. Filipovych and E. Ribeiro
take a particularly simple form. Further details on Gaussian joint distributions can be found in [1]. For a pose model, we commence by extracting a set of subregions centered at the locations provided by the interest point detector. The method requires two types of input. The first one is a set of positive training images (i.e., images containing the target pose) and a set of negative training images (i.e., background images). We associate a 3D location with every extracted subregion. Here, the locations is represented by the x- and y-coordinates of the subregion in the pose image, and the additional t-coordinate is the frame-position of the pose image in the input sequence. Unlike some other approaches [2], our method does not require the pose to be segmented from the image. We adopt the learning process described by Crandall and Huttenlocher [6]. However, in our work, we consider the spatial-temporal configuration of parts rather than only the spatial configuration. In essence, their method uses a clustering technique to estimate the initial appearances of the possible parts. Then, an initial spatial model is created and the optimal number of parts is determined. An EM-based procedure is used to simultaneously refine the initial estimates of the appearances and the spatial parameters. In our method, we use an E.M. approach to simultaneously (i) (i) estimate the parameters of the distributions p(xj |xr ) in Equation 4 and the pose appearance in Equation 5. We estimate the parameters of the dynamic model in a similar fashion as in the case of the pose models. We proceed by extracting a set of spatial-temporal interest points using the detector described in [7]. We again use the learning (M) (M) method from [6] to estimate the parameters of the distributions p(xj |xr ) in Equation 4 and the dynamics appearance in Equation 6. Learning step 2 - Estimating the parameters of the global model. The goal of this step is to estimate the parameters of the distributions that govern the relationships between the partial models. More specifically, we aim at estimating (i) (M) the parameters of the distributions p(xr |xr ) in Equation 4. Given the original training data instances for each partial model (i.e., extracted frames for the pose models and aligned sequences for the dynamics model), we compute the most likely location for each data type by maximizing the likelihood of pose models: ˆ (i) = arg max p(x(i) |Pi ) x
(8)
ˆ (M) = arg max p(x(M) |M) x
(9)
x
and the dynamics model:
x
Once the maximum likelihood locations evaluated for every partial model and its corresponding data instances are at hand, we can directly estimate the (i) (M) parameters of the distributions p(xr |xr ) in Equation 4. These distributions govern the spatial-temporal interaction between the partial models.
Combining Models of Pose and Dynamics
29
Classification. The problem of recognizing a human motion in a video sequence can then be posed as follows. We seek for the spatial-temporal location in the video sequence that maximizes the posterior probability of the location of the motion given a set of partial models as given in (1): = arg max p(X |V) X X
(10)
It is worth pointing out that, in the case of the tree-structured Bayesian network, the model is equivalent to the Random Markov Fields (RMF) model in which the potential functions are the conditional probability densities. An efficient inference algorithm for such graph structure was studied by Felzenszwalb and Huttenlocher [8]. The algorithm allows to perform exact inference in a reasonable time if the number of partial models is small.
4
Experimental Results
The goal of our experiments is to demonstrate the potential of our method for the classification of human motion. To accomplish this goal, we tested our model on the human action dataset from [2]. This database contains nine action classes performed by nine different subjects. Figure 3 shows a sample of video frames for each motion analyzed in our experiments. Additionally, we compared our results with the results reported by Niebles and Fei Fei in [15]. Finally, we provide some preliminary experimental results on the effect of including additional partial models into the global modeling proposed in this paper. Video Data Preparation. We begin by pre-processing the video data. Since our method is view-dependent, we reflect frames of some sequences with respect to the y-axis, such that the direction of motion is the same in all sequences (e.g., a subject is always walking from right to left). In our implementation, when learning a pose model, we employ the Harris corner detector to obtain static interest point locations for pose images. We limit the number of interest points to be 20 for every pose image. A Gaussian smoothed edge-map of the pose images is obtained from which we extract square patches centered at the detected locations. The features required to create the dynamics model were obtained by means of the spatial-temporal interest point detector described in [7]. In all cases the dimensionality of the data was reduced using PCA. However, the appearance of the background in the sequences from [2] is very similar. This appearance similarity tends to induce a bias in the learning process. To address this issue, we created background data for the dynamics model from portions of the sequences in which no subject was present. On the other hand, corresponding frames served as the background data for the pose learning module. A sample of the static frames extracted from the background sequences is shown in Figure 2. In the results that follow, the maximum number of learned parts of each partial model is set to four. This is done by selecting only up to four most descriptive parts using the descriptiveness evaluation procedure as described in [6].
30
R. Filipovych and E. Ribeiro
Fig. 3. Human action dataset: Example frames from video sequences in the dataset from [2]. The images correspond to frames extracted at t = 0 (a), and t = 0.25 (b).
Classification. We compared our results with the results reported by Niebles and Fei Fei [15]. Similarly, we adopted a leave-one-out scheme for evaluation, by taking videos of one subject as testing data, and using sequences of the remaining subjects for training. The segmentation of sequences is not required by our method. Additionally, only the best match for each model is considered when making the labeling decision. For a given motion type we selected one motion cycle from every original training sequences. The set of the segmented motion cycles is the training set of our method. The partial model learning algorithm is EM-based and strongly depends on the correct initialization. To reduce the effect of incorrect initialization, we removed one of the training sequences from the training set and assigned it to be a validation sequence. The learning algorithm was repeated five times and the model for which the posterior probability calculated on the validation sequence was the highest was retained. In our experiments, we also investigated the effect of including additional partial models into the global model within our framework. First, we built a “dynamics one-pose” model that combines the motion dynamics model and a single pose model. The classification results obtained with this model were compared to results produced by a “dynamics two-pose” model that combines motion dynamics model and two pose models. For the “dynamics one-pose” model the pose was extracted at t = 0. For the “dynamics two-pose” model, the poses were extracted at t = 0 and t = 0.25, respectively. Figure 3 shows a sample of pose images that correspond to these time instants. The confusion tables generated by our classification results are shown in Figure 4. When classifying sequences, the “dynamics one-pose” model allows to correctly classify 70.4% of the testing videos. The method mostly misclassified those sequences for which the pose is similar at the given time instant. This is the case for pose images for the “pjump”, “jack”, and “side” actions (Figure 3(a)). On the other hand, with the “dynamics two-pose” model our system was able to correctly classify 79.0% of the test sequences. This is superior to the 72.8% classification rate in [15].
Combining Models of Pose and Dynamics
(a)
31
(b)
Fig. 4. Confusion matrices for the “dynamics one-pose” model (a) and “dynamics twopose” model (b). The “dynamics one-pose” model correctly classifies 70.4% of the test sequences. The “dynamics-two poses” model correctly classifies 79.0% of the sequences.
5
Conclusions
In this paper, we presented a novel principled solution to the problem of recognizing human motion in videos. Our method works by combining data of different nature within a single probabilistic integration framework. More specifically, we demonstrated how partial models of individual static poses can be combined with partial models of the video’s motion dynamics to achieve motion classification. We demonstrated the effectiveness of the proposed method on a series of motion classification experiments using a well-known motion database. We also provided a comparison with a recently published motion recognition approach. Our results demonstrate that our method offers promising classification performance. Future directions of investigation include a study of the possibility to automatically select poses that would lead to optimal recognition performance. A possible way to follow is to use boosting to improve the selection of optimal poses and dynamics information. Acknowledgments. This research was supported by U.S. Office of Naval Research under contract: N00014-05-1-0764.
References 1. Bishop, C.M.: Pattern Recognition and Machine Learning (Information Science and Statistics), Secaucus, NJ, USA. Springer, Heidelberg (2006) 2. Blank, M., Gorelick, L., Shechtman, E., Irani, M., Basri, R.: Actions as space-time shapes. Int. Conference on Computer Vision, 1395–1402 (2005) 3. Boiman, O., Irani, M.: Detecting irregularities in images and in video. In: Conf. on Computer Vision and Pattern Recognition, pp. 462–469 (2005)
32
R. Filipovych and E. Ribeiro
4. Burl, M.C., Weber, M., Perona, P.: A probabilistic approach to object recognition using local photometry and global geometry. In: Burkhardt, H., Neumann, B. (eds.) ECCV 1998. LNCS, vol. 1407, pp. 628–641. Springer, Heidelberg (1998) 5. Carneiro, G., Lowe, D.: Sparse flexible models of local features. In: Leonardis, A., Bischof, H., Pinz, A. (eds.) ECCV 2006. LNCS, vol. 3953, pp. 29–43. Springer, Heidelberg (2006) 6. Crandall, D.J., Huttenlocher, D.P.: Weakly supervised learning of part-based spatial models for visual object recognition. In: Leonardis, A., Bischof, H., Pinz, A. (eds.) ECCV 2006. LNCS, vol. 3951, pp. 16–29. Springer, Heidelberg (2006) 7. Doll´ ar, P., Rabaud, V., Cottrell, G., Belongie, S.: Behavior recognition via sparse spatio-temporal features. In: VS-PETS (October 2005) 8. Felzenszwalb, P.F., Huttenlocher, D.P.: Pictorial structures for object recognition. Int. J. Comput. Vision 61(1), 55–79 (2005) 9. Fergus, R., Perona, P., Zisserman, A.: Weakly supervised scale-invariant learning of models for visual recognition. Int. J. Comput. Vision 71(3), 273–303 (2007) 10. Fergus, R., Perona, P., Zisserman, A.: A sparse object category model for efficient learning and exhaustive recognition. In: CVPR 2005. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (June 2005) 11. Fischler, M., Elschlager, R.: The representation and matching of pictorial structures. IEEE Transactions - Computers 22, 67–92 (1977) 12. Laptev, I., Lindeberg, T.: Space-time interest points. In: IEEE Int. Conf. on Computer Vision, Nice, France (October 2003) 13. Leo, M., D’Orazio, T., Gnoni, I., Spagnolo, P., Distante, A.: Complex human activity recognition for monitoring wide outdoor environments. In: ICPR 2004. Proceedings of the Pattern Recognition, 17th International Conference, vol. 4, pp. 913–916. IEEE Computer Society Press, Los Alamitos (2004) 14. Niebles, J., Wang, H., Wang, H., Fei Fei, L.: Unsupervised learning of human action categories using spatial-temporal words. In: BMVC 2006. British Machine Vision Conference, p. 1249 (2006) 15. Niebles, J.C., Fei-Fei, L.: A hierarchical model of shape and appearance for human action classification. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Minneapolis, USA (July 2007) 16. Schuldt, C., Laptev, I., Caputo, B.: Recognizing human actions: A local svm approach. In: ICPR 2004. Proceedings of the Pattern Recognition, 17th International Conference, vol. 3, pp. 32–36. IEEE Computer Society Press, Los Alamitos (2004) 17. Wang, Y., Jiang, H., Drew, M.S., Li, Z.-N., Mori, G.: Unsupervised discovery of action classes. In: CVPR 2006. Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp. 1654–1661. IEEE Computer Society Press, Los Alamitos (2006) 18. Wong, S.-F., Kim, T.-K., Cipolla, R.: Learning motion categories using both semantic and structural information. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Minneapolis, USA (June 2007)
Optical Flow and Total Least Squares Solution for Multi-scale Data in an Over-Determined System Homa Fashandi1, Reza Fazel-Rezai1, and Stephen Pistorius2,3 1
Department of Electrical and Computer Engineering, University of Manitoba, Winnipeg, MB, Canada R3T 5V6 {Fashandi,Fazel}@ee.umanitoba.ca 2 Departments of Radiology & Physics and Astronomy, University of Manitoba, Winnipeg, MB, Canada R3T 2N2 3 Medical Physics, CancerCare Manitoba, Winnipeg, MB, Canada R3E 0V9
[email protected]
Abstract. In this paper, we introduce a new technique to estimate optical flow fields based on wavelet decomposition. In order to block error propagation between layers of multi-resolution image pyramid, we consider information of the all pyramid levels at once. We add a homogenous smoothness constraint to the system of optical flow constraints to obtain smooth motion fields. Since there are approximations on both sides of our over determined equation system, a total least square method is used as a minimization technique. The method was tested on several standard sequences in the field and megavoltage images taken by linear accelerator devices and showed promising results.
1 Introduction Optical flow is defined as “the distribution of apparent velocities of movements of brightness patterns in an image” [1]. It is an estimation of 2D projection of moving 3D environment. A Wide range of applications use optical flow including scene interpretation algorithms, recognizing camera motion, determining the number of moving objects, characterizing their motion, recovering camera ego motion, or performing motion segmentation. A comprehensive survey of different optical flow techniques is presented in [2]. Methods are broadly classified into four different categories; gradient-based, correlation-based, phase-based and spatiotemporal energy-based methods. Gradient-based techniques utilize spatial and temporal derivatives of the image. The most salient work in this category has been presented by Horn and Schnuck [1]. Correlation-based approaches are similar to block matching techniques. For each pixel in the image, a block is opened, the best match in the previous block is found and the amount of motion is calculated. The best match is determined by maximizing or minimizing a similarity measure [3]. Phase-based approaches define velocity in terms of the phase behavior of band-pass filter outputs [4]. Spatiotemporal energy-based methods use physiologically based models for motion extraction. Oriented spatiotemporal subband filters are applied to the image and their outputs measure the motion energy [5]. A broader classification of optical flow techniques is also introduced in [6]. G. Bebis et al. (Eds.): ISVC 2007, Part II, LNCS 4842, pp. 33–42, 2007. © Springer-Verlag Berlin Heidelberg 2007
34
H. Fashandi, R. Fazel-Rezai, and S. Pistorius
Optical flow methods are also classified into local approaches and global methods. Local techniques which are more robust to noise optimize some form of local energy objective [1], while global methods which provide flow fields with full density optimize global energy function [7]. In this paper, we have developed a gradient based technique to enable us to evaluate real time patient positioning errors in radiation therapy. Initially a multi-resolution image pyramid is created using wavelet decomposition. For each block in the original image, information at all coarser levels is incorporated to establish an overdetermined system of linear equations based on optical flow constraints. A homogenous smoothness constraint at the finest level is added to the system and finally a total least squares method is used to solve the system. The paper is organized as follows. Section 2 develops the technical background required before we describe our proposed method in Section 3. The experimental results are shown in Section 4 while in Section 5, conclusions and future work are presented.
2 Technical Backgrounds A brief definition of optical flow and regularization techniques are presented in Section 2.1. Since this paper estimates optical flow using wavelets, Section 2.2 briefly describes the salient work on wavelet-based optical flow techniques. The affine motion model is discussed in Section 2.3 while in Section 2.4, a method for solving overdetermined system of linear equations is presented. 2.1 Optical Flow There are three major techniques to estimate displacement vectors from successive image frames; block matching, the pel recursive method and optical flow [8]. Optical flow provides relatively more accurate results [8].Optical flow algorithms estimate the motion vector for each pixel in an image. Most optical flow techniques assume intensity conservation between images which implies that the intensity values of pixels do not change in an image sequence. Under this assumption we can write
f ( x + u , y + v, t + 1) = f ( x, y, t )
(1)
where (u,v) is optical flow vector at point (x,y). If the first order Taylor series is used to expand equation 1, the result will be called Optical Flow Constraint:
f xu + f y v + ft = 0
(2)
where f x , f y and f t are partial derivatives in x, y and t, respectively. To estimate the two unknowns u and v, we need to solve equation 2. This single equation does not have enough information to be solved uniquely. This is called aperture problem as only the flow component parallel to ∇f = ( f x , f y ) , where the image gradient is not zero, can be computed. In general, we need an additional constraint to solve the problem and variational methods consider smooth or piecewise smooth optical fields [9] while minimizing some form of energy function, E:
Optical Flow and Total Least Squares Solution
∫ OPC (u, v, ∇
E (u , v) =
3
f ) + αS (∇ 3u, ∇ 3v, ∇ 3 f )dxdydt
Ω×[ 0,T ]
35
(3)
where Ω is the spatial neighbourhood, OPC is optical flow constraint (equation 2), S is the smoothness function, ∇ 3 = (∂ x , ∂ y , ∂ t )T is spatiotemporal gradient operator and
α is a regularisation parameter which determines the contribution of smoothness in optical flow estimation. Regularization has a strong influence on the result and an overview of regularization techniques can be found in [6] [10]. We used the regularization technique introduced by Horn and Schunck which utilized the Laplacian of u and v as a smoothing constraint [1]. In this method, the smoothness function is expressed as: 2
S (∇ 3u, ∇3v, ∇3 f ) = ∇u + ∇v
2
(4)
2.2 Wavelet-Based Optical Flow Techniques
Time aliasing, where large displacements can not be recovered at a fine scale, is a common problem in optical flow techniques. To overcome this, a multi-resolution approach where optical flow fields are estimated at the coarsest level and then propagated to the finer levels to estimate more details has been used intensively [12]. Since a wavelet transform has a built-in multi-scale structure, it has attracted attention for estimating motion fields [11][12][13][14]. Wu et al. proposed a method [11] which minimizes the following function to recover u and v: E=
∑ [I ( x + u( x, y) , y + v( x, y)) − I
0 ( x, y )
x, y
]2
(5)
Motion vectors u and v are approximated using two dimensional basis functions which themselves are tensor products of one dimensional basis functions. Each motion field is expressed by linear combinations of the coarsest scale spline function and horizontal, vertical and diagonal wavelets in finer levels. The problem is then converted to estimating coefficient vectors [11]. Chen et al. used wavelets to represent u and v as well as image related operators such as the gradient operator [14]. To overcome the aperture problem Bernard used wavelets to calculate an inner product of the optic flow constraint with S different vectors to establish a solvable system of equations [13]. The final form of the system is as follows: ⎧ ∂ψ 1w ∂ψ 1w ∂ u ( w) + I , v( w) = I ,ψ w1 ⎪ I, ∂y ∂t ∂x ⎪ ⎪ # ⎨ ⎪ ∂ψ wN ∂ψ wN ∂ u ( w) + I , v( w) = I ,ψ wN ⎪ I, ∂y ∂t ∂x ⎪⎩
(6)
36
H. Fashandi, R. Fazel-Rezai, and S. Pistorius
where (ψ n ) n=1,...,N defined in L2 (ℜ 2 ) centered around (0, 0) with different frequency contents and ψ wn ( x) = ψ n ( x − w) . Typically 3 or 4 equations are used to solve the system for u and v. Lui et al. proposed a framework for wavelet based optical flow estimation to overcome the problem of error propagation in multi-level pyramids [12]. Typically, optical flow is first estimated at a coarse level and then propagated to a finer level as a warp function to morph an image. The algorithm is then applied to the warped version of an image and its reference. When the coarse level estimations contain large errors that can not be corrected in finer levels, the result contains large errors. This typically happens when regions of low textures become flat in coarser levels. To solve the error propagation problem, Lui et al. suggested considering optical flow constraint at all levels of multi-resolution pyramid simultaneously and solving the system of equations at once. We will discuss this method further in Section 3. 2.3 Affine Motion Model for Optical Flow
As indicated in equation 1, only translational motion is considered to estimate optical flow. Since true motion occurs in 3-dimensional space and then is projected into 2directional image space, a better assumption for motion would be an affine motion model. This model is first introduced to the field of optical flow estimation in [15]. In this model, u and v are defined as follows: u = p1 x + p 2 y + p 3 v = p 4 x + p5 y + p 6
(7)
where six parameters, p1 to p6 , represent the affine motion model; p1 to p4 are linear affine, p5 and p6 are translations parameters. Considering affine motion model, equation 2 can be written in vector form as bellow:
( f x , f y )⎛⎜⎜ x0 ⎝
y 1 0 0 0⎞ ⎟( p1 0 1 x y 1 ⎟⎠
p2
p3
p4
p5
p6 )T − f t = 0
(8)
2.4 Over-Determined System of Linear Equations and Total Least Squares
Regardless of the method used to solve the aperture problem, we obtain a system of linear equations to estimate the motion fields. One example of this is shown in equation 8. There are only 6 unknown parameters, and it is expected that 6 equations are enough to estimate the unknowns. However, since we are using approximations, erroneous and noisy data, 6 equations will not give the best solution and generally, more equations are used to solve this problem [16]. An over-determined system of linear equation is as follows: Ax = b
(9)
where A ∈ ℜ m× n is a data matrix, b ∈ ℜm is an observation vector and m>n. In our case n equals 6. In classical Least Squares (LS) the measurements of A are considered
Optical Flow and Total Least Squares Solution
37
error free and all errors are confined to b. In solving equation 9 for optical flow, both A and b contain errors due to noise, approximations and occlusion. Van Huffel and Vandewalle proposed a method called Total Least Squares (TLS) which outperforms LS when both data and observations matrices are erroneous [17]. They define the multidimensional TLS problem as follows. Let AX=B be an over-determined set of m equations with n×d unknowns X (m>n). TLS minimizes: min [ Aˆ ; Bˆ ] ∈ ℜ m×( n+d )
[ A; B] − [ Aˆ ; Bˆ ]
F
(10)
is the Frobenius norm of M. Once a minimizing [ Aˆ ; Bˆ ] is found, any X satisfying Aˆ X = bˆ is a TLS solution and [ΔAˆ ; ΔBˆ ] = [ A; B ] − [ Aˆ − Bˆ ] is the corresponding TLS correction. Singular value decomposition (SVD) of the matrix [A; B] is as follows:
subject to Bˆ ⊆ R( Aˆ ) . M
F
[ A; B ] = UΣV T
(11)
such that 0⎤ ⎡Σ m×( n + d ) , t = min{m − n, d } Σ=⎢ 1 ⎥ = diag (σ 1 ,..., σ n + t ) ∈ ℜ 0 Σ 2⎦ ⎣ Σ 1 = diag (σ 1 ,..., σ n ) ∈ ℜ n×n , Σ 2 = diag (σ n +1 ,..., σ n +t ) ∈ ℜ ( m − n )×d ,
(12)
σ 1 ≥ ... ≥ σ n +t ≥ 0 If σ n′ > σ n +1 = ... = σ n + d , where σ n′ is singular value of A, the solution to equation 10 will be as follows: 2 Xˆ = ( AT A − σ n +1 I )−1 AT B
(13)
3 Our Proposed Method Our proposed method is inspired by work done by Lie et. al. [12] and [16]. Liu et al. considered information at all levels of resolution simultaneously to block error propagation [12]. Bab Hadiashar and Suter compared different kinds of least square techniques to find a robust method for optical flow determination [16]. The novelty of our work is to consider smoothness constraint in addition to information at all resolution levels. We also used TLS to solve this over-determined system .The overall structure of the proposed method is depicted in Fig. 1. The first step is to use a twodimensional wavelet transform to construct an image pyramid. At each level of decomposition, approximation, vertical, horizontal and diagonal channels are obtained. As in equation 8, vertical and horizontal derivatives of the image are used to obtain the optical flow constraint. These derivatives were calculated in wavelet decomposition pyramid. Fig. 2 shows the schematic form of two-dimensional wavelet decomposition.
38
H. Fashandi, R. Fazel-Rezai, and S. Pistorius
We reconstructed equation 3 so that translational motion is replaced by affine motion model. TLS is used to minimize the objective function E: L
E ( p1 ,", p6 ) =
∫ ∑ OPC ( p ,", p , ∇ l
1
6
3
f l ) + αS (∇ 3 p1 ,", ∇ 3 p6 , ∇ 3 f 0 )dxdydt
(14)
Ω×[ 0,T ] l = 0
where f l is image approximation at level l of multi-resolution pyramid. l=0 is bottom of pyramid, l=L is the coarsest level.
[p1, … , p6] Optical Flow Constraint TLS
Image Pyramid
A p=B Smoothness Constraint
Over-determined System of Linear Equations
Fig. 1. Overall structure of our proposed method. Image pyramid is constructed by wavelet decomposition. Optical flow constraints are obtained for pixels in blocks of 2L-m+1×2L-m+1 at level m, where L is the total number of levels. In addition to all of the equations, smoothness constraint is also considered for the finest level. An over-determined system of linear equations Ap=B is solved using TLS method. [p1, ….,p6] are affine motion parameters.
Fig. 2. Two level wavelet decomposition. A: approximation channel, H: horizontal channel, V: vertical channel, D: diagonal channel.
The TLS solution to equation 14 is the same as the system shown in equation 15. Here optical flow parameters are considered similar in small neighborhood. For each pixel in the image or each 2L+1 pixels in image, the system in equation 15 is computed. Since u and v become half of their value when moving from one level to the next coarser one, we add power of 2 corrections in the spatial matrixes in system 15. The last two equations in system 15 are responsible for homogenous smoothness. α is the contribution of smoothness in the minimization process while ε1 and ε2 are almost zero.
Optical Flow and Total Least Squares Solution
⎧ 0 ⎛ x yi 2 L 0 0 0 ⎞ G 0 ⎟ p = f 2 0 ( xi , yi ) − f10 ( xi , yi ) , i = 1,...,2 L +1 ⎪( f1 x ( xi , yi ), f1 y ( xi , yi ))⎜⎜ i L⎟ ⎪ ⎝ 0 0 0 xi y i 2 ⎠ ⎪ # ⎪ 0 ⎛ ⎞ ⎪⎪ ( f1 L ( xi , yi ), f1 L ( xi , y i ))⎜ xi yi 2 0 0 0 ⎟ pG = f 2 L ( xi , yi ) − f1 L ( xi , yi ) , i = 1,...,2 2 y ⎜ 0 0 0 x y 20 ⎟ ⎨ x i i ⎝ ⎠ G ⎪ ∂p ⎪ α = ε1 ∂x ⎪ G ⎪ ∂p = ε2 α ⎪ ⎪⎩ ∂y
39
(15)
4 Experimental Results There are several test sequences for optical flow estimation. They are categorized as real and synthetic sequences. To obtain the error measure for a method, the true optical flow of a sequence is needed. Normally in this field, error is measured by angular error between the space time direction vectors (vact,1) and (v,1):
⎡ ⎢ (vact ,1).(v,1) e = arccos⎢ ⎢ 1+ v 2 1+ v act ⎣⎢
2
⎤ ⎥ ⎥ ⎥ ⎦⎥
(16)
where vact is the actual 2-D motion fields and v is the vector of estimated motion field. It is usual to consider a confidence measure for estimated optical flows to enhance the result. We obtain a reliability measure for our method based on TLS solution where the confidence measure is R =1 −
σ n +1 2
∑ (b
i
− bi ) 2
(17)
where σ n+1 is the same as defined in equation 13 and bi are observation vector elements. This measure should be close to one [16]. To test the system, we used the Yosemite1, Hamburg taxi2 and Vc-box3 sequences. The Yosemite sequence is a challenging one because it includes a range of velocities, the occluding edges between the mountains and at the horizon and severe aliasing in the lower portion of image [2]. Two frames of this sequence, true optical flow and our estimated optical flow are shown in Fig. 3(a-d). We found most errors in the cloud region. We set R=0.8 as a threshold and remove the motion fields below the threshold. Our overall error is 12.3 degrees with standard deviation 9.35 degrees. By using higher thresholds, we could gain a better result but at the same time we lose the optical flow density. Therefore there is a tradeoff between density and lower error rate. 1 2 3
http://www.cs.brown.edu/~black/images.html http://i21www.ira.uka.de/image_sequences/ http://of-eval.sourceforge.net/
40
H. Fashandi, R. Fazel-Rezai, and S. Pistorius
Fig. 3. (a-b) Yosemite image sequence, frames 9 and10, (c) true optical flow, (d) estimated flow field with threshold set to 0.8 (e-f) frame 16 and 17 of Vc-box sequence, (g) true motion field , (h) estimated motion field with threshold equals 0.8, (i) reference mega voltage image, (j) mega voltage image with 2 degrees rotation to image shown in i, (k) estimated optical flow, (l) estimated optical flow with threshold is set to 0.8, (m) reference mega voltage image, (n) mega voltage image with 2 mm translational motion to the right with respect to image shown in m, (o) estimated optical flow, (p) threshold is set to 0.8, (q-r) Hamburg taxi Sequence, frames 5 and 6(s) estimated optical flow
Images in Fig. 3(e-g), show two frames of Vc-box sequence and true and estimated optical flow. The sequence involves zooming out from a view of a cardboard box [18]. In addition to standard sequences, we also applied our method to megavoltage images taken on a linear accelerator. These images are taken with high energy X-rays (in the megavolt range), and are of relatively poor contrast and resolution. We used these images because we wanted to identify if the method is capable of recognizing
Optical Flow and Total Least Squares Solution
41
small changes in noisy and low resolution images. As shown in Fig. 3 (i-p) our system successfully recognized rotation and translational motions. These images contain illumination changes which caused errors especially in image boundaries. Finally Hamburg taxi sequence and the estimated optical flow are shown in Fig. 3(q-s). This sequence shows three moving cars, the taxi turning, a car moving from left to right at the bottom left and another car driving right to left at the bottom right of the sequence. Estimated optical flow shows these motions correctly.
5 Summary and Conclusions Optical flow is an estimation of 2D projection of moving 3D environment. Optical flow is used by a wide variety of applications, including: scene interpretation, recognizing camera movements, determining number of moving objects, etc. In this paper, we construct an over determined system of linear equations to estimate optical flow. This system contains information of neighborhood of each pixel at different resolution. Multi-resolution scheme is used in estimating optical flow, to recognize larger motions. Most techniques used multi-resolution pyramid to propagate motion fields from coarser levels to the finer ones. In this paper, we are inspired by the idea presented in [12]. We gathered all the information at different levels to block error propagation. Two dimensional wavelet transform is used to construct multi-resolution pyramid. In addition to optical flow constraints, we propose to add a smoothness constraint to the system. Since numerical approximations are used in calculating image gradients, the smoothness constraint and given the noise in the images, there are perturbations in both sides of our system. We propose using total least squares method instead of traditional least squares as a robust method to solve the system and estimate optical flow vectors. In comparison to summery of different techniques applied to Yosemite sequence reported in [12], our results are promising.
Acknowledgement Financial support from CancerCare Manitoba and MITACS is gratefully acknowledged.
References 1. Horn, B.K.P., Schunck, B.G.: Determining Optical Flow. Artificial Intelligence 17, 185– 204 (1981) 2. Barron, J.L., Fleet, D.J., Beauchemin, S.S.: Performance of Optical Flow Techniques. International Journal of Computer Vision 12, 43–77 (1994) 3. Anandan, P.: A Computational Framework and an Algorithm for the Measurement of Visual Motion. International Journal of Computer Vision 2, 283–310 (1989) 4. Gautama, T., Van Hulle, M.: A Phase-based Approach to the Estimation of the Optical Flow Field. IEEE Transactions on Neural Networks 13(5), 1127–1136 (2000) 5. Simoncelli, E.P., Adelson, E.H.: Computing Optical flow Distributions Using Spatiotemporal Filters, Technical Report 165, M.I.T Media Lab Vision and Modeling (1991)
42
H. Fashandi, R. Fazel-Rezai, and S. Pistorius
6. Bruhn, A., Weickert, J.: Lucas/Kanade Meets Horn/Schunck. International Journal of Computer Vision 16(3), 211–231 (2005) 7. Lucas, B., Kanade, T.: An Iterative Image Registration Technique with an Application to Stereo Vision. In: Proceeding Seven International Joint Conference on Artificial Intelligence, Vancouver, pp. 674–679 (1981) 8. Shi, Y.Q., Sun, H.: Image and Video Compression for Multimedia Engineering: Fundamentals, Algorithms and Standards. CRC Press, New York (2000) 9. Bruhn, A., Weickert, J.: A Confidence Measure for Variational Optic Flow Methods. In: Geometric Properties for Incomplete Data, pp. 283–297. Springer, Heidelberg (2006) 10. Weickert, J., Schnorr, C.: A Theoritical Framework for Convex Regularizers in PDE based Computation of Image Motion. International Journal of Computer Vision 45, 245–264 (2001) 11. Wu, Y.T., Kanade, T., Li, C.C., Cohn, J.: Optical Flow Estimation Using Wavelet Motion Model. International Journal of Computer Vision 38(2), 129–152 (2000) 12. Liu, H., Chellappa, R., Rosenfeld, A.: Fast Two Frame Multi-scale Dense Optical Flow Estimation Using Discrete Wavelet Filters. Journal of Optical Society of America 20(8), 1505–1515 (2003) 13. Bernard Ch.: Wavelet and Ill-posed Problems: Optic Flow Estimation and Scattered Data Interpolation, PhD Thesis, Ecole Polytechnique (1999) 14. Chen, L.F., Liao, H.Y., Lin, J.C.: Wavelet Based Optical Flow Estimation. IEEE Transactions on Circuits and Systems for Video Technology 12(1), 1–12 (2002) 15. Liu, H., Hong, T.H., Herman, M., Chellappa, R.: A General Motion Model and Spatio Temporal Filters for Computing Optical Flow. International Journal of Computer Vision 22(2), 141–172 (1997) 16. Bab Hadiashar, A., Suter, D.: Robust Optical Flow Computation. International Journal of Computer Vision 29(1), 59–77 (1998) 17. Van Huffel, S., Vandewalle, J.: The Total Least Squares Problem Computational Aspects and Analysis, SIAM (1991) ISBN 0-89871-275-0 18. McCane, B.: On Benchmarking Optical Flow. Computer Vision and Image Understanding 84, 126–143 (2001)
A Hardware-Friendly Adaptive Tensor Based Optical Flow Algorithm Zhao-Yi Wei, Dah-Jye Lee, and Brent E. Nelson Department of Electrical and Computer Engineering, Brigham Young University, Provo, UT USA
Abstract. A tensor-based optical flow algorithm is presented in this paper. This algorithm uses a cost function that is an indication of tensor certainty to adaptively adjust weights for tensor computation. By incorporating a good initial value and an efficient search strategy, this algorithm is able to determine optimal weights in a small number of iterations. The weighting mask for the tensor computation is decomposed into rings to simplify a 2D weighting into 1D. The devised algorithm is well-suited for real-time implementation using a pipelined hardware structure and can thus be used to achieve real-time optical flow computation. This paper presents simulation results of the algorithm in software, and the results are compared with our previous work to show its effectiveness. It is shown that the proposed new algorithm automatically achieves equivalent accuracy to that previously achieved via manual tuning of the weights.
1 Introduction Tensor based optical flow algorithms can produce dense and accurate optical flow fields [1]-[5] for motion detection and estimation. Tensors provide a closed form representation of the local brightness pattern. Using special-purpose hardware to compute optical flow has previously shown its advantages over traditional softwarebased implementations of optical flow algorithms [6]-[10]. Depending on the application, a fast optical flow algorithm with adequate accuracy can be more useful in practice than a complex and slow algorithm with higher “theoretical accuracy”. This is because the brightness constancy assumption is better satisfied when processing at high frame rates. A small processing unit with special processing hardware can be more useful for many real-time applications than a general purpose PC. However, mapping from software to hardware is not trivial and performance will deteriorate if hardware implementation considerations are not taken into account carefully. That is, it is necessary to devise the algorithm with hardware in mind from the outset. In [6] a tensor-based optical flow algorithm was implemented on an FPGA that was able to process 64 640×480 frames per second. This computation contained two weighting processes and the weights were determined offline by finding the setting which gave the best accuracy compared against the ground truth. However, this method was not optimal in practice. In this paper, a new algorithm is proposed to use a cost function to adaptively determine the optimal weights. An efficient scheme is G. Bebis et al. (Eds.): ISVC 2007, Part II, LNCS 4842, pp. 43–51, 2007. © Springer-Verlag Berlin Heidelberg 2007
44
Z.-Y. Wei, D.-J. Lee, and B.E. Nelson
devised to determine the optimal weights faster and more accurately. To better fit the hardware structure, an efficient tensor computation method is proposed. Experimental results are presented in Section 3 to show the effectiveness of the algorithm.
2 Algorithm 2.1 Tensor-Based Algorithm Overview Given an image sequence g(x), structure tensor T(x) can be computed at each pixel to incorporate the local brightness pattern. Structure tensor T(x) is a 3 by 3 symmetric semidefinite matrix. The structure tensor [4] is defined as
⎛ t1 ⎜ T = ∑ ci O i = ⎜ t 4 i ⎜t ⎝ 5
t4 t2 t6
t5 ⎞ ⎟ t6 ⎟ t 3 ⎟⎠
(1)
where ci are weights for averaging the outer products O of the averaged gradient. O is calculated as
⎛ o1 ⎜ O = ∇g (x)∇g (x) T = ⎜ o 4 ⎜o ⎝ 5
o4 o2 o6
o5 ⎞ ⎟ o6 ⎟ , o3 ⎟⎠
(2)
where the averaged gradient is
∇g (x) = ∑ wi ∇g (x i ) = (g x (x), g y (x), g z (x) )
T
(3)
i
and wi are weights for averaging the gradient ∇g (x) . From (1)-(3), we can see that the tensor is calculated by first smoothing the gradient and then weighting the outer product of the smoothed gradient. The weights, ci and wi, are critical to the performance of the algorithm. Optical flow v = (v x , v y )T can be extended to a 3D spatio-temporal vector T v = ( vT ,1)T = (v x , v y ,1)T . According to the brightness constancy assumption, v Tv=0 if
there’s no rotational movement or noise in the neighborhood [1]-[2]. In the presence of rotation and noise, vTTv will not be zero and v can be determined by minimizing vTTv instead. The optical flow can then be solved as
vx =
(t 6 t 4 − t 5t 2 ) , (t t − t t ) v y = 5 4 6 21 . 2 (t1t 2 − t 4 ) (t1t 2 − t 4 )
(4)
2.2 Cost Function Using a tensor to represent orientation has a notable advantage over scalars and vectors. Tensors not only estimate the orientation but also include the certainty of the
A Hardware-Friendly Adaptive Tensor Based Optical Flow Algorithm
45
estimation. In [4], local brightness patterns were divided into different cases and eigenvalues of the structure tensor in each case were analyzed. Three measures: total coherency measure, spatial coherency measure, and corner measure were defined. They were functions of the eigenvalues of structure tensor. Middendorf et al. [11] used eigenvalue analysis to divide the optical flow field into five categories for motion segmentation. Kühne et al. [12] derived a coherence measure based on eigenvalues. This measure was integrated into an active contour model for segmentation of moving objects. In [3], a corner measure was applied to adaptively adjust the Gaussian window function to improve tensor accuracy. All of the above work first calculated the eigenvalues of the structure tensor and then devised measures using certain combinations of these eigenvalues. The main challenge of using these measures in hardware is that eigenvalues are difficult to obtain. In this paper, the following cost function [1] is used to indicate the certainty
ct (T) =
t3 − t T T −1t , where ⎛T t ⎞. ⎟⎟ T = ⎜⎜ T trace(T) ⎝ t t3 ⎠
(5)
T is a 2×2 symmetric matrix and its inverse matrix can be easily computed. ct is the minimum value of vTTv [1] normalized by the trace of the tensor and indicates the variation along direction v. Therefore, the smaller ct is, the more reliable the tensor will be and vice versa. 2.3 Finding Optimal Weights Cost function ct is not directly related to wi in (3). It is difficult to decouple ci and wi and to adjust wi by evaluating the cost function. Cost function ct in (5) directly indicates the performance of the weights ci in (1) if we assume wi are fixed. Our algorithm adjusts ci while using fixed wi. The support of wi is chosen to be relatively small to prevent “over smoothing”. The reason for applying two small weighting masks instead of one big mask is that it is more economical to implement such a scheme in hardware. The ci are given by the Gaussian function. The shape of the Gaussian function can be characterized by its standard deviation σ . The problem can be interpreted as “finding the optimal standard deviation σ for ci such that the cost function ct (T) is minimized”. Liu et al. [3] proposed an adaptive standard deviation updating algorithm. Starting from a small value, standard deviation σ was increased by Δσ if the confidence measure did not reach the threshold. The support size was then adjusted according to the standard deviation σ . This process was repeated until the confidence measure reached the desired value or a set number of iterations were reached. In this paper, an efficient and accurate algorithm for updating the standard deviation is proposed. It is different from the adaptive algorithm in [3] in four major aspects: 1) It uses a different confidence measure; 2) It has a fixed support size; 3) It uses a better initial value; 4) It uses different searching strategy.
46
Z.-Y. Wei, D.-J. Lee, and B.E. Nelson
The first aspect was discussed above in Section 2.2. The support size is fixed because changing the support size usually requires changes in the hardware structure as opposed to changing weights. During the weighting process, the mask is moved sequentially along a certain direction, say from left to right and then from top to bottom. Two adjacent pixels have most of the masked region overlapped. We can expect that the brightness patterns of the two masked regions are very similar. Therefore, instead of using one initial value for every pixel, we use the standard deviation σ f ( x − 1, y ) resolved from the previous pixel to initialize the standard deviation σ 1 ( x, y ) of the current pixel. The standard deviation is set to zero for the first pixel of each row. There are two advantages of this method: 1) It dramatically decreases the number of iterations; 2) It increases the dynamic range of the standard deviation and can handle signals in a wider range. The pseudocode of the algorithm used for searching and for building the tensor for pixel (x, y) is shown in Fig. 1. The threshold for cost function is t c and the iteration limit is t iter , σ i ( x, y ) is the standard deviation for pixel (x, y) at the ith iteration. By using this scheme, for each iteration a better initial value is given, the distance to the ideal standard deviation is shortened, and the number of iterations is decreased. The tensor can be computed using (1) or the method introduced in the subsection 2.4. There are two modes for updating the standard deviation; increasing mode and decreasing mode. One way to decide which mode should be taken is to compute tensors and cost functions using both modes and choose the one with smaller cost. The iteration will be terminated under one of three conditions: 1) The cost decreases below a pre-set threshold; 2) A maximum iteration limit is reached; 3) The cost increases compared to the last iteration.
2.4 Tensor Computation If the weighting process in (1) is directly implemented in hardware, for a (2n+1)×(2n+1) mask, all (2n+1)2 data in the mask need to be stored in hardware registers at each iteration for computing the tensor in the next iteration. With an increase of mask size, the number of hardware registers will increase quadratically. We propose a method to implement the weighting process efficiently. First, the weighting mask is divided into concentric rings centered at the center of the mask. The weights on each ring are similar because their distances to the center of the mask are roughly the same. Therefore, the parameters c j ,k and outer products O j,k of the averaged gradient on the jth ring Rj can be replaced by
c j and O j shown below.
T = ∑ ciO i = ∑∑ c j , k O j , k ≈ ∑ (c j ∑ O j , k ) = ∑ m j c j O j . . i
where
j
k
j
k
m j is the number of the weights on ring Rj .
j
(6)
A Hardware-Friendly Adaptive Tensor Based Optical Flow Algorithm
47
initialize σ 1 ( x, y ) ; compute tensor T1 using σ 1 ( x, y) ; compute ct as in (5); if ct is smaller than t c set the final standard deviation σ f ( x, y ) = σ 1 ( x, y ) ; return T1; end if; judge which mode will be taken; for i = 1 : t iter if it is increasing mode σ i +1 ( x, y ) = σ i ( x, y ) + Δσ ; else σ i +1 ( x, y ) = σ i ( x, y ) − Δσ ; end if; compute tensor Ti +1 using σ i+1 ( x, y ) ; compute ct as in (5); if ct is smaller than t c σ f ( x, y ) = σ i +1 ( x, y ) ; return Ti+1; else if ct is increasing σ f ( x, y ) = σ i ( x, y ) ; return Ti; end if; end for; σ f ( x, y ) = σ i +1 ( x, y ) ; return Ti+1; Fig. 1. Algorithm Pseudocode
For a (2n+1)×(2n+1) weighting mask, it can be divided into 2n rings. If we denote c ( x, y ) as the parameter at (x, y) on the mask and S as the summation of the absolute values of the x and y coordinates (which will have a range of [0,2n] ), the division of the rings can be formulated as follows:
R1 = {c( x, y) : S ( x, y) = 0},
(7)
R j = {c( x, y ) : S ( x, y ) = j − 1 , x = 0 or y = 0 } ∪ {c( x, y ) : S ( x, y ) = j , x ≠ 0, y ≠ 0)}, j = 2,3,…,2n; x, y ∈ [− n, n ]; x, y ∈ Z.
(8)
D j = {( x, y ) : c ( x, y ) ∈ R j }, j = 1,2, … ,2n. .
(9)
48
Z.-Y. Wei, D.-J. Lee, and B.E. Nelson
c j is calculated as d2
c j (σ ) =
− 1 1 2σ 2 e , where d 2 = m 2π σ j
∑ (x
2
+ y2 ) .
(10)
( x , y )∈D j
The distribution of rings of a 7×7 mask is shown in Fig.2 as an example. Values of
S are shown in each grid of the image. Locations belonging to the same ring are connected by a dashed line in the figure. When the standard deviation is changed from σ 1 to σ 2 , a new tensor can be calculated as T=∑ j
c j (σ 2 ) c j (σ 1 )
mjOj .
(11)
As a result of using this simplified tensor computation, the required number of hardware registers increases linearly instead of quadratically with increasing mask size. In this paper, spatial smoothing instead of spatio-temporal smoothing is used due to the difficulty of implementing temporal smoothing in hardware. Nevertheless, this computation method works for temporal smoothing as well. Although the accuracy of the ring approximation decreases as the mask size increases, acceptable accuracy is obtained with the current settings as shown in the experiment. Using a large mask size is not necessary.
Fig. 2. The distribution of rings of a 7 by 7 mask
3 Experimental Results The proposed algorithm was simulated in MATLAB to evaluate its performance. The algorithm was tested on the Yosemite sequence and the Flower Garden sequence. The results for the Yosemite sequence are shown in Table 1. The first weighting mask in the proposed algorithm is a 5×5 mask whose parameters are ones and
A Hardware-Friendly Adaptive Tensor Based Optical Flow Algorithm
49
Δσ = 0.5 , t c = 0.001 , and titer = 10. Two limits σ max = 8 , σ min = 1 were set for the standard deviation σ to make sure it is within a reasonable range. Table 1. Experiment data on Yosemite sequence n
ACUR1
2 3 4 5
11.73 9.12 7.65 6.75
° ° ° °
ACUR2
° ° ° °
11.73 9.12 7.65 6.77
ACUR3
° ° ° °
11.89 9.13 7.56 6.66
ACUR4 22.34 22.69 22.93 23.22
° ° ° °
AVG ITER1 2.31 2.08 1.85 1.66
AVG ITER2 4.12 4.04 3.97 3.90
The accuracy of these results is measured in angular error as shown in columns 2-5, where n is the half size of the second mask (column 1). ACUR1 is the accuracy of the proposed algorithm, and ACUR2 is the accuracy of the same algorithm without the simplified tensor computation. ACUR3 is the highest accuracy obtained in the work from [6] by tweaking different standard deviations manually, and ACUR4 is the lowest accuracy of this algorithm. AVG ITER1 represents the average iterations per pixel using the proposed algorithm. AVG ITER2 represents the average iterations per pixel using the searching scheme in [3]. The proposed algorithm uses a simplified tensor computation method which reduces the number of hardware registers required for implementation. We compare the accuracy with (ACUR1) and without simplified tensor computation method (ACUR2) and conclude that the proposed simplification process does not affect the accuracy. The proposed algorithm ACUR3 and ACUR4 are obtained by setting the first weighting mask in algorithm [6] the same as that in the proposed algorithm and increasing the standard deviation for the second weighting process from 0.5 to 8 at a step of 0.5. ACUR1 is very close to the highest accuracy (ACUR3) and much better than the lowest (ACUR4). This demonstrates the effectiveness of the proposed weights searching strategy. The average number of iterations required for the proposed searching strategy is compared to those in [3] using AVG ITER1 and AVG ITER2, respectively. The 8th frame of the Yosemite sequence and the 10th frame of the Garden sequence and their optical flow fields using the proposed algorithm are shown in Fig. 3 ( n = 5 and the others settings are the same as the above).
4 Conclusions Using the proposed adaptive algorithm, the optimal parameters for the weighting process can be determined. The accuracy is close to or even better than the best results obtained by manually tweaking the parameters. Also, using the proposed efficient tensor computation method, the number of iterations required is reduced around 2× and the computation can be better pipelined in hardware. Of importance, this optimization is also effective in software implementations of optical flow. Our next step is to implement the proposed algorithm in FPGA.
50
Z.-Y. Wei, D.-J. Lee, and B.E. Nelson
(a)
(b)
(c)
(d)
Fig. 3. Image sequences and optical flow fields
Acknowledgment This work was supported in part by David and Deborah Huber.
References 1. Farnebäck, G.: Very high accuracy velocity estimation using orientation tensors, parametric motion, and simultaneous segmentation of the motion field. In: Proc. ICCV, vol. 1, pp. 77–80 (2001) 2. Farnebäck, G.: Fast and accurate motion estimation using orientation tensors and parametric motion models. In: Proc. ICPR., vol. 1, pp. 135–139 (2000) 3. Liu, H., Chellappa, R., Rosenfeld, A.: Accurate dense optical flow estimation using adaptive structure tensors and a parametric model. IEEE Trans. Image Processing 12, 1170– 1180 (2003) 4. Haussecker, H., Spies, H.: Handbook of Computer Vision and Application, vol. 2, ch. 13, Academic, New York (1999) 5. Wang, H., Ma, K.: Structure tensor-based motion field classification and optical flow estimation. In: Proc. ICICS-PCM, vol. 1, pp. 66–70 (2003) 6. Previous publication hidden for blind review 7. Correia, M., Campilho, A.: Real-time implementation of an optical flow algorithm. In: Proc. ICIP, vol. 4, pp. 247–250 (2002) 8. Zuloaga, A., Martín, J.L, Ezquerra, J.: Hardware architecture for optical flow estimation in real time. In: Proc. ICIP, vol. 3, pp. 972–976 (1998) 9. Martín, J.L., Zuloaga, A., Cuadrado, C., Lázaro, J., Bidarte, U.: Hardware implementation of optical flow constraint equation using FPGAs. In: Computer Vision and Image Understanding, vol. 98, pp. 462–490 (2005)
A Hardware-Friendly Adaptive Tensor Based Optical Flow Algorithm
51
10. Díaz, J., Ros, E., Pelayo, F., Ortigosa, E.M., Mota, S.: FPGA-based real-time optical-flow system. IEEE Trans. Circuits and Systems for Video Technology 16(2), 274–279 (2006) 11. Middendorf, M., Nagel, H.–H.: Estimation and interpretation of discontinuities in optical flow fields. In: Proc. ICCV, vol. 1, pp. 178–183 (2001) 12. Kühne, G., Weickert, J., Schuster, O., Richter, S.: A tensor-driven active contour model for moving object segmentation. In: Proc. ICIP, vol. 2, pp. 73–76 (2001)
Image Segmentation That Optimizes Global Homogeneity in a Variational Framework Wei Wang and Ronald Chung Department of Mechanical and Automation Engineering The Chinese University of Hong Kong Shatin, Hong Kong, China {wangwei,rchung}@mae.cuhk.edu.hk
Abstract. A two-phase segmentation mechanism is described that allows a global homogeneity-related measure to be optimized in a level-set formulation. The mechanism has uniform treatment toward texture, gray level, and color boundaries. Intensities or colors of the image are first coarsely quantized into a number of classes. Then a class map is formed by having each pixel labeled with the class identity its gray or color level is associated with. With this class map, for any segmented region, it can be determined which pixels inside the region belong to which classes, and it can even be calculated how spread-out each of such classes is inside the region. The average spread-size of the classes in the region, in comparison with the size of the region, then constitutes a good measure in evaluating how homogeneous the region is. With the measure, the segmentation problem can be formulated as the optimization of the average homogeneity of the segmented regions. This work contributes chiefly by expressing the above optimization functional in such a way that allows it to be encoded in a variational formulation and that the solution can be reached by the deformation of an active contour. In addition, to solve the problem of multiple optima, this work incorporates an additional geodesic term into the functional of the optimization to maintain the active contour’s mobility at even adverse condition of the deformation process. Experimental results on synthetic and real images are presented to demonstrate the performance of the mechanism.
1
Introduction
Image segmentation is an important problem in image processing and computer vision, with applications encompassing pattern recognition, image understanding, and data transmission. It is to divide an image into disjointed collections of pixels so that each collection represents a surface or object. Much of the previous work is based on the postulate that pixels in the same collection are more or less homogeneous in their brightness or texture information, and pixels from adjacent collections are not.
Corresponding Author.
G. Bebis et al. (Eds.): ISVC 2007, Part II, LNCS 4842, pp. 52–61, 2007. c Springer-Verlag Berlin Heidelberg 2007
Image Segmentation That Optimizes Global Homogeneity
53
Approaches for gray level or color image segmentation could be categorized as boundary based [1], [2] and region based [3], [4], [5], [6], [7]. In general, methods such as [4] [7], that are based upon region features or more precisely the statistical characteristics of intensity distribution in the image, are more robust than the boundary based ones. It is for the reason that a region by nature must have a closed boundary, whereas bridging isolated edge elements in the boundary based methods to form closed boundaries is often a nontrivial task, and it is especially so if the image is of weak contrast. However, in the region-based approach, if splitand-merge or alike mechanism that works pixel-by-pixel is used for separating the regions, the resultant region boundaries are often shaggy due to the local nature of decision-making in the mechanism. Another problem of the split-andmerge or alike mechanism is, because of the absence of the notion of boundary, introducing explicit encouragement of smoothness in the segmentation boundary is difficult. Co-presence of texture regions in the image would add further complexity to the segmentation problem. Either specific methods for texture segmentation [8] [9] are designed to augment the original process, or specific discriminants [4] [10] to describe the texture’s characteristic are needed. For images with both gray level (including color) regions and texture regions, multi-channel information [8] [6] or features derived from Gabor filters [9] etc. are generally required to realize segmentation. To our knowledge, Deng’s work [11] is one of the few that address uniform treatment to gray level, color, and texture segmentation. The work describes a segmentation method that is based on intensity (gray level or color vector) classes, but could also handle texture regions in no different treatment. Intensities or colors of the image are first quantized into a few major classes, and each pixel is labeled with the class number its intensity or color is associated with. A homogeneity-related measure which is about the ratio of the region size to the average class spread is then defined. By the use of a mechanism that minimizes the measure, the image can be divided into segments that contain uniformly distributed classes. In [11], the measure is used first to outline points that are located around the center of the desired regions, and some seed regions are formed around those points. The regions are then grown and merged under a heuristic mechanism that aims at minimizing the above measure on the way. Definable for the entire image domain, the homogeneity-related measure is however only used in Deng’s work as a local measure in a split-and-merge-like mechanism. More precisely, the measure is used as a local operator to indicate the possibility of a pixel as being on the boundary of a region or in the middle of it. Seed regions’ selection, region growing, region merging, and design of the stopping condition constitute the core of the mechanism. There is no encouragement of smoothness in the segmentation boundary, nor is the mechanism formulated in an analytical fashion. In this work, we propose a mechanism that allows a global form of the homogeneity-related measure to be optimized in a variational framework. More precisely, the measure is optimized under the level set formulation, as the
54
W. Wang and R. Chung
deformation of an active contour in the image domain. The measure is defined not locally but upon the entire image, thus having the heuristic part of the design greatly simplified. The mechanism inherits the property of having uniform treatment toward gray level, color, and texture regions in an image. Ever since level set method was introduced by Osher and Sethian [12], it has been widely used in active contour based image segmentation schemes [2], [7], [3], [4], [5], [8] for its many advantages including flexibility, and ease of change of region topology at any stage of the boundary evolution process. In particular, it allows smoothness constraint to be introduced explicitly to the segmentation boundaries. The variational mechanism could also simplify the evolution process by having less parameters to deal with. As the first attempt to directly minimize the homogeneity-related measure in a global way, this work is restricted to two-phase segmentation (segmentation of foreground and background in an image) only. In such a case, only one level set function needs be employed. The measure’s minimization is tackled by solving the corresponding Euler-Lagrange function, and realized by iteratively evolving the related PDE’s to the steady state. In addition, to deal with the problem of multiple minima, we introduce a geodesic term to the functional of the minimization. The term is to maintain mobility of the active contour even at adverse initialization from the user or at adverse condition of the evolution process. The proposed solution has the following assumptions: segments in the image contain uniformly distributed classes, and the two phases can be separated by distinguishable patterns formed by the classes. The rest of the paper is organized as follows. In section 2, the homogeneityrelated measure adopted in this work is outlined. In section 3, we show how the measure can be expressed in the level set formulation for minimization. In section 4, experimental results with performance comparison with those of other mechanisms are presented. In section 5 we draw the conclusion and indicate possible future work.
2
Segmentation Criterion
As in the work of Deng et al. [11], intensities or colors of the input image are first coarsely quantized into a few classes. For gray level image, the intensity values are normalized according to approximate prior knowledge of the number of classes in the image. Then each pixel is labeled with the nearest class number its gray level or color is associated with, forming a class map which is of the same size of the original image. As for color image, more sophisticated method can be used, like that in [13]. In our experiments, generally 10∼20 classes were used to process each image. With the above process, a class map is attained that has each pixel attached with a particular class label. The class map then replaces the original image in the subsequent segmentation process. Notice that it is not required that the labeling be perfect; the subsequent segmentation process has tolerance toward incorrect labels that are often inevitable in a step so preliminary.
Image Segmentation That Optimizes Global Homogeneity
55
The segmentation criterion, or the optimization measure, is then defined over the class map. Below we first briefly review the criterion J¯ used in [11]. 2.1
Deng’s Criterion
Let Z = {z : z = (x, y)} be the set ofall N pixels in the class map, and m be z, in which z ∈ Z. Suppose Z has been the center of the set. That is, m = N1 labeled as consisting of n classes {Zp : p = 1, ..., n}, and m p is the center of the totally Np data points in the class Zp . That is, mp = N1p z, in which z ∈ Zp . Notice that the n class-groups are not necessarily disjointed in the image domain: there could be significant overlap between some of them. If the image is rather homogeneous (e.g., like a checker board), all class-groups (i.e., the two classes of black pixels and white pixels respectively) span more or less the entire image; otherwise the class-groups have less overlap. Then moments ST and SW can be defined as ST = z∈Z z − m2 and two n SW = p=1 z∈Zp z − mp 2 . While ST describes the spread of the image from the image center, or equivalently speaking the size of the image, SW describes the average spread of the class groups. Again, for a homogeneous image, ST and SW are of about the same value; for inhomogeneous image, SW is generally much smaller than ST . W Then a measure J can be defined as J = STS−S , which compares the image W size with the average class spread. Small J value indicates homogeneous distribution of classes in the class map, and large J value indicates that the class-groups are distinctly separated. Now suppose the class map is segmented into a number of regions (generally each region could contain several classes, and the members of one class could be distributed over multiple regions). Then denote the J value on each region the whole k as Jk (in other words, J is calculated over each region instead of map), and define J¯ as the weighted average of all the Jk ’s: J¯ = N1 k Mk Jk , where Mk is the number of pixels in region k. Generally a good segmentation that comprises homogeneous regions will has small J¯ value. 2.2
Our Criterion
The J¯ can be used as a measure to drive the segmentation process. We shall refer to it the inhomogeneity measure, as the higher is its value the more inhomogeneous are the segmented regions, and we desire a segmentation with a small value of it. However, it is difficult to minimize J¯ globally over the entire image domain, and in the work [11] it is used only as a local operator. ¯ Specifically, we derive In contrast, we prefer a more global way of utilizing J. ¯ J’s first variation, and adopt gradient descent method to find the minimum of the measure. As a first effort in this direction, this work sets the number of segments as two and is restricted to the two-phase segmentation problem. In such a case, only one level set function is needed to embed all segmentation boundaries.
56
W. Wang and R. Chung
Let φ(z, t) represent the level set function defined on the class map Z with time parameter t. The zero level contour separates the class map into interior ¯ and exterior regions. Then the J¯ equation can be reformulated as J(φ(z, t)) = Mi Mo J (φ(z, t)) + J (φ(z, t)), where M is the number of pixels in the interior i o i N N region, and Mo the number of points in the exterior region. The J value defined S −S on the interior region is represented as Ji = TiSW Wi , and J value defined on S
−S
i
the exterior region is represented as Jo = ToSW Wo . o Straight minimization of the global inhomogeneity measure does not always derive the optimal segmentation; there is the notion of multiple local minima. In particular, a region with a radially symmetric distribution of classes could ¯ resulting in immobility of the active contour. Fig. 1 shows an also have small J, example. The pixels in the image can be readily clustered into three classes by intensity values, and a segmentation result as shown in Fig. 1 (c) is obviously preferred. Under such a segmentation, the J¯ value will be nearly zero which is ¯ However, if the active contour moves to a global minimum of the measure J. location as that shown in (b), the J¯ value will also be nearly zero. It indicates ¯ that multiple-minimum property of the measure J.
(a)
(b)
(c)
Fig. 1. Two different segmentation results on image (a) are shown in (b) and (c), both with small J¯ value
To tackle the problem of multiple minima, we introduce a geodesic measure LR + νAR [2] into the functional of the optimization process, where ν is a weight parameter. The first term LR measures the weighted contour length, and the second term AR measures the weighted area of the interior region enclosed by the contour. Details of the terms will be elaborated in the next section. With this additional term to minimize, our mechanism encourages not only homogeneous regions in the segmentation result, but also compact regions, i.e., the region’s boundaries had better fall on edges in the class map. In summary, our mechanism minimizes the measure J¯ + μ(LR + νAR ) in the level-set formulated segmentation process, where μ is a weight parameter.
3
Curve Evolution Scheme
Assume that there are n class-groups Zp (p = 1, ..., n) in the class map Z that is defined on the image domain Ω. A level set function φ(z, t) is defined on Ω, in which z represent a point (x, y) in Ω and t is the time parameter. The two
Image Segmentation That Optimizes Global Homogeneity
57
phases in Ω are separated by the zero level contour of function φ. With derivation similar to that in the work [4], we minimize the functional J¯ with respect to t using the evolution equation derived from function φ. To indicate the interior and exterior regions separated by the zero level contour, a Heaviside function H is defined on function φ: H(φ) = 1 if φ ≥ 0, and H(φ) = 0 if φ < 0. Its derivative is defined by the one dimensional Dirac mead H(φ). Also, we define Hp on each class Zp (p = 1, 2, ..., n) as: sure δ(φ) = dφ Hp (z) = 1 if z ∈ Zp , and Hp (z) = 0 if z ∈ Zp . Then we can express Ji and Jo as: z − mi 2 H(φ)dz STi Ji = − 1 = n Ω −1 (1) 2 SWi p=1 Ω z − mpi H(φ)Hp (z)dz z − mo 2 (1 − H(φ))dz STo Jo = − 1 = n Ω −1 (2) 2 SWo p=1 Ω z − mpo (1 − H(φ))Hp (z)dz where mi is the center of the interior region, mo the center of the exterior region, mpi the center of the members of Zp class in the interior region, and mpo the center of the members of Zp class in the exterior region. In addition, J¯ can be expressed as H(φ)dz H(φ)dz Ω ¯ J(φ) = Ji (φ) + (1 − Ω )Jo (φ) (3) N N It can be seen that J¯ is a functional defined on mi , mo , mpi ’s, mpo ’s (expressed as m’s later) and φ. First, keeping φ fixed and minimizing J¯ with respectÊ to m’s, we can derive Ê Ê zH(φ)dz z(1−H(φ))dz zH(φ)H (z)dz Ω Ω that: mi = Ê H(φ)dz , mo = Ê (1−H(φ))dz , mpi = ÊΩ H(φ)Hpp(z)dz , mpo = Ω Ê ÊΩ z(1−H(φ))Hp (z)dz ,
Ω
Ω
(p = 1, 2, ..., n). (1−H(φ))Hp (z)dz Ω Then, from the Euler-Lagrange equation of function (3), we can derive the ¯ gradient flow for J: n 2 H(φ)dz STi z − mi 2 ∂φ p=1 z − mpi Hp (z) Ω = −δ(φ) − ∂t N SWi STi SWi n 2 z − mo 2 p=1 z − mpo Hp (z) Ω H(φ)dz STo +(1 − ) − N SWo SWo STo 1 (4) + (Ji − Jo ) N As to the geodesic measure LR + νAR , which is equal to Ω gδ(φ)|∇φ| + ν Ω gH(φ) in the level set formulation (g is the edge indicator function defined on the J image), its gradient flow is
∇φ ∂φ = δ(φ) div g − νg (5) ∂t |∇φ|
58
W. Wang and R. Chung
∂φ with boundary condition ∂n = 0, where n denotes the normal to the image boundary ∂Ω, ν is a constant used to speed up the contour’s convergence. Therefore, the combined flow which minimizes the functional J¯+μ(LR +νAR ) is μ weighted summation of Equation (4) and (5). It can be observed that there are only two weight parameters μ and ν. Thus, by the variational formulation the rather complex design in the heuristic approach can be much simplified. In the numerical implementation, the general form of the edge indicator function g [2] on image I is g = 1+|∇G1 σ ∗I|p , (p ≥ 1). In this work, to allow texture structure be processed under the same framework, we use J value instead of the gradient magnitude item |∇Gσ ∗ I| in the g function. The J value is calculated at each pixel in the class map Z with a circular neighborhood of diameter 9 pixels, W . The larger is the J value, the more likely would the by equation J = STS−S W pixel be near the region boundary.
4
Experimental Results
We present experimental results on synthetic and real images to illustrate the performance of the proposed method. In all examples, we set μ = 0.1, ν = 0.1, Δt = 0.1. The initial contour was set as a rectangle as shown in Fig. 2 (a), and the level set function φ was re-initialized every 20 iterations. In fact, the example in Fig. 1 already shows one set of experimental results. Fig. 1 (b) shows the initial location of the contour, and (c) shows the final location of the contour. Fig. 2 (a) shows an image consisting of a textured region and a homogeneous gray region. The white rectangle indicates the location of the initial zero level contour of function φ. Fig. 2 (b) shows the final contour derived by our method with class number n = 10. In comparison with the result derived by JSEG method [11] as shown in (c), our method could derive more accurate and smoother contour. Experiments under the setting μ = 0 and ν = 0 also derived the same segmentation result as in (b), showing that the geodesic measure is not always needed in our method. Experiments nonetheless show that negative impact to the result was not induced by the presence of the geodesic term. Fig. 2(d) shows the result derived for the corrupted image with SN R = 40dB and n = 10; (e) shows the result derived for the same corrupted image but with the class number n increased to 20. Fig. 2(f) shows the result derived for the corrupted image with SN R = 26dB and n = 20. The results show that the proposed mechanism is robust to the increase of noise, and the same result can be obtained over a rather wide range of the preset number of classes. Fig. 3 shows an image consisting of two textured regions with different patterns. Shown in Fig. 3 (a) is the original image with the initial contour superimposed. The result of our method is shown in (b). In comparison with the result of the JSEG method as shown in (c), the boundary from our method was of higher accuracy and smoothness. Fig. 4 illustrates how the segmentation algorithm performed on two images that comprise Brodatz textures [14]. On images shown in Fig. 4, it was set that class number n = 10. The first column shows the original images, the second
Image Segmentation That Optimizes Global Homogeneity
(a)
(b)
(c)
(d)
(e)
59
(f)
Fig. 2. Segmentation result for a synthetic image from the proposed method: (a) initial contour, (b) final contour, (c) result derived from JSEG method for comparison, (d) final contour (of the proposed method) under SN R = 40dB, class number n = 10, (e) SN R = 40dB, n = 20, (f) SN R = 26dB, n = 20
(a)
(b)
(c)
Fig. 3. Segmentation results for an image of two textured regions. (a) initial contour; (b) final contour by our method; (c) final contour by JSEG method.
(a)
(b)
(c)
(d)
(e)
(f)
Fig. 4. Segmentation results for two images that comprise Brodatz textures. (a),(d): original images. (b),(e): segmentation results by our method. (c),(f): segmentation results by the JSEG method.
60
W. Wang and R. Chung
column shows the results derived by our method, and the third column shows the results derived by the JSEG method for comparison. It can be seen that our method derived smoother and more precise region boundaries. Fig. 5 illustrates how the segmentation algorithm performed on a number of real images. To all images shown in Fig. 5, the class number n is set as n = 10. The first row shows the original images, the second row shows the results from our method, and the third row shows the results from the JSEG method for comparison. It seems that on the two color images, the boundaries from the JSEG method are smoother than ours, but upon close examination and comparison with the original images it could be observed that our method actually derived more precise region boundaries. On the second image, the JSEG method had difficulty in achieving the two-phase segmentation; if the merging parameter was increased further, all segments would be merged together. On the third image, our method again derived a more reasonable segmentation result, although still with certain errors. We ascribe the better performance of our method to the use of the J measure in a more global form.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
Fig. 5. Segmentation result on a number of real images. (a),(b),(c): original image. (d),(e),(f): segmentation results by our method. (g),(h),(i): segmentation results by the JSEG method.
Image Segmentation That Optimizes Global Homogeneity
5
61
Conclusion and Future Work
A two-phase segmentation mechanism that allows a global homogeneity-related measure be optimized in a level-set formulation has been presented. The mechanism has uniform treatment toward texture, gray level, and color segmentations, and allows them to co-exist in the image. By allowing the measure to be minimized under a variational method, the mechanism is made much simpler than the heuristic split-and-merge mechanism. In addition, smoothness can be explicitly encouraged to the segmentation boundary, and the homogeneity-related measure can be applied to the entire image domain and be made global. Future work will be upon extending the work for multiple-phase segmentation.
References 1. Kass, M., Witkin, A., Terzopoulos, D.: Snakes: Active contour models. Int’l J. Computer Vision 1(4), 321–331 (1988) 2. Caselles, V., Kimmel, R., Sapiro, G.: Geodesic active contours. Int’l J. Computer Vision 22(1), 61–79 (1997) 3. Samson, C., Blanc-feraud, L., Aubert, G., Zerubia, J.: A level set model for image classification. Int’l J. Computer Vision 40(3), 187–197 (2000) 4. Chan, T.F., Vese, L.A.: Active contours without edges. IEEE Trans. Image Processing 10, 266–277 (2001) 5. Chan, T.F., Vese, L.A.: A level set algorithm for minimizing the mumford-shah functional in image processing. In: Proc. of 1st IEEE Workshop on Variational and Level Set Methods in Computer Vision, pp. 161–168 (2001) 6. Zhu, S.C., Yuille, A.: Region competition: Unifying snakes, region growing, and bayes/mdl for multiband image segmentation. IEEE Trans. Pattern Analysis and Machine Intelligence 18(9), 884–900 (1996) 7. Yezzi, A., Tsai, A., Willsky, A.: A statistical approach to snakes for bimodal and trimodal imagery. In: IEEE Int’l Conf. Computer Vision-II, pp. 898–903 (1999) 8. Chan, T.F., Sandberg, B.Y., Vese, L.A.: Active contours without edges for vectorvalued images. J. Visual Communication and Image Represenation 11(2), 130–141 (2000) 9. Sagiv, C., Sochen, N.A., Zeevi, Y.Y.: Integrated active contours for texture segmentation. IEEE Trans. Image Processing 1(1), 1–19 (2004) 10. Sumengen, B., Manjunath, B.: Graph partitioning active contours for image segmentation. IEEE Trans. Pattern Analysis and Machine Intelligence 28(4), 509–521 (2006) 11. Deng, Y., Manjunath, B., Shin, H.: Color image sementation. In: IEEE Comput. Soc. Conf. Computer Vision and Pattern Recognition-II, pp. 23–25 (1999) 12. Osher, S., Sethian, J.: Fronts propagation with curvature dependent speed: Algorithms based on hamilton-jacobi fomulations. J. Comput. Phys. 79, 12–49 (1988) 13. Deng, Y., Kenney, C., Moore, M.S., Manjunath, B.: Peer group filtering and perceptual color image quantization. In: IEEE Int’l Symposium on Circuits and SystemsIV, pp. 21–24 (1999) 14. Brodatz, P.: Textures: A Photographic Album for Artists and Designers. New York, Dover (1966)
Image and Volume Segmentation by Water Flow Xin U. Liu and Mark S. Nixon ISIS group, School of ECS, University of Southampton, Southampton, UK
Abstract. A general framework for image segmentation is presented in this paper, based on the paradigm of water flow. The major water flow attributes like water pressure, surface tension and capillary force are defined in the context of force field generation and make the model adaptable to topological and geometrical changes. A flow-stopping image functional combining edge- and region-based forces is introduced to produce capability for both range and accuracy. The method is assessed qualitatively and quantitatively on synthetic and natural images. It is shown that the new approach can segment objects with complex shapes or weak-contrasted boundaries, and has good immunity to noise. The operator is also extended to 3-D, and is successfully applied to medical volume segmentation.
1 Introduction Image segmentation is a fundamental task. For example, in retinal images, vessel structures can provide useful information like vessel width, tortuosity and abnormal branching which are helpful in medical diagnoses. However, natural images often comprise topologically and/or geometrically complex shapes, like the vessels. The complexity and variability of features, together with the image imperfections such as intensity inhomogeneities and imaging noise which cause the boundaries of considered features discontinuous or indistinct, make the task very challenging. Many methods have been proposed in medical image segmentation. Active contours or snakes [1] are one of the most powerful established techniques. An active contour is essentially a parameterized curve which evolves from an initial position to the object’s boundary so that a specified energy functional can be minimized. The methods achieve desirable features including inherent connectivity and smoothness that counteract object boundary irregularities and image noise, so they provide an attractive solution to image segmentation. However, there are still many limitations. Classical parametric snakes use edge information and need good initialization for a correct convergence. Moreover, they cannot handle topological and geometrical changes like object splitting or merging and boundary concavities. Many methods have been proposed to overcome these problems. Balloon models [2], distance potentials [3], and gradient vector flow (GVF) [4] have been developed to solve the problems of initialization and concave boundary detection. Snake energy functionals using region statistics or likelihood information have also been proposed [5, 6]. A common premise is to increase the capture range of the external forces to guide the curve towards the boundaries. For complex topology detection, several authors have proposed adaptive methods like the T-snake [7] G. Bebis et al. (Eds.): ISVC 2007, Part II, LNCS 4842, pp. 62–74, 2007. © Springer-Verlag Berlin Heidelberg 2007
Image and Volume Segmentation by Water Flow
63
based on repeated sampling of the evolving contour on an affine grid. Geometric active contours [8, 9] have also been developed where the planar curve is represented as a level set of an appropriate 2-D surface. They work on a fixed grid and can automatically handle topological and geometrical changes. However, many methods solve only one problem whilst introducing new difficulties. Balloon models introduce an inflation force so that it can “pull” or “push” the curve to the target boundary, but the force cannot be too strong otherwise “weak” edges would be overwhelmed. Region-based energy can give a large basin of attraction and can converge even when explicit edges do not exist but it cannot yield as good localization of the contour near the boundaries as can edge-based methods. Level set methods can detect complex shapes well but also increase the complexity since a surface is evolved rather than a curve. Instead of model-based methods, some proposed the morphological watershed based region growing techniques [10, 11]. The approach is based on the fact that smooth surfaces can be decomposed into hills and valleys by studying critical points and their gradient. Considering pixel properties (intensity or gradient) as elevation and then simulating rainfall on the landscape, rain water will flow from areas of high altitude along lines of steepest descent to arrive at some regional minimal height. The catchment basins are defined as the draining areas of its regional minima and their boundaries can then be used in object extraction. Though assuming water collection, the method does not use the features of water itself and focuses on the image’s geographical features. The non-linearity arising from issues like finding steepest descent lines between two points makes the method complicated. Moreover, the region growing framework often yields irregular boundaries, over-segmentation and small holes. Unlike the mathematical models introduced above, we propose a physical model focusing on water itself rather than the landscape of images. Water is chosen because features like fluidity and surface tension can lead to topological adaptability and geometrical flexibility, as well as contour smoothness. We completely redefined the basis of our previous water-flow based segmentation approaches [12, 13] by adopting the force filed theory which has been used in feature extractions [14]. The method shows decent segmentation performance in quantitative and qualitative assessments. Further, the nature of physical analogy makes the working principles and parameters easy and explicit to interpret. The 3D extension is also more natural and straightforward than mathematical models like T-surfaces [7].
2 Methodology Water flow is a compromise between several factors: the position of the leading front of a water flow depends on pressure, surface tension, and adhesion (if any). There are some other natural properties like turbulence and viscosity, which are ignored here. Image edges and some other characteristics that can be used to distinguish objects are treated as the “walls” terminating the flow. The final static shape of the water should give the related object’s contour. Some physical principles are first introduced. The flow velocity is determined by total flow driving force and the flow resistance. The relationship between the flow velocity v, the flow resistance R and the total driving force F is given by:
64
X.U. Liu and M.S. Nixon
v = FD
A⋅R
(1)
where A is the cross-sectional area of the flowing water and is set to unity here. FD comprises the pressure, surface tension and adhesion. The flow is mainly driven by the pressure pointing outwards. The surface tension, which is the attractive force between water surface elements, can form a water film to bridge gaps in object boundaries. The adhesion, which is defined as the attractive force from image edges to water surface, can assist water in flowing inside narrow braches. For the image analogy, one pixel in the image is considered to be one basic water element. An adaptive water source is assumed at the starting point(s) so that the water can keep flowing until stasis, where flow ceases. The image is now separated into dry and flooded areas by the water. Only elements at water contours are adjacent to dry regions, so only contour elements are of interest in the implementation. The implementation of the flow process of one contour element is shown by the flowchart in figure 1. Applying same procedures to all the contour elements forms one complete flow iteration. As shown by figure 1, the flow process is separated into two stages – the acceleration stage and the flow stage. In the first stage, the considered element achieves an initial flow velocity determined by the driving force FD and resistance R. Then we examine the movements at possible flow directions pointing from the considered contour element toward adjacent dry points one by one. For the direction i, the component velocity scalar vi is calculated. If vi > 0, the process then progress to the next stage, where the element is assumed to be flowing to the dry position related to the direction i and some image force is acting on it. To reconcile the flow velocity with the image force and hence conduct the movement decision processor, dynamical formulae are used. The movement decision is made according to the sign of J and
J = mvi 2 2 + Fi S
(2)
where S and m are defined as the fixed flow distance in one iterative step and the water element mass. In this equation, Fi is the scalar image force at direction i. It is defined to be positive if consistent with i, and negative if opposite. J ≥ 0 means that the initial kinetic energy exceeds the resistant work produced by Fi during S and thus the contour element is able to flow the target position at direction i. The definitions and calculations of the factors and parameters introduced above then need to be clarified. In this paper, the force field theory is embodied into the water flow model to define the flow driving force FD.
Fig. 1. The flowchart of implementing the flow process for one water contour element
Image and Volume Segmentation by Water Flow
65
2.1 Force Field, Water Driving Force, and Flow Velocity In this new water flow model, each water element is treated as a particle exhibiting attraction or repulsion to other ones, depending on whether or not it is on the contour / surface. The image pixels at the dry areas are considered as particles exhibiting attractive forces to water contour elements. Now both the water elements and the dry area image pixels are assumed to be arrays of mutually attracted or repelled particles acting as the sources of Gaussian force fields. Gauss’s law is used as a generalization of the inverse square law which defines the gravitational and/or electrostatic force fields. Denoting the mass value of pixel with position vector rj as L(rj), we can define the total attractive force at rj from other points within the area W as FD ( r j ) =
∑
j∈ W , j ≠ k
L ( rk )
( r j − rk ) |r j − r k | 3
(3)
Equation (3) can be directly adopted into the framework of the water flow model, provided the mass values of different kinds of elements are properly defined. Here the magnitude of a water element is set to 1, and that of a dry image pixel is set to be the edge strength at that point (an approximation of the probability that the considered pixel is an edge point). The mass values of water contour elements and image pixels should be set positive, and those of the interior water elements should be negative because equation (3) is for attractive forces. From equation (3), the flow velocity is inversely proportional to the resistance of water (the cross-sectional area A has been set to 1). In a physical model, the resistance is decided by the water viscosity, the flow channel and temperature etc. Since this is an image analogy which offers great freedom in selection of parameter definitions, we can relate the resistance definition to certain image attributes. For instance, in retina vessel detection, if the vessels have relatively low intensity, we can define the resistance to be proportional to the intensity of the pixel. Further, if we derive the resistance from the edge information, the process will become adaptive. That is, when the edge response is strong, resistance should be large and the flow velocity should be weakened. Thereby, even if the driving force set by users is too “strong”, the resistance will lower its influence at edge positions. Thereby the problem in balloon models [2], where strong driving forces may overwhelm “weak” edges, can be suppressed. Therefore, such a definition is adopted here. The flow resistance R at arbitrary position (u, v) is defined as a function of the corresponding edge strength:
R = exp{k ⋅ E(u, v)}
(4)
where E is the edge strength matrix and the positive parameter k controls the rate of fall of the exponential curve. If we assign a higher value to k, the resistance would be more sensitive to the edge strength, and a lower k will lead to less sensitivity. Substitute equations (3) and (4) to equation (1), the resultant flow velocity can be calculated. From figure 1, we can see that each possible flow direction is examined separately, so the component velocity at the considered direction, vi needs to be computed:
vi = v ⋅ cos γ
(5)
where γ is the angle between the flow direction i and the resultant velocity direction.
66
X.U. Liu and M.S. Nixon
2.2 Image Forces If vi ≤ 0, the contour element will not flow to the corresponding direction i. Otherwise, the movement decision given by equation (2) should be carried out, during which the image force is needed. The gradient of an edge response map is often defined as the potential force in active contour methods since it gives rise to vectors pointing to the edge lines [3]. This is also used here. The force is large only in the immediate vicinity of edges and always pointing towards them. The second property means that the forces at two sides of an edge have opposite directions. Thus it will attract water elements onto edges and prevent overflow. The potential force scalar acting on the contour element starting from position (xc, yc) and flowing toward target position (xt, yt) is given by:
FP ,i = [∇E( xt , yt )] cos β
(6)
where ∇E is the gradient of the edge map and β is the angle between the gradient and the direction i pointing from (xc, yc) to (xt, yt). The gradient of edges at the target position rather than that at the considered water contour position is defined as the potential force because the image force is presumed to act only during the second stage of flow where the element has left the contour and is moving to the target position. The forces defined above work well as long as the gradient of edges pointing to the boundary is correct and meaningful. However, as with corners, the gradient can sometimes provide useless or even incorrect information. Unlike the method used in the inflation force [2] and T-snakes [7], where the evolution is turned off when the intensity is bigger than some threshold, we propose a pixel-wise regional statistics based image force. The statistics of the region inside and outside the contour are considered respectively and thus yield a new image force: FS ,i = −
nint nint + 1
(I( xt , yt ) − μint )2 +
next next − 1
(I( xt , yt ) − μext )
2
(7)
where subscripts “int” and “ext” denote inner and outer parts of the water, respectively; μ and n are the mean intensity and number of pixels of each area, separately; I is the original image. The equation is deduced from the Mumford-Shah functional [6]: F1 (C ) + F2 (C ) = ∫inside ( C ) | I ( x , y ) − μint | + ∫outside ( C ) | I ( x , y ) − μext | 2
2
(8)
where C is the closed evolving curve. If we assume C0 is the real boundary of the object in the image, then when C fits C0, the term will achieve the minimum. Instead of globally minimizing the term as in [6], we obtain equation (9) by looking at the change of the total sum given by single movement of the water element. If an image pixel is flooded by water, the statistics of the two areas (water and non-water) will change and are given by equation (9). The derivation has been shown in [13, 14]. Edge-based forces provide a good localization of the contour near the real boundaries but have limited capture range whilst region-based forces have a large basin of attraction and relatively low detection accuracy. A convex combination method is chosen to unify the two functionals:
Image and Volume Segmentation by Water Flow
Fi = α FP ,i + (1 − α ) FS ,i
67
(9)
where all terms are scalar quantities, and α (0≤α≤1) is determined by the user to control the balance between them. 2.3 Final Movement Decision
If the scalar image force is not less than zero, then J given by equation (2) must be positive (because the initial velocity vi needs to be positive to pass the previous decision process as shown in figure 1). Since only the sign of J is needed in this final decision-making step, the exact value of J need not be calculated in this case and the element will be able to flow to the target position. If the scalar image force, however, is negative (resistant force), equation (2) must be calculated to see if the kinetic energy is sufficient to overcome the resistant force. As the exact value of J is still unnecessary to compute, equation (2) can be simplified
J = λ vi + Fi 2
(10)
where λ is a regularization parameter set by users which controls the tradeoff between the two energy terms. It can be considered as the combination of mass m and displacement S. Its value reflects smoothing of image noise. For example, more noise requires larger λ. The sign of J from equation (10) then determines whether the considered element can flow to the target position at direction i. 2.4 Three Dimensional Water Flow Model
The extension of the water flow model to 3-D is very straightforward and natural because the physical water flow process is just three dimensional. Still, assume one voxel of the volume matrix represents one basic water element, and define the water elements adjacent to dry areas as surface elements under certain connectivity (here the 26-connectivity is chosen). Now the forces acting on surface elements are of interest. The implementation process is exactly the same as the one shown in figure 1. The difference is that now the factors discussed above need to be extended to 3-D. Equation (3) is again used to calculate the total driving forces given that the position vectors r’s are three dimensional. The definition of flow resistance is also unchanged, provided that the edge / gradient operator used is extended to 3-D. Simply defining the image force functions given by equations (6), (7) and hence (9) in Ω ⊂ R3, the same equations then can be used to calculate the 3-D force functionals.
3 Experimental Results The new technique is applied to both synthetic and natural images, and is evaluated both qualitatively and quantitatively. 3.1 Synthetic Images
First, the goodness of analogy to water flow is examined. Figure 2 indicates water flowing in a cube-like object with and without adhesive force. The evolution is
68
X.U. Liu and M.S. Nixon
(a) without adhesion
(b) with adhesion
(c) without adhesion
(d) with adhesion
Fig. 2. Imitating water flowing inside a tube-like course with a narrow branch
initialized at the left end of the pipe. We can see that the water stops at the interior side of the step edge and the front forms a shape which is similar to that observed on naturally flowing water. Figures 2(a) and (b) have slightly different front shapes – the two edges of the water flow faster due to the effect of adhesive forces. The adhesion also helps flow into narrow branches, as indicated in figure 2(d). Without the adhesive force, the surface tension will bridge the entrance of the very narrow branch and thus the water cannot enter it, as shown in figure 2(c). Introducing the region-based force functional enables the operator to detect objects with weak boundaries, as shown in figure 3. The region-based force will stop the flow even if there is no marked edge response. The segmentation result here is mainly determined by the value of α. To assess the immunity to noise, a quantitative performance evaluation is also performed. The level set method based on regional statistics [6] is chosen for comparison. The test image is generated so that the ground truth segmentation result can be compared. The shape of the considered object is designed as a circle with a boundary concavity to increase the detection difficulty. Different levels of Gaussian and Impulsive noise are added. The mean square error (MSE) is used to measure the performance under noise. ID
M SE = ∑ d k k =1
2
m ax( I D , I I )
(11)
where II and ID are the number of ideal and detected contour points respectively and dk is the distance between the kth detected contour point and the nearest ideal point. The
Fig. 3. Segmentation of the object with weak-contrasted boundaries (α=0)
Image and Volume Segmentation by Water Flow
69
quantitative results are shown by figure 4(a) and (b). For both noise, the performance of the water flow model is markedly better than the level set operator especially when the noise contamination is severe (SNR less than 10dB). The performance superiority of the water operator under noisy conditions is further illustrated qualitati- vely by the segmentation results for Gaussian noise (SNR: 13.69) and impulsive noise (SNR: 11.81), see figure 4(c) to (f). This robustness to noise is desirable for many practical applications like medical image segmentation.
(a)
(c) LS (MSE: 0.83) (d) WF (MSE: 0.13)
(b)
(e) LS (MSE: 1.02)
(f) WF (MSE: 0.31)
Fig. 4. Quantitative evaluation and detection examples for level set method (LS) and water flow operator (WF), left for Gaussian noise and right for Impulsive noise
3.2 Natural Images
Natural images with complex shape and topology are also assessed. Figure 5 shows the result for the image of a river delta with different parameters, where the river is the target object. It is suited to performance evaluation since gaps and “weak” edges exist in the image. One example is the upper part of the river, where boundaries are blurred and irregular. There are also inhomogeneous areas inside the river, which are small islands and have lower intensity. Our water flow based operator can overcome these problems. As shown in figure 5(a), a reasonably accurate and detailed contour of the river is detected. At the upper area, the very weak boundaries are also detected. This is achieved by using high value of k in equation (4) that gives the operator a high sensitivity to edges. The contour is relatively smooth by virtue of surface tension. The fluidity leading to topological adaptability is shown well by successful flow to the branches at the lower area. Most of them are detected except failure at several narrow branches. The barriers are caused either by natural irregularities inside them or noise.
70
X.U. Liu and M.S. Nixon
(a) α=0.5, λ=1, k=50
(b) α=0.5, λ=1, k=0 Fig. 5. Water-flow detection results for river delta photo with different parameters: increased λ reduces the significance of image forces, and smaller k makes flow less sensitive to edges, therefore the detail detection level is lower in (b)
Different initializations inside the river were tried and with the same parameters chosen, the results are almost the same, as expected. The operator is insensitive to the source positions. By changing the parameters, however, some alternative results can be achieved. For example, figure 5(b) shows a segmentation of the whole basin of the river. It is analogy to a flood from the river. The water floods the original channels and stops at the relatively high regions. This shows the possibility of achieving different level of detail just by altering some parameters. The new water flow model is also applied to segment the complex and variable anatomical features in medical images that typically have limited quality and are often contaminated by noise. Figure 6 presents the example results for several MR images. The water sources are all set inside the object of interest and parameter are chosen as k=20, α=0.5, λ=1. The resultant contours are relatively smooth by virtue of surface
Image and Volume Segmentation by Water Flow
(a)
(b)
71
(c)
Fig.6. Segmentation results in real medical images: a) brain in a sagittal MR image, b) carotid artery in a MR carotid MRA image and, c) grey/white matter interface in MR brain image slice
tension. The operator can find weak-contrasted boundaries as shown by figure 6(a) where the indistinct interface between the brain and the spine is detected. This is achieved by combining a high value of k that gives the operator a high sensitivity to edge response and the region-based forces. The fluidity of water leads to both topological adaptability and geometrical flexibility, and the capillary force assists in detecting narrow tube-like features. Figure 6(b) and (c) illustrate those – the complex structures and irregular branches are segmented successfully. Retinal vessel segmentation plays a vital role in medical imaging since it is needed in many diagnoses like diabetic retinopathy and hypertension. The irregular and complex shape of vessels requires the vessel detector to be free of topology and geometry. Furthermore, digital eye fundus image often have problems like low resolution, bad quality and imaging noise. The water flow model is a natural choice. Figure 7 shows the segmentation results. Multiple initializations/water sources are set inside the vessel
(a)
(b)
Fig. 7. Segmenting vessels in retinal images with low resolution and quality (k=50, α=0.5, λ=1)
72
X.U. Liu and M.S. Nixon
structures to lighten the problems caused by gaps on the vessels. In figure 7(a), multiple flows of water merged, leading to a single vessel structure. In figure 7(b), some water flows merged and some remained separated. This can be improved by post-processes like gap-linking techniques.
(a)
(b)
(c)
Fig. 8. An example of the MRI volume segmentation by 3-D water flow analogy: a) the water flow model segments the lateral ventricles of brain; b) – c) cross-sections of the results
3.3 Medical Images Volume Segmentation
The 3-D water flow model is expected to have comparative performance in volume segmentation. We have applied our 3-D water model to a variety of medical images so as to segment anatomical structures with complex shapes and topologies. Figure 8
Image and Volume Segmentation by Water Flow
73
presents a typical example where the model is applied to a 181×217×181 MR image volume of a human brain. The water source is set inside the lateral ventricles and the parameters are set at k=5, α=0.5, λ=1. The operator detects most parts of the lateral ventricles. Two cross-sections of the fitted model are also shown in figure 8.
4 Conclusions This paper introduces a new general framework for image segmentation based on a paradigm of water flow. The operator successfully realizes the key attributes of flow process under the structure of force field generation. The resistance given by images is defined by a combination of object boundary and regional information. The problems of boundary concavities and topological changes are settled whist the attractive feature of snakes, the smoothness of the evolving contour, is achieved. Those are approved by the results on synthetic and real images. Good noise immunity is justified both quantitatively. Besides, the complexity of the algorithm is relatively low. Therefore the method is expected to be of potential use in practical areas like medical imaging and remote sensing where target objects are often complex shapes corrupted by noise. A 3-D version of the operator is also defined and implemented, and is applied to the medical volume segmentation area. The algorithm here uses the simple edge potential forces. In the future we seek to embody more refined edge detectors [15] or new force functionals like GVF [3] into the water flow based framework.
References [1] Kass, M., Witkin, A., Terzopoulos, D.: Snakes: Active contour models. Int’l. J. of Comp. Vision 1(4), 321–331 (1988) [2] Cohen, L.D.: On active contour models and balloons, CVGIP. Image Understanding 53(2), 211–218 (1991) [3] Cohen, L.D., Cohen, I.: Finite element methods for active models and balloons for 2-D and 3-D images. IEEE Trans. PAMI 15, 1131–1147 (1993) [4] Xu, C., Prince, J.L.: Snakes, shapes, and gradient vector flow. IEEE Trans. Image Processing 7(3), 359–369 (1998) [5] Figueiredo, M., Leitao, J.: Bayesian estimation of ventricular contours in angiographic images. IEEE Trans. Medical Imaging 11, 416–429 (1992) [6] Chan, T.F., Vese, L.A.: Active contours without edges. IEEE Trans. Image Processing 10, 266–276 (2001) [7] McInerney, T., Terzopoulos, D.: T-snakes: topologically adaptive snakes. Medical Image Analysis 4, 73–91 (2000) [8] Casselles, V., Kimmel, R., Spiro, G.: Geodesic active contours. Int’l Journal of Computer Vision 22(1), 61–79 (1997) [9] Malladi, R., et al.: Shape modeling with front propagation: A level set approach. IEEE Trans. PAMI 17, 158–174 (1995) [10] Vincent, L., Soille, P.: Watersheds in digital space: an efficient algorithm based on immersion simulations. IEEE Trans. PAMI 13, 583–598 (1991) [11] Bleau, A., Leon, L.J.: Watershed-base segmentation and region merging. Computer Vision and Image Understanding 77, 317–370 (2000)
74
X.U. Liu and M.S. Nixon
[12] Liu, X.U., Nixon, M.S.: Water Flow Based Complex Feature Extraction. In: Blanc-Talon, J., Philips, W., Popescu, D., Scheunders, P. (eds.) ACIVS 2006. LNCS, vol. 4179, pp. 833–845. Springer, Heidelberg (2006) [13] Liu, X.U., Nixon, M.S.: Water flow based vessel detection in retinal images. In: Proceedings of Int’l Conference on Visual Information Engineering, pp. 345–350 (2006) [14] Hurley, D.J., Nixon, M.S., Carter, J.N.: Force field feature extraction for ear biometrics. Computer Vision and Image Understanding 98, 491–512 (2005) [15] Evans, A.N., Liu, X.U.: A morphological gradient approach to color edge detection. IEEE trans. Image Processing 15(6), 1454–1463 (2006)
A Novel Hierarchical Technique for Range Segmentation of Large Building Exteriors Reyhaneh Hesami, Alireza Bab-Hadiashar, and Reza Hosseinnezhad Faculty of Engineering and Industrial Sciences Swinburne University of Technology, VIC 3127, Australia {rhesami,abab-hadiashar,rhosseinnezhad}@swin.edu.au
Abstract. Complex multiple structures, high uncertainty due to the existence of moving objects, and significant disparity in the size of features are the main issues associated with processing range data of outdoor scenes. The existing range segmentation techniques have been commonly developed for laboratory sized objects or simple architectural building features. In this paper, main problems related to the geometrical segmentation of large and significant buildings are studied. A robust and accurate range segmentation approach is also devised to extract very fine geometric details of building exteriors. It uses a hierarchical model-base range segmentation strategy and employs a high breakdown point robust estimator to deal with the existing discrepancies in size and sampling rates of various features of large outdoor objects. The proposed range segmentation algorithm facilitates automatic generation of fine 3D models of environment. The computational advantages and segmentation capabilities of the proposed method are shown using real range data of large building exteriors.
1 Introduction During the last decade, large scale 3D measurement technology has been significantly advanced. Accurate dense range data of outdoor objects, up to a few hundred meters in size, can now be produced in minutes. As a result, production of automated urban models of whole buildings is emerging as one of the viable applications of 3D data. In particular, capturing the fine architectural details embedded in the façade of important buildings has found new significance for developing realistic virtual reality tours of monuments, computer games, etc. The size and complexity of buildings, unavoidable existence of moving objects (as shown in Figure 1(a)), unpredictable change of environmental conditions and existence of sharp contrasts between the levels of details in different parts of large buildings (as shown in Figure 1(b)) pose significant challenges for the existing computer vision techniques. A number of approaches for the segmentation of dense range images of outdoor scenes have been developed during the last few years. A common approach, particularly for segmenting building exteriors, is to use architectural features. Attributes such as vanishing points [1], parallelism of walls and orthogonality of edges [2] are employed to extract linear features of buildings. Another common approach is to consider the 3D dataset as a collection of pre-defined classes of segments [3-6]. In this approach, a learning method is employed to find the various G. Bebis et al. (Eds.): ISVC 2007, Part II, LNCS 4842, pp. 75–85, 2007. © Springer-Verlag Berlin Heidelberg 2007
76
R. Hesami, A. Bab-Hadiashar, and R. Hosseinnezhad
instances of different classes of objects such as ground, vegetations, buildings, shrubs, etc. Although the above techniques are generally able to extract large segments of various buildings, they are not designed to detect fine details particularly seen on the façade of important buildings. Moreover, these techniques rely on the existence of distinguished features embedded in the scene which their availability is application dependent. In addition, due to the fact that they often employ edge detection or region growing techniques for segmentation, they require significant post-processing to overcome the occlusion problem. To our knowledge, automatic extraction of fine details of the buildings of interest from range data is yet to be addressed satisfactorily.
Large Segments
Small Segments
(a)
(b)
Fig. 1. a) Intensity and range images of the Royal Exhibition Building- Melbourne, Australia. Cars, passengers and vegetation are obstacles that couldn’t have been avoided at the time of data collection. Moving objects appear as straight lines in the range image. b) Large disparity in size of various features is highlighted (the Shrine of Remembrance – Melbourne, Australia).
Our main goal has been to develop a computationally feasible technique capable of extracting all possible geometric details embedded in 3D data of the exteriors of large building. The proposed range segmentation algorithm indeed facilitates automatic generation of fine 3D models of environment. To overcome the problems associated with measurement uncertainties and structural complexities of range data of outdoor scenes, we have developed a hierarchical (parametric) model-based robust range segmentation algorithm. The segmentation strategy has been adopted from the techniques presented by [7, 8] while a hierarchical approach, involving sequential usage of a robust estimator, is used to significantly reduce the computational cost and increase the level of accuracy in segmentation of fine details. In this paper, we first introduce and analyze the main characteristics of outdoor scenes (building exteriors, in particular) that complicate its geometric segmentation task. We then outline our new parametric robust hierarchical scheme that is specifically designed to address those problems. Our experiments with real data are presented in Sec. 4 where we demonstrate that this method is able to segment range data of building of significance, containing substantial disparities in size and noise.
2 Characteristics of Range Data of Building Exteriors The application domain of outdoor range segmentation is an open environment and there are many factors that significantly influence the measurement processes. In particular, there are several main issues that complicate the outdoor range data
A Novel Hierarchical Technique for Range Segmentation
77
segmentation task. In the following subsections, we explain those problems in detail and show ways by which they can be addressed. 2.1 Disparity in Size In range images of large structures, the difference between the shape and size of objects of interest can be significant. For example, as shown in Figure 1(b), when walls of a building may contain as many as 30% of all data points, surfaces associated with roof decoration may only contain 1% of all data. Since distant and small structures have a small number of data samples, a segmentation algorithm that relies on a minimum size for structures may not be able to extract all possible structures. To show the effect of disparity in size on the segmentation process, we have designed and conducted a simulation experiment as shown in Figure 2(a). The scene in this experiment represents 3D synthetic data containing two parallel planar structures. The large plane contains 1600 data points while the size of the small plane is varied from 16 to 1600 data points. Data of both structures are generated using square shape regular grids corrupted by additive Gaussian noise N (0, 0.1). Around 80 (representing 5% of whole population) uniformly distributed wrong measurements, imitating the effect of gross outliers, have also been added to the mix. A robust estimator (MSSE [7]) is then applied to segment this data. k=0.02
P (Percentage of Success)
Depth (meter)
k=0.03
100
60 40 20 0 6 4 2 0 Y (meter)
-2
-2
0
2 X (meter)
(a)
4
k=0.04 k=0.05
80
k=0.06 k=0.07
60
k=0.08 40
k=0.09 k=0.10
20
k=0.11
6
k=0.12 0
0
0.1 0.2 0.3 0.4 size of small structure/size of all data
0.5
(b)
Fig. 2. a) Sample of synthetic data used to demonstrate effect of disparity in size for large-scale range data segmentation. b) Plot of percentage of success in segmenting both small and large structures with a robust estimator versus the ratio of the size of small structure to the size of whole population for different values of K.
The proposed hierarchical robust segmentation technique is aimed to overcome this issue by performing segmentation at different scales and hence recovering small structures without the interference of the larger ones. The above experiment was repeated 100 times for every value of the K (the proportion of the size of the smallest data group that would be considered a structure – here, varied from 2% to 12% of the whole population) and the successes of the robust estimator in separating both planes were recorded as shown in Figure 2(b). This figure indicates that successful segmentation of all possible structures of interest greatly depends on the size of the embedded structure. Structures containing less than 20% of all data are less likely to be segmented as a separate structure.
78
R. Hesami, A. Bab-Hadiashar, and R. Hosseinnezhad
2.2 Existence of Very Fine Details Modern 3D laser scanners are able to capture high resolution dense geometric data points of building exteriors in a short period of time. As a result, outdoor range datasets are rich in detail. Moreover, many buildings, in addition to their main structure, contain different architectural details such as columns, statues and staircases. Generation of a simplified model of such a building is not unfeasible with existing techniques – for instance, see [9]. However, extraction of fine details of the ornamental buildings has remained a challenging task that can only be performed either manually [10] or by huge amount of computation. The cost associated with either of those methods increases rapidly with modest increases in the desired level of interest. In order to analyze this phenomenon, we consider the cost associated with RANSAC [12] type robust estimation approach. Most of the robust estimators use a search method such as random sampling to solve the problem of optimization. As shown by Fischler and Bolles [11] , if ε is the fraction of data points not belonging to the segment one tries to find by random sampling and P is the probability of having at least one “good sample” (a sample belonging to the segment of interest) in p-dimensional parameter space, minimum number of random samples required for having at least one good sample (which by itself is far from satisfying the sufficiency condition [12]) is calculated by: m=
log(1 − P ) log[1 − (1 − ε ) p ]
.
(1)
Number of required random samples
For instance, if the size of the smallest structure of interest in a multi-structure scenario is 1% (ε=0.99) of all data population, then more than 2 million random samples are required to find the structure of interest 90% of times. Figure 3 shows the rapid change in the number of required random samples when high level of details is desired. 4
x 10
4
P =0.99 P =0.95 P =0.90
3 2 1 0
0
0.05 0.1 0.15 0.2 0.25 0.3 0.35 Minim um relative s iz e of the s m alles t desired detail
0.4
Fig. 3. Plot representing the number of required random samples verses the minimum relative size of the smallest desired detail for different probabilities of success in 3D. The number of required samples enormously increases when the size of desired structure goes below 10%.
It is important to note that in practice, the outlier ratio ε is not known a priori and has to be assumed to be fairly large to guarantee that small structures aren’t overlooked. Therefore, for successful segmentation of small patches, ε values very close to one must be chosen which would result in prohibitive computation as exemplified above.
A Novel Hierarchical Technique for Range Segmentation
79
2.3 High Uncertainty Due to Construction Errors In our experiments with range data of building exteriors, we’ve found that segmentation of building exterior is highly affected by the construction accuracy of the modeled building. Construction errors in large buildings are generally unavoidable and their scales are significant compared to the accuracy of the 3D measurement systems (a few centimeters and a few millimeters, respectively). In particular, the effect of construction error becomes a significant issue when different parts of one structure are located apart. In such circumstances, and depending on the level of construction error, model-based range segmentation algorithms may no longer be able to detect coplanar surfaces as single structures. To investigate the effect of construction error on the segmentation process, we have performed a simulation experiment as shown in Figure 4(a). The scene represents three dimensional synthetic data containing coplanar surfaces of similar size; each contains a total of 500 data points (5 meter wide planes separated by 5 to 15 meters). Data of both planar surfaces are generated using rectangular (and regular) grids corrupted by additive Gaussian noise N (0, 0.1). The construction errors are then modeled by moving one surface parallel to the other in depth by different amounts (µ times the scale of noise). A number of randomly distributed gross outliers (around 30% of population, representing wrong measurements or miscellaneous building parts) have also been added to the set and a robust estimator (MSSE) is applied to segment this data. μ=0.5 μ=1 μ=1.5 μ=2 μ=2.5 μ=3
15
10
5 10 15 5
10
Y(meter)
5 0
0
(a)
X(meter)
P (Percentage of Success)
Depth of Structur in meter
110 100 90 80 70 60 50 40
0
10
20 30 40 m(Distance of Structures in meter)
50
60
(b)
Fig. 4. a) Sample of the simulation data used for segmentation analysis of distant co-planar surfaces b) Likelihood of detecting co-planar surfaces as one segment vs. distance of structures for cases where K=0.1
The above experiment was repeated 100 times for different values of µ (the construction error in depth) ranging from 0.5 to 3 times of measurement error (here, 10 mm). The number of times that the robust estimator has successfully labeled both patches as a single plane was recorded and is shown in Figure 4(b). The plot shows that successful segmentation of coplanar surfaces directly depends on the distance separating those coplanar structures and the amount of construction error. Coplanar structures separated by more than 2 times of their dimension are not likely to be segmented as coplanar and the situation worsens as the construction error increases.
80
R. Hesami, A. Bab-Hadiashar, and R. Hosseinnezhad
3 Hierarchical Robust Segmentation Scheme (HRS) As was mentioned previously, robust estimation is the tool we have chosen to address the aforementioned complexity and uncertainty issues associated with segmentation of range images. A suitable robust estimator needs to have breakdown points much higher than 50% offered by traditional robust estimators like M-estimators [13] and LMedS [14]. Overtime, a number of very high breakdown robust estimators have been specifically developed for computer vision applications (i.e. RANSAC [11], MSSE [7], PbM [15] and most recently HBM [16]) but those have only been used for applications involving laboratory-sized objects. To deal with the problems explained in Section 2.1 and 2.2, a single global approach is unlikely to be sufficient. Hierarchical Robust Segmentation (HRS) technique presented here is designed to overcome the issues associated with range segmentation of building exteriors. In this approach, a robust range segmentation strategy is applied at different stages, significantly reducing the overall computation requirements to a level achievable by ordinary computers (see Table 1 and 2 for a comparison). Moreover, we assume that most of the structural and decorative parts of large building exteriors are either planar (due to the ease of their constructions) or can be approximated by small planar patches. This allows us to use the highly effective model-based approach and take advantage of existing robust segmentation techniques [7]. However, for applications where nonlinear forms are of importance, our proposed hierarchical framework can be extended to include model selection strategies similar to those introduced in [8]. The proposed algorithm starts by specifying a user-defined input to the robust estimator (a threshold K, which is the size of the smallest region that can be regarded as a separate region). Without this constraint, the segmentation task becomes a philosophical question as every 3 points in the dataset can in theory represent a planar patch. We also assume that the scale of typical measurement error of the rangefinder is either readily available or can be measured from data. The outline of our proposed range data segmentation algorithm is as follows: Range data pre-processing – In this stage, first, those data points whose associated depths are not valid (due to the limitation of the laser rangefinder used for measuring the depth) are eliminated. These points are usually marked by the rangescanner with an out-of-range number. Data of outdoor man-made objects, captured by laser technology is contaminated by noise due to the “mixed-pixel” effect and moving objects. To reduce these effects, a median filter (here, 5 × 5) then is applied to the entire valid range data. Robust range segmentation - A robust segmentation algorithm is applied to the entire data. This algorithm is initially tuned to extract a preliminary collection of coarse/large segments. The remaining data are marked as outliers and stored for further processing. In this work we have chosen to use the Modified Selective Statistical Estimator (MSSE) [7], because it is straightforward and has the least finite sample bias in comparison with other popular robust estimators [17]. However, other highly robust estimators could also be used in this step and would be expected to produce similar results. This estimator is explained in Section 3.1.
A Novel Hierarchical Technique for Range Segmentation
81
Surface fit – We, then, fit a planar surface to the data of each coarse/large segment (of the previous stage) and calculate the scale of noise. Hierarchy criterion - If the calculated value of scale is more than scale of noise of the measurement unit, we consider this segment as coarse segment and once again, apply the robust segmentation algorithm. Otherwise, it will be labeled as a large segment. Where applicable, this step is repeated to extract all possible details embedded in the data. Outlier segmentation - Those data marked as outliers in the first segmentation stage are not discarded since the majority of such points may belong to some small structures. We again apply a finer robust segmentation algorithm to these data points. Smaller structures are normally detected at this stage. 3.1 Robust Estimation and Segmentation Using MSSE As was mentioned earlier, in our experiments, we have used the MSSE [7] to perform segmentation at every level. Although describing the full detail of this technique is outside the scope of this paper, we briefly outline how the method is implemented. MSSE uses random sampling to determine a number of candidate fits, ranks these candidate fits by least K-th order residuals and estimates the scale from the best preliminary fit. The algorithm classifies inliers and outliers by using scale estimation. The important steps of MSSE are as follows: A value of K is set (by the user) as the lower limit of the size of populations one is interested in. A localised data group inside the data space in which all the pixels appear on a flat plane is found using random sampling. A planar model with the least K-th order squared residuals is selected from the planar models fitted to those samples. For the accepted model, starting from n = K, the unbiased estimate of scale of noise is calculated using the smallest n residuals: 2
σn =
n 2 ∑ r j =1 j
.
(2)
n− p
where rj is the j-th smallest residual and p is the number of parameters in the model. Those points whose squared residual is greater than a threshold (T – specified based on the level of significance in the normal distribution) multiple of the scale of noise are rejected. The equivalent characterization of the point of transition from inlier to outlier occurs when: 2
σ n +1 2 σn
> 1+
T
2
−1
n − p +1
.
(3)
A new segment containing all the inliers to this fit regardless of their geometrical location is generated. As a result, the algorithm has the advantage of detecting and
82
R. Hesami, A. Bab-Hadiashar, and R. Hosseinnezhad
resolving occlusion while segmenting the data. The above tasks are iteratively performed until the number of remaining data points becomes less than the size of the smallest possible region in the considered application.
4 Experimental Results We have conducted a number of experiments to determine the functionality of the proposed algorithm and one is detailed here. The range data of this experiment is captured from the front view of a historical building called the Shrine of Remembrance (Melbourne, Australia) by a Riegl (LMS-Z210) laser rangescanner. The exterior of this building is highly structured with many large planar objects like walls, doors and roofs and smaller planar objects such as stairs. Part of the building also contains some small and decorative structures. The building is shown in Figure 5(a) (left). The scanned range image of the building is sampled on a 250× 382 grid and contains almost 105 data points. Angular resolution of the scanner was set to be 0.1 degree and its measurement error is typically 10mm. The proposed set of algorithms has all been implemented in MATLAB and the original range image and the results of the first and last stages of the segmentation strategy are shown in Figure 5(b) and (c). To highlight the high accuracy of the proposed segmentation algorithm, the decorative part of the front exterior and its segmentation outcome are magnified in Figure 5(d). The quality and the required computation of achieving the above outcomes are further elaborated here. 4.1 Quantitative Evaluation of Results To highlight the advantages of the proposed hierarchical strategy, we have compared the results of the direct and step-wise implementation of the robust range segmentation technique using a range image of a typical building. Table 1 and 2 summarizes the various outcomes of each approach for different values of K (the proportional size of the smallest data group that would be considered a structure). The results for the direct approach (Table 1) show that as the value of K is decreased to extract more details (finer structures), the required computational cost is significantly increased to levels that would be considered impractical for most vision applications. At the same time, the value of σ (estimated noise scale) for each segment also decreases pointing to the fact that the segmentation has become more accurate with the smaller values of K. The oversegmentation problem however worsens when K is fairly small. Table 2 shows the results of hierarchical approach to the robust range segmentation of the Shrine of Remembrance (see Figure 5) requiring a three level pyramid. At the first level, the algorithm has focused on the large/coarse segments (e.g. structures that contain at least 20% of the whole population) and has separated data into 4 parts. Stages two and three have further refined those parts into smaller/finer segments where a very accurate segmentation is achieved at its final stage. This table also shows that our hierarchical approach to the segmentation, drastically decreases the required time of computation (3 minutes verses 13 hours) and has taken the full advantage of the high accuracy that the MSSE can produce.
A Novel Hierarchical Technique for Range Segmentation
83
Table 1. Outcomes of direct implementation of the robust range segmentation algorithm for the Shrine of Remembrance with different values of K (size of the smallest structure)
K
No. of Samples
Segmentation Time (in seconds)
No. of Segments
0.3 0.2 0.1
84 286 2,301
28 36 150
2 3 8
0.08
4,496
0.05
18,419
0.02 0.01
287,821 2,302,583
Segmentation Quality
No fine details detected No fine detail detected No fine detail detected Moderate number of fine 398 10 details Moderate number of fine 1661 15 details 44822 (~13 hours) 29 Most details are detected Stopped due to the computational limitations
Table 2. Outcomes of hierarchical implementation of robust segmentation algorithm for the Shrine of Remembrance Hierarchy
K
First
0.2
Number and Quality of Generated Segments Segment I
Segment II
Segment III
Remainder (outliers)
σ >> 0.01 Segments I-1 and I-2 Second
0.15
Segment II-1 to Segment II-7
Segments III1 to III-7
σ < 0.01
σ < 0.01
σ > 0.01
Third
0.4
Segment I-1.1 to Segment I-1.4 σ < 0.01
Segments O-1 toO-9 σ<0.01 Segment O10 σ>0.01 Segments O-10.1 to O10.3 σ<0.01
Segmentation time = 191 (s)
5 Conclusion In this paper, we have studied the main issues associated with the geometrical segmentation of large buildings. A novel method is also proposed to efficiently partition range data of such objects into planar patches using a hierarchical segmentation approach. The algorithm extracts detailed planar patches of large and complex datasets with very modest computational cost. In a case study presented here, it has taken around 190 seconds to segment 28 planar patches embedded in the range data set of a decorative monument. The same task takes around 13 hours when a similar robust segmentation technique is applied directly to this dataset. Our experimental results also show that the outcomes of the proposed method are more accurate and less prone to the usual over or under segmentation issues.
84
R. Hesami, A. Bab-Hadiashar, and R. Hosseinnezhad
(a)
(b)
(c)
(d)
Fig. 5. a) Intensity (left) and range (right) image of the front side of the Shrine of Remembrance. b) Resulting segmentation of the first level of hierarchy c) Final result of hierarchical segmentation d) All possible detail (planar and decorative) of the head of the building is successfully segmented.
A Novel Hierarchical Technique for Range Segmentation
85
References [1] Stamos, I., Allen, P.: Geometry and Texture Recovery of Scenes of Large Scale. Computer Vision and Image Understanding (CVIU) 88(2), 94–118 (2002) [2] Cantzler, H., Fisher, R.B., Devy, M.: Improving Architectural 3D Reconstruction by Plane and Edge Constraining. In: (BMVC), Britain, pp. 43–52 (2002) [3] Zhao, H., Shibasaki, R.: A Vehicle-Borne Urban 3D Acquisition System using Single-row Laser Range Scanners. Systems, Man and Cybernetics, Part B 33(4), 658–666 (2003) [4] Anguelov, D., Taskarf, B., Chatalbashev, V., Koller, D., Gupta, D., Heitz, G., Ng, A.: Discriminative Learning of Markov Random Fields for Segmentation of 3D Scan Data. In: CVPR, CA, USA, pp. 169–176 (2005) [5] Triebel, R., Kersting, K., Burgard, W.: Robust 3D Scan Point Classification Using Associative Markov Networks. In: (ICRA), Florida, USA, pp. 2603–2608 (2006) [6] Lakaemper, R., Latecki, L.J.: Using Extended EM to Segment Planar Structures in 3D. In: (ICPR), Hong Kong, pp. 1077–1082 (2006) [7] Bab-Hadiashar, A., Suter, D.: Robust Segmentation of Visual Data Using Ranked Unbiased Scale Estimate. ROBOTICA 17, 649–660 (1999) [8] Bab-Hadiashar, A., Gheissari, N.: Range Image Segmentation Using Surface Selection Criterion. IEEE Trans. on Image Processing 15(7), 2006–2018 (2006) [9] Stamos, I., Yu, G., Wolberg, G., Zokai, S.: 3D Modelling Using Planar Segments and Mesh Elements. In: (3DPVT), University of North Carolina, pp. 599–606. Chapel Hill (2006) [10] Allen, P.K., Stamos, I., Troccoli, A., Smith, B., Leordeanu, M., Hsu, Y.C.: 3D Modeling of Historic Sites Using Range and Image Data. In: (ICRA), Taiwan, pp. 145–150 (2003) [11] Fischler, M.A., Bolles, R.C.: Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography. Communications of the ACM 24(6), 381–393 (1981) [12] Meer, P.: Robust Techniques for Computer Vision. In: Emerging Topics in Computer Vision, pp. 107–190. Prentice Hall, Englewood Cliffs (2004) [13] Huber, P.J.: Robust Statistics. Wiley, New York (1981) [14] Rousseeuw, P.J.: Least Median of Squares Regression. Journal of American Statistical Association 79, 871–880 (1984) [15] Chen, H., Meer, P.: Robust Regression with Projection Based M-Estimators. In: (ICCV), Nice, France, pp. 878–885 (2003) [16] Hoseinnezhad, R., Bab-Hadiashar, A.: A Novel High Breakdown M-estimator for Visual Data Segmentation. In: (ICCV), Rio de Janeiro, Brazil (October 2007) [17] Hoseinnezhad, R., Bab-Hadiashar, A., Suter, D.: Finite Sample Bias of Robust Scale Estimators in Computer Vision Problems. In: (ISVC), Nevada, USA, pp. 445–454 (November 2006)
Lip Contour Segmentation Using Kernel Methods and Level Sets A. Khan, W. Christmas, and J. Kittler Centre for Vision, Speech and Signal Processing University of Surrey Guildford, GU2 7XH, UK {a.khan,w.christmas,j.kittler}@surrey.ac.uk
Abstract. This paper proposes a novel method for segmenting lips from face images or video sequences. A non-linear learning method in the form of an SVM classifier is trained to recognise lip colour over a variety of faces. The pixel-level information that the trained classifier outputs is integrated effectively by minimising an energy functional using level set methods, which yields the lip contour(s). The method works over a wide variety of face types, and can elegantly deal with both the case where the subjects’ mouths are open and the mouth contour is prominent, and with the closed mouth case where the mouth contour is not visible.
1
Introduction
The ability to extract a person’s lips from an image or image sequence has some useful and interesting applications. Bi-modal speech recognition is one: according to [1], speech perception and understanding in humans is not just an auditory activity, but rather also employs visual information conveyed through the associated lip and mouth movement of the speaker. Even in machine-based speech understanding, visual cues extracted from lip shape can serve as a complementary source of information that can help bolster the speech recognition process when combined with the auditory information. The appearance of the lips also conveys valuable information about a person’s facial expression. Applications include expression/emotion recognition and character-driven animation. This paper proposes a novel method of segmenting/tracking lip shapes in images/videos of a person’s face. Lip extraction has generally been performed using some sort of flexible lip shape representation, such as deformable templates [2], active contours [3] or active shape models [4]. Generally, in a sequence consisting of a person speaking into the camera, it will be observed that the shape of the lips exhibits some dominant modes of variation. Therefore some of these methods try to impose a strong prior on the set of possible shapes that these contours or templates can take. This can be achieved , for instance, by using a parametric shape model with a limited degree of freedom that can model these variations with sufficient accuracy, or by learning the shape statistics and constraining shape deformations accordingly[5],[6]. G. Bebis et al. (Eds.): ISVC 2007, Part II, LNCS 4842, pp. 86–95, 2007. c Springer-Verlag Berlin Heidelberg 2007
Lip Contour Segmentation Using Kernel Methods and Level Sets
87
Another issue to be considered is how to model both the inner and outer lip contour, given that the mouth of a speaking person opens and closes, affecting the visibility and prominence of the inner lip boundary. Methods differ in whether they model only the outer boundary of the lip or both the inner and outer contours, or whether the lip model is switched depending on whether the mouth is ascertained to be open or closed[7]. In the method presented here, the level set method is used to represent the lip shape. Level sets provide an energy minimisation framework that has been used extensively to model shapes and object boundaries in the computer vision community. This method facilitates incorporation of region information at an image pixel level while still enforcing global notions such as boundary smoothness. An additional benefit of this method in this particular application, is that because of its unique behaviour with regard to topological properties of shapes, the problem of modelling both the inner and outer lip contour is elegantly solved. To drive the shape fitting process to the actual in-image lips, some sort of colour and/or gradient information (of the lip region and lip boundaries respectively) is used. When gradient-based features are used, the segmentation process needs to be supported by a strong shape model, as the contrast between the lip region and the skin often tends to be weak. When using colour information, the assumption is that in a face image the colour distribution of lips is sufficiently different from everything else (primarily skin, but also other facial features and hair). This assumption can be relaxed a bit (as in this paper) by assuming a non-negligible degree of overlap between the colour distributions of lip and skin. Methods that rely on learning to distinguish lip and non-lip regions make the implicit assumption that over a large set of face images, the differences between the lip and non-lip feature observations can be characterised over the different races or skin types. The rest of this paper is organised as follows: Section 2 gives a detailed description of the approach used in this work. Section 3 presents some visual results, and numerical characterisation of their quality. The paper is drawn to conclusion in section 4.
2
The Method
The primary task to be achieved is the segmentation of the lip shape in a face image. For shape segmentation, the level set approach is a popular variant of active contour methods among the computer vision community, and is the one used in this work. In one of its basic formulations, level sets facilitate the segmentation of an image or image sequence into two regions, separated by a boundary over which some smoothness constraint has been exerted, such that the homogeinity of some property in each region is maximised. The property used depends on the particular application, and may be one, or a combination, of various cues (such as intensity, texture, optical flow, etc.) but is basically a scalar function defined over the image domain. To define this function, the method presented in this paper takes a machine-learning approach; a support vector machine classifier,
88
A. Khan, W. Christmas, and J. Kittler
suitably trained over a set of colour-based features, defines at a pixel-by-pixel level some notion of the likelihood of the class label (whether lip or non-lip). This effectively allows the conversion of a multidimensional feature vector (based on RGB colour components) to a scalar quantity which represents a “soft” decision regarding whether a particular pixel looks like lip or non-lip. The level set method allows integrating this information at a more global level, by yielding an entire lip region, rather than a pixel-level classification. A practical overview of the method is as follows: a number of example face images with the lip region demarcated are used to generate a training set of feature vectors and class labels (lip, non-lip) and fed as training examples to a SVM (support vector machine) classifier. Once the classifier has been trained, a new instance of a face image for lip extraction can be presented to the system, and the SVM output is treated as a function over which an appropriate energy minimisation problem is defined. This problem is solved by means of gradient descent of the level set function. The solution of this problem generally yields the lip contour(s). The details of the method are given in the next section. 2.1
Choice of Classification Method
It is observed that in general it is not possible to linearly separate skin and lip colours when colour is represented in RGB. Several non-linear colour spaces (i.e. obtained as non-linear transformation of the RGB space) have been proposed that purport to give better results for distinguishing lip and skin pixels[8]. This problem becomes even more serious when considering the distribution of skin and lip colour over the range of races and skin types, and it may well be impossible to be able to distinguish adequately between these two classes by using any particular colour space. Given the non-linear nature of the classification problem, in this method we chose to employ a support vector machine-based classifier with a radial basis kernel. The first advantage of using SVMs is, for colour-based features, we can justifiably dispense with the task of having to find a new colour-space to represent the data, as the non-linearity built into the SVM classifier should be able to cope. Hence RGB can be retained as the colour space. Further it is possible to cope with variations of skin and lip colour, and its correlation with race or type of skin, by including the necessary features that bring out these characteristics. Another important characteristic of the SVM is that the classification process yields not a hard binary decision of which class a particular observation fall in, but rather a decision function that is a continuous function of the feature variables. This functional characteristic makes the SVM output usable by the next stage of the process, namely level set method-based evolution. This will be discussed in more detail later. The training set was composed of tightly cropped face images (although it is acceptable to have a fair bit of background, as long as the skin region dominates the image area) which were subjectively chosen to be representative of the majority of the images that would be used to test the system.
Lip Contour Segmentation Using Kernel Methods and Level Sets
89
A 6-dimensional feature vector was chosen for classification: three of its components were the R, G and B intensities of the pixel, and the other three were the medians of the individual R,G, and B components of the training image, and referred from here onwards as the “dominant colour” of the image. It is this dominant image colour that brings out the differences between the various types of faces. Although strictly speaking, colour elements cannot be ordered (because of their multidimensionality), however it is quite reasonable to think that colours that are perceptually near have small Euclidean distances between them in the RGB space, and hence taking the median of the individual colour components does in fact represent the representative colour of the face (i.e. skin colour). Simple tests performed on the images bear this out. Once the classifier has been trained, a test image is fed to the system, which outputs the value of the SVM decision function for each pixel of the image. The sign of the decision function denotes the class label assigned to it by the binary classifier, and in many SVM-based applications, that is all the information that is used. However, the absolute value of the decision function (which is a real number) is actually a measure of the confidence of the classification decision, i.e. a larger absolute value indicated a higher likelihood of the correctness of the classification. “Borderline” cases have values close to zero. The decision function map is going to be used in defining the lip segmentation energy functional. 2.2
The Energy Functional and Its Level Set Based-Minimisation
To extract and represent the lip shape, a level-set shape model[9] is used. Level sets provide an implicit representation of shape that is free of parametrisation (and the problems associated with it). For instance, they can handle the sharp discontinuities in the shape, such as at the corners of the mouth where the curvature of the lip shape is quite high. Also, because the level sets automatically handle shape and regions that are multiply connected or possess holes, in this particular problem they present an elegant means of dealing with multiple hypotheses (i.e. if there are other regions in the image that look like lip) as well as dealing with the appearance and disappearance of the inner lips contour as the speaker’s mouth opens and closes. Suppose the decision function returns a positive result for the lip class and a negative result for the non-lip class. In order to define an energy functional over the decision function map output by the SVM classifier, the following simple fact is used: in the decision function map, the lip region will contain a large proportion of positive valued numbers (ideally 100% - although if that were the case, the SVM-based classifier would be enough to extract the lip shape and any further steps would be unnecessary) whereas the non-lip pixels would consist of (again, mostly) negative values. What needs to be determined now is the boundary that separates these two regions. Let f be the decision function on Ω, a subset of R2 (corresponding to the image support). Suppose C represents this boundary, ins(C) and out(C) represent the
90
A. Khan, W. Christmas, and J. Kittler
(possibly multiply-connected) regions on either side of this boundary. Consider the following energy functional: 2
f (x) dx
E=−
−
ins(C)
2 f (x) dx
+ μ length(C)
(1)
out(C)
The first two terms depend upon the decision function map and the last term penalises the length of the boundary separating the two regions. If we momentarily ignore the contribution of the last term, the minimisation of the above function becomes trivial: C simply corresponds to the “boundary” separating the binary thresholded version of the decision function (with a threshold of zero). The all-important boundary length term imposes the requirement of smoothness on the solution, which is where the level set method comes in to play. This allows the lip boundaries to be smooth in shape and “whole” (i.e. even though they contain small regions where the pixels which have been wrongly classified as skin pixels.) To recast this energy minimisation problem into the level set framework, we introduce the level set surface function: φ(x) : R2 → R. The contour C is represented by the (1-dimensional) zero level set of this function: C = {x : φ(x) = 0} and the two inside and outside are represented as follows the following twodimensional sets: ins(C) = {x : φ(x) > 0} out(C) = {x : φ(x) < 0} We also introduce the Heaviside function defined as follows: 1, φ > 0 H(φ) = 0, φ ≤ 0
(2)
and this allows us to write the level set version of (1) as follows: E(φ) = − Ω
2 2 f H(φ) dx − f (1 − H(φ)) dx + μ δ (φ) |∇φ| dx (3) Ω
Ω
Here, δ (φ) is the distributional derivative of the Heaviside function. The last term is equal to the length of the set φ(x) = 0 and is a consequence of the co-area formula[10]. The level set evolution equation obtained for the gradient descent of (3) is given by ∂φ ∇φ = β f + μ div( ) |∇φ| (4) ∂t |∇φ| where β = Ω f (x) dx The discrete version of (4) over the image grid is solved using well-known methods for solving partial differential equations.
Lip Contour Segmentation Using Kernel Methods and Level Sets
3
91
Some Results
The method was tested on face images from XM2VTS database. The training set for the SVM classifier consisted of 8 images chosen from this database, and the performance of the method was tested on 122 images (not including the ones in the training set). Face Image
SVM decision function
Final lip segmentation
Fig. 1. SVM decision function map Final lip segmentation
Final lip segmentation
Fig. 2. Lip segmentation in open-mouth cases
The centre image in figure 1 provides a two-colour visual representation of the SVM-decision map; red indicates that the corresponding pixel has been classified as a lip pixel, while blue indicates non-lip classification. The intensity of the colour is proportional to the reliability of the classification; brighter colours represent pixels more likely to belong to their respectively assigned classes. From this representation it can be observed that even within the true lip region, there are sub-regions that the classifier is incorrect for, or uncertain about (for example, the dark region of the upper-left portion of the lip). However, since the level-set minimisation process (through the boundary-smoothness term) takes a broader, region-level look instead of focusing on individual pixel values, and the lip region has been correctly segmented.
92
A. Khan, W. Christmas, and J. Kittler
Fig. 3. Some examples of good results
As the results indicate, the classifier is able to distil sufficient information from the training process to allow it to capture the lip region over a wide variety of faces. From figure 2, the advantages of using level set techniques should also be apparent; the mouth contour has been located in the examples where the subjects have opened their mouth. The contours are also able to deal with the high curvature at the corners of the mouth. 3.1
Quantitative Measurement of the Results
To numerically define a notion of the quality of the results, a reasonable approach is to find a measure that matches the shape of the extracted region with respect to the ground-truth. This was done as follows: let G denote the lip region as demarcated in the ground-truth, and E the lip region extracted by the method, considered as sets inside the image region (which can be taken to be the “universal set”). If | · | denotes the region area, then the quality of the extracted shape when matched with the ground-truth shape has been defined as follows: q(E, G) =
|E ∩ G| |E ∪ G|
(5)
The measure q is simply a ratio between the overlapping area and the total area of the two shapes. q(·, ·) is symmetric with respect to its arguments, lies in the range [0, 1], where 1 represents a perfect match and 0 represents a total mismatch. The histogram indicate that the majority of results have a quality measure of greater than 0.65 and visually correspond to a “good” segmentation result. Results with values in the intermediate range contain results of reasonable quality towards the upper end of this range, while at the lower end lie images that were partially segmented, but the level-set evolution process got stuck somewhere in a local minimum. There are a small number of completely failed segmentations, and these have a quality measure of less than 0.1.
Lip Contour Segmentation Using Kernel Methods and Level Sets
93
Fig. 4. Histogram distribution of the image quality
3.2
Discussion
It may be noticed from the results that at times some portion of the face other than lips may also be captured. Since only colour features have been used, this is inevitable, as other parts of the face may have similar colouring to lips. However, due to the topological property of level sets, these regions tend to be disjoint of the true lip contours, and can be treated as cases where there are multiple hypotheses regarding the lip region. This is not necessary bad; it may in fact be advantageous if, for instance, the image/video had several faces, so the method would work without having prior knowledge of their number. It is also observed that whether or not the method discovers multiple lip-like regions is strongly dependent on the shape and position of the initial level set contour. Gradient descent energy minimisation gives local solutions which depend on the initial estimate of the object whose energy is being minimised. As might be expected, by initialising closer to the expected lip region, better results are obtained (the results are usually “better” in the sense that a smaller number of lip-like candidates are extracted). By employing another process that considers higher level
94
A. Khan, W. Christmas, and J. Kittler
information such as lip shape, position and size, the true lip contour can be chosen from the set of lip candidates. In a tracking application, it is expected that this would have to be done only once (if at all) after which the segmented lip boundary from every frame would serve as a good initial estimate for the next frame, and due to the local nature of the minimisation, lip-like regions away from the lip region would not be found again. With regard to the few instances of complete failures such as the leftmost image in figure 4, it may be attributed to the fact that the skin tone in these cases was quite different from any of the eight images used in the training set.
4
Conclusion
In this paper, we have presented a new method to segment lips in face images. This method employs learning to deal with difficulties in the separability of lip and skin colour. Contour-based segmentation using level set methods ensures that the lip will be segmented as a whole shape, and further deals elegantly with the problem of segmentation of the mouth contour. 4.1
Future Work
It would be interesting to adapt the method proposed in this work to track a speaker’s lips in a video sequence. Although the SVM classifier was found to be the bottle-neck in terms of speed of the method, this problem could be alleviated in the tracking scenario, by pre-computing the classifier’s decision function once over a range of feature vector values and then employing a look-up table to construct the decision function map for each frame. In an environment with controlled lighting conditions, this seems like quite a feasible thing to do, as the skin colour components would not be expected to vary much throughout the sequence (and the variation in the median features would be even less). Alternative methods to speed up the SVM include reducing its complexity by means of selectively reducing the training set, or by simplifying the decision function itself[11][12]. In the level set minimisation phase, the contour extracted at each frame would serve as an excellent approximation for the next frame, and convergence could be achieved within a few iterations. Another improvement that might be considered is the incorporation of shape prior information in the level set framework[13].
References 1. Mcgurck, H., Macdonald, J.W.: Hearing lips and seeing voices. Nature 264 (1976) 2. Hennecke, M., Prasad, K., Stork, D.: Using deformable templates to infer visual speech dynamics. In: 9th Asilomar Conference on Signals Systems and Computers, Pacific Grove, CA, pp. 578–582 (1994) 3. Kaucic, R., Blake, A.: Accurate, real-time, unadorned lip tracking. In: ICCV 1998: Proceedings of the Sixth International Conference on Computer Vision, p. 370. IEEE Computer Society, Washington, DC, USA (1998)
Lip Contour Segmentation Using Kernel Methods and Level Sets
95
4. Luettin, J., Thacker, N.A., Beet, S.W.: Visual speech recognition using active shape models and hidden markov models. In: IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 1996), vol. 2, pp. 817–820 (1996) 5. Lievin, M., Delmas, P., Coulon, P., Luthon, F., Fristot, V.: Automatic lip tracking: Bayesian segmentation and active contours in a cooperative scheme. In: ICMCS, vol. 1, pp. 691–696 (1999) 6. Bregler, C., Omohundro, S.M.: Nonlinear manifold learning for visual speech recognition. In: ICCV 1995: Proceedings of the Fifth International Conference on Computer Vision, p. 494. IEEE Computer Society, Washington, DC, USA (1995) 7. Tian, Y.-L., Kanade, T., Cohn, J.: Robust lip tracking by combining shape, color and motion. In: Proceedings of the 4th Asian Conference on Computer Vision (ACCV 2000) (2000) 8. Li´evin, M., Luthon, F.: Nonlinear color space and spatiotemporal mrf for hierarchical segmentation of face features in video. IEEE Transactions on Image Processing 13, 63–71 (2004) 9. Osher, S., Fedkiw, R.: Level set methods and dynamic implicit surfaces. Springer, Heidelberg (2003) 10. Morgan, F.: Geometric Measure Theory: A Beginner’s Guide, 3rd edn. Academic Press, London (2000) 11. Bakir, G.H., Bottou, L., Weston, J.: Breaking svm complexity with cross-training. In: NIPS (2004) 12. Burges, C.J.C.: Simplified support vector decision rules. In: International Conference on Machine Learning, pp. 71–77 (1996) 13. Chan, T., Zhu, W.: Level set based shape prior segmentation. In: CVPR 2005: Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2005), vol. 2, pp. 1164–1170. IEEE Computer Society, Washington, DC, USA (2005)
A Robust Two Level Classification Algorithm for Text Localization in Documents R. Kandan, Nirup Kumar Reddy, K.R. Arvind, and A.G. Ramakrishnan MILE Laboratory, Electrical Engineering Department, Indian Institute of Science, Bangalore 560 012, INDIA
[email protected],
[email protected],
[email protected],
[email protected]
Abstract. This paper describes a two level classification algorithm to discriminate the handwritten elements from the printed text in a printed document. The proposed technique is independent of size, slant, orientation, translation and other variations in handwritten text. At the first level of classification, we use two classifiers and present a comparison between the nearest neighbour classifier and Support Vector Machines(SVM) classifier to localize the handwritten text. The features that are extracted from the document are seven invariant central moments and based on these features, we classify the text as hand-written. At the second level, we use Delaunay triangulation to reclassify the misclassified elements. When Delaunay triangulation is imposed on the centroid points of the connected components, we extract features based on the triangles and reclassify the misclassified elements. We remove the noise components in the document as part of the pre-processing step.
1
Introduction
Most document images invariably consist of a mixture of machine printed elements such as logos, text, barcodes etc and handwritten elements such as address or name texts, signatures, markings etc. From established methods of machine-printed and handwritten character recognition it is understood that the methods are quite different from each other. Hence a necessary preprocessing step to an OCR is the separation of machine-printed and hand-written elements. Imade et al. [1] have described a method to segment a Japanese document into machine-printed Kanji and Kana, handwritten Kanji and Kana, photograph and printed image. They extracted the gradient and luminance histogram of the document image and used a feed forward neural network in their system. Kuhnke et al. [2] developed a method for the distinction between machine-printed and handwritten character images using directional and symmetrical features as the input of a neural network. Guo and Ma [3] have propose a scheme which combined the statistical variations in projection profiles with hidden Markov models (HMMs) to separate the handwritten material from the machine printed G. Bebis et al. (Eds.): ISVC 2007, Part II, LNCS 4842, pp. 96–105, 2007. c Springer-Verlag Berlin Heidelberg 2007
A Robust Two Level Classification Algorithm
97
text. Fan et al. [4] have proposed a scheme for classification of machine-printed and handwritten texts. They used spatial features and character block layout variance as the prime features in their approach. They have also claimed that this technique could be applied to English or Chinese document images. Pal and Chaudhuri [5] have used horizontal projection profiles for separating the printed and hand-written lines in Bangla script. In this paper we use a set of seven 2D invariant moments, that are insensitive to translation, scale, mirroring and rotation as the feature for distinguishing the printed and handwritten elements. Then we go on to use Delaunay triangulation to reassign the labels assigned to the elements. We find that the accuracy achieved is around 87.85% using the nearest neighbour classifier and with the SVM classifier the accuracy is 93.22%
2
System Description
The entire system is divided into three stages. The first stage is the preprocessing stage, in which the document is cleaned of all the noise components present such as spurious dots and lines. In the second stage we extract the features based on invariant moments for classification of the elements into printed or handwritten. This classification is done with the Nearest neighbor and SVM classifiers separately. Finally, in the third stage we use Delaunay Triangulation to reassign the class labels assigned to the elements. The flowchart of the entire system is as shown in Figure 1. Let us look at the three stages in detail.
Fig. 1. Flowchart showing the Algorithm for Text Localization
98
2.1
R. Kandan et al.
Preprocessing
In this stage we remove the noise elements such as dots and lines in the document image. This process is described below. – Apply Connected Component Analysis (CCA) – Obtain Bounding Boxes of the connected components. Then we find the area of each connected element Ai and also find the minimum area Amin , maximum area Amax in the entire document. – If one of the following conditions is met then it indicates noise in the document and it is removed. • If the value of; (Ai - Amin )/(Amax - Amin ) < T1 (a threshold value, for the test documents it is set at 0.002) • Aspect ratio is used to remove horizontal and vertical lines. • Also if the height or width of the connected component is lesser than a threshold value, then it is a spurious element or a dot, and we remove it. The thresholds which are used have been chosen empirically. 2.2
Feature Extraction
We use the features drawn by invariants moment technique which is used to evaluate seven distributed parameters of an image element. The invariant moments (IMs) are well known to be invariant under translation, scaling, rotation and reflection [6,7]. They are measures of the pixel distribution around the centre of gravity of the character and allow to capture the global character shape information. In the present work, the moment invariants are evaluated using central moments of the image function f(x,y) up to third order. Discrete representation of the central moments is; (x − x ¯)p (y − y¯)q f (x, y) (1) μpq = x
y
where for p,q = 0,1,2,... and x and y are moments evaluated from the geometrical moments of Mpq as follows M10 M01 M00 and y¯ = / M00 (x)p (y)q f (x, y) Mpq =
x¯ =
x
(2) (3)
y
The central mmoments μ00 , μ10 , μ01 , μ11 , μ20 , μ02 , μ30 , μ03 , μ21 , μ12 of order upto 3 are calculated. A further normalization for variations in scale is implemented using the formula’ ηpq =
μpq μ00
From the central moments, the following values are calculated;
(4)
A Robust Two Level Classification Algorithm
99
φ1 = η20 + η02 2 φ2 = (η20 + η02 )2 + 4η02
φ3 = (η30 + 3η12 )2 + (3η21 − η03 )2 φ4 = (η30 + η12 )2 + (η21 − η03 )2 φ5 = (η30 + 3η12 )2 (η30 − η12 )(η30 − 3η12 )2 − 3(η21 − η03 )2 + (3η21 − η03 )(η21 + η03 )[(3(η30 − η12 )2 − (η21 − η03 )2 φ6 = (η20 − η02 )(η30 + η12 )2 − (η21 + η03 )2 + η11 (η30 − η12 ) φ7 = (3η21 − η02 )(η30 + η12 )(η30 − η12 )2 − 3(η21 − η03 )2 + (3η12 − η30 )(η21 + η03 )[(3(η30 − η12 )2 − (η21 − η03 )2
(a) Input Document
(b) Image after Handwritten elements are classified using NN classifier Fig. 2.
where φ7 is a skew invariant to distinguish mirror images. In the above, φ1 and φ2 are second order moments and φ3 through φ7 are third order moments. φ1 (the sum of the second order moments) may be thought of as the spread of the pattern; whereas φ2 may be interpreted as the ”slenderness” of the pattern. The third order moments, φ3 through φ7 do not have any direct physical meaning but includes the spatial frequencies and ranges of the image element.
100
2.3
R. Kandan et al.
Classification
The following classifiers are used to localisze the handwritten text regions; i) Nearest Neighbour Classifier ii) Support Vector Machines. The feature vector is considered to be a point in the feature space and the training data is a distribution of points in the feature space. Now for the test block, we extract the feature vectors and then the Eculidean distances are calculated from each of the points of the training data. Using the Nearest neighbour classifier principle we assign the class label of the training vector which has the minimum distance from the test vector, to the test block. Figure 2(a) and 2(b) depict the input image from which the handwritten elements are to be separated and the output after classification using the nearest neighbour classifier. In Figure 2(b), all those elements that have a class value of two, which represent handwritten text are marked by a magenta Bounding Box. We trained an SVM classifier with Radial Basis Function(RBF) kernel[8] with the invariant moments as the features. Then SVM finds a linear separating hyperplane with the maximal margin in this higher dimensional space. C > 0 is the penalty parameter of the error term. The RBF kernel used is given below K(xi ; xj ) = exp(−γ(||xi − xj ||)2 , γ > 0
(5)
The kernel parameters were chosen by using a five fold cross validation using all the training data samples. The best parameters were found to be C= 256 and γ = 0.0625 which was operating at an efficiency of 96%. With a lower computation cost i.e, by reducing the value of C=32 we achieve an efficiency of 95% when cross validation is done as shown in Figure 3. Figure 4 depict the image in which the handwritten elements are separated using SVM’s. 2.4
Reclassification
We now use Delaunay triangulation[9] for reclassification of the elements which are misclassified. We briefly give the definition of Delaunay triangulation. Delaunay triangulation of a set of non-degenerate vertices V is defined as the unique triangulation with empty circles, i.e, no vertex lies inside the circumscribing circle of any Delaunay triangles, as follows: DT (V ) = (pi .pj , pk )V 3 , B(pi .pj , pk ) ∩ V \ (pi .pj , pk )φ
(6)
where B(pi ; pj ; pk ) is the circle circumscribed by the three vertices pi ; pj ; pk that form a Delaunay triangle. The Delaunay triangulation carried out on printed text/handwritten text regions have the following features: – The lengths of the sides of most triangles in a printed text region are similar as compared to the lengths of the handwritten text.
A Robust Two Level Classification Algorithm
101
– Triangles in the printed text have their longest and similar sides link the point pairs between two adjacent text lines above which is also printed text. – The height of the triangles in the printed text region are uniform. The above features are extracted after applying the Delaunay triangulation and a threshold value based on comparing with the neighbouring points is set to reclassify the text as machine printed or handwritten text. If a particular element and its neighbouring elements have similar features and the element in consideration is labelled differently then it is assigned the label of the neighbours. We carry out the reclassification as per the following algorithm: – First the Delaunay triangulation is done on the document for the centroid points as shown in Figure 5(a) in which NN classifier is used and 5(b), in which SVM is used as the classifier. – Now, let us consider a centroid point P(x,y). A number of triangles originate from P. Thus P is associated with other centroid points P1 , P2 and Pn by the Delaunay triangles. All such points P1 , P2 and Pn which are connected to the point P are said to be the neighboring points of P. – After we get these neighboring points we compare the label of each point with the label of the centroid point P(x,y). If the label is not the same then we find the degree of similarity of the triangles; i.e in this case the difference between the heights of the element defined by the neighboring centroid points and the height of the element defined by the reference point P(x,y). If the difference is less than 7 pixels then we increment a count indicating the similarity in height. – If more than 50% of the neighbouring points have similar height i.e, the diference in height is less than 7 pixels then we reassign the label i.e 1 as 2 or 2 as 1. Let us assume count as Ci and the total no of neighbouring points Ci as Ni for the centroid point i then if the value of N ∗ 100 > 50 - the label i is reassigned else the label remains the same. This is then done for all the centroid points. – This means that if the centroid point P, has different text as compared to the neighboring points, then the height difference will be greater than 7 pixels. However if the centroid point P, has similar text as compared to the neighboring points and is misclassified we compare the height feature of the triangles and compute the difference in height. If the feature is same(i.e if the difference in height is less than 7 pixels), with more than 50% of the neighboring points then the point P(x,y) is given the label of the neighboring points and is re-classified. If the point P has the same label as that of its neighbors then the above steps are not required and the above algorithm is done for the next point. Figure 6(a) and 6(b) shows the image of the document with the handwritten elements localized within a magenta colored bounding box after the labels are reclassified.
102
R. Kandan et al.
Fig. 3. Graph showing the cross-validation results where γ is varied between 1 to 2−10 , C is varied between 1 to 2+10 and the best pairs of (γ, C) are choosen
Fig. 4. Image after the Handwritten elements are classified using SVM
A Robust Two Level Classification Algorithm
103
(a) Image after the NN classification show- (b) Image after the SVM classification ing Delaunay triangulation’s plot showing Delaunay trangulation’s plot Fig. 5.
3 3.1
Experimental Results Data Description
The training data are extracted from over 500 documents which contain predominantly machine printed elements. The handwritten elements are composed of text that is both cursive and block handwriting besides signatures, dates and address locations. Our test data consists of 150 English document images, scanned at 200 dpi and stored in 1-bit depth monochrome format. These documents contain handwritten elements, signatures, logos and other such things along with free-flowing text paragraphs. 3.2
Accuracy Calculation
Table (1) shows the classification accuracy using the proposed method. Using the nearest neighbour classifier we find that the number of printed text elements which are misclassified is higher which reduces the overall accuracy after the second stage of classification. The SVM classifier shows better accuracy and also the misclassified elements are few in number. There were a total of 1,67