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, GSP1, 119991 Russia
email: 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 establishment 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 considerations 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. 020100182, 030706056; 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 timeconsuming (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
f1
R 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 coordinates
f(ρ, θ), by replacing the variables
x = ρcosθ,
y =
ρsinθ. Let
g be a rotation trough 2π/3 angle,
g–1 a rotation 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 observation 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
f1
R f2 ⇒
f2
R 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 representative, 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
ndimensional 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
ldimensional information vector on the basis of an
models can be constructed on the basis of invariant fea
ndimensional 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
realvalued 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
ndimensional feature vector, the
ldimensional vector
based on the construction of image invariants.
of estimations for classes, and the
ldimensional information 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 homomorphism ϕ :
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 factorring 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 ∆ = 3
b2c2 + 6abcd – 4
b3
d – 4
ac3 –
a2
d2 of a
for practical purposes. In many tasks of image analysis
ternary (
n = 2,
r = 3) form
f(
x,
y) =
ax3 + 3
bx2
y + 3
cxy2 +
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 socalled 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 finitedimensional 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 socalled
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
kalge
Definition 4.1.1. [3] Polynomial ϕ(…,
a
bra
R and an algebraic group
G of its
kautomorphisms.
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
kalgebra 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 + 2
bxy +
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 Mellinetype [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
noiseimmune. 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 description
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) “MercuryPRESS” 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. PAMI2, 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_03570.pdf
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, 910 October, 2001 THE GLOBALISATION IMPERATIVE Reuel Khoza On behalf of Eskom and the Business Coordinating Forum of South Africa, I wish to thank, the BASD Steering Committee Chair, Mark Moody Stuart for hosting this meeting. United Nations SecretaryGeneral, Kofi Annan has stated that “We have to choose between a global market driven only by calculation