Image analysis – Image segmentation
Reexamination Certificate
1998-07-09
2003-05-06
Au, Amelia M. (Department: 2623)
Image analysis
Image segmentation
C382S195000, C382S227000
Reexamination Certificate
active
06560359
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a data processing method and apparatus for generating a classification tree utilized to recognize a pattern such as an image, character, audio or the like.
As disclosed in reference “Classification and Regression Trees” by Breiman, Friedman, Olshen and Stone, it is a known method to classify a pattern by using a so-called classification tree. The method has advantages in that the recognition speed is relatively fast and that the method is applicable to recognizing any types of patterns. Therefore, the method is widely used for pattern recognition of an image, character, audio or the like.
However, the method also has a disadvantage in that generation of a classification tree, used for classifying a pattern, is time consuming. Particularly, if the number of dimensions of a characteristic value space representing the pattern is large, an extremely large amount of time is required to generate a classification tree.
For instance, for each node of the classification tree, a certain dimension of a characteristic value space is looked at, and determination is made as to whether or not the coordinate in the object dimension of the input pattern is larger/smaller than a predetermined value. The “predetermined value” used herein is normally called a “threshold value.” In other words, when generating a classification tree, decision cannot be made for each node unless it is determined “which dimension of the n dimensions should be looked at?” and “where in the coordinate axis of the object dimension the threshold value is set?” More specifically, with respect to each of all dimensions (n dimensions), a threshold value that achieves highest classification efficiency is obtained (the total number of the obtained threshold values is n), and a dimension and a threshold value that can attain the highest classification efficiency among all the dimensions are obtained. In this manner, each node of the classification tree is generated.
SUMMARY OF THE INVENTION
The present invention is made in consideration of the above situation, and has as its object to provide a data processing method and apparatus which enables to generate, at high speed, a classification tree for classifying a pattern having a characteristic value expressed in a plurality of dimensions.
Another object of the present invention is to provide a data processing method and apparatus which can generate a classification tree that realizes a high recognition success rate even if the number of learning patterns provided is small.
To attain the above objects, the present invention provides a data processing method for generating a classification tree for classifying a pattern, comprising: a step of hierarchically segmenting a coordinate axis of a characteristic value space, and generating a plurality of coordinate-axis segments and threshold values corresponding to these segments; a step of generating hierarchy information indicative of coordinate-axis segments to which a characteristic value of each of a plurality of learning patterns belongs; and a step of selecting a dimension of the characteristic value space and a threshold value as a classification condition of each node of the classification tree, based on a distribution of the plurality of learning patterns in the hierarchy information.
Furthermore, in order to attain the above objects, the present invention provides a data processing method for generating a classification tree for classifying a pattern, comprising: a step of hierarchically segmenting a coordinate axis of a characteristic value space, and generating a plurality of coordinate-axis segments and threshold values corresponding to these segments; a step of deriving learning sub-patterns from each of a plurality of learning patterns, each of which is represented by combinations of dimensions of a characteristic value space; a first generating step of generating, for each of the combinations of dimensions, hierarchy information indicative of coordinate-axis segments to which a characteristic value of each of a plurality of learning sub-patterns belongs; and a second generating step of generating a classification tree for each of the combination of dimensions, by selecting a dimension of the characteristic value space and a threshold value as a classification condition of each node of the classification tree, based on a distribution of the plurality of learning patterns in the corresponding hierarchy information.
Moreover, according to another embodiment of the present invention, a data processing apparatus which realizes the aforementioned data processing method can be provided. Furthermore, according to another embodiment of the present invention, a memory medium storing control programs for causing a computer to execute the aforementioned data processing method, can be provided.
Other features and advantages of the present invention will be apparent from the following description taken in conjunction with the accompanying drawings, in which like reference characters designate the same or similar parts throughout the figures thereof.
REFERENCES:
patent: 4685142 (1987-08-01), Ooi et al.
patent: 5325445 (1994-06-01), Herbert
patent: 5634087 (1997-05-01), Mammone et al.
patent: 5787194 (1998-07-01), Yair
patent: 5982933 (1999-11-01), Yoshii et al.
patent: 6233352 (2001-05-01), Yoshii
H. Yoshii, “Binary PACT”; IEEE Proceedings on Pattern Recognition, ISBN: 0-8186-7282-X, vol. 3, pp. 606-610, Aug. 1996.*
Nadler et al, “Pattern Recognition Engineering”; ISBN: 0-471-62293-1, pp. 340-345, and 417-418, Jun. 1992.*
C. L. Nehaniv, “Algebraic Engineering of Understanding: Global Hierarchical Coordinates on Computation for the Manipulation of Data, Knowledge, and Process”; IEEE Proceedings on Computer Software and Applications Conference, ISBN: 0-8186-6705-2, pp. 418-425, Nov. 1994.*
Classification and Regression Trees, Leo Breiman, et al., pp. 102-111, Chapman & Hall, New York (1984).
Au Amelia M.
Dastouri Mehrdad
LandOfFree
Data processing method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data processing method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data processing method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3053922