Introduction About Site Map

XML
RSS 2 Feed RSS 2 Feed
Navigation

Main Page | Blog Index

Archive for February, 2012

A Diffusion-based Approach for Verification

A 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).

ROC for diffusion

Problems with diffusion

Diffusion match

Best Version of Touch Me In The Morning

ONE of my favourite songs as of late is actually one that I knew well as a kid (but never quite paid attention to its lyrics). The composition of this piece would be hard to reproduce (many vocals and orchestra) and this particular version is a lot better than the many alternative ones.

Diffusion-based Surface Comparison

OVER 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.

GMDS for Surface Comparison: Approaching perfect Tests

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.

Retrieval statistics: 18 queries taking a total of 0.122 seconds • Please report low bandwidth using the feedback form
Original styles created by Ian Main (all acknowledgements) • PHP scripts and styles later modified by Roy Schestowitz • Help yourself to a GPL'd copy
|— Proudly powered by W o r d P r e s s — based on a heavily-hacked version 1.2.1 (Mingus) installation —|