3D SHAPE MATCHING METHOD AND DEVICE BASED ON 3D LOCAL FEATURE DESCRIPTION USING SGHS

Abstract

A 3D shape matching method and a 3D shape matching device based on 3D local feature description using SGHs are provided. In the method, the spherical neighborhood of the feature point is not only divided based on space but also divided based on geometry, the spherical neighborhood of the feature point is not only divided based on the radial direction and the azimuth respectively but also divided based on the elevation, and the spherical neighborhood of the feature point is not only divided based on the deviation angle deviating from the z axis but also divided based on the deviation angle deviating from the x axis. When the deviation angle deviating from the z axis of the spherical neighborhood is divided, the deviation angle is divided more densely where it is closer to the positive direction of the z axis.

Claims

1. A 3D shape matching method based on 3D local feature description using SGHs, comprising: acquiring a 3D point cloud of a real scene; acquiring a feature point p of the 3D point cloud of the real scene; establishing a local reference frame for a spherical neighborhood of the feature point p, wherein an origin of the spherical neighborhood coincides with the feature point p and the spherical neighborhood has a support radius of R, and an origin of the local reference frame coincides with the feature point p and the local reference frame have an orthogonal and normalized x axis, y axis, and z axis; establishing a 3D local feature descriptor based on the local reference frame to encode spatial information within the spherical neighborhood so as to acquire 3D local surface information within the spherical neighborhood; and matching the 3D local surface information within the spherical neighborhood with 3D local surface information of a target object to perform 3D shape matching; wherein the step of establishing the 3D local feature descriptor based on the local reference frame to encode spatial information within the spherical neighborhood comprises: dividing the spherical neighborhood into a plurality of radial partitions along a radial direction with the origin of the spherical neighborhood as a center; dividing the spherical neighborhood into a plurality of azimuth partitions with the z axis as a central axis; dividing a first angle θ.sub.z between a negative direction of the z axis and a positive direction of the z axis into a plurality of first deviation partitions with the origin of the spherical neighborhood as the center, where θ.sub.z=π; acquiring a 3D point set P within the spherical neighborhood, wherein P={p.sub.1,p.sub.2,p.sub.3, . . . , p.sub.n} P={p.sub.i|i=1,2, 3, . . . , n}, p.sub.i(i=1 2 3 . . . n)p.sub.i is a neighborhood point within the spherical neighborhood, and n is the number of neighborhood points within the spherical neighborhood; determining the radial partition where the neighborhood point p.sub.i is located, the azimuth partition where the neighborhood point p.sub.i is located, and the first deviation partition into which a first axial angle α between a normal vector n.sub.i of the neighborhood point p.sub.i and the z axis falls; and generating a corresponding radial distribution histogram, a corresponding azimuth distribution histogram, and a corresponding first deviation distribution histogram respectively for the 3D point set P within the spherical neighborhood to characterize the 3D local surface information within the spherical neighborhood.

2. The 3D shape matching method according to claim 1, wherein the plurality of first deviation partitions of the spherical neighborhood are non-uniformly divided, and the first deviation angle is divided more densely where it is closer to the positive direction of the z axis.

3. The 3D shape matching method according to claim 2, wherein the first angle θ.sub.z is non-uniformly divided through establishing a sine function 2 sin(θ/2) about θ and dividing amplitude of the sine function non-uniformly, where θ∈[0,θ.sub.z].

4. The 3D shape matching method according to claim 1, wherein the method further comprises: dividing an elevation angle of the spherical neighborhood into a plurality of elevation partitions with the origin of the spherical neighborhood as the center; determining the elevation partition where the neighborhood point p.sub.i is located; and generating a corresponding elevation distribution histogram for the 3D point set P within the spherical neighborhood, and characterizing the 3D local surface information within the spherical neighborhood by using the radial distribution histogram, the azimuth distribution histogram, the elevation distribution histogram and the first deviation distribution histogram.

5. The 3D shape matching method according to claim 4, wherein the method further comprises: dividing a second angle θ.sub.x, formed by using the x axis as a starting axis and using the x axis as an ending axis on a x-p-y plane, into a plurality of second deviation partitions, where θ.sub.x=2π; determining the second deviation partition into which a second axial angle β between a projected vector of the normal vector n.sub.i of the neighborhood point p.sub.i on the x-p-y plane and the x axis falls; and generating a corresponding second deviation distribution histogram for the 3D point set P within the spherical neighborhood, and characterizing the 3D local surface information within the spherical neighborhood by using the radial distribution histogram, the azimuth distribution histogram, the elevation distribution histogram, the first deviation distribution histogram and the second deviation distribution histogram.

6. The 3D shape matching method according to claim 5, wherein the steps of generating the corresponding histograms comprise at least one of: respectively assigning weights w.sub.1.sup.R and w.sub.2.sup.R to contribution values that the neighborhood point p.sub.i contributes to two adjacent radial partitions closest to the neighborhood point p.sub.i, accumulating the contribution values that the 3D point set P contributes to each of the radial partitions, and generating the corresponding radial distribution histogram, where w.sub.1.sup.R∈[0,1], w.sub.2.sup.R∈[0,1], w.sub.1.sup.R+w.sub.2.sup.R=1; respectively assigning weights w.sub.1.sup.A and w.sub.2.sup.A to contribution values that the neighborhood point p.sub.i contributes to two adjacent azimuth partitions closest to the neighborhood point p.sub.i, accumulating the contribution values that the 3D point set P contributes to each of the azimuth partitions, and generating the corresponding azimuth distribution histogram, where w.sub.1.sup.A∈[0,1], w.sub.2.sup.A∈[0,1], and w.sub.1.sup.A+w.sub.2.sup.A=1; respectively assigning weights w.sub.1.sup.E and w.sub.2.sup.E to contribution values that the neighborhood point p.sub.i contributes to two elevation partitions closest to the neighborhood point p.sub.i, accumulating the contribution values that the 3D point set P contributes to each of the elevation partitions, and generating the corresponding elevation distribution histogram, where w.sub.1.sup.E∈[0,1] w.sub.2.sup.E∈[0,1], and w.sub.1.sup.E+w.sub.2.sup.E=1; respectively assigning weights w.sub.1.sup.α and w.sub.2.sup.α to contribution values that the neighborhood point p.sub.i contributes to two adjacent first deviation partitions closest to the neighborhood point p.sub.i, accumulating the contribution values that the 3D point set P contributes to each of the first deviation partitions, and generating the corresponding first deviation distribution histogram, where w.sub.1.sup.α∈[0,1] w.sub.2.sup.α∈[0,1], and w.sub.1.sup.α+w.sub.2.sup.α=1; respectively assigning weights w.sub.1.sup.β and w.sub.2.sup.β to contribution values that the neighborhood point p.sub.i contributes to two second deviation partitions closest to the neighborhood point p.sub.i, accumulating the contribution values that the 3D point set P contributes to each of the second deviation partitions, and generating the corresponding second deviation distribution histogram, where w.sub.1.sup.β∈[0,1] w.sub.2.sup.β∈[0,1] and w.sub.1.sup.β+w.sub.2.sup.β=1.

7. The 3D shape matching method according to claim 6, wherein the weights w.sub.1.sup.R and w.sub.2.sup.R are inversely proportional to distances from the neighboring point p.sub.i to the centroids of the two adjacent radial partitions respectively, the weights w.sub.1 and w.sub.2 are inversely proportional to distances from the neighboring point p.sub.i to the centroids of the two adjacent azimuth partitions respectively, the weights w.sub.1.sup.E and w.sub.2.sup.E are inversely proportional to distances from the neighboring point p.sub.i to the centroids of the two adjacent elevation partitions respectively, the weights w.sub.1.sup.α and w.sub.2.sup.α are inversely proportional to distances from the neighboring point p.sub.i to the centroids of the two adjacent first deviation partitions respectively, and the weights w.sub.1.sup.β and w.sub.2.sup.β are inversely proportional to distances from the neighboring point p.sub.i to the centroids of the two adjacent second deviation partitions respectively.

8. A 3D shape matching method based on 3D local feature description using SGHs, comprising: acquiring a 3D point cloud of a target object; acquiring a feature point p of the 3D point cloud of the target object; establishing a local reference frame for a spherical neighborhood of the feature point p, wherein an origin of the spherical neighborhood coincides with the feature point p and the spherical neighborhood has a support radius of R, and an origin of the local reference frame coincides with the feature point p and the local reference frame have an orthogonal and normalized x axis, y axis, and z axis; establishing a 3D local feature descriptor based on the local reference frame to encode spatial information within the spherical neighborhood so as to acquire 3D local surface information within the spherical neighborhood; and matching the 3D local surface information within the spherical neighborhood with 3D local surface information of a scene to perform 3D shape matching; wherein the step of establishing the 3D local feature descriptor based on the local reference frame to encode spatial information within the spherical neighborhood comprises: dividing the spherical neighborhood into a plurality of radial partitions along a radial direction with the origin of the spherical neighborhood as a center; dividing the spherical neighborhood into a plurality of azimuth partitions with the z axis as a central axis; dividing a first angle θ.sub.z between a negative direction of the z axis and a positive direction of the z axis into a plurality of first deviation partitions with the origin of the spherical neighborhood as the center, where θ.sub.z=π; acquiring a 3D point set P within the spherical neighborhood, wherein P={p.sub.1,p.sub.2,p.sub.3, . . . , p.sub.n}P={p.sub.i|i=1,2,3, . . . , n}, p.sub.i(i=1 2 3 . . . n)p.sub.i is a neighborhood point within the spherical neighborhood, and n is the number of neighborhood points within the spherical neighborhood; determining the radial partition where the neighborhood point p.sub.i is located, the azimuth partition where the neighborhood point p.sub.i is located, and the first deviation partition into which a first axial angle α between a normal vector n.sub.i of the neighborhood point p.sub.i and the z axis falls; and generating a corresponding radial distribution histogram, a corresponding azimuth distribution histogram, and a corresponding first deviation distribution histogram respectively for the 3D point set P within the spherical neighborhood to characterize the 3D local surface information within the spherical neighborhood.

9. The 3D shape matching method according to claim 8, wherein the plurality of first deviation partitions of the spherical neighborhood are non-uniformly divided, and the first deviation angle is divided more densely where it is closer to the positive direction of the z axis.

10. The 3D shape matching method according to claim 9, wherein the first angle θ.sub.z is non-uniformly divided through establishing a sine function 2 sin(θ/2) about θ and dividing amplitude of the sine function non-uniformly, where θ∈[0,θ.sub.z].

11. The 3D shape matching method according to claim 8, wherein the method further comprises: dividing an elevation angle of the spherical neighborhood into a plurality of elevation partitions with the origin of the spherical neighborhood as the center; determining the elevation partition where the neighborhood point p.sub.i is located; and generating a corresponding elevation distribution histogram for the 3D point set P within the spherical neighborhood, and characterizing the 3D local surface information within the spherical neighborhood by using the radial distribution histogram, the azimuth distribution histogram, the elevation distribution histogram and the first deviation distribution histogram.

12. The 3D shape matching method according to claim 11, wherein the method further comprises: dividing a second angle θ.sub.x, formed by using the x axis as a starting axis and using the x axis as an ending axis on a x-p-y plane, into a plurality of second deviation partitions, where θ.sub.x=2π; determining the second deviation partition into which a second axial angle β between a projected vector of the normal vector n.sub.i of the neighborhood point p.sub.i on the x-p-y plane and the x axis falls; and generating a corresponding second deviation distribution histogram for the 3D point set P within the spherical neighborhood, and characterizing the 3D local surface information within the spherical neighborhood by using the radial distribution histogram, the azimuth distribution histogram, the elevation distribution histogram, the first deviation distribution histogram and the second deviation distribution histogram.

13. The 3D shape matching method according to claim 12, wherein the steps of generating the corresponding histograms comprise at least one of: respectively assigning weights w.sub.1.sup.R and w.sub.2.sup.R to contribution values that the neighborhood point p.sub.i contributes to two adjacent radial partitions closest to the neighborhood point p.sub.i, accumulating the contribution values that the 3D point set P contributes to each of the radial partitions, and generating the corresponding radial distribution histogram, where w.sub.1.sup.R∈[0,1], w.sub.2.sup.R∈[0,1], w.sub.1.sup.R+w.sub.2.sup.R=1; respectively assigning weights w.sub.1.sup.A and w.sub.2.sup.A to contribution values that the neighborhood point p.sub.i contributes to two adjacent azimuth partitions closest to the neighborhood point p.sub.i, accumulating the contribution values that the 3D point set P contributes to each of the azimuth partitions, and generating the corresponding azimuth distribution histogram, where w.sub.1.sup.A∈[0,1], w.sub.2.sup.A∈[0,1], and w.sub.1.sup.A+w.sub.2.sup.A=1; respectively assigning weights w.sub.1.sup.E and w.sub.2.sup.E to contribution values that the neighborhood point p.sub.i contributes to two elevation partitions closest to the neighborhood point p.sub.i, accumulating the contribution values that the 3D point set P contributes to each of the elevation partitions, and generating the corresponding elevation distribution histogram, where w.sub.1.sup.E∈[0,1] w.sub.2.sup.E∈[0,1], and w.sub.1.sup.E+w.sub.2.sup.E=1; respectively assigning weights w.sub.1.sup.α and w.sub.2.sup.α to contribution values that the neighborhood point p.sub.i contributes to two adjacent first deviation partitions closest to the neighborhood point p.sub.i, accumulating the contribution values that the 3D point set P contributes to each of the first deviation partitions, and generating the corresponding first deviation distribution histogram, where w.sub.1.sup.α∈[0,1] w.sub.2.sup.α∈[0,1], and w.sub.1.sup.α+w.sub.2.sup.α=1; respectively assigning weights w.sub.1.sup.β and w.sub.2.sup.β to contribution values that the neighborhood point p.sub.i contributes to two second deviation partitions closest to the neighborhood point p.sub.i, accumulating the contribution values that the 3D point set P contributes to each of the second deviation partitions, and generating the corresponding second deviation distribution histogram, where w.sub.1.sup.β∈[0,1] w.sub.2.sup.β∈[0,1] and w.sub.1.sup.β+w.sub.2.sup.β=1.

14. The 3D shape matching method according to claim 13, wherein the weights w.sub.1.sup.R and w.sub.2.sup.R are inversely proportional to distances from the neighboring point p.sub.i to the centroids of the two adjacent radial partitions respectively, the weights w.sub.1.sup.A and w.sub.2.sup.A are inversely proportional to distances from the neighboring point p.sub.i to the centroids of the two adjacent azimuth partitions respectively, the weights w.sub.1.sup.E and w.sub.2.sup.E are inversely proportional to distances from the neighboring point p.sub.i to the centroids of the two adjacent elevation partitions respectively, the weights w.sub.1.sup.α and w.sub.2.sup.α are inversely proportional to distances from the neighboring point p.sub.i to the centroids of the two adjacent first deviation partitions respectively, and the weights w.sub.1.sup.β and w.sub.2.sup.β are inversely proportional to distances from the neighboring point p.sub.i to the centroids of the two adjacent second deviation partitions respectively.

15. A 3D shape matching device based on 3D local feature description using SGHs, comprising an acquisition apparatus, a memory and a processor, wherein the acquisition apparatus is configured to acquire a 3D point cloud of a real scene, a computer program is stored in the memory, and the processor, when executing the computer program, implements the steps of: acquiring a feature point p of the 3D point cloud of the real scene; establishing a local reference frame for a spherical neighborhood of the feature point p, wherein an origin of the spherical neighborhood coincides with the feature point p and the spherical neighborhood has a support radius of R, and an origin of the local reference frame coincides with the feature point p and the local reference frame have an orthogonal and normalized x axis, y axis, and z axis; establishing a 3D local feature descriptor based on the local reference frame to encode spatial information within the spherical neighborhood so as to acquire 3D local surface information within the spherical neighborhood; and matching the 3D local surface information within the spherical neighborhood with 3D local surface information of a target object to perform 3D shape matching; wherein the step of establishing the 3D local feature descriptor based on the local reference frame to encode spatial information within the spherical neighborhood comprises: dividing the spherical neighborhood into a plurality of radial partitions along a radial direction with the origin of the spherical neighborhood as a center; dividing the spherical neighborhood into a plurality of azimuth partitions with the z axis as a central axis; dividing a first angle θ.sub.z between a negative direction of the z axis and a positive direction of the z axis into a plurality of first deviation partitions with the origin of the spherical neighborhood as the center, where θ.sub.z=π; acquiring a 3D point set P within the spherical neighborhood, wherein P={p.sub.1,p.sub.2,p.sub.3, . . . , p.sub.n}P={p.sub.i|i=1,2,3, . . . , n}, p.sub.i(i=1 2 3 . . . n)p.sub.i is a neighborhood point within the spherical neighborhood, and n is the number of neighborhood points within the spherical neighborhood; determining the radial partition where the neighborhood point p.sub.i is located, the azimuth partition where the neighborhood point p.sub.i is located, and the first deviation partition into which a first axial angle α between a normal vector n.sub.i of the neighborhood point p.sub.i and the z axis falls; and generating a corresponding radial distribution histogram, a corresponding azimuth distribution histogram, and a corresponding first deviation distribution histogram respectively for the 3D point set P within the spherical neighborhood to characterize the 3D local surface information within the spherical neighborhood.

16. The 3D shape matching device according to claim 15, wherein the plurality of first deviation partitions of the spherical neighborhood are non-uniformly divided, and the first deviation angle is divided more densely where it is closer to the positive direction of the z axis.

17. The 3D shape matching device according to claim 15, wherein the processor, when executing the computer program, further implements the steps of: dividing an elevation angle of the spherical neighborhood into a plurality of elevation partitions with the origin of the spherical neighborhood as the center; determining the elevation partition where the neighborhood point p.sub.i is located; and generating a corresponding elevation distribution histogram for the 3D point set P within the spherical neighborhood, and characterizing the 3D local surface information within the spherical neighborhood by using the radial distribution histogram, the azimuth distribution histogram, the elevation distribution histogram and the first deviation distribution histogram.

18. The 3D shape matching device according to claim 17, wherein the processor, when executing the computer program, further implements the steps of: dividing a second angle θ.sub.x, formed by using the x axis as a starting axis and using the x axis as an ending axis on a x-p-y plane, into a plurality of second deviation partitions, where θ.sub.x=2π; determining the second deviation partition into which a second axial angle β between a projected vector of the normal vector n.sub.i of the neighborhood point p.sub.i on the x-p-y plane and the x axis falls; and generating a corresponding second deviation distribution histogram for the 3D point set P within the spherical neighborhood, and characterizing the 3D local surface information within the spherical neighborhood by using the radial distribution histogram, the azimuth distribution histogram, the elevation distribution histogram, the first deviation distribution histogram and the second deviation distribution histogram.

19. The 3D shape matching device according to claim 18, wherein the steps of generating the corresponding histograms comprise at least one of: respectively assigning weights w.sub.1.sup.R and w.sub.2.sup.R to contribution values that the neighborhood point p.sub.i contributes to two adjacent radial partitions closest to the neighborhood point p.sub.i, accumulating the contribution values that the 3D point set P contributes to each of the radial partitions, and generating the corresponding radial distribution histogram, where w.sub.1.sup.R∈[0,1], w.sub.2.sup.R∈[0,1], w.sub.1.sup.R+w.sub.2.sup.R=1; respectively assigning weights w.sub.1.sup.A and w.sub.2.sup.A to contribution values that the neighborhood point p.sub.i contributes to two adjacent azimuth partitions closest to the neighborhood point p.sub.i, accumulating the contribution values that the 3D point set P contributes to each of the azimuth partitions, and generating the corresponding azimuth distribution histogram, where w.sub.1.sup.A∈[0,1], w.sub.2.sup.A∈[0,1], and w.sub.1.sup.A+w.sub.2.sup.A=1; respectively assigning weights w.sub.1.sup.E and w.sub.2.sup.E to contribution values that the neighborhood point p.sub.i contributes to two elevation partitions closest to the neighborhood point p.sub.i, accumulating the contribution values that the 3D point set P contributes to each of the elevation partitions, and generating the corresponding elevation distribution histogram, where w.sub.1.sup.E∈[0,1] w.sub.2.sup.E∈[0,1], and w.sub.1.sup.E+w.sub.2.sup.E=1; respectively assigning weights w.sub.1.sup.α and w.sub.2.sup.α to contribution values that the neighborhood point p.sub.i contributes to two adjacent first deviation partitions closest to the neighborhood point p.sub.i, accumulating the contribution values that the 3D point set P contributes to each of the first deviation partitions, and generating the corresponding first deviation distribution histogram, where w.sub.1.sup.α∈[0,1] w.sub.2.sup.α∈[0,1], and w.sub.1.sup.α+w.sub.2.sup.α=1; respectively assigning weights w.sub.1.sup.β and w.sub.2.sup.β to contribution values that the neighborhood point p.sub.i contributes to two second deviation partitions closest to the neighborhood point p.sub.i, accumulating the contribution values that the 3D point set P contributes to each of the second deviation partitions, and generating the corresponding second deviation distribution histogram, where w.sub.1.sup.β∈[0,1] w.sub.2.sup.β∈[0,1] and w.sub.1.sup.β+w.sub.2.sup.β=1.

20. The 3D shape matching device according to claim 19, wherein the weights w.sub.1.sup.R and w.sub.2.sup.R are inversely proportional to distances from the neighboring point p.sub.i to the centroids of the two adjacent radial partitions respectively, the weights w.sub.1.sup.A and w.sub.2.sup.A are inversely proportional to distances from the neighboring point p.sub.i to the centroids of the two adjacent azimuth partitions respectively, the weights w.sub.1.sup.E and w.sub.2.sup.E are inversely proportional to distances from the neighboring point p.sub.i to the centroids of the two adjacent elevation partitions respectively, the weights w.sub.1.sup.α and w.sub.2.sup.α are inversely proportional to distances from the neighboring point p.sub.i to the centroids of the two adjacent first deviation partitions respectively, and the weights w.sub.1.sup.β and w.sub.2.sup.β are inversely proportional to distances from the neighboring point p.sub.i to the centroids of the two adjacent second deviation partitions respectively.

Description

DESCRIPTION OF THE DRAWINGS

[0043] FIG. 1 is a schematic flowchart of the 3D shape matching method based on 3D local feature description with SGHs according to an embodiment.

[0044] FIG. 2 is a schematic diagram of establishing a local reference frame for a feature point of the 3D point cloud according to an embodiment.

[0045] FIG. 3 is a schematic diagram of a spherical neighborhood according to an embodiment.

[0046] FIG. 4 is a schematic diagram of dividing the spherical neighborhood according to an embodiment.

[0047] FIG. 5 is a schematic diagram of non-uniform division of the first angle θ.sub.z according to an embodiment.

[0048] FIG. 6 is a schematic diagram of assigning weight values based on contributions of the neighborhood point p.sub.i to two adjacent radial partitions closest to the neighborhood point p.sub.i respectively according to an embodiment.

[0049] FIG. 7 is a schematic diagram of assigning weight values based on contributions of the neighborhood point p.sub.i to two adjacent azimuth partitions closest to the neighborhood point p.sub.i respectively according to an embodiment.

[0050] FIG. 8 is a schematic diagram of assigning weight values based on contributions of the neighborhood point p.sub.i to two adjacent first deviation partitions closest to the neighborhood point p.sub.i respectively according to an embodiment.

[0051] FIG. 9 is a schematic diagram of dividing an elevation angle of the spherical neighborhood into a plurality of elevation partitions according to an embodiment.

[0052] FIG. 10 is a schematic diagram of assigning weight values based on contributions of the neighborhood point p.sub.i to two elevation partitions closest to the neighborhood point p.sub.i respectively according to an embodiment.

[0053] FIG. 11 is a schematic diagram of dividing the x-p-y plane into a plurality of second deviation partitions according to an embodiment.

[0054] FIG. 12 is a schematic diagram of assigning weight values based on contributions of the neighborhood point p.sub.i to two second deviation partitions closest to the neighborhood point p.sub.i respectively according to an embodiment.

[0055] FIG. 13 is a schematic structural diagram of the 3D shape matching device based on 3D local feature description with SGHs according to an embodiment.

DETAILED EMBODIMENTS

[0056] In order to make the objections, technical solutions, and advantages of the present application clearer, the present application is further described below in detail with reference to the accompanying drawings and specific embodiments. It should be understood that the specific embodiments described herein are only used to illustrate the present application, and are not used to limit the present application.

[0057] Unless otherwise defined, all technical terms and scientific terms used in this specification have the same meanings as commonly understood by those skilled in the art of the present application. The terms used in the specification of the present application are only aimed to describe specific embodiments, but not to limit the present application. The term “and/or” used in this specification includes any and all combinations of one or more related listed items.

[0058] In addition, the terms “first”, “second”, etc. are only used for descriptive purposes, and cannot be understood as indicating or implying the number or relative importance of a technical feature. The specific embodiments of the present application are described below, and the technical features involved in the described different embodiments may be combined with each other as long as they do not conflict with each other.

[0059] As is well-known, the 3D point cloud records a surface of a scene or an object in the form of points after scanning the scene or the object, and each of the points is provided with a three-dimensional coordinate. The 3D shape matching is to match a surface of a scene or an object represented by 3D point data with another or more surfaces of scenes or objects represented by 3D point data, so as to further achieve a result of 3D object recognition.

[0060] According to the first aspect of the present application, in an embodiment as shown in FIG. 1, the present application proposes a 3D shape matching method based on 3D local feature description using SGHs, and the method may include:

[0061] acquiring a 3D point cloud of a real scene;

[0062] acquiring a feature point p of the 3D point cloud of the real scene;

[0063] establishing a local reference frame for a spherical neighborhood of the feature point p, here an origin of the spherical neighborhood coincides with the feature point p and the spherical neighborhood has a support radius of R, and an origin of the local reference frame coincides with the feature point p and the local reference frame have an orthogonal and normalized x axis, y axis, and z axis;

[0064] establishing a 3D local feature descriptor based on the local reference frame to encode spatial information within the spherical neighborhood so as to acquire 3D local surface information within the spherical neighborhood; and matching the 3D local surface information within the spherical neighborhood with 3D local surface information of a target object to perform 3D shape matching.

[0065] In this embodiment, the real scene may be any scene in real life, especially in industrial applications. The present application does not make specific restrictions on the application scene, as long as it is a scene that requires the 3D shape matching or 3D recognition method. In this embodiment, the 3D point cloud may be acquired in real time, and the 3D point cloud of the target object may be pre-stored, i.e., the target object may be a model used to match the same object in the real scene. That is to say, in this embodiment, the 3D local surface information of the 3D point cloud acquired by measuring the real scene in real time can be matched with the 3D local surface information acquired by calculating the 3D point cloud of the pre-stored target object, so as to achieve recognition of a shape matching the model of the target object from the 3D point cloud of the real scene.

[0066] In this embodiment, the feature points are also referred to as key points or points of interest, that is, the feature points are provided with a specific shape. The feature points of the 3D point cloud may be acquired by a method based on a fixed-scale or a method based on an adaptive-scale, alternatively the feature points may also be acquired by any other existing technology, which is not limited herein.

[0067] In an embodiment, as shown in FIGS. 2 and 3, any local reference frame construction method well known to those skilled in the art may be used to construct the local reference frame for the feature points of the 3D point cloud in the present application.

[0068] In an embodiment, as shown in FIG. 4, the step of establishing a 3D local feature descriptor based on the local reference frame to encode spatial information within the spherical neighborhood may include:

[0069] dividing the spherical neighborhood into a plurality of radial partitions along a radial direction with the origin of the spherical neighborhood as a center, as shown in FIG. 4A;

[0070] dividing the spherical neighborhood into a plurality of azimuth partitions with the z axis as a central axis, as shown in FIG. 4B;

[0071] dividing a first deviation angle θ.sub.z between a negative direction of the z axis and a positive direction of the z axis into a plurality of first deviation partitions with the origin of the spherical neighborhood as the center, as shown in FIG. 4C, where θ.sub.z=π;

[0072] acquiring a 3D point set P within the spherical neighborhood, where P={p.sub.i|I=1, 2, 3, . . . , n}, p.sub.i is a neighborhood point within the spherical neighborhood, and n is the number of neighborhood points within the spherical neighborhood;

[0073] determining the radial partition where the neighborhood point p.sub.i is located, the azimuth partition where the neighborhood point p.sub.i is located, and the first deviation partition into which a first axial angle α between a normal vector n.sub.i of the neighborhood point p.sub.i and the z axis falls; and

[0074] generating a corresponding radial distribution histogram, a corresponding azimuth distribution histogram, and a corresponding first deviation distribution histogram respectively for the 3D point set P within the spherical neighborhood to characterize 3D local surface information within the spherical neighborhood.

[0075] In this embodiment, the generation of the feature distribution histograms, namely, is to take the partitions as the abscissa and determine the number of neighborhood points included in each of the partitions so as to generate the corresponding statistical histograms, and the data represented by the statistical histograms is used to perform shape matching for the 3D local surface, such that the data and time required for matching can be greatly reduced, thereby simplifying the matching process.

[0076] In an embodiment, preferably, the spherical neighborhood may have 4 radial partitions.

[0077] In an embodiment, preferably, the spherical neighborhood may have 8 azimuth partitions.

[0078] In an embodiment, preferably, the spherical neighborhood may have 4 first deviation partitions.

[0079] In an embodiment, the plurality of radial partitions of the spherical neighborhood may be uniformly divided.

[0080] In an embodiment, the plurality of radial partitions of the spherical neighborhood may also be non-uniformly divided, which is related to the scene to be measured.

[0081] In an embodiment, the plurality of azimuth partitions of the spherical neighborhood may be uniformly divided.

[0082] In an embodiment, the plurality of azimuth partitions of the spherical neighborhood may also be non-uniformly divided, which is related to the scene to be measured.

[0083] In an embodiment, since the depths of the same object in the scene may not change drastically, then the normal vectors of the neighborhood points within the spherical neighborhood may not deviate greatly away from the z axis. Therefore, the plurality of first deviation partitions may be non-uniformly divided, and the first deviation angle is divided more densely where it is closer to the positive direction of the z axis.

[0084] In this embodiment, preferably, since the first deviation angle is required to be divided more densely where it is closer to the positive direction of the z axis, a sine function about θ may be established, and the amplitude of the sine function may be uniformly divided to realize the non-uniform division of the first angle θ.sub.z, where θ∈[0, θ.sub.z].

[0085] In this embodiment as shown in FIG. 5, preferably, the sine function may be determined as

[00001]$2\sin \left(\frac{\theta }{2}\right),$

0∈[0,θ.sub.z].

[0086] In an embodiment, the step of generating the corresponding radial distribution histogram for the 3D point set P within the spherical neighborhood may include:

[0087] respectively assigning weights w.sub.1.sup.R and w.sub.2.sup.R to contribution values that the neighborhood point p.sub.i contributes to two adjacent radial partitions closest to the neighborhood point p.sub.i as shown in FIG. 6, where w.sub.1.sup.R∈[0,1], w.sub.2.sup.R∈[0,1], w.sub.1.sup.R+w.sub.2.sup.R=1; and

[0088] accumulating the contribution values that the 3D point set P contributes to each of the radial partitions, and generating the corresponding radial distribution histogram.

[0089] In this embodiment, the “two adjacent radial partitions closest to the neighboring point p.sub.i” refer to two adjacent radial partitions whose centroids are closest to the neighboring point p.sub.i among all radial partitions.

[0090] In this embodiment, preferably, the weights w.sub.1.sup.R and w.sub.2.sup.R are inversely proportional to distances from the neighboring point p.sub.i to the centroids of the two closest adjacent radial partitions respectively, that is, in the two closest adjacent radial partitions, the contribution value that the neighboring point p.sub.i contributes to this radial partition is smaller if the centroid of the radial partition is farther away from the neighboring point p.sub.i. For example, if the neighborhood point p.sub.i is located at the centroid of one of the radial partitions, then the weight w.sub.1.sup.R assigned to the contribution of the neighborhood point p.sub.i to this radial partition is equal to 1, and the weight w.sub.2.sup.R assigned to the contribution of the neighborhood point p.sub.i to another radial partition is equal to 0, correspondingly the contribution value that the neighboring point p.sub.i contributes to this radial partition is equal to 1 and the contribution value that the neighboring point p.sub.i contributes to another radial partition is equal to 0 if a cardinality of the contribution value is equal to 1. For example, if the neighborhood point p.sub.i is a little closer to the centroid of one of the two radial partitions and a little farther away from the centroid of another radial partition, then the weight w.sub.1.sup.R of the contribution of the neighborhood point p.sub.i to the one radial partition may range from 0 to 1 and be greater than w.sub.2.sup.R, and correspondingly the contribution value that the neighboring point p.sub.i contributes to the one radial partition will be greater than the contribution value that the neighboring point p.sub.i contributes to another radial partition. For example again, if the neighborhood point p.sub.i is located at an edge of the two closest adjacent radial partitions, i.e., the distances from the neighborhood point p.sub.i to the centroids of the two closest adjacent radial partitions are the same, then each of the weights w.sub.1.sup.R and w.sub.2.sup.R of the contribution of the neighborhood point p.sub.i to the two radial partitions may be equal to 0.5, and correspondingly the contribution values that the neighborhood point p.sub.i contributes to the two radial partitions are also the same, for example, each of the contribution values may be equal to 0.5. Of course, the cardinality of the contribution value may be set arbitrarily according to an actual situation. For example, in order to better distinguish the effect, the cardinality may be set to be greater than 1. In this way, the description for the neighborhood points located at and near the edges of the radial partitions can be effectively improved.

[0091] In an embodiment, the step of generating the corresponding azimuth distribution histogram for the 3D point set P within the spherical neighborhood may include:

[0092] respectively assigning weights w.sub.1.sup.A and w.sub.2.sup.A to contribution values that the neighborhood point p.sub.i contributes to two adjacent azimuth partitions closest to the neighborhood point p.sub.i as shown in FIG. 7, where w.sub.1.sup.A∈[0,1], w.sub.2.sup.A∈[0,1], and w.sub.1.sup.A+w.sub.2.sup.A=1; and

[0093] accumulating the contribution values that the 3D point set P contributes to each of the azimuth partitions, and generating the corresponding azimuth distribution histogram.

[0094] In this embodiment, the “two adjacent azimuth partitions closest to the neighboring point p.sub.i” refer to two adjacent azimuth partitions whose centroids are closest to the neighboring point p.sub.i among all azimuth partitions.

[0095] In this embodiment, preferably, the weights w.sub.1.sup.A and w.sub.2.sup.A are inversely proportional to distances from the neighboring point p.sub.i to the centroids of the two adjacent azimuth partitions respectively, that is, in the two closest adjacent azimuth partitions, the contribution value that the neighboring point p.sub.i contributes to this azimuth partition is smaller if the centroid of the azimuth partition is farther away from the neighboring point p.sub.i. The weights of the azimuth partitions may be set with reference to the foregoing embodiment in which the weights of the radial partitions are set. In this way, the description for the neighboring points located at and near the edges of the azimuth partitions can be effectively improved.

[0096] In an embodiment, the step of generating the corresponding first deviation distribution histogram for the 3D point set P within the spherical neighborhood may include:

[0097] respectively assigning weights w.sub.1.sup.α and w.sub.2.sup.α to contribution values that the neighborhood point p.sub.i contributes to two adjacent first deviation partitions closest to the neighborhood point p.sub.i as shown in FIG. 8, where w.sub.1.sup.α∈[0,1] w.sub.2.sup.α∈[0,1], and w.sub.1.sup.α+w.sub.2.sup.α=1; and

[0098] accumulating the contribution values that the 3D point set P contributes to each of the first deviation partitions, and generating the corresponding first deviation distribution histogram.

[0099] In this embodiment, the “two adjacent first deviation partitions closest to the neighboring point p.sub.i” refer to two adjacent first deviation partitions whose centroids are closest to the neighboring point p.sub.i among all first deviation partitions.

[0100] In this embodiment, preferably, the weights w.sub.1.sup.α and w.sub.2.sup.α are inversely proportional to distances from the neighboring point p.sub.i to the centroids of the two adjacent first deviation partitions respectively, that is, in the two closest adjacent first deviation partitions, the contribution value that the neighboring point p.sub.i contributes to this first deviation partition is smaller if the centroid of the first deviation partition is farther away from the neighboring point p.sub.i. The weights of the first deviation partitions may be set with reference to the foregoing embodiment in which the weights of the radial partitions are set. In this way, the description for the neighboring points located at and near the edges of the first deviation partitions can be effectively improved.

[0101] In an embodiment, the method includes the basic technical features of the above embodiments, and the method, on the basis of the above embodiments, may further include:

[0102] dividing an elevation angle of the spherical neighborhood into a plurality of elevation partitions with the origin of the spherical neighborhood as the center (for example, the y-p-z plane is taken as an example) as shown in FIG. 9;

[0103] determining the elevation partition where the neighborhood point p.sub.i is located; and generating a corresponding elevation distribution histogram for the 3D point set P within the spherical neighborhood, and characterizing the 3D local surface information within the spherical neighborhood by using the radial distribution histogram, the azimuth distribution histogram, the elevation distribution histogram and the first deviation distribution histogram.

[0104] In an embodiment, preferably, the spherical neighborhood may have 4 elevation partitions.

[0105] In an embodiment, the step of generating the corresponding elevation distribution histogram for the 3D point set P within the spherical neighborhood may include:

[0106] respectively assigning weights w.sub.1.sup.E and w.sub.2.sup.E to contribution values that the neighborhood point p.sub.i contributes to two elevation partitions closest to the neighborhood point p.sub.i as shown in FIG. 10, where w.sub.1.sup.E∈[0,1] w.sub.2.sup.E∈[0,1], and w.sub.1.sup.E+w.sub.2.sup.E=1; and accumulating the contribution values that the 3D point set P contributes to each of the elevation partitions, and generating the corresponding elevation distribution histogram.

[0107] In this embodiment, the “two adjacent elevation partitions closest to the neighboring point p.sub.i” refer to two adjacent elevation partitions whose centroids are closest to the neighboring point p.sub.i among all elevation partitions.

[0108] In this embodiment, preferably, the weights w.sub.1.sup.E and w.sub.2.sup.E are inversely proportional to distances from the neighboring point p.sub.i to the centroids of the two adjacent elevation partitions respectively, that is, in the two closest adjacent elevation partitions, the contribution value that the neighboring point p.sub.i contributes to this elevation partition is smaller if the centroid of the elevation partition is farther away from the neighboring point p.sub.i. The weights of the elevation partitions may be set with reference to the foregoing embodiment in which the weights of the radial partitions are set. In this way, the description for the neighboring points located at and near the edges of the elevation partitions can be effectively improved.

[0109] In an embodiment, the method includes the basic technical features of the above embodiment, and the method, on the basis of the above embodiment, may further include:

[0110] dividing a second angle θ.sub.x, formed by using the x axis as a starting axis and using the x axis as an ending axis on the x-p-y plane, into a plurality of second deviation partitions as shown in FIG. 11, where θx=2π;

[0111] determining the second deviation partition into which a second axial angle β between a projected vector of the normal vector n.sub.i of the neighborhood point p.sub.i on the x-p-y plane and the x axis falls; and

[0112] generating a corresponding second deviation distribution histogram for the 3D point set P within the spherical neighborhood, and characterizing the 3D local surface information within the spherical neighborhood by using the radial distribution histogram, the azimuth distribution histogram, the elevation distribution histogram, and the first deviation distribution histogram and the second deviation distribution histogram.

[0113] In an embodiment, preferably, the spherical neighborhood has 4 second deviation partitions.

[0114] In an embodiment, the step of generating the corresponding second deviation distribution histogram for the 3D point set P within the spherical neighborhood may include:

[0115] respectively assigning weights w.sub.1.sup.β and w.sub.2.sup.β to contribution values that the neighborhood point p.sub.i contributes to two second deviation partitions closest to the neighborhood point p.sub.i as shown in FIG. 12, where w.sub.1.sup.β∈[0,1] w.sub.2.sup.β∈[0,1] and w.sub.1.sup.β+w.sub.2.sup.β=1; and

[0116] accumulating the contribution values that the 3D point set P contributes to each of the second deviation partitions, and generating the corresponding second deviation distribution histogram.

[0117] In this embodiment, the “two adjacent second deviation partitions closest to the neighboring point p.sub.i” refer to two adjacent second deviation partitions whose centroids are closest to the neighboring point p.sub.i among all second deviation partitions.

[0118] In this embodiment, preferably, the weights w.sub.1.sup.β and w.sub.2.sup.β are inversely proportional to distances from the neighboring point p.sub.i to the centroids of the two adjacent second deviation partitions respectively, that is, in the closest two adjacent second deviation partitions, the contribution value that the neighboring point p.sub.i contributes to this second deviation partition is smaller if the centroid of the second deviation partition is farther away from the neighboring point p.sub.i. The weights of the second deviation partitions may be set with reference to the foregoing embodiment in which the weights of the radial partitions are set. In this way, the description for the neighboring points located at and near the edges of the second deviation partitions can be effectively improved.

[0119] The second aspect of the present application proposes a 3D shape matching method based on 3D local feature description using SGHs. The steps of the embodiments of the second aspect of the present application is similar to the steps of the above described embodiments of the first aspect, and their difference lies in that the 3D point cloud of the target object may be pre-stored and the 3D point cloud of the scene may also be pre-stored after being acquired. That is to say, in this method, the 3D local surface information acquired by calculating the 3D point cloud of the pre-stored target object may be matched with the 3D local surface information acquired by calculating the 3D point cloud of the scene, so as to realize recognition of a shape matching the model of the target object from the 3D point cloud of the scene. For other technical features of the second aspect of the present application, reference may be made to the technical features in the specific embodiments of the first aspect of the present application, which will not be repeated herein again.

[0120] According to the third aspect of the present application, in an embodiment as shown in FIG. 13, a 3D shape matching device based on 3D local feature description using SGHs is proposed, which may include an acquisition apparatus, a memory and a processor. Among them, the acquisition apparatus is configured to acquire a 3D point cloud of a real scene, a computer program is stored in the memory, and the processor, when executing the computer program, implements the operations of the embodiments of the method described in the first aspect of the present application except for acquiring the 3D point cloud of the real scene. In this embodiment, the acquisition apparatus may be a 3D scanning apparatus, a laser scanning apparatus, an acquisition apparatus using structured light, or any other apparatus that can acquire the 3D point cloud of the real scene, and the memory may be any storage apparatus with a software storage function, and the processor may be any processor that may execute the computer program and instruct a certain execution subject to perform related operations. In an embodiment, the 3D point cloud data acquired by the acquisition apparatus may be directly or indirectly stored in the memory, or may be accessed by the memory or the processor. In an embodiment, the processor may directly or indirectly control the acquisition apparatus to acquire the 3D point cloud data. For other technical features of the third aspect of the present application, reference may be made to the technical features in the specific embodiments of the first aspect of the present application, which will not be repeated herein again.

[0121] According to the fourth aspect of the present application, an embodiment proposes a 3D shape matching device based on 3D local feature description using SGHs, which includes a memory and a processor. Among them, a computer program is stored in the memory, and the processor, when executing the computer program, implements the embodiments of the methods described in the first aspect or the second aspect of the present application. For other technical features of the fourth aspect of the present application, reference may be made to the technical features in the specific embodiments of the first, second or third aspect of the present application, which will not be repeated herein again.

[0122] The specific embodiments of the present application described above do not constitute a limitation on the protection scope of the present application. Any amendment, equivalent replacement and improvement made within the principles of the present application shall be included in the protection scope of the present application.