Detect rigid body motions in a cloud of points

Question

This question popped up today in our group meeting. Suppose you are given a cloud of N points in 2D and each is associated with a velocity vector. These points are associated with particles on a 2D interface and velocities are obtained via simple particle tracking.

The interface we are studying is not "clean" in the sense that there are solid "island" spread over the liquid interface. As a results, some of the particles actually sit on the said islands while remaining ones are spread on the liquid interface.

Here's the question: Given the velocity information can you determine and isolate the particles on the solid islands? I did a quick search but could not find anything useful but came up with a simple algorithm based on computing relative angular velocities between all particle pairs. If particle $\mathbf{p}_i$ and $\mathbf{p}_j$ belong to the same rigid body, then one can write: $$\mathbf{v}_j = \mathbf{v}_i + \Omega_{ij} \:\hat{\mathbf{k}} \times \mathbf{r}_{ji},$$ where $\mathbf{r}_{ji} = \mathbf{r}_j - \mathbf{r}_i$ is the relative position. For any particle $\mathbf{p}_k$ that belongs to the same rigid body, one requires that $\Omega_{ik} = \Omega_{jk} = \Omega_{ij}$. Finally I detect the islands by generating a histogram of the matrix entries and looking of the peaks.

Here is a sample made-up examples, were a bunch of random points are considered. Red and blue particles belong to two different rigid bodies with $\Omega_{red} = 5$ and $\Omega_{blue} = 10$. Black particles are assumed to be Brownian and have random velocities. As you can see the histogram detects two peaks at 5 and 10 but also fictitious peaks around 0.

Can you think of a better algorithm or point me to some references?

Answer 1

Your algorithm makes sense, but is going to be too slow if you have many particles because you do pairwise comparisons. But there are other ways of looking at your data. Let us imagine for a moment that if you had islands that only moved but did not rotate. Then imagine each particle to be a point in 4d space: its two spatial coordinates plus the two components of its velocity vector. In effect, then, you will find islands as clusters of points that aren't just closely located but also are close in their velocities -- in other words, you will need to find clusters of particles in 4d space. There is a whole field in statistics that deals with this question -- cluster analysis.

The situation is a bit more complex if you allow islands to also rotate. In that case, the particles on islands are characterized by 7-dimensional vectors: the two location coordinates, the two components of the linear velocity of the island, the two components of the rotation center of the island, and its angular velocity. The problem is that if you only analyze two subsequent pictures all you get are four pieces of information for each particle: its position and its velocity. In other words, each particle occupies a three-dimensional manifold within the 7-dimensional space. Identifying islands then comes down to finding locations of your 7-dimensional space where multiple of these manifolds cluster.

(If you can analyze more than 2 frames, you may be able to determine whole arcs of particle motion, and in that case you will get more than 4 pieces of data if the arcs are not straight, since then only certain rotation centers and angular velocities are compatible with the arc. You should then be able to reduce the dimensionality of the manifolds, which should also make finding clusters easier.)