72
Patterns and Pattern Classes in
Object Recognition for DIP
and its implementation in MATLAB
© Dr. Dafda
❖ Image processing main steps:
6. Types of Digital Image Processing ?
(1) Low level processing: Primitive operations such as noise reduction, image
sharpening, enhancement etc. Input and output are images.
(2) Mid level processing: Image segmentation, classification of individual objects etc.
Here input are images but output are attributes of images for e.g. edges of image.
(3) High level processing: It involves making sense of recognized objects and
performing functions associated with visions. For e.g. Automatic character
recognition, military recognition, autonomous navigation etc.
❖ Preview: Object Recognition
• The automatic recognition of objects or patterns is one of very important image analysis tasks.
An object recognition system is like a computer program that tries to identify things in
pictures of the real world.
• It does this by using models of objects that it already knows about. This is a tough job because
it's not easy to teach computers to do this. Humans, on the other hand, can recognize objects
in pictures without any effort and really quickly.
Object Recognition
Methods Central idea: Learning from sample patterns
pattern arrangements
Decision-theoretic methods Structural methods
deal with patterns best described by qualitative descriptors
deals with patterns described using quantitative (symbolic information), such as the relational descriptors for
descriptors and have patterns arranged in numeric repetitive structures, e.g. staircase). Here the Patterns are
vectors, such as length, area, and texture. arranged in strings or trees.
❖ Patterns and Pattern Classes:
• A pattern is an arrangement of descriptors (or features).
• A pattern class is a family of patterns that share some common properties. Pattern classes are
denoted w1, w2, . . . , wN where N is the number of classes.
• Pattern recognition by machine involves techniques for assigning patterns to their respective
classes automatically and with as little human intervention as possible.
• The object or pattern recognition task consists of two steps:
➢ feature selection (extraction)
➢ matching (classification)
There are three common pattern arrangements used in practice:
• Numeric pattern vectors (for quantitative descriptions)
𝑥1
𝑥 = 𝑥2
[⋮]
𝑥𝑛
• Strings and trees (for qualitative(structural) descriptions)
x = abababa….
❖ Numeric Pattern vectors (Decision-theoretic methods):
• Fisher 1936, performed Recognition of three types of Iris flowers(Iris serosa,
versicolor and virginica by the lengths[x1] and widths[x2] of their petals.
• Here 3 pattern classes are w1, w2 and w3 corresponding to Iris setosa, versicolor
and virginica. Also there are variations between and within classes.
• Class separability depends strongly on the choice of descriptors.
❖ Numeric Pattern vectors (Decision-theoretic methods):
• Instead of using “raw” sampled signatures, a more common approach is to compute some
function, xi=g((r(θi)) of the signature samples and use them to form vectors.
• These vectors become points in n-dimensional Euclidean space, and pattern classes can be
imagined to be ‘clouds’ in n dimensions.
• Instead of using signatures, other shape characteristics can be employed (e.g. statistical
moments).
• The choice of descriptors has a profound role in the recognition performance.
❖ String descriptors (Structural methods):
• In some applications, patterns are best described by structural relationships. eg: fingerprint
recognition.
• Primitive components that describe fingerprint ridge properties are:
➢ Interrelationships of print features (minutiae).
✓ Abrupt endings, branching, merging, disconnected segments,…
➢ Relative sizes and locations of print features
• For example: Staircase pattern described by a head-to-tail structural relationship. The rule
allows only alternating pattern and It excludes other types of structures but other rules may be
defined.
❖ Tree descriptors (Structural methods):
• A more powerful approach is the use of tree
descriptors. Basically most hierarchical ordering
schemes lead to tree structures.
• In the satellite image example, the structural
relationship is defined as: “composed of
downtown area and surrounding residential area.
Thank You
73
Recognition Based on Decision-Theoretic
Methods and Matching in Object Recognition
for DIP and its implementation in MATLAB
© Dr. Dafda
❖ Preview: Object Recognition
• The automatic recognition of objects or patterns is one of very important image analysis tasks.
An object recognition system is like a computer program that tries to identify things in
pictures of the real world.
• It does this by using models of objects that it already knows about. This is a tough job because
it's not easy to teach computers to do this. Humans, on the other hand, can recognize objects
in pictures without any effort and really quickly.
Object Recognition
Methods Central idea: Learning from sample patterns
pattern arrangements
Decision-theoretic methods Structural methods
deal with patterns best described by qualitative descriptors
deals with patterns described using quantitative (symbolic information), such as the relational descriptors for
descriptors and have patterns arranged in numeric repetitive structures, e.g. staircase). Here the Patterns are
vectors, such as length, area, and texture. arranged in strings or trees.
❖ Decision-theoretic methods:
• The basic concept in decision-theoretic methods is the idea of pattern matching
based on measures of distance between pattern vectors. Where it includes decision
(discriminant) functions and decision boundaries.
• Let x=[x1, x2,…, xn]T represent a pattern vector.
• For W pattern classes ω1, ω2,…, ωW, the basic problem is to find W decision
functions d1(x), d2(x),…, dW (x) with the property that if x belongs to class ωi:
di(x) > dj(x) for j = 1,2,..., W; j # i
• In other words, an unknown pattern x is said to belong to the ith pattern class if
upon substitution of x into all decision functions, di(x) yields the largest numerical
value. We want to classify x, which is a pattern. We are given a finite set of classes
of objects. We want to categorize the pattern x into one of the classes. To do so,
we apply x to all decision functions, and categorize x to the class of best fit.
❖ Decision-theoretic methods (cont.):
• The decision boundary separating class ωi from class ωj is given by the values of x
for which di (x) = dj (x) or
• If x belongs to class ωi:
• If x belongs to class ωj:
❖ Types of Decision-theoretic methods:
• Matching: an unknown pattern is assigned to the class to which it is closest with
respect to a metric.
– Minimum distance classifier (Computes the Euclidean distance between the
unknown pattern and each of the prototype vectors).
– Correlation (It can be directly formulated in terms of images)
• Optimum statistical classifiers (A probabilistic approach to recognition)
• Neural networks (nonlinear computing elements (called neurons) organized as
networks)
❖ Matching and Minimum distance classifier:
• Matching is an important concept in computer vision and object recognition. Images of the
same item can be taken with any angle and any lighting condition and any scale. The simplest
approach of matching is the minimum distance classifier. Matching represent each class by a
prototype pattern vector. The prototype of each pattern class is the mean vector:
• Using the Euclidean distance as a measure of closeness:
• We assign x to class ωj if Dj(x) is the smallest distance. That is, the smallest distance implies the
best match in this formulation.
• It is easy to show that selecting the smallest distance is equivalent to evaluating the functions:
and assigning x to class ωj if dj(x) yields the largest numerical value. This formulation agrees
with the concept of a decision function.
❖ Minimum distance classifier(cont.):
• The decision boundary between classes ωi
and ωj is given by:
• The surface given by above equation is the
perpendicular bisector of the line segment
joining mi and mj.
• For n=2, the perpendicular bisector is a line, for
n=3 it is a plane and for n>3 it is called a
hyperplane. The two classes, Iris versicolor and Substitution of any pattern vector from class ω1 would
Iris setosa, denoted ω1 and ω2, respectively, yield d12(x) > 0. Conversely, any pattern from class ω2
have sample mean vectors m1 = (4.3, 1.3)T and would yield d12(x) < 0. In other words, given an
m2 = (1.5, 0.3)T. The decision functions are unknown pattern belonging to one of these two classes,
sign of d12(x) to one of these two classes, sign of d12(x)
would be sufficient to determine pattern's class
membership.
❖ Minimum distance classifier (cont.):
• In practice, the classifier works well when the
distance between means is large compared to the
spread of each class. This occurs seldom unless the
system designer controls the nature of the input.
• An example is the recognition of characters on bank
checks. - American Banker’s Association E-13B
font character set.
• Characters are purposely designed on a 9x7 grid to
facilitate their reading. Also the characters are
stylized to maximize the difference between them.
• The font was designed to be readable by humans,
but the overriding purpose was that the characters
should be readable by machine, quickly and with
high accuracy.
• The waveforms (signatures) are different for each
character.
Thank You
74
Structural Methods in Object Recognition
for DIP and its implementation in MATLAB
© Dr. Dafda
❖ Preview: Object Recognition
• The automatic recognition of objects or patterns is one of very important image analysis tasks.
An object recognition system is like a computer program that tries to identify things in
pictures of the real world.
• It does this by using models of objects that it already knows about. This is a tough job because
it's not easy to teach computers to do this. Humans, on the other hand, can recognize objects
in pictures without any effort and really quickly.
Object Recognition
Methods Central idea: Learning from sample patterns
pattern arrangements
Decision-theoretic methods Structural methods
deal with patterns best described by qualitative descriptors
deals with patterns described using quantitative (symbolic information), such as the relational descriptors for
descriptors and have patterns arranged in numeric repetitive structures, e.g. staircase). Here the Patterns are
vectors, such as length, area, and texture. arranged in strings or trees.
❖ Structural Methods :
• The techniques discussed in decision theoretic methods deal with
patterns quantitatively and largely ignore any structural relationships
inherent in a pattern's shape. That is Decision theoretic methods focus on
numbers and don't pay much attention to the way things are arranged in a
pattern.
• On the other hand, structural methods are all about recognizing patterns by
paying close attention to how things are arranged (qualitatively) or connected
in the pattern. The structural methods discussed here, however, seek to
achieve pattern recognition by capitalizing precisely on these types of
relationships.
❖ Types of Structural Methods :
• Matching Shape Numbers:
Matching Shape Numbers is a structural method in object recognition that
involves comparing objects based on their first difference chain code
representations to determine if they match.
• String Matching
String Matching is a structural method in object recognition that involves
comparing the object's boundary encoding as a string with a reference template to
determine if they match.
❖ Matching Shape Numbers :
• The degree of similarity, k,
between two shapes is defined as the
largest order for which their shape
numbers still coincide.
− Reminder: The shape number
of a boundary is the first difference of
smallest magnitude of its chain code
(invariance to rotation).
− The order n of a shape number
is defined as the number of digits in its
representation.
• Examples. All closed shapes of
order n=4, 6 and 8.
• First differences are computed by
treating the chain as a circular
sequence.
❖ Matching Shape Numbers (cont.) :
• Let a and b denote two closed shapes which are represented by 4-directional chain codes and
s(a) and s(b) their shape numbers.
• The shapes have a degree of similarity, k, if:
• This means that the first k digits should be equal.
• The subscript indicates the order. For 4-directional chain codes, the minimum order for a closed
boundary is 4.
• Alternatively, the distance between two shapes a and b is defined as the inverse of their degree of
similarity:
• It satisfies the properties:
❖ Matching Shape Numbers :
• Suppose that we have a shape f and want to
find its closest match in a set of five other
shapes (a, b, c, d and e), as shown in Fig.(a).
• Suppose that the shapes are identical up to
degree 8, with the exception of shape a
whose degree of similarity with respect to
all other shapes is 6. Shape d has degree of
similarity 8 with respect to all others, and so
on.
• Shapes f and c match uniquely, having a
higher degree of similarity than any other
two shapes.
• If a had been an unknown shape, all we could
have said using this method is that a was
similar to the other five shapes with degree of
similarity 6.
❖ String matching :
• Suppose that two region boundaries, a and b,
are coded into strings denoted by a1a2a3 …an
and b1b2b3 …bm.
• Let p represent the number of matches
between the two strings.
− A match at the kth position occurs if ak = bk.
• The number of symbols that do not match is:
• A simple measure of similarity is:
Thank You
