A novel isomorphism based on nearest neighbours for efficient graph matching algorithm
A novel isomorphism based on nearest neighbours for efficient graph matching algorithm
复制标题
DOI：
10.1109/icarcv.2002.1238511
复制
发表时间：
2002-12
期刊：
影响因子：
--
通讯作者：
D. Piriyakumar;P. Levi
中科院分区：
文献类型：
--
作者：
D. Piriyakumar;P. Levi
对于机器人、卫星图像和医学成像等需要实时解决方案的领域中的许多应用，识别给定图像中的关键部分或结构继续吸引更多的关注。因此，在这些计算机视觉相关领域中，最重要的因素是匹配图像中的对象。图形通常用来表示对象。众所周知，图匹配一般是NT-完全问题。为了满足实时解的需要，针对特定的条件提出了各种低阶复杂度的算法。在这里，引入了一种新颖的节点邻居同构（NNI），它可以在O（n/sup 4/）中有效地匹配两个图，其中n是两个图中可以加权和属性的顶点数。使用NNI，图的顶点被互斥地分组。而不是匹配所有的顶点，只有相关的NNI顶点单独匹配铺平道路，充分的效率，减少匹配操作的数量。该算法在Sun Ultra 10上实现，并给出了关键算例和随机图的结果。该算法的运行时性能和新颖性证明了算法的高效性，同时也表现出并行性。该算法与标准方法相比，需要最少的时间匹配的图形。
For many applications in the fields of robotics, satellite imagery and medical imaging demanding real-time solutions, recognizing the crucial parts or structures in the given images continues to attract more attention. Tims, the paramount factor in these computer vision related fields is matching the objects in the images. Often graphs are used to represent the objects. It is well-known that graph matching is NT-complete problem in general. To accomplish the need of real-time solutions, various lower order complexity algorithms are developed with specific conditions. Here, a novel Node Neighbour Isomorphism (NNI) is introduced which efficiently matches two graphs in O(n/sup 4/) where n is the number of vertices in both the graphs which can be weighted and attributed. Using tliis NNI, the vertices of the graphs are grouped mutually exclusively. Instead of matching all the vertices, only the relevant NNI vertices alone are matched paving way for ample efficiency by reducing the number of matching operations. The algorithm is implemented on Sun Ultra 10 and results of crucial examples and random graphs are also tabled. The run-time performance and novality of the algorithm exemplifies the efficiency of the algorithm which also exhibits parallelism. The algorithm is compared with standard methods and requires the minimal time for matching the graphs.