Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Efficient implementation of spatial occupancy grid

Reply
Thread Tools

Efficient implementation of spatial occupancy grid

 
 
Marco Körner
Guest
Posts: n/a
 
      02-13-2008
Hello,

I'm working on mapping the car's environment by updating an occupancy
grid. An occupancy grid dicretizes the 3D space in small grid elements
(voxels). A grid element contains informations about the space it's
representing.

I need to map a space of the dimensions 50m * 5m * 3m with grid
elements of size 1cm * 1cm * cm (= 750 000 000 grid elements).

My question is how to implement such a data structure in an efficient
way. I need to access fast by indizes. Access by iterators is not
needed. The implentation has to be dynamic because of the iterative
mapping process.

My idea was to store all voxels in a long std::vector<double> and let
pointing a kd-tree's leafs on the vector elements. But this would have
the drawback that the kd-tree has to be reorganized during the update
process to avoid a degeneration to a linear list.

Does anybody has an other idea? Or exemplary code?

Best regards,

Marco Körner
 
Reply With Quote
 
 
 
 
shazled@gmail.com
Guest
Posts: n/a
 
      02-13-2008
On Feb 13, 8:38*am, "Marco Körner" <(E-Mail Removed)> wrote:
> I'm working on mapping the car's environment by updating an occupancy
> grid. An occupancy grid dicretizes the 3D space in small grid elements
> (voxels). A grid element contains informations about the space it's
> representing.
>

I recently did something similar to this in 6D where I used my own
datastructures.

> I need to map a space of the dimensions 50m * 5m * 3m with grid
> elements of size 1cm * 1cm * cm (= 750 000 000 grid elements).
>

Does every element in the grid contain data? In my case they didn't,
and I found a sparse matrix was the best data structure to use.

> My question is how to implement such a data structure in an efficient
> way. I need to access fast by indizes. Access by iterators is not
> needed. The implentation has to be dynamic because of the iterative
> mapping process.
>

I'd consider a 3D matrix or 3D sparse matrix. I've not used them, but
google shows there are some free implementations.

> My idea was to store all voxels in a long std::vector<double> and let
> pointing a kd-tree's leafs on the vector elements. But this would have
> the drawback that the kd-tree has to be reorganized during the update
> process to avoid a degeneration to a linear list.
>

Are there any advantages to using a kd-tree that can't be done by
indexing a 3D matrix (this is a genuine question)?

Saul
 
Reply With Quote
 
 
 
 
Marco Körner
Guest
Posts: n/a
 
      02-13-2008
Hi Saul,

thank you for your reply.

On 13 Feb., 13:18, (E-Mail Removed) wrote:
> On Feb 13, 8:38*am, "Marco Körner" <(E-Mail Removed)> wrote:>
> > I'm working on mapping the car's environment by updating an occupancy
> > grid. An occupancy grid dicretizes the 3D space in small grid elements
> > (voxels). A grid element contains informations about the space it's
> > representing.

>
> I recently did something similar to this in 6D where I used my own
> datastructures.
>
> > I need to map a space of the dimensions 50m * 5m * 3m with grid
> > elements of size 1cm * 1cm * cm (= 750 000 000 grid elements).

>
> Does every element in the grid contain data? In my case they didn't,
> and I found a sparse matrix was the best data structure to use.


Yes, normally it does. I would like to implement a probabilistic
approach, so every grid element is initialized with probability 0.5.

> > My question is how to implement such a data structure in an efficient
> > way. I need to access fast by indizes. Access by iterators is not
> > needed. The implentation has to be dynamic because of the iterative
> > mapping process.

>
> I'd consider a 3D matrix or 3D sparse matrix. I've not used them, but
> google shows there are some free implementations.
>
> > My idea was to store all voxels in a long std::vector<double> and let
> > pointing a kd-tree's leafs on the vector elements. But this would have
> > the drawback that the kd-tree has to be reorganized during the update
> > process to avoid a degeneration to a linear list.

>
> Are there any advantages to using a kd-tree that can't be done by
> indexing a 3D matrix (this is a genuine question)?


I don't know. My idea was to create a grid element if it's not
allready stored in the vector. The kd-tree would be used to find and
access each grid element in logarithmic time O(log N) instead of
search linear through the vector of grid elements in O(N). The
advantage would be, that I just manage cells I've previously touched.
Queries for all other grid elements would return the initial value.


 
Reply With Quote
 
royroy royroy is offline
Junior Member
Join Date: May 2008
Posts: 1
 
      05-30-2008
Hi i think i know what you want to do with this tree but can you please reffer me to some paper of how to get those cells using images?
so obvoiusly u do some estimation over each image but in what way?

thanks in advance,
Ran Z.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
spatial search & search radius circumference with Geokit Xin Zheng Ruby 7 01-16-2008 10:38 PM
video buffering scheme, nonsequential access (no spatial locality) wallge VHDL 14 01-30-2007 04:07 PM
Re: is there any Python code for spatial tessellation? Shi Mu Python 1 10-13-2005 09:06 AM
library for querying virtual polygon over raster spatial data paul C++ 1 10-01-2005 08:44 PM
convert to grey: 4 x the spatial resolution? digiboy@mailinator.com Digital Photography 1 02-19-2005 07:22 PM



Advertisments