\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$}}
\begin{document}
\bibliographystyle{plain}

\Huge
\begin{center}
Chapter 6 Neighborhood Operators
\end{center}

\LARGE
6.1 Introduction \\
neighborhood operator: workhorse of low-level vision \\
neighborhood operator: performs conditioning, labeling, grouping 

\vspace{1cm}
The output of a neighborhood operator at a given pixel position is a function
of the position, of the input pixel value at the position, of the values of the
input pixels in some neighborhood around the given input position, and possibly
of some values of previously generated output pixels. \\
numeric domain: arithmetic operations, +, -, min, max \\
symbolic domain: Boolean operations, AND, OR, NOT, table-look-up \\
nonrecursive neighborhood operators: output is function of input \\
recursive neighborhood operators: output depends partly on previous output \\ 
neighborhood might be small and asymmetric or large \\
=====Fig. 6.1=====

\vspace{1cm}
\noindent
$N(r,c)$: set of neighboring pixel positions around position $(r,c)$ \\
general nonrecursive neighborhood operator $\phi$ : input $f$, output $g$
\[
g(r,c)=\phi [ r,c,f(r',c'): (r',c') \in N(r, c)]
\]

\vspace{1cm}
\noindent
linear operator: one common nonrecursive neighborhood operator \\
output: possibly position-dependent linear combination of inputs
\[
g(r,c) = \sum_{(r',c') \in N(r,c)} f(r',c')w(r',c',r,c)
\]
shift-invariant: position invariant: action same regardless of position \\
composition of shift-invariant operators: shift-invariant  

\vspace{1cm}
\noindent
cross-correlation of $f$ with $w$: $g = f \otimes w$
\[
g(r,c) = \sum_{(r',c') \in W, (r+r', c+c') \in F} f(r+r', c+c')w(r',c')
\]
$w$: weight function: kernel or mask of weights \\
$W$: domain of $w$  \\
common $3 \times 3 $ masks for noise cleaning, (a) box filter \\
=====Fig. 6.2===== \\
common $5 \times 5$ masks for noise cleaning \\
=====Fig. 6.3===== \\
application of mask with weights to image \\
=====Fig. 6.5=====

\vspace{1cm}
\noindent
convolution of $f$ with $w$: $g = f * w$
\[
g(r,c) = \sum_{(r',c') \in W, (r-r', c-c') \in F} f(r-r', c-c')w(r',c')
\]
convolution: close relative to cross-correlation \\
convolution: linear shift-invariant \\
if mask symmetric, convolution and correlation the same

\vspace{1cm}
6.2 Symbolic Neighborhood Operators \\
indexing of neighborhoods \\
=====Fig. 6.7=====

\vspace{1cm}
6.2.1 Region-Growing Operator \\
$h$: projection, outputs first or second argument 
\[
h(c,d) = \left\{
\begin{array}{l l}
d & {\rm \ if \ } c = g \\
c & {\rm \ if \ } c \neq g 
\end{array}
\right.
\]
$g$: background \\
background pixel labeled first nonbackground label 

\vspace{1cm}
\noindent
4-connected: $a_0 = x_0$
\[
a_n = h(a_{n-1}, x_n), \ \ \ n = 1, ..., 4
\]
output $y=a_4$

\vspace{1cm}
\noindent
8-connected: $a_0 = x_0$
\[
a_n = h(a_{n-1}, x_n), \ \ \ n = 1, ..., 8
\]
output $y=a_8$ \\
=====Fig. 6.8=====

\vspace{1cm}
6.2.2 Nearest Neighbor Sets and Influence Zones \\
influence zones: nearest neighbor sets \\
influence zones: iteratively region-growing \\
4-neighborhood for city-block distance \\
8-neighborhood for max distance (of horizontal and vertical distances) \\
alternate 4, 8-neighborhood for Euclidean distance \\
=====joke=====

\vspace{1cm}
6.2.3 Region-Shrinking Operator \\
region-shrinking: changes all border pixels to background \\
region-shrinking: can change connectivity \\
region-shrinking: can entirely delete region if repeatedly applied \\
$h$: whether or not arguments identical
\[
h(c,d) = \left\{
\begin{array}{l l}
c & {\rm \ if \ } c = d \\
g & {\rm \ if \ } c \neq d 
\end{array}
\right.
\]
$g$: background \\
border: has different neighbor and becomes background

\vspace{1cm}
\noindent
4-connected: $a_0 = x_0$
\[
a_n = h(a_{n-1}, x_n), \ \ \ n = 1, ..., 4
\]
output $y=a_4$

\vspace{1cm}
\noindent
8-connected: $a_0 = x_0$
\[
a_n = h(a_{n-1}, x_n), \ \ \ n = 1, ..., 8
\]
output $y=a_8$ \\
region shrinking: related to binary erosion except on labeled region \\
=====Fig. 6.9=====

\vspace{1cm}
6.2.4 Mark-Interior/Border-Pixel Operator \\
mark-interior/border-pixel operator marks all interior pixels with the label
$i$ and all border pixels with the label $b$ \\
$h$: whether or not arguments identical
\[
h(c,d) = \left\{
\begin{array}{l l}
c & {\rm \ if \ } c = d \\
b & {\rm \ if \ } c \neq d 
\end{array}
\right.
\]
$f$: recognizes whether or not its argument is symbol $b$
\[
f(c) = \left\{
\begin{array}{l l}
b & {\rm \ if \ } c = b \\
i & {\rm \ if \ } c \neq b 
\end{array}
\right.
\]


\vspace{1cm}
\noindent
4-connected: $a_0 = x_0$
\[
a_n = h(a_{n-1}, x_n), \ \ \ n = 1, ..., 4
\]
output $y=f(a_4)$

\vspace{1cm}
\noindent
8-connected: $a_0 = x_0$
\[
a_n = h(a_{n-1}, x_n), \ \ \ n = 1, ..., 8
\]
output $y=f(a_8)$ 

\vspace{1cm}
6.2.5 Connectivity Number Operator \\
connectivity number: nonrecursive and symbolic data domain \\
connectivity number: classify the way pixel connected to neighbors \\
six values of connectivity: five for border, one for interior \\
border: isolated, edge, connected, branching, crossing \\
=====Fig. 6.10===== \\
corner neighborhood \\
=====Fig. 6.11=====

\vspace{1cm}
Yokoi Connectivity Number \\
4-connectivity
\[
h(b,c,d,e) = \left\{
\begin{array}{l l}
q & {\rm \ if \ } b = c {\rm \ and \ } (d \neq b {\rm \ or \ } e \neq b)\\
r & {\rm \ if \ } b = c {\rm \ and \ } (d = b {\rm \ and \ } e = b)\\
s & {\rm \ if \ } b \neq c 
\end{array}
\right.
\]
$q$: corner $1 \rightarrow 0$ transition \\
$r$: corner all 1, no transition \\
$s$: center 1, neighbor 0, nothing will happen
\[
f(a_1, a_2, a_3, a_4) = \left\{
\begin{array}{l l}
5 & {\rm \ if \ } a_1 = a_2 = a_3 = a_4 = r \\
n & {\rm \ where \ } n = \#\{a_k|a_k=q\}, {\rm \ otherwise \ }
\end{array}
\right.
\]
5: no transition, all 8 neighbors 1, thus interior \\
$n$: 1 transition generates one connected component if center removed \\
connectivity number $y=f(a_1, a_2, a_3, a_4)$
\[
a_1 = h(x_0, x_1, x_6, x_2)
\]
\[
a_2 = h(x_0, x_2, x_7, x_3)
\]
\[
a_3 = h(x_0, x_3, x_8, x_4)
\]
\[
a_4 = h(x_0, x_4, x_5, x_1)
\]
=====Fig. 6.12===== \\
=====lena.64x64===== \\
=====lena.yokoi=====

\vspace{1cm}
\noindent
8-connectivity, only $h$ slightly different 
\[
h(b,c,d,e) = \left\{
\begin{array}{l l}
q & {\rm \ if \ } b \neq c {\rm \ and \ } (d = b {\rm \ or \ } e = b)\\
r & {\rm \ if \ } b = c {\rm \ and \ } (d = b {\rm \ and \ } e = b)\\
t & {\rm \ if \ } b = c {\rm \ and \ } (d \neq b {\rm \ and \ } e = b)\\
s & {\rm \ otherwise }
\end{array}
\right.
\]
$q$: center 1 and corner $0 \rightarrow 1$ transition \\
$r$: corner no transition, all 1 \\
$t$: itself and two 4-neighbors 1, corner 0
\[
f(a_1, a_2, a_3, a_4) = \left\{
\begin{array}{l l}
5 & {\rm \ if \ } a_1 = a_2 = a_3 = a_4 = r \\
n & {\rm \ where \ } n = \#\{a_k|a_k=q\} {\rm \ and \ } n \neq 0 \\
1 & n=0 {\rm \ and \ } m \neq 0 {\rm \ where \ } m = \#\{a_k|a_k=t\}  \\
0 & n=0 {\rm \ and \ } m =0
\end{array}
\right.
\]

\vspace{1cm}
Rutovitz Connectivity Number \\
Rutovitz connectivity: number of transitions from one symbol to another \\
Rutovitz connectivity number: sometimes called crossing number

\vspace{1cm}
6.2.6 Connected Shrink Operator \\
connected shrink: recursive operator, symbolic data domain \\
connected shrink: deletes border pixels without disconnecting regions \\
top-down, left-right scan: deletes edge pixels not right-boundary \\
=====Fig. 6.13=====

\vspace{1cm}
$h$: determines whether corner connected 
\[
h(b,c,d,e) = \left\{
\begin{array}{l l}
1 & {\rm \ if \ } b = c {\rm \ and \ } (d \neq b {\rm \ or \ } e \neq b)\\
0 & {\rm \ otherwise }
\end{array}
\right.
\]
\[
f(a_1,a_2,a_3,a_4,x) = \left\{
\begin{array}{l l}
g & {\rm \ if \ exactly\ one \ of \ } a_1, a_2, a_3, a_4 = 1 \\
x & {\rm \ otherwise }
\end{array}
\right.
\]
$g$: background \\
output symbol $y=f(a_1, a_2, a_3, a_4, x_0)$
\[
a_1 = h(x_0, x_1, x_6, x_2)
\]
\[
a_2 = h(x_0, x_2, x_7, x_3)
\]
\[
a_3 = h(x_0, x_3, x_8, x_4)
\]
\[
a_4 = h(x_0, x_4, x_5, x_1)
\]
=====Fig. 6.14=====

\vspace{1cm}
6.2.7 Pair Relationship Operator \\
pair relationship: nonrecursive operator, symbolic data domain \\
$h$: determines whether first argument equals label 1 
\[
h(a,1) = \left\{
\begin{array}{l l}
1 & {\rm \ if \ } a = 1  \\
0 & {\rm \ otherwise }
\end{array}
\right.
\]
4-connected mode, output $y$
\[
y = \left\{
\begin{array}{l l}
q & {\rm \ if \ } \sum_{n=1}^4 h(x_n, 1) < 1 {\rm \ or \ } x_0 \neq 1  \\
p & {\rm \ if \ } \sum_{n=1}^4 h(x_n, 1) \geq 1 {\rm \ and \ } x_0 = 1
\end{array}
\right.
\]
$q$: not deletable if Yokoi number $\neq$ 1 or no neighbor 1 \\
$p$: possibly deletable if Yokoi number 1 and some neighbor 1 

\vspace{1cm}
6.2.8 Thinning Operator \\
thinning operator is composition of three operators: Yokoi connectivity,
pair relationship, connected shrink \\
=====Fig. 6.15===== \\
=====lena.thin===== \\
=====joke=====

\vspace{1cm}
6.2.9 Distance Transformation Operator \\
distance transformation: produces distance to closest border pixel \\
nonrecursive, iterative, start with \\
\begin{tabular}{l l l l l l l}
g & g & g & g & g & g & g \\
g & g & 0 & 0 & 0 & 0 & g \\
g & g & 0 & i & i & 0 & g \\
... \\
\end{tabular} \\
$g$: background \\
$0$: border, because distance to border is 0 \\
$i$: interior pixels \\
=====Fig. 6.16===== \\
$n$th iteration: label with $n$ all $i$ with neighbor $n-1$

\vspace{1cm}
\noindent
equivalent algorithm: nonrecursive, iterative
\[
h(a_0,...,a_N) = \left\{
\begin{array}{l l}
i & {\rm \ if \ } a_n = i, n = 0,...,N  \\
\min & \{b| {\rm for \ some \ } n \leq N, a_n \neq i, b = a_n+1\}  \\
  &     {\rm \ if \ } a_0 = i {\rm \ and \ there \ exists \ } n {\rm \ such \ 
     that \ } a_n \neq i \\
a_0 & {\rm \ if \ } a_0 \neq i
\end{array}
\right.
\]
$i$: if no neighbor labeled, still interior, leave it alone \\
$\min$: $a_0=x_0$ self interior but neighbor labeled \\
$a_0$: already labeled, won't change value since later route farther \\
4-connected: output $y=h(x_0, x_1, x_2, x_3, x_4)$

\vspace{1cm}
\noindent
distance transformation: produces distance to closest background \\
recursive, two-pass \\
first pass: left-right, top-bottom
\[
h(a_1,...,a_N;d) = \left\{
\begin{array}{l l}
0 & {\rm \ if \ } a_N = 0 \\
\min \{ a_1,...,a_{N-1}\}+d  & {\rm \ otherwise }
\end{array}
\right.
\]
$0$: if background still background, since $a_N = x_0$ \\
$\min$: min of upper and left neighbors and add $d=1$ \\
4-connected: output $y=h(x_2, x_3, x_0; 1)$ \\
second pass: right-left, bottom-up 
\[
g(a_1,...,a_N;d) = \min \{ a_1,...,a_N\} + d
\]
4-connected: output $y=\min\{x_0, g(x_1,x_4;1)\}$ \\
after pass 1 \\
\begin{tabular}{l l l l l l l}
0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 1 & 1 & 0 \\
0 & 0 & 1 & 2 & 2 & 2 & 0 \\
0 & 1 & 2 & 3 & 3 & 3 & 0 \\
0 & 0 & 1 & 2 & 3 & 4 & 0 \\
0 & 0 & 1 & 2 & 3 & 4 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 \\
\end{tabular} \\
=====Fig. 6.16=====

\vspace{1cm}
6.2.10 Radius of Fusion \\
The radius of fusion for any connected component of binary image $I$ is the
radius $\rho$ of a disk satisfying the condition that if the binary image
$I$ is morphologically closed with a disk of radius $\rho$, then the given
connected region will fuse with some other connected region

\vspace{1cm}
6.2.11 Number of Shortest Paths \\
number of shortest paths for each 0-pixel: to binary-1 pixel set \\
given binary image $p^0(r, c)$
\[
p^m(r,c) = \left\{
\begin{array}{l l}
p^{m-1}(r,c) & {\rm \ if \ } p^{m-1}(r,c) \neq 0 \\
\sum_{(r',c') \in N} p^{m-1}(r-r', c-c')  & {\rm \ if \ } p^{m-1}(r,c) = 0
\end{array}
\right.
\]
$N$: can be 4-neighborhood or 8-neighborhood \\
$p^{m-1}(r,c)$: nonzero, stays unchanged since shortest paths counted \\
$\sum$: if zero then sum of neighboring shortest paths \\
=====Fig. 6.17=====

\vspace{1cm}
6.3 Extremum-Related Neighborhood Operators 

\vspace{1cm}
6.3.1 Non-Minima-Maxima Operator \\
non-minima-maxima: nonrecursive operator, symbolic output \\
a pixel can be neighborhood maximum not relative maximum \\
=====Fig. 6.18===== \\
4-connected: $a_0=b_0=x_0 $
\[
a_n=\min\{a_{n-1}, x_n\} \ \ \ n = 1,2,3,4
\]
\[
b_n=\max\{b_{n-1}, x_n\} \ \ \ n = 1,2,3,4
\]
output pixel
\[
l = \left\{
\begin{array}{l l}
0 \ ({\rm flat}) & {\rm \ if \ } a_4 = x_0 = b_4 \\
1 \ ({\rm nonmaximum}) & {\rm \ if \ } a_4 = x_0 < b_4 \\
2 \ ({\rm nonminimum}) & {\rm \ if \ } a_4 < x_0 = b_4 \\
3 \ ({\rm transition}) & {\rm \ if \ } a_4 < x_0 < b_4 \\
\end{array}
\right.
\]

\vspace{1cm}
6.3.2 Relative Extrema Operator \\
relative extrema operators: relative maximum and minimum operators \\
relative extrema: recursive operator, numeric data domain \\
relative extrema: input not changed, output successively modified \\
top-down, left-right scan, then bottom-up, right-left scan until no change \\
output: value of highest extrema reachable by monotonic path \\
relative extrema pixels: output same as input pixels \\
pixel designations for the normal and reverse scans \\
=====Fig. 6.19===== \\
two primitive functions $h$ and max 
\[
h(b,c,d,e) = \left\{
\begin{array}{l l}
\max\{d,e\} & {\rm \ if \ } c \geq b \\
d & {\rm \ if \ } c < b 
\end{array}
\right.
\]
$\max\{d,e\}$: use new maximum value when ascending \\
$d$: keep original maximum when descending \\
4-connected, output $l = a_2$
\[
a_0 = l_0
\]
\[
a_n = h(x_0, x_n, a_{n-1}, l_n), \ \ \ n = 1 {\rm \ and \ } 2
\]
=====Fig. 6.20=====

\vspace{1cm}
6.3.3 Reachability Operator \\
successively propagating labels that can reach by monotonic paths \\
descending reachability operator employs $h$
\[
h(a,b,x,y) = \left\{
\begin{array}{l l}
a & {\rm \ if \ } (b=g {\rm \ or \ } a = b) {\rm \ and \ } x < y \\
b & {\rm \ if \ } a=g {\rm \ and \ } x < y \\
c & {\rm \ if \ } a \neq g, b \neq g, a \neq b, {\rm \ and \ } x < y \\
a & {\rm \ if \ } x > y 
\end{array}
\right.
\]
$g$: pixels that are not relative extrema labeled background \\
$a$: unchanged when neighbor is $g$ or the same with neighbor \\
$b$: become first propagated label if originally $g$ \\
$c$: common region: more than one extremum can reach it by monotonic path \\
$c$: already labeled and neighbor has different label, then two extrema reach\\
$a$: propagate from extremum \\
4-connected, output $l = a_2$
\[
a_0 = l_0
\]
\[
a_n = h(a_{n-1}, l_n, x_0, x_n), \ \ \ n = 1 {\rm \ and \ } 2
\]
\[
\begin{array}{ccccccc}
9 & 2 & 1 & 2 & 3 & 3 & 1 \\
2 & 1 & 2 & 3 & 3 & 1 & 2 \\
1 & 2 & 3 & 3 & 1 & 2 & 3 \\
2 & 3 & 3 & 1 & 2 & 3 & 9
\end{array} \stackrel{\rm max}{\Rightarrow}
\begin{array}{ccccccc}
9 & 9 & 9 & 3 & 3 & 3 & 9 \\
9 & 9 & 3 & 3 & 3 & 9 & 9 \\
9 & 3 & 3 & 3 & 9 & 9 & 9 \\
3 & 3 & 3 & 9 & 9 & 9 & 9
\end{array} \stackrel{\rm region}{\Rightarrow}
\begin{array}{ccccccc}
1 & 1 & 1 & 2 & 2 & 2 & 3 \\
1 & 1 & 2 & 2 & 2 & 3 & 3 \\
1 & 2 & 2 & 2 & 3 & 3 & 3 \\
2 & 2 & 2 & 3 & 3 & 3 & 3
\end{array} 
\]

\[
\stackrel{g}{\Rightarrow}
\begin{array}{ccccccc}
1 & g & g & g & 2 & 2 & g \\
g & g & g & 2 & 2 & g & g \\
g & g & 2 & 2 & g & g & g \\
g & 2 & 2 & g & g & g & 3
\end{array} \stackrel{\rm reachable}{\Rightarrow}
\begin{array}{ccccccc}
1 & 1 & c & 2 & 2 & 2 & c \\
1 & c & 2 & 2 & 2 & c & 3 \\
c & 2 & 2 & 2 & c & 3 & 3 \\
2 & 2 & 2 & c & 3 & 3 & 3
\end{array} 
\]
=====joke=====


\vspace{1cm}
6.4 Linear Shift-Invariant Neighborhood Operators \\
convolution: commutative, associative, distributor over sums, homogeneous

\vspace{1cm}
6.4.1 Convolution and Correlation \\
convolution of an image $f$ with kernel $w$
\[
(f * u)(r,c) = \sum_{(r',c') \in W, (r-r', c-c') \in F} f(r-r', c-c')w(r',c')
\]
=====Fig. 6.21===== \\
$w$: impulse response function: point spread function

\vspace{1cm}
6.4.2 Separability \\
straightforward computation: $(2M+1)\times(2N+1)$ multiplications, additions \\
decomposition: $(2M+1)+(2N+1)$ multiplications, additions \\
=====Fig. 6.22=====






\vspace{1cm}
Project due Nov. 16 \\
Write a program to generate Yokoi connectivity number 

\vspace{1cm}
Project due Nov. 30 \\
Write a program to generate thinned image 

\vspace{1cm}
Midterm Nov. 23 \\
extent: whatever covered up to Nov. 16 (inclusive)

\end{document}
