PDF version of this entire document
All the prior experiments weighed eyes and nose regions equally, not quite permitting one to discern the impact of each components (no visualisation tools for the task). As a systematic experiment that aids understanding, someone could isolate these two. So, as a little exploratory experiment, hard cases were piled together to just see what areas of the faces - if taken in isolation - provide better recognition rate at borderline cases. The conclusion drawn from it is that the eyes region contains valuable discriminatory properties.
|
Work on exact geodesics had begun before the above experiments were concluded.
Work then involved Michael Zibulevsky who was working on exact geodesics. One is looking forward to the boosting. Regarding GMDS and high resolution. The issue is that currently the GMDS is using fast marching (FMM) to compute geodesics, which is a first order accurate scheme. There are alternatives which include using 2nd order method, also called exact, for computing geodesics. Note that with exact geodesics, the interpolation phase should also be replaced with an exact distance computation. It could be exact at least on the polyhedron approximating the surface.
These exact 2nd order methods have been studied We I suspended other experiments for the time being.
The MATLAB code is an enclosure of existing code. The code is an implementation of geodesic methods as per MMP (Mitchell, Mount and Papadimitriou). It is an improved implementation with some C code that scales gracefully. Ir proceeds by identifying shortest paths on a graph in a way that is similar to FMM.
The algorithms/code are at http://code.google.com/p/geodesic/http://code.google.com/p/geodesic/.
This is an implementation of exact geodesics algorithm for a triangular mesh (first described by MMP) with some minor improvements, extensions, and simplifications. The algorithm has O(n^2 log n) worst-case time complexity, as opposes to O(n log n) in FMM.
In searching for exact geodesic it follows an approach similar to [31].
In our own experiments (thus far), we have been running experiments with just several hundreds of triangles that are coarse equivalents of face parts such as the nose and eyes. There is a limitation due to scale and accuracy, affecting whatever assesses similarity based on FMM-derived distances, which discrete nature (and no interpolation) makes the measurements an approximation.
We still suffer from dependence on the degree of information loss, resulting from pixels-to-meshes conversion. Fast Exact and Approximate Geodesics on Meshes describes in some level of detail the approaches of others who tackled the same problem on dense meshes composed of triangles and explains why operations like these are commonly applied to polygons in general (for computer vision, computer graphics, and more). It says that shortest paths typically cut across faces in the mesh and are therefore not found by the traditional graph-based Dijkstra algorithm for shortest paths. Contrariwise, Surazhsky proposes an exact algorithm for an efficient implementation of the method from Mitchell, Mount, and Papadimitriou (MMP). He can do better than O(n2 log n) in practice, nearly removing the quadratic complexity (reduced to linear) and claiming to be able to deal with half a million triangles in less than a minute, giving all-to-all distances. For the one-to-one case, the claimed performance is a few seconds for a mesh with approximately 1 million triangles.
Another suggested paper is [1].
The paper deals with partly missing data too. It cites Kimmel and Sethian as present[ing] an approach called Fast Marching Method (FMM) on triangular domains that computes approximations to the geodesic distances from one source point on S to all other points of S by solving the Eikonal equation on a triangular grid. The algorithm's running time is O(n log n) and therefore optimal. The accuracy of the approach depends on the quality of the underlying triangulation; namely on the longest edge and the widest angle in the triangular mesh.
The paper proposes a heuristic solution based on multi-dimensional scaling, which is similar to classical PCA or PCO. They have very few experimental results, with holes added to a human body mesh with 20002 vertices
We shall see how different measurements - exact and approximations - affect recognition performance when the number of triangles is kept intentionally low (for speed).