Evaluate Alternative Tessellation Methods of 3D Space
The constrained object models use cubic voxels to tile space, but alternatives may improve spatial precision while enabling computationally efficient search algorithms.
Background
Our constrained object models represent space during learning as tessellated cubes (voxels). The presence of features in each of these voxels then informs the construction of a point cloud that we later use for K-D tree search.
This item is about first determining whether "anisotropy" (see below) in voxels may cause issues for object classification and pose estimation. If so, then addressing this with alternative tesselation methods may already prove useful for how we construct point clouds for each model. More advanced work on this item could then investigate whether voxel-querying methods are a faster alternative to K-D tree search, in which case the same improvements to anisotropy may help further with accuracy.
Motivating Discrete Cells and the Problem of Anisotropy
It may be that querying these voxels directly, for example with a hash table, could represent a more efficient method of search than our current K-D tree method (see this related item for further discussion). While our past investigations have indicated that K-D tree search is quite efficient, this may differ with hardware appropriately matched to a specific algorithm. Moreover, K-D trees have the disadvantage that, during significant updates to the point cloud (i.e. learning), the tree must generally be reconstructed. A long-term aim however is that Monty can continuously learn in an online manner, prompting the desire to avoid such a rebuilding process. Direct voxel-querying or methods such as hash tables may be an approach to avoid this issue, although we would need to quantify construction and update costs to confirm that they represent an improvement.
A problem arises, however, with simply using the existing voxel-based representations. In particular, cubes are a poor way of tessellating 3D space when concerned with cell membership: points that fall just within the corner of a cube are still considered a member of that cube, yet are more distant from the voxel center than points that fall just within the face-center of a cube. This is what is known as anisotropy, or a lack of uniformity in all directions. In Monty, this has the practical risk of biasing which voxel a point belongs to, depending on which direction a sensor is moving. This could impact the precision with which the location and pose of an object is resolved, additionally harming classification accuracy. This issue may become more pronounced as our models become sparser (as voxels may cover a larger proportion of space), yet sparser models are an important long term aim of ours.
More isotropic methods of tessellating (i.e. a non-overlapping, gap-free space filling process) in 3D space include using the rhombic dodecahedron or the truncated octahedron. The images below show the 3D tessellations formed by these solids. An outcome of this work would be to implement a custom learning module that uses such a tessellation instead of cubic voxels, and then leverages these directly at inference (rather than a K-D tree search). We would then want to evaluate the effect, if any, on using one format over the other in terms of classification and pose accuracy. Should these alternative approaches prove promising from an accuracy standpoint, further work could explore various algorithms that search for members in a reference frame by querying membership in a polyhedral cell directly.
A First Investigation
The above work would require a series of changes to both the search algorithm, and model representations. A more immediate item to investigate is whether the existing conversion we perform from a voxel grid to a point cloud could be improved. In particular, the collection of observations within a voxel (including point locations, surface normal directions, sensed colors, etc.) are averaged over to determine the properties of that voxel (and hence the properties of the continuous point cloud member that it becomes). Anisotropy can bias which observations fall within certain voxels, potentially affecting the match between features stored in the learned models, and those queried at inference time when L-2 Euclidean distance is used. Again, this could manifest as reduced pose error and improved classification accuracy, but it remains an open question whether such error is measurable.
Rhombic Dodecahedron
Truncated Octahedron
Image credit: https://www.matematicasvisuales.com
Note that the aim of this work is to improve the computational properties of Monty. An interesting aside however is that a 2D slice through certain tessellations may result in a triangular or hexagonal tiling, similar to 2D grid cells in biology. Together with making hypothesis updates more similar to leaky-integrate and fire neurons, this could represent an intriguing side effect where computational constraints result in Monty's representations being more brain like.
Help Us Make This Page Better
All our docs are open-source. If something is wrong or unclear, submit a PR to fix it!
Updated 4 days ago