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 Russiae-mail: igourevi@ccas.ru; jer_irina@mail.ruAbstract—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) ∈ Ff2(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 operatorB.
-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 ϕ : FF'. 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 groupG.
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 Pi = 1, 2, …, q; j = 1, 2, …, pDefinition 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 iA(I, S , …, S , P , …, P ) = α
images, i = 1, 2, … q, jith equivalence class, pi is the number of images in the
i = 1, 2, …, pi; Mi = { I , I , …, Ii = 1, 2, …, q are equivalence classes in the set I iK1, 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. ImageAnal. 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 andMachine 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. 12thIgor 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 Visualization2002” (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

CHROMOSOMAL ABERRATIONS INDUCED BY AMBIENT AIR CHROMOSOMAL ABERRATIONS BY FLUORESCENCE IN SITU HYBRIDIZATION (FISH) – BIOMARKER OF EXPOSURE TO CARCINOGENIC PAHS Olena Beskid, Blanka Binkova, Zdík Dusek, Pavel Rössner,1 Ivan Kalina,2 Todor A. Popov,3 Peter B. Farmer,4 Radim J.Srám1 ABSTRACT The fluorescence in situ hybridisation (FISH) technique with whole chromosome painting fo

BASD Strategy Meeting Paris, 9-10 October, 2001 THE GLOBALISATION IMPERATIVE Reuel Khoza On behalf of Eskom and the Business Co-ordinating Forum of South Africa, I wish to thank, the BASD Steering Committee Chair, Mark Moody Stuart for hosting this meeting. United Nations Secretary-General, Kofi Annan has stated that “We have to choose between a global market driven only by calculation