200-vertex on-chip clique-finding VLSI processor for real-time 3-D object recognition

A novel on-chip clique-finding VLSI processor for high-speed graph matching is presented. It is utilized in applications to real-time complex vision systems such as 3-D object recognition. An efficient algorithm based on a branch-and-bound method is modified to perform high-speed clique finding, so that clique finding can be executed in parallel. Two kinds of VLSI arrays in the processor perform parallel search operations in a digital-level pipelining. Each digit cell in the VLSI arrays can be implemented using floating-gate MOS transistors. The proposed VLSI arrays are very useful for finding the cliques between two large-scale graphs. It is demonstrated that clique-finding with the proposed processor can be achieved 500 times faster than with the software system with a 28.5 MIPS SPARC station