Ccas.ru

IMAGE REPRESENTATION, PROCESSING,
ANALYSIS, AND UNDERSTANDING
The Joint Use of Image Equivalence and Image Invariance
in Image Recognition1
I. B. Gurevich and I. A. Jernova
Scientific Council on Cybernetics, Russian Academy of Sciences, ul. Vavilova 40, Moscow, GSP-1, 119991 Russia e-mail: igourevi@ccas.ru; jer_irina@mail.ru Abstract—The work is devoted to the investigation of the key concepts of mathematical theory of pattern rec-
ognition: image equivalence and invariance. Different ways to determine equivalence on the image set are con-
sidered and relations between image equivalence and invariance are analyzed. It is proved that the image rec-
ognition task in standard formulation can be reduced to the task that has a correct algorithm in the framework
of AEC algebraic closure (with certain restrictions on image transformations).
Therefore, it is sufficient to construct a family of suchheuristic algorithms for solving corresponding tasks Over several years, research into the development of and then to construct an algebraic closure of this family.
the mathematical apparatus for analysis and estimation The existence theorem is proved; it asserts that any task of information represented in the form of images has from the set of tasks related to the investigation of been carried out at the Scientific Council on Cybernet- poorly formalized situations turns out to be solvable in ics of the Russian Academy of Sciences [9, 10, 21].
This work presents new results concerning the estab-lishment of the conditions for existence of the class of Image recognition is one of the classical examples effective algorithms that includes the algorithm for cor- of the tasks with incompletely formalized and partially rect solution of an image recognition task. The pro- contradictory information. This gives reason to believe posed method for verifying the condition feasibility is that the algebraic approach applied to image recogni- based on the new definition of image equivalence intro- tion can yield convincing results and, hence, the most duced with reference to the special formulation of the perspective direction for developing the desired mathe- image recognition task. It is shown that the efficient matical apparatus for the analysis and estimation of the class of algorithms based on estimate calculations information represented by images is the “algebraiza- (AEC) [2] contains such an algorithm in its algebraic closure. The existence theorem is the main result.
Note that the idea of developing a unified algebraic theory covering different approaches and operations The selection of the algorithm that correctly classi- used in image and signal processing has a certain his- fies images on the basis of their descriptions is a topical tory that starts with the works of von Neumann and was problem in image recognition. The approach to image continued by S. Unger, U. Grenander [8], M. Duff, recognition developed by the authors is a specialization Yu.I. Zhuravlev [2, 20], G. Matheron, G. Ritter [16], of the algebraic approach to recognition and classifica- J. Serra [17], and others. The results presented here are tion problems introduced by Yu.I. Zhuravlev [2, 20]. It related to the descriptive approach to image analysis is based on the following idea. No accurate mathemat- and recognition [9, 10], a line of research in the field of ical models have been developed for poorly formalized image algebras different from those mentioned above, fields, such as geology, biology, medicine, and sociol- ogy. However, decent methods based on heuristic con-siderations have a great practical effect in many cases.
Unfortunately, the algebraic apparatus developed by Zhuravlev failed when applied directly to an image rec- 1 This work was partially supported by the Russian Foundation for ognition task. This is mainly caused by the complexity Basic Research, project nos. 02-01-00182, 03-07-06056; by the of the object of recognition, the image, and, as a conse- federal target oriented program “Research and Development in quence, by the substantial differences between the Priority Directions of Science and Technology” in 2002–2006, image recognition task and the classical one: project no. 37.011.11.0016; and by the program for fundamentalResearch of the Department of Mathematical Sciences of the • The standard object of classical recognition theory Russian Academy of Sciences “Algebraic and Combinatorial is usually described by the feature set; there is no natu- Methods for Mathematical Cybernetics,” project no. 10002- ral way for image description without losing essential information about the image; the known ways of imagedescription are either too complicated and time-con-suming (e.g., image representation as a raster) or Pattern Recognition and Image Analysis, Vol. 13, No. 4, 2003, pp. 570–578.
Original Text Copyright 2003 by Pattern Recognition and Image Analysis. English Translation Copyright 2003 by MAIK “Nauka /Interperiodica” (Russia). THE JOINT USE OF IMAGE EQUIVALENCE AND IMAGE INVARIANCE • Several images that differ in brightness, contrast, Let us introduce the notation f1 R f2; that is, f1 and f2 scale, or viewpoint can correspond to the same object are equivalent; i.e., they are related by the equivalence (scene); in the context of the recognition task, this means that different images of the same object should The equivalence relation should be reflexive, sym- be equally classified by the recognition algorithm.
metric, and transitive. Let us check these properties for This explains the interest that has arisen in the study and use of image equivalence in recognition f = e( f ) (by virtue of the existence of a unit element ∀f ⇒ f R f is fulfilled.
One of the basic ideas of the proposed approach to image recognition is the idea that a certain image is not f1 = g( f2) f2 = g ( f1) (since each nonzero element the only visual representation of the object but one of many possible. This means that one object can corre- f2 R f1 is fulfilled.
spond to several images that differ in scale, observation f = g ( f ), f = g ( f ) ⇒ f = g (g ( f )) = g ( f ) (by Thus, image recognition tasks in the framework of the proposed approach consist in the following: (a) the image is a partial representation of a certain entity 1, f2, f3 f1R f2, f2 R f3 f1 R f3 is fulfilled.
(object, scene) that should be described through these All three properties are fulfilled; therefore, R is the partial representations only; (b) on the image set, the equivalence relation can be defined as correspondenceof the images to the same entity; (c) images of one class The definition proposed is a constructive definition should have equal vectors of belonging; and (d) transi- in the sense that it suggests a way to construct classes tion from images to features is not predetermined, so of equivalent images. Let us consider simple examples features can be varied in applied tasks.
There are several ways to determine the equivalence Example 2.1.1.
relation on the image set. Note that the equivalence Let a finite group of transformations of order 3 be relation should be reflexive, symmetric, and transitive given; it is described by the following equations: G = at the same time it splits the entire set of images into {g, g–1, e}, g · g = g–1, g–1 · g–1 = g, and g · g–1 = g–1 · g = e.
nonoverlapping classes: image equivalence classes.
Let F be the space of image functions. Each element of Hereafter, the image will be regarded as a function the group of transformations operates in the following that satisfies the following definition.
Definition 2.1. Image, or image function, is a real-
g: f1(x, y) ∈ F f2(x, y) ∈ F, g is a bijection.
valued function f (x, y) such that f (x, y) ≠ 0 on the The effect of the element of the group of transfor- f (x, y)dxdy > 0.
mations on the image function can be interpreted in the following way. Let us consider f(x, y) in polar coordi-nates f(ρ, θ), by replacing the variables x = ρcosθ, y = ρsinθ. Let g be a rotation trough 2π/3 angle, g–1 a rota-tion trough –2π/3, and e a rotation trough 0. Here, the equations g · g = g–1and g–1 · g–1 = g are fulfilled. Then, Let us consider a definition of equivalent images g( f (ρ, θ)) = f ρ, θ based on the hypothesis that images of the same object (scene), differing in scale, illumination, and observa-tion angle, are equivalent in a sense (in the common or Image equivalence classes are formed according to everyday meaning of the term). Let us fix a certain set the following rule: two images are equivalent if one can of transformations that describe changes in scale, illu- be derived from another by rotating it trough 2π/3, mination, or observation angle. At first, the case where the transformations form a group is considered.
Example 2.1.2.
Let F be a space of image functions and G = {g1, …, gn} Let G = {g, g–1, e} be a group of transformations described by the equations g · g = g–1, g–1 · g–1 = g, Definition 2.1.1. Two images f1(x, y) and f2(x, y) are
and g · g–1 = g−1 · g = e. Let F = {f1, f2, f3, f4, f5, f6, f7, f8} equivalent if ∃g ∈ G: f1(x, y) = g( f2(x, y)).
PATTERN RECOGNITION AND IMAGE ANALYSIS Vol. 13 No. 4 2003 the equivalence definition if the requirement to be agroup on the transformation set is weakened? For instance, let us remove the axiom of inverse element existence from group axioms. Let us consider a sem- igroup G = {g1, …, gn}. Suppose that two images 1(x, y) and f2(x, y) are connected with equivalence relation R, if ∃g ∈ G: f1(x, y) = g( f2(x, y)). Let us check Let us recall that equivalence relation R was intro- whether this relation is reflexive, symmetric, and tran- duced as follows: fi R fj, if ∃g0 ∈ G: fi = g0( fj), i, j ∈ {1, sitive, i.e., whether this relation is an equivalence rela- The following relations are fulfilled in this example: f R f , f R f , f R f , f R f , f R f , f R f , (2.1.3) f = e( f ) (by virtue of the existence of a unit ele- f R f , f R f , f R f , f R f , f R f , f R f , (2.1.4) ∀f ⇒ f R f is fulfilled.
f = g ( f ) ⇒ f = g ( f )? ∀f1, f2 f1R f2 ⇒ f2R f1 is not fulfilled.
The following image equivalence classes are f1 = g1( f2), f2 = g2( f3) ⇒ f1 = g1(g2( f3)) = g3( f3) (by K = { f , f , f }, K = { f , f , f }, 1, f2, f3 f1 R f2, f2 R f3 f1 R f3 is fulfilled.
The reflexivity and transitivity properties are ful- The notion of image equivalence introduced above filled, while the symmetry property fails without the is convenient, and it has indubitable advantages in axiom of existence of inverse elements. Consequently, respect to applicability to pattern recognition theory.
this relation is not an equivalence relation. Further Let us formulate the major advantages of this defini- weakening of group requirements leads to the failure of transitivity and reflexivity property fulfillment.
(1) The physical interpretation of this definition Since the practical importance of the introduced conforms to our view of image equivalence, according equivalence definition consists in its application for to which images are considered to be equivalent if one proving the theorem about the correctness of algebraic differs from another due to a certain transformation, closure of AEC in an image recognition task, the group e.g., rotation, translation, scaling, illumination change, requirement can be considered necessary for the trans- (2) The introduced definition allows one to reduce Also note that the question arises as to how to inter- an image recognition task in terms of equivalence pret group application for image functions with the use classes to the image recognition task in standard formu- of an arbitrary group G of transformations of order n.
lation. This reduction is carried out by substituting eachequivalence class by a single image, a class representa-tive, with certain restrictions on the type of transforma- 2.2. Equivalence Directed at the Recognition Task tions. As will be shown further, the theorem on the cor- Image equivalence definitions directed at the special rectness of an algebraic closure of AEC algorithms can setup of an image recognition task can be considered.
be proved for the reduced image recognition task [13].
Let a certain set of allowable images described by (3) It is essential that, in the case where transforma- n-dimensional feature vectors be given. The set of tions form a group, the mathematical methods of image allowable images is covered by a finite number of sub- invariant construction are developed, which allows sets called classes; let l classes K1, …, Kl be given. Let images to be compactly described with no extra calcu- a recognition algorithm A be given which constructs an lating effort [15]. Particularly, the parametric image l-dimensional information vector on the basis of an models can be constructed on the basis of invariant fea- n-dimensional description vector. Let us recall that a tures. In this case, equivalent images have the same vector of the object’s belonging to a class is called an descriptions according to the equivalence definition information vector; here, information vector element values (0, 1, ∆) are interpreted as follows: “object does Let us consider some additional aspects of image not belong to the class,” “object belongs to the class,” equivalence regarding groups of transformations.
and “the algorithm fails to determine whether the object Only transformations that form a group were used in belongs to the class or not,” respectively [2]. We con- this definition. The question arises as to how important sider that each recognition algorithm A ∈ {A} can be this requirement is. In other words, what will happen to represented as a consequent implementation of algo- PATTERN RECOGNITION AND IMAGE ANALYSIS Vol. 13 No. 4 2003 THE JOINT USE OF IMAGE EQUIVALENCE AND IMAGE INVARIANCE rithms B and C, where B is a recognition operator that of formal image descriptions or in a space of features rep- transforms training information and a description of the resenting images. As this takes place, ε-equivalence of allowable object into a numerical vector, called the esti- images can be considered for a certain a priori given mation vector, and C is a decision rule that transforms parameter ε. We recall that we regard an image as a an arbitrary numerical vector into an information vec- real-valued function f (x, y) meeting the conditions of Definition 2.1. Let D( f (x, y)) be a certain formal image The performance of a recognition algorithm (A = description (vector of features, image defined at each BC) can be sketched in the following way.
point of a raster, analytical representation of imagefunction, etc.) and L(D( f (x, y))) be a metric space of formal image descriptions with metric ρ.
Definition 2.3.1. Two images f1(x, y) and f2(x, y) are
Recognition operator B.
-equivalent with respect to metric ρ if ρ( f1(x, y), f2(x, y)) < ε, where ε is an a priori given constant.
Information vector γ = (γ1, γ2, …, γl).
The construction of equivalence classes becomes a topical problem since the notion of equivalence is one Thus, during the solution of an image recognition of the crucial notions in the proposed approach to task, an object of recognition, i.e., an image, is image recognition. Let us consider here one of the ways described with the help of three different vectors: the to decompose an image set into equivalent classes n-dimensional feature vector, the l-dimensional vector based on the construction of image invariants.
of estimations for classes, and the l-dimensional infor-mation vector. This permits consideration of three lev- Let the space F of image functions f(x, y) be given. Let F be a ring. Let us define a homomor-phism ϕ : F F'. The kernel of homomorphism is Definition 2.2.1. Images are called equivalent with
Kerϕ = {f(x, y)|ϕ( f (x, y)) = 0}. Let us construct a factor respect to the recognition algorithm A if their informa- set F from the kernel of homomorphism F\Kerϕ. The tion vectors constructed by the algorithm A coincide.
set (ring) of image functions is split into nonoverlap- Definition 2.2.2. Images are called equivalent with
ping cosets from the kernel of homomorphism. These respect to the recognition operator B if their vectors of cosets are considered to be image equivalence classes.
estimations for classes constructed by the algorithm Bcoincide.
{ f (x, y)|ϕ( f (x, y)) = a} = Class(a).
Definition 2.2.3. Images are called equivalent if
(Each coset is defined as follows: Class = bKerϕ = It is easy to verify that the introduced equivalence The main idea is to use invariants as the basis for definitions are correct, since they represent an equality constructing the kernel of the homomorphism. Let us relation which is a special case of the equivalence rela- recall one of the definitions of an invariant.
tion. Moreover, image equivalence in terms of Defini- Definition 3.1. [3] An invariant is a mapping ϕ of
tion 2.2.3 implies image equivalence in terms of Defi- the considered aggregate of mathematical objects M, nition 2.2.2, which, in turn, leads to image equivalence supplied with a fixed equivalence relation ρ, into another aggregate of mathematical objects N, which is Let us consider the equivalence definition based on constant on equivalence classes M on ρ (more precisely, the group of transformations introduced in the previous the invariant of equivalence relation ρ at M).
paragraph. If an image is described by the vector of fea- The definition of invariant implies that the mapping tures invariant relative to the group transformations, is constant on equivalence classes of the set. Hence images equivalent in terms of Definition 2.1.1 will have homomorphism ϕ is invariant. In other words, the the same feature descriptions. In this case, image equiv- invariant ϕ must be constructed for the set F of func- alence based on group transformations implies image tions f(x, y) and, therewith, the set ϕ is the kernel of a equivalence in terms of Definitions 2.2.1, 2.2.2, and certain homomorphism. In order to construct image 2.2.3, i.e., equivalence directed at the recognition task.
equivalence classes, the kernel of homomorphismshould be constructed and, then, a factor-ring fromKerϕ.
2.3. Equivalence with Respect to a Metric In some cases, when images in the recognition task are not strictly equivalent in terms of the definitions introduced above, it makes sense to consider image It is obvious from the above reasoning that invari- proximity with respect to a metric specified in a space ance is a very important notion in image recognition PATTERN RECOGNITION AND IMAGE ANALYSIS Vol. 13 No. 4 2003 theory. Note that image invariance is often employed criminant ∆ = 3b2c2 + 6abcd – 4b3d – 4ac3 – a2d2 of a for practical purposes. In many tasks of image analysis ternary (n = 2, r = 3) form f(x, y) = ax3 + 3bx2y + 3cxy2 + and processing, it is convenient to describe images by sets of invariant characteristics: they are more resistant The classical setup of the main task of the theory of to noise as compared to other features and, as a rule, invariants is to calculate invariants and provide their provide high recognition quality. The proposed complete description. Various formal processes (polar- approach treats invariants not only as effective numeri- ization, restitution, Kapelli identity law, Kelly Ω-pro- cal features but also as an algebraic instrument for con- cess, etc.) were developed for this purpose. The devel- structing equivalence classes in image recognition opment of the so-called symbolic method in the theory tasks. In order to cover these two positions of invariant of invariants was the culminant point of this activity; it application in image recognition, we recall some is a formal way to calculate all invariants of a degree no knowledge of invariant theory (Section 4.1) and briefly discuss the invariant features that will be most oftenused in image analysis (Section 4.2).
The global theory of semisimple groups and their representations developed by the 1930s promoted thefollowing most common setup of the main task of the 4.1. Basic Facts from the Theory of Invariants classical theory of invariants. Let an arbitrary group G The theory of invariants [1] in its classical definition and its finite-dimensional linear representation ρ in the (the algebraic theory of invariants) is an algebraic the- linear space V on the field k be given. If x1, …, xn are the ory concerned with algebraic expressions (polynomi- coordinates in V (in some basis), then each element als, rational functions and their aggregates) changing in g ∈ G determines a linear replacement of variables a certain way during nondegenerate linear replace- x1, …, xn. Performing this replacement of variables in ments of the variables. Here, generally speaking, not the arbitrary polynomial ϕ(x1, …, xn), one obtains a new the entire linear group is considered (i.e., not the com- polynomial; hence g induces a certain transform (auto- plete set of nondegenerate linear replacements of the morphism) of the ring of all polynomials k[x1, …, xn] on variables) but its certain subgroup (e.g., orthogonal, variables x1, …, xn on the field k. The polynomial ϕ(x1, …, xn), not changing under these transforms (i.e., One of the first objects invariant theory was con- when g runs over entire G), is called ϕ(x1, …, xn)- cerned with were so-called invariants of the form. The invariant of representation ρ for group G.
form of order r of n variables with undefined coeffi- From the very beginning, invariant theory revealed the circumstance that made it possible to survey the entire system of invariants as a whole: in all the consid- ered cases, it was possible to separate a finite number of basic invariants ϕ1, …, ϕm, i.e., the invariants that made after linear replacement of variables x it possible to express each other invariant ϕ with the prescribed representation as their polynomial; i.e., ϕ = j , 1 ≤ i ≤ n, where αij are real or complex F(ϕ1, …, ϕm). In other words, the algebra of invariants numbers, it converts into the following form: turned out to be finitely generated.
A new stage in invariant theory is connected to the extension of the number of tasks and geometric appli- cations of the theory. Contrary to the classical theory of invariants, where, as a main object, the ring of polyno- so that the linear replacement of variables mentioned mials of n variables over the field k with a group of above determines a certain transformation of form automorphisms induced by the linear replacements of variables was considered, the contemporary theory of invariants considers arbitrary, finitely generated k-alge- Definition 4.1.1. [3] Polynomial ϕ(…, a
bra R and an algebraic group G of its k-automorphisms.
Instead of linear space V and representation ρ, an arbi- 1, …, xn) coefficients is called (relative) invari- trary affine algebraic manifold X and an algebraic ant of the form if the following equation is fulfilled for group G of its algebraic transformations (automor- all nondegenerate linear replacements of variables: phisms) are considered, so that R is a ring of regular , …), (4.1.3) functions on X and the effect of G on R is induced by the effect of G on X. Elements of R stationary with respect to G are invariants; their complete set consti- ij is the linear transformation determinant and q is a constant (weight). If q = 0, then invariant is called tutes k-algebra of RG.
absolute. Thus, the simplest examples of an invariant The definition of invariant connected with the group are the discriminant D = b2 – ac of a binary quadratic performance on the set is of interest for image recogni- (n = r = 2) form f(x, y) = ax2 + 2bxy + cy2 and the dis- tion theory. Let Γ be a group acting in the set E. This PATTERN RECOGNITION AND IMAGE ANALYSIS Vol. 13 No. 4 2003 THE JOINT USE OF IMAGE EQUIVALENCE AND IMAGE INVARIANCE of image representations. For this purpose, invariant classification was carried out in [12] by generalizing (1) (σ · τ) · x = σ · (τ · x) for every x ∈ E, σ, τ ∈ Γ; and normalizing knowledge about invariants and taking (2) ε · x = x for every x ∈ E, where ε is a unit element into account specific properties of different types of The following basic principles are suggested for σ · x will be a bijection of the set E. By vir- classification: (a) globality vs. locality, (b) transform under which the invariance is required, (c) noise sensi- into the group of bijections of the set E is a homomor- tivity, (d) information redundancy, and (e) reconstruc- Definition 4.1.2. [1] Element x ∈ E is called
One reason to use invariants as features for image -invariant or invariant if µσ(x) = x for all σ ∈ Γ.
description in recognition tasks is that invariants con- The concept of invariants is one of the most impor- tain more information about images as compared to tant in mathematics, since the study of invariants is other features. Thus, an invariant set makes it possible closely related to the classification tasks for objects of to describe images and objects of a scene in a suffi- different kinds. In essence, the goal of each mathemat- ciently compact manner. It should be mentioned, how- ical classification is to construct a certain complete sys- ever, that different invariants convey information of dif- tem of invariants (the simplest, whenever possible), that ferent types. Invariants characterizing, for example, is, a system separating any two nonequivalent objects image texture or shapes of objects in the image can be distinguished in the set of known invariants. Therefore,the use of different types of invariants depends on the 4.2. Image Description with the Help recognition task. For instance, invariant features based on moments of different types [5, 6, 14, 18] are oftenused in plane identification, recognition of ship images, One of the most commonly used ways to describe symbol recognition, scene matching, and 3D object images is their representation by feature sets. Invariants recognition from 2D projections. Some types of invari- are often used as features for image description in prac- ants are used for texture analysis and recognition. The tice; this is based on the following facts. The most following invariants can be assigned to the basic types effective methods among widely used image recogni- of invariants used in image recognition: (a) texture tion algorithms are those invariant under certain trans- invariants based on a cooccurrence matrix for a gray- formations: in the simplest case, translation, rotation, scale image [7]; (b) invariants regarding blurring, affine and scaling, and in real application tasks, changes in transformations, and changes in intensity and contrast intensity and contrast, blurring, viewpoint changes (for based on moments of different types [5, 6, 14, 18]; 3D scenes), etc., can be added to those mentioned (c) integral invariants based on integral transformations above. The easiest way to achieve this is to use charac- of Fourier- and Melline-type [19]; and (d) invariants of teristics invariant to these transforms as algorithmic geometric objects in the image [15].
parameters. It is not always possible to ensure strictinvariance of image features, since images are usuallydiscrete. However, in some cases, it is possible to con- struct characteristics that are nonstrictly invariant and noise-immune. For the cases when transforms whichnecessitate the invariance form a group, the methods Let us return to the problem of selecting the algo- for constructing the invariants were developed. More- rithm that correctly solves the image recognition task.
over, an image can be restored with a certain accuracy In order to prove the theorem on the existence of an from the fixed set of invariants of the same type. Com- algorithm that correctly solves the image recognition putational experiments and the results of solved applied task, let us lean toward the similar Zhuravlev theorem tasks show that invariants can be efficient for construct- on the correctness of algebraic closure of AEC for a pattern recognition task [2]. The results of the theorem While constructing image descriptions, a question cannot be employed immediately in the case when the arises concerning the invariants to be chosen. The prob- image is an object for recognition. There are several lem of invariant selection, as well as the number of reasons for this. Firstly, representing an image as a fea- invariants, is complicated by the fact that the known ture vector (as a standard object for recognition) usu- invariants are conceptually dissimilar in their proper- ally results in the loss of a considerable amount of ties, form, and geometric and physical interpretation. It information about the image and, as a consequence, in should be taken into account that a formalized image incorrect classification. Secondly, the existence of description depends on the recognition task at hand.
equivalence classes substantially differ the image rec- It is necessary to systematize knowledge about ognition task from the recognition task in the classical invariants and their properties for effective construction PATTERN RECOGNITION AND IMAGE ANALYSIS Vol. 13 No. 4 2003 A method based on image invariance and equiva- A(I (l), D(I)) = lence was proposed in order to eliminate these differ- ences. Here, an image is described not by an arbitrary Standard interpretation is accepted for elements αA : feature set but by a set of invariants. As was shown above, this representation is not only compact but also αA = 1, the image I belongs to the class K sufficiently informative and immune to image distor- tions. An image recognition task in terms of equivalent αA = 0, the image I does not belong to the class K classes can be reduced to the classical setup with the use of the allowable transformation notion. To show ∆, the algorithm A failed to identify whether this, a standard formulation of the recognition task, as the image I belongs to the class K well as different setups of an image recognition task, j ; j = 1, 2, …, l.
Since real recognition tasks concern not objects but their images, we consider that the entire set of imagesis somehow divided into equivalence classes. There- 5.1 Classical Setup of Pattern Recognition Task Z with, we assume that there is a correspondence between Let us briefly recall a pattern recognition task in the image equivalence classes and objects; however, we standard setup formulated by Zhuravlev [2].
will drop objects in setting up a recognition task fromhere on. Taking into account the introduced notion of Let Z(I0, S1, …, Sq, P1, …, Pl) be a recognition task, image equivalence, the image recognition task can be where I0 is allowable initial information, S1, …, Sq is a set of allowable objects described by feature vectors, 1, …, Kl is a set of classes, and P1, …, Pl is a set of i}i = 1, 2, …, q, {Kt}t = 1, 2, …, l, predicates on allowable objects, Pi = Pi(S), i = 1, 2, …, l.
The task Z is to calculate predicate values P i = 1, 2, …, q; j = 1, 2, …, p Definition 5.1.1. [2] The algorithm is correct for the
task Z if the following equation is fulfilled: is the image recognition task Z1, where I i A(I, S , …, S , P , …, P ) = α images, i = 1, 2, … q, j ith equivalence class, pi is the number of images in the i = 1, 2, …, pi; Mi = { I , I , …, I i = 1, 2, …, q are equivalence classes in the set I i K1, K2, …, Kl are the classes in the image recognition The task setup consists in the following [13]. Let the ∈ Kt”, t = 1, 2, …, l, i = 1, 2, …, q, set K of objects to be classified be given. It is known ji = 1, 2, …, pi are the predicates. Task Z1 consists in cal- that the set K can be represented as a sum of subsets culating values of the predicate P i .
information I0(K1, …, Kl) about the classes be given.
According to the approach described above, an image is a visual representation of a certain essence S(e.g., object, scene) and each scene S has a correspond- The difference between task Z2 and task Z1 is that ing set of images that differ in scale, viewpoint, illumi- each equivalence class is replaced by a single image, nation, etc. In other words, these images are equivalent class representative, with the number ni, 1 ≤ ni ≤ pi, (in terms of the definitions provided above). Let us con- where i is the number of the equivalence class. The sider the situation when each image is represented by a replacement is made by introducing the notion of The main task is to calculate predicate values Pj(I): Definition 5.3.1. An arbitrary transformation
“I ∈ Kj”; j = 1, 2, …, l from information about classes { I j } is called an allowable transformation 0(K1, …, Kl ) and from image I description D(I) = (a1, if f ( I ) and I belong to the same equivalence class for Let A be a recognition algorithm transforming train- ing information I0(K1, …, Kl) = I0(l) and object descrip-tion D(I) = (a 1, a2, …, an) into an information vector t}t = 1, 2, …, l, an image recognition task Z 2, where I , i = 1, 2, …, q, PATTERN RECOGNITION AND IMAGE ANALYSIS Vol. 13 No. 4 2003 THE JOINT USE OF IMAGE EQUIVALENCE AND IMAGE INVARIANCE ∈ Mi; K1, K2 ,…, Kl are the classes in the The following theorem is the direct generalization of Theorem 6.1. for the task Z2.
image recognition task; and Pi : “ I i ∈ Kt”; t = 1, 2, …, l, Theorem 6.2. Let allowable image transformations
i = 1, 2, …, q are the predicates. The task Z 2 consists in {f1, f2, …} form a transitive group. Then, image recog- calculating values of the predicate Pi .
nition task Z 1 can be reduced to recognition task Z 2and algebraic closure of the AEC class is correct forthe task Z 2.
This theorem establishes the conditions of existence of the correct algorithm in the image recognition taskand proves that such an algorithm can be found in alge- The main result of the research concerns the compu- tationally efficient class of recognition algorithms forestimate calculations [13]. These algorithms are basedon formalization of the concept of precedents or partial precedents; i.e., the “proximity” between partial The problem of selecting a correct algorithm for descriptions of objects already classified and the object image recognition tasks was investigated in the paper.
to be classified is analyzed. Let standard descriptions Notions of image equivalence and invariance related to for objects { S˜ }, S˜ ∈ Kj and {S'}, S' ∉ Kj be given, as this topic were examined. Different ways to define well as a method for finding the proximity of some image equivalence were considered, namely, equiva- parts of description {I( S˜ ), I(S')} and corresponding lence based on groups of transformations, equivalencedirected at the recognition task, and equivalence with parts of descriptions j = 1, 2, …, l, where S is the object respect to a metric. Examples of equivalence classes of recognition. By calculating proximity estimations were constructed for the case of equivalence definition for parts of descriptions of {I( S˜ )} and {I(S')}, I(S) and based on groups of transformations. It was shown that I(S'), respectively, one can make a generalized estima- equivalence is one if the key notions of image recogni- tion of the proximity between S and object sets S˜ and {S'} (in the simplest case, the generalized estima- The connection between image equivalence and tion equals the sum of proximity estimations between invariance was studied. The notion of an invariant both description parts). Then, the overall estimation of the in terms of its practical application in image analysis object over the class is formed from the estimation set; and processing and in terms of algebraic theory of this is the value of the function of an object’s belonging invariants was analyzed. Different definitions of an The following theorem on the existence of an algo- Based on the notion of image equivalence, the stan- rithm for estimate calculations, solving the recognition dard mathematical setup of the image recognition task task Z correctly, is proved for algebraic closure of AEC.
was modified, and the image recognition task was for- Theorem 6.1. [2] Let the natural assumptions about
mulated in terms of equivalence classes. It was proved the difference in descriptions of classes and objects that the image recognition task in the classical setup can under recognition be true for feature vectors in the rec- be modified to a reduced task that has a correct algo- ognition task Z. Then, the algebraic closure of the AEC rithm in the framework of algebraic closure of AEC class is correct for the task Z.
under certain restrictions on image transformations.
It should be noted once again that the equivalence is In our further investigations, we plan to study in not employed in the classical setup of a recognition more detail the image equivalence and relations task, which prevents the immediate application of the between image equivalence and invariance. The proven theorem on existence algorithm to correct obtained results will be applied to automated diagnos- tics of lymphatic system tumors from hematologicalspecimens.
The task Z1 differs from Z in that it employs image equivalence classes in an explicit form. In order toreduce an image recognition task Z1 to a standard rec- ognition task Z, it is necessary to move from classifica- 1. Djodonne, G. Kerrol. Theory of invariants. Old and New.
tion of object groups to classification of a single object.
(1971) “Mercury-PRESS” Publishing House, Chere- The task Z2 is distinguished from Z1 by the presence of povets, 2000 (in Russian). Translated from: Dieudonne allowable transformations that do not move an image J., La theorie des invariants au XIX siecle, Seminaire out of the equivalence class; it is possible to operate Bourbaki, 1970/71, Berlin, Springer, 1972.
with a single object, a representative of the equivalence 2. Zhuravlev, Yu.I., An Algebraic Approach to Recognition class, under certain restrictions on allowable transfor- or Classification Problems, Pattern Recognit. Image Anal. 1998, vol. 8, No. 1, pp. 59–100.
PATTERN RECOGNITION AND IMAGE ANALYSIS Vol. 13 No. 4 2003 3. Matematicheskaya Entsiklopediya (Mathematical Ency- ysis and Machine Intelligence, 1990, vol. 12, no. 5, clopedia), Vinogradov, I.M., Ed., vol. 2, Moscow: Sov.
15. Mundy, J.L. and Zisserman, A., Towards a New Framework 4. Shafarevich, I.P., Osnovnye ponyatiya algebty (Basic for Vision: Geometric Invariance in Computer Vision, Notions of Algebra), Izhevsk: NITS Regular and Chaotic Mundy, J. and Zisserman, A., Eds., 1992, pp. 1–39.
16. Ritter, G.X. and Wilson, J.N. Handbook of Computer 5. Flusser, J. and Suk, T., Degraded Image Analysis: An Vision Algorithms in Image Algebra, CRC Press Inc., Invariant Approach, IEEE Trans on Pattern Analysis and Machine Intelligence, 1998, vol. 20, no. 6, pp. 590–603.
17. Serra, J. Image Analysis and Mathematical Morphology, 6. Flusser, J. and Suk, T., Blur and Affine Moment Invari- ants, Proc. 16th Int. Conf. on Pattern Recognition 18. The, C.-H. and Chin Roland, T., On Image Analysis by (ICPR2002), Quebec, 2002, vol. 4, pp.339–342.
the Methods of Moments, IEEE Trans. on Pattern Anal- 7. Fu, K.-S. and Mui, J.K., Automated Classification of ysis and Machine Intelligence, 1988, vol. 10, no. 4, Nucleated Blood Cells Using a Binary Tree Classifier, IEEE Trans. on Pattern Analysis and Machine Intelli- 19. Wood, J., Invariant Pattern Recognition: A Review, Pat- gence, 1980 vol. PAMI-2, no. 5, pp. 429–436.
tern Recognition, 1996, vol. 29, no. 1, pp. 1–17.
8. Grenander, U., General Pattern Theory: A Mathematical 20. Zhuravlev, Yu.I., Algebraic Methods in Recognition and Study of Regular Structures, Oxford: Clarendon, 1993.
Classification Problems, Pattern Recognit. Image Anal., 9. Gurevich, I.B., The Descriptive Framework for an Image Recognition Problem, Proc. 6th Scandinavian Conf. on 21. Zhuravlev, Yu.I. and Gurevitch, I.B., Pattern Recognition Image Analysis, Oulu, 1989, vol.1 pp. 220–227.
and Image Recognition, Pattern Recognit. Image Anal., 10. Gurevich, I.B., Descriptive Technique for Image Description, Representation, and Recognition, PatternRecognit. Image Anal., 1991, vol. 1, no. 1, pp. 50–53.
11. Gurevich, I.B. and Smetanin, Y.G., On the Equivalence of Images in Pattern Recognition Problems, Proc. 12th Igor B. Gurevich. (See p. 568).
Scandinavian Conf. on Image Analysis, Bergen, 2001,pp. 679–685.
12. Gurevich, I.B., Jernova, I.A., and Smetanin, Y.G. A Irina A. Jernova. Born 1981.
Method of Image Recognition Based on the Fusion of Reduced Invariant Representations: Mathematical Sub- stantiation, Proc. 16th Int. Conf. on Pattern Recognition (ICPR2002), Quebec, 2002, vol.3, pp. 391–394.
sity, Moscow, in 2003. Since 2001,works at the Scientific Council on 13. Gurevich, I.B. and Zhuravlev, Y.I. An Image Algebra Accepting Image Models and Image Transforms, Proc. 7th Int. Workshop “Vision, Modeling, and Visualization 2002” (VMV2002), Erlangen, Greiner, G., Niemann, H., et al., IOS Press, B.V. Amsterdam, Infix, Akademische Ver- lagsgesellschaft, Aka GMBH, Berlin, 2002, pp. 21–26.
14. Khotanzad, A. and Hong, Y.H. Invariant Image Recogni- analysis, and recognition. Member of the Russian Associa- tion by Zernike Moments, IEEE Trans. on Pattern Anal- PATTERN RECOGNITION AND IMAGE ANALYSIS Vol. 13 No. 4 2003

Source: http://www.ccas.ru/tc16/PatRec4_03-570.pdf