Next: Computer Science and Up: Department of Computer Previous: Shape Modeling Laboratory

Image Processing Laboratory


/ Shunji Mori / Professor
/ Hirobumi Nishida / Associate Professor
/ Tony Y.T. Chan / Assistant Professor
/ Yu Nakajima / Research Associate

First and foremost, the Image Processing Laboratory engages in research and development of image pattern recognition systems. More specifically, as can be seen from the background information and the recent research publications of the members of the laboratory, character recognition is our current focus. Related to the recent involvement of multimedia systems, character recognition has been noted by many researchers and engineers. On the other hand, character recognition techniques are generally divided into off-line and on-line methods. The former is typical in character recognition and aims at duplicating the human ability in recognition. However, on-line character recognition is also noted recently in connection with so-called pen computers. On-line methods provide very flexible, convenient, and natural human-interface. Historically speaking, these techniques have been developed separately. However, both techniques can be developed together in principle. The common approach makes possible recognition flexibility in such a way that the usual constraints being imposed on the on-line techniques can be removed. For example, writing order and number of strokes constituting a character are typical of such constraints. On the other hand, we are requested to develop an inspection system for flaw of Sake bottles. The contribution to the domestic industry is very important mission of our University. Therefore, we are doing a basic research on that together with Industry Application Laboratory. In general, image inspection is a very important theme and has many applications in industry broadly.

In this respect, one of our members, Prof. Nishida, is a world-class to level researcher and engineer. Now he becomes well-known in this field internationally and so has been appointed as a Chairman of the IAPR (International Association for Pattern Recognition) Technical Committee, TC 8 (Application in Industry) in spite of his young age. This is very appropriate considering his engineering background. Actually, an OCR group in which Prof. Nishida played and important role developed a very powerful OCR package when he worked for Ricoh Research and Development Center. One of the members of the OCR group was Mr. Nakajima, who has joined us as a research associate. He is well-acquainted with different computer systems and also works as an instructor in programming. The system developed is called filtering in character recognition, which makes the packages very fast without being hardware-specific. Prof. Nishida and the OCR group were awarded the Excellence in Programming Prize from the Ministry of Post and Telecommunications. The basic configuration of the system was proposed by Prof. Mori when he was head of the Artificial Intelligence Research center of Ricoh.

Naturally, the essential point of the developed system lies in the excellent algorithm of character recognition, which is based on an algebraic approach to shape description. This approach was investigated as basic research by Prof. Mori when he worked for the Electrotechnical Laboratory of the Ministry of International Trade and Industry.

Later the basic line was further developed, in theory and in practice, by Prof. Nishida. We think that this is one of the most elegant theories in character recognition. He is developing his theory further and succeeded in making a very systematic nonlinear deformation model of a standard shape belonging to a class. This model covers almost conceivable deformation of a character shape in the level of Roman alphabet, Katakana and Hirakana, at least. Because of its theoretical richness and high-level abstraction, the model has very broad applications in shape recognition in general. It is applicable to both off-line and on-line character recognition systems, for example. Further extension of the theory is in the application of the recognition of three-dimensional bodies, in which a piece of the surfaces must be represented effectively in terms of pattern recognition and global organization mechanism. In this regard, a set of primitive surfaces must be considered. Furthermore, in addition to basic recognition mechanisms in a bottom-up manner. Rich knowledge concerning " objects" must be naturally employed. Some knowledge representational methods developed in the field of artificial intelligence research are being considered. Assistant Professor Chan is investigating unifying pattern recognition and artificial intelligence approaches based on models proposed by Prof. Lev Goldfarb of the University of New Brunswick, Prof. Nishida, and himself.

On the other hand, any abstract theory must have its raison d'etre in the real world. The proofs are in its utility. In this sense, experiments and/or computer simulation are essential research components. To that end, we need powerful facilities such as observation. display, interface, and calculation systems. To make such an integrated experimental system is also very important research work.

In turn, it can be easily applicable to the top-down education system at the University of Aizu. Actually we have developed such experimental system called IRAPES (Image Recognition And Processing Experiment System) cooperated with Ricoh Software Engineering. This will be further developed in such a way that it contains more application programs.

At any rate, the performance level of current image recognition systems is far below that of the human beings, who can recognize very distorted handwritten characters and degraded noisy printed characters easily without any heuristical learning. This ability is most mysterious. Therefore, from a long-term historical perspective, we are still only at the dawn of the day. Lots of work is available for ambitious young students, researchers, and engineers, in particular. We will pursue this very interesting research field along the lines mentioned.


Refereed Journal Papers

  1. H. Nishida. Structural feature extraction using multiple bases. Computer Vision and Image Understanding, 62(1):78--89, July 1995.

    The prime difficulty in research and development of the handwritten character recognition systems is in the variety of shape deformations. In particular, throughout more than a quarter of a century of research, it is found that some qualitative features such as quasi-topological features (convexity and concavity), directional features, and singular points branch points and crossings are effective in coping with variations of shapes. On the basis of this observation, Nishida and Mori (1992) proposed a method for structural description of character shapes by few components with rich features. This method is clear and rigorous, can cope with various deformations, and has been shown to be powerful in practice. Furthermore, shape prototypes (structural models) can be constructed automatically from the training data (Nishida and Mori, 1993). However, in the analysis of directional features, the number of directions is fixed to four, and more directions such as 8 or 16 cannot be dealt with. For various applications of Nishida-Mori's method, we present a method for structural analysis and description of simple arcs or closed curves based on $2^m$-directional features ($m=2,3,4,\ldots$) and convex/concave features. On the other hand, software OCR systems without specialized hardware attract much attention recently. Based on the proposed method of structural analysis and description, we describe a software implementation of a handwritten character recognition system using multi-stage strategy.

  2. H. Nishida. Model-based shape matching with structural feature grouping. IEEE Transactions on Pattern Analysis and Machine Intelligence, 17(3):315--320, March 1995.

    An essential problem in on-line handwriting recognition is in the shape variation along with the variety of stroke number and stroke order. In this paper, we present a clear and systematic approach to shape matching based on structural feature grouping. To cope with topological deformations caused by stroke connection and breaking, we incorporate some aspects of top-down approaches systematically into the shape matching algorithm. The grouping of local structural features into high-level features is controlled by high-level knowledge as well as the simple geometric conditions. The shape matching algorithm has the following properties from the viewpoint of on-line character recognition: (a) Stroke order, direction, and number are free; (b) Stroke connection and breaking are allowed.

  3. H. Nishida. Curve description based on directional features and quasi-convexity/concavity. Pattern Recognition, 28(7), July 1995.

    Qualitative and global features are appropriate for describing the shape of a complex and deformed object rather than quantitative and local features. In particular, quantized directional features and quasi-convexity/concavity are powerful and flexible for describing shape of handwritten characters. In this paper, we present a method for structural analysis and description of simple (open) arcs or closed curves based on $2m$-directional features ($m=1,2,3,\ldots$) and quasi-convexity/concavity. We show some examples of shape description of handwritten characters and experimental results for selecting the optimal quantization of direction in handwritten character recognition.

  4. H. Nishida. A structural model of shape deformation. Pattern Recognition , 28(9), September 1995.

    An essential problem in handwriting recognition is how to cope with the complex shape deformation, and therefore, the modeling of the deformation and metamorphosis (transformation of an instance of a class into an instance of the other class via continuous transformation) is a key to breaking through the difficulties in handwriting recognition. In this paper, on the basis of the structural feature extraction and description by Nishida, we present a model for structural deformation with simple, local operations that preserve the global structure of the shape. Furthermore, we present an experimental approach to analysis of metamorphosis of character shapes based on the structural deformation model.

  5. H. Nishida. Shape recognition by integrating structural descriptions and geometrical/statistical transforms. Computer Vision and Image Understanding, 1995.

    The prime difficulty in research and development of handwritten character recognition systems is the variety of shape deformations. The key to recognizing such complex objects as handwritten characters is through shape descriptions which are robust against shape deformation, together with quantitative estimation of the amount of deformation. In this paper, on the basis of the structural description by Nishida and Mori (1992), we propose a shape matching algorithm and a method for analysis and description of shape transformation for handwritten characters. The object is described in terms of a qualitative and global structure which is robust against deformation, and the description is matched against built-in models. On the basis of the correspondence of components between the object and the model, geometrical and statistical transformations are estimated, and the decision of recognition or rejection is based on the estimations. Structural descriptions and geometrical/statistical transforms are integrated in a systematic way. Experimental results are shown for off-line handwritten numeral recognition and on-line handwriting recognition.

  6. H. Nishida and S. Mori. A model-based split-and-merged method for character string recognition. International Journal of Pattern Recognition and Artificial Intelligence, 8(5):1205--1222, 1994.

    Recognition of handwritten character strings is a challenging problem, because we need to cope with variations of shapes and touching/breaking of characters at the same time. A natural approach to recognizing such complex objects is as follows: The object is decomposed into segments, and meaningful partial shapes--shapes which are recognized as some characters are constructed by merging segments locally. Then, a globally consistent interpretation of the object is determined from the combination of partial shapes. This approach can be referred to as a model-based split-and-merge method. Based on this idea, we present an algorithm for recognition and segmentation of character strings. We give systematic performance statistics by experiments using handwritten numerals. This algorithm can be applied to character strings composed of any number of characters and any types of touching or breaking, whether the number of constituent characters is known or unknown.

Refereed Proceeding Papers

  1. H. Nishida. Curve description based on directional features and quasi-convexity/concavity. In G. Borgefors, editor, Proceedings of the Ninth Scandinavian Conference on Image Analysis (Uppsala, Sweden), pages 579--586. IAPR, June 1995.

    Qualitative and global features are appropriate for describing the shape of a complex and deformed object rather than quantitative and local features. In particular, quantized directional features and quasi-convexity/ concavity are powerful and flexible for describing shape of handwritten characters. In this paper, we present a method for structural analysis and description of simple (open) arcs or closed curves based on $2N$-directional features ($N=1,2,3,\ldots$) and quasi-convexity/concavity. We show some examples of shape description of handwritten characters and experimental results for selecting the optimal quantization of direction in handwritten character recognition.

  2. H. Nishida. A structural model of continuous transformation of handwritten characters. In Proceedings of the Third International Conference on Document Analysis and Recognition (Montreal, Canada). IAPR, IEEE Computer Soceity Press, August 1995.

    An essential problem in handwriting recognition is how to cope with the complex shape deformation, and therefore, the modeling of the deformation and metamorphosis (transformation of an instance of a class into an instance of the other class via continuous transformation) is a key to breaking through the difficulties in handwriting recognition. In this paper, on the basis of the structural feature extraction and description by Nishida, we present a model for structural deformation with simple, local operations that preserve the global structure of the shape. Furthermore, we present an experimental approach to analysis of metamorphosis of character shapes based on the structural deformation model.

  3. H. Nishida. Automatic construction of structural models for unconstrained handwritten characters. In Proceedings of the Third International Conference on Document Analysis and Recognition (Montreal, Canada). IAPR, IEEE Computer Soceity Press, August 1995.

    An innovative approach to automatic construction of structural models was proposed by Nishida and Mori (1993). This approach classifies shapes according to the representation of continuous transformation, and a class is composed of shapes that can be transformed continuously to each other. However, global structure and features of the shape are changed considerably by shape deformation in unconstrained handwriting, and therefore, a large number of classes are required for dealing with unconstrained handwritten characters. The clues for discontinuous structural transformation lie in deformation around singular points and stroke connection of handwriting. For designing an algorithm for automatic construction of structural models incorporating discontinuous transformations, we analyze systematically how global structure and features are changed according to (1) structural transformation around singular points; (2) stroke connection. Based on the set of systematic laws of shape transformation, we design an algorithm for finding component correspondence between a pair of deformed patterns, and present an algorithm for automatic construction of structural models for unconstrained handwritten characters along with some examples and experimental results. The proposed algorithm can generalize unconstrained handwritten characters into a small number of classes, and one class can represent various deformed patterns.

  4. T. Suzuki, H. Nishida, Y. Nakajima, H. Yamagata, M. Tachikawa, and G. Sato. A handwritten character recognition system by efficient combination of multiple classifiers. In A. L. Spitz and A. Dengel, editors, Document Analysis Systems, pages 169--187. World Scientific, 1995.

    Handwritten character recognition has been increasing its importance and has been expanding its application areas. It is challenging to develop a handwritten character recognition system that satisfies the requirements for processing speed, performance, and portability at the same time. In this paper, we present an engineering solution to the problem of finding an efficient way of combination of multiple algorithms based on the following principle: clearly and neatly written data of high image quality are recognized quickly by a simple and fast algorithm, and distorted or degraded ones are recognized based on decisions by multiple experts even if it takes time to ask and collect their answers. We demonstrate the performance of the completed system by experiments using real data.

  5. H. Nishida. Model-based shape matching with structural feature grouping. In Proceedings of the 12th International Conference on Pattern Recognition (Jerusalem, Israel), volume 2, pages 599--601. IAPR, IEEE Computer Society Press, October 1994.

    An essential problem in on-line handwriting recognition is in the shape variation along with the variety of stroke number and stroke order. This paper presents a clear and systematic approach to shape matching based on structural feature grouping. To cope with topological deformations caused by stroke connection and breaking, we incorporate some aspects of top-down approaches systematically into the shape matching algorithm. The grouping of local structural features into high-level features is controlled by high-level knowledge as well as the simple geometric conditions. The shape matching algorithm requires a small number of prototypes and has the following properties from the viewpoint of on-line character recognition: (a) The order of strokes is free; (b) The number of strokes is free; (c) Stroke connection and breaking are allowed.

  6. T. Suzuki, H. Nishida, Y. Nakajima, H. Yamagata, M. Tachikawa, and G. Sato. A fast and high-performance system for handwritten character recognition by efficient combination of multiple classifiers. In A. Dengel and L. Spitz, editors, Proceedings of International Association for Pattern Recognition Workshop on Document Analysis Systems (Kaiserslautern, Germany), pages 175--189. IAPR TC-10, 11, October 1994.

    Handwritten character recognition has been increasing its importance and has been expanding applications. New applications give rise to new requirements for the technology. It is challenging to develop a handwritten character recognition system with high processing speed, high performance, and high portability, because there is a trade-off among them. In current technology, it is difficult to attain high performance and high processing speed at the same time with single algorithms, and therefore, we need to find an efficient way of combination of multiple algorithms. In this paper, we present an engineering solution to this problem based on the following principle: clearly and neatly written data of high image quality are recognized quickly by a simple and fast algorithm, and distorted or degraded ones are recognized on the basis of decisions by multiple experts even if it takes time to ask and collect their answers. The system is based on multi-stage strategy as a whole: The first stage is the simple, fast, and reliable recognition algorithm with few substitution errors, and data of high quality are recognized in this stage, whereas sloppily written or degraded data are rejected and sent out to the second stage. The second stage is composed of a sophisticated structural classifier and a pattern matching method, and these two complementary algorithms run in parallel (multiple expert approach). We demonstrate the performance of the completed system by experiments using real data.

  7. H. Nishida. Integrating structural description and geometrical \& statistical transform. In C. Arcelli, L. P. Cordella, and G. S. di Baja, editors, Aspects of Visual Form Processing , pages 420--429. World Scientific, 1994.

    The prime difficulty in research and development of handwritten character recognition systems is the variety of shape deformations. The key to recognizing such complex objects as handwritten characters is through shape description which is robust against shape deformation and quantitative estimation of the amount of deformation. In this paper, on the basis of the structural description by Nishida (1992), we propose a shape matching algorithm and a method of analysis and description of shape transformation for handwritten characters. The object is described in terms of qualitative and global structure which is robust against deformation, and it is matched against the built-in models. On the basis of the correspondence of components between the object and the model, geometrical and statistical transformations are estimated, and the decision of recognition or rejection is made based on the estimations. Structural description and geometrical/statistical transform are integrated in a systematic way. Experimental results are shown for handwritten digit recognition and on-line handwriting recognition.

Chapters in Books

  1. H. Nishida and S. Mori. Document image analysis, a model-based split-and-merge method for character string recognition. pages 209--226. World Scientific, 1995.

Technical Reports

  1. H. Nishida. Integrating structural description and geometrical/statistical transform. 94-1-019, University of Aizu, April 1994.

  2. H. Nishida. A structural model of shape deformation. 94-1-035, University of Aizu, July 1994.

  3. H. Nishida. Curve description based on directional features and quasi-convexity/concavity. 94-1-036, University of Aizu, July 1994.

  4. H. Nishida. Automatic construction of structural models for unconstrained handwritten characters. 94-1-046, University of Aizu, November 1994.

Patents

  1. H. Nishida. Method for extracting features from on-line handwritten characters. register 5313528, H. Nishida, USA, May 1994.

  2. H. Nishida. Method for classifying line patterns of characters in dictionary. register 5317649, H. Nishida, USA, May 1994.

Academic Activities

  1. Hirobumi Nishida, International Association for Pattern Recognition, 1994. Chairman, Technical Committee on Applications in Industry, International Association for Pattern Recognition (October 1994--).

  2. Hirobumi Nishida, International Association for Pattern Recognition, 1994. Member, Technical Committee on Structural and Syntactic Pattern Recognition, International Association for Pattern Recognition (January 1995--).

  3. Hirobumi Nishida, IEEE Computer Society, 1994. Reviewer, IEEE Transactions on Pattern Analysis and Machine Intelligence (IEEE Computer Society).

  4. Hirobumi Nishida, Computer Vision, Graphics, and Image Processing, 1994. Reviewer, Computer Vision, Graphics, and Image Processing: Image Understanding (Academic Press).

  5. Hirobumi Nishida, IEEE Systems, Man, and Ceybernetics Society, 1994. Reviewer, IEEE Transactions on Systems, Man, and Cybernetics (IEEE SMC Society).

  6. Hirobumi Nishida, Fourth International Workshop on Frontiers in Handwriting Recognition, 1994. Reviewer, Fourth International Workshop on Frontiers in Handwriting Recognition.

  7. Hirobumi Nishida, Third International Conference on Document Analysis and Recognition, 1994. Reviewer, Third International Conference on Document Analysis and Recognition.

  8. Shunji Mori, Third International Conference on Document Analysis and Recognition., 1994. A member of the program committee of ICDAR '95: The Third International Conference on Document Analysis and Recognition.

  9. Tony Y. T. Chan, International Workshop on Syntactic and Structural Pattern Recognition 1996, 1994.

    Involved in the selection of the next venue for holding the International Workshop on Syntactic and Structural Pattern Recognition 1996, which will be at Leipzig (Bach's hometown), Deutschland, co-chaired by Dr. Patrick Wang and Dr. Petra Perner with honorary chair Azriel Rosenfeld.

Others

  1. Tony Y. T. Chan, 1994.

    Presented and defended a paper on Oct 6, 1994 in the IAPR's International Workshop on Syntactic and Structural Pattern Recognition in Israel, Proceedings to be published as a book later on. In this paper, we present a general and formal definition for the induction problem, and a general and formal model to solve this problem. We demonstrate the usefulness of the model on the specific induction problem given by Mitchell.

  2. Tony Y. T. Chan, 1994. Member of the program committee of pAs'95: Aizu International Symposium on Parallel Algorithm/Architecture Synthesis.

  3. Tony Y. T. Chan, 1995.

    Submitted a paper to Fifth Scandinavian Conference on Artificial Intelligence, to be held in Trondheim, Norway. It was accepted. Currently, there are two mainstreams in the study of pattern learning or machine learning. The symbolist AI mainstream uses discrete representation and discrete processing. The neural network/statistical pattern recognition mainstream uses numeric (finite approximation of continua) representation and numeric processing. There is a new metric unified approach, first proposed by Goldfarb, that could uses discrete representation but numeric (continuous) processing. The most intensively and extensively studied subarea of machine learning is inductive learning, i.e.,learning to generalize from given examples and non-examples. Instead of learning concepts by discrete search as traditionally done in AI, or learning weights in a fixed euclidean vector space as done in neural networks, we apply the metric unified (dynamic and super-euclidean) model to confront this general problem. More specifically, in this paper, we demonstrate the success of the model on the bench mark xor problem. We show how the system successfully learns the weights that would allow it to distinguish between 2-bit vectors of odd and even parity.



Next: Computer Science and Up: Department of Computer Previous: Shape Modeling Laboratory


www@u-aizu.ac.jp
January 1996