Efficient implementation of spatial occupancy grid

Discussion in 'C++' started by Marco Körner, Feb 13, 2008.

  1. 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
     
    Marco Körner, Feb 13, 2008
    #1
    1. Advertising

  2. Marco Körner

    Guest

    On Feb 13, 8:38 am, "Marco Körner" <> 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
     
    , Feb 13, 2008
    #2
    1. Advertising

  3. Hi Saul,

    thank you for your reply.

    On 13 Feb., 13:18, wrote:
    > On Feb 13, 8:38 am, "Marco Körner" <> 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.
     
    Marco Körner, Feb 13, 2008
    #3
  4. Marco Körner

    royroy

    Joined:
    May 30, 2008
    Messages:
    1
    grid

    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.
     
    royroy, May 30, 2008
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Shi Mu
    Replies:
    1
    Views:
    641
    Magnus Lycka
    Oct 13, 2005
  2. wallge
    Replies:
    14
    Views:
    731
    wallge
    Jan 30, 2007
  3. paul
    Replies:
    1
    Views:
    342
    Victor Bazarov
    Oct 1, 2005
  4. Xin Zheng
    Replies:
    7
    Views:
    176
    Clifford Heath
    Jan 16, 2008
  5. Jan Martin
    Replies:
    7
    Views:
    325
    Ryan Davis
    Jun 24, 2009
Loading...

Share This Page