chapter6

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

1#1: set of neighboring pixel positions around position 2#2
general nonrecursive neighborhood operator 3#3 : input 4#4, output 122#122

5#5

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

6#6

shift-invariant: position invariant: action same regardless of position
composition of shift-invariant operators: shift-invariant

cross-correlation of 4#4 with 7#7: 8#8

9#9

7#7: weight function: kernel or mask of weights
10#10: domain of 7#7
common 11#11 masks for noise cleaning, (a) box filter
=====Fig. 6.2=====
common 12#12 masked for noise cleaning
=====Fig. 6.3=====
application of mask with weights to image
=====Fig. 6.5=====

convolution of 4#4 with 7#7: 13#13

14#14

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
15#15: projection, outputs first or second argument

16#16

122#122: background
background pixel labeled first nonbackground label

4-connected: 17#17

18#18

output 19#19

8-connected: 17#17

20#20

output 21#21
=====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
15#15: whether or not arguments identical

22#22

122#122: background
border: has different neighbor and becomes background

4-connected: 17#17

18#18

output 19#19

8-connected: 17#17

20#20

output 21#21
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 76#76 and all border pixels with the label 23#23
15#15: whether or not arguments identical

24#24

4#4: recognizes whether or not its argument is symbol 23#23

25#25

4-connected: 17#17

18#18

output 26#26

8-connected: 17#17

20#20

output 27#27

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

28#28

29#29: corner 30#30 transition
31#31: corner all 1, no transition
32#32: center 1, neighbor 0, nothing will happen

33#33

5: no transition, all 8 neighbors 1, thus interior
148#148: 1 transition generates one connected component if center removed
connectivity number 34#34

35#35

36#36

37#37

38#38

=====Fig. 6.12=====
=====lena.64x64=====
=====lena.yokoi=====

8-connectivity, only 15#15 slightly different

39#39

29#29: center 1 and corner 40#40 transition
31#31: corner no transition, all 1
41#41: itself and two 4-neighbors 1, corner 0

42#42

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

15#15: determines whether corner connected

43#43

44#44

122#122: background
output symbol 45#45

35#35

36#36

37#37

38#38

=====Fig. 6.14=====

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

46#46

4-connected mode, output 47#47

48#48

29#29: not deletable if Yokoi number 49#49 1 or no neighbor 1
50#50: 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

...

122#122: background
51#51: border, because distance to border is 0
76#76: interior pixels
=====Fig. 6.16=====
148#148th iteration: label with 148#148 all 76#76 with neighbor 52#52

equivalent algorithm: nonrecursive, iterative

53#53

76#76: if no neighbor labeled, still interior, leave it alone
54#54: 17#17 self interior but neighbor labeled
55#55: already labeled, won't change value since later route farther
4-connected: output 56#56

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

57#57

51#51: if background still background, since 58#58
54#54: min of upper and left neighbors and add 59#59
4-connected: output 60#60
second pass: right-left, bottom-up

61#61

4-connected: output 62#62
after pass 1

0	0	0	0	0
0	1	1	1	1
0	1	2	2	2
1	2	3	3	3
0	1	2	3	4
0	1	2	3	4
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 63#63 is the radius 64#64 of a disk satisfying the condition that if the binary image 63#63 is morphologically closed with a disk of radius 64#64, 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 65#65

66#66

67#67: can be 4-neighborhood or 8-neighborhood
68#68: nonzero, stays unchanged since shortest paths counted
69#69: 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: 70#70

71#71

72#72

output pixel

73#73

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 15#15 and max

74#74

75#75: use new maximum value when ascending
4#4: keep original maximum when descending
4-connected, output 76#76

77#77

78#78

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

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

79#79

122#122: pixels that are not relative extrema labeled background
80#80: unchanged when neighbor is 122#122 or the same with neighbor
23#23: become first propagated label if originally 122#122
48#48: common region: more than one extremum can reach it by monotonic path
48#48: already labeled and neighbor has different label, then two extrema reach
80#80: propagate from extremum
4-connected, output 76#76

77#77

81#81

82#82

83#83

=====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 4#4 with kernel 7#7

84#84

=====Fig. 6.21=====
7#7: impulse response function: point spread function

6.4.2 Separability
straightforward computation: 85#85 multiplications, additions
decomposition: 86#86 multiplications, additions
=====Fig. 6.22=====

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

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