INCREMENTAL SUCCESSIVE ORTHOGONAL IMAGES (ISOI)

The Library for Uniform Deterministic Sequences and Sets of Samples over 2-sphere and SO(3)



Publications
  • Generating Uniform Incremental Grids on SO(3) Using the Hopf Fibration (pdf)
    Anna Yershova, Swati Jain, Steven M. LaValle, and Julie C. Mitchell,
    International Journal of Robotics Research, IJRR 2009

  • Generating Uniform Incremental Grids on SO(3) Using the Hopf Fibration (pdf, ppt)
    Anna Yershova, Steven M. LaValle, and Julie C. Mitchell,
    In Proc. Eighth International Workshop on the Algorithmic Foundations of Robotics (WAFR 2008)


  • Software Below are the implementations of the sequences over the 2-sphere and 3-dimensional rotation group, SO(3), presented in our publications. The code is written using C++. The README file contains the instructions on how to download and run the code.

    S2_sequence.tar.gz This code provides a uniform deterministic sequence of samples over the 2-sphere. It generates an ordered sequence of points from the multiresolution grid structure provided by HEALPix. The output is parametrized by (x,y,z) coordinates in 3D.

    SO3_grid.tar.gz This code provides a uniform multiresolution grids over SO(3). The method uses Hopf coordinates to generate grid cells. The base-resolution grid consists of 72 points. The output is parametrized using unit quaternions, represented by (x,y,z,w) in 4D.

    SO3_sequence.tar.gz This code provides a uniform deterministic sequence over SO(3). The base-resolution grid consists of 72 points. The method uses Hopf coordinates to generate grid cells. The output is parametrized using unit quaternions, represented by (x,y,z,w) in 4D.

    The advantages of the deterministic sequences provided by this software are: uniformity (good covering of the 2-sphere and SO(3) is obtained, this can be formulated in terms of spherical dispersion and discrepancy), incremental quality (samples are added one by one maintaining the uniformity of the resulting distribution), explicit neighborhood structure (the samples are organized in a grid fashion, allowing efficient nearest neighbor calculations). It is important to note that the resulting sequence is infinite, that is, infinitely many samples can be generated retaining all of the above properties. Deterministic sequences were tested in sampling-based motion planning algorithms and compared to the performance of random sequences. While the performance efficiency is usually comparable, deterministic sequences provide important resolution completeness guarantees to motion planning methods.

    Last updated 18/07/2022