THE DISCRETE GEOMETRICAL APPROACH TO VISUAL PATTERN RECOGNITION .

V.N.Kozlov. 1

1 M.V. Lomonosov Moscow State University, 119991, Russia, Moscow, Vorobjovy Gory , MSU, Main Building, Faculty of Mechanics and Mathematics, MATIS department, (495)-939-46-37, vnkozlov@mail.ru

We define an image as a finite nonempty set of points in a plane (or in a space). This definition is justified by the fact that any real grayscale image can be approximated by an image consisting of black points. In this way, any shade of gray can be represented by varying the density of points in different parts of the image. This representation also allows an analysis of color images, since any such image can be represented by combining three monochrome images. Finally, we see everything with our eyes. An image is projected on the retina in an eye and stimulates receptor cells, forming an analog of the image consisting of points on the retina.

The approach essentially bases on introduction of the internal coding of figures, invariant to their affine transformations.

In plane and space cases the internal code of figures is defined by the following. Points of a figure are numbered; with regard to dimension (2D or 3D) the set of all simplexes which are derived from figure's points is considered. For each simplex the measure is calculated. The code of a figure is the set of all triples which consist from two simplexes and their non-zero measures ratio.

It is shown for each case (plane or space), that figures have the same code (accurate within point’s numbers permutation) if and only if they are affine equivalent.

Matching (and recognition) of arbitrary figures A and B is grounded on the following. Sets А* and В* are generated as sets of all figures obtained from A and B by conversions from some class (affine in general case) of transformations. The set of values r(A`, B`), (where A` belongs to A*,and B` belongs to B*), which are the distances between sets A` and B` (Hausdorff distance) is considered. It is shown, that the minimum on this set is achieved on its finite subset that allows calculating it. This minimum is also a measure of similarity and distinction of figures.

Images stored in the memory of a recognizing device may contain numerous minute and superfluous details. The problem is to simplify an image so that only the features necessary for recognition are retained. However, it is not known in advance what features are essential. An approach to constructing a simplified analog of an image (called sketch) is described. It is proved that there exists a certain relation between similarity of sketches and similarity of originals. That allows to minimize the calculation for recognition.

Restoring of space figures using their plane projections (simulation of stereoperception) is considered. This restoring is based on theorems for relation between plane and space images.

To present time there exist two computer software implementations of the approach: first concerned with plane (2-dimensional) black-and-white image recognition and the second is concerned with stereoperception (r estoring of space figures using their plane projections).