Mutual Symmetry Detection

• US 20070297681A1
• Filed: 09/06/2007
• Published: 12/27/2007
• Est. Priority Date: 06/05/2003
• Status: Active Grant

• Current Assignee: National Instruments Corporation (Emerson Electric Company)
• Original Assignee: National Instruments Corporation (Emerson Electric Company)
• Inventors: Wenzel, Lothar
• Granted Patent: US 7,936,928 B2
• Time in Patent Office: Days
• US Class Current: 382/209
• CPC Class Codes: G06V 10/42 Global feature extraction by analysis of the whole pattern, e.g. using frequency domain transformations or autocorrelation
• CPC Class Codes: G06V 10/443 by matching or filtering
• CPC Class Codes: G06V 10/46 Descriptors for shape, contour or point-related descriptors, e.g. scale invariant feature transform [SIFT] or bags of words [BoW]; Salient regional features colour feature extraction G06V10/56

Abstract

System and method for detecting symmetries of configurations of discrete curves. Configuration characterization information for a configuration of a plurality of discrete curves is received, where the configuration characterization information comprises rotational symmetry groups for each of the plurality of discrete curves. A greatest common divisor of the rotational symmetry groups of the discrete curves is determined, where the greatest common divisor is a maximum possible object-based mutual rotational symmetry group for the configuration. The determined value is stored, and is usable to perform pattern matching between configurations. This value may be compared to that of a target configuration to determine if the two configurations can match. Additional symmetry-based matching techniques are used to perform staged pattern matching between the two configurations, where the process may terminate as soon as one of the techniques determines that the configurations cannot match, or a matching algorithm determines that they match.

Claims

1. A computer-accessible memory medium that stores program instructions for detecting symmetries of configurations of discrete curves, wherein the program instructions are executable by a processor to perform:

receiving configuration characterization information for a configuration of discrete curves, wherein the configuration comprises a plurality of discrete curves, and wherein the configuration characterization information comprises rotational symmetry groups for each of the plurality of discrete curves;

determining a greatest common divisor of the rotational symmetry groups of the discrete curves, wherein the greatest common divisor is a maximum possible object-based mutual rotational symmetry group for the configuration; and

storing the maximum possible object-based mutual rotational symmetry group, wherein the maximum possible object-based mutual rotational symmetry group is usable to perform pattern matching between configurations.

2. The memory medium of claim 1, wherein the program instructions are further executable to perform:

receiving target configuration characterization information for a target configuration of discrete curves, comprising a maximum possible object-based mutual rotational symmetry group for the target configuration;

comparing the maximum possible object-based mutual rotational symmetry group with the maximum possible object-based mutual rotational symmetry group for the target configuration;

determining that the maximum possible object-based mutual rotational symmetry group fails to match the maximum possible object-based mutual rotational symmetry group for the target configuration; and

indicating that the configuration does not match the target configuration.

3. The memory medium of claim 1, wherein the program instructions are further executable to perform:

receiving target configuration characterization information for a target configuration of discrete curves, comprising a maximum possible object-based mutual rotational symmetry group for the target configuration;

comparing the maximum possible object-based mutual rotational symmetry group with the maximum possible object-based mutual rotational symmetry group for the target configuration;

determining that the maximum possible object-based mutual rotational symmetry group matches the maximum possible object-based mutual rotational symmetry group for the target configuration; and

indicating that the configuration may match the target configuration.

4. The memory medium of claim 3, wherein the program instructions are further executable to perform:

in response to said determining that the maximum possible object-based mutual rotational symmetry group matches the maximum possible object-based mutual rotational symmetry group for the target configuration;

determining the center of mass for each of the discrete curves in the configuration;

determine the mean of the respective centers of mass for the discrete curves in the configuration;

normalize the respective centers of mass for the discrete curves with respect to the mean, wherein the normalized centers of mass for the discrete curves compose a constellation, wherein the determined mean comprises a center of the constellation;

determining all maximum rotational sub-groups of the constellation;

determining a greatest common divisor of the maximum rotational sub-groups, comprising a constellation rotational symmetry group for the configuration;

storing the constellation rotational symmetry group, wherein the constellation rotational symmetry group is usable to perform pattern matching between configurations.

5. The memory medium of claim 4, wherein the target configuration characterization information comprises a constellation rotational symmetry group for the target configuration, and wherein the program instructions are further executable to perform:

comparing the constellation rotational symmetry group with the constellation rotational symmetry group for the target configuration;

determining that the constellation rotational symmetry group fails to match the constellation rotational symmetry group for the target configuration; and

indicating that the configuration does not match the target configuration.

6. The memory medium of claim 4, wherein the target configuration characterization information comprises a constellation rotational symmetry group for the target configuration, and wherein the program instructions are further executable to perform:

comparing the constellation rotational symmetry group with the constellation rotational symmetry group for the target configuration;

determining that the constellation rotational symmetry group matches the constellation rotational symmetry group for the target configuration; and

indicating that the configuration may match the target configuration.

7. The memory medium of claim 6, wherein the program instructions are further executable to perform:

in response to said determining that the constellation rotational symmetry group matches the constellation rotational symmetry group for the target configuration;

determining a greatest common divisor between the maximum possible object-based mutual rotational symmetry group and the constellation rotational symmetry group, comprising a maximum possible mutual rotational symmetry group for the configuration; and

storing the maximum possible mutual rotational symmetry group, wherein the maximum possible mutual rotational symmetry group is usable to perform pattern matching between configurations.

8. The memory medium of claim 7, wherein the target configuration characterization information comprises a maximum possible mutual rotational symmetry group for the target configuration, and wherein the program instructions are further executable to perform:

comparing the maximum possible mutual rotational symmetry group with the maximum possible mutual rotational symmetry group for the target configuration;

determining that the maximum possible mutual rotational symmetry group fails to match the maximum possible mutual rotational symmetry group for the target configuration; and

indicating that the configuration does not match the target configuration.

9. The memory medium of claim 7, wherein the target configuration characterization information comprises a constellation rotational symmetry group for the target configuration, and wherein the program instructions are further executable to perform:

comparing the maximum possible mutual rotational symmetry group with the maximum possible mutual rotational symmetry group for the target configuration;

determining that the maximum possible mutual rotational symmetry group matches the maximum possible mutual rotational symmetry group for the target configuration; and

indicating that the configuration may match the target configuration.

10. The memory medium of claim 9, wherein the program instructions are further executable to perform:

in response to said determining that the maximum possible mutual rotational symmetry group matches the maximum possible mutual rotational symmetry group for the target configuration;

determining a configuration rotational symmetry group for the configuration, comprising;

determining a largest factor of the maximum possible mutual rotational symmetry group that is a valid rotational symmetry group for the configuration, wherein the largest factor is the configuration rotational symmetry group for the configuration; and

storing the configuration rotational symmetry group for the configuration, wherein the configuration rotational symmetry group is usable to perform pattern matching between configurations.

11. The memory medium of claim 10, wherein the target configuration characterization information comprises a configuration rotational symmetry group for the target configuration, and wherein the program instructions are further executable to perform:

comparing the configuration rotational symmetry group with the configuration rotational symmetry group for the target configuration;

determining that the configuration rotational symmetry group fails to match the configuration rotational symmetry group for the target configuration; and

indicating that the configuration does not match the target configuration.

12. The memory medium of claim 10, wherein the target configuration characterization information comprises a configuration rotational symmetry group for the target configuration, and wherein the program instructions are further executable to perform:

comparing the configuration rotational symmetry group with the configuration rotational symmetry group for the target configuration;

determining that the configuration rotational symmetry group matches the configuration rotational symmetry group for the target configuration; and

indicating that the configuration may match the target configuration.

13. The memory medium of claim 12, wherein the program instructions are further executable to perform:

analyzing the configuration and the target configuration to determine whether the configuration matches the target configuration;

if the configuration fails to match the target configuration, indicating that the configuration does not match the target configuration; and

if the configuration matches the target configuration, indicating that the configuration matches the target configuration.

14. The memory medium of claim 1, wherein the program instructions are further executable to perform:

determining the rotational symmetry groups for the plurality of curves, comprising;

applying respective mapping operators to a first plurality of discrete curves, thereby generating a first plurality of mapped discrete curves, wherein the mapping operators operate to amplify features of the first plurality of discrete curves, wherein the plurality of discrete curves of the configuration comprise the first plurality of mapped discrete curves;

computing an autocorrelation of each mapped discrete curve, thereby generating a corresponding plurality of correlation values for each mapped discrete curve, 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 for each mapped discrete curve based on the corresponding plurality of correlation values; and

determining a rotational symmetry group for each mapped discrete curve based on the minimum period;

wherein the determined rotational symmetry groups for the mapped discrete curves comprise the rotational symmetry groups in the configuration characterization information.

15. The memory medium of claim 14, wherein the program instructions are further executable to perform:

receiving the first plurality of discrete curves, wherein each of the first plurality of discrete curves comprises a respective closed discrete curve, and wherein each of the first plurality of discrete curves is interpreted as a curve in a complex plane; and

determining the respective mapping operators based on the first plurality of discrete curves.

16. The memory medium of claim 15, wherein the program instructions are further executable to perform:

preprocessing the first plurality of discrete curves prior to said determining the respective mapping operators, wherein said preprocessing comprises;

normalizing each of the first plurality of discrete curves to generate respective normalized discrete curves;

computing the center of mass of each of the normalized discrete curves;

wherein said determining the respective mapping operators based on the plurality of discrete curves comprises determining each respective mapping operator based on a respective normalized discrete curve of the normalized discrete curves; and

wherein said applying the respective mapping operators to the first plurality of discrete curves comprises applying the respective mapping operators to the normalized discrete curves.

17. The memory medium of claim 16, wherein said normalizing each of the first plurality of discrete curves comprises normalizing one or more of:

number of points in each discrete curve;

distribution of points in each discrete curve;

energy of each discrete curve;

average position of each discrete curve; and

length of each discrete curve.

18. The memory medium of claim 17, wherein said normalizing the number of points in each discrete curve comprises:

normalizing the number of points such that the number of points is proportional to arc-length for the discrete curve.

19. The memory medium of claim 16, wherein each normalized discrete curve comprises a sequence of N points, D=(d₁, . . . , d_N), and wherein said determining the mapping operator based on the normalized discrete curve comprises:

calculating the mapping operator w such that;

$\underset{n=1}{\overset{N}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>d_{n+k}<br><br>d_n^{*}<br><br>w_n={\mathrm{\delta <br><br>}}_{k<br><br>\text{\hspace{1em}<br><br>}<br><br>0}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{for}<br><br>\text{\hspace{1em}<br><br>}<br><br>k=0,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},N$$w_{k+1}-w_k\cong <br><br>0<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{for}<br><br>\text{\hspace{1em}<br><br>}<br><br>k=0,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},N$

substantially holds, wherein w_N+1=w₁, and wherein δ

_ko is the Kronecker delta.

20. The memory medium of claim 14, wherein the program instructions are further executable to perform:

normalizing each mapped discrete curve to generate corresponding normalized mapped discrete curves, wherein said computing an autocorrelation of each mapped discrete curve comprises computing an autocorrelation of each normalized mapped discrete curve.

21. The memory medium of claim 14, wherein said computing a correlation of each mapped discrete curve comprises computing:

22. The memory medium of claim 14, wherein said determining a minimum period for each mapped discrete curve based on the corresponding plurality of correlation values comprises:

for each mapped discrete curve;

determining a plurality of maximum correlation values of the plurality of correlation values, wherein each of the plurality of maximum correlation values corresponds to a respective rotational shift of the mapped discrete curve; and

determining a relative rotational shift corresponding to successive maximum correlation values of the plurality of maximum correlation values;

wherein the relative rotational shift comprises the minimum period.

23. The memory medium of claim 14, wherein said determining the rotational symmetry group for each mapped discrete curve based on the minimum period comprises:

for each mapped discrete curve, dividing one rotational cycle by the minimum period, thereby generating the rotational symmetry group for the mapped discrete curve.

24. A computer-implemented method for detecting symmetries of configurations of discrete curves, wherein the program instructions are executable by a processor to:

receive configuration characterization information for a configuration of discrete curves, wherein the configuration comprises a plurality of discrete curves, and wherein the configuration characterization information comprises rotational symmetry groups for each of the plurality of discrete curves;

determine a greatest common divisor of the rotational symmetry groups of the discrete curves, wherein the greatest common divisor is a maximum possible object-based mutual rotational symmetry group for the configuration; and

store the maximum possible object-based mutual rotational symmetry group, wherein the maximum possible object-based mutual rotational symmetry group is usable to perform pattern matching between configurations.