DIGITAL IMAGE PROCESSING
Download
Report
Transcript DIGITAL IMAGE PROCESSING
DIGITAL IMAGE
PROCESSING
Instructors:
Dr J. Shanbehzadeh
[email protected]
M.Kachooeian
[email protected]
DIGITAL IMAGE
PROCESSING
Instructors:
Dr J. Shanbehzadeh
[email protected]
M.Kachooeian
[email protected]
Road map of chapter 11
3.1
3.2
3.3
3.4
3.5
Use
of Principal Components
Regional
Representation
Boundary
Descriptors
RelationalDescriptors
Descriptors
for Description
11.1- Representation
11.2- Boundary Descriptors
11.3- Regional Descriptors
11.4- Use of Principal Components for Description
11.5 - Relational Descriptors
11.1 Representation
Representation
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Chain Codes
Polygonal Approximations
Signatures
Boundary Segments
Skeletons
Chain Codes
• Chain codes are used to represent a boundary by a
connected sequence of straight-line segments of specified
length and direction.
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
•
a chain code can be generated by following a boundary (in
a clockwise direction) and assigning a direction to the
segments connecting every pair of pixels.
• This method generally is unacceptable for two principal
reasons:
The resulting chain tends to be quite long
any small disturbances along the boundary due to noise or
imperfect segmentation cause changes in the code that may
not be related to the principal shape features of the
boundary.
Chain Codes
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Chain Codes
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
• The chain code of a boundary depends on the starting point.It can
be normalized with respect to the starting point.
• We simply treat the chain code as a circular sequence of direction
numbers and redefine the starting point so that the resulting
sequence of numbers forms an integer of minimum magnitude.
We can normalize also for rotation (in angles that are integer
multiples of the directions in Fig. 11.3) by using the firs
difference of the chain code instead of the code itself.
Chain Codes
Normalization For Rotation
This difference is obtained by counting the number of direction
changes that separate two adjacent elements of the code.
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Example
Chain code is 10103322
Normalized with first difference 3133030
If we treat the code as a circular sequence to normalize with respec
to the starting point,the result is 33133030.
Chain Codes
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Chain Codes
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
• The 8-directional Freeman chain code :
00006066666666444444242222202202
• The integer of minimum magnitude of the code:
00006066666666444444242222202202
• The first difference of either code is
00062600000006000006260000620626
• Using any of these codes to represent the boundary results in a
significant reduction in the amount of data needed to store the
boundary. In addition, keep in mind that the subsampled
boundary can be recovered from any of the preceding codes.
Representation
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Chain Codes
Polygonal Approximations
Signatures
Boundary Segments
Skeletons
Polygonal Approximations
• A digital boundary can be approximated with arbitrary
accuracy by a polygon.
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
• Polygonal approximations: to represent a boundary by
straight line segments, and a closed path becomes a
polygon.
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
• to be exact,we should have:
Number of segments of polygon=number of points in
boundary
Polygonal Approximations
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Polygonal Approximations
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
• The size of the cells determines the accuracy of the
polygonal approximation.
• if the size of each (square) cell corresponds to a pixel in
the boundary, error in each cell between the boundary
and the MPP approximation at most would be 2𝑑,
where d is the minimum possible distance between
pixels.
• The objective is to use the largest possible cell size
acceptable in a given application
producing MPPs with the fewest number of vertices
Polygonal Approximations
Concave vertex
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Convex
vertex
Polygonal Approximations
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
1. The MPP bounded by a simply connected cellular complex
is not self intersecting.
2. Every convex vertex of the MPP is a W vertex, but not
every W vertex of a boundary is a vertex of the MPP
3. Every mirrored concave vertex of the MPP is a B vertex,
but not every B vertex of a boundary is a vertex of the MPP
4. All B vertices are on or outside the MPR and all W vertices
are on or in side the MPP
5. The uppermost, leftmost vertex in a sequence of vertices
contained in a cellular complex is always a W vertex of the
MPP
Polygonal Approximations
• orientation of triplets of points:
the triplet of points, (a, b, c)
a = (x1, y1), b = (x2,y2), and c = (x3,y3)
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Polygonal Approximations
Algorithm:
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
• form a list whose rows are the coordinates of each
vertex and an additional element denoting whether the
vertex is W or B.
• V0 the first vertex be the uppermost leftmost
• assume that vertices are arranged in the
counterclockwise direction.
• WC crawls along convex (W) vertices
• Bc crawls along mirrored concave (B) vertices
• VL last MPP vertex found
• Vk current vertex being examined.
Polygonal Approximations
• SetWC = BC = V0
(a) Vk lies to the positive side of the line through pair (VL, WC);
that is, sgn(VL, WC, Vk) > 0.
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
the next MPP vertex is WC, and we let VL = WC; then we
reinitialize the algorithm by setting WC = BC = VL, and continue
with the next vertex left
(b) Vk lies on the negative side of the line though pair (VL, WC)
or is collinear with it; that is sgn(VL, WC, Vk) 0. At the same
time, VK lies to the positive
side of the line through (VL, BC) or is collinear with it; that is,
sgn(VL,BC, Vk) = 0.
VL becomes a candidate MPP vertex. In this case, we set WC =
Vk if Vk is convex (i.e., it is a W vertex); otherwise we set BC =
Vk.
We then continue with the next vertex in the list.
Polygonal Approximations
(c) Vk lies on the negative side of the line though pair (VL,
Bc): that is, sgn(VL, BC, VK) < 0.
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
the next MPP vertex is BC and we let VL = BC; then we
reinitialize the algorithm by setting WC = BC = VL and
continue with the next vertex after VL
• Algorithm terminates when it reaches the first vertex
again, and thus has processed all the vertices in the
polygon. The VL vertices found by the algorithm are
the vertices of the MPP
Polygonal Approximations
Example
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
• letting WC = BC = V0 = VL = (1.4).
The next vertex is V1 = (2, 3).
sgn(VL, WC, V1) = 0 and sgn(VL, BC, V1) = 0
condition (b) holds.
We let BC = V1 = (2, 3) and WC is at (1, 4),
VL is still at (1,4) because no new MPP-vertex was found.
Polygonal Approximations
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
• Next, we look at V2 = (3, 3).
sgn(VL, WC, V2) = 0, and sgn(VL, BC, V2) = 1
condition (b) of the algorithm holds again.
Because V2 is a W (convex) vertex , we let WC = V2 = (3, 3).
At this stage, the crawlers are at WC = (3,3) and BC = (2,3);
VL remains un- changed.
Polygonal Approximations
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
• If we we examine V5 = (7,1) ,we’ll have:
sgn(VL, WC, V5) = 9
so condition (a) holds
set VL = WC = (4, 1). Because a new MPP
vertex was found, we reinitialize the algorithm
by setting WC = BC = VL and start again with
the next vertex being the vertex after the newly
found VL. The next vertex is V5, so we visit it
again.
Polygonal Approximations
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Continuing as above with this and the remaining
vertices yields the MPP vertices in Fig below.
Polygonal Approximations
11.1Representation
11.2- Boundary
Descriptors
11,3- Regional
Descriptors
11.4- Use of
Principal
Components for
Description
11.5 - Relational
Descriptors
Representation
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Chain Codes
Polygonal Approximations
Signatures
Boundary Segments
Skeletons
Signatures
•
represents a shape by a one dimensional function derived from shape
boundary point.
• 1-D function is easier to describe than the original 2-D boundary.
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Signatures
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Signatures
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
• Problem: Signatures generated by this approach are
invariant to translation, but they do depend on rotation.
• Solution for rotation: We can normalize with respect
to rotation .
find a way to select the same starting point to generate the
signature, regardless of the shape’s orientation.
One way to do so is to select the starting point as the point
farthest
from the centroid, assuming that this point is
unique for each shape of interest.
Signatures
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
• Solution for scaling: We can normalize with respect to
scaling.
Scale all functions so that they always span the same range
of values, e.g., [0, 1].
Advantage: simplicity
disadvantage :depends on only two values the minimum
and maximum.
Representation
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Chain Codes
Polygonal Approximations
Signatures
Boundary Segments
Skeletons
Boundary Segments
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
• Decomposition reduces the boundary’s complexity and
thus simplifies the description process.
• In this case, use of the convex hull of the region
enclosed by the boundary is a powerful tool for robust
decomposition of the boundary.
Boundary Segments
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
• convex hull H of an arbitrary set S is the smallest
convex set containing S.
• The set difference H - S is called the convex deficiency
D of the set S. The region boundary can be partitioned
by following the contour of S and marking the points at
which a transition is made into or out of a component of
the convex deficiency.
Convex deficiency
Boundary Segments
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
S = dbabcbabdbabcbab
Boundary Segments
• Another use of convex deficiency is to recognize human actions.
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Boundary Segments
• Problem: digital boundaries tend to be irregular .
•
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
These effects usually result in convex deficiencies
that have small, meaningless components scattered
randomly through-out the boundary.
• Solution: smooth a boundary prior to partitioning.
traverse the boundary and replace the coordinates of
each pixel by the average coordinates of k of its
neighbors along the boundary.
• works for small irregularities, but it is timeconsuming and difficult to control
• Large values of k excessive smoothing
• small values of k insufficient in some segments of
the boundary
Boundary Segments
• Better solution: use a polygonal approximation prior to
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
finding the convex deficiency of a region. Most digital
boundaries of interest are simple .Graham and Yao [1983]
give an algorithm for finding the convex hull of such
polygons.
Representation
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Chain Codes
Polygonal Approximations
Signatures
Boundary Segments
Skeletons
Skeletons
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
• Represent structural shape of a plane region reduce it
to a graph.
• Use skeletonizing algorithm via a thinning
• Problem of some skeletonizing algorithms:
the procedure made no provisions for keeping the skeleton
connected.
• The skeleton of a region may be defined via the medial
axis transformation (MAT) proposed by Blum [1967].
Skeletons
medial axis is the locus of centers of maximal disks that fit
within the shape.
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Skeletons
• Difference between MAT and skeleton
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Skeletons
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
• The MAT of a region R with border B:
1. For each point p in R, find its closest neighbor in B.
2. If p has more than one such neighbor, it is said to
belong to the skeleton of R.
Problem: direct implementation of this definition is
expensive computationally.
Implementation involves calculating the distance from
every interior point to every point on the boundary of a
region.
Skeletons
Solution: thinning algorithms that iteratively delete
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
boundary points of a region subject to the constraints that
deletion of these points
(1) does not remove end points
(2) does not break connectivity
(3) does not cause excessive erosion of the region.
Skeletons
Algorithm for thinning binary regions
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
Step 1 flags a contour point p, for deletion if
the following conditions are satisfied:
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
•
N(p1) is the number of nonzero neighbors
of p1
• T(p1) is the number of 0-1 transitions in the
ordered sequence p2, p3, ,..., p8. p9, p2.
Skeletons
Example
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
0
1
1
0
p1
0
1
0
1
N(p1) = 4 and T(p1) = 3
Skeletons
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
Step 2 conditions (a) and (b) remain the same, but
conditions (c) and (d) are changed to
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Algorithm:
1.Apply Step 1 to every border pixel in the binary region .
2. if all conditions (a)-(d) are satisfied the point is flagged
for deletion. 3.Delete flagged points (changed to 0).
4.Apply step 2 to the resulting data
Skeletons
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
11.2 Boundary Descriptors
Boundary Descriptors
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Some Simple Descriptors
Shape Numbers
Fourier Descriptors
Statistical Moments
Some Simple Descriptors
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
• There are several simple geometric measures that can
be useful for describing a boundary.
• The length of a boundary: the number of pixels
along a boundary gives a rough approximation of its
length.
• Curvature: the rate of change of slope
• To measure a curvature accurately at a point in a
digital boundary is difficult
• The difference between the slops of adjacent
boundary segments is used as a descriptor of
curvature at the point of intersection of segments
Boundary Descriptors
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Some Simple Descriptors
Shape Numbers
Fourier Descriptors
Statistical Moments
Shape Numbers
First
difference
• The shape number of a boundary is defined as the first
difference of smallest magnitude.
• The order n of a shape number is defined as the number of
digits in its representation.
Shape Numbers
Shape Numbers
Boundary Descriptors
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Some Simple Descriptors
Shape Numbers
Fourier Descriptors
Statistical Moments
Fourier Descriptors
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
• This is a way of using the Fourier transform to analyze
the shape of a boundary.
• The x-y coordinates of the boundary are treated as
the real and imaginary parts of a complex number.
• Then the list of coordinates is Fourier transformed
using the DFT (chapter 4).
• The Fourier coefficients are called the Fourier
descriptors.
• The basic shape of the region is determined by the
first several coefficients, which represent lower
frequencies.
• Higher frequency terms provide information on the
fine detail of the boundary.
Fourier Descriptors
Fourier descriptor: view a coordinate (x,y) as a complex number
(x = real part and y = imaginary part) then apply the Fourier
transform to a sequence of boundary points.
Let s(k) be a coordinate
of a boundary point k :
Fourier descriptor :
s(k ) x(k ) jy(k )
1
a (u )
K
K 1
2uk / K
s
(
k
)
e
k 0
Reconstruction formula
Boundary
points
1 K 1
s(k ) a (u )e2uk / K
K k 0
Fourier Descriptors
1
ˆs (k )
K
P 1
2uk / K
a
(
u
)
e
k 0
Fourier Descriptors
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Some properties of Fourier descriptors
Boundary Descriptors
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Some Simple Descriptors
Shape Numbers
Fourier Descriptors
Statistical Moments
Statistical Moments
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
• Moments are statistical measures of data.
• They come in integer orders.
• Order 0 is just the number of points in the data.
• Order 1 is the sum and is used to find the average.
• Order 2 is related to the variance, and order 3 to the
skew of the data.
• Higher orders can also be used, but don’t have
simple meanings.
Statistical Moments
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
• Let r be a random variable, and g(ri) be normalized (as
the probability of value ri occurring), then the moments
are
K 1
n (r ) (ri m) n g (ri )
k 0
K 1
where m ri g (ri )
i 0
11.3 Regional Descriptors
Regional Descriptors
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Some Simple Descriptors
Topological Descriptors
Texture
Moments of Two-Dimensional Functions
Some Simple Descriptors
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
• Some simple descriptors
• The area of a region: the number of pixels in the
region
• The perimeter of a region: the length of its boundary
• The compactness of a region: (perimeter)2/area
• The mean and median of the gray levels
• The minimum and maximum gray-level values
• The number of pixels with values above and below the
mean
Some Simple
Descriptors
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Regional Descriptors
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Some Simple Descriptors
Topological Descriptors
Texture
Moments of Two-Dimensional Functions
Topological Descriptors
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
Topological property 1:
the number of holes (H)
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Topological property 2:
the number of connected
components (C)
Topological Descriptors
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
Topological property 3:
Euler number: the number of connected components
subtract the number of holes
E=C-H
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
E=0
E= -1
Topological Descriptors
11.1- Representation
11.2- Boundary
Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for
Description
11.5 - Relational
Descriptors
Topological
property 4:
the largest
connected
component.
Regional Descriptors
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Some Simple Descriptors
Topological Descriptors
Texture
Moments of Two-Dimensional Functions
Texture
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
• Texture is usually defined as the smoothness or
roughness of a surface.
• In computer vision, it is the visual appearance of the
uniformity or lack of uniformity of brightness and color.
• There are two types of texture: random and regular.
• Random texture cannot be exactly described by
words or equations; it must be described statistically.
The surface of a pile of dirt or rocks of many sizes
would be random.
• Regular texture can be described by words or
equations or repeating pattern primitives. Clothes
are frequently made with regularly repeating
patterns.
• Random texture is analyzed by statistical methods.
• Regular texture is analyzed by structural or spectral
(Fourier) methods.
Texture
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Statistical Approaches
• Let z be a random variable denoting gray levels and let p(zi),
i=0,1,…,L-1, be the corresponding histogram, where L is the
number of distinct gray levels.
• The nth moment of z:
L 1
n ( z ) ( zi m) p( zi ) where m zi p( zi )
L 1
n
k 0
• The measure R:
• The uniformity:
i 0
R 1
1
1 2 ( z)
L 1
U p 2 ( zi )
i 0
• The average entropy:
L 1
e p( zi ) log 2 p( zi )
i 0
Statistical Approaches
Smooth
Coarse
Regular
Statistical Approaches
• Structural concepts:
• Suppose that we have a rule of the
form S→aS, which indicates that
the symbol S may be rewritten as
aS.
• If a represents a circle [Fig.
11.23(a)] and the meaning of
“circle to the right” is assigned to a
string of the form aaaa… [Fig.
11.23(b)] .
Spectral Approaches
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Spectral Approaches
Regional Descriptors
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Some Simple Descriptors
Topological Descriptors
Texture
Moments of Two-Dimensional Functions
Moments of Two-Dimensional
Functions
• For a 2-D continuous function f(x,y), the moment of order (p+q) is defined as
mpq
x y f ( x, y)dxdy for p, q 1,2,3,...
p
q
• The central moments are defined as
pq
( x x ) ( y y ) f ( x, y)dxdy
p
m10
m01
where x
and y
m00
m00
q
Moments of Two-Dimensional
Functions
• If f(x,y) is a digital image, then
pq ( x x ) p ( y y ) q f ( x, y )
x of yorder up to 3 are
• The central moments
00 ( x x ) 0 ( y y ) 0 f ( x, y ) f ( x, y ) m00
x
y
x
y
m10
(m00 ) 0
m00
x
y
m01
0
1
01 ( x x ) ( y y ) f ( x, y ) m01
(m00 ) 0
m00
x
y
m10m01
1
1
11 ( x x ) ( y y ) f ( x, y ) m11
m00
x
y
10 ( x x )1 ( y y ) 0 f ( x, y ) m10
m11 x m01 m11 ym10
Moments of Two-Dimensional
Functions
• The central moments of order up to 3 are
20 ( x x ) 2 ( y y ) 0 f ( x, y ) m20 x m10
x
y
x
y
02 ( x x ) 0 ( y y ) 2 f ( x, y ) m02 ym01
21 ( x x ) 2 ( y y )1 f ( x, y ) m21 2 x m11 ym20 2 x m01
x
y
x
y
12 ( x x )1 ( y y ) 2 f ( x, y ) m12 2 ym11 x m02 2 ym10
30 ( x x )3 ( y y ) 0 f ( x, y ) m30 3x m20 2 x 2 m10
x
y
03 ( x x ) 0 ( y y )3 f ( x, y ) m03 3 ym02 2 y 2 m01
x
y
Moments of Two-Dimensional
Functions
• The normalized central moments
are defined as
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
pq
pq
00
pq
where
1
2
for p q 2,3,....
Moments of Two-Dimensional
Functions
• A seven invariant moments can be derived from the
second and third moments:
1 20 02
2 ( 20 02 ) 2 4112
3 (30 312 ) 2 (3 21 03 ) 2
4 (30 12 ) 2 ( 21 03 ) 2
5 (30 312 )(30 12 )(30 12 ) 2 3( 21 03 ) 2
(3 21 03 )( 21 03
)3(
12 ) ( 21 03 )
2
30
2
Moments of Two-Dimensional
Functions
6 ( 20 02 )(30 12 ) 2 ( 21 03 ) 2
411 (30 12 )( 21 03 )
7 (3 21 03 )(30 12 )(30 12 ) 3( 21 03 )
2
2
(312 30 )( 21 03 ) 3(30 12 ) 2 ( 21 03 ) 2
This set of moments is invariant to translation,
rotation, and scale change
Moments of Two-Dimensional
Functions
Moments of Two-Dimensional
Functions
Table 11.3 Moment invariants for the images in Figs. 11.25(a)-(e).
11.4 Use of Principal
Components for Description
Principal Components for
Description
Purpose: to reduce dimensionality of a vector image while
maintaining information as much as possible.
Let
Mean:
x [ x1
x2 ... xn ]T
1
m x E{x}
K
Covariance matrix
K
x
k 1
k
1
C x E{( x m x )( x m x )T }
K
K
T
T
x
x
m
m
k k x x
k 1
Principal Components for
Description
Let
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
y A( x m x )
Where A is created from eigenvectors of Cx as follows
Row 1 contain the 1st eigenvector with the largest
eigenvalue.
Row 2 contain the 2nd eigenvector with the 2nd largest
eigenvalue.
….
1 0
... 0
m y E{y} 0
0 ... 0
1
and
C
y
... ... ... ...
C y AC x AT
0 ... ... 1
are
uncorrelated.
The
y A( x m )
Then elements of
x
component of y with the largest is called the principal
component.
Principal Components for
Description
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Eigenvector and eigenvalue of Matrix C are defined as
Let C be a matrix of size NxN and e be a vector of size
Nx1.
If
Ce e
Where is a constant
We call e as an eigenvector and as eigenvalue of C
Principal Components for
Description
6 spectral images
from an airborne
Scanner.
Principal Components for
Description
Component
1
2
3
4
5
6
3210
931.4
118.5
83.88
64.00
13.40
Original image
After Hotelling transform
Principal Components for
Description
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
11.5 Relational Descriptors
Relational Descriptors
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Relational Descriptors
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Relational Descriptors
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Relational Descriptors
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Relational Descriptors
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors
Relational Descriptors
11.1- Representation
11.2- Boundary Descriptors
11,3- Regional Descriptors
11.4- Use of Principal
Components for Description
11.5 - Relational Descriptors