DISTANCE, PERIMETER, AND AREA MEASUREMENTS
593
TABLE 18.2-1. Example of Perimeter and Area Computation
18.2.1. Bit Quads
Gray (9) has devised a systematic method of computing the area and perimeter of
binary objects based on matching the logical state of regions of an image to binary
patterns. Let represent the count of the number of matches between image
pixels and the pattern Q within the curly brackets. By this definition, the object area
is then
(18.2-5)
If the object is enclosed completely by a border of white pixels, its perimeter is
equal to
(18.2-6)
Now, consider the following set of pixel patterns called bit quads defined in
Figure 18.2-1. The object area and object perimeter of an image can be expressed in
terms of the number of bit quad counts in the image as
p C(p) j(p) k(p) j(p) A(p)
10 0 100
23–1 0–1 0
3001–1–1
41100–1
50010–1
63–1 0–1–1
72 0–1–1 0
83–1 0–2 0
9 2 0–1–2 2
10 2 0 –1 –2 4
11 1 1 0 –1 4
121 1004
∆∆
00000
01010
01100
00000
nQ{}
A
O
n 1{}=
P
O
2n 01{}2n
0
1
+=
22×
594
SHAPE ANALYSIS
(18.2-7a)
(18.2-7b)
These area and perimeter formulas may be in considerable error if they are utilized
to represent the area of a continuous object that has been coarsely discretized. More
accurate formulas for such applications have been derived by Duda (10):
(18.2-8a)
(18.2-8b)
FIGURE 18.2-1. Bit quad patterns.
A
O
1
4
-
nQ
1
{}2nQ
2
{}3nQ
3
{}4nQ
4
{}2nQ
D
{}++++[]=
P
O
nQ
1
{}nQ
2
{}nQ
3
{}2nQ
D
{}+++=
A
O
1
4
-
nQ
1
{}
1
2
-
nQ
2
{}
7
8
-
nQ
3
{}nQ
4
{}
3
4
-
nQ
D
{}++++=
P
O
nQ
2
{}
1
2
-
nQ
1
{}nQ
3
{}2nQ
D
{}++[]+=
DISTANCE, PERIMETER, AND AREA MEASUREMENTS
595
Bit quad counting provides a very simple means of determining the Euler number of
an image. Gray (9) has determined that under the definition of four-connectivity, the
Euler number can be computed as
(18.2-9a)
and for eight-connectivity
(18.2-9b)
It should be noted that although it is possible to compute the Euler number E of an
image by local neighborhood computation, neither the number of connected compo-
nents C nor the number of holes H, for which E = C – H, can be separately computed
by local neighborhood computation.
18.2.2. Geometric Attributes
With the establishment of distance, area, and perimeter measurements, various geo-
metric attributes of objects can be developed. In the following, it is assumed that the
number of holes with respect to the number of objects is small (i.e., E is approxi-
mately equal to C).
The circularity of an object is defined as
(18.2-10)
This attribute is also called the thinness ratio. A circle-shaped object has a circular-
ity of unity; oblong-shaped objects possess a circularity of less than 1.
If an image contains many components but few holes, the Euler number can be
taken as an approximation of the number of components. Hence, the average area
and perimeter of connected components, for E > 0, may be expressed as (9)
(18.2-11)
(18.2-12)
For images containing thin objects, such as typewritten or script characters, the
average object length and width can be approximated by
E
1
4
-
nQ
1
{}nQ
3
{}– 2nQ
D
{}+[]=
E
1
4
-
nQ
1
{}nQ
3
{}– 2nQ
D
{}–[]=
C
O
4πA
O
P
O
()
2
=
A
A
A
O
E
-=
P
A
P
O
E
-=
596
SHAPE ANALYSIS
(18.2-13)
(18.2-14)
These simple measures are useful for distinguishing gross characteristics of an
image. For example, does it contain a multitude of small pointlike objects, or fewer
bloblike objects of larger size; are the objects fat or thin? Figure 18.2-2 contains
images of playing card symbols. Table 18.2-2 lists the geometric attributes of these
objects.
FIGURE 18.2-2. Playing card symbol images.
L
A
P
A
2
=
W
A
2A
A
P
A
=
(
a
) Spade (
b
) Heart
(
c
) Diamond (
d
) Club
SPATIAL MOMENTS
597
TABLE 18.2-2 Geometric Attributes of Playing Card Symbols
18.3. SPATIAL MOMENTS
From probability theory, the (m, n)th moment of the joint probability density
is defined as
(18.3-1)
The central moment is given by
(18.3-2)
where and are the marginal means of . These classical relationships of
probability theory have been applied to shape analysis by Hu (11) and Alt (12). The
concept is quite simple. The joint probability density of Eqs. 18.3-1 and
18.3-2 is replaced by the continuous image function . Object shape is charac-
terized by a few of the low-order moments. Abu-Mostafa and Psaltis (13,14) have
investigated the performance of spatial moments as features for shape analysis.
18.3.1. Discrete Image Spatial Moments
The spatial moment concept can be extended to discrete images by forming spatial
summations over a discrete image function . The literature (15–17) is nota-
tionally inconsistent on the discrete extension because of the differing relationships
defined between the continuous and discrete domains. Following the notation estab-
lished in Chapter 13, the (m, n)th spatial moment is defined as
(18.3-3)
Attribute Spade Heart Diamond Club
Outer perimeter 652 512 548 668
Enclosed area 8,421 8,681 8.562 8.820
Average area 8,421 8,681 8,562 8,820
Average perimeter 652 512 548 668
Average length 326 256 274 334
Average width 25.8 33.9 31.3 26.4
Circularity 0.25 0.42 0.36 0.25
pxy,()
Mmn,() x
m
y
n
pxy,()xdyd
∞
–
∞
∫
∞
–
∞
∫
=
Umn,() x η
x
–()
m
y η
y
–()
n
pxy,()xdyd
∞
–
∞
∫
∞
–
∞
∫
=
η
x
η
y
p
xy,()
pxy,()
Fxy,()
Fjk,()
M
U
mn,() x
k
()
m
y
j
()
n
Fjk,()
k 1
=
K
∑
j 1
=
J
∑
=
598
SHAPE ANALYSIS
where, with reference to Figure 13.1-1, the scaled coordinates are
(18.3-4a)
(18.3-4b)
The origin of the coordinate system is the lower left corner of the image. This for-
mulation results in moments that are extremely scale dependent; the ratio of second-
order (m + n = 2) to zero-order (m = n = 0) moments can vary by several orders of
magnitude (18). The spatial moments can be restricted in range by spatially scaling
the image array over a unit range in each dimension. The (m, n)th scaled spatial
moment is then defined as
(18.3-5)
Clearly,
(18.3-6)
It is instructive to explicitly identify the lower-order spatial moments. The zero-
order moment
(18.3-7)
is the sum of the pixel values of an image. It is called the image surface. If is
a binary image, its surface is equal to its area. The first-order row moment is
(18.3-8)
and the first-order column moment is
(18.3-9)
Table 18.3-1 lists the scaled spatial moments of several test images. These
images include unit-amplitude gray scale versions of the playing card symbols of
Figure 18.2-2, several rotated, minified and magnified versions of these symbols, as
shown in Figure 18.3-1, as well as an elliptically shaped gray scale object shown in
Figure 18.3-2. The ratios
x
k
k
1
2
-
–=
y
j
J
1
2
-
j–+=
Mmn,()
1
J
n
K
m
x
k
()
m
y
j
()
n
Fjk,()
k 1
=
K
∑
j 1
=
J
∑
=
Mmn,()
M
U
mn,()
J
n
K
m
=
M 00,() Fjk,()
k 1
=
K
∑
j 1
=
J
∑
=
Fjk,()
M 10,()
1
K
x
k
Fjk,()
k 1
=
K
∑
j 1
=
J
∑
=
M 01,()
1
J
- y
j
Fjk,()
k 1
=
K
∑
j 1
=
J
∑
=
599
TABLE 18.3-1. Scaled Spatial Moments of Test Images
Image M(0,0) M(1,0) M(0,1) M(2,0) M(1,1) M(0,2) M(3,0) M(2,1) M(1,2) M(0,3)
Spade 8,219.98 4,013.75 4,281.28 1,976.12 2,089.86 2,263.11 980.81 1,028.31 1,104.36 1,213.73
Rotated spade 8,215.99 4,186.39 3,968.30 2,149.35 2,021.65 1,949.89 1,111.69 1,038.04 993.20 973.53
Heart 8,616.79 4,283.65 4,341.36 2,145.90 2,158.40 2,223.79 1,083.06 1,081.72 1,105.73 1,156.35
Rotated Heart 8,613.79 4,276.28 4,337.90 2,149.18 2,143.52 2,211.15 1,092.92 1,071.95 1,008.05 1,140.43
Magnified heart 34,523.13 17,130.64 17,442.91 8,762.68 8,658.34 9,402.25 4,608.05 4,442.37 4,669.42 5,318.58
Minified heart 2,104.97 1,047.38 1,059.44 522.14 527.16 535.38 260.78 262.82 266.41 271.61
Diamond 8,561.82 4,349.00 4,704.71 2,222.43 2,390.10 2,627.42 1,142.44 1,221.53 1,334.97 1,490.26
Rotated diamond 8,562.82 4,294.89 4,324.09 2,196.40 2,168.00 2,196.97 1,143.83 1,108.30 1,101.11 1,122.93
Club 8,781.71 4,323.54 4,500.10 2,150.47 2,215.32 2,344.02 1,080.29 1,101.21 1,153.76 1,241.04
Rotated club 8,787.71 4,363.23 4,220.96 2,196.08 2,103.88 2,057.66 1,120.12 1,062.39 1,028.90 1,017.60
Ellipse 8,721.74 4,326.93 4,377.78 2,175.86 2,189.76 2,226.61 1,108.47 1,109.92 1,122.62 1,146.97
600
SHAPE ANALYSIS
FIGURE 18.3-1 Rotated, magnified, and minified playing card symbol images.
(
a
) Rotated spade (
b
) Rotated heart
(
c
) Rotated diamond (
d
) Rotated club
(
e
) Minified heart (
f
) Magnified heart
SPATIAL MOMENTS
601
(18.3-10a)
(18.3-10b)
of first- to zero-order spatial moments define the image centroid. The centroid,
called the center of gravity, is the balance point of the image function such
that the mass of left and right of and above and below is equal.
With the centroid established, it is possible to define the scaled spatial central
moments of a discrete image, in correspondence with Eq. 18.3-2, as
(18.3-11)
For future reference, the (m, n)th unscaled spatial central moment is defined as
FIGURE 18.3-2 Eliptically shaped object image.
x
k
M 10,()
M 00,()
=
y
j
M 01,()
M 00,()
-=
Fjk,()
Fjk,() x
k
y
j
Umn,()
1
J
n
K
m
x
k
x
k
–()
m
y
j
y
j
–()
n
Fjk,()
k 1
=
K
∑
j 1
=
J
∑
=
602
SHAPE ANALYSIS
(18.3-12)
where
(18.3-13a)
(18.3-13b)
It is easily shown that
(18.3-14)
The three second-order scaled central moments are the row moment of inertia,
(18.3-15)
the column moment of inertia,
(18.3-16)
and the row–column cross moment of inertia,
(18.3-17)
The central moments of order 3 can be computed directly from Eq. 18.3-11 for m +
n = 3, or indirectly according to the following relations:
(18.3-18a)
(18.3-18b)
U
U
mn,() x
k
x
k
–()
m
y
j
y
j
–()
n
Fjk,()
k 1
=
K
∑
j 1
=
J
∑
=
x
˜
k
M
U
10,()
M
U
00,()
=
y
˜
j
M
U
01,()
M
U
00,()
=
Umn,()
U
U
mn,()
J
n
K
m
=
U 20,()
1
K
2
x
k
x
k
–()
2
Fjk,()
k 1
=
K
∑
j 1
=
J
∑
=
U 02,()
1
J
n
y
j
y
j
–()
2
Fjk,()
k 1
=
K
∑
j 1
=
J
∑
=
U 11,()
1
JK
x
k
x
k
–()y
j
y
j
–()Fjk,()
k 1
=
K
∑
j 1
=
J
∑
=
U 30,()M 30,()3y
j
M 20,()2 y
j
()
2
M 10,()+–=
U 21,()M 21,()2y
j
M 11,()– x
k
M 20,()2 y
j
()
2
M 01,()+–=
Không có nhận xét nào:
Đăng nhận xét