Constraints based on Phases

If ${\bf A}_l$ is a symmetric matrix (in Equation 5), it can be shown that the auto-correlation $\psi(0, 0)$ is real. This implies that that the phase of $\psi(0, l)$ would be $\frac{2\pi\lambda_l k}{N}$.

If we have $M$ views, then we can form a $M\!\times\!(N-1)$ matrix $\Theta^{\prime}$ with the phase angles of $\psi(0,l)[k], 0 < k < N$ forming the row $l$. It is clear that the rows of the matrix differ only by a scale factor. Therefore, $\Theta^{\prime}$ is a rank deficient matrix with a fixed rank of 1, irrespective of the number of views. Therefore a necessary condition for recognition in multiple views related by symmetric affine homographies is

$$rank(\Theta^{\prime}) = 1$$ (10)

This rank-one constraint implies that the phases of CCP in different views are linearly related. Thus, the phases form a signature of the shape that is invariant to affine transformations. Unfortunately this relationship is valid only if the affine transformation (${\bf A}_l$) is symmetric. Also, the CCP is computed between each view and a fixed reference view; it thus depends on two views.

For affine transformations when ${\bf A}_l$ can be arbitrary, we derive a rank-two constraint as follows. ${\bf A}_l$ now contains a skew-symmetric component in addition to a symmetric one. We define a new measure $\kappa^{\prime}(\cdot)$, which correlates each Vector Fourier coefficient with a fixed one within each view.

$$\kappa'_p(l)[k] = ({\bf X}^l[k])^{*{\mbox{\small\sc t}}} \left[ \begin{array}{cl} 0 & 1 -1\;\; & 0 \end{array}\right] { \bf X}^l[p], \;\;\; 0 < k < N$$

$$= (A {\bf X}^0[k] e^{j\frac{2\pi\lambda_l k}{N}})^{*{\mbox{\small... ... & 1 -1 & 0 \end{array}\right] A {\bf X}^0[k]e^{j\frac{2\pi\lambda_l p}{N}}$$

$$= ({\bf X}^0[k])^{*{\mbox{\small\sc t}}}A^{\mbox{\small\sc t}} \lef... ... -1 & 0 \end{array}\right] A{\bf X}^0[k] e^{-j\frac{2\pi\lambda_l (k-p)}{N}}$$

$$= \vert A\vert\; \kappa^{\prime}_p(0)[k]\; e^{ - j2\pi\lambda_l (k - p) / N}$$ (11)

for any fixed $p \neq 0$. Equation 11 states that the phases of $\kappa'_p(l)$ and $\kappa'_p (0)$ differ by an amount proportional to the shift $\lambda_l$ and the differential frequency $k - p$. Therefore, the ratio $\frac{\kappa'_p(l)}{\kappa'_p(0)}$ will be a complex sinusoid $c e^{ - j2\pi\lambda_l (k - p) / N}$. The value of $\lambda_l$ can be computed from the inverse Fourier transform of the quotient series. Thus, the phases of $\kappa'_p(l)$ can be used as a signature for the contour.

We can also form a $M\times (N-1)$ matrix $\Theta^{\prime\prime}$, similar to the one above, that stacks the phases of $\kappa^{\prime}_1(l)$ (taking $p = 1$). It will have the form $\Theta^{\prime\prime} =$

$${\scriptsize \left[ \begin{array}{ccccc} \theta_1 & \theta_2... ... \ldots & \theta_{N-1} + (N-2)\phi_{M-1} \end{array} \right] }$$ (12)

where $\theta_i$ are the phases of $\kappa'_1(0)$ and $\phi_l = -2\pi\lambda_l / N$. This matrix will have a rank of 2 irrespective of $M$. The rank constraint on the above matrix, which is a necessary condition for recognition of shapes in views related by affine image-to-image homographies, is

$$\mbox{rank}(\Theta^{\prime\prime}) = 2.$$ (13)

We see that $\kappa'$ can be computed from a single view. Thus, the phases of $\kappa'$ values provide a truly view-independent description of the boundary.

Experiments were conducted to affirm the validity of the above constraint. Figure 1 shows four affine transform related views of a dinosaur. When the $\Theta^{\prime\prime}$ was constructed from the $\kappa^{\prime}$ measures of the four views (a), (b), (c) and (d), with random shifts applied to the boundary representations in each view, the rank of $\Theta^{\prime\prime}$ was found to be essentially 2, the three greatest singular values being 33952.7, 58.8366, and 0.00242446.