\documentstyle[12pt]{article}
\setlength{\textwidth}{9.75 in}
\setlength{\evensidemargin}{-0.4 in}
\setlength{\oddsidemargin}{-0.4  in}
\setlength{\textheight}{7.2 in}
\setlength{\topmargin}{-1.05 in}
\setlength{\arraycolsep}{9pt}
\renewcommand{\baselinestretch}{1.0}
\newcommand{\psfuh}    {/u/vision/fuh/document/}
\newcommand{\open}{\mbox{\Large $\circ$}}
\newcommand{\close}{\mbox{\Large $\bullet$}}
% \input{psfig}
\newcommand{\epsfig}[1]{\psfig{#1}}
\begin{document}
\bibliographystyle{plain}

\Huge
\begin{center}
Chapter 3 Binary Machine Vision: \\
Region Analysis
\end{center}

\LARGE
3.1 Introduction \\
region properties: measurement vector, input to classifier 

\vspace{1cm}
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 

\vspace{1cm}
\noindent
bounding rectangle: smallest rectangle circumscribes the region \\
area:
\[
A = \sum_{(r,c) \in R} 1
\]
centroid:
\[
\bar{r} = \frac{1}{A} \sum_{(r,c) \in R} r
\]
\[
\bar{c} = \frac{1}{A} \sum_{(r,c) \in R} c
\]

\vspace{1cm}
\noindent
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) \in R | N_8(r,c)-R \neq \emptyset \}
\]
\[
P_8 = \{(r,c) \in R | N_4(r,c)-R \neq \emptyset \}
\]
e.g. center is in $P_4$ but not in $P_8$ for 
\[
\begin{array}{cccc}
r \backslash c & 0 & 1 & 2 \\
0              &   & * &   \\ 
1              & * & * & * \\ 
2              &   & * & 
\end{array}
\]
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)\}$ 

\vspace{1cm}
\noindent
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}) \in N_4(r_k,c_k)\} 
\]
\[
    + \sqrt{2}\#\{k|(r_{k+1},c_{k+1}) \in 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}$ 
 

\vspace{1cm}
\noindent
mean distance $\mu_R$ from the centroid to the shape boundary
\[
\mu_R = \frac{1}{K} \sum_{k=0}^{K-1} \|(r_k, c_k)-(\bar{r},\bar{c})\|
\]
e.g. $\mu_R(P_4)=4/8=0.5$, $\mu_R(P_8)=1$ \\
standard deviation $\sigma_R$ of distances from centroid to boundary 
\[
\sigma_R^2=\frac{1}{K} \sum_{k=0}^{K-1} [\|(r_k, c_k)-(\bar{r},\bar{c})\|-\mu_R]^2
\]
e.g. $\sigma_R(P_4)=0.5$, $\sigma_R(P_8)=0$ \\
Haralick shows that $\mu_R / \sigma_R$ has properties:
\begin{enumerate}
\item digital shape $\rightarrow$ circular, $\mu_R / \sigma_R$ increases monotonically
\item $\mu_R / \sigma_R$ similar for similar digital/continuous shapes
\item orientation (rotation) and area (scale) independent
\end{enumerate}
=====marriage=====

\vspace{1cm}
\noindent
Average gray level (intensity)
\[
\mu = \frac{1}{A} \sum_{(r,c) \in R} I(r,c)
\]
Gray level (intensity) variance
\[
\sigma^2 = \frac{1}{A} \sum_{(r,c) \in R} [I(r,c) - \mu]^2 =
[\frac{1}{A} \sum_{(r,c) \in R} I(r,c)^2] - \mu^2
\]
right hand equation lets us compute variance with only one pass

\vspace{1cm}
\noindent
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)] \in S | I(r_1, c_1) = g_1
{\rm \ and \ } I(r_2,c_2)=g_2\}}{\#S}
\]
texture second moment (Haralick, Shanmugam, and Dinstein, 1973)
\[
M=\sum_{g_1,g_2} P^2(g_1, g_2)
\]
texture entropy 
\[
E = - \sum_{g_1,g_2} P(g_1, g_2) \log P(g_1, g_2) 
\]
texture correlation
\[
\rho = \sum_{g_1,g_2} (g_1 - \mu)(g_2 - \mu)P(g_1, g_2)/\sigma^2
\]
where
\[
\mu = \frac{1}{2}[\sum_{g_1} \sum_{g_2} g_1 P(g_1, g_2)
   +\sum_{g_1} \sum_{g_2} g_2 P(g_1, g_2)]
\]
\[
\sigma^2 = \frac{1}{2}[\sum_{g_1} \sum_{g_2} (g_1-\mu)^2 P(g_1, g_2)
   +\sum_{g_1} \sum_{g_2} (g_2-\mu)^2 P(g_1, g_2)]
\]
texture contrast
\[
C=\sum_{g_1} \sum_{g_2} |g_1 - g_2| P(g_1, g_2)
\]
texture homogeneity
\[
H=\sum_{g_1} \sum_{g_2} \frac{P(g_1, g_2)}{k+|g_1 - g_2|}
\]
where $k$ is some small constant \\
=====New 3:10=====

\vspace{1cm}
3.2.1 Extremal Points \\
eight distinct extremal pixels: topmost right, rightmost top, rightmost 
   bottom,\\
\hspace*{1cm} bottommost right, bottommost left, leftmost bottom, leftmost 
   top,\\
\hspace*{1cm} 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) \in R \}
\]
\[
c_2 = \max \{ c|(rmin, c) \in R \}
\]
\[
r_3 = \min \{ r|(r, cmax) \in R \}
\]
\[
r_4 = \max \{ r|(r, cmax) \in R \}
\]
\[
c_3 = c_4 = cmax
\]
\[
r_5 = r_6 = rmax
\]
\[
c_5 = \max \{ c|(rmax, c) \in R \}
\]
\[
c_6 = \min \{ c|(rmax, c) \in R \}
\]
\[
r_7 = \max \{ r|(r, cmin) \in R \}
\]
\[
r_8 = \min \{ r|(r, cmin) \in 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 $\leftrightarrow$
bottommost right, \\
\hspace*{1cm} topmost right $\leftrightarrow$ bottommost left,
    rightmost top $\leftrightarrow$ leftmost bottom, \\
\hspace*{1cm} rightmost bottom $\leftrightarrow$ leftmost top \\
each opposite extremal point pair: defines an axis \\
axis properties: length, orientation 

\vspace{1cm}
\noindent
the length covered by two pixels horizontally adjacent
\begin{itemize}
\item 1: distance between pixel centers
\item 2: from left edge of left pixel to right edge of right pixel 
\end{itemize}
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(\phi_1)
\]
\[
M_2 = \sqrt{(r_2 - r_6)^2 + (c_2 - c_6)^2} + Q(\phi_2)
\]
\[
M_3 = \sqrt{(r_3 - r_7)^2 + (c_3 - c_7)^2} + Q(\phi_3)
\]
\[
M_4 = \sqrt{(r_4 - r_8)^2 + (c_4 - c_8)^2} + Q(\phi_4)
\]
orientation taken counterclockwise w.r.t. column (horizontal) axis \\
=====Fig. 3.3=====
\[
\phi_1 = \tan^{-1} \frac{r_1 - r_5}{-(c_1 - c_5)}
\]
\[
\phi_2 = \tan^{-1} \frac{r_2 - r_6}{-(c_2 - c_6)}
\]
\[
\phi_3 = \tan^{-1} \frac{r_3 - r_7}{-(c_3 - c_7)}
\]
\[
\phi_4 = \tan^{-1} \frac{r_4 - r_8}{-(c_4 - c_8)}
\]
orientation convention for the axes \\
=====Fig. 3.4===== 
\[
Q(\theta) = \left\{ 
\begin{array}{l l}
\frac{1}{|\cos \theta|} & {\rm \ if\ } | \theta | < 45^\circ \\
\frac{1}{|\sin \theta|} & {\rm \ if\ } | \theta | > 45^\circ
\end{array}
\right.
\]
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 $i$th and $j$th extremal point
\[
M_{ij} = \sqrt{(r_i - r_j)^2 + (c_i - c_j)^2} + 1.12
\]
average value of $Q(\theta)= 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=====

\vspace{1cm}
3.2.2 Spatial Moments \\
second-order row moment
\[
\mu_{rr} = \frac{1}{A} \sum_{(r,c) \in R} (r - \bar{r})^2
\]
second-order mixed moment
\[
\mu_{rc} = \frac{1}{A} \sum_{(r,c) \in R} (r - \bar{r})(c - \bar{c})
\]
second-order column moment
\[
\mu_{cc} = \frac{1}{A} \sum_{(r,c) \in R} (c - \bar{c})^2
\]

\vspace{1cm}
3.2.3 Mixed Spatial Gray Level Moments \\
region properties: position, extent, shape, gray level properties \\
second-order mixed gray level spatial moments 
\[
\mu_{rg} = \frac{1}{A} \sum_{(r,c) \in R} (r - \bar{r})[I(r,c)-\mu]
\]
\[
\mu_{cg} = \frac{1}{A} \sum_{(r,c) \in R} (c - \bar{c})[I(r,c)-\mu]
\]
=====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=====

\vspace{1cm}
3.3 Signature Properties \\
vertical projection
\[
P_V (c) = \#\{r|(r,c) \in R\}
\]
horizontal projection
\[
P_H (r) = \#\{c|(r,c) \in R\}
\]
diagonal projection from lower left to upper right
\[
P_D (d) = \#\{(r,c) \in R | r+c = d\}
\]
diagonal projection from upper left to lower right
\[
P_E (e) = \#\{(r,c) \in R | r-c = e\}
\]
projections: easily obtainable in pipeline hardware \\
compute properties from projections \\
area
\[
A = \sum_{(r,c) \in R} 1 = \sum_r \sum_{\{c|(r,c) \in R\}} 1 = \sum_r P_H(r)
\]
rmin: top row of bounding rectangle
\[
rmin = \min\{r | (r,c) \in R\} = \min\{r|P_H (r) \neq 0 \}
\]
rmax: bottom row of bounding rectangle
\[
rmax = \max\{r | (r,c) \in R\} = \max\{r|P_H (r) \neq 0 \}
\]
cmin: leftmost column of bounding rectangle
\[
cmin = \min\{c | (r,c) \in R\} = \min\{c|P_V (c) \neq 0 \}
\]
cmax: rightmost column of bounding rectangle
\[
cmax = \max\{c | (r,c) \in R\} = \max\{c|P_V (c) \neq 0 \}
\]
row centroid
\[
\bar{r} = \frac{1}{A} \sum_{(r,c) \in R} r = \frac{1}{A} \sum_r \sum_{\{c|(r,c) \in R\}} r
\]
\[
= \frac{1}{A} \sum_r r \sum_{\{c|(r,c) \in R\}} 1 = \frac{1}{A} \sum_r r P_H(r)
\]
column centroid
\[
\bar{c} = \frac{1}{A} \sum_{(r,c) \in R} c = \frac{1}{A} \sum_c \sum_{\{r|(r,c) \in R\}} c
\]
\[
= \frac{1}{A} \sum_c c \sum_{\{r|(r,c) \in R\}} 1 = \frac{1}{A} \sum_c c P_V(c)
\]
diagonal centroid
\[
\bar{d} = \frac{1}{A} \sum_d d P_D(d)
\]
another diagonal centroid
\[
\bar{e} = \frac{1}{A} \sum_e e P_E(e)
\]
diagonal centroid related to row and column centroid
\[
\bar{d} = \bar{r} + \bar{c}
\]
\[
\bar{e} = \bar{r} - \bar{c}
\]
second row moment from horizontal projection
\[
\mu_{rr} = \frac{1}{A} \sum_r (r-\bar{r})^2 P_H(r)
\]
second column moment from vertical projection
\[
\mu_{cc} = \frac{1}{A} \sum_c (c-\bar{c})^2 P_V(c)
\]
second diagonal moment
\[
\mu_{dd} = \frac{1}{A} \sum_d (d-\bar{d})^2 P_D(d)
\]
second diagonal moment related to $\mu_{rc}, \mu_{rr}, \mu_{cc}$
\[
\mu_{dd} = \mu_{rr}+2 \mu_{rc} + \mu_{cc}
\]
second mixed moment can be obtained from projection
\[
\mu_{rc} = \frac{\mu_{dd}-\mu_{rr}-\mu_{cc}}{2}
\]
second diagonal moment related to $\mu_{rc}, \mu_{rr}, \mu_{cc}$
\[
\mu_{ee} = \mu_{rr}-2 \mu_{rc} + \mu_{cc}
\]
second mixed moment can be obtained from projection
\[
\mu_{rc} = \frac{\mu_{rr}+\mu_{cc}-\mu_{ee}}{2}
\]
mixed moment $\mu_{rc}$ obtained directly from $\mu_{dd}$ and $\mu_{ee}$
\[
\mu_{rc} = \frac{\mu_{dd}-\mu_{ee}}{4}
\]

\vspace{1cm}
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 $(\Delta x, \Delta y)$ of rectangle 
   by corner location $(a_1, b_1)$, \\
\hspace*{1cm}  side lengths $w, h$, orientation angle $\theta$ 
\[
\left (
\begin{array}{c}
x_{rot} \\
y_{rot}
\end{array} \right ) = \left (
\begin{array}{cc}
 \cos \theta & \sin \theta \\
-\sin \theta & \cos \theta
\end{array} \right )
\left (
\begin{array}{c}
x \\
y
\end{array} \right )
\]
\[
\left (
\begin{array}{c}
x_{new} \\
y_{new}
\end{array} \right ) = \left (
\begin{array}{c}
a_1 \\
b_1
\end{array} \right ) = \left (
\begin{array}{cc}
 \cos \theta & \sin \theta \\
-\sin \theta & \cos \theta
\end{array} \right )
\left (
\begin{array}{c}
x \\
y
\end{array} \right ) + \left (
\begin{array}{c}
\Delta x \\
\Delta y
\end{array} \right )
\]
\[
\left (
\begin{array}{c}
\Delta x \\
\Delta y
\end{array} \right ) = \left (
\begin{array}{c}
a_1 + \frac{w}{2} \cos \theta - \frac{h}{2} \sin \theta \\
b_1 - \frac{w}{2} \sin \theta - \frac{h}{2} \cos \theta
\end{array} \right ) 
\]
geometry for determining the translation of the center of a rectangle \\
=====Fig. 3.12===== \\
partition rectangle into six regions formed by two vertical lines \\
\hspace*{1cm} a known distance $g$ apart and one horizontal line \\
=====Fig. 3.14===== 
\[
\Delta x = \frac{(C+D)-(A+B)}{2h} \cos \theta
\]
\[
\Delta y = \frac{(A+E+C)-(B+F+D)}{2w} \cos \theta
\]
where rotation angle
\[
\cos \theta = \frac{hg}{E+F}
\]

\vspace{1cm}
3.3.2 Using Signature Analysis to Determine the Center of a Circle \\
partition the circle into four quadrants formed by two orthogonal lines \\
\hspace*{1cm} which meet inside the circle \\
geometry for the circle, its center, and a chord \\
=====Fig. 3.15===== \\
$A+B=\pi r^2$ \\
$r = \sqrt{\frac{A+B}{\pi}}$ \\
$A = \frac{r^2}{2}[2 \theta - \sin 2 \theta]$ \\
$\frac{2 \pi A}{A + B} = 2 \theta - \sin 2 \theta$ \\
$d = \sqrt{\frac{A+B}{\pi}} \cos \theta$ \\
circle projected onto the four quadrants of the projection index image \\
=====Fig. 3.16=====  \\
each quadrant area from histogram of the masked projection 
\[
| \Delta y | = \sqrt{ \frac{A+B+C+D}{\pi}} \cos \theta_y
\]
$\Delta y$ positive if $A+B > C+D$, negative otherwise, where 
\[
\frac{2 \pi (A+B)}{A+B+C+D} = 2 \theta_y - \sin 2 \theta_y
\]
$\Delta x$ positive if $B+D > A+C$, negative otherwise
\[
| \Delta x | = \sqrt{ \frac{A+B+C+D}{\pi}} \cos \theta_x
\]
\[
\frac{2 \pi (B+D)}{A+B+C+D} = 2 \theta_x - \sin 2 \theta_x
\]

\vspace{1cm}
3.4 Summary \\
region properties from connected components or signature analysis



\vspace{1in}
\begin{center}
R. C. Gonzalez and R. E. Woods, {\em Digital Image Processing}, 
Addison Wesley, Reading, MA, 1992 \\
Chapter 4 Image Enhancement \\
4.2 Enhancement by Point Processing \\
4.2.2 Histogram Processing
\end{center}
Histogram Equalization p. 173-180 \\
pixel transformation 
\[
s = T(r)
\]
$r,s$: original, new intensity, $T$: transformation 
\begin{itemize}
\item $T(r)$ single-valued, monotonically increasing
\item $0 \leq T(r) \leq 255$ for $0 \leq r \leq 255$
\end{itemize}
=====Fig. 4.10===== \\
histogram equalization, histogram linearization 
\[
s_k = 255 \sum_{j=0}^k \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=====

\vspace{1cm}
Project due Oct. 26: \\
Write a program to do histogram equalization

\end{document}
