Chapter 3 Binary Machine Vision: Region Analysis

3.1 Introduction region properties: measurement vector, input to classifier

3.2 Thresholding regions: produced by connected components labeling operator region intensity histogram: gray level values for all pixels mean gray level value: summary statistics of region’s intensity

bounding rectangle: smallest rectangle circumscribes the region area:

A = _{(r,c)∈R}^{∑} 1

centroid:

r̄ = \frac{1}{A} _{(r,c)∈R}^{∑} r

c̄ = \frac{1}{A} _{(r,c)∈R}^{∑} c

border pixel: has some neighboring pixel outside the region P_{4}: 4-connected perimeter: if 8-connectivity for inside and outside P_{8}: 8-connected perimeter: if 4-connectivity for inside and outside

P_{4} = {(r, c) ∈ R|N_{8}(r, c) − R ≠ ∅}
P_{8} = {(r, c) ∈ R|N_{4}(r, c) − R ≠ ∅}

e.g. center is in P_{4} but not in P_{8} for

\begin{matrix}r\c & 0 & 1 & 2 \\ 0 & & ∗ \\ 1 & ∗ & ∗ & ∗ \\ 2 & & ∗ \end{matrix}

e.g. P_{4} = {(1, 0), (1, 1), (2, 1), (1, 1), (1, 2), (1, 1), (0, 1), (1, 1)} e.g. P_{8} = {(1, 0), (2, 1), (1, 2), (0, 1)}

length of perimeter P =< (r_{0}, c_{0}), ..., (r_{K−1}, c_{K−1}) >, successive pixels, neighbors

|P | = #{k|(r_{k+1}, c_{k+1}) ∈ N_{4}(r_{k}, c_{k})}

+\sqrt{2}#\{k|(r_{k+1}, c_{k+1}) ∈ N_{8}(r_{k}, c_{k}) − N_{4}(r_{k}, c_{k})\}

where k + 1 is computed modulo K i.e. (r_{0}, c_{0}) = (r_{K}, c_{K}) e.g. |P_{4}| = 8, |P_{8}| = 4\sqrt{2} mean distance μ_{R} from the centroid to the shape boundary

μ_{R} = \frac{1}{K} K−1 ; ∑ ; k=0 ∥(r_{k}, c_{k}) − (r̄, c̄)∥

e.g. μ_{R}(P_{4}) = 4/8 = 0.5, μ_{R}(P_{8}) = 1 standard deviation σ_{R} of distances from centroid to boundary

σ_{R}^{2} = \frac{1}{K} K−1 ; ∑ ; k=0[∥(r_{k}, c_{k}) − (r̄, c̄)∥ − μ_{R}]^{2}

e.g. σ_{R}(P_{4}) = 0.5, σ_{R}(P_{8}) = 0 Haralick shows that μ_{R}/σ_{R} has properties:

1. digital shape → circular, μ_{R}/σ_{R} increases monotonically 2. μ_{R}/σ_{R} similar for similar digital/continuous shapes

3. orientation (rotation) and area (scale) independent =====marriage=====

Average gray level (intensity)

μ = \frac{1}{A} _{(r,c)∈R}^{∑} I(r, c)

Gray level (intensity) variance

σ^{2} = \frac{1}{A} _{(r,c)∈R}^{∑}[I(r, c) − μ]^{2} = [\frac{1}{A} _{(r,c)∈R}^{∑} I(r, c)^{2}] − μ^{2}

right hand equation lets us compute variance with only one pass

microtexture properties: function of co-occurrence matrix S: set of pixels in designated spatial relationship e.g. 4-neighbors co-occurrence matrix P

P (g_{1}, g_{2}) = \frac{#\{[(r_{1}, c_{1}), (r_{2}, c_{2})] ∈ S|I(r_{1}, c_{1}) = g_{1} and I(r_{2}, c_{2}) = g_{2}\}}{#S}

texture second moment (Haralick, Shanmugam, and Dinstein, 1973)

M = _{g_{1},g_{2}}^{∑} P^{2}(g_{1}, g_{2})

texture entropy

E = − _{g_{1},g_{2}}^{∑} P (g_{1}, g_{2}) log P (g_{1}, g_{2})

texture correlation

ρ = _{g_{1},g_{2}}^{∑}(g_{1} − μ)(g_{2} − μ)P (g_{1}, g_{2})/σ^{2}

where

μ = \frac{1}{2}[_{g_{1}}^{∑} _{g_{2}}^{∑} g_{1}P (g_{1}, g_{2}) + _{g_{1}}^{∑} _{g_{2}}^{∑} g_{2}P (g_{1}, g_{2})]

σ^{2} = \frac{1}{2}[_{g_{1}}^{∑} _{g_{2}}^{∑}(g_{1} − μ)^{2}P (g_{1}, g_{2}) + _{g_{1}}^{∑} _{g_{2}}^{∑}(g_{2} − μ)^{2}P (g_{1}, g_{2})]

texture contrast

C = _{g_{1}}^{∑} _{g_{2}}^{∑} |g_{1} − g_{2}|P (g_{1}, g_{2})

texture homogeneity

H = _{g_{1}}^{∑} _{g_{2}}^{∑} \frac{P (g_{1}, g_{2})}{k + |g_{1} − g_{2}|}

where k is some small constant =====New 3:10=====

3.2.1 Extremal Points eight distinct extremal pixels: topmost right, rightmost top, rightmost bottom,

bottommost right, bottommost left, leftmost bottom, leftmost top, topmost left

=====Fig. 3.1===== different extremal points may be coincident =====Fig. 3.2===== association of the name of the eight extremal points with their coordinates =====Table 3.1=====

r_{1} = r_{2} = rmin

c_{1} = min{c|(rmin, c) ∈ R}
c_{2} = max{c|(rmin, c) ∈ R}
r_{3} = min{r|(r, cmax) ∈ R}
r_{4} = max{r|(r, cmax) ∈ R}
c_{3} = c_{4} = cmax
r_{5} = r_{6} = rmax
c_{5} = max{c|(rmax, c) ∈ R}
c_{6} = min{c|(rmax, c) ∈ R}
r_{7} = max{r|(r, cmin) ∈ R}
r_{8} = min{r|(r, cmin) ∈ R}
c_{7} = c_{8} = cmin

association of the name of an external coordinate with its definition =====Table 3.2===== extremal points occur in opposite pairs: topmost left ↔ bottommost right,

topmost right ↔ bottommost left, rightmost top ↔ leftmost bottom, rightmost bottom ↔ leftmost top

each opposite extremal point pair: defines an axis axis properties: length, orientation the length covered by two pixels horizontally adjacent

• 1: distance between pixel centers

• 2: from left edge of left pixel to right edge of right pixel

distance calculation: add a small increment to the Euclidean distance M_{1}: axis between (r_{1}, c_{1}) and (r_{5}, c_{5}) M_{2}: axis between (r_{2}, c_{2}) and (r_{6}, c_{6}) M_{3}: axis between (r_{3}, c_{3}) and (r_{7}, c_{7}) M_{4}: axis between (r_{4}, c_{4}) and (r_{8}, c_{8})

M_{1} = \sqrt{(r_{1} − r_{5})^{2} + (c_{1} − c_{5})^{2}} + Q(ϕ_{1})
M_{2} = \sqrt{(r_{2} − r_{6})^{2} + (c_{2} − c_{6})^{2}} + Q(ϕ_{2})
M_{3} = \sqrt{(r_{3} − r_{7})^{2} + (c_{3} − c_{7})^{2}} + Q(ϕ_{3})
M_{4} = \sqrt{(r_{4} − r_{8})^{2} + (c_{4} − c_{8})^{2}} + Q(ϕ_{4})

orientation taken counterclockwise w.r.t. column (horizontal) axis =====Fig. 3.3=====

ϕ_{1} = tan^{−1} \frac{r_{1} − r_{5}}{−(c_{1} − c_{5})}

ϕ_{2} = tan^{−1} \frac{r_{2} − r_{6}}{−(c_{2} − c_{6})}

ϕ_{3} = tan^{−1} \frac{r_{3} − r_{7}}{−(c_{3} − c_{7})}

ϕ_{4} = tan^{−1} \frac{r_{4} − r_{8}}{−(c_{4} − c_{8})}

orientation convention for the axes =====Fig. 3.4=====

Q(θ) = \{ \begin{matrix}\frac{1}{| cos θ|} & if |θ| < 45^{∘} \\ \frac{1}{| sin θ|} & if |θ| > 45^{∘} \end{matrix}

length going from left edge of left pixel to right edge of right pixel =====Fig. 3.5===== axes paired: M_{1} with M_{3} and M_{2} with M_{4} calculation of the axis length and orientation of a linelike shape =====Fig. 3.6===== distance between ith and jth extremal point

M_{ij} = \sqrt{(r_{i} − r_{j})^{2} + (c_{i} − c_{j})^{2}} + 1.12

average value of Q(θ) = 1.12, largest error 0.294 = \sqrt{2} − 1.12 calculations for length of sides, base, and altitude for a triangle =====Fig. 3.7===== geometry of the tilted rectangle =====Fig. 3.8===== calculation for the orientation of an example rectangle =====Fig. 3.9===== axes and their mates that arise from octagonal-shaped regions =====Fig. 3.10=====

3.2.2 Spatial Moments second-order row moment

μ_{rr} = \frac{1}{A} _{(r,c)∈R}^{∑}(r − r̄)^{2}

second-order mixed moment

μ_{rc} = \frac{1}{A} _{(r,c)∈R}^{∑}(r − r̄)(c − c̄)

second-order column moment

μ_{cc} = \frac{1}{A} _{(r,c)∈R}^{∑}(c − c̄)^{2}

3.2.3 Mixed Spatial Gray Level Moments region properties: position, extent, shape, gray level properties second-order mixed gray level spatial moments

μ_{rg} = \frac{1}{A} _{(r,c)∈R}^{∑}(r − r̄)[I(r, c) − μ]

μ_{cg} = \frac{1}{A} _{(r,c)∈R}^{∑}(c − c̄)[I(r, c) − μ]

=====Example 3.1===== connected components labeling of the image in Fig. 2.2 =====Fig. 3.11===== all the properties measured from each of the regions =====Table 3.3===== =====joke=====

3.3 Signature Properties vertical projection

P_{V} (c) = #{r|(r, c) ∈ R}

horizontal projection

P_{H}(r) = #{c|(r, c) ∈ R}

diagonal projection from lower left to upper right

P_{D}(d) = #{(r, c) ∈ R|r + c = d} diagonal projection from upper left to lower right

P_{E}(e) = #{(r, c) ∈ R|r − c = e}

projections: easily obtainable in pipeline hardware compute properties from projections area

A = _{(r,c)∈R}^{∑} 1 = _{r}^{∑} _{{c|(r,c)∈R}}^{∑} 1 = _{r}^{∑} P_{H}(r)

rmin: top row of bounding rectangle

rmin = min{r|(r, c) ∈ R} = min{r|P_{H}(r) ≠ 0}

rmax: bottom row of bounding rectangle

rmax = max{r|(r, c) ∈ R} = max{r|P_{H}(r) ≠ 0}

cmin: leftmost column of bounding rectangle

cmin = min{c|(r, c) ∈ R} = min{c|P_{V} (c) ≠ 0}

cmax: rightmost column of bounding rectangle

cmax = max{c|(r, c) ∈ R} = max{c|P_{V} (c) ≠ 0}

row centroid

r̄ = \frac{1}{A} _{(r,c)∈R}^{∑} r = \frac{1}{A} _{r}^{∑} _{\{c|(r,c)∈R\}}^{∑} r

= \frac{1}{A} _{r}^{∑} r _{\{c|(r,c)∈R\}}^{∑} 1 = \frac{1}{A} _{r}^{∑} rP_{H}(r)

column centroid

c̄ = \frac{1}{A} _{(r,c)∈R}^{∑} c = \frac{1}{A} _{c}^{∑} _{\{r|(r,c)∈R\}}^{∑} c

= \frac{1}{A} _{c}^{∑} c _{\{r|(r,c)∈R\}}^{∑} 1 = \frac{1}{A} _{c}^{∑} cP_{V} (c)

diagonal centroid

d̄ = \frac{1}{A} _{d}^{∑} dP_{D}(d)

another diagonal centroid

ē = \frac{1}{A} _{e}^{∑} eP_{E}(e)

diagonal centroid related to row and column centroid

d̄ = r̄ + c̄

ē = r̄ − c̄

second row moment from horizontal projection

μ_{rr} = \frac{1}{A} _{r}^{∑}(r − r̄)^{2}P_{H}(r)

second column moment from vertical projection

μ_{cc} = \frac{1}{A} _{c}^{∑}(c − c̄)^{2}P_{V} (c)

second diagonal moment

μ_{dd} = \frac{1}{A} _{d}^{∑}(d − d̄)^{2}P_{D}(d)

second diagonal moment related to μ_{rc}, μ_{rr}, μ_{cc}

μ_{dd} = μ_{rr} + 2μ_{rc} + μ_{cc}

second mixed moment can be obtained from projection

μ_{rc} = \frac{μ_{dd} − μ_{rr} − μ_{cc}}{2}

second diagonal moment related to μ_{rc}, μ_{rr}, μ_{cc}

μ_{ee} = μ_{rr} − 2μ_{rc} + μ_{cc}

second mixed moment can be obtained from projection

μ_{rc} = \frac{μ_{rr} + μ_{cc} − μ_{ee}}{2}

mixed moment μ_{rc} obtained directly from μ_{dd} and μ_{ee}

μ_{rc} = \frac{μ_{dd} − μ_{ee}}{4}

3.3.1 Using Signature Analysis to Determine the Center and Orientation of a Rectangle signature analysis: important because of easy, fast implementation surface mount device (SMD) placement: position and orientation of parts determine center (Δx, Δy) of rectangle by corner location (a_{1}, b_{1}),

side lengths w, h, orientation angle θ

( \begin{matrix}x_{rot} \\ y_{rot} \end{matrix} ) = ( \begin{matrix}cos θ & sin θ \\ − sin θ & cos θ \end{matrix} ) ( \begin{matrix}x \\ y \end{matrix} )

( \begin{matrix}x_{new} \\ y_{new} \end{matrix} ) = ( \begin{matrix}a_{1} \\ b_{1} \end{matrix} ) = ( \begin{matrix}cos θ & sin θ \\ − sin θ & cos θ \end{matrix} ) ( \begin{matrix}x \\ y \end{matrix} ) + ( \begin{matrix}Δx \\ Δy \end{matrix} )

( \begin{matrix}Δx \\ Δy \end{matrix} ) = ( \begin{matrix}a_{1} + \frac{w}{2} cos θ − \frac{h}{2} sin θ \\ b_{1} − \frac{w}{2} sin θ − \frac{h}{2} cos θ \end{matrix} )

geometry for determining the translation of the center of a rectangle =====Fig. 3.12===== partition rectangle into six regions formed by two vertical lines

a known distance g apart and one horizontal line =====Fig. 3.14=====

Δx = \frac{(C + D) − (A + B)}{2h} cos θ

Δy = \frac{(A + E + C) − (B + F + D)}{2w} cos θ

where rotation angle

cos θ = \frac{hg}{E + F}

3.3.2 Using Signature Analysis to Determine the Center of a Circle partition the circle into four quadrants formed by two orthogonal lines

which meet inside the circle geometry for the circle, its center, and a chord =====Fig. 3.15===== A + B = πr^{2} r = \sqrt{\frac{A+B}{π}} A = \frac{r^{2}}{2}[2θ − sin 2θ] \frac{2πA}{A+B} = 2θ − sin 2θ d = \sqrt{\frac{A+B}{π}} cos θ circle projected onto the four quadrants of the projection index image =====Fig. 3.16===== each quadrant area from histogram of the masked projection

|Δy| = \sqrt{\frac{A + B + C + D}{π}} cos θ_{y}

Δy positive if A + B > C + D, negative otherwise, where

\frac{2π(A + B)}{A + B + C + D} = 2θ_{y} − sin 2θ_{y}

Δx positive if B + D > A + C, negative otherwise

|Δx| = \sqrt{\frac{A + B + C + D}{π}} cos θ_{x}

\frac{2π(B + D)}{A + B + C + D} = 2θ_{x} − sin 2θ_{x}

3.4 Summary region properties from connected components or signature analysis

R. C. Gonzalez and R. E. Woods, Digital Image Processing, Addison Wesley, Reading, MA, 1992

Chapter 4 Image Enhancement 4.2 Enhancement by Point Processing 4.2.2 Histogram Processing

Histogram Equalization p. 173-180 pixel transformation

s = T (r)

r, s: original, new intensity, T: transformation

• T (r) single-valued, monotonically increasing

• 0 ≤ T (r) ≤ 255 for 0 ≤ r ≤ 255

=====Fig. 4.10===== histogram equalization, histogram linearization

s_{k} = 255 k ; ∑ ; j=0 \frac{n_{j}}{n}

k = 0, 1, ..., 255, n_{j}: number of pixels with intensity j n: total number of pixels for every pixel if I(im, i, j) = k then I(imhe, i, j) = s_{k} =====Fig. 4.13===== =====Garfield 17:3=====

Project due Oct. 26: Write a program to do histogram equalization