\documentstyle[12pt]{article}
\setlength{\textwidth}{9.75 in}
\setlength{\evensidemargin}{-0.4 in}
\setlength{\oddsidemargin}{-0.4  in}
\setlength{\textheight}{7.2 in}
\setlength{\topmargin}{-1.05 in}
\setlength{\arraycolsep}{9pt}
\renewcommand{\baselinestretch}{1.0}
\newcommand{\psfuh}    {/u/vision/fuh/document/}
\newcommand{\open}{\mbox{\Large $\circ$}}
\newcommand{\close}{\mbox{\Large $\bullet$}}
\input{psfig}
\newcommand{\epsfig}[1]{\psfig{#1}}
\begin{document}
\bibliographystyle{plain}

\Huge
\begin{center}
Chapter 8 The Facet Model
\end{center}

\LARGE
8.1 Introduction \\
facet model: image as continuum or piecewise continuous intensity surface \\
observed digital image: noisy, discretized sampling of distorted version \\
general forms:
\begin{enumerate}
\item piecewise constant (flat facet model), ideal region: constant gray level 
\item piecewise linear (sloped facet model), ideal region: sloped plane 
      gray level
\item piecewise quadratic, gray level surface: bivariate quadratic
\item piecewise cubic, gray level surface: cubic surfaces
\end{enumerate}

\vspace{1cm}
8.2 Relative Maxima \\
relative maxima: first derivative zero, second derivative negative 

\vspace{1cm}
8.3 Sloped Facet Parameter and Error Estimation \\
least-squares procedure: to estimate sloped facet parameter, noise variance 
\[
g(r,c)=\alpha r + \beta c + \gamma + \eta (r,c)
\]
$g$: image function \\
$r$: row \\
$c$: column \\
$\alpha$: slope in row direction \\
$\beta$: slope in column direction \\
$\gamma$: bias \\
$\eta$: noise having mean 0 and variance $\sigma^2$

\vspace{1cm}
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===== 

\vspace{1cm}
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 

\vspace{1cm}
8.6 Gradient-Based Facet Edge Detection \\
gradient-based facet edge detection: high values in first partial derivative 

\vspace{1cm}
8.7 Bayesian Approach to Gradient Edge Detection \\
The Bayesian approach to the decision of whether or not an observed gradient
magnitude $G$ is statistically significant and therefore participates in some
edge is to decide there is an edge (statistically significant gradient)
when,
\[
P({\rm edge}|G) > P({\rm nonedge}|G)
\]
$P({\rm edge}|G)$: given gradient magnitude, conditional probability of edge \\
$P({\rm nonedge}|G)$: given gradient magnitude, conditional probability 
of nonedge 
\[
P({\rm edge}|G) = \frac{P(G|{\rm edge})P({\rm edge})}{P(G)}
\]
\[
P({\rm nonedge}|G) = \frac{P(G|{\rm nonedge})P({\rm nonedge})}{P(G)}
\]
\[
P(G|{\rm edge})P({\rm edge}) > P(G|{\rm nonedge})P({\rm nonedge})
\]
possible to infer $P(G|{\rm edge})$ from observed image data
\[
P(G)=P(G|{\rm edge})P({\rm edge}) + P(G|{\rm nonedge})P({\rm nonedge})
\]
\[
P(G|{\rm edge})=\frac{P(G)-P(G|{\rm nonedge})P({\rm nonedge})}{P({\rm edge})}
\]
\[
=\frac{P(G)-P(G|{\rm nonedge})P({\rm nonedge})}{1-P({\rm nonedge})}
\]

\vspace{1cm}
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 $f$ takes the form
\[
f(r,c)=k_1+ k_2 r + k_3 c + k_4 r^2 + k_5 rc + k_6 c^2 +k_7 r^3 + k_8 r^2c
       +k_9 rc^2 + k_{10} c^3
\]       

\vspace{1cm}
8.8.1 Discrete Orthogonal Polynomials \\
discrete orthogonal polynomial basis set of size $N$: polynomials deg. $
0..N-1$ \\
discrete Chebyshev polynomials: these unique polynomials
\[
P_0(r) = 1
\]
\[
P_1(r)=r
\]
\[
P_n(r)=r^n+a_{n-1}r^{n-1}+...+a_1 r + a_0
\]
$P_n(r)$: orthogonal to $P_0(r), ..., P_{n-1}(r)$, thus
\[
\sum_{r \in R} P_k(r)(r^n+a_{n-1}r^{n-1}+...+a_1 r + a_0) = 0, \ \ \ k=0,...,n-1
\]
discrete orthogonal polynomials can be recursively generated
\[
P_{i+1}(r) = r P_i(r)-\beta_i P_{i-1}(r)
\]
\[
\beta_i=\frac{\sum_{r \in R} r P_i(r)P_{i-1}(r)}{\sum_{r \in R} P_{i-1}(r)^2}
\]
\[
P_2(r)=r^2 - \frac{\mu_2}{\mu_0}
\]
\[
P_3(r) = r^3 - \frac{\mu_4}{\mu_2}r
\]
\[
P_4(r) = r^4 + \frac{(\mu_2 \mu_4- \mu_0 \mu_6)r^2+(\mu_2 \mu_6 - \mu_4^2)}{
\mu_0 \mu_4 - \mu_2^2}
\]
\[
\mu_k=\sum_{s \in R} s^k
\]

\vspace{1cm}
8.8.2 Two-Dimensional Discrete Orthogonal Polynomials \\
2-D discrete orthogonal polynomials creatable from tensor products of 1D \\
from above equations
\[
\begin{array}{ll}
{\rm Index \ Set} & {\rm Discrete \ Orthogonal \ Polynomial \ Set} \\
\{ -\frac{1}{2}, \frac{1}{2}\} & \{1,r\} \\
\{-1,0,1\} & \{1,r,r^2-\frac{2}{3}\} \\
\{-\frac{3}{2}, -\frac{1}{2}, \frac{1}{2}, \frac{3}{2} \} & \{1,r,
r^2-\frac{5}{4},r^3-\frac{41}{20}r\} \\
\{-2,-1,0,1,2\} & \{1,r,r^2-2,r^3-\frac{17}{5}, r^4+3r^2+\frac{72}{35}\} 
\end{array}
\]

\vspace{1cm}
8.8.3 Equal-Weighted Least-Squares Fitting Problem \\
weight
\[
\frac{P_m(r)}{\sum_{s \in R} P_m^2(s)}
\]
e.g. $r$: row, $c$: column, $k_5$: $rc$ numerator, $\sum (rc)^2$ denominator \\
=====Fig. 8.8=====

\vspace{1cm}
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 \\
$r$: row \\
$c$: column \\
$\rho$: radius in polar coordinate \\
$\alpha$: angle in polar coordinate, clockwise from column axis \\
$r=\rho \sin \alpha, c=\rho \cos \alpha$ \\
directional derivative of $f$ at point $(r,c)$ in direction $\alpha$:
\[
f'_\alpha(r,c)=\lim_{h \rightarrow 0} \frac{f(r+h \sin \alpha, c+h \cos \alpha)
-f(r,c)}{h}
\]
\[
f'_\alpha(r,c)=\frac{\partial f}{\partial r}(r,c) \sin \alpha +
\frac{\partial f}{\partial c}(r,c) \cos \alpha
\]
second directional derivative of $f$ at point $(r,c)$ in direction $\alpha$:
\[
f''_\alpha(r,c)=\frac{\partial^2 f}{\partial r^2}(r,c) \sin^2 \alpha +
2\frac{\partial^2 f}{\partial r \partial c}(r,c) \sin \alpha \cos \alpha +
\frac{\partial^2 f}{\partial c^2}(r,c) \cos^2 \alpha
\]
\[
f'''_\alpha(r,c)=\frac{\partial^3 f}{\partial r^3}(r,c) \sin^3 \alpha +
3\frac{\partial^3 f}{\partial r^2 \partial c}(r,c) \sin^2 \alpha \cos \alpha 
\]
\[
+3\frac{\partial^3 f}{\partial r \partial c^2}(r,c) \sin \alpha \cos^2 \alpha +
\frac{\partial^3 f}{\partial c^3}(r,c) \cos^3 \alpha
\]

\vspace{1cm}
8.9 Integrated Directional Derivative Gradient Operator \\
integrated directional derivative gradient operator: more accurate \\
\hspace*{1cm} step edge direction  \\
=====joke=====

\vspace{1cm}
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  

\vspace{1cm}
8.11 Isotropic Derivative Magnitudes \\
gradient edge: from first-order isotropic derivative magnitude

\vspace{1cm}
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 ...

\vspace{1cm}
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:
\begin{itemize}
\item peak
\item pit
\item ridge
\item ravine
\item saddle
\item flat
\item hillside
\end{itemize}
topographic primal sketch: rich, hierarchical, structurally complete rep. 

\vspace{1cm}
Invariance Requirement \\
histogram normalization, equal probability quantization: nonlinear, enhancing\\
peak, pit, ridge, valley, saddle, flat, hillside: have required invariance 

\vspace{1cm}
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

\vspace{1cm}
8.13.2 Mathematical Classification of Topographic Structures \\
topographic structures: invariant under monotonically increasing intensity tran.

\vspace{1cm}
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
\[
||\nabla f || = 0, \lambda_1 < 0, \lambda_2 < 0
\]
$||\nabla f ||$: gradient magnitude \\
$\lambda_1$: second directional derivative in $w^{(1)}$ direction \\
$\lambda_2$: second directional derivative in $w^{(2)}$ direction 

\vspace{1cm}
Pit \\
pit: sink: bowl: local minimum in all directions \\
pit: gradient zero, second directional derivative positive
\[
||\nabla f || = 0, \lambda_1 > 0, \lambda_2 > 0
\]

\vspace{1cm}
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===== 
\[
||\nabla f || \neq 0, \lambda_1 < 0, \nabla f \cdot w^{(1)} = 0
\]
\[
{\rm or} \ \ \ ||\nabla f || \neq 0, \lambda_2 < 0, \nabla f \cdot w^{(2)} = 0
\]
\[
{\rm or}\ \ \ ||\nabla f || = 0, \lambda_1 < 0, \lambda_2 = 0
\]

\vspace{1cm}
Ravine \\
ravine: valley: local minimum in one direction \\
walk along ravine line: points to the right and left are higher 
\[
||\nabla f || \neq 0, \lambda_1 > 0, \nabla f \cdot w^{(1)} = 0
\]
\[
{\rm or}\ \ \ ||\nabla f || \neq 0, \lambda_2 > 0, \nabla f \cdot w^{(2)} = 0
\]
\[
{\rm or}\ \ \ ||\nabla f || = 0, \lambda_1 > 0, \lambda_2 = 0
\]

\vspace{1cm}
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
\[
||\nabla f || = 0, \lambda_1 * \lambda_2 < 0
\]

\vspace{1cm}
Flat \\
flat: plain: simple, horizontal surface \\
=====Fig. 8.26===== \\
flat: zero gradient, no curvature 
\[
||\nabla f || = 0, \lambda_1 = 0, \lambda_2  = 0
\]
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=====

\vspace{1cm}
Hillside \\
hillside point: anything not covered by previous categories \\
hillside: nonzero gradient, no strict extrema  \\
slope: tilted flat (constant gradient) 
\[
\lambda_1 = \lambda_2  = 0
\]
convex hill: curvature positive (upward) 
\[
\lambda_1 \geq \lambda_2 \geq 0, \lambda_1 \neq 0
\]
concave hill: curvature negative (downward) 
\[
\lambda_1 \leq \lambda_2 \leq 0, \lambda_1 \neq 0
\]
saddle hill: up in one direction, down in perpendicular direction 
\[
\lambda_1 * \lambda_2 < 0
\]
inflection point: zero crossing of second directional derivative 

\vspace{1cm}
Summary of the Topographic Categories \\
mathematical properties of topographic structures on continuous surfaces \\
=====Table 8.5=====

\vspace{1cm}
Invariance of the Topographic Categories \\
topographic labels: invariant under monotonically increasing gray level tran. \\
monotonically increasing: positive derivative everywhere

\vspace{1cm}
Ridge and Ravine Continua \\
entire areas of surface: may be classified as all ridge or all ravine 

\vspace{1cm}
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 

\vspace{1cm}
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=====

\vspace{1cm}
Case Two: One Zero Crossing \\
one zero crossing: peak, pit, ridge, ravine, or saddle \\
=====Table 8.7=====

\vspace{1cm}
Case Three: Two Zero Crossings \\
LABEL1, LABEL2: assign label to each zero crossing \\
=====Table 8.8=====

\vspace{1cm}
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 

\vspace{1cm}
8.13.4 Summary of Topographic Classification Scheme \\
one pass through the image, at each pixel
\begin{enumerate}
\item calculate fitting coefficients, $k_1$ through $k_{10}$ of cubic polynomial
\item Use above coefficients to find gradient, gradient magnitude, eigenvalues, ...
\item search in eigenvector direction for zero crossing of first derivative
\item recompute gradient, gradient magnitude, second derivative, then classify
\end{enumerate}
=====Garfield 17:8=====

\vspace{1cm}
Previous Work \\
web representation [Hsu et al. 1978]: axes divide image into regions







\vspace{1cm}
Project due Dec. 21 \\
Write the following programs to detect edge: \\
1. zero-crossing on the following four types of images to get edge images
   (choose proper thresholds), p. 349 \\
2. Laplacian, Fig. 7.33 \\
3. minimum-variance Laplacian, Fig. 7.36 \\
4. Laplacian of Gaussian, Fig. 7.37 \\
5. Difference of Gaussian, (use tk to generate D.O.G.) \\
\hspace*{1cm} D. Marr, {\em Vision}, W.H. Freeman, San Francisco, p.54-74, 
1982.\\
=====Marr, {\em Vision}, Fig. 2.9===== \\
=====Marr, {\em Vision}, Fig. 2.16===== \\
dog (inhibitory $\sigma=1$, excitatory $\sigma=3$, kernel size=11)



\end{document}
