Heo Gyeong Yong, Jang Kyung Sik, Jang Moon IK, Kim Jai Hie

The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 5, No. 8, pp. 2061-2074, Aug. 1998
10.3745/KIPSTE.1998.5.8.2061,   PDF Download:

Abstract

In pattern recognition and image analysis applications, a graph is a useful tool for complex object representation and recognition. However it takes much time to pair proper nodes between the prototype graph and an input data graph. Futhermore it is difficult to decide whether the two graphs in a class are the same because real images are degraded in general by noise and other distortions. In this paper we propose a matching algorithm using a matrix. The matrix is suitable for simple and easily understood representation and enables the ordering and matching process to be convenient due to its predefined matrix manipulation. The nodes which constitute a graph are ordered in the matrix by their geometrical positions and this makes it possible to save much comparison time for finding proper node pairs. For the classification, we defined a distance measure that reflects the symbol's structural aspect that is the sum of the node distance and the relation distance; the former is from the parameters describing the node shapes, the latter from the relations with other node in the matrix. We also introduced a subdivision operation to compensate node merging which is mainly due to the preprocessing error. The proposed method is applied to the recognition of musical symbols and the result is given. The result shows that almost all, except heavily degraded symbols are recognized, and the recognition rate is approximately 95 percent.

Statistics
Cite this article