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

Midterm Nov. 27

extent: whatever covered up to Nov. 20 (inclusive)

2001-09-19 Counter:

FastCounter by bCentral