2
$\begingroup$

This is a problem from projective geometry. Suppose I have a vector $z \in R^k$ of unit length $\| z \| =1$ inside a $k$-dimensional hypercube. I don't know its value but do know its projection upto an unknown face-dependent scaling factor $\lambda_j$ onto $(k-1)$ orthogonal faces, $j = 1 \ldots (k-1)$ of the cube. My question is how best can I reconstruct the direction of $z$ from the $(k-1)$ projections?

The situation is complicated by the fact that my information about the projections is only approximate and potentially over-specified if I have estimates from more than $(k-1)$ faces.

I have an initial solution using $L_2$-optimisation but wondered if there is any established algorithm for this problem. It is obviously related to more general projective reconstructions where the views are not necessarily observed from orthogonal planes, and the orientation of those planes is typically unknown.

$\endgroup$
1
$\begingroup$

Thinking about it even more, I feel like the problem resembles triangulation of lines under orthographic camera model. It is possible and useful to visualize the setting in 3D: enter image description here

The blue vector is what we like to recover. The identity element for the orthographic camera and projection matrices are defined respectively as: $$ K=\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \\ \end{bmatrix}\quad P=\begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1\\ \end{bmatrix} $$

I will base my explanations on the following papers, which you should consult in case this method is to be implemented:

Wu, Fuchao, et al. "Algebraic Error Based Triangulation and Metric of Lines." PloS one 10.7 (2015): e0132354. https://pdfs.semanticscholar.org/5f79/2b04f318c6923496ab475168f6e94adfe93e.pdf

Bartoli, Adrien, and Peter Sturm. "Structure-from-motion using lines: Representation, triangulation, and bundle adjustment." Computer vision and image understanding 100.3 (2005): 416-441. https://hal.archives-ouvertes.fr/hal-00092589/document

To benefit from these well studied tools, it is possible to think of this scenario as a $k-D$ line imaged from $k$ cameras. It is also good that we have a large baseline.

Now, in the examplary figure provided above, one could think that each 2D line is composed of $2$ end-points $l_i=\{(x_1,y_1), (x_2,y_2)\}$. This is the standard two-point parameterization. Note that the precise location of the end points only effects the precision and has no theoretical implications. This will be clearer later. I will also parameterize the unknown 3D line $z$ as a homogeneous Pluecker vector $L \in \mathbb{R}^6$: $$ L \triangleq \begin{bmatrix} u \\ v \end{bmatrix} $$ where the 3D vectors $u^Tv=0$. $L$ is defined only up to a scale, and hence it follows: $$ L^T \begin{bmatrix} & I_3 \\ I_3 & \end{bmatrix} L = 0 $$

We can also define a $3 \times 6$ line-projection matrix $\hat{P}$ from a standard camera projection matrix $P=K [R | t]$ by the following equation:

$$ \hat{P} = \begin{bmatrix} det(P)R & [t]_xR \end{bmatrix} $$

The solution to the line triangulation problem can be obtained through a closed form solution:

$$ L^{\star} = \arg\min_{L} L^T A L \quad \text{s.t. } L^T \begin{bmatrix} & I_3 \\ I_3 & \end{bmatrix} L = 0 \,\, \text{ and } \,\, L^T L = 1 $$ The second condition only avoids the trivial solution. $A$ can be defined as follows: $$ A = \sum\limits_{i=1}^{\text{# views}} \hat{P}_i (\sum\limits_{j=1}^{2}l_{ij}^Tl_{ij}) \hat{P}_i $$

The resulting $L$ may not satisfy the Pluecker constraint and hence it might need a correction (projection onto the Pluecker vectors or the Klein quadric). This operation can be found here or here. The obtained line does not specify the sign of the direction of course, but I guess this can easily be imposed as prior or found from the orientation of 2D projections (e.g. sample two points on the line, project and if vectors do not align, reverse).

What is presented above minimizes an algebraic error term that is not always the most desired energy. Of course for this problem a true geometric fit in this sense of MLE cannot be written in closed form. Bartoli and Sturm (see above) provide at least two alternatives, a quasi-linear and a non-linear refinement of this initial fit. If you are keen on getting the most accuracy, then a subsequent non-linear optimization is definitely worth looking into.

The computer vision tools are generally devised for 2D/3D scenarios. For lower dimensions, e.g. 2D, this algorithm can be simplified. However, it might not be easy to generalize the aforementioned approach to $N$-dimensions. Though, the idea and the essence of the approach would be identical.

$\endgroup$
  • $\begingroup$ Hi Tolga - many thanks for this. I think this is the lead I was looking for. For me N would be typically between 3 and 4, and I have a code which seems to work for larger values but I'm very aware of reinventing the wheel and making something that is square. I'll accept your answer and update my question with comments to say what I did. $\endgroup$ – drw Feb 26 at 7:23
  • $\begingroup$ You're welcome. Note that due to over-parameterization I'm not sure whether this works for less than 3 projections for the case of 3D. $\endgroup$ – Tolga Birdal Feb 27 at 19:04
1
$\begingroup$

The problem seems quite ill posed so I will assume some level of over-determinism is there.

First, note that your vector, $\mathbf{z}$ lives on a hypersphere. Thus, it is indeed on a $(k-1)$ dimensional manifold, $\mathcal{S}^{k-1}$. Then, because you don't know the scales, we could always write the problem as linear combination of $k$ unit vectors, $\{\mathbf{v}_i\in \mathbb{R}^{k}\}$, absorbing the unknowns into the linear coefficients:

$$ \mathbf{z}= \lambda_1\mathbf{v}_1 + \lambda_2\mathbf{v}_2 + \cdots + \lambda_{k}\mathbf{v}_{k} $$

As you said you could overspecify $k$, I will, for the moment, assume that $\mathbf{v}_{k}$ is available.

Let us write those vectors in a matrix: $$ \mathbf{V} = \begin{bmatrix} \mathbf{v}_1 & \mathbf{v}_2 & \cdots & \mathbf{v}_{k-1} & \mathbf{v}_{k} \end{bmatrix} $$

Since both $\mathbf{z}$ and $\{\mathbf{v}_i\}$ are unit length, $\boldsymbol{\lambda}=\{\lambda_i\}$ must be unit length: $\|\boldsymbol{\lambda}\|=1$. $\mathbf{z}$ can then be written as:

$$ \mathbf{z} = \mathbf{V} \boldsymbol{\lambda} $$

Of course $\mathbf{z}$ and $\boldsymbol{\lambda}$ are the unknowns. If we have multiple projection sets (different subsets can reconstruct $\mathbf{z}$) then $i=1\dots L$ and $L>>k$ growing $\mathbf{V}$ in width, while keeping each column unit length. In contrast, we will have a set of $\boldsymbol{\lambda}$ vectors, for each projection set: $\boldsymbol{\Lambda}=\{\boldsymbol{\lambda}_i\}$. We can then write the above relation as:

$$ \mathbf{Z}_{k\times D}=\mathbf{V}_{k \times L}\boldsymbol{\Lambda}_{L \times D} $$ where $\mathbf{Z}=\begin{bmatrix} \mathbf{z} & \mathbf{z} & \cdots & \mathbf{z}\end{bmatrix}$ as each of the $D$ projection sets should recover the same $\mathbf{z}$.

At this stage, I propose to pick two paths:

1. Alternating Optimization Start with initializing $\mathbf{z}$ to the expected value. To do that we assume $\lambda_i=1/L\,\,\forall i$ and compute $\mathbf{z}_i = \mathbf{V}\boldsymbol{\lambda}_0\,\,\forall i$ (At this stage you could also use your initialization). We can then iterate as:

a. $t=0$.

b. Fix $\mathbf{z}=\mathbf{z}_t$ and solve: $$ \boldsymbol{\Lambda}^{\star}=\arg\min_{\boldsymbol{\Lambda}} \|\mathbf{Z}_t-\mathbf{V}\boldsymbol{\Lambda} \|_F $$ c. Fix $\boldsymbol{\Lambda}_t=\boldsymbol{\Lambda}$ and solve: $$ \mathbf{z}^{\star}=\arg\min_{\mathbf{z}} \|\mathbf{Z}_t-\mathbf{V}\boldsymbol{\Lambda} \|_F $$ d. $\mathbf{z}_t\gets \mathbf{z}^{\star}$, $\,\,t\gets t+1$. Iterate to (b)

2. Sparse Coding Note that under the observation that the number of projections (in high dimensions) grow with factorial, and the desired vector can be reconstructed from a minimal subset of projections (thus sparse $\boldsymbol{\lambda}$), this can potentially (and sorry if I made a mistake already) formulated as a sparse coding problem, that tries to learn $\boldsymbol{\Lambda}$ and $\mathbf{z}$ simultaneously.

From this perspective $\mathbf{Z}$ denotes a dictionary, and $\boldsymbol{\Lambda}$ a representation that we simultaneously like to learn to recover the input, $\mathbf{V}$. The result of this will hopefully be multiple $\mathbf{z}_i$ corresponding to the columns of the learned $\mathbf{Z}$. We could for instance average those to get the most probable solution.

I will take a look at the details of this and update soon.

$\endgroup$
  • $\begingroup$ Many thanks for this. I guess I may have done something similar in which my $L_2$ approach only I used the more naive approach of simply optimising the estimates for $z$ and my view rescaling factors $\{\lambda_i\}$ in the same numerical optimisation step. The dimensions are are low - in single figures - and it seemed to work. The alternating directions idea is certainly nice. I still wonder if there is a cut down version of the more general projective reconstruction theory here. $\endgroup$ – drw Feb 24 at 21:49
  • $\begingroup$ Added another answer along the projective reconstruction. $\endgroup$ – Tolga Birdal Feb 25 at 0:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.