Re: [Algorithms] Efficient Voxel Interpolation / Splatting

[Jon O. <jon...@gm...>]

@Manuel: I think he wants to find the nearest point on the image to the
voxel. I'm not sure how a DDA tracing algorithm would help there.

Whats the application?

That all sounds like good ideas. If you want nearest filtering, the first
approach is probably best. I would bet though that you want a smooth output,
like radiating heat.  So option number 3 sounds best for that. Alternatively
to the inverse distance you could do a 3D Gaussian on the data depending on
what kind of output you want.

On Sun, Jun 13, 2010 at 10:38 AM, Stefan Dänzer <ste...@gm...>wrote:

> 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
>
>
> ------------------------------------------------------------------------------
> ThinkGeek and WIRED's GeekDad team up for the Ultimate
> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
> lucky parental unit.  See the prize list and enter to win:
> http://p.sf.net/sfu/thinkgeek-promo
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>