December 23, 2014

Based on this paper on graph matching for registration of biomed data. We can adapt the approach to our multi-view data using knowledge of (a) the cameras and (b) small motion between views. Our graphs will deform differently than theirs, because parallax doesn't maintain relative euclidean distances. However, geodesic distances should be roughly maintained, so we can use geodesic distance in our nonlinear deformation GP. The coarse-to-fine strategy should make inference more tractible than our previous appraoches; fitting branch points first, interior points later. This approach will require better foreground-background segmentation than we've used in the past, which we can achieve by training a pixel classifier with the Weka segmenter in Fiji.

This appraoch answers the question of how to project an embedded graph from one view to another using a small number of known correspondences. In the original paper, the GP evidence consisted of the graph vertex positions in the original view, which are allowed to deform in the second view using a squared-expoential covariance function. In our approach, we will also use the original vertex positions in order to encourage minimal motion, under the assumption of minimal camera motion. However, we will also introduce evidence from the epipolar lines, using known cameras. To accomplish this, we will backproject the points to a default depth, and reproject them into the second image. The likelihood covariance will have infinite variance in the direction of the epipolar line. For any particular point, the product of (a) the "zero motion" likelihood function and (b) the "epipolar constraint" likelihood function should be their product -- an enlongated eliptical gaussian with mean lying on (or very near) the eipolar line nearest to the original point location.

The prior covariance between graph points will be given by a covariance function similar to that in the original paper, but using geodesic distance between points instead of euclidean distance. This should allow greater movement in the tips of plant.

We can train this model on ground truth curve skeletons.

The coarse graph matching proceeds by proposing correspondence between two pairs of points, using point covariance to choose good candidates. We then update to covariance of remaining points and propose a new correspondence from the pair with fewest matches. We resume until a threshold of matches is met, and we evaluate the result. We then back up the decision tree and try the other correspondence candidate (i.e. depth first search over all candidates). Note that at each level of the decision tree, the number of candidates decreases, due to less uncertainty in point positions, which mitigates the combinitoric explosion in correspondences. We terminate early if the relative geodesic distance between pairs of corresponding nodes differs significantly. We may also use triangulation error as a stoping criterion, but this is probably already handled by the epipolar constraint likelihood.

In some cases, the graph changes topology between views, due to overlapping stems. Our approach should be robust somewhat to different topologies, but it is unclear how much. We may need to convert our graphs to trees somehow, maybe by sampling. Other possible heuristics:

- use X-junctions as candidates for overlapping edges
- assume bottom of image is graph root; prefer nodes closer to the root according to breadth-first-search depth when breaking loops.
- eliminate short segments, merging their nodes
- prune short edges, or edges with fast-varying width. (e.g. at flower tips.)

\[
\begin{align}
\mu_N(\mathbf{x}^A) &= \mathbf(k)^T \mathbf{C}_N^{-1} \mathbf{Y}_N^B \\
\sigma^2_N(\mathbf{x}^A) &= k(\mathbf{x}^A, \mathbf{x}^A) + \beta^{-1} - \mathbf{k}^T \mathbf{C}_N^{-1}\mathbf{k}
\end{align}
\]

where

\[
\begin{align}
\mathbf{C}_N = diag(K,3) + K_y
K_y = (\sigma_o^{-1} I + \Sigma_e^{-1})^{-1}
Y^B_N = K_y (\sigma_o^{-1} I X^B_N + \Sigma_e^{-1} e
e is the epipole
\pi^K(X) is the epipiolar projection of the points in X into view K (see explanation)
\Sigma^A_e = diag([\Sigma^A_{e,1}, ..., \Sigma^A_{e,N}])
\Sigma^{-A}_{e,i} = 1/\sigma_e^2 R(\Theta(x_i)) [1 0; 0 0] R^T(\Theta(x_i))
\Theta(x_i) = atan2(-F_1 x_i, F_2 x_i)
K_ij = k(x_i^A, k_j^A)
\end{align}
\]

Posted by
Kyle Simek