Nearest neighbor search method, apparatus, device, and storage medium

Patent metadata

Field	Value
Publication number	US-12200231-B2
Application number	US-202217851808-A
Country	US
Kind code	B2
Filing date	Jun 28, 2022
Priority date	Jan 6, 2020
Publication date	Jan 14, 2025
Grant date	Jan 14, 2025

Abstract

Described is a nearest neighbor search method. The method is applicable in a device and comprises: acquiring a Morton code set of point cloud data to be searched; stratifying the point cloud data on the basis of the Morton code set and of a first distance threshold to produce current stratum data; shifting to the right by a first preset digit Morton codes of prediction data other than the stratified data in the point cloud data to produce a corresponding first parent node set; determining, on the basis of Morton codes of the current stratum data, a neighbor area satisfying a criterion in the first parent node set; and determining a nearest neighboring point set of the current stratum data in the neighboring area. Also provided in an exemplary embodiment of the present application are a device and a computer storage medium.

First claim

What is claimed is:

1. A method for nearest neighbor search, comprising:
acquiring a Morton code set of point cloud data to be searched;
hierarchizing the point cloud data according to a set and a first distance threshold to obtain data of a current level; wherein the set is obtained by arranging Morton codes of the point cloud data in an ascending order;
performing right shift of a Morton code of data other than hierarchized data in the point cloud data by first preset digits to obtain a corresponding first parent node set;
determining a neighbor region that satisfies a condition in the first parent node set according to the data of the current level, wherein the neighbor region that satisfies the condition is a neighbor region near a current parent node; and
determining a set of nearest neighbor points of the data of the current level in the neighbor region and using the determined set of nearest neighbor points for coding the attribute data of the point cloud.

2. The method according to claim 1 , wherein, hierarchizing the point cloud data to obtain the data of the current level, comprises:
determining a second set at least containing a point corresponding to a Morton code arranged in the first according to the set obtained by arranging Morton codes of the point cloud data in an ascending order;
if a distance between a current point currently being processed in the point cloud data and a point in the second set is less than or equal to the first distance threshold, putting the current point into a first set; wherein, the first set is an empty set;
if a distance between the current point and a point in the second set is greater than the first distance threshold, putting the current point into the second set to obtain an updated second set; and
determining a point in the updated second set of which a distance from the current point is less than or equal to a second distance threshold, to obtain the data of the current level;

wherein the first distance threshold is smaller than the second distance threshold.

3. The method according to claim 2 , wherein, performing right shift of point cloud data other than the hierarchized data in the point cloud data by the first preset digits to obtain the corresponding first parent node set, comprises:
performing right shift of a point in the updated second set by second preset digits to obtain a second parent node set; and
when a level of point cloud data is partitioned from the updated second set, performing right shift of a point in the second parent node set by the first preset digits to obtain the first parent node set.

4. The method according to claim 3 , further comprising:
sampling the Morton code set according to a preset interval to obtain a sample set;
performing right shift of a Morton code of a point in the sample set by the first preset digits to obtain a sampling parent node set; wherein, each sampling parent node corresponds to a right-shifted Morton code;
determining neighbors other than samples in a region corresponding to the sampling parent node set; and
determining that the first preset digits are the same as the second preset digits if an average number of neighbors in the sampling parent node set is greater than a preset average threshold.

5. The method according to claim 2 , wherein, determining the neighbor region that satisfies the condition in the first parent node set according to the data of the current level, comprises:
determining a current parent node to which the current point in the data of the current level belongs in the first parent node set;
determining a neighbor parent node set adjacent to the current parent node;
establishing a look-up table according to the neighbor parent node set and the current parent node;
determining a neighbor parent node according to the look-up table; and
determining a region corresponding to the neighbor parent node as the neighbor region that satisfies the condition.

6. The method according to claim 5 , wherein determining the neighbor parent node according to the look-up table, comprises:
determining the neighbor parent node according to the look-up table and a coordinate value of the current parent node.

7. The method according to claim 5 , wherein, determining the region corresponding to the neighbor parent node as the neighbor region that satisfies the condition, comprises:
determining an arrangement number of the neighbor parent node in the second set;
determining the region corresponding to of the neighbor parent node according to the arrangement number; and
taking at least part of the region occupied by the neighbor parent node as the neighbor region.

8. The method according to claim 5 , wherein establishing the look-up table according to the neighbor parent node set and the current parent node, comprises:
determining a difference between a coordinate value of the neighbor parent node and a coordinate value of the current parent node to obtain a difference set; and
establishing the look-up table according to the difference set and a belonging relationship between the neighbor parent node set and the current parent node; wherein, the belonging relationship is used to indicate that the neighbor parent node set is adjacent to the current parent node.

9. The method according to claim 6 , wherein establishing the look-up table according to the neighbor parent node set and the current parent node, comprises:
according to a belonging relationship and a distance value from a center point of the neighbor parent node set to a center of the current parent node, establishing the look-up table.

10. The method according to claim 6 , wherein establishing the look-up table according to the neighbor parent node set and the current parent node, comprises:
according to a Morton code of the neighbor parent node and a Morton code of the current parent node, determining a Hamming distance between the neighbor parent node and the current parent node and a Morton code difference between the neighbor parent node and the current parent node; and
establishing the look-up table according to the Hamming distance, the Morton code difference and a belonging relationship.

11. The method according to claim 2 , wherein determining the set of nearest neighbor points of the data of the current level in the neighbor region, comprises:
determining a distance between a point in the neighbor region and a point in the data of the current level, to obtain a distance set;
determining a target distance that is less than a third distance threshold from the distance set; and
according to a point corresponding to the target distance, determining a set of nearest neighbor points of the current point.

12. The method according to claim 11 , further comprising:
if the distance set does not contain the target distance that is less than the third distance threshold, determining a point arranged at a preset position from the second set as the set of nearest neighbor points of the current point.

13. The method according to claim 11 , wherein according to the point corresponding to the target distance, determining the set of nearest neighbor points of the current point, comprises:
determining points corresponding to a smallest distance value, which satisfy a preset number, from points corresponding to the target distance to obtain the set of nearest neighbor points of the current point.

14. An apparatus for nearest neighbor search, comprising a processor, wherein the processor is configured to perform the following acts:
acquiring a Morton code set of point cloud data to be searched;
hierarchizing the point cloud data acc

Assignees

• Guangdong Oppo Mobile Telecommunications Corp Ltd

Inventors

• Yang Fuzheng
• Yang Lihui
• Sun Zexing
• Wan Shuai

Classifications

• H04N19/597

  specially adapted for multi-view video sequence encoding · CPC title

• H04N19/167

  Position within a video image, e.g. region of interest [ROI] · CPC title

• H04N19/132

  Sampling, masking or truncation of coding units, e.g. adaptive resampling, frame skipping, frame interpolation or high-frequency transform coefficient masking · CPC title

• H04N19/119

  Adaptive subdivision aspects, e.g. subdivision of a picture into rectangular or non-rectangular coding blocks · CPC title

• G06T9/004

  Predictors, e.g. intraframe, interframe coding · CPC title