\documentclass[11pt,twocolumn]{article}
\usepackage{times,amsmath,amsfonts}
\usepackage[dvips]{graphicx,graphics}

\setlength{\textheight}{10in} \setlength{\textwidth}{7.1in}
\setlength{\columnsep}{0.3in} \setlength{\topmargin}{0in}
\setlength{\headheight}{-0.3in} \setlength{\headsep}{0in}
\setlength{\oddsidemargin}{-0.6in}  % Centers text.

% Add the period after section numbers.  Adjust spacing.
%\newcommand{\Section}[1]{\vspace{-5pt}\section{\hskip -1em.~~#1}\vspace{-3pt}}
%\newcommand{\SubSection}[1]{\vspace{-2pt}\subsection{\hskip -1em.~~#1}
%        \vspace{-3pt}}
\newcommand{\bqn}{\begin{eqnarray*}}
\newcommand{\eqn}{\end{eqnarray*}}
\newcommand{\bq}{\begin{eqnarray}}
\newcommand{\eq}{\end{eqnarray}}

\begin{document}

\title{Stat 992: Lecture 30\\
Curve Modelling III.}
\author{Moo K. Chung \tt{mchung@stat.wisc.edu}}
\maketitle \thispagestyle{empty}

%\begin{figure}
%\centering
%\renewcommand{\baselinestretch}{1}
%\includegraphics[scale=0.8]{homework05-1.eps}
%\end{figure}

\begin{enumerate}

\item {\em Active contour.} Active contour models (snakes) first
proposed by Kass, Witkin and Terzopoulos (International Journal of
Computer Vision 1:321-31, 1987) is a variational method for
detecting object boundaries in images. Given $n$ points
$C^0=\{p_1^0,\cdots,p_n^0\}$ that define the initial closed
contour, we deform the points to lie along the object boundary
(Figure \ref{fig:ima30-1}). The initial contour $C^0$ is deformed
to $C^1=\{p_1^1,\cdots,p_n^1\}$ by minimizing a certain energy
function.  We deform contour $C_i=\{p_1^i,\cdots,p_n^i\}$ to
$C_{i+1}=\{p_1^{i+1},\cdots,p_n^{i+1}\}$ by
$$p_j^{i+1} = p_j^i + d(p_j^i) \mbox{ for all } j$$
where $d$ is the displacement vector that minimize the total
energy. This procedure is iteratively performed until the snake
$C^i$ hit the object boundary.




\item {\em Energy via parameterization.} Read G. Sapiro's
Geometric Partial Differential Equations and Image Analysis. Let
$X(p)$ be a parameterization of contour $C$ and $I$ be a image
intensity. Then the energy given by Kass {\em et al.} is
$$E(C) = \alpha \int |X'(p)|^2 + \beta \int |X''(p)| - \lambda
\int |\nabla I (X(p))|.$$ The first two terms are the internal
energy while the last term is the external energy. The internal
energy is responsible for smoothness while the external energy is
responsible for attracting the contour toward the object boundary.
Parameters $\alpha,\beta$ and $\lambda$ are determined a priori.
Smaller $\lambda$ reduces the noise but can not capture the sharp
corners while larger $\lambda$ can effectively capture boundary
but it is sensitive to the noise. The the total energy given by
Kass {\em et al.} can be written as
$$E(C) = E_{internal}(C) + \lambda E_{external}(C).$$
It can be shown from the {\em calculus of variations}, the contour
should satisfy Euler-Lagrange equation:
$$-\frac{d}{dp} (\alpha X') + \frac{d^2}{dp^2}(\beta X'') -
\lambda \Delta I(X)=0.$$

\begin{figure}[t]
\centering
\renewcommand{\baselinestretch}{1}
\includegraphics[scale=0.33]{ima30-1.eps}
\includegraphics[scale=0.33]{ima30-2.eps}
\includegraphics[scale=0.33]{ima30-3.eps}
\caption{Left: Initial contour $C_0$ picked manually using {\tt
ginput} mouse command in {\tt MATLAB}. Middle:the trace of
deformation. Right: After 50 iterations with no external energy
term ($\lambda =0$).\label{fig:ima30-1}}
\end{figure}
\item {\em Discrete version.} The energy corresponding to each
points is denoted as
$$E(p_j^i) = E_{internal}(p_j^i) + E_{external}(p_j^i).$$ Energy terms
are $$E_{internal} = \sum_{j=1}^n
E_{internal}(p_j^i),$$
$$E_{external} = \sum_{j=1}^n E_{external}(p_j^i).$$

The first internal energy term $\int |X'(p)|^2$ measures the
linear elastic potential of a string that is proportional to the
squared distance between neighboring points, i.e.
$$E_{elastic}(p_j^i) =\|p_{j+1}^i-p_j^i\|^2 + \|p_j^i-p_{j-1}^i\|^2.$$

The second term $\int |X''(p)|^2$ measures the curvature and at
each point it is given as
$$E_{curvature}(p_j^i) = \|p_{j+1}^i-2p_j^i+p_{j-1}\|^2.$$
Many authors incorporate different energy terms.

The external energy can be written
$$E_{external} = a E_{intensity} + bE_{gradient}$$
where $E_{intensity}$ attracts the contour to either high or low
intensity regions and $E_{gradient}$ forces the contour to move
toward the extreme image gradient. $E_{intensity}(p_j^i) =
f(I(p_j^i))$ for some simple function $f$. $E_{gradient}(p_j^i) =
\|\nabla I(p_j^i)\|^2$. To make this energy function smooth,
$\|\nabla K_{\sigma}*I(p_j^i)\|^2$ is used instead.

\begin{figure}[t]
\centering
\renewcommand{\baselinestretch}{1}
\includegraphics[scale=0.33]{ima30-4.eps}
\includegraphics[scale=0.33]{ima30-5.eps}
%\includegraphics[scale=0.33]{ima30-3.eps}
\caption{Left: $\partial_x I$, Right: $\partial_x(K_{\sigma}*I)$
\label{fig:ima30-2} Extreme image gradient corresponds to the
object boundary.}
\end{figure}

\item {\em Updating scheme.} Hamarneh and Gustavsson (Combining
snakes and active shape models for segmenting the human left
ventricle in echocardiographic images, IEEE computers in
cardiology, 2000) uses the following updating scheme.
$$p_j^{i+1} = p_j^i + d(p_j^i) \mbox{ for all } j$$ where the
displacement vector field is given in terms of force
$$d(p_j^i) = - \nu(F_{internal} + F_{external}).$$
This method would be very useful for improving upon manual
segmentation result.

\item {\em Goodness of fit of contouring} The measure of the
goodness of fit between the manual contouring and active
contouring is based on the geodesic distance the snake has moved.
Suppose that $C_m$ gives the final estimate of the object boundary
from the original manual contouring $C_0$. Note that the path of
point $p_j^0$ is  $p_j^0 \to p_j^1 \to \cdots \to p_j^m$ so the
total geodesic distance the point moved is
$$d_{geodesic}(p_j^0,p_j^m) = \sum_{i=0}^{m-1} \|p_j^{i+1} - p_j^i\|.$$
For small deformation,
$$d_{geodesic}(p_j^0,p_j^m) \doteq \|p_j^n - p_j^0\|$$
and the total goodness-of-fit measure of the manual contouring is
given by
$$GOF = \sum_{j=1}^n d_{geodesic}(p_j^0,p_j^m).$$


\begin{figure}[t]
\centering
\renewcommand{\baselinestretch}{1}
\includegraphics[scale=0.27]{ima30-6.eps}
%\includegraphics[scale=0.33]{ima30-3.eps}
\caption{The result of Hamarneh and Gustavsson's method applied to
an ultrasound image. See the original paper.}
\end{figure}


 {\bf Problem 44.} The following code will pick out the manual
 contouring points on images. To stop picking points, right click
the mouse button.
\begin{verbatim}
imageshow(image);
hold on;
xs = []; ys = [];
xold = 0; yold = 0;
but = 1;
while but == 1
    [xi, yi, but] = ginput(1);
    xs = [xs; xi];
    ys = [ys; yi];
    if xold;
        plot([xold xi], [yold yi], 'ro-');
    else
        plot(xi, yi, 'ro');
    end;
    xold = xi;
    yold = yi;
end;
plot([xi xs(1)], [yi ys(1)], 'r-');
\end{verbatim}
Suppose your image is very simple binary image of a circle, i.e.
$I(x,y)=1$ if $x^2+y^2 =r^2$ and $I(x,y)=0$ if $x^2+y^2 \neq r^2$.
Pick out 10 points $C_0$ close to the circle boundary and write
very simple active contouring {\tt MATLAB} code for detecting a
circle.


\end{enumerate}

\end{document}


\item {\em Covariance function estimation.} On manifolds $\partial
\Omega$, we have model
$$Y(x) = \mu(x) + \epsilon(x)$$
where $\epsilon$ is unknown random field. We may estimate $\mu$ by
kernel smoothing so that $\widehat{\mu} = K_{\sigma}*Y$. Now we
estimate the noise with the residual $\widehat{\epsilon} = Y -
K_{\sigma}*Y$.