IEEE-CS   
Venue


Home > Program > Tutorials > AM-03


ICPR2012 Tutorials AM-03
The Algebraic Approaches and Techniques in Image Analysis

Lecturer:
Igor Gurevich and Vera Yashina,
The Federal State Institution of Science Dorodnicyn Computing Centre of the Russian Academy of Sciences, Moscow, Russian Federation

 

Abstract:

The main task of the tutorial is to explain and discuss the opportunities and limitations of algebraic approaches in image analysis. During recent years there was accepted that algebraic techniques, in particular different kinds of image algebras, is the most prospective direction of construction of the mathematical theory of image analysis and of development an universal algebraic language for representing image analysis transforms and image models.
So, the main goal of the Algebraic Approach is designing of a unified scheme for representation of objects under recognition and its transforms in the form of certain algebraic structures. It makes possible to develop corresponding regular structures ready for analysis by algebraic, geometrical and topological techniques.
Development of this line of image analysis and pattern recognition is of crucial importance for automatic image-mining and application problems solving, in particular for diversification classes and types of solvable problems and for essential increasing of solution efficiency and quality.
The main subgoals of the tutorial are:
a) to set forth the state of the art of mathematical theory of image analysis;
b) to consider the algebraic approaches and techniques acceptable for image analysis;
c) to present a methodology, mathematical and computational techniques for automation of image mining on the base of Descriptive Approach to Image Analysis (DAIA);
d) to illustrate opportunities of algebraic techniques via an example of biomedical image analysis application problem.
In the Tutorial are essentially used the materials and discussions of the IAPR Technical Committee 16 "Algebraic and Discrete Mathematical Techniques in Pattern Recognition and Image Analysis".

 

Course description

Introduction. The goals and main parts of the tutorial. On a way to a unified theory (M.Duff, G.Matheron, J.Serra, J. von Neumann, S.Sternberg, S.Unger, U.Grenander, Yu.Zhuravlev, et al).
Duration – 15 min.

 

1. State of the art of mathematical theory of image analysis.

 

Modern trends in developing of mathematical tools for automation of image analysis, in particular in image- mining.
Duration – 30 min.

2. Algebraization of Pattern Recognition and Image Analysis (1970 – till now). The basic Algebraic Approaches and Techniques in Image Analysis.

Duration: 1 hour.
The goal: presentation of leading approaches of mathematical theory for image analysis oriented tor automation of image analysis and understanding.


2.1. Steps of the Algebraization. The history of developing algebraic construction for image analysis and processing – formal grammars, cellular automata, mathematical morphology, image algebras, multiple algorithms, descriptive approach.


2.2 Fundamentals and the Basic Theories.

  • The Basic Theories: 1) “Pattern Theory” (U.Grenander) – techniques for pattern recognition data representation and transformation on the base of regular combinatorial structures and algebraic and probabilistic means; 2) “Theory of Categories Techniques in Pattern Recognition” (M.Pavel) – formal describing of pattern recognition algorithms via transforms of initial data preserving its class membership; 3) “The Algebraic Approach to Recognition, Classification and Forecasting Problems” (Yu.Zhuravlev) – mathematical set-up of a pattern recognition problem, correctness and regularity conditions, multiple classifiers;

  • Image Algebras: 1) Standard Image Algebra by G.Ritter – a unified algebraic representation of image processing and analysis operations; 2) Descriptive Image Algebra by I.Gurevich – a unified algebraic language for describing, performance estimating and standardizing representation of algorithms for image analysis, recognition and understanding as well as for image models.

  • Contribution of the Russian mathematical school. Presentation of the most important original results on algebraic tools for pattern recognition and image analysis including algebras on algorithms, algebraic multiple classifiers, algebraic committees of algorithms, combinatorial algorithms for recognition of 2-D data, descriptive image models, 2-D formal grammars.

 

3. Descriptive Approach to Image Analysis and Understanding (DAIA)

 

Duration: 1 hour.

The goal: representation of main concepts and mathematical tools of DAIA by I.Gurevich and his school (conceptualization of notions for characterizing images in pattern recognition problems; basic model of image recognition process; descriptive image models, descriptive algorithmic schema).

 

  • Descriptive Approaches – basic steps (F.Ambler, G.Barrow, R.Burstall, T.Evans, S.Kaneff, R.Kirsh, R.Narasimhan, A.Rosenfeld, A.Shaw).

  • DAIA. The main intention of DAIA is to structure different techniques, operations and representations being applied in image analysis and recognition. The axiomatics and formal constructions of DAIA establish conceptual and mathematical base for representing and describing images and for its analysis and estimation. The DAIA provides a methodology and a theoretical base for solving the problems connected with the development of formal descriptions for an image as a recognition object as well as the synthesis of transformation procedures for an image recognition and understanding. The analysis of the problems is based on the investigation of inner structure and content of an image as a result of the procedures “constructing” it from its primitives, objects, descriptors, features and tokens, and relations between them.

  • Basic Axioms – Axiomatization of algebraic image analysis constitutes a base for unification of image analysis algorithms representations and image models representations. The axioms define properties and structure of the Image Formalization Space.

  • Image Formalization Space – the space includes sets of an image “states” and sets of image transforming schema for formalization and systematization of techniques and forms of information representations in image analysis, recognition and understanding problems. The presentation includes: a) construction of algorithmic schema generating phase trajectories for solving image analysis and recognition problems; b) Descriptive Image Models (DIM) - mathematical objects providing representation in a form acceptable for a recognition algorithm of information carried by an image and by an image legend (context); c) multiple DIM and multi-aspect image representations; d) topological properties of the Image Formalization Space.

4. Example.


The goal: to demonstrate application of the descriptive algebras techniques in an application problem - automating of biomedical image analysis.
Duration: 45 minutes.

  • The Matter of the Problem. It will be presented a technique for automation of analysis: a) cytological stained slide; b) histological stained slide.

  • Descriptive Algebraic Scheme for the Problem Solution. It will be presented techniques for slides analysis implemented via descriptive image algebras.

  • Mathematical Tools for Formal Representation of an Information Technology for Bio-medical Image Analysis. It will be presented descriptive image algebras and descriptive models being used for representation of descriptive algorithmic schema implementing the mathematical image analysis techniques.

  • Discussion of the results,

 

5. Conclusion.

 

Duration: 15 minutes.
Future Research (open and prospective problems and topics) and Bibliography.

 

 

 

Relevant References:

  1. H.G. Barrow, A.P. Ambler, and R.M. Burstall. Some Techniques for Recognizing Structures in Pictures // Frontiers of Pattern Recognition (The Proceedings of the International Conference on Frontiers of Pattern Recognition, ed. Satosi Watanabe).- Academic Press, New York, London.- 1972.-pp. 1-30.
  2. M.J.B. Duff, D.M. Watson, T.J. Fountain, and G.K. Shaw. A cellular logic array for image processing // Pattern Recognition, vol.5, no.3, June 1973.-pp. 229–247.
  3. T.G. Evans. Descriptive Pattern Analysis Techniques: Potentialities and Problems // Methodologies of Pattern Recognition (The Proceedings of the International Conference on Methodologies of Pattern Recognition).- Academic Press, New York, London, 1969.-pp. 149-157.
  4. A.I. Frei. Accurate estimates of the generalization ability for symmetric set of predictors and randomized learning algorithms // Pattern Recognition and Image Analysis, Pleiades Publishing, 2010. - Vol.20, No.3. - Pp.241–250.
  5. U. Grenander. Lectures in Pattern Theory// N.Y.: Sprinder-Verlag, 1976 V.1; 1978 V.2; 1981 V.3.
  6. U. Grenander. General Pattern Theory. A Mathematical Study of Regular Structure.- Clarendon Press, Oxford, 1993.
  7. I.B. Gurevich and V.V. Yashina. Descriptive Approach to Image Analysis: Image Models // Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications. - MAIK "Nauka/Interperiodica"/Pleiades Publishing, Inc., 2008. - Vol.18, No.4. - P. 518-541.
  8. I.B. Gurevich. Descriptive Technique for Image Description, Representation and Recognition // Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications in the USSR.- MAIK “Interpreodika”, 1991.-vol. 1- P. 50 – 53.
  9. I.B. Gurevich, A.V. Nefyodov. Algorithms for Estimate Calculations Designed for 2D Support Sets. Part 1: Rectangular Support Sets  // Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications. - 2001. - Vol. 11, No.4. - P. 662-689.
  10. I.B. Gurevich, V.V. Yashina. Operations of Descriptive Image Algebras with One Ring // Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications. Pleiades Publishing, Inc. 2006. - Vol.16, No.3. - pp. 298-328.
  11. I.B. Gurevich and V.V. Yashina. Descriptive Approach to Image Analysis: Image Models // Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications. - MAIK "Nauka/Interperiodica"/Pleiades Publishing, Inc., 2008. - Vol.18, No.4. - P. 518-541.
  12. I.B. Gurevich, V.V. Yashina, I.V. Koryabkina, H. Niemann, and O. Salvetti. Descriptive Approach to Medical Image Mining. An Algorithmic Scheme for Analysis of Cytological Specimens // Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications. - MAIK "Nauka/Interperiodica"/Pleiades Publishing, Inc., 2008. - Vol.18, No.4. - P. 542-562.
  13. I.B.Gurevich, V.V.Yashina. Image Formalization Space: Formulation of Tasks, Structural Properties, and Elements // Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications. – Pleiades Publishing, Ltd., 2011. - Vol. 21, No. 2. - P.134-139.
  14. S.Kaneff. Pattern Cognition and the Organization of Information // Frontiers of Pattern Recognition (The Proceedings of the International Conference on Frontiers of Pattern Recognition, ed. Satosi Watanabe).- Academic Press, New York, London.- 1972.-pp. 193-222.
  15. M.Yu Khachay. M.I.Poberii. Compexity and Approximability of Committee Polyhedral Separability of Sets in General Position // Informatica. 2009, Vol.20., no.2., p.217-234.
  16. M.Yu. Khachay. Computational and approximational complexity of combinatorial problems related to the committee polyhedral separability of finite sets //Pattern recognition and image analysis, 2008, Vol.18, no.2, P. 236-242.
  17. R. Kirsh. Computer Interpretation of English Text and Picture Patterns // IEEE-TEC, Vol. EC-13, No. 4, August, 1964.
  18. G. Matheron. Random Sets and Integral Geometry, Wiley, New York, 1975.
  19. J. Serra. Image Analysis and Mathematical Morphology, London, Academic Press, 1982.
  20. R.Narasimhan. Picture Languages // Picture Language Machines (ed. S.Kaneff).- Academic Press, London, New York.-1970.-pp. 1-30.
  21. M. Pavel. Fundamentals of Pattern Recognition, New York, Marcell, Dekker, Inc., 1989.
  22. M. Pavel. Pattern Recognition Categories // Pattern Recognition, 1976, Vol.8, No.3.- pp. 115-118.
  23. G.X. Ritter, J.N. Wilson.  Handbook of Computer Vision Algorithms in Image Algebra, 2-d Edition. CRC Press Inc., 2001.
  24. G.X. Ritter. Image Algebra. Center for computer vision and visualization, Department of Computer and Information science and Engineering, University of Florida, Gainesville, FL 32611, 2001.
  25. A.Rosenfeld. Picture Languages. Formal Models for Picture Recognition.-Academic Press, New York, San Francisco, London, 1979.
  26. A.Shaw. A Proposed Language for the Formal Description of Pictures // CGS Memo. 28, Stanford University, 1967.
  27. S. R. Sternberg. An overview of Image Algebra and Related Architectures, Integrated Technology for parallel Image Processing (S. Levialdi, ed.), London: Academic Press, 1985.
  28. S.R. Sternberg. Grayscale morphology // Computer Vision, Graphics and Image Processing, vol.35, no.3, 1986.-pp. 333-355.
  29. S.H. Unger. A computer oriented toward spatial problems // Proceedings of the IRE, vol.46, 1958, - pp. 1744-1750.
  30.  J. von Neumann. The general logical theory of automata// Celebral Mechenism in Behavior: The Hixon Symposium, John Wiley & Sons, New York, NY, 1951.
  31. Yu.I. Zhuravlev. An Algebraic Approach to Recognition and Classification Problems // Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications.- MAIK "Nauka/Interperiodica", vol.8. 1998.-pp.59-100.

 

About Lecturer:

Igor B.Gurevich. born 1938. dr.-eng. [diploma engineer (automatic control and electrical engineering), 1961, Moscow Power Engineering Institute, Moscow, USSR]; Dr. (mathematical cybernetics), 1975, Moscow Institute of Physics and Technology, Moscow, USSR. Head of Department at the Federal State Institution of Science “Dorodnicyn Computing Centre of the Russian Academy of Sciences (DCC), Moscow, RF; assistant professor at the Computer Science faculty, Moscow Lomonosov State University. He has worked from 1960 till now as an engineer and researcher in industry, medicine, and universities and from 1985 in the USSR/Russian Academy of Sciences. Area of expertise: mathematical theory of image analysis, image understanding, mathematical theory of pattern recognition, theoretical computer science, medical informatics, applications of pattern recognition and image analysis techniques in medicine, knowledge-based systems. 2 monographs (in co-authorship), 235 papers in peer reviewed journals and proceedings; 5 patents. He is scientific secretary of the National Committee for Pattern Recognition and Image Analysis of the Russian Academy of Sciences, member of the IAPR governing board (representative from RF), IAPR fellow, Vice-Chairman of the IAPR technical committee 16 "Algebraic and Discrete Mathematical Techniques in Pattern Recognition and Image Analysis". He has been the PI of many R&D projects as part of national and international research programs. Vice-editor-in-chief of Pattern Recognition and Image Analysis journal, member of editorial boards of several international scientific journals, member of the committees of many international scientific conferences. Teaching experience: Moscow Lomonosov State University, RF (assistant professor), Dresden Technical University, Germany (visiting professor), George Mason University, USA (visiting professor). prior experience in proposed topic: 32 years of research activity, 78 papers in peer reviewed journals, conference and workshop proceedings, 25 invited papers at international conferences, 5 lecture courses Moscow Lomonosov State University, supervision of PhD students and of graduate students. The tutorials on close topics were presented at 4 international conferences.


Vera V.Yashina. Born 1980. Diploma mathematician, Moscow Lomonosov State University (2002). Dr. (Theoretical Foundations of Informatics), 2009, the Federal State Institution of Science “Dorodnicyn Computing Centre of the Russian Academy of Sciences (DCC), Moscow, RF. researcher at DCC. She is scientofic secretary of the IAPR Technical Committee 16 "Algebraic and Discrete Mathematical Techniques in Pattern Recognition and Image Analysis". She has been the member of many R&D projects as part of national and international research programs. Scientific expertise: mathematical theory of image analysis, image algebras, models and medical informatics. Author of 40 papers in peer reviewed journals, conference and workshop proceedings. She was awarded several times for the best young scientist papers presented at several international conferences. Teaching experience: Moscow State Lomonosov University. Prior experience in proposed topic: 10 years of research activity, 27 papers in peer reviewed journals, conference and workshop proceeding, 14 invited papers at International Conferences, supervision of graduate students.

 

> Back to List of Tutorials

 

Archive: Call for Tutorial Proposals

 

 

(C) 2010-2012 ICPR2012 Organizing Committee. All rights reserved. http://www.icpr2012.org