\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 7 Conditioning and Labeling
\end{center}

\LARGE
7.1 Introduction \\
conditioning: noise removal, background normalization, ... \\
labeling: thresholding, edge detection, corner finding, ...

\vspace{1cm}
7.2 Noise Cleaning \\
noise cleaning: uses neighborhood spatial coherence \\
noise cleaning: uses neighborhood pixel value homogeneity 

\vspace{1cm}
\noindent
box filter: computes equally weighted average \\
box filter: separable \\
box filter: recursive implementation with two +, two -, one / per pixel  \\
=====Fig. 7.2=====

\vspace{1cm}
\noindent
Gaussian filter: linear smoother
\[
w(r,c) = k e^{-\frac{1}{2} ( \frac{r^2+c^2}{\sigma^2})}
\]
for all $(r,c) \in W$, where
\[
k = \frac{1}{\sum_{(r,c) \in W} e^{-\frac{1}{2} ( \frac{r^2+c^2}{\sigma^2})}}
\]
$W$: two or three $\sigma$ from the center \\
linear noise-cleaning filters: defocusing images, edges blurred

\vspace{1cm}
7.2.1 A Statistical Framework for Noise Removal \\
idealization: if no noise, each neighborhood the same constant

\vspace{1cm}
7.2.2 Determining Optimal Weight from Isotropic Covariance Matrices 

\vspace{1cm}
7.2.3 Outlier or Peak Noise \\
outlier: peak noise: pixel value replaced by random noise value \\
neighborhood size: larger than noise, smaller than preserved detail \\
center-deleted neighborhood: pixel values in neighborhood except center \\
$x_1,...,x_N$: center-deleted neighborhood \\
$y$: center pixel value \\
$\hat{\mu}$: mean of center-deleted neighborhood
\[
\hat{\mu}=\frac{1}{N} \sum_{n=1}^N x_n
\]
$z_{\rm outlier \ removal}$: output value of neighborhood outlier removal
\[
z_{\rm outlier \ removal} = \left \{
\begin{array}{ll}
y & {\rm if \ } |y-\hat{\mu}| < \theta \\
\hat{\mu} & {\rm otherwise}
\end{array} \right .
\]
$y$: not an outlier value if $y$ reasonably close to $\hat{\mu}$ \\
$\hat{\mu}$: use mean value when outlier \\
$\theta$: threshold for outlier value \\
$\theta$ too small: edges blurred \\
$\theta$ too large: noise cleaning will not be good 

\vspace{1cm}
\noindent
$\hat{\sigma}^2$: center-deleted neighborhood variance 
\[
\hat{\sigma}^2 = \frac{1}{N-1} \sum_{n=1}^N (x_n - \hat{\mu})^2
\]
$z_{\rm contrast-dependent \ outlier \ removal}$: output value with 
contrast-dependent-threshold
\[
z_{\rm contrast-dependent \ outlier \ removal} = \left \{
\begin{array}{ll}
y & {\rm if \ } |\frac{y-\hat{\mu}}{\hat{\sigma}}| < \theta \\
\hat{\mu} & {\rm otherwise}
\end{array} \right .
\]
$\hat{\mu}$: use neighborhood mean if pixel value significantly far from mean

\vspace{1cm}
\noindent
smooth replacement: instead of complete replacement or not at all \\
$z_{\rm smooth \ replacement}$: convex combination of input and mean \\
$K$: weighting parameter 
\[
z_{\rm smooth \ replacement}=\frac{|\frac{y-\hat{\mu}}{\hat{\sigma}}|}{
|\frac{y-\hat{\mu}}{\hat{\sigma}}|+K} \hat{\mu} 
+ \frac{K}{|\frac{y-\hat{\mu}}{\hat{\sigma}}|+K} y
\]
$K=0$: use neighborhood mean $\hat{\mu}$ \\
$K=\infty$: use input pixel value $y$

\vspace{1cm}
7.2.4 $k$-Nearest Neighbor \\
$k$-nearest neighbor average: equally weighted average of $k$-nearest neighbors

\vspace{1cm}
7.2.5 Gradient Inverse Weighted  \\
gradient inverse weighted: reduces sum-of-squares error within regions

\vspace{1cm}
7.2.6 Order Statistic Neighborhood Operators \\
order statistic: linear combination of neighborhood sorted values \\
$x_1, ..., x_N$: neighborhood pixel values \\
$x_{(1)}, ..., x_{(N)}$: sorted neighborhood values from smallest to largest

\vspace{1cm}
Median Operator \\
median: most common order statistic operator \\
median root: fixed-point result of a median filter \\
median roots: comprise only constant-valued neighborhoods, sloped edges \\
median: effective for impulsive noise \\
median: distorts or loses fine detail such as thin lines 
\[
z_{\rm median}=x_{(\frac{N+1}{2})}
\]

\vspace{1cm}
\noindent
$Q$: interquartile distance
\[
Q = x_{(\frac{3N+2}{4})}-x_{(\frac{N+2}{4})}
\]

\vspace{1cm}
Trimmed-Mean Operator \\
trimmed-mean: first $k$ and last $k$ order statistics not used \\
trimmed-mean: equal weighted average of central $N-2k$ order statistics
\[
z_{\rm trimmed \ mean} = \frac{1}{N-2k} \sum_{n=1+k}^{N-k} x_{(n)}
\]

\vspace{1cm}
Midrange \\
midrange: noise distribution with light and smooth tails 
\[
z_{\rm midrange} = \frac{1}{2}[x_{(1)}+x_{(N)}]
\]

\vspace{1cm}
7.2.7 A Decision Theoretic Approach to Estimating Mean \\
=====New 3:12=====

\vspace{1cm}
7.2.8 Hysteresis Smoothing \\
hysteresis smoothing: removes minor fluctuations, preserves major transients \\
hysteresis smoothing: finite state machine with two states: UP, DOWN \\
hysteresis smoothing: applied row-by-row and then column-by-column \\
if state DOWN and next one larger, if next local maximum does not exceed
threshold then stays current value i.e. small peak cuts flat \\
otherwise state changes from DOWN to UP and preserves major transients \\
if state UP and next one smaller, if next local minimum does not exceed 
threshold then stays current value i.e. small valley filled flat \\
otherwise state changes from UP to DOWN and preserves major transients \\
=====Fig. 7.9=====

\vspace{1cm}
7.2.9 Sigma Filter \\
sigma filter: average only with values within two-sigma interval
\[
\hat{y}= \frac{1}{\#M} \sum_{n \in M} x_n
\]
where $M=\{n|y-2\sigma \leq x_n \leq y+2\sigma\}$

\vspace{1cm}
7.2.10 Selected-Neighborhood Averaging \\
selected-neighborhood averaging: assumes pixel a part of homogeneous region\\
noise-filtered value: mean value from lowest variance neighborhood

\vspace{1cm}
7.2.11 Minimum Mean Square Noise Smoothing \\
minimum mean square noise smoothing: additive or multiplicative noise \\
each pixel in true image: regarded as a random variable

\vspace{1cm}
7.2.12 Noise-Removal Techniques-Experiments \\
=====Fig. 7.10===== \\
types of noise 
\begin{itemize}
\item uniform
\item Gaussian
\item salt and pepper \\
$i_{\rm min}$: minimum gray value for noise pixels \\
$i_{\rm max}$: maximum gray value for noise pixels \\
$p$: fraction of image to be corrupted with noise \\
$u$: uniform random variable in $[0,1]$ \\
$I(r,c)$: gray value at given pixel $(r,c)$ in input image \\
$O(r,c)$: gray value at given pixel $(r,c)$ in output image
\[
O(r,c)=\left \{
\begin{array}{ll}
I(r,c) & {\rm if \ } u > p \\
i_{\rm min}+(i_{\rm max}-i_{\rm min})*u & {\rm otherwise}
\end{array} \right .
\]
\item varying noise (the noise energy varies across the image)
\end{itemize}
S/N ratio: signal to noise ratio: $S=10*\log_{10}(VS/VN)$ \\
$VS$: image gray level variance \\
$VN$: noise variance \\
=====Fig. 7.11===== \\
contrast-dependent noise removal ($z_{\rm contrast-dependent \ outlier \ 
removal}$, $9\times 9$, $\theta=0.1$) \\
=====Fig. 7.12===== \\
smooth replacement ($z_{\rm smooth \ replacement}$, $9\times 9$, $\theta=0.4$,
$K=0.2$) \\
=====Fig. 7.13===== \\
default peak noise removal ($z_{\rm outlier \ removal}$, $9\times 9$, 
$\theta=0.2$) \\
=====Fig. 7.14===== \\
hysteresis smoothing \\
=====Fig. 7.15===== \\
interquartile mean filter ($z_{\rm trimmed \ mean}$, $7\times 7$, $k=N/4$) \\
=====Fig. 7.16===== \\
neighborhood midrange filter ($z_{\rm midrange}$, $7\times 7$) \\
=====Fig. 7.17===== \\
neighborhood running-mean filter (box filter, $7\times 7$) \\
=====Fig. 7.18===== \\
sigma filter (Eq. 7.18, $9\times 9$, $\sigma=0.2$) \\
=====Fig. 7.19===== \\
neighborhood weighted median filter ($7\times 7$)
\[
\begin{array}{ccccccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 2 & 2 & 2 & 2 & 2 & 1 \\
1 & 2 & 3 & 3 & 3 & 2 & 1 \\
1 & 2 & 3 & 4 & 3 & 2 & 1 \\
1 & 2 & 3 & 3 & 3 & 2 & 1 \\
1 & 2 & 2 & 2 & 2 & 2 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 
\end{array}
\]
=====Fig. 7.20===== \\
gain in S/N ratio \\
=====Table 7.5=====

\vspace{1cm}
7.3 Sharpening \\
unsharp masking: subtract fraction of neighborhood mean and scale result 
\[
z_{\rm sharpened}=s[y-k\hat{\mu}] = \hat{\mu}+s[y-\hat{\mu}]
\]
where $\hat{\mu}=\frac{1}{N}\sum_{n=1}^N x_n$ is neighborhood mean \\
$y$: center pixel value \\
$s$: scaling constant \\
$k$: fraction, reasonable between $\frac{1}{5}, \frac{2}{3}$ \\
possible to replace neighborhood mean with neighborhood median


\vspace{1cm}
7.3.1 Extremum Sharpening \\
extremum-sharpening: output closer of neighborhood maximum or minimum 
\[
z_{\rm min}=\min\{f(r+r',c+c')|(r',c') \in W \} = f \ominus W
\]
\[
z_{\rm max}=\max\{f(r+r',c+c')|(r',c') \in W \} = f \oplus W
\]
\[
z_{\rm extremum \ sharpened} = \left\{
\begin{array}{l l}
z_{\rm min} & {\rm \ if \ } f(r,c)-z_{\rm min} < z_{\rm max}-f(r,c) \\
z_{\rm max} & {\rm \ otherwise \ }
\end{array}
\right.
\]
$W$: neighborhood, (value 0 in gray scale morphology) \\
=====Oldie 34:14=====

\vspace{1cm}
7.4 Edge Detection \\
digital edge: boundary where brightness values significantly different \\
edge: brightness value appears to jump \\
The Archer, working model, by Henry Moore, 1964 \\
=====Nalwa, {\em A Guided Tour of Computer Vision}, Fig. 3.1===== \\
profiles of various types of image-intensity edges \\
=====Nalwa, {\em A Guided Tour of Computer Vision}, Fig. 3.2===== \\
physical events in a scene that may lead to intensity edges \\
=====Nalwa, {\em A Guided Tour of Computer Vision}, Fig. 3.3===== 

\vspace{1cm}
7.4.1 Gradient Edge Detectors \\
Roberts operators: two $2\times 2$ masks to calculate gradient \\
=====Fig. 7.21===== \\
gradient magnitude: $\sqrt{r_1^2+r_2^2}$ \\
where $r_1, r_2$ are values from first, second masks respectively

\vspace{1cm}
\noindent
Prewitt edge detector: two $3 \times 3$ masks in row, column direction \\
=====Fig. 7.22===== \\
gradient magnitude: $g=\sqrt{p_1^2+p_2^2}$ \\
gradient direction: $\theta=\arctan(p_1/p_2)$ clockwise w.r.t. column axis \\
where $p_1, p_2$ are values from first, second masks respectively

\vspace{1cm}
\noindent
Sobel edge detector: two $3 \times 3$ masks in row, column direction \\
=====Fig. 7.23===== \\
gradient magnitude: $g=\sqrt{s_1^2+s_2^2}$ \\
gradient direction: $\theta=\arctan(s_1/s_2)$ clockwise w.r.t. column axis \\
where $s_1, s_2$ are values from first, second masks respectively \\
Sobel edge detector: $2 \times 2$ smoothing followed by $2 \times 2$ gradient 
\[
\left[
\begin{array}{lll}
-1 & 0 & +1 \\
-2 & 0 & +2 \\
-1 & 0 & +1
\end{array} \right] = \left[
\begin{array}{ll}
1 & 1 \\
1 & 1 
\end{array} \right] * \left[
\begin{array}{ll}
-1 & +1 \\
-1 & +1 
\end{array} \right]
\]
\[
\left[
\begin{array}{rrr}
+1 & +2 & +1 \\
 0 &  0 &  0 \\
-1 & -2 & -1
\end{array} \right] = \left[
\begin{array}{ll}
1 & 1 \\
1 & 1 
\end{array} \right] * \left[
\begin{array}{ll}
+1 & +1 \\
-1 & -1 
\end{array} \right]
\]

\vspace{1cm}
\noindent
Frei and Chen edge detector: two in a set of nine orthogonal masks 
($3 \times 3$) \\
=====Fig. 7.24===== \\
gradient magnitude: $g=\sqrt{f_1^2+f_2^2}$ \\
gradient direction: $\theta=\arctan(f_1/f_2)$ clockwise w.r.t. column axis \\
where $f_1, f_2$ are values from first, second masks respectively

\vspace{1cm}
\noindent
Kirsch: set of eight compass template edge masks \\
=====Fig. 7.25===== \\
gradient magnitude
\[
g = \max_{n, n=0,...,7} k_n
\]
gradient direction: $\theta=45^\circ \arg\max k_n$

\vspace{1cm}
\noindent
Robinson: compass template mask set with only $0, \pm 1, \pm 2$ \\
=====Fig. 7.26===== \\
done by only four masks: since negation of each mask is also a mask \\
gradient magnitude and direction same as Kirsch operator

\vspace{1cm}
\noindent
Nevatia and Babu: set of six $5 \times 5$ compass template masks \\
=====Fig. 7.27===== \\
Robinson and Kirsch compass operator: detect lineal edges \\
=====Fig. 7.28===== \\
edge contour direction: along edge, right side bright, left side dark \\
edge contour direction: $90^\circ$ more than gradient direction

\vspace{1cm}
\noindent
four important properties an edge operator might have
\begin{enumerate}
\item accuracy in estimating gradient magnitude
\item accuracy in estimating gradient direction
\item accuracy in estimating step edge contrast
\item accuracy in estimating step edge direction
\end{enumerate}

\vspace{1cm}
\noindent
gradient direction: used for edge organization, selection, linking \\
=====Fig. 7.31=====

\vspace{1cm}
7.4.2 Zero-Crossing Edge Detectors \\
first derivative maximum: exactly where second derivative zero crossing \\
=====D. Marr, {\em Vision}, Fig. 2.8===== \\
Laplacian of a function $I(r,c)$
\[
\nabla^2 I = (\frac{\partial^2}{\partial r^2}+\frac{\partial^2}{\partial c^2})I
  = \frac{\partial^2 I}{\partial r^2}+\frac{\partial^2 I}{\partial c^2}
\]
two common $3 \times 3$ masks to calculate digital Laplacian \\
=====Fig. 7.33===== \\
the $3\times 3$ neighborhood values of an image function \\
=====Fig. 7.34===== \\
$3\times 3$ mask computing a digital Laplacian $e= -(4a+4b), 2a+b=1$ \\
=====Fig. 7.35===== \\
$3 \times 3$ mask for computing minimum-variance digital Laplacian \\
=====Fig. 7.36===== \\
Laplacian of the Gaussian kernel \\
=====Fig. 7.37===== 

\vspace{1cm}
A pixel is declared to have a zero crossing if it is less than $-t$ and one of
its eight neighbors is greater than $t$, or if it is greater than $t$ and one 
of its eight neighbors is less than $-t$, for some fixed threshold $t$ \\
=====Fig. 7.38===== \\
=====D. Marr, {\em Vision}, Fig. 2.12===== \\
=====D. Marr, {\em Vision}, Fig. 2.13===== \\
=====D. Marr, {\em Vision}, Fig. 2.14===== 

\vspace{1cm}
7.4.3 Edge Operator Performance \\
edge detector performance characteristics: misdetection/false-alarm rate \\
the Canny edge operator applied to a parts image \\
=====Nalwa, {\em A Guided Tour of Computer Vision}, Fig. 3.8===== \\
edges at two different scales detected by the Canny operator \\
=====Nalwa, {\em A Guided Tour of Computer Vision}, Fig. 3.9===== \\
the Nalwa-Binford and Marr-Hildreth edge operators \\
=====Nalwa, {\em A Guided Tour of Computer Vision}, Fig. 3.16===== \\
improvement of the resolution of an edge detector by image interpolation \\
=====Nalwa, {\em A Guided Tour of Computer Vision}, Fig. 3.17===== \\
edgel aggregation and edge description \\
=====Nalwa, {\em A Guided Tour of Computer Vision}, Fig. 3.18===== 


\vspace{1cm}
7.5 Line Detection \\
A line segment on an image can be characterized as an elongated rectangular
region having a homogeneous gray level bounded on both its longer sides by
homogeneous regions of a different gray level \\
one-pixel-wide lines can be detected by compass line detectors \\
=====Fig. 7.39===== \\
semilinear line detector by step edge on either side of the line \\
=====Fig. 7.40===== \\
detecting lines of one to three pixels in width \\
=====Fig. 7.41===== \\
=====joke=====














\vspace{1cm}
Project due Dec. 7 \\
Write the following programs: \\
1. Generate additive white Gaussian noise: \\
\hspace*{1cm} $I(nim,i,j) = I(im, i,j)+amplitude*N(0,1)$ \\
\hspace*{1cm} $N(0,1)$: Gaussian random variable with zero mean and st. dev. 1\\
\hspace*{1cm} $amplitude$ determines signal-to-noise ratio, try 10, 30 \\
\hspace*{1cm} =====zooma.im===== \\
\hspace*{1cm} =====zooma.gaus.8.06.im===== \\
\hspace*{1cm} =====zooma.gaus.25.5.im===== \\
2. Generate salt-and-pepper noise: \\
\hspace*{1cm} $I(nim,i,j) = 0$ if $uniform(0,1) < 0.05$ \\
\hspace*{1cm} $I(nim,i,j) = 255$ if $uniform(0,1) > 1-0.05$ \\
\hspace*{1cm} $I(nim,i,j) = I(im,i,j)$ otherwise \\
\hspace*{1cm} $uniform(0,1)$: random variable uniformly distributed over [0,1]\\
\hspace*{1cm} try both 0.05 and 0.1 \\
\hspace*{1cm} =====zooma.pep.0.05.im===== \\
\hspace*{1cm} =====zooma.pep.0.1.im===== \\
3. Run box filter ($3 \times 3$, $5 \times 5$) on all noisy images \\
4. Run median filter ($3 \times 3$, $5 \times 5$) on all noisy images \\
5. Run opening followed by closing or closing followed by opening 

\vspace{1cm}
Project due Dec. 14 \\
Write programs to generate the following gradient magnitude images and choose
proper thresholds to get the binary edge images: \\
1. Roberts operator \\
2. Prewitt edge detector \\
3. Sobel edge detector \\
4. Frei and Chen gradient operator \\
5. Kirsch compass operator \\
6. Robinson compass operator \\
7. Nevatia-Babu 5X5 operator



\end{document}
