ICCV Workshop: Multiview Relationships in 3D Data (MVR3D 2017)

This year, in Venice, in conjunction with one of the best computer vision conferences, International Conference on Computer Vision (ICCV), I am co-organizing the workshop of Multiview Relationships in 3D Data (MVR3D 2017). .
I am very excited to announce that we have a marvelous list of speakers, and are looking forward to an amazing set of papers and presentations. We grant awards to authors of all accepted papers, and give out very exclusive awards for the best papers. So make sure to check it out: mvr3d.github.io

Here are the speakers:
Andrew Fitzgibbon, Partner Scientist, Microsoft Research
Alex Bronstein, Associate Professor, Tel-Aviv University
Vladlen Koltun, Principal Scientist, Intel
Radu Horaud, Senior Research Scientist, INRIA
Andreas Nüchter, Professor for Telematics, Julius-Maximilians-University
Konrad Schindler, Professor, ETH Zurich
Chrisopher Zach, Research Scientist, Toshiba Europe
Luc Robert, Software Architect, Fellow, Bentley

A short list of topics:

• Global point cloud alignment
• Multiview registration using scene priors
• Learning methods for multiview correspondence estimation
• 3D Object reconstruction from multiple views
• Joint registration and segmentation of multiple scans
• Joint matching of multiple non-rigid surfaces
• Multiview object detection
• Multi-object Instance reconstruction
• Feature descriptors for multiview 3D matching
• Multiview pose estimation
• Joint processing of multiple point clouds
• Pose averaging and error diffusion on graphs
• Multiview stitching of 3D scans on mobile and embedded devices
• Practical applications of multiple scan registration on large scale settings
• Datasets and dataset methods for ground truth acquisition

Here are the organizing committee:
Tolga Birdal, Technical University of Munich
Emanuele Rodolà, Università della Svizzera Italiana
Gul Varol, INRIA
Slobodan Ilic, Siemens AG
Umberto Castellani, University of Verona
Andrea Torsello, Ca' Foscari University of Venice

Looking forward to meeting all at this exciting event in Venice! #MVR3D2017

A Note on Projective Splines

In this post, I'll make a seemingly in-obvious remark on the great work of Projective Splines by Thomas Lewiner and Marcos Craizer. Special thanks to Marcos Craizer for the discussion. The paper of interest is Projective splines and estimators for planar curves. The goal of the paper is an invariant spiral construction in the canonical projective frame. The setting looks like:

The idea is to use \(3\) points augmented by the tangents to generate new points and exploit the cross ratio in estimation of two projective invariants: projective length and projective curvature. The spline construction is basically done by solving a linear system in Section 3c. There, the last pair of equations require \((P_{x,3},P_{y,3})\), which are not explicitly given in the paper. Here I'll provide the expression for that: Following Section 3a, knowing \(P\), the standard spiral, the spiral corresponding to the newly generated point \(x_{i,3}\) could be written as \(\mathbf{P}_3(\sigma_i) = \mathbf{P}(\sigma_i) + t\mathbf{W}\). Here $$W(\sigma)=a e^{a\sigma}$$ and \(t\) is given in Section 3a. Also, \(a=\frac{3}{2}+\frac{i\sqrt{3}}{2}\). Here the complex notation is used to jointly represent coordinates \((x,y)\). If we plug \(a\) into \(W\): $$ \begin{align*} W(\sigma)&=a e^{a\sigma}\\ &=(\frac{3}{2}+\frac{i\sqrt{3}}{2}) e^{3\sigma/2} e^{\sqrt{3}i\sigma/2} \\ &=(\frac{3}{2}e^{3\sigma/2}+\frac{i\sqrt{3}}{2}e^{3\sigma/2}) e^{\sqrt{3}i\sigma/2} \\ &=\bigg(\frac{3}{2}e^{3\sigma/2}+\frac{i\sqrt{3}}{2}e^{3\sigma/2}\bigg) \bigg(cos(\frac{\sqrt{3}\sigma}{2})+i sin(\frac{\sqrt{3}\sigma}{2})\bigg) \text{ (via Euler's Formula)}\\ \text{fast forwarding...} & \\ &=\frac{\sqrt{3}}{2} e^{3\sigma/2} \bigg( \frac{\sqrt{3}}{2} cos(\frac{\sqrt{3}\sigma}{2}) - sin(\frac{\sqrt{3}\sigma}{2}) \bigg) + i \frac{\sqrt{3}}{2} e^{3\sigma/2} \bigg( \frac{\sqrt{3}}{2} sin(\frac{\sqrt{3}\sigma}{2}) + cos(\frac{\sqrt{3}\sigma}{2}) \bigg) \end{align*} $$ We could now define the vector \(\mathbf{W}\) to be: $$ \mathbf{W} = (W_x, W_y, W_z)^T = \begin{bmatrix} \frac{\sqrt{3}}{2} e^{3\sigma/2} \bigg( \frac{\sqrt{3}}{2} cos(\frac{\sqrt{3}\sigma}{2}) - sin(\frac{\sqrt{3}\sigma}{2}) \bigg) \\ \frac{\sqrt{3}}{2} e^{3\sigma/2} \bigg( \frac{\sqrt{3}}{2} sin(\frac{\sqrt{3}\sigma}{2}) + cos(\frac{\sqrt{3}\sigma}{2}) \bigg) \\ 1 \end{bmatrix} $$ Note that the linear system uses only two components of \(\mathbf{P}_3\), letting us to set \(W_z=w=1\). Now, let's get back to Section 2b to define: $$ \mathbf{P} = (P_x, P_y, P_z) = \begin{bmatrix} e^{\sigma/2}cos(\frac{\sqrt{3}\sigma}{2})\\ e^{\sigma/2}sin(\frac{\sqrt{3}\sigma}{2})\\ e^{-\sigma} \end{bmatrix} $$ being the components of standard spiral. To obtain the projective curve at w=1, we have to multiply all components by \(e^{\sigma}\). Plugging in \(\mathbf{P}_3(\sigma_i) = \mathbf{P}(\sigma_i) + t\mathbf{W}\) results in: $$ \mathbf{P}_3 = (P_{x,3}, P_{y,3}, P_{z,3})^T = \begin{bmatrix} e^{3\sigma/2}cos(\frac{\sqrt{3}\sigma}{2}) + t \frac{\sqrt{3}}{2} e^{3\sigma/2} \bigg( \frac{\sqrt{3}}{2} cos(\frac{\sqrt{3}\sigma}{2}) - sin(\frac{\sqrt{3}\sigma}{2}) \bigg) \\ e^{3\sigma/2}sin(\frac{\sqrt{3}\sigma}{2}) + t\frac{\sqrt{3}}{2} e^{3\sigma/2} \bigg( \frac{\sqrt{3}}{2} sin(\frac{\sqrt{3}\sigma}{2}) + cos(\frac{\sqrt{3}\sigma}{2}) \bigg) \\ t \end{bmatrix} $$ Here is the MATLAB code:

% requires P (the standard spiral), t (step), sigma (projective length)
% computes the canonical coordinate P_3
function [P3] = compute_p3(P, t, sigma)
s32 = sqrt(3)/2;
coeff = s32 * exp(1.5*sigma);
W = [
    coeff .* (s32.*cos(s32.*sigma) - sin(s32.*sigma));
    coeff .* (s32.*sin(s32.*sigma) + cos(s32.*sigma));
       1
];
P3 = P + t.*W;
end

A Better Approach to Plane Intersection

One interesting problem, arises in many geometric algorithms is the intersection of two planes. For sure, this problem has a well studied textbook answer, which I don't find particularly elegant. This is because, the solution is depends on picking an arbitrary point, which lacks geometric intuition. Ideally, we'd like this point to have some meaning, such as being close to the planes, or the line or etc. For that, in this post, I'd like to remind you of a solution by John Krumm, which remains to be unnoticed by many. While the plane-plane intersection problem is well studied, for our purposes, we would like to summarize a different, more effective approach. The textbook solution to the problem depends on picking an arbitrary point, which might lack geometric intuition. Ideally, we'd like this point to have some meaning, such as being close to the points, planes, or the line or etc. Let \(\mathbf{p}=\{p_x,p_y,p_z\}\) and \(\mathbf{n}=\{n_x,n_y,n_z\}\) compose the plane \(\mathbf{P}=\{\mathbf{n},\mathbf{p}\}\). Let there be two planes \(P_1\) and \(P_2\), for which we'd like to compute the intersecting line \(\mathbf{l}\). Let's first review the standard solution. It's trivial to compute the direction as the cross-product: \begin{equation} \mathbf{l}_d=\mathbf{n}_1 \times \mathbf{n}_2 \end{equation} We then pick an arbitrary point (origin, or the midpoint) \(\mathbf{p}_0\), plug it into both the equations and solve for the unknowns. At this stage there is no meaning of \(\mathbf{p}_0\). In the following, we'll pick this point to be the midpoint of the input points. Basically, we desire that the resulting point \(\mathbf{p}\) is as close to the chosen point \(\mathbf{p}_0\) as possible. Thus, we could write a distance : \begin{equation} \lVert \mathbf{p}-\mathbf{p}_0 \rVert = (p_x-p_{0x})^2 + (p_y-p_{0y})^2 + (p_z-p_{0z})^2 \end{equation} Incorporating the other points in the similar fashion, and writing this constraint using Lagrange multipliers into an objective function results in: \begin{equation} J=\lVert \mathbf{p}-\mathbf{p}_0 \rVert+\lambda(\mathbf{p}-\mathbf{p}_1)^2 + \mu(\mathbf{p}-\mathbf{p}_2)^2 \end{equation} Using the standard Lagrange framework (omitting the details), one establishes a nice matrix, in the form: \begin{equation} M= \left[ {\begin{array}{ccccc} 2 & 0 & 0 & n_{1x} & n_{2x}\\ 0 & 2 & 0 & n_{1y} & n_{2y}\\ 0 & 0 & 2 & n_{1z} & n_{2z} \\ n_{1x} & n_{1y} & n_{1z} & 0 & 0\\n_{2x} & n_{2y} & n_{2z} & 0 & 0 \end{array} } \right] \end{equation} This matrix can now be used in a system of linear equations: \begin{equation} \mathbf{M}\left[ {\begin{array}{c} p_x \\ p_y \\ p_z \\ \lambda \\ \mu \end{array} } \right] = \left[ {\begin{array}{c} 2p_{0x} \\ 2p_{0y} \\ 2p_{0z} \\ \mathbf{p}_1 \cdot \mathbf{n}_1 \\ \mathbf{p}_2 \cdot \mathbf{n}_2 \end{array} } \right] \end{equation} to solve for the unknown point, \(\mathbf{p}\), as well as the Lagrange multipliers, \(\{\lambda, \mu\}\). While the multipliers are not of particular interest they would be interesting for understanding configuration of points, or for different parametrizations. Here is the MATLAB script:

% Robust plane to plane intersection
% Plane is parameterized by a point and a normal.
function [p, n] = intersect_planes(p1, n1, p2, n2, p0)

M = [2 0 0 n1(1) n2(1)
     0 2 0 n1(2) n2(2)
     0 0 2 n1(3) n2(3)
     n1(1) n1(2) n1(3) 0 0
     n2(1) n2(2) n2(3) 0 0
    ];

b4 = p1(1).*n1(1) + p1(2).*n1(2) + p1(3).*n1(3);
b5 = p2(1).*n2(1) + p2(2).*n2(2) + p2(3).*n2(3);
b = [2*p0(1) ; 2*p0(2) ; 2*p0(3); b4 ; b5];

x = M\b;
p = x(1:3);
n = cross(n1, n2);
end

Direct Visibility of Point Sets

\(\newcommand{\norm}[1] {\lVert #1 \rVert}
\)
Given a set of points \(P=\{p_i | 1\lt i \lt N\} \in \mathbb{R^{D}}\), and a viewpoint \(C\), the goal is to determine the visible points \(\forall p_i \in P\) with respect to \(C\). The method is based on Sphreical Flipping), where each \(p_i \in P\) is reflected about a sphere, centered at \(C\) and constrained to include all points in \(P\). The flip operator is defined as follows:

\begin{equation}
\hat{p_i} = p_i + 2(R-\norm{p_i})\frac{p_i}{\norm{p_i}}
\end{equation}

Generously, Katz et. al. provide a theoretical proof as well as MATLAB implementation within the paper. We further improve this implementation by applying simplifying \(\hat{p_i}\):

\begin{equation} \label{eq1}
\begin{split}
\hat{p_i} & = p_i + 2(R-\norm{p_i})\frac{p_i}{\norm{p_i}}\\
 & = p_i + \frac{2R}{\norm{p_i}}p_i - 2p_i \\
 & = p_i (\frac{2R}{\norm{p_i}}-1)
\end{split}
\end{equation}
Using this reduction and cpu-friendly optimizations, we could provide a shorter, simpler and more efficient algorithm for the visibility problem. In comparison to the original, our MATLAB implementation runs twice as fast, while significantly reducing the memory usage. Our C implementation is more than \(5\) orders of magnitude faster, easily achieving realtime capability even for very large point clouds.

Shock Filtering

As a first post to this blog, I will be referring to my Shock Filter implementation, which I believe is a great image processing tool to both get idea on PDEs and to come up with a practically working algorithm.

Quoting J. Weickert,

Shock filters are based in the idea to apply locally either dilation or erosion process, depending on whether the pixel belongs to the influence zone of a maximum or a minimum. They create a sharp shock between two influence zones and produce piece-wise constant segmentation.

Principle of shock filtering is applying dilation and erosion operations in order to satisfy the differential equation: $u_t=s|\nabla u|$ on the function $u$ defined by the gray values in the image. The decision between dilation and erosion is made using the signum function based on Laplace operator. Applying such a procedure produces a sharp discontinuity called shock at the borderline between two influence zones. The resulting equation reads $$u_t=-sign(\Delta u)|\nabla u|$$ Because Laplacian is a second derivative operator, using it alone will not be noise prone. For this reason, in order to make the edge detector more robust, $u_t$ is smoothed at each iteration by a Gaussian kernel. The rest is simply solving the mentioned PDE in an iterative fashion. The resulting effect is basically enhancement/sharpening of the input image. Below is a sample from Shock Filtering:

Entire source code can be found here

References

F. Guichard, J. Morel; “A Note on Two Classical Shock Filters and Their Asymptotics”; Michael Kerckhove (Ed.): Scale-Space 

and Morphology in Computer Vision, LNCS 2106, pp. 75-84; Springer, New York; 2001. 

G. Aubert, P. Kornprobst; “Mathematical Problems inImage Processing”; Applied Mathematical Sciences 147; Springer, New 

York; 2002. 

J. Weickert Coherence-enhancing shock filters; In B. Michaelis, G. Krell (Eds.): Pattern Recognition. Lecture Notes in Computer 

Science, Vol. 2781, Springer, Berlin, 1-8, 2003.