This work presents a method for object recognition in digital images based on Graph Theory. We aim at establishing if a given object is present in an image. To do this, we describe the object and the image by a labeled topological graph. The search of the object in the image is done testing the existence of a subgraph isomorphism between the topological graph associated to the object and the topological graph associated to the image. Our method to detect labeled subgraph isomorphisms is based on an analysis of the breadth first search trees and on the construction of an isomorphism by an extension procedure. The method has been applied to the object retrieval in digital images; each object and image region represented by the vertices of the topological graph is described by a feature vector; the similarity between two regions is measured calculating the L1-distance between the corresponding feature vectors; the L1 - norm is used also to define a cost for each isomorphism; by a thresholding strategy based on the distance analysis only the isomorphisms of interest can be selected
Object Retrieval in Digital Images Using Subgraph Isomorphism
Lecca, Michela
2003-01-01
Abstract
This work presents a method for object recognition in digital images based on Graph Theory. We aim at establishing if a given object is present in an image. To do this, we describe the object and the image by a labeled topological graph. The search of the object in the image is done testing the existence of a subgraph isomorphism between the topological graph associated to the object and the topological graph associated to the image. Our method to detect labeled subgraph isomorphisms is based on an analysis of the breadth first search trees and on the construction of an isomorphism by an extension procedure. The method has been applied to the object retrieval in digital images; each object and image region represented by the vertices of the topological graph is described by a feature vector; the similarity between two regions is measured calculating the L1-distance between the corresponding feature vectors; the L1 - norm is used also to define a cost for each isomorphism; by a thresholding strategy based on the distance analysis only the isomorphisms of interest can be selectedI documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
