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:

  1. piecewise constant (flat facet model), ideal region: constant gray level
  2. piecewise linear (sloped facet model), ideal region: sloped plane gray level
  3. piecewise quadratic, gray level surface: bivariate quadratic
  4. 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:

topographic primal sketch: rich, hierarchical, structurally complete rep.




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

  1. calculate fitting coefficients, 62#62 through 63#63 of cubic polynomial
  2. Use above coefficients to find gradient, gradient magnitude, eigenvalues, ...
  3. search in eigenvector direction for zero crossing of first derivative
  4. recompute gradient, gradient magnitude, second derivative, then classify
=====Garfield 17:8=====




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