Reconstruction of Quadrics from two views

In Computed Tomography imaging, a volume image is reconstructed from measured projection images. Reconstruction algorithms aim to calculate a 3d distribution which, when integrated along some beam of rays, yields the observed transmission images.

These algorithms are very time consuming and resource expensive as the complexity of the problem is high. Recently I have been interested in alternatives for volume reconstruction for parametrized geometrical objects.

In this post I want to investigate a method for reconstruction of quadric shapes from a few projection conics.

Example setup of Quadric Reconstruction. The quadric Q is projected onto two planes using a perspective map to obtain the two elliptical conics C1 and C2. It is our goal to reconstruct Q from observed C1 and C2.

Quadrics

A quadric surface in 3d space is defined by a polynomial function of degree two with a total of 9 unknown coefficients. The most common quadric describes an ellipsoidal object such as an ellipsoid or a sphere.

Definition of quadric as 4x4 symmetric matrix. The null space of the second equation defines a quadric surface. Due to the homogenous representation, the parameter c can be omitted, which gives a total of 9 unknowns.

More details on how these quadric representations can be derived from a covariance matrix and mean vector can be found here.

Conics

A conic is the 2d-analogous of a quadric. Typical conics include ellipses, hyperbolas and parabolas. The general conic equation is a polynomial with 5 independant coefficients.

The conic outline of a quadric projected onto a 2d plane can be calculated efficiently using matrix notation:

Quadric Projection: Quadric Q projected along projection matrix P (3x4 matrix) yields view-conic C.

Reconstruction from two views

Cross, Zisserman (1998) describe a method of retriving the Quadric Q from two observed view-conics C1 and C2. To do so, the above formula for quadric projection is vectorized.

In this context, vectorization means that the Conic C and Quadric Q are reshaped to vectors containing the independent free-variables. The symmetric 4x4 matrix Q is reshaped to a vector of size 10 (upper triangular matrix) whilst C (3x3 matrix) is converted to a vector of size 6 analogously.

The vector-to-vector mapping can then be carried out with a single mutliplication by a 10x6 matrix B. Here I summarize how to derive B from P.

Vectoriation of quadric projection.

Given the two projection conics {c, c’} and the corresponding projection matrices {B, B’}, we can create and solve an equation system. To explicitly account for the scaling of the two conic equation, we also include two parameters for scale.

The 12x12 matrix M defines the constraints imposed on the quadric by two projection conics c and c’.

The null space of Mw = 0 yields the reconstructed quadric v* in its dual form. By rearranging in a 4x4 matrix and computation of the inverse, a solution quadric Q can be obtained.

Ambiguity of two-view reconstruction

The paper continues to state that the resulting solution of a two-view equation system will be a family of quadrics given by:

Solution space for two-view reconstruction.

Choosing free parameter using the positive-definite constraint

To obtain a unique reconstruction from the parameter family, we can assess what happens for different choice of lambda and impose constraints on it. A simple constraint would be, that the upper left triangle matrix A must be positive definite if we know the quadric is an ellipsoid.

A positive definite symmetric matrix has only positive eigenvalues and the determinants of all upper left triangle submatrices are positive. We can write formalize that as follows:

All upper left sub-matrices of A must have a positive determinant.

Example

We define an ellipsoid which has its longest axis along the y = x line. We proceed as described above to obtain a solution family. For the projection matrices we use a z-axis and y-axis projection for simplicity:

Ground truth Quadric and result of reconstruction. We see that if we set b=-1 and c=0, we obtain the original quadric.

The resulting solution space looks sensible, but as we usually dont know the ground truth we have to investigate what happens for different parametrizations of c and b.

The choice of lambda depends on the normally neglegible scaling constant b. In the plot below, we see the relationship arizing between b and c (lambda). The quadric is pos. definite iff b < 0 and f(c, b) > 0.

We can see, there exists a 2d solution space which satisfies the positive definite constraint.

Parameter space c and b. The positive definite constraint yields that b<0 and f(c, b) > 0. This yields the 2d parameter solution space where the blue function is positive and b negative.

To investigate the effects of the parameters c and b on the resulting shape of the quadric we plot it while choosing c(b) on the function obtained from the constraint.

We see, that it stays an ellipsoid until b ~ -1.9 then it becomes a hyperboloid of one sheet.

Changing shape of reconstructed quadric wrt choice of free parameter c.

Conclusion

Using the constraint that the quadric must be positive definite, we can define bounds for the free parameters. However, the resulting family of quadrics does not seem to approximate the input ellipsoid well. Further work has to be dedicated to searching the optimal solution.