Image categorization: Graph edit distance+edge direction histogram |
| |
| Authors: | Xinbo Gao Bing Xiao Dacheng Tao Xuelong Li |
| |
| Affiliation: | 1. School of Electronic Engineering, Xidian University, Xi’an 710071, PR China;2. Biometrics Research Centre, Department of Computing, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong, PR China;3. School of Computer Science and Information Systems, Birkbeck College, University of London, London WC1E 7HX, UK;1. State Key Laboratory of Software Engineering, School of Computer, Wuhan University, China;2. College of Automation, Nanjing University of Posts and Telecommunications, China;1. Department of Biochemistry, Dr. B.C. Roy Post Graduate Institute of Basic Medical Education and Research (IPGME&R), 244B, AJC Bose Road, Kolkata 700020, India;2. Department of Endocrinology & Metabolism, IPGMER & SSKM Hospital, 244, AJC Bose Road, Kolkata 700020, India;3. Department of Pathology, Midnapore Medical College, Paschim Midnapore, India;4. Regional Institute of Ophthalmology, 88, College Street, Kolkata 700088, India;1. University of Liège, Allée de la découverte 10, 4000 Liège, Belgium;2. University College Dublin, Belfield, Dublin 4, Ireland;3. University of Perpignan, Via Domitia, 52 Av. Paul Alduy, 66100 Perpignan, France |
| |
| Abstract: | This paper presents a novel algorithm for computing graph edit distance (GED) in image categorization. This algorithm is purely structural, i.e., it needs only connectivity structure of the graph and does not draw on node or edge attributes. There are two major contributions: (1) Introducing edge direction histogram (EDH) to characterize shape features of images. It is shown that GED can be employed as distance of EDHs. This algorithm is completely independent on cost function which is difficult to be defined exactly. (2) Computing distance of EDHs with earth mover distance (EMD) which takes neighborhood bins into account so as to compute distance of EDHs correctly. A set of experiments demonstrate that the newly presented algorithm is available for classifying and clustering images and is immune to the planar rotation of images. Compared with GED from spectral seriation, our algorithm can capture the structure change of graphs better and consume 12.79% time used by the former one. The average classification rate is 5% and average clustering rate is 25% higher than the spectral seriation method. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
