Discrete curve symmetry detection
First Claim
1. A medium configured for detecting symmetries of discrete curves, wherein the medium is configured to perform:
- applying a first mapping operator to a first discrete curve, thereby generating a first mapped discrete curve, wherein the mapping operator operates to amplify features of the first discrete curve;
computing a correlation of the first mapped discrete curve with each of a plurality of rotationally shifted versions of a second mapped discrete curve, thereby generating a corresponding plurality of correlation values, wherein each correlation value indicates a respective degree of correlation between the first mapped discrete curve and a respective rotationally shifted version of the second mapped discrete curve;
determining a minimum period of the first and second discrete curves based on the plurality of correlation values;
determining a symmetry group of the first and second discrete curves based on the minimum period; and
outputting the determined symmetry group.
5 Assignments
0 Petitions
Accused Products
Abstract
System and method for detecting symmetries of discrete curves. A mapping operator is applied to a first discrete curve to amplify its features, generating a first mapped discrete curve. A correlation of the first mapped discrete curve with each of a plurality of rotationally shifted versions of a second mapped discrete curve is computed, generating a corresponding plurality of correlation values. A minimum period of the two curves is determined based on the correlation values, and, based on the minimum period, a symmetry group (SG) of the two curves is determined and output. If the two curves are the same curve, the SG is the rotational SG of the discrete curve. If the second curve is a reflection of the first, the SG is the mutual reflection SG of the first. If the first and second curves are different curves, the SG is the mutual SG of the two curves.
-
Citations
64 Claims
-
1. A medium configured for detecting symmetries of discrete curves, wherein the medium is configured to perform:
-
applying a first mapping operator to a first discrete curve, thereby generating a first mapped discrete curve, wherein the mapping operator operates to amplify features of the first discrete curve;
computing a correlation of the first mapped discrete curve with each of a plurality of rotationally shifted versions of a second mapped discrete curve, thereby generating a corresponding plurality of correlation values, wherein each correlation value indicates a respective degree of correlation between the first mapped discrete curve and a respective rotationally shifted version of the second mapped discrete curve;
determining a minimum period of the first and second discrete curves based on the plurality of correlation values;
determining a symmetry group of the first and second discrete curves based on the minimum period; and
outputting the determined symmetry group. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43)
-
-
15. The medium of claim 15, wherein said determining the minimum period based on the power spectrum comprises:
determining a dominant peak in the power spectrum by testing against a specified threshold.
-
44. A method for detecting symmetries of discrete curves, the method comprising:
-
applying a first mapping operator to a first discrete curve, thereby generating a first mapped discrete curve, wherein the mapping operator operates to amplify features of the first discrete curve;
computing a correlation of the first mapped discrete curve with each of a plurality of rotationally shifted versions of a second mapped discrete curve, thereby generating a corresponding plurality of correlation values, wherein each correlation value indicates a respective degree of correlation between the first mapped discrete curve and a respective rotationally shifted version of the second mapped discrete curve;
determining a minimum period of the first and second discrete curves based on the plurality of correlation values;
determining a symmetry group of the first and second discrete curves based on the minimum period; and
outputting the determined symmetry group. - View Dependent Claims (45, 46, 47, 48, 49, 50, 51, 52, 53, 54)
-
-
55. A method for detecting symmetries of discrete curves, the method comprising:
-
applying a first mapping operator to a first discrete curve, thereby generating a first mapped discrete curve, wherein the mapping operator operates to amplify features of the first discrete curve;
computing a correlation of the first mapped discrete curve with each of a plurality of rotationally shifted versions of a second mapped discrete curve, thereby generating a corresponding plurality of correlation values, wherein each correlation value indicates a respective degree of correlation between the first mapped discrete curve and a respective rotationally shifted version of the second mapped discrete curve;
determining a minimum period of the first and second discrete curves based on the plurality of correlation values;
determining a symmetry group of the first and second discrete curves based on the minimum period; and
outputting the determined symmetry group.
-
-
56. A medium configured for detecting rotational symmetries of discrete curves, wherein the medium is configured to perform:
-
applying a mapping operator to a discrete curve, thereby generating a mapped discrete curve, wherein the mapping operator operates to amplify features of the discrete curve;
computing a correlation of the mapped discrete curve with each of a plurality of rotationally shifted versions of the mapped discrete curve, thereby generating a corresponding plurality of correlation values, wherein each correlation value indicates a respective degree of correlation between the mapped discrete curve and a respective rotationally shifted version of the mapped discrete curve;
determining a minimum period of the discrete curve based on the plurality of correlation values; and
determining a symmetry group of the discrete curve based on the minimum period; and
outputting the determined rotational symmetry group.
-
-
57. A medium configured for detecting reflection symmetries of a discrete curve, wherein the medium is configured to perform:
-
applying a mapping operator to a discrete curve, thereby generating a mapped discrete curve, wherein the mapping operator operates to amplify features of the discrete curve;
computing a correlation of the mapped discrete curve with each of a plurality of rotationally shifted versions of a reflected image of the mapped discrete curve, thereby generating a corresponding plurality of correlation values, wherein each correlation value indicates a respective degree of correlation between the mapped discrete curve and a respective rotationally shifted version of the reflected image of the mapped discrete curve;
determining a minimum period of the discrete curve based on the plurality of correlation values; and
determining a reflection symmetry group of the discrete curve based on the minimum period; and
outputting the determined reflection symmetry group.
-
-
58. A medium configured for detecting rotational symmetries of discrete curves, wherein the medium is configured to perform:
-
applying first and second mapping operators respectively to a first and second discrete curve, thereby generating first and second mapped discrete curves, wherein the mapping operators operate to amplify features of the first and second discrete curves;
computing a correlation of the first mapped discrete curve with each of a plurality of rotationally shifted versions of the second mapped discrete curve, thereby generating a corresponding plurality of correlation values, wherein each correlation value indicates a respective degree of correlation between the first mapped discrete curve and a respective rotationally shifted version of the second mapped discrete curve;
determining a minimum period of the first and second discrete curves based on the plurality of correlation values;
determining a mutual rotational symmetry group of the first and second discrete curves based on the minimum period; and
outputting the mutual rotational symmetry group.
-
-
59. A medium configured for detecting reflection symmetries of discrete curves, wherein the medium is configured to perform:
-
applying first and second mapping operators respectively to a first and second discrete curve, thereby generating first and second mapped discrete curves, wherein the mapping operators operate to amplify features of the first and second discrete curves;
generating a third mapped discrete curve by reflecting the second mapped discrete curve about a specified axis of reflection;
computing a correlation of the first mapped discrete curve with each of a plurality of rotationally shifted versions of the third mapped discrete curve, thereby generating a corresponding plurality of correlation values, wherein each correlation value indicates a respective degree of correlation between the first mapped discrete curve and a respective rotationally shifted version of the third mapped discrete curve;
determining a minimum period of the first and second discrete curves based on the plurality of correlation values;
determining a mutual reflection symmetry group of the first and second discrete curves based on the minimum period; and
outputting the mutual reflection symmetry group.
-
-
60. A medium configured for detecting rotational symmetries between discrete curves, wherein the medium is configured to perform:
-
receiving a first discrete curve and a second discrete curve, comprising a first number of points and a second number of points, respectively, wherein the points of the first discrete curve and the second discrete curve are uniformly distributed with a common increment;
if the first number of points and the second number of points are approximately equal, if the first number of points and the second number of points are unequal, uniformly re-sampling the first discrete curve and the second discrete curve such that the number of points in each discrete curve are equal;
computing a plurality of correlation values between the first discrete curve and a plurality of rotationally shifted versions of the second discrete curve, wherein each correlation value indicates a respective degree of correlation between the first discrete curve and a respective rotationally shifted version of the second discrete curve;
determining whether the first discrete curve and the second discrete curve are substantially equivalent based on the plurality of correlation values, and if the first discrete curve and the second discrete curve are substantially equivalent;
determining a mutual rotational symmetry group of the first discrete curve and the second discrete curve based on the plurality of correlation values, wherein the first discrete curve and the second discrete curve are mutually rotationally symmetric under the mutual rotational symmetry group; and
outputting the determined mutual rotational symmetry group.
-
-
61. A medium configured for detecting reflection symmetries between discrete curves, wherein the medium is configured to perform:
-
receiving a first discrete curve and a second discrete curve, comprising a first number of points and a second number of points, respectively, wherein the points of the first discrete curve and the second discrete curve are uniformly distributed with a common increment;
if the first number of points and the second number of points are approximately equal, if the first number of points and the second number of points are unequal, uniformly re-sampling the first discrete curve and the second discrete curve such that the number of points in each discrete curve are equal;
computing a plurality of correlation values between the first discrete curve and a plurality of rotationally shifted versions of a reflected image of the second discrete curve, wherein each correlation value indicates a respective degree of correlation between the first discrete curve and a respective rotationally shifted version of the reflected image of the second discrete curve;
determining whether the first discrete curve and the reflected image of the second discrete curve are substantially equivalent based on the plurality of correlation values, and if the first discrete curve and the reflected image of the second discrete curve are substantially equivalent;
determining a mutual reflection symmetry group of the first discrete curve and the second discrete curve based on the plurality of correlation values, wherein the first discrete curve and the second discrete curve are mutually reflective symmetric under the mutual reflection symmetry group; and
outputting the determined mutual reflection symmetry group.
-
-
62. A medium configured to perform discrete curve matching between a first discrete curve and a second discrete curve using symmetry detection, wherein the medium is configured to perform:
-
determining a mutual rotational symmetry group for the first discrete curve and the second discrete curve;
if the mutual rotational symmetry group is greater than 1, outputting the mutual rotational symmetry group, indicating that the discrete curves are substantially equivalent under rotation;
if the mutual rotational symmetry group is equal to 1, thereby indicating no mutual rotational symmetry between the discrete curves, determining a mutual reflection symmetry group between the first discrete curve and the second discrete curve;
if the mutual reflection symmetry group is greater than 1, thereby indicating that the discrete curves are substantially equivalent under reflection, outputting the mutual reflection symmetry group;
if the mutual rotational symmetry group and the mutual reflection symmetry group are both equal to 1, outputting results indicating that the discrete curves are not substantially equivalent under rotation or reflection. - View Dependent Claims (63, 64)
-
Specification