Fast Pattern Recognition in a Space of Tree-structured Representations
A new approach has been developed for fast pattern recognition in the original space of tree-structured pattern representations by geometric primitives. The approach is oriented for a wide class of 2D patterns given by the solid shapes with grayscale features. The possible patterns are hand gestures, poses, handwritten characters, signatures, faces, and these examples are not exhausted all applications. The proposed methodology allows us to construct the universal tree-like representations that are approximately invariant to pattern rotation, translation, scale, and brightness. Given original distance measure for any pare of the representations permits to solve the recognition task with a small recognition error provided that a computational complexity of the decision algorithm is exponentially smaller relatively to the full search algorithm. The main stones of the approach are the following.
1. Constructing the pattern representations in a form of complete binary trees or pyramids that contains the representations with increasing resolution levels.
2. Leaning the classifier in a space of the tree-structured pattern representations over a given distance measure; this procedure amounts to selecting a set of templates that provide the generalized Kolmogorov's epsilon-network.
3. Constructing the hierarchically structured base of the templates containing the multiresolution levels. This structure permits to make the recognition decision about any submitted pattern by a successive refinement search algorithm.
4. The algorithm of guided search for the decision in the base of the templates using a special strategy of reducing the search regions in successive levels with increasing resolution.
It is shown that the base of the templates consisting of L resolution levels provide approximately 2^L/(L+1) times decrease of a computational complexity of the recognition algorithm relatively to a full search algorithm. The performed experiments on gesture and signature recognition via the tree-structured representations showed the rate of error no more than 0,015 when L > 6.
Publications
1. Lange M., Lange A. Data classification in the space of tree-structured representations. // Pattern Recognition and Image Analysis. Vol. 14, no. 1, pp. 12-22. - Moscow: MAIK Nauka/Interperiodica, 2004.
2. Lange M., Ganebnykh S. Tree-like data structures for effective recognition of 2-D solids. // Proceedings of 17th International Conference on Pattern Recognition (ICPR 2004, Cambridge, UK). Vol. 1, pp. 592-595. - Los Alamitos, Calif.: IEEE CS Press, 2004.
3. Lange M. An Efficiency of Block-based Data Array Representations. // Pattern Recognition and Image Analysis. Vol. 15, no. 1, pp. 76-79. - Moscow: MAIK Nauka/Interperiodica, 2005.
4. Lange M., Ganebnykh S., Lange A. Moment-Based Pattern Representation Using Shape and Grayscale Features. // Lecture Notes in Computer Science. Vol. 4477, pp. 523-530. - Berlin: Springer, 2007.
5. Tatarchuk A., Sulimova V., Windridge D., Mottl V., Lange M. Supervised Selective Combining Pattern Recognition Modalities and its Application to Signature Verification by Fusing On-Line and Off-Line Kernels. // Lecture Notes in Computer Science. Vol. 5519, pp. 324-334. - Berlin: Springer, 2009.
6. Ganebnykh S., Lange M. Classification of 2D Grayscale Objects in a Space of the Multiresolution Representations. // Pattern Recognition and Image Analysis. Vol.19, no.4, pp. 591-602. - Moscow: MAIK Nauka/Interperiodica, 2009.
_________________________________________________________________________________________
Projects