Project 1645

Mathematical methods and algorithms for recognition of 3D contours

Leader: dr Boško Jovanovic


Subject of research

Development of mathematical methods and design of algorithms for the recognition of a class of surfaces in the three-dimensional space represented by a finite set of points.

Description of the work

The use of equipment for 3D scanning (3D scanners) in modern production processes and other areas of industry and technology is of growing importance. 3D scanner are used for scanning surfaces of real three-dimensional objects. After scanning of an object C, the image of it’s surface is obtained, i.e. a finite set S of points, where points are represented by their coordinates x, y, z. In most cases, S is the only information we have about the contour C. However, in many cases we need to know various mathematical properties of the contour C: geometrical, analytical, differential, topological, fractal, etc. Reconstruction and recognition of the contour C according to the image S is a hard problem in general, and for its solution various mathematical methods are necessary. In our project we shall focus mainly on polygonal surfaces, then second order surfaces, and in some cases on surfaces of the irregular shape. Also, we shall consider the degree of similarity of scanned objects in respect to their geometrical types. We shall use in our research the following methods: signal processing (digital image processing), fractal geometry, numerical mathematics and machine vision. Besides customary operations necessary in the early stage of the analysis of the image S (smoothing, clustering, and noise filtration), we shall use other methods and algorithms. These techniques will include edge detection (for example Sobel and Roberts edge detector), as well as method and notions of fractal geometry (for example, fractal dimension, fractal images of surfaces, fractal compression). The first phase of our research will include the use of software packages Mathematica 4.0 and Matlab 6.0. Occasionally, we shall use Lindermayer systems (a language for self-similarity). In the later phase of our project we shall try to implement so developed algorithms. For obtaining the experimental data, we are going to use an industrial 3D scanner. German Company MEL Micro Electronic GMBH (Munich, Germany), gave us this facility for this purpose. Also, we expect that we shall have the opportunity to use a relatively fast computer (workstation) that Mathematical Institute in Belgrade expects to have in the near future.

Originality of research

Application of modern mathematical methods in the analysis of 3D images, as of fractal geometry. Recognition of shapes of real three-dimensional objects with the irregular contours, as of chips.

Research Goal

The main goal of the project is the development of mathematical methods and design of new algorithms for recognition of shapes of real three-dimensional objects with surfaces represented by finite sets of points. The special attention will be given to the surfaces of the irregular contour. In the later phase of the project we plan to implement so obtained algorithms, namely to project the software for recognition of shapes of some classes of three-dimensional objects.

State of the Art in Scientific Field

World-wide Situation

The problem of pattern recognition is becoming very actual, especially with appearance of fast and cheap computers, and also in connection to automation and robotization of industrial production. Various aspects of this problem were considered from the mathematical and technological point of view. This problem is considered in various mathematical disciplines: discrete mathematics, geometry, numerical mathematics, topology, combinatorics, computer science, etc. Besides various very interesting mathematical contents, there have very important and rather concrete applications. All these leaded to the high activity in this field: publication of scientific articles and books, software development and construction of specialized facilities. A good review of this subject and the bibliography can be found, for example, in the book Fractal Geometry in Digital Imaging, M.J. Tarner, J.M. Blackledge, P.R. Andrews, Academic Press, 1998.

Domestic Situation

In the previous period there was a project Methods and models in theoretical, industrial an applied mathematics (04M03), coordinated by the Mathematical institute in Belgrade. As a part of it, Prof. Lj. Kocic leaded the project theme Geometrical modeling. There were studied mathematical models in computer geometry, properties of lines and surfaces of free form, as well as visualization of such models. Other groups of our mathematicians (specialized in geometry and topology), also considered the problem of shape recognition from their point of view. However, all these researches were mainly theoretically oriented, for example looking for topological and combinatorial aspects of the problem. We do not know if any of these researches had software implementation, or if they were applied to the analysis of contours of real three-dimensional objects.

Planned Project Results

Besides the interesting scientific aspect of the project, we expect that we shall also obtain results that can be directly applied in industry and the in technological development. The scientific aspect of the project concerns the development, understanding and introduction of contemporary mathematical disciplines in the subject of pattern recognition (from OCR up to computer visualization). It is well known that companies in the world produce equipment used in this area and that this equipment is commercially available. We stress the fact that the function of these facilities is based on mathematically sophisticated computer software. In this respect, results of our project make a basis for development of new technologies in automatic (robotic) production, automatic control of products, final and during the production process.

We expect that the software based on the algorithms developed in the project can be directly used for image processing from data supplied by industrial 3D scanners. In this respect, the possible applications are in the industry in automatic (robotic) production, automatic control of the quality and the standard of products, in medicine (for example in prosthetics), photogrammetry and other areas. Some applications include automatic assembling of electronic components, welding, control of railroad tracks, etc. Besides that, developed software might have very interesting commercial value.