Chapter 8 The Facet Model

8.1 Introduction

facet model: image as continuum or piecewise continuous intensity surface

observed digital image: noisy, discretized sampling of distorted version

general forms:

- piecewise constant (flat facet model), ideal region: constant gray level
- piecewise linear (sloped facet model), ideal region: sloped plane gray level
- piecewise quadratic, gray level surface: bivariate quadratic
- piecewise cubic, gray level surface: cubic surfaces

8.2 Relative Maxima

relative maxima: first derivative zero, second derivative negative

8.3 Sloped Facet Parameter and Error Estimation

least-squares procedure: to estimate sloped facet parameter, noise variance

1#1

122#122: image function

31#31: row

48#48: column

2#2: slope in row direction

3#3: slope in column direction

4#4: bias

5#5: noise having mean 0 and variance 6#6

8.4 Facet-Based Peak Noise Removal

peak noise pixel: gray level intensity significantly differs from neighbors

(a) peak noise pixel, (b) not

=====Fig. 8.1=====

8.5 Iterated Facet Model

facets: image spatial domain partitioned into connected regions

facets: satisfy certain gray level and shape constraints

facets: gray levels as polynomial function of row-column coordinates

8.6 Gradient-Based Facet Edge Detection

gradient-based facet edge detection: high values in first partial derivative

8.7 Bayesian Approach to Gradient Edge Detection

The Bayesian approach to the decision of whether or not an observed gradient
magnitude 7#7 is statistically significant and therefore participates in some
edge is to decide there is an edge (statistically significant gradient)
when,

8#8

9#9: given gradient magnitude, conditional probability of edge

10#10: given gradient magnitude, conditional probability of nonedge

11#11

12#12

13#13

possible to infer 14#14 from observed image data

15#15

16#16

17#17

8.8 Zero-Crossing Edge Detector

gradient edge detector: looks for high values of first derivatives

zero-crossing edge detector: looks for relative maxima in first derivative

zero-crossing: pixel as edge if zero crossing of second directional derivative

underlying gray level intensity function 4#4 takes the form

18#18

8.8.1 Discrete Orthogonal Polynomials

discrete orthogonal polynomial basis set of size 67#67: polynomials deg. 19#19

discrete Chebyshev polynomials: these unique polynomials

20#20

21#21

22#22

23#23: orthogonal to 24#24, thus

25#25

discrete orthogonal polynomials can be recursively generated

26#26

27#27

28#28

29#29

30#30

31#31

8.8.2 Two-Dimensional Discrete Orthogonal Polynomials

2-D discrete orthogonal polynomials creatable from tensor products of 1D

from above equations

32#32

8.8.3 Equal-Weighted Least-Squares Fitting Problem

weight

33#33

e.g. 31#31: row, 48#48: column, 34#34: 35#35 numerator, 36#36 denominator

=====Fig. 8.8=====

8.8.4 Directional Derivative Edge Finder

We define the directional derivative edge finder as the operator that places
an edge in all pixels having a negatively sloped zero crossing of the second
directional derivative taken in the direction of the gradient

31#31: row

48#48: column

64#64: radius in polar coordinate

2#2: angle in polar coordinate, clockwise from column axis

37#37

directional derivative of 4#4 at point 2#2 in direction 2#2:

38#38

39#39

second directional derivative of 4#4 at point 2#2 in direction 2#2:

40#40

41#41

42#42

8.9 Integrated Directional Derivative Gradient Operator

integrated directional derivative gradient operator: more accurate

step edge direction

=====joke=====

8.10 Corner Detection

corners: to detect buildings in aerial images

corner points: to determine displacement vectors from image pair

gray scale corner detectors: detect corners directly by gray scale image

8.11 Isotropic Derivative Magnitudes

gradient edge: from first-order isotropic derivative magnitude

8.12 Ridges and Ravines on Digital Images

A digital ridge (ravine) occurs on a digital image when there is a simply
connected sequence of pixels with gray level intensity values that are
significantly higher (lower) in the sequence than those neighboring
the sequence.

ridges, ravines: from bright, dark lines or reflection, variation ...

8.13 Topographic Primal Sketch

8.13.1 Introduction

The basis of the topographic primal sketch consists of the labeling and
grouping of the underlying image-intensity surface patches according to
the categories defined by monotonic, gray level, and invariant functions of
directional derivatives.

categories:

- peak
- pit
- ridge
- ravine
- saddle
- flat
- hillside

Invariance Requirement

histogram normalization, equal probability quantization: nonlinear, enhancing

peak, pit, ridge, valley, saddle, flat, hillside: have required invariance

Background

primal sketch: rich description of gray level changes present in image

description: includes type, position, orientation, fuzziness of edge

topographic primal sketch: two-dimensional gray level variations

8.13.2 Mathematical Classification of Topographic Structures

topographic structures: invariant under monotonically increasing intensity tran.

Peak

peak: knob: local maximum in all directions

=====Fig. 8.24=====

peak: curvature downward in all directions

at peak: gradient zero

at peak: second directional derivative negative in all directions

point classified as peak if

43#43

44#44: gradient magnitude

45#45: second directional derivative in 46#46 direction

47#47: second directional derivative in 48#48 direction

Pit

pit: sink: bowl: local minimum in all directions

pit: gradient zero, second directional derivative positive

49#49

Ridge

ridge: occurs on ridge line

ridge line: a curve consisting of a series of ridge points

walk along ridge line: points to the right and left are lower

ridge line: may be flat, sloped upward, sloped downward, curved upward,...

ridge: local maximum in one direction

=====Fig. 8.25=====

50#50

51#51

52#52

Ravine

ravine: valley: local minimum in one direction

walk along ravine line: points to the right and left are higher

53#53

54#54

55#55

Saddle

saddle: local maximum in one direction, local minimum in perpendicular dir.

saddle: positive curvature in one direction, negative in perpendicular dir.

saddle: gradient magnitude zero

saddle: extrema of second directional derivative have opposite signs

56#56

Flat

flat: plain: simple, horizontal surface

=====Fig. 8.26=====

flat: zero gradient, no curvature

57#57

flat: foot or shoulder or not qualified at all

foot: flat begins to turn up into a hill

shoulder: flat ending and turning down into a hill

=====joke=====

Hillside

hillside point: anything not covered by previous categories

hillside: nonzero gradient, no strict extrema

slope: tilted flat (constant gradient)

58#58

convex hill: curvature positive (upward)

59#59

concave hill: curvature negative (downward)

60#60

saddle hill: up in one direction, down in perpendicular direction

61#61

inflection point: zero crossing of second directional derivative

Summary of the Topographic Categories

mathematical properties of topographic structures on continuous surfaces

=====Table 8.5=====

Invariance of the Topographic Categories

topographic labels: invariant under monotonically increasing gray level tran.

monotonically increasing: positive derivative everywhere

Ridge and Ravine Continua

entire areas of surface: may be classified as all ridge or all ravine

8.13.3 Topographic Classification Algorithm

peak, pit, ridge, ravine, saddle: likely not to occur at pixel center

peak, pit, ridge, ravine, saddle: if within pixel area, carry the label

Case One: No Zero Crossing

no zero crossing along either of two directions: flat or hillside

no zero crossing: if gradient zero, then flat

no zero crossing: if gradient nonzero, then hillside

hillside: possibly inflection point, slope, convex hill, concave hill,...

=====Table 8.6=====

Case Two: One Zero Crossing

one zero crossing: peak, pit, ridge, ravine, or saddle

=====Table 8.7=====

Case Three: Two Zero Crossings

LABEL1, LABEL2: assign label to each zero crossing

=====Table 8.8=====

Case Four: More Than Two Zero Crossing

more than two zero crossings: choose the one closest to pixel center

more than two zero crossings: after ignoring the other, same as case 3

8.13.4 Summary of Topographic Classification Scheme

one pass through the image, at each pixel

- calculate fitting coefficients, 62#62 through 63#63 of cubic polynomial
- Use above coefficients to find gradient, gradient magnitude, eigenvalues, ...
- search in eigenvector direction for zero crossing of first derivative
- recompute gradient, gradient magnitude, second derivative, then classify

Previous Work

web representation [Hsu et al. 1978]: axes divide image into regions

Project due Dec. 21

Write the following programs to detect edge:

~~1.~~ zero-crossing on the following four types of ~~images~~(methods) to get edge images
(choose proper thresholds), p. 349

~~2.~~1. Laplacian, Fig. 7.33

~~3.~~2. minimum-variance Laplacian, Fig. 7.36

~~4.~~3. Laplacian of Gaussian, Fig. 7.37

~~5.~~4. Difference of Gaussian, (use tk to generate D.O.G.)

D. Marr, *Vision*, W.H. Freeman, San Francisco, p.54-74,
1982.

=====Marr, *Vision*, Fig. 2.9=====

=====Marr, *Vision*, Fig. 2.16=====

dog (inhibitory 64#64, excitatory 65#65, kernel size=11)

2001-09-19 Counter:

FastCounter by bCentral