Introduction About Site Map

XML
RSS 2 Feed RSS 2 Feed
Navigation

Main Page | Blog Index

Archive for the ‘Science’ Category

“Do You Believe We Came From Monkeys?”

No, I didn’t ask that, but sometimes people ask me that. You too may have come across people who ask that question. Here is my typical, respectable verbal response (I wrote the text below quickly in one pass), which is likely to spread reason into people who are more resistant to it. Being rude is counter-productive.

A hypothetical response would go like this. No, we did not come from monkeys. I don’t believe that and neither should you. You have definitely heard or read a deliberate misrepresentation of what Evolution is. Monkeys and us have common ancestors; in that sense, we have very, very distant cousins. Let us explain how scale reconciles the apparent complexity of this statement. The tree of life connects all forms of life, leading back to life’s origin (and going billions of years back in time). We’ll start at the micro level.

You and your siblings have two common ancestors, assuming a common family structure. You and your cousins share at least a grandparent, i.e. one common ancestor or more. You therefore are likely to have some similarities. Now, imagine going further back 4 generations or about 100 years. A lot of nearby humans share common ancestors with you (from around that time). You might not even know those common ancestors. Now, think of 1,000 years instead of 100 and probably everyone around you has common ancestors with you. Go back 10,000 and the complexity is vast, but almost everyone alive today is somehow connected to you. Going much further back, prior to the origin of what we call “humans” (over 100,000 years ago), one can find common ancestors with other apes, ones we call “monkeys”, which were fit enough to survive in their present form. They are actually very good at what they do, but we cannot grasp this because we are ego-centric in the species sense. We fail to see their unique skills like climbing tress, cooperating, using basic tools and even communicating. Evolution takes us much further back in time (billions of years, not a million or less), tying everything together. DNA evidence helps validate Darwin’s theory as fact, just like the theory of gravity. Believe it or not, all trees are your very, very distant cousins. That’s a beautiful fact, isn’t it?

Testing GMDS With Denser Voronoi Cells

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

Coarse Correspondence in Riemannian Manifolds: Masks and Multi-Resolution Approach

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

Computer Vision Versus Big Brother

Handycam

LIKE nuclear physics, good science can be exploited for bad causes. Getting access to powerful methods need not necessarily mean that this power will be benign. In fact, a lot of funding comes towards science for malicious reasons, such as war. Just look how much money gets funneled by the military industrial complex into aviation and other such research faculties/industries. There is a danger, however, which has a lot to do with how Computer Vision gets tied up with Big Brother connotations, even though Computer Vision gets used a lot to save people’s lives, e.g. in computer-guided surgeries. It would be a travesty if everyone extrapolated ideas to only show the negative uses of these ideas while ignoring the underlying science. Computer graphics is a generative science, whereas Computer Vision is more analytical. Both use models to understand nature, but one synthesises it, whereas the other converts it into information. If we are doing to assume that information collection is always a bad idea, then the World Wide Web too can be considered harmful.

Decimal Timing System

OUR current mechanism for measuring time is a combination of Babylonian and other cycling conventions, making up one of the most messed up timing systems to ever be conceived, with months of nearly arbitrary length (and unknown astronomical meaning) and a base unit ranging from 12 to 60. If our distance and weighting standards were the same, even the imperial system would be an improvement over them. The beautiful thing about decimal systems with base 10 is that once we choose some immutable base unit like the Earth’s diameter we can expand in a way which is easily divisible and makes physics a lot simpler. Currently, in the science of physics, it is common to just measure everything in seconds and then subdivide those by shifting decimal points (millisecond for example). What happened to macro seconds and giga seconds? They do not seem to exist because for large time units we have a sordid mess that extends to our mind (perceptual gap).

Will there ever be a reconstruction of the timing system? It would be nice, but there would be a highly complicated transition phase consisting re-education of the already-adult and thus unwilling-to-relearning, not just revision of many programs and systems. Better to make time more science-compatible than adhere to an arcane system for several generations to come. Complications of the mathematics of time impede progress.

One day in the future civilisation will abandon this current pile of garbage and look back in a way we can’t grasp now how silly an analogue wrist watch looks (especially for the twenty-first century).

GMDS-based Surface Matching After Alignment, Masking

FOLLOWING this previous shoutout I was speaking to a colleague about a more reliable way of comparing two triangulated surfaces as it is required once the masking gets done and good alignment is attained.

I spent some time searching around the Web to see if someone made a robust and accurate way of doing so, rather than rely on ad hoc methods that I wrote on my own. The triangles already are reduced for analogous regions to overlap, but comparing on this basis (in 3-D) needs some cunning theory to be robust to slight changes in expression. MathWorks’ File Exchange hardly provides anything for this purpose. I looked through hundreds of submissions. There is a paper titled “Surface Matching: geodesic distance evolution PDEs on manifolds” and it links to http://www.cs.cmu.edu/~3dvision/meshtoolbox/executables.html. The page is no longer there, but there is a new working URL for it. “Overlap” is the tool closest to what we need (but not quite the best for the job). The comparison we do is not a topological one but one that should be sensitive to small localised anomalies, with just 4,000 (at most, for technical limitation in FMM) triangles. To get to the very high 90s in terms of matching rates (%-wise) I could use some advice/pointers. I have been reading “Geodesic Matching of Triangulated Surfaces”. It is a paper from A. Ben Hamza and Hamid Krim (North Carolina State University) and it demonstrates the use of Jensen-Shannon dissimilarity results. Wang et al. in “3D Brain surface matching based on geodesics and local geometry” seemed interesting and relevant. This paper, however, does not deal with surface-to-surface comparison of brains but with other problems. After a while it was time to explore older methods.

We experimented a lot with GMDS back in July until a few months later. It did not give sufficiently good results for two main reasons: 1) the separability in terms of scores was not good enough and 2) GMDS did not always find the correct correspondences, perhaps due to initialisation issues and other factors. GMDS gave recognition rates higher than 90%, but this baseline was surpassed by the newer implementation. As GMDS is a refinement mechanism, it would be useful to see what would happen if we iterate (i.e. re-run it after some other way of aligning the surfaces). I decided to give that a go.

The results so far look so-and-so, with more false pairs being run to smoothen the curve and draw better conclusions. I am merely presenting the results, irrespective of their quality, just the quality of the experiments used to arrive at them. What’s measured in this case is the best fit stress (best among all iterations), which means that the rest get altogether discarded. ~4000 triangles are used for FMM in this case.

Running further experiments to account for more example pairs has done little to actually contribute to optimism, so I will explore another approach in iterating over the set with GMDS (run overnight).

Taking the average GMDS score rather than the best fit (minimum) score leads to results that are not better. These results are significantly inferior to those attaind through the older FMM-based method.

Important enough to mention was the fact that in the aforementioned experiments — those with GMDS iterations — only the area around the nose was factored in because it surrounds the landmark point which can most accurately be determined. Experiments from last year, however, systematically showed superior performance when an estimation of eye locations form the basis for an expanded mask, so additional experiments will now be run with the expectation that they will show improved recognition performance (hopefully around 95% correct).

Several more experiments have been run to explore the use of GMDS in a supposedly more robust way to establish when an image pair comprises corresponding people. Starting with experiments that look at the use of 3 GMDS processes around 3 different centres, there is a best fit approach, from which the following ROC curve was obtained.

The same for average reveals similar performance.

By taking all centre points at once and performing GMDS on a mask around that we get the third ROC curve.

he same for average shows performance lagging considerably (in comparison with results from another approach).

It is a lot worse than the ~97% recognition rates we got some months ago, Time to step back and rethink perhaps.

Geometry Gurus Needed (First Order Geodesics on Surface Pairs)

I COULD really use the advice of some people who are interested in computer graphics and vision — inverse but complementary fields, which are largely related to geometry and mathematics at large. The challenge is to compare surfaces based on their 3-D characteristics, using Euclidean, geodesic or another non-Euclidean metrics.

Here is what the surfaces look like.

Subject surfaces

The following image represents a performance ROC curve we have.

ROC curve dilation approach

In simple terms, this means that we’re able to classify correctly about 70% of the time. Having summarised a year’s work, culminating in mostly unsuccessful experiments around diffusion (around 97^ recognition rate, the above is poor, So I return to working with geodesic distances as the Swiss army knife for measurement of distances. But the approach being explored at the moment is different and with further enhancement it can hopefully yield performance higher than 97% (matching rate). The sources of limitation are generally well understood in the sense that they can be visualised and overlaid on top of the image pairs. There is no trivial and reliable way to establish multiple landmark points around which to measure distances consistently, so I am trying another way, which at a very coarse level has a matching rate of about 80% (can be significantly improved soon).

The approach attempted at this stage involves triangle comparison post- and pre-marking, but the performance attained so far is not satisfactory.

The limitation is likely inherent in the measuring of distances in FMM and the sub-sampling that results from triangulation (see image for the size of triangles to be fully appreciated).

One particular weakness of the diffusion approach to masking is that it leads to holes in the data, which invalidates some of the measures that were used routinely beforehand. In order to fuse together both geodesic and spectral measures, we now attempt to get a more symbiotic approach that carves out surfaces based on geodesic properties and then uses spectral features on these surfaces. Since ordering does not exist (e.g. point-to-point correspondences), the histogram of images is used to describe the sub-surfaces (carved out around a known correspondence). By increasing the number of rings and bins in the histogram, the performance can be varied somewhat. I was running overnight experiment to test this and got some other appalling ROC curves, such as this:

Curve dilation approach with more rings

The results from the last experiment were disappointing because they did not provide good separability. So the following morning I designed and started running an experiment that explores the potential of measuring diffusion distance between furthest points in the surface carved in accordance with geodesic boundaries (several rings). This too did not give good results. Generally speaking, diffusion distance as a measurement has not proven to be anywhere as useful as FMM so far (since December). It seems to be insensitive to small differences and it does not seem to degrade linearly, either. The next experimental design will explore another new approach, perhaps conceding the potential of diffusion being integrated into the framework’s pipeline.

So the question is this: given two surfaces that are geodetically craves around the surface, what approach would you use to compare them for similarity? We’ve tried a variety of known methods, but none seems to yield very encouraging results thus far. Thanks for any advice or pointers you may have.

Retrieval statistics: 21 queries taking a total of 0.130 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 —|