Chapter 6 Neighborhood Operators

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

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=====

N(r, c): set of neighboring pixel positions around position (r, c) general nonrecursive neighborhood operator ϕ : input f, output g

g(r, c) = ϕ[r, c, f(r′, c′) : (r′, c′) ∈ N(r, c)]

linear operator: one common nonrecursive neighborhood operator output: possibly position-dependent linear combination of inputs

g(r, c) = _{(r′,c′)∈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

cross-correlation of f with w: g = f ⊗ w

g(r, c) = _{(r′,c′)∈W,(r+r′,c+c′)∈F}^{∑} f(r + r′, c + c′)w(r′, c′)

w: weight function: kernel or mask of weights W: domain of w common 3 × 3 masks for noise cleaning, (a) box filter =====Fig. 6.2===== common 5 × 5 masks for noise cleaning =====Fig. 6.3===== application of mask with weights to image =====Fig. 6.5===== convolution of f with w: g = f ∗ w

g(r, c) = _{(r′,c′)∈W,(r−r′,c−c′)∈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

6.2 Symbolic Neighborhood Operators indexing of neighborhoods =====Fig. 6.7=====

6.2.1 Region-Growing Operator h: projection, outputs first or second argument

h(c, d) = \{ \begin{matrix}d & if c = g \\ c & if c ≠ g \end{matrix}

g: background background pixel labeled first nonbackground label

4-connected: a_{0} = x_{0}

a_{n} = h(a_{n−1}, x_{n}), n = 1, ..., 4

output y = a_{4}

8-connected: a_{0} = x_{0}

a_{n} = h(a_{n−1}, x_{n}), n = 1, ..., 8

output y = a_{8} =====Fig. 6.8=====

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=====

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) = \{ \begin{matrix}c & if c = d \\ g & if c ≠ d \end{matrix}

g: background border: has different neighbor and becomes background

4-connected: a_{0} = x_{0}

a_{n} = h(a_{n−1}, x_{n}), n = 1, ..., 4

output y = a_{4}

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=====

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(c, d) = \{ \begin{matrix}c & if c = d \\ b & if c ≠ d \end{matrix}

f: recognizes whether or not its argument is symbol b

f(c) = \{ \begin{matrix}b & if c = b \\ i & if c ≠ b \end{matrix}

4-connected: a_{0} = x_{0}

a_{n} = h(a_{n−1}, x_{n}), n = 1, ..., 4

output y = f(a_{4})

8-connected: a_{0} = x_{0}

a_{n} = h(a_{n−1}, x_{n}), n = 1, ..., 8

output y = f(a_{8})

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=====

Yokoi Connectivity Number 4-connectivity

h(b, c, d, e) = \{ \begin{matrix}q & if b = c and (d ≠ b or e ≠ b) \\ r & if b = c and (d = b and e = b) \\ s & if b ≠ c \end{matrix}

q: corner 1 → 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}) = \{ \begin{matrix}5 & if a_{1} = a_{2} = a_{3} = a_{4} = r \\ n & where n = #\{a_{k}|a_{k} = q\}, otherwise \end{matrix}

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=====

8-connectivity, only h slightly different

h(b, c, d, e) = \{ \begin{matrix}q & if b ≠ c and (d = b or e = b) \\ r & if b = c and (d = b and e = b) \\ t & if b = c and (d ≠ b and e = b) \\ s & otherwise \end{matrix}

q: center 1 and corner 0 → 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}) = \{ \begin{matrix}5 & if a_{1} = a_{2} = a_{3} = a_{4} = r \\ n & where n = #\{a_{k}|a_{k} = q\} and n ≠ 0 \\ 1 & n = 0 and m ≠ 0 where m = #\{a_{k}|a_{k} = t\} \\ 0 & n = 0 and m = 0 \end{matrix}

Rutovitz Connectivity Number Rutovitz connectivity: number of transitions from one symbol to another Rutovitz connectivity number: sometimes called crossing number

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=====

h: determines whether corner connected

h(b, c, d, e) = \{ \begin{matrix}1 & if b = c and (d ≠ b or e ≠ b) \\ 0 & otherwise \end{matrix}

f(a_{1}, a_{2}, a_{3}, a_{4}, x) = \{ \begin{matrix}g & if exactly one of a_{1}, a_{2}, a_{3}, a_{4} = 1 \\ x & otherwise \end{matrix}

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=====

6.2.7 Pair Relationship Operator pair relationship: nonrecursive operator, symbolic data domain h: determines whether first argument equals label 1

h(a, 1) = \{ \begin{matrix}1 & if a = 1 \\ 0 & otherwise \end{matrix}

4-connected mode, output y

y = \{ \begin{matrix}q & if ∑_{n=1}^{4} h(x_{n}, 1) < 1 or x_{0} ≠ 1 \\ p & if ∑_{n=1}^{4} h(x_{n}, 1) ≥ 1 and x_{0} = 1 \end{matrix}

q: not deletable if Yokoi number ≠ 1 or no neighbor 1 p: possibly deletable if Yokoi number 1 and some neighbor 1

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

6.2.9 Distance Transformation Operator distance transformation: produces distance to closest border pixel nonrecursive, iterative, start with

g g g g g g g
g g 0 0 0 0 g
g g 0 i i 0 g

... g: background 0: border, because distance to border is 0 i: interior pixels =====Fig. 6.16===== nth iteration: label with n all i with neighbor n − 1 equivalent algorithm: nonrecursive, iterative

h(a_{0}, ..., a_{N}) = \{ \begin{matrix}i & if a_{n} = i, n = 0, ..., N \\ min & \{b|for some n ≤ N, a_{n} ≠ i, b = a_{n} + 1\} \\ & if a_{0} = i and there exists n such that a_{n} ≠ i \\ a_{0} & if a_{0} ≠ i \end{matrix}

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})

distance transformation: produces distance to closest background recursive, two-pass first pass: left-right, top-bottom

h(a_{1}, ..., a_{N}; d) = \{ \begin{matrix}0 & if a_{N} = 0 \\ min\{a_{1}, ..., a_{N−1}\} + d & otherwise \end{matrix}

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

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

=====Fig. 6.16=====

6.2.10 Radius of Fusion The radius of fusion for any connected component of binary image I is the radius ρ of a disk satisfying the condition that if the binary image I is morphologically closed with a disk of radius ρ, then the given connected region will fuse with some other connected region

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) = \{ \begin{matrix}p^{m−1}(r, c) & if p^{m−1}(r, c) ≠ 0 \\ ∑_{(r′,c′)∈N} p^{m−1}(r − r′, c − c′) & if p^{m−1}(r, c) = 0 \end{matrix}

N: can be 4-neighborhood or 8-neighborhood p^{m−1}(r, c): nonzero, stays unchanged since shortest paths counted ∑: if zero then sum of neighboring shortest paths =====Fig. 6.17=====

6.3 Extremum-Related Neighborhood Operators

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 = \{ \begin{matrix}0 (flat) & if a_{4} = x_{0} = b_{4} \\ 1 (nonmaximum) & if a_{4} = x_{0} < b_{4} \\ 2 (nonminimum) & if a_{4} < x_{0} = b_{4} \\ 3 (transition) & if a_{4} < x_{0} < b_{4} \end{matrix}

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) = \{ \begin{matrix}max\{d, e\} & if c ≥ b \\ d & if c < b \end{matrix}

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 and 2

=====Fig. 6.20=====

6.3.3 Reachability Operator successively propagating labels that can reach by monotonic paths descending reachability operator employs h

h(a, b, x, y) = \{ \begin{matrix}a & if (b = g or a = b) and x < y \\ b & if a = g and x < y \\ c & if a ≠ g, b ≠ g, a ≠ b, and x < y \\ a & if x > y \end{matrix}

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 and 2

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 ⇒^{max} 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 ⇒^{region} 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

⇒^{g} \begin{matrix}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{matrix} ⇒^{reachable} \begin{matrix}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{matrix}

=====joke=====

6.4 Linear Shift-Invariant Neighborhood Operators convolution: commutative, associative, distributor over sums, homogeneous

6.4.1 Convolution and Correlation convolution of an image f with kernel w

(f ∗ u)(r, c) = _{(r′,c′)∈W,(r−r′,c−c′)∈F}^{∑} f(r − r′, c − c′)w(r′, c′)

=====Fig. 6.21===== w: impulse response function: point spread function

6.4.2 Separability straightforward computation: (2M + 1) × (2N + 1) multiplications, additions decomposition: (2M + 1) + (2N + 1) multiplications, additions =====Fig. 6.22=====

Project due Nov. 16 Write a program to generate Yokoi connectivity number

Project due Nov. 30 Write a program to generate thinned image

Midterm Nov. 23 extent: whatever covered up to Nov. 16 (inclusive)