[Algorithms] Efficient Voxel Interpolation / Splatting

[Stefan D. <ste...@gm...>]

Dear List,

I'm trying to implement an efficient splatting algorithm. The input of the
system are two-dimensional images which have position and orientation in
space. Using these input images I want to "fill" a three-dimensional voxel
grid which also has position and orientation in space (Represented by a 4x4
transformation matrix: 3x3 rotation matrix and translation vector).

In order to fill the voxel grid using the pixels on the two-dimensional
input images one needs to implement a splatting / interpolation method which
determines the value of a voxel depending on the position, size and color of
the pixels on the input. There are three splatting methods for my data which
seem to make sense to me.

1. Find the nearest pixel to a voxel and assign the color of the pixel to
the voxel (nearest Neighbor)
2. Find the n-nearest pixels to a voxel and weight the color-contribution of
these pixels inverse linearly with the distance of the pixels to the voxel
3. Find the nearest pixels within a pre-defined distance to the voxel and
weight the color-contribution of these pixels inverse linearly with the
distance to the voxel

In ether way one would iterate through all voxels in the output and find
some pixels on the input images near it. This clearly calls for some sort of
efficient bounding hierarchy creation before conducting the neighbor search.
I was thinking that putting the voxels into an octree data structure and
putting the pixels into a quadtree datastructure might do for a good enough
performance.

Another method to speed up the computation further is to reduce the number
of output voxels (given a fixed voxel size) by aligning the voxel grid
efficiently before the search. I basically try to align the voxel grid in a
way that the two dimensional inputs fit into the object-aligned bounding box
with maximum space occupancy on the voxel grid (minimal number of voxels
given a fixed voxel side length).

I thought of a statistical approach here. The problem boils down to placing
and aligning two of the local coordinate axes of the volume along the
directions with the most variance in the dataset (with the dataset being the
positions of the pixels on the input images). This could be done by
calculating the covariance matrix of those positions and performing a
principal component analysis (PCA) on the covariance matrix. This gives the
eigenvalues and eigenvectors along the main variance directions of the input
pixel positions. The two eigenvectors with the largest eigenvalues would
then be good axes for the coordinate system of the voxel grid. The third
axis can then be determined by the "right-hand-rule".

Regards,

Stefan
-- 
--
Stefan Daenzer
Körnerplatz 8
04107 Leipzig


"Work like you don't need the money, love like you've never been hurt and
dance like no one is watching." - Randall G Leighton