Searching point clouds - Hashes vs Trees

About a year ago I was sitting in the lawn outside of the Google buildings in Mountain View, discussing the project I was working on at the time. I had the fun job of displaying very large (60GB +) NetCDF data sets in NASA WorldWind. We were approaching it from the classic game developer perspective and considering building an octree or hyper-octree (this data had temporal slices) index over the dataset to quickly locate subsections we wanted to display at the proper detail. As an aside we began to consider what the limits of the disk to screen transmission are. A 1920x1200 screen with RGB data will have about 6.6 MB of data uncompressed, with compression this will come down a bit. At 60 FPS this requires about 3 Gbit/s disk bandwidth, compare this to what is available via SATA 3. SATA 2 will definitely be too slow adding the times required to search the index, perform seeks and read the pre-computed chunk. It might look better with highly redundant data and good compression.

The idea here comes down to searching using 2 different methods - Hash Search vs Binary Search. Octree based rendering is essentially a binary search in 3 dimensions. The other way to render would be to hash the camera position and orientations or view frustrums, create indexes and blocks of the point cloud being rendered to load chunks as the camera is moved around and data block required is located on the disk using the index + hash. The gamers keep harping on about polygon counts without looking at how the facade of the very large word-count of the internet can be quickly acessed via hashing the query, similarly the first surface of a large object count scene can be quickly accessed via hashing the camera.

All this brings me to the point of the conversation. In the last few days a bit of a drama played out in the hard-core gamer community regarding a leak from Euclideon, who make engines not websites. Hash based searching will work quite well for static data and unlike trees will not require rebalancing for dynamic data. Finding a nice unique hash for frustrums can get quite tricky and storing and compressing the results in a nice data format will also be a challenge. Building a game engine from scratch without all the blocks the graphics world has put in place is a Radical Rewrite. May be it will work, then again we live in a universe where there are 4 dimensions and no one asks how to compute the volume of a hyper-sphere. Knowing e=mc^2 does not let you build an atom bomb or a nuclear reactor, even figure out how to avoid Fukushima. Engineering simply is not the same as Mathematics.

Building faster Bundler with CPU/GPU parallelism

The initial Bundler release caused quite a stir allowing simple bundle adjustment from random collection of photos. It leverages the sparse bundle adjustment - SBA created by Lourakis. However being totally single threaded it does not scale quite well to large images. Sift point finding can be accelerated using SiftGPU - Changchang seem to have moved to greater things at Google since his PhD and academic research days.

I have built bundler for Windows 64 bit + CUDA as the MCBA documentation suggests. A few flags are not supported as shown below.
    CHECK_PARAM_SUPPORT(explicit_camera_centers == false);
    CHECK_PARAM_SUPPORT(optimize_for_fisheye);
    CHECK_PARAM_SUPPORT(use_constraints);
    CHECK_PARAM_SUPPORT(use_point_constraints);
    CHECK_PARAM_SUPPORT(fix_points);


I am calling it PBA_Bundler, please give it a try and let me know if it makes bundle adjustments faster for you. The GPU has higher error rates on floating-point calculations and can lead to large bundles drifting off reality. Even computers can have optical illusions. CPU parallel version has less error rate and yields more stable bundles. I am currently working on adding pthreads based parallelism to match filtering stages of Bundler (computing Epipolar Geometry and establishing bundle bounds) and removing the constraint in multi-core bundler which prevents the use of camera constraints.

Image processing with cat brains - Gabor Filters

When building panoramas or capturing depth using multiview geometry or structure from motion techniques, temporal decorrelation often makes things harder. One of the confusing elements typically is cloud. Hugin had a nice addition during one of the previous GSoC's to identify match points found on clouds - Celeste. So I decided to attach it to the SFM solution while I figured out how the cloudy_photos option in Bundler actually worked.

So this is how I initially came across the fabled Gabor filter. The Hugin cloud detection implementation classifies matchpoints using the local texture estimated with -- a system similar to that in the mammalian visual cortex. Here is a nice OpenCV Gabor filter which can be conveniently glued together in Python to the osm-bundler scripts.  The cat brain research and the biological basis of the Gabor filter is quite interesting :

In 1946, Gabor suggested representing signals over space and time called Information diagrams. He showed that a Gaussian occupies minimal area in such diagrams.  Time and Frequency analysis are the two extremes of such an analysis.  Gabor filters  became popular in vision partly because J.G Daugman (1980, ‘88, ‘90) showed that the receptive fields of most orientation receptive neurons in the (cat’s) brain looked very much like Gabor functions.
As with Gabor filters, the brain often makes use of over complete, non-orthogonal functions.

- Stanforn Robotics.

I tend to get excited whenever a new library sprouts Python bindings. For point cloud processing, a lot of effort is going into the Point Cloud Library (PCL), it is nice to see Python bindings among the projects for GSoC 2012. There is a pass through filter in PCL which can be used perform simple colour-range based filters on the bundle adjustment outputs. The statistical outlier detection can then be used to clean up any straggling garbage points.

New year in life and new job

A new year in life started a couple of days ago. Sharing the birthday with Einstein brings some disadvantages and advantages at the same time. One of the advantages is the constant nagging urge to learn more about the universe and see it the way the my illustrious birthdaymate did. The disadvantage is realising that if I were ever to invent a time machine and move in this extra dimension he conjured up, I will have to keep looking for clues that I have left myself - damn you predestination paradox.

As part of my continuous Brownian motion through life, I started a new job. No organisation (organism) is cool without a scientific name or acronym, the previous one I worked for was a mouthful - CSIRO, the current one is shorter, just AMX (Aerometrex). Doing multiview geometry mapping and point cloud collection. Calibrating lots of cameras in Agisoft, Imageiron, PhotoModeler etc. The approach here is very pragmatic, we will go with whatever is available off the shelf to create the product and my job is to develop an efficient production chain using the right mix of automation and human intervention.

The first order of business was setting up the development environment including - Python 2.7 64bit goodies and implementing Python image calibration (with some changes to account for the new cv2 API which makes numpy arrays and OpenCV images identical). I read through Zhang's core paper on simple flat checkerboard based camera calibration, implemented in OpenCV to estimate 2-3 radial distortion parameters and 2 tangential parameters (Brown's model), as well as the X and Y focal lengths and principal point (which can be different if the lens has astigmatism). Staring at these calibration targets for a while tends to give you optical illusions as the eye and the brain aim to iteratively approach a calibrated view of reality.



OpenCV needs to be told how many corners to expect, so a simple histogram equalisation and mean transition count is required on the checkerboard. Then simply populate the camera ( remember the corner element is 1) and distortions matrix and undistort. Writing calibrations and undistorts with higher order polynomials and even piecewise linear functions will be required for wide angle lenses. Otherwise I am also looking at the 3 rotations degrees of freedom we have in spaceland and their methods of representation via Rotation matrixes, Quaternions and Euler angles. Is there rotational degree of freedom in space-time land ?