Object recognition algorithm based on inexact graph matching and its application in a color vision system for recognition of electronic components on PCBs
Natalia H. Kroupnova, Maarten J. Korsten · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1997
The paper describes a framework for fast objects recognition and its application in a system for recognition of certain electronic components on printed circuit boards (PCB) for recycling purposes. Objects in the DB and in the image are represented as attributed graph, where vertices are regions with attributes (color, shape) and edges are spatial relations between the regions (adjacent, surrounds). The task of finding model objects in the input data thus becomes a problem of inexact subgraph isomorphism finding. The suggested algorithm finds all the occurrences of all model graphs in the input graph in the presence of the low-level processing errors and model uncertainty. Using the ideas of inexact network algorithm (INA) we build a network from the model graphs, so that in cases when the models share identical substructures these substructures have to be matched only once. Because different models share the same substructures mostly in case when they belong to the same more general class, we incorporate the possibility of attribute refining in our model network. To further speed up the matching, we introduce the notion of a `key' vertex, so that recognition goes from easily recognizable substructures to more ambiguous ones. The algorithm was applied to real images of PCB's. The results show the effectiveness of INA and suggested modifications in this application.