Rotational symmetry detection for configurations of discrete curves

• US 7,212,673 B2
• Filed: 06/05/2003
• Issued: 05/01/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
• Primary Examiner(s): Mehta; Bhavesh M
• Assistant Examiner(s): Strege; John B
• Application Number:
  US10/454,940
• Publication Number:
  US 20040247182A1
• Time in Patent Office: 1,426 Days
• Field of Search: 382/199, 382/203, 382/209, 382/217
• US Class Current: 382/203
• 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/44 Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components
• 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 characterizing configurations of discrete curves based on detected symmetries in the configuration. A configuration of discrete closed curves is received. A plurality of configuration rotational symmetry sub-groups of the configuration are determined, each associated with one or more of the discrete curves, and based on each curve'"'"'s distance from a configuration center of mass, equivalence class, rotational symmetry group, and sub-configuration rotational symmetry group. The configuration rotational symmetry sub-groups are determined by normalizing the configuration, including determining a configuration center of mass, determining the equivalence class and rotational symmetry group for each discrete curve, determining one or more subsets of the discrete curves based on each discrete curve'"'"'s equivalence class and distance from the configuration center of mass, and determining configuration rotational symmetry sub-groups for each of the subsets based on each curve'"'"'s rotational symmetry group, and relative orientations of the discrete curves in the subset.

Claims

1. A computer accessible memory medium that stores program instructions for determining an underlying rotational symmetry group of a configuration of discrete curves, wherein the program instructions are executable to perform:

receiving a configuration of discrete closed curves;

determining a plurality of configuration rotational symmetry sub-groups of the configuration, wherein each of the plurality of configuration rotational symmetry sub-groups is associated with one or more of the discrete curves, and wherein the plurality of configuration rotational symmetry sub-groups are based on each discrete curve'"'"'s distance from a configuration center of mass, equivalence class, rotational symmetry group, and sub-configuration rotational symmetry group, wherein a rotational symmetry group of one indicates no rotation symmetry; and

if no discrete curves having a distance from the configuration center of mass of substantially zero also have a rotational symmetry group of one;

computing a greatest common divisor (GCD) of the plurality of configuration rotational symmetry sub-groups, wherein the GCD comprises an underlying rotation symmetry group of the configuration; and

outputting the underlying rotation symmetry group of the configuration.

2. The memory medium of claim 1, wherein said determining a plurality of configuration rotational symmetry sub-groups of the configuration comprises:

normalizing the configuration, including determining a configuration center of mass;

determining an equivalence class for each discrete curve, including determining a rotational symmetry group for each discrete curve;

determining one or more subsets of the plurality of discrete curves based on each discrete curve'"'"'s equivalence class and distance from the configuration center of mass, wherein each subset comprises one or more discrete curves at a respective distance from the configuration center of mass; and

determining one or more configuration rotational symmetry sub-groups for each of the one or more subsets based on each discrete curve'"'"'s rotational symmetry group, and relative orientations of the discrete curves in the subset.

3. The memory medium of claim 2,

wherein each of the one or more subsets comprises a respective sub-configuration of discrete curves;

and

wherein said determining one or more configuration rotational symmetry groups for each of the one or more subsets based on each discrete curve'"'"'s rotational symmetry group, and relative orientations of the discrete curves in the subset comprises;

normalizing the sub-configuration of discrete curves;

determining a plurality of respective orientations between respective pairs of the discrete curves in the sub-configuration; and

determining one or more finite sub-groups of the sub-configuration discrete curves based on the sub-configuration and the plurality of respective orientations, wherein the one or more finite sub-groups corresponds to a respective one or more rotational symmetry sub-groups of the subset.

4. The memory medium of claim 3, wherein said normalizing the sub-configuration comprises:

normalizing each of the sub-configuration discrete curves;

computing a respective discrete curve center of mass for each of the sub-configuration discrete curves;

computing a sub-configuration center of mass, wherein the sub-configuration center of mass comprises a center of mass of the sub-configuration discrete curves, wherein distances between the sub-configuration center of mass and each respective discrete curve center of mass are constants, and wherein each discrete curve center of mass comprises a respective coordinate in the complex plane; and

normalizing each discrete curve center of mass with respect to the sub-configuration center of mass.

5. The memory medium of claim 4, wherein said normalizing each discrete curve center of mass with respect to the sub-configuration center of mass comprises:

setting the distances between the sub-configuration center of mass and each discrete curve center of mass to a specified value; and

normalizing each discrete curve center of mass such that a first discrete curve center of mass is located at the specified value on the positive real axis of the complex plane.

6. The memory medium of claim 5, wherein the specified value is one, wherein the sub-configuration center of mass is at the origin of the complex plane, and wherein each discrete curve center of mass is located on a unit circle centered at the sub-configuration center of mass.

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

removing each finite sub-group that is a subset of another finite sub-group, resulting in remaining finite sub-groups.

8. The memory medium of claim 7, wherein said determining the plurality of configuration rotational symmetry sub-groups of the configuration comprises determining the rotational symmetry sub-groups of the sub-configuration that correspond to the remaining finite sub-groups.

9. The memory medium of claim 3, wherein said determining a plurality of respective orientations between respective pairs of the discrete curves comprises:

determining a minimum period between each pair in the plurality of discrete curves, thereby generating the corresponding plurality of respective orientations between respective pairs of the discrete curves.

10. The memory medium of claim 3, wherein said determining a minimum period between each pair in the plurality of discrete curves comprises:

for each pair;

computing a plurality of correlation values between a first discrete curve in the pair and a plurality of rotationally shifted versions of a second discrete curve in the pair, 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.

11. The memory medium of claim 10, wherein the first discrete curve comprises a first sequence of N points, D₁=(d₁₁, . . . , d_1N), and wherein the second discrete curve comprises a second sequence of N points, D₂=(d₂₁, . . . , d_2N), and wherein said computing a correlation of the first discrete curve in the pair with each of a plurality of rotationally shifted versions of the second discrete curve in the pair comprises computing:

$s_k=\underset{n=1}{\overset{N}{\sum <br><br>}}<br><br>d_{1,n+k}<br><br>d_{2,n}^{*}$

for k=0, . . . , N;

wherein each s_k comprises a respective correlation value between the first discrete curve and a respective rotationally shifted version of the second discrete curve.

12. The memory medium of claim 2, wherein said determining a rotational symmetry group for each discrete curve comprises:

applying a mapping operator to the 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 the rotational symmetry group of the discrete curve based on the minimum period.

13. The memory medium of claim 12, wherein said computing a correlation of the mapped discrete curve with each of a plurality of rotationally shifted versions of the mapped discrete curve comprises computing:

$s_k=\underset{n=1}{\overset{N}{\sum <br><br>}}<br><br>d_{n+k}<br><br>d_n^{*}<br><br>w_n$

for k=0, . . . , N;

wherein each s_k comprises a respective correlation value between the mapped discrete curve and a respective rotationally shifted version of the mapped discrete curve.

14. The memory medium of claim 12, wherein the medium is further configured to perform:

normalizing the discrete curve; and

determining the mapping operator based on the normalized discrete curve;

wherein said applying the mapping operator to the discrete curve comprises applying the mapping operator to the normalized discrete curve.

15. The memory medium of claim 14, wherein the 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>d_{n+k}<br><br>d_n^{*}<br><br>w_n={\mathrm{\delta <br><br>}}_{\mathrm{k0}}<br><br><br><br>\mathrm{for}<br><br><br><br>k=0,\mathrm{\dots <br><br>}<br><br>,N$ $w_{k+1}-w_k\cong <br><br>0<br><br><br><br>\mathrm{for}<br><br><br><br>k=0,\mathrm{\dots <br><br>}<br><br>,N$

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

_ko is the Kronecker delta.

16. A system for determining an underlying rotational symmetry group of a configuration of discrete curves, the system comprising:

means for receiving a configuration of discrete closed curves;

means for determining a plurality of configuration rotational symmetry sub-groups of the configuration, wherein each of the plurality of configuration rotational symmetry sub-groups is associated with one or more of the discrete curves, and wherein the plurality of configuration rotational symmetry sub-groups are based on each discrete curve'"'"'s distance from a configuration center of mass, equivalence class, rotational symmetry group, and sub-configuration rotational symmetry group;

means for computing a greatest common divisor (GCD) of the plurality of configuration rotational symmetry sub-groups, wherein the GCD comprises an underlying rotation symmetry group of the configuration; and

means for outputting the underlying rotation symmetry group of the configuration.

17. A method for determining an underlying rotational symmetry group of a configuration of discrete curves, the method comprising:

receiving a configuration of discrete closed curves;

determining a plurality of configuration rotational symmetry sub-groups of the configuration, wherein each of the plurality of configuration rotational symmetry sub-groups is associated with one or more of the discrete curves, and wherein the plurality of configuration rotational symmetry sub-groups are based on each discrete curve'"'"'s distance from a configuration center of mass, equivalence class, rotational symmetry group, and sub-configuration rotational symmetry group, wherein a rotational symmetry group of one indicates no rotation symmetry; and

if no discrete curves having a distance from the configuration center of mass of substantially zero also have a rotational symmetry group of one;

computing a greatest common divisor (GCD) of the plurality of configuration rotational symmetry sub-groups, wherein the GCD comprises an underlying rotation symmetry group of the configuration; and

outputting the underlying rotation symmetry group of the configuration.

18. The method of claim 17, wherein said determining a plurality of configuration rotational symmetry sub-groups of the configuration comprises:

normalizing the configuration, including determining a configuration center of mass;

determining an equivalence class for each discrete curve, including determining a rotational symmetry group for each discrete curve;

determining one or more subsets of the plurality of discrete curves based on each discrete curve'"'"'s equivalence class and distance from the configuration center of mass, wherein each subset comprises one or more discrete curves at a respective distance from the configuration center of mass; and

determining one or more configuration rotational symmetry sub-groups for each of the one or more subsets based on each discrete curve'"'"'s rotational symmetry group, and relative orientations of the discrete curves in the subset.

19. The method of claim 18,

wherein each of the one or more subsets comprises a respective sub-configuration of discrete curves;

and

wherein said determining one or more configuration rotational symmetry groups for each of the one or more subsets based on each discrete curve'"'"'s rotational symmetry group, and relative orientations of the discrete curves in the subset comprises;

normalizing the sub-configuration of discrete curves;

determining a plurality of respective orientations between respective pairs of the discrete curves in the sub-configuration; and

determining one or more finite sub-groups of the sub-configuration discrete curves based on the sub-configuration and the plurality of respective orientations, wherein the one or more finite sub-groups corresponds to a respective one or more rotational symmetry sub-groups of the subset.

20. The method of claim 19, wherein said normalizing the sub-configuration comprises:

normalizing each of the sub-configuration discrete curves;

computing a respective discrete curve center of mass for each of the sub-configuration discrete curves;

computing a sub-configuration center of mass, wherein the sub-configuration center of mass comprises a center of mass of the sub-configuration discrete curves, wherein distances between the sub-configuration center of mass and each respective discrete curve center of mass are constants, and wherein each discrete curve center of mass comprises a respective coordinate in the complex plane; and

normalizing each discrete curve center of mass with respect to the sub-configuration center of mass.

21. A computer accessible memory medium that stores program instructions for determining rotational symmetry groups of a configuration of discrete curves, wherein the program instructions are executable to perform:

receiving a configuration of discrete curves, wherein the configuration comprises a plurality of discrete closed curves;

normalizing the configuration, including determining a configuration center of mass;

determining a rotational symmetry group for each discrete curve;

determining an equivalence class for each discrete curve;

determining one or more subsets of the plurality of discrete curves based on each discrete curve'"'"'s equivalence class and distance from the configuration center of mass, wherein each subset comprises one or more discrete curves at a respective distance from the configuration center of mass;

determining one or more configuration rotational symmetry groups for each of the one or more subsets based on each discrete curve'"'"'s rotational symmetry group, and relative orientations of the discrete curves in the subset; and

outputting the determined one or more configuration rotational symmetry groups for each of the one or more subsets.

22. The memory medium of claim 21, wherein said normalizing the configuration comprises:

computing a discrete curve center of mass for each discrete curve in the configuration.

23. The memory medium of claim 21, wherein said determining a rotational symmetry group for each discrete curve comprises:

applying a respective mapping operator to the 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 rotational symmetry group of the discrete curve based on the minimum period.

24. The memory medium of claim 23, wherein said computing a correlation of the mapped discrete curve with each of a plurality of rotationally shifted versions of the mapped discrete curve comprises computing:

$s_k=\underset{n=1}{\overset{N}{\sum <br><br>}}<br><br>d_{n+k}<br><br>d_n^{*}<br><br>w_n$

for k=0, . . . , N;

wherein each s_k comprises a respective correlation value between the mapped discrete curve and a respective rotationally shifted version of the mapped discrete curve.

25. The memory medium of claim 22, wherein said determining an equivalence class for each discrete curve comprises:

for each pair of discrete curves in the plurality of discrete curves;

computing a correlation between a first mapped discrete curve of the pair with each of a plurality of rotationally shifted versions of a second mapped discrete curve of the pair, 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;

wherein groupings of discrete curves whose correlation values are close to one define respective equivalence classes for the discrete curves.

26. The memory medium of claim 21,

wherein each of the one or more subsets comprises a respective sub-configuration of discrete curves;

and

wherein said determining one or more configuration rotational symmetry groups for each of the one or more subsets based on each discrete curve'"'"'s rotational symmetry group and relative orientations of the discrete curves in the subset comprises;

normalizing the sub-configuration of discrete curves;

determining a plurality of respective orientations between respective pairs of the discrete curves in the sub-configuration; and

determining one or more finite sub-groups of the sub-configuration discrete curves based on the sub-configuration and the plurality of respective orientations, wherein the one or more finite sub-groups corresponds to a respective one or more rotational symmetry sub-groups of the subset.

27. The memory medium of claim 26, wherein said normalizing the sub-configuration comprises:

normalizing each of the sub-configuration discrete curves;

computing a respective discrete curve center of mass for each of the sub-configuration discrete curves;

computing a sub-configuration center of mass, wherein the sub-configuration center of mass comprises a center of mass of the sub-configuration discrete curves, wherein distances between the sub-configuration center of mass and each respective discrete curve center of mass are constants, and wherein each discrete curve center of mass comprises a respective coordinate in the complex plane; and

normalizing each discrete curve center of mass with respect to the sub-configuration center of mass.

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

removing each finite sub-group that is a subset of another finite sub-group, resulting in remaining finite sub-groups;

wherein said determining the plurality of configuration rotational symmetry sub-groups of the configuration comprises determining the rotational symmetry sub-groups of the sub-configuration that correspond to the remaining finite sub-groups.

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

determining a minimum period between each pair in the plurality of discrete curves based on the plurality of correlation values; and

determining a mutual rotational symmetry group of the first and second discrete curves based on the minimum period.

30. The memory medium of claim 29, wherein the first discrete curve comprises a first sequence of N points, D₁=(d₁₁, . . . , d_1N), and wherein the second discrete curve comprises a second sequence of N points, D₂=(d₂₁, . . . , d_2N), wherein respective points of the first discrete curve and the second discrete curve are ordered in a mathematically positive manner, and wherein said computing a correlation of the first discrete curve in the pair with each of a plurality of rotationally shifted versions of the second discrete curve in the pair comprises computing:

$s_k=\underset{n=1}{\overset{N}{\sum <br><br>}}<br><br>d_{1,n+k}<br><br>d_{2,n}^{*}$

for k=0, . . . , N;

wherein each s_k comprises a respective correlation value between the first discrete curve and a respective rotationally shifted version of the second discrete curve.

31. A method for determining rotational symmetry groups of a configuration of discrete curves, the method comprising:

receiving a configuration of discrete curves, wherein the configuration comprises a plurality of discrete closed curves;

normalizing the configuration, including determining a configuration center of mass;

determining a rotational symmetry group for each discrete curve;

determining an equivalence class for each discrete curve;

determining one or more subsets of the plurality of discrete curves based on each discrete curve'"'"'s equivalence class and distance from the configuration center of mass, wherein each subset comprises one or more discrete curves at a respective distance from the configuration center of mass;

determining one or more configuration rotational symmetry groups for each of the one or more subsets based on each discrete curve'"'"'s rotational symmetry group, and relative orientations of the discrete curves in the subset; and

outputting the determined one or more configuration rotational symmetry groups for each of the one or more subsets.

32. The method of claim 31, wherein said normalizing the configuration comprises:

computing a discrete curve center of mass for each discrete curve in the configuration.

33. The method of claim 31, wherein said determining a rotational symmetry group for each discrete curve;

comprises;

applying a respective mapping operator to the 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 rotational symmetry group of the discrete curve based on the minimum period.

34. The method of claim 31, wherein said determining an equivalence class for each discrete curve comprises:

for each pair of discrete curves in the plurality of discrete curves;

computing a correlation between a first mapped discrete curve of the pair with each of a plurality of rotationally shifted versions of a second mapped discrete curve of the pair, 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;

wherein groupings of discrete curves whose correlation values are close to one define respective equivalence classes for the discrete curves.

35. The method of claim 31,

wherein each of the one or more subsets comprises a respective sub-configuration of discrete curves;

and

wherein said determining one or more configuration rotational symmetry groups for each of the one or more subsets based on each discrete curve'"'"'s rotational symmetry group and relative orientations of the discrete curves in the subset comprises;

normalizing the sub-configuration of discrete curves;

determining a plurality of respective orientations between respective pairs of the discrete curves in the sub-configuration; and

determining one or more finite sub-groups of the sub-configuration discrete curves based on the sub-configuration and the plurality of respective orientations, wherein the one or more finite sub-groups corresponds to a respective one or more rotational symmetry sub-groups of the subset.

36. The method of claim 35, wherein said normalizing the sub-configuration comprises:

normalizing each of the sub-configuration discrete curves;

computing a respective discrete curve center of mass for each of the sub-configuration discrete curves;

computing a sub-configuration center of mass, wherein the sub-configuration center of mass comprises a center of mass of the sub-configuration discrete curves, wherein distances between the sub-configuration center of mass and each respective discrete curve center of mass are constants, and wherein each discrete curve center of mass comprises a respective coordinate in the complex plane; and

normalizing each discrete curve center of mass with respect to the sub-configuration center of mass.

37. The method of claim 35, the method further comprising:

removing each finite sub-group that is a subset of another finite sub-group, resulting in remaining finite sub-groups;

wherein said determining the plurality of configuration rotational symmetry sub-groups of the configuration comprises determining the rotational symmetry sub-groups of the sub-configuration that correspond to the remaining finite sub-groups.

38. A system for determining rotational symmetry groups of a configuration of discrete curves, comprising:

means for receiving a configuration of discrete curves, wherein the configuration comprises a plurality of discrete closed curves;

means for normalizing the configuration, including determining a configuration center of mass;

means for determining a rotational symmetry group for each discrete curve;

means for determining an equivalence class for each discrete curve;

means for determining one or more subsets of the plurality of discrete curves based on each discrete curve'"'"'s equivalence class and distance from the configuration center of mass, wherein each subset comprises one or more discrete curves at a respective distance from the configuration center of mass;

means for determining one or more configuration rotational symmetry groups for each of the one or more subsets based on each discrete curve'"'"'s rotational symmetry group, and relative orientations of the discrete curves in the subset; and

means for outputting the determined one or more configuration rotational symmetry groups for each of the one or more subsets.

44. The memory medium of claim 38, wherein said determining a plurality of respective orientations between respective pairs of the discrete curves comprises:

determining a minimum period between each pair in the plurality of discrete curves, thereby generating the corresponding plurality of respective orientations between respective pairs of the discrete curves.

45. The memory medium of claim 44, wherein said determining a minimum period between each pair in the plurality of discrete curves comprises:

for each pair;

computing a plurality of correlation values between a first discrete curve in the pair and a plurality of rotationally shifted versions of a second discrete curve in the pair, 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.

46. The memory medium of claim 45, wherein the first discrete curve comprises a first sequence of N points, D₁=(d₁₁, . . . , d_1N), and wherein the second discrete curve comprises a second sequence of N points, D₂=(d₂₁, . . . , d_2N), and wherein said computing a correlation of the first discrete curve in the pair with each of a plurality of rotationally shifted versions of the second discrete curve in the pair comprises computing:

$s_k=\underset{n=1}{\overset{N}{\sum <br><br>}}<br><br>d_{1,n+k}<br><br>d_{2,n}^{*}$

for k=0, . . . , N;

wherein each s_k comprises a respective correlation value between the first discrete curve and a respective rotationally shifted version of the second discrete curve.

39. A computer accessible memory medium that stores program instructions for determining rotational symmetry sub-groups of a configuration of substantially equivalent discrete curves, wherein the program instructions are executable to perform:

receiving a configuration of discrete curves, wherein the configuration of discrete curves comprises a plurality of discrete curves, and wherein each of the plurality of discrete curves are closed;

normalizing the configuration of discrete curves;

determining a plurality of respective orientations between respective pairs of the discrete curves;

determining one or more finite sub-groups of the plurality of discrete curves based on the configuration and the plurality of respective orientations, wherein the one or more finite sub-groups corresponds to a respective one or more rotational symmetry sub-groups of the configuration; and

outputting the one or more rotational symmetry sub-groups of the configuration.

40. The memory medium of claim 39, wherein said normalizing the configuration comprises:

normalizing each of the configuration discrete curves;

computing a respective discrete curve center of mass for each of the configuration discrete curves;

computing a configuration center of mass, wherein the configuration center of mass comprises a center of mass of the configuration discrete curves, wherein distances between the configuration center of mass and each respective discrete curve center of mass are constants, and wherein each discrete curve center of mass comprises a respective coordinate in the complex plane; and

normalizing each discrete curve center of mass with respect to the configuration center of mass.

41. The memory medium of claim 40, wherein said normalizing each discrete curve center of mass with respect to the configuration center of mass comprises:

setting the distances between the configuration center of mass and each discrete curve center of mass to a specified value; and

normalizing each discrete curve center of mass such that a first discrete curve center of mass is located at the specified value on the positive real axis of the complex plane.

42. The memory medium of claim 41, wherein the specified value is one, wherein the configuration center of mass is at the origin of the complex plane, and wherein each discrete curve center of mass is located on a unit circle centered at the configuration center of mass.

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

removing each finite sub-group that is a subset of another finite sub-group, resulting in remaining finite sub-groups;

wherein said determining the plurality of configuration rotational symmetry sub-groups of the configuration comprises determining the rotational symmetry sub-groups of the configuration that correspond to the remaining finite sub-groups.

47. A method for determining rotational symmetry sub-groups of a configuration of substantially equivalent discrete curves, the method comprising:

receiving a configuration of discrete curves, wherein the configuration of discrete curves comprises a plurality of discrete curves, and wherein each of the plurality of discrete curves are closed;

normalizing the configuration of discrete curves;

determining a plurality of respective orientations between respective pairs of the discrete curves;

determining one or more finite sub-groups of the plurality of discrete curves based on the configuration and the plurality of respective orientations, wherein the one or more finite sub-groups corresponds to a respective one or more rotational symmetry sub-groups of the configuration; and

outputting the one or more rotational symmetry sub-groups of the configuration.

48. The method of claim 47, wherein said normalizing the configuration comprises:

normalizing each of the configuration discrete curves;

computing a respective discrete curve center of mass for each of the configuration discrete curves;

computing a configuration center of mass, wherein the configuration center of mass comprises a center of mass of the configuration discrete curves, wherein distances between the configuration center of mass and each respective discrete curve center of mass are constants, and wherein each discrete curve center of mass comprises a respective coordinate in the complex plane; and

normalizing each discrete curve center of mass with respect to the configuration center of mass.

49. The method of claim 48, wherein said normalizing each discrete curve center of mass with respect to the configuration center of mass comprises:

setting the distances between the configuration center of mass and each discrete curve center of mass to one; and

normalizing each discrete curve center of mass such that a first discrete curve center of mass is located on the positive real axis of the complex plane;

wherein the configuration center of mass is at the origin of the complex plane, and wherein each discrete curve center of mass is located on a unit circle centered at the configuration center of mass.

50. The method of claim 47, the method further comprising:

removing each finite sub-group that is a subset of another finite sub-group, resulting in remaining finite sub-groups;

wherein said determining the plurality of configuration rotational symmetry sub-groups of the configuration comprises determining the rotational symmetry sub-groups of the configuration that correspond to the remaining finite sub-groups.

51. The method of claim 47, wherein said determining a plurality of respective orientations between respective pairs of the discrete curves comprises:

determining a minimum period between each pair in the plurality of discrete curves, thereby generating the corresponding plurality of respective orientations between respective pairs of the discrete curves.

52. The method of claim 51, wherein said determining a minimum period between each pair in the plurality of discrete curves comprises:

for each pair;

computing a plurality of correlation values between a first discrete curve in the pair and a plurality of rotationally shifted versions of a second discrete curve in the pair, 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.

53. The method of claim 52, wherein the first discrete curve comprises a first sequence of N points, D₁=(d₁₁, . . . , d_1N), and wherein the second discrete curve comprises a second sequence of N points, D₂=(d₂₁, . . . , d_2N), and wherein said computing a correlation of the first discrete curve in the pair with each of a plurality of rotationally shifted versions of the second discrete curve in the pair comprises computing:

$s_k=\underset{n=1}{\overset{N}{\sum <br><br>}}<br><br>d_{1,n+k}<br><br>d_{2,n}^{*}$

for k=0, . . . , N;

wherein each s_k comprises a respective correlation value between the first discrete curve and a respective rotationally shifted version of the second discrete curve.

54. A system for determining rotational symmetry sub-groups of a configuration of substantially equivalent discrete curves, the system comprising:

means for receiving a configuration of discrete curves, wherein the configuration of discrete curves comprises a plurality of discrete curves, and wherein each of the plurality of discrete curves are closed;

means for normalizing the configuration of discrete curves;

means for determining a plurality of respective orientations between respective pairs of the discrete curves;

means for determining one or more finite sub-groups of the plurality of discrete curves based on the configuration and the plurality of respective orientations, wherein the one or more finite sub-groups corresponds to a respective one or more rotational symmetry sub-groups of the configuration; and

means for outputting the one or more rotational symmetry sub-groups of the configuration.