previous up next
Next: Synthesis using example sets Up: Example Based Image Synthesis Previous: Modeling smooth and/or linear

Finding consistent example sets

Given examples from a complicated (non-linear, non-smooth) appearance mapping, we find local regions of appearance which are well-behaved as smooth, possibly linear, functions. We wish to cluster our examples into sets which can be used for successful interpolation using our local appearance model.

Conceptually, this problem is similar to that faced by Bregler and Omohundro [2], who built image manifolds using a mixture of local PCA models. Their work was limited to modeling shape (lip outlines); they used K-means clustering of image appearance to form the initial groupings for PCA analysis. However this approach had no model of texture and performed clustering using a mean-squared-error distance metric in simple appearance. Simple appearance clustering drastically over-partitions the appearance space compared to a model that jointly represent shape and texture. Examples which are distant in simple appearance can often be close when considered in 'vectorized' representation. Our work extends the notion of example clustering to the case of coupled shape and texture appearance models.

Our basic method is to find sets of examples which can be well-approximated from their convex hull in parameter space. We define a set growing criterion which enforces compactness and the good-interpolation property. To add a new point to an example set, we require both that the new point must be well approximated by the previous set alone and that all interior points in the resulting set be well interpolated from the exterior examples. We define exterior examples to be those on the convex hull of the set in parameter space. Given a training subset $s \subset \Omega$ and new point $p \in \Omega$,

\begin{displaymath}
E(s,p) = \max( E_I(s \cup \{p\}), E_E(s,p) ) ~,\end{displaymath}

with the interior error

\begin{displaymath}
E_I(s)= \max_{p' \in (s-{\cal H}_x(s))} \vert\vert y_{p'}-{\hat y}({{\cal H}_x(s)},x_{p'})\vert\vert ~,\end{displaymath}

and the extrapolation error

\begin{displaymath}
E_E(s,p)= \vert\vert y_p-{\hat y}({{\cal H}_x(s)},x_p)\vert\vert ~ . \end{displaymath}

${\cal H}_x(s)$ is the subset of s whose x vectors lie on the convex hull of all such vectors in s. To add a new point, we require $E<\epsilon$, where $\epsilon$ is a free parameter of the clustering method.

Given a seed example set, we look to nearest neighbors in appearance space to find the next candidate to add. Unless we are willing to test the extrapolation error of the current model to all points, we have to rely on precomputed non-vectorized appearance distance (e.g., MSE between example images). If the examples are sparse in the appearance domain, this may not lead to effective groupings.

If examples are provided in sequence and are based on observations from an object with realistic dynamics, then we can find effective groupings even if observations are sparse in appearance space. We make the assumption that along the trajectory of example observations over time, the underlying object is likely to remain smooth and locally span regions of appearance which are possible to interpolate. We thus perform set growing along examples on their input trajectory. Specifically, in the results reported below, we select K seed points on the trajectory to form initial clusters. At each point p we find the set s which is the smallest interval on the example trajectory which contains p, has a non-zero interior region $(s-{\cal
H}_x(s))$, and for which $E_I(s)<\epsilon$. If such set exists, we continue to expand it, growing the set along the example trajectory until the above set growing criterion is violated. Once we can no longer grow any set, we test whether any set is a proper subset of another, and delete it if so. We keep the remaining sets, and use them for interpolation as described below.


previous up next
Next: Synthesis using example sets Up: Example Based Image Synthesis Previous: Modeling smooth and/or linear
Trevor Darrell
9/11/1998