Nearest neighbor search using compressed octrees representing high definition maps for autonomous vehicles

Abstract

According to an aspect of an embodiment, operations may comprise receiving a search query for points near a query-point, accessing a compressed octree representation of a point cloud comprising 3D points of a region, and traversing the compressed octree representation to identify regions that overlap a search space by, marking a current node as overlapping the search space responsive to determining that the current node is a leaf node, identifying a child node of the current node and performing a nearest neighbor search in the child node responsive to determining that a region represented by the current node overlaps the search space, and identifying a sibling node of the current node and performing the nearest neighbor search in the sibling node responsive to determining that a region represented by the current node does not overlap the search space.

1 . (canceled) 
     
     
         2 . A method comprising:
 determining a correspondence between a point cloud corresponding to a region and a compressed octree representation corresponding to the region based at least on traversing the compressed octree representation to identify one or more nodes of the compressed octree representation that correspond to an area within the region that also corresponds to one or more points of the point cloud;   determining a location of a machine within the region based at least on the correspondence; and   performing one or more control operations with respect to the machine based at least on the location.   
     
     
         3 . The method of  claim 2 , wherein the traversing of the compressed octree representation is based at least on a search space that corresponds to the area and that is defined based at least on a first point included in the point cloud and a search range around a point location in the region that corresponds to the first point. 
     
     
         4 . The method of  claim 3 , wherein the traversing of the compressed octree representation includes selecting a particular node of the compressed octree representation and performing one or more traversing operations with respect to the particular node based at least on the search space. 
     
     
         5 . The method of  claim 4 , wherein the one or more traversing operations include one or more of:
 marking the particular node as corresponding to the area responsive to the particular node being determined to be a leaf node and responsive to a determination that one or more coordinates associated with the current node correspond to the search space;   responsive to a determination that the particular node is not a leaf node and responsive to the determination that one or more coordinates associated with the particular node correspond to the search space, identifying a child node of the particular node and performing the one or more traversing operations with respect to the identified child node in which the identified child node is selected as the next particular node used in the one or more traversing operations; or.   responsive to determining that no coordinates associated with the particular node correspond to the search space, identifying a sibling node of the particular node and performing the one or more traversing operations with respect to the identified sibling node in which the identified sibling node is selected as the next particular node used in the one or more traversing operations.   
     
     
         6 . The method of  claim 5 , wherein no traversing operations are performed for any child node of the particular node responsive to determining that no coordinates associated with the particular node correspond to the search space. 
     
     
         7 . The method of  claim 5 , wherein the identifying of the sibling node of the particular node is based at least on a sibling link corresponding to the particular node, the sibling link storing an index of the sibling node, the index identifying the sibling node in a linear array. 
     
     
         8 . The method of  claim 2 , wherein the traversing of the compressed octree representation is performed without decompressing the compressed octree representation. 
     
     
         9 . A system comprising:
 one or more processing units to cause performance of operations, the operations comprising:   determining a correspondence with respect to a point cloud and a compressed octree representation based at least on traversing the compressed octree representation to identify one or more nodes of the compressed octree representation that correspond to a same area as one or more points included in the point cloud; and   performing one or more control operations with respect to a machine based at least on the correspondence.   
     
     
         10 . The system of  claim 9 , wherein the performing of the one or more control operations with respect to the machine based at least on the correspondence is based at least on a location of the machine that is determined based at least on the correspondence. 
     
     
         11 . The system of  claim 9 , wherein the traversing of the compressed octree representation is based at least on a search space that corresponds to the area and that is defined based at least on a first point included in the point cloud and a search range around a point location in that corresponds to the first point. 
     
     
         12 . The system of  claim 11 , wherein the traversing of the compressed octree representation includes selecting a particular node of the compressed octree representation and performing one or more traversing operations with respect to the particular node based at least on the search space. 
     
     
         13 . The system of  claim 12 , wherein the one or more traversing operations include one or more of:
 marking the particular node as corresponding to the area responsive to the particular node being determined to be a leaf node and responsive to a determination that one or more coordinates associated with the current node correspond to the search space;   responsive to a determination that the particular node is not a leaf node and responsive to the determination that one or more coordinates associated with the particular node correspond to the search space, identifying a child node of the particular node and performing the one or more traversing operations with respect to the identified child node in which the identified child node is selected as the next particular node used in the one or more traversing operations; or.   responsive to determining that no coordinates associated with the particular node correspond to the search space, identifying a sibling node of the particular node and performing the one or more traversing operations with respect to the identified sibling node in which the identified sibling node is selected as the next particular node used in the one or more traversing operations.   
     
     
         14 . The system of  claim 13 , wherein no traversing operations are performed for any child node of the particular node responsive to determining that no coordinates associated with the particular node correspond to the search space. 
     
     
         15 . The system of  claim 9 , wherein the traversing of the compressed octree representation is performed without decompressing the compressed octree representation. 
     
     
         16 . A processor comprising processing circuitry to cause performance of operations, the operations comprising:
 determining a correspondence with respect to a point cloud corresponding to a region and a compressed octree representation corresponding to the region, the determining of the correspondence including traversing the compressed octree representation to identify one or more nodes of the compressed octree representation that correspond to an area within the region that also corresponds to one or more points included in the point cloud; and   performing one or more control operations with respect to a machine based at least on the correspondence.   
     
     
         17 . The processor of  claim 16 , wherein the traversing of the compressed octree representation is based at least on a search space that corresponds to the area and that is defined based at least on a first point included in the point cloud and a search range around a location in the region that corresponds to the first point. 
     
     
         18 . The processor of  claim 17 , wherein the traversing of the compressed octree representation includes selecting a particular node of the compressed octree representation and performing one or more traversing operations with respect to the particular node based at least on the search space. 
     
     
         19 . The processor of  claim 18 , wherein the one or more traversing operations include one or more of:
 marking the particular node as corresponding to the area responsive to the particular node being determined to be a leaf node and responsive to a determination that one or more coordinates associated with the current node correspond to the search space;   responsive to a determination that the particular node is not a leaf node and responsive to a determination that one or more coordinates associated with the particular node correspond to the search space, identifying a child node of the particular node and performing the one or more traversing operations with respect to the identified child node in which the identified child node is selected as the next particular node used in the one or more traversing operations; or.   responsive to determining that no coordinates associated with the particular node correspond to the search space, identifying a sibling node of the particular node and performing the one or more traversing operations with respect to the identified sibling node in which the identified sibling node is selected as the next particular node used in the one or more traversing operations.   
     
     
         20 . The processor of  claim 19 , wherein no traversing operations are performed for any child node of the particular node responsive to determining that no coordinates associated with the particular node correspond to the search space. 
     
     
         21 . The processor of  claim 16 , wherein the traversing of the compressed octree representation is performed without decompressing the compressed octree representation.