HE task of comparing atomically-meaningful 3-D surfaces is not simple. The plethora of diffusion-based techniques have not managed to overcome the drawbacks and ever surpass the performance attained through geodesic distances. The main issue, to summarise this very briefly, is that when the differences are very small between one subject and another (no topological differences) there is not enough that can be done to distinguish by kernel-based score.

I have meanwhile returned to geodesics again. Based on literature surveys from a few years ago (I read three with great interest), for 3-D in isolation the verification rates are almost always worse than for 2-D (and of course 3-D plus 2-D), which brings up the question, what type of performance levels are expected from 3-D alone in order to make a technique publishable? With our best methods we hover around the mid-nineties. With further refinements that do not require 2-D data we can make further improvements, but there are inherent difficulties. For example, as I showed a colleague at the lab some pairs of different range image (in 3-D) she was unable to tell if there were the same or not. When the similarity is high it becomes almost about gut feeling or guesswork, even for verification as opposed to identification (one-to-many or many-to-many).

Additionally, spectral methods degrade poorly compared to geodesics, as shown in the images below (first a meaningful slicing, then improper).

Spectral examples

Spectral problems

I am currently working on a concise report about this project (which has exceeded a year in duration so far). There’s a lot more coming. I also added some list of side projects (totally unrelated) I’ve been working on recently. I hope to focus more on ERC-funded work and not whatever pays more (industry pays more than academic). But all these are a matter to be discussed another day.

COLLEAGUE has said that diffusion-based methods were never quite so suitable for the task of analysis of surfaces where differences are very subtle. However, even when poorly adjusted, performance can be somewhere at the range of 80% recognition (3-D only, we never use 2-D). It is not clear how to divide the face and one suggestion made at the lab last week (when face-to-face meetings took place) is that smoothing methods should be changed and parts that are problematic removed altogether to reduce noise-to-signal ratio. With diffusion-based methods, performance exceeding 90% should be attainable, but it still trails behind some other methods that we tested.

I have read a lot of literature (5 papers) that presents surveys with performance benchmarks. For 3-D alone, the recognition (verification) results are not so high, at least based on surveys from a few years back. I’ll further refine diffusion-based methods as more capable computational servers return online (after over a week of partial downtime).

For context, see this previous post and some example results (GMDS and ROC curve).

VER the past few days progress has been made primarily by exploring diffusion-based methods, having come to the point where geodesics cannot quite have their resultant performance improved any further. So far I got just one mistake in the GMDS-based approach and none in the other FMM-based approach, so it is looking similar to what I saw before. If I can rid myself of all errors (even in hard cases), that will be great, but it depends on the inherent limitations and strengths of the methodology, not the will.

The latest experiment showed comparable performance (w.r.t. prior experiments) but it is a lot slower, so I switched back to 2000 vertices and tried 300 points (to find correspondence for) rather than just 100 as before.

This aforementioned approach did indeed seem to improve things somewhat, but it would take longer experiments to provide good empirical evidence for it (need for harder pairs to distinguish based on many false negatives/positives). The only pair that causes trouble at the moment (among about 60 pairs that are being tested) is one that looks similar but is actually of different subjects. GMDS also detects it as being similar enough to fall near the border but at the side of true pairs rather than false ones. Let’s just take a face example (the methods are generic and can be applied to other data).

Some of my more recent modifications did not succeed at resolving the more problematic cases — ones where pairs are too similar/dissimilar to make an accurate assessment (it would be interesting to know how other methods cope with those as even a human observer would struggle, despite our brains being well wired to recognise faces). Doing 2D+3D or just 2D might in some sense be easier than 3D only, depending on the methods tested.

The other issue is, very consistently I find that GMDS is outperformed by a simpler FMM-based method that I implemented, without exceptions (the latter is a lot faster). But the mask continues to be modified in accordance with prior results and some observation of the stress (shown in different shades of grey upon points inside Voronoi cells) studied. If we hit a recognition barrier at around 97% (depending on the datasets), then perhaps using a mixture of methods would help, e.g. shape descriptors where the photometric data is encoded as geometric. I will revisit heat kernel signature and see if I can make those work better than before, then incorporate newer code like the stuff most recently published.

Now, moving on to heat kernel signatures we get some encouraging early results. With improvements to the code and to the masks, I have reimplemented the diffusion-based thresholding around landmark points and preliminary tests suggest high recognition performance. However, at this stage, the code is not stable, so it takes a lot of effort to produce a ROC curve. Performance of the diffusion-based comparator seems to have been vastly improved since last month, but there are still some issues to overcome. Heat kernels, being less dependent on the plane’s surface than geodesics calculated upon triangles, sometimes leave isolated patches that penalise and significantly increase the dissimilarity score, removing much of its signal. Maybe both distance types can be fused to resolve this in an ad hoc fashion. The first image just shows what happens if the surface if fragmented, the second shows what happens when it’s all in one unit. The third and fourth images provide examples of diffusion-based cutoffs leaving small ‘islands’ that pose a challenge.

Over the past two days I have running some more experiments that look at what can be refined for better performance. At some adjustments of the parameters it seems to hit the sweet spot for a couple dozen pairs, but then the errors start creeping in. Basically, pairs belonging to different people do not entail big enough a penalty, even when they are clearly quite different. I am getting closer though, to the extent one can given GMDS as the instrument of choice…

No classification mistakes were made after I had adjusted several parameters appropriately. Having explored high density sampling, I found that it works reasonably well at around 2000 vertices, 20 GMDS operations on each pair, and as many as 30 levels in the multi-scale approach (this does not take long with the C++ implementation). The performance achieved is quite satisfactory and after trying all kinds of masks I ended up with a new type of mask, one which is intentionally asymmetric so as to help GMDS not flip any faces over (around the Y axis, horizontally rather than vertically), thus always comparing like with like.

I have made lots of progress although much of the progress was not documented in a detailed fashion. This was done in order to make improvements more rapid and not too dependent on formality.

There is a lot more room for improvement, so these results are just a glimpse at the sort of level easily attained. Shown are the results from the latest experiments.

FMM-based method ROC curve

GMDS-based method ROC curve

More images and explanations will now follow.

A 20-layer approach before buxfixes

2 pairs after bugfixes

Mismatches after some bugfixes

Correct matches after some bugfixes

A 20-layer coarse correspondence check

Same as above but with smaller mask

Same as above but with further improvements

Currently I am looking at whether or not doubling the number of vertices again will lead to improvements. Previous experiments suggest that at a certain point it might leads to exacerbation.

have put a colleague’s code to use and explored the possibility of doubling the number of points given the vastly faster implementation. Surprisingly, however, with additional points there is somewhat of a struggle to find the correct macro-correspondence, even within real pairs of surfaces that are not so intrinsically different (and 15 levels in the multi-scale approach, coarse-to-fine).

I am running some more experiments that look at what can be refined for better recognition/classification performance. Shown below are segmentations (based on correspondence) of pairs of surfaces with 400 and 600 Voronoi cells.

Overnight I ran a GMDS-intensive experiment to see how good a signal — for discriminative purposes — one can get with a 40-step geodesic dilation iterative process — the type of process that previously gave very good discriminative power (mistake once in about 40 comparisons). It would be heartening to believe that given the right formula (black art of adjusting parameters) GMDS will provide a flawless test, or maybe make up one of a series of tests that achieve it. At the moment, all experiments measure 5 different things at the same time in order to reduce the need to rerun lengthy experiments.

N the previous post on this subject we looked at the masks used in a GMDS pipeline tailored for recognition purposes. The question now is, what would be a constructive way to progress from the conclusion?

Well, the goal is to beat the competition and do so with methods of a particular kind — the kind we advocate — which seems achievable but requires a lot of tinkering, seeing where and how mistakes can be resolved/avoided.

An additional experiment, taking about a day to complete, shows not much promise. Its goal is simply to compare the performance of GMDS with the new Fast Marching Methods-based measures (faster) when all parameters are kept consistent across runs. With many rings, many points, and many vertices, recongition performance is relatively poor because of the hard dataset, as demonstrated by the ROC curve. The point to note though is that in hard cases GMDS is outperformed by the other approach. One question is, are there any measurable quantifies (other than stress) resulting from GMDS and capable of assessing similarity?

GMDS multiple runs

FMM-based

There are some additional results from the last set of shallow, comparative tests. By applying the same experiment’s parameters to test an antiquated triangle-counting approach and a best fit GMDS approach (rather than average over multiple runs) we get two more ROC curves.

Triangle counting

GMDS best fit

Finally, using this same difficult set (where problematic cases are included) we get a ROC curve for the standard GMDS approach.

Simple GMDS

In GMDS one could either work with and L₂ norm (which is what we do right now) or L_infty. In fact, if one takes the log of the distances and apply GMDS, one does, in a sense Lipschitz embedding. The diffusion distances could also be used within the GMDS framework. In fact, with better interpolation properties, one can interpolate the eigenfunction before integrating the distance itself…

I spoke to a colleague about L_infty and I now attempt to compile it on GNU/Linux (not done before). It would be interesting to know if GMDS been tested where D is computed based on spectral properties (not as geodesics). There an IJVC paper with Sapiro in which this is done; in it, the authors are also finding symmetries that way.

HIS post is part of a series that explores the potential of comparing surfaces using GMDS, or generalised multidimensional scaling.

A 15-level multi-resolution approach has led to no classification errors being made, at least thus far. This may have helped prevent the convergence near local minima, but it is painfully slow, especially when the C++ implementation does not get used. I have looked into more ways to widen the separation between correct pairs (same person) and incorrect pairs. I have begun looking at the impact of two factors; one is the size of the mask used prior to GMDS (or dilation through iteration) and another is the number of multi-resolution levels. Based on an ongoing experiment, a very coarse correspondence/initialisation leads to something quite reasonable when the pairs belong to the same subject and everything is a lot quicker and a bit of a mess otherwise (see the first two images).

At 3 cumulative levels in the multi-resolution reproach, a false classification does not take long to occur, so I increased that to 15 and ran that at 3 levels of dilation from the three centres for half a day. In spite of the optimisation process taking a lot longer, performance was not good, peaking well below 90% recognition rate. Although the tested dataset is not large enough to draw conclusions from, the recent experiments seem to suggest that not that a multi-scale approach on its own cannot resolve frequent recurrence of misclassifications.

In order to better understand what weakens these measures I have taken a closer look at visual GMDS output. It seems as though the scores are heightened when real (correspondent) pairs of surfaces are not yielding the correct correspondence, even after a 15-level optimisation when the data is exactly the same except the mask size (as shown in the images).

In the past, taking the best fit among all matches was tried (and watched as secondary/surrogate in all of the recent experiments in fact), but it does not perform well as a discriminant on its own. If GMDS succeeds at finding the accurate correspondence 95% of the time in these circumstances, then in this case we need to rerun GMDS several times to exceed it in terms of recognition rates. The other FMM-based method (the one I created) achieved better recognition rates than that.

In order to test the mask type and its effect on performance I ended up setting all parameters to fixed values and running very coarse-scale experiments, first on the entire face and later on a masked subset of limited size, particularly focusing on rigid parts alone.

Results were interesting in the sense that they showed that, based on GMDS as assessment criterion, smaller mask around the fixed points do not clearly and unambiguously produce better results, at least not in the case of this dataset. The assumption we had about removing the non-rigid area may have been misplaced — inherited from other work.

In the next stage I will return to fine levels to get vastly better results.

Ideally, we should initiate these high-resolution triangulations by the result we get from the lower resolution. Currently, by default, there are 9 levels, adjusted according to m, the number of sample size (300 in the latest few experiments). It’s the number of levels in the multi-resolution hierarchy. At the finest level there are typically 15999 faces and 8101 vertices (in older experiments we had just about ~2000 and in recent ones there were ~4000). A low-to-high resolution is operated by default, but it is not sufficient for evading local minima. This should explain the decrease in performance and Initialisation with lower resolution result (iteratively) should solve part of the problems.