Models for Shape¶
Snakes/Active Contour Models¶
Starts with a circular configuration and adapts to the shape.
Useful when there is little prior information about the object.
Shape Templates¶
Starts with the correct shape of the object.
Want to estimate the parameters of the transformation that maps the shape onto the current image.
Cannot be fit in closed form because we do not know which edge points in the image correspond to each landmark point in the model.
Iterative closest point algorithm alternatively matches points in the image to the landmark points and computes the best closed form transformation.
Statistical Shape Models/Active Shape Models/Point Distribution Models¶
Describe the variation within a class of objects.
Capable of adapting to novel individual shapes from that class.
Generalized procrustes analysis alternatively optimizes the mean shape and the parameters of the transformations that best maps the observed data points to this mean.
Non-Gaussian Statistical Shape Models¶
Gaussian process latent variable model (GPLVM) extends the PPCA model so that the hidden variables are transformed through a fixed nonlinearity before being weighted by the basis functions.
Exercise 17.1¶
\(\mathbf{C}_2\) is a singular matrix.
[1]:
import numpy as np
import matplotlib as mpl
import matplotlib.pyplot as plt
def conicMatrix(v, xlim=[-2, 2], ylim=[-2, 2], xlab='x', ylab='y', title='', col='k'):
x = np.linspace(*xlim, 200)
y = np.linspace(*ylim, 200)
x, y = np.meshgrid(x, y)
_ = (v[0] * x**2 + v[1] * x * y + v[2] * y**2 + v[3] * x + v[4] * y + v[5])
plt.contour(x, y, _, [0], colors=col)
plt.xlim(*xlim)
plt.ylim(*ylim)
plt.xlabel(xlab)
plt.ylabel(ylab)
plt.title(title)
plt.axis('equal')
plt.show()
conicMatrix([3, 0, 2, 0, 0, -1], xlim=[-1, 1], ylim=[-1, 1], title='Ellipse', col='red')
conicMatrix([0, 0, 0, 1 * 2, 0, -2], title='Vertical Line', col='green')
conicMatrix([-1, 0, 0, 0, 1 * 2, 0], xlim=[-4, 4], ylim=[-1, 9], title='Parabola', col='blue')
<Figure size 640x480 with 1 Axes>
<Figure size 640x480 with 1 Axes>
<Figure size 640x480 with 1 Axes>
Exercise 17.2¶
The distance transform computes for each pixel the distance to the nearest background pixel whose value is zero. To compute the distance to the nearest non-zero element of the original binary image, apply the same algorithm to the negated binary image.
[2]:
import numpy
def city_block_distance(grid):
dt = numpy.zeros_like(grid)
max_distance = grid.shape[0] * grid.shape[1]
#top-left corner of matrix in numpy
for i in range(grid.shape[0]):
for j in range(grid.shape[1]):
#already at boundary
if 0 == grid[i,j]:
continue
#not at boundary, so initially assume maximum distance to boundary
dt[i,j] = max_distance
#examine west and north neighbors
for k, l in [(i - 1, j), (i, j - 1)]:
if 0 <= k < grid.shape[0] and 0 <= l < grid.shape[1]:
dt[i,j] = min(1 + dt[k,l], dt[i,j])
else:
#values outside grid are zero
dt[i,j] = min(numpy.inf, dt[i,j])
print('Result from forward pass:\n{}'.format(dt))
#bottom-right corner of matrix in numpy
for i in range(grid.shape[0] - 1, -1, -1):
for j in range(grid.shape[1] - 1, -1, -1):
#already at boundary
if 0 == dt[i,j]:
continue
#examine east and south neighbors
for k, l in [(i + 1, j), (i, j + 1)]:
if 0 <= k < grid.shape[0] and 0 <= l < grid.shape[1]:
dt[i,j] = min(1 + dt[k,l], dt[i,j])
else:
#values outside grid are zero
dt[i,j] = min(numpy.inf, dt[i,j])
print('Result from backward pass:\n{}'.format(dt))
grid = numpy.asarray([[0, 0, 0, 0, 1, 0, 0],
[0, 0, 1, 1, 1, 0, 0],
[0, 1, 1, 1, 1, 1, 0],
[0, 1, 1, 1, 1, 1, 0],
[0, 1, 1, 1, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0]])
city_block_distance(1 - grid)
Result from forward pass:
[[49 49 49 49 0 1 2]
[49 49 0 0 0 1 2]
[49 0 0 0 0 0 1]
[49 0 0 0 0 0 1]
[49 0 0 0 1 1 2]
[49 1 0 1 2 2 3]
[49 2 1 2 3 3 4]]
Result from backward pass:
[[3 2 1 1 0 1 2]
[2 1 0 0 0 1 2]
[1 0 0 0 0 0 1]
[1 0 0 0 0 0 1]
[1 0 0 0 1 1 2]
[2 1 0 1 2 2 3]
[3 2 1 2 3 3 4]]
Exercise 17.3¶
By inspection, the point at the minimum is \(\mathbf{w}_2 = \begin{bmatrix} 150 & 200 \end{bmatrix}^\top\).
Exercise 17.4¶
Since the image is a single color, there are no edge pixels so the distance transform will return \(\infty\) for each pixel. This reduces the likelihood in (17.7) to a constant, so only the prior information will affect the snakes model. The prior coefficients can be set to make the points spread out (or collapse) smoothly (or irregularly).
Exercise 17.5¶
Suppose the center of the shape could be computed from the edge information. (17.5) could use the averaged distance to the center from each landmark, which is essentially automating (17.8).
Exercise 17.6¶
Recall that \(\mathbf{w} \in \mathbb{R}^{2N}\) is a compound vector containing all the of the \(x\)- and \(y\)-positions of the landmark points in an image.
We could take a maximum likelihood approach and optimize (17.23) with respect to \(\mathbf{h}\). This is equivalent to a least square fitting as shown in (4.14).
Exercise 17.7¶
Given \(\mathbf{W} = \mathbf{U} \mathbf{L} \mathbf{V}^\top\) where \(\mathbf{U}, \mathbf{V}\) are orthogonal matrices and \(\mathbf{L}\) is a diagonal matrix,
Exercise 17.8¶
Let \(\boldsymbol{\theta} = \left\{ \boldsymbol{\mu}, \boldsymbol{\Phi}, \sigma^2 \right\}\).
(a)¶
(b)¶
The following relations are useful for (b.1), (b.2), (b.3):
The SVD solution yields the same mean but different principal components.
(a.1)¶
Substitute in the corresponding values into Exercise 7.9 to give
and
(b.1)¶
(b.2)¶
(b.3)¶
Exercise 17.9¶
where \(\mathbf{w}_n = \boldsymbol{\mu}_n + \boldsymbol{\Phi}_n \mathbf{h}\) and
Exercise 17.10¶
The activation function (9.66) can use \(\mathbf{h}\) to learn the coefficients of the gender classification model (9.65).
The ICP approach to (17.31) already handles the lack of landmark points.
Exercise 17.11¶
Each point in the point distribution could have mass-spring constraints, which can be used to iteratively redistribute the points towards the hidden portion of the shape.
Exercise 17.12¶
[GH+96] provides more details on Modeling Complex Data Densities.
[TB99] elaborates on the book’s coverage of probabilistic principal component analysis by showing how to train a mixture of them.
[PM00] extends the book’s analysis of t-distributions to mixture models.
[dRF03][KD04] are alternative nonlinear shape models that should be read after the foregoing materials.
Exercise 17.13¶
Rewrite \(\mathbf{x}_\cdot \in \mathbb{R}^2\) as
When \(\mathbf{x}_\cdot \in \mathbb{R}^3\) then
Assuming that the original and transformed positions have the same barycentric coordinates, warping the whole image is equivalent to
computing each position’s barycentric coordinates,
warping each triangle,
solving for the position relative to the warped triangle.
Exercise 17.14¶
(i)¶
(ii)¶
There exists a real unique solution for \(s\) when the discriminant is zero:
If the camera has intrinsic matrix \(\boldsymbol{\Lambda}\), then \(\mathbf{w} = \boldsymbol{\Lambda}^{-1} \mathbf{x} = \tilde{\mathbf{x}}\) and \(\mathbf{C} = \boldsymbol{\Lambda}^{-\top} \left( \mathbf{b} \mathbf{b}^\top - c \mathbf{A} \right) \boldsymbol{\Lambda}^{-1}\).