Image analysis – Pattern recognition – Feature extraction
Reexamination Certificate
1998-10-27
2002-07-23
Au, Amelia M. (Department: 2623)
Image analysis
Pattern recognition
Feature extraction
C382S203000, C382S224000
Reexamination Certificate
active
06424746
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to classification and search of figures, and, in particular, to a classification and a search using structural features of contours of figures.
2. Description of the Related Art
Because a contour includes all the information of a figure or an object, various methods for classifying (recognizing) of closed contour using models have been devised. In an ordinary algorithm, for a particular model, a mutually independent data-structure model is considered. However, when the number of models increases, efficiency of recognition decreases. Therefore, a method of ‘structural indexing’ has been considered.
A basic concept of this structural indexing is as follows: For a set of models, one large-scale data structure (table) is prepared; discrete features (structural features) obtained from model figures are used as indexes; and the models are dispersed and disposed in the large-scale data structure. Then, when an input figure is recognized (classified), the features obtained from the input figure are compared with the table. Then, by voting on respective models, models having features the same as those of the input figure are obtained as a result of a narrowing-down operation. As an example of such a data structure, there is a large-scale table in which indexes are calculated from features, and entries of the table corresponding to the thus-obtained indexes are lists of identifiers of models having the features.
In such a structural indexing, for a complex figure, the first candidate obtained from a simple voting is not necessarily a correct answer. When a complex figure is recognized, a small number (several percent to ten percent of the total number of models) of candidate models are obtained as a result of the narrowing-down operation. Then, another complicated algorithm should be applied to the candidate models. Accordingly, conditions required for the structural indexing are that a correct model be surely included in the candidate models obtained from the narrowing-down operation as a result of voting, and that the time required for this process be so short as to be ignored in comparison to the time required for the complicated algorithm which is performed on the narrowed-down candidate models, that is, the speed of this process should be very high. When these two conditions are fulfilled, it is possible to increase the speed of the figure recognition, without degrading recognition accuracy, to several ten times the speed of the conventional figure recognition, through the structural indexing. These two conditions are essential conditions which determine performance and efficiency of figure search using a large-scale figure database.
Such a problem has been considered in earnest recently because capacities of a disk and a memory of a computer are increasing. For example, Baird considered an application to printed character recognition, and devised a method in which one bit is assigned to each feature obtained from a particular model (character figure), and, thereby, a figure is represented by a series of bits as to whether or not the figure has the features (Henry S. Baird, “Feature Identification for Hybrid Structural/Statistical Pattern Classification,” Computer Vision, Graphics, and Image Processing, vol. 42, pages 318-333, 1988). This method can be applied when a large amount of training data is present for each character. Structural features such as an arc, a stroke, a crossing, a hole, and an end point are expressed by parameters for each type, clustering is performed on the parameter space, and one bit is assigned to one cluster. When an input figure has a feature corresponding to a cluster, “1” is set for the bit of the cluster. The input figure is classified as a result of classification of thus-formed large-scale dimensions of a bit vector.
However, when only one sample figure can be used for one model figure, this method of Baird cannot be applied. A weak point of the method using structural features is that the features change due to noise or deformation. In the method of Baird, a large number of sample patterns are prepared for one model, and, through statistical and inductive learning using the data, various changes in features which can actually occur are dealt with.
In order to deal with a case where one sample figure can be used for one model, Stein and Medioni devised a method in which a figure contour is approximated by a polygon with various permissible errors, and, then, from a thus-obtained plurality of figures, structural features of the figure are extracted (F. Stein and G. Medioni, “Structural Indexing: Efficient 2-D Object Recognition,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 14, no. 12, pages 1198-1204, 1992). Further, Del Bimbo and P. Pala devised a method in which a scale space method in which a curve is smoothed through Gaussian functions having various extents and features of concavity/convexity are extracted, and the structural indexing is integrated (A. Del Bimbo and P. Pala, “Image Indexing using Shape-based Visual Features,” Proceedings of 13th International Conference on Pattern Recognition, Vienna, Austria, August 1996, vol. C, pages 351-355). In such methods, based on a description of a structural feature obtained from each scale, a hierarchical data structure is formed considering noise and a local deformation of a contour. However, in the scale space method, a contour is smoothed through Gaussian functions having various extents. As a result, an amount of calculation increases, and, also, a process of finding correspondence of features between adjacent different scales should be performed.
In such a situation in which only one sample can be used for one model, an efficient and effective method for structural indexing which is robust for noise and/or local deformation which changes structural features has not been devised.
Further, various methods for matching (determining correspondence) between two closed contours and classification (recognition) have been devised. However, an actual input figure includes noise and/or global/local deformation. Therefore, when designing algorithm of matching, prerequisites as to what deformation and conversion can be permitted and also how much deformation and conversion can be permitted should be determined. A method in which a change in size cannot be permitted and a method in which rotation cannot be permitted were devised. Further, there are many methods in which only a ‘rigid body’ which neither expands nor shrinks is considered.
Especially, when affine transformation is considered as a general transformation, it is known that Fourier features and moment features are features which do not change through affine transformation. However, when a shape is classified using these features, high-degree coefficients (the coefficients in Fourier series expansion or the degree number of the moment) are needed. As a result, a large amount of calculation is needed. Further, these high-degree coefficients are sensitive to noise, and only low-degree coefficients are stable. Further, in the methods using these features, a figure is classified merely using coefficient parameters. Therefore, specific point correspondence between figures and transformation parameters cannot be obtained.
In order to eliminate the above-mentioned problems, a method was devised in which a figure is described by a series of features on the contour, and optimum correspondence between two contour feature series is considered. A typical example thereof is a method in which a figure is expressed by concavity/convexity features of the contour. This method has been applied to figure recognition including character recognition. A concavity/convexity structure depends on noise, and, also, a scale, in which a figure is observed. As a result, such a method is called a scale space method. A method was devised in which a closed contour is smoothed through Gaussian functions having various sizes of supports, and a point of inflection which is a
Au Amelia M.
Dastouri Mehrdad
Dickstein , Shapiro, Morin & Oshinsky, LLP
Ricoh & Company, Ltd.
LandOfFree
FIGURE CLASSIFYING METHOD, FIGURE CLASSIFYING SYSTEM,... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with FIGURE CLASSIFYING METHOD, FIGURE CLASSIFYING SYSTEM,..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and FIGURE CLASSIFYING METHOD, FIGURE CLASSIFYING SYSTEM,... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2890346