Discrete curve symmetry detection

• US 7,269,286 B2
• Filed: 06/05/2003
• Issued: 09/11/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: Williams, Mark S., Wenzel, Lothar
• Primary Examiner(s): Mehta; Bhavesh M.
• Assistant Examiner(s): Strege; John B
• Application Number:
  US10/455,141
• Publication Number:
  US 20040247181A1
• Time in Patent Office: 1,559 Days
• Field of Search: 382/199, 382/203, 382/209, 382/217, 382/216
• 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/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 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.

Claims

1. A computer accessible memory medium that stores program instructions for detecting symmetries of discrete curves, wherein the program instructions are executable by a processor 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 correlation 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.

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

receiving the first discrete curve, wherein the first discrete curve comprises a closed discrete curve, and wherein the first discrete curve is interpreted as a curve in a complex plane; and

determining the mapping operator based on the first discrete curve.

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

preprocessing the first discrete curve prior to said determining the mapping operator, wherein said preprocessing comprises;

normalizing the first discrete curve;

computing the center of mass of the normalized discrete curve;

wherein said determining the mapping operator based on the first discrete curve comprises determining the mapping operator based on the normalized discrete curve; and

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

4. The memory medium of claim 3, wherein said normalizing comprises normalizing one or more of:

number of points in the first discrete curve;

distribution of points in the first discrete curve;

energy of the first discrete curve;

average position of the first discrete curve; and

length of the first discrete curve.

5. The memory medium of claim 4, wherein said normalizing the number of points in the first discrete curve comprises:

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

6. The memory medium of claim 4, wherein said normalizing the energy of the first discrete curve comprises:

computing the center of mass of the first discrete curve;

normalizing the distance from each point in the first discrete curve to the center of mass such that the sum of the squares of the distances is equal to a specified value.

7. The memory medium of claim 3, 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;

$\begin{array}{cc}\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}}& \mathrm{for}<br><br><br><br>k=0,\mathrm{\dots <br><br>}<br><br>,N\\ w_{k+1}-w_k\cong <br><br>0& \mathrm{for}<br><br><br><br>k=0,\mathrm{\dots <br><br>}<br><br>,N\end{array}$

substantially holds, wherein w<sub>N−

1</sub>=w₁, and wherein δ

_ko is the Kronecker delta.

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

acquiring a data set; and

determining the first discrete curve from the data set, wherein the first discrete curve corresponds to a respective object in the data set;

wherein the first discrete curve corresponds to an object of interest.

9. The memory medium of claim 8, wherein said determining the first discrete curve from the data set comprises:

performing edge detection on the data set to determine the first discrete curve.

10. The memory medium of claim 9, wherein said determining the first discrete curve from the data set further comprises:

applying a filter to smooth the first discrete curve.

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

normalizing the mapped discrete curve, thereby generating a normalized mapped discrete curve, wherein the second mapped discrete curve comprises a second normalized mapped discrete curve, and wherein said computing the correlation of the mapped discrete curve with a plurality of rotationally shifted versions of the second mapped discrete curve comprises computing the correlation of the normalized mapped discrete curve with a plurality of rotationally shifted versions of the second normalized mapped discrete curve.

12. The memory medium of claim 1, wherein said computing a correlation of the mapped discrete curve with each of a plurality of rotationally shifted versions of the second mapped discrete curve 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 d₁ is the first mapped discrete curve, and d₂ is the second mapped discrete curve, and wherein each s_k comprises a respective correlation value between the mapped discrete curve and a respective rotationally shifted version of the second mapped discrete curve.

13. The memory medium of claim 1, wherein said determining a minimum period of the correlation of the first and second discrete curves based on the plurality of correlation values comprises:

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 between the first and second discrete curves; 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.

14. The memory medium of claim 1, wherein said determining a minimum period of the correlation of the first and second discrete curves based on the plurality of correlation values comprises:

computing a power spectrum of the plurality of correlation values; and

determining the minimum period based on the power spectrum.

15. The memory medium of claim 14, 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.

16. The memory medium of claim 1, wherein said determining a minimum period of the correlation of the first and second discrete curves based on the plurality of correlation values comprises:

performing peak detection on the plurality of correlation values to determine two or more successive peaks; and

determining the minimum period based on the determined two or more successive peaks.

17. The memory medium of claim 16, wherein said determining a minimum period of the correlation of the first and second discrete curves based on the plurality of correlation values further comprises:

filtering the plurality of correlation values prior to said performing peak detection, thereby reducing peaks resulting from random effects.

18. The memory medium of claim 17, wherein said filtering comprises using a Savitzky-Golai filter of an order that avoids random effects.

19. The memory medium of claim 1, wherein said determining a minimum period of the correlation of the first and second discrete curves based on the plurality of correlation values comprises:

determining two or more zero crossing points in the plurality of correlation values; and

determining the minimum period based on the determined two or more zero crossing points.

20. The memory medium of claim 19, wherein said determining a minimum period of the correlation of the first and second discrete curves based on the plurality of correlation values further comprises:

removing DC components from the plurality of correlation values to generate a modified set of correlation values; and

applying one or more filters to the modified set of correlation values to generate filtered correlation values; and

determining the two or more zero crossing points based on the filtered correlation values to estimate an underlying principal frequency of the filtered correlation values; and

determining the minimum period based on the estimated underlying principal frequency.

21. The memory medium of claim 1,

wherein the mapping operator comprises a first mapping operator;

and

wherein the program instructions are further executable to perform;

applying a second mapping operator to a second discrete curve, thereby generating the second mapped discrete curve, wherein the second mapping operator operates to amplify features of the second discrete curve;

wherein the symmetry group comprises a mutual symmetry group of the first and second discrete curves.

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

normalizing the first discrete curve prior to said applying the mapping operator to the first discrete curve; and

normalizing the second discrete curve prior to said applying the second mapping operator to the second discrete curve.

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

normalizing the first and second mapped discrete curves prior to said computing the correlation of the first mapped discrete curve with each of the plurality of rotationally shifted versions of the second mapped discrete curve.

24. The memory medium of claim 1, wherein said determining the symmetry group based on the minimum period comprises:

dividing one rotational cycle by the minimum period, thereby generating the symmetry group, wherein the symmetry group comprises a rotational symmetry group.

25. The memory medium of claim 1, wherein the first discrete curve and the second discrete curve comprise closed discrete curves, wherein the first discrete curve and the second discrete curve are interpreted as curves in a complex plane.

26. The memory medium of claim 1, wherein respective points of the first discrete curve and the second discrete curve are ordered in a mathematically positive manner.

27. The memory medium of claim 1, wherein the first mapped discrete curve comprises a first sequence of N points, D₁′

=(d₁₁, . . . , d_1N), and wherein the second mapped discrete curve comprises a second sequence of N points, D₂′

=(d₂₁, . . . , d_2N), and wherein said computing a correlation of the first mapped discrete curve with each of a plurality of rotationally shifted versions of the second mapped discrete curve 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.

28. The memory medium of claim 1,

wherein the second mapped discrete curve comprises a reflected version of a third mapped discrete curve about a specified axis of reflection.

29. The memory medium of claim 28, wherein said determining the symmetry group based on the minimum period comprises:

dividing one rotational cycle by the minimum period, thereby generating the symmetry group, wherein the symmetry group comprises a reflection symmetry group.

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

determining one or more axes of reflection based on the specified axis of reflection and the minimum period.

31. The memory medium of claim 30, wherein said determining one or more axes of reflection based on the specified axis of reflection and the minimum period comprises:

determining a rotational shift between an initial orientation of the second mapped discrete curve and an orientation associated with a first correlation value peak, wherein the determined rotational shift indicates a reflection axis offset equal to half the rotational shift;

determining an initial axis of reflection based on the specified axis of reflection and the reflection axis offset.

32. The memory medium of claim 31,

wherein the specified axis has a first orientation angle;

and

wherein said determining the initial axis of reflection based on the specified axis of reflection and the reflection axis offset comprises;

computing an orientation of the initial axis of reflection by adding the reflection axis offset to the first orientation angle.

33. The memory medium of claim 32,

wherein the specified axis has a first orientation angle such that the initial axis of reflection has an orientation equal to the reflection axis offset.

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

generating the second mapped discrete curve by reflecting each point in the third mapped discrete curve about the specified axis, thereby generating respective points in the second mapped discrete curve.

35. The memory medium of claim 34, wherein said reflecting each point in the third mapped discrete curve about the specified axis comprises:

shifting and rotating a coordinate system in the complex plane such that the specified axis of rotation comprises a positive vertical axis through an origin of the complex plane;

determining corresponding positions for each point in the third mapped discrete curve based on the shifted and rotated coordinate system, thereby generating corresponding transformed points; and

computing a complex conjugate for of the transformed points, thereby generating corresponding reflected points, wherein the reflected points comprise the second mapped discrete curve.

36. The memory medium of claim 1,

wherein the second discrete curve and the first discrete curve comprise the same discrete curve;

wherein said computing a correlation of the first mapped discrete curve with each of a plurality of rotationally shifted versions of the second mapped discrete curve comprises computing a correlation of the first mapped discrete curve with each of a plurality of rotationally shifted versions of the first mapped discrete curve; and

wherein said determining a minimum period of the correlation of the first and second discrete curves based on the plurality of correlation values comprises determining a minimum period of the correlation of the first discrete curve, wherein the minimum period indicates a symmetry group of the first discrete curve.

37. The memory medium of claim 36, wherein said determining the symmetry group based on the minimum period comprises:

dividing one rotational cycle by the minimum period, thereby generating the symmetry group, wherein the symmetry group comprises a rotational symmetry group of the first discrete curve.

38. The memory medium of claim 36,

wherein the second mapped discrete curve comprises a reflected version of the first mapped discrete curve about a specified axis of reflection;

and

wherein said determining the symmetry group based on the minimum period comprises;

dividing one rotational cycle by the minimum period, thereby generating the symmetry group, wherein the symmetry group comprises a reflection symmetry group of the first discrete curve.

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

determining zero or more axes of reflection based on the specified axis of reflection and the minimum period.

40. The memory medium of claim 39, wherein said determining zero or more axes of reflection based on the specified axis of reflection and the minimum period comprises:

determining a rotational shift between an initial orientation of the second mapped discrete curve and an orientation associated with a first correlation value peak, wherein the determined rotational shift indicates a reflection axis offset equal to half the rotational shift;

determining an initial axis of reflection based on the specified axis of reflection and the reflection axis offset; and

determining zero or more additional axes of reflection based on the initial axis of reflection and the minimum period.

41. The memory medium of claim 40,

wherein the specified axis has a first orientation angle;

and

wherein said determining the initial axis of reflection based on the specified axis of reflection and the reflection axis offset comprises;

computing an orientation of the initial axis of reflection by adding the reflection axis offset to the first orientation angle; and

wherein said determining zero or more additional axes of reflection based on the initial axis of reflection and the minimum period comprises;

computing a respective zero or more orientations of the zero or more additional axes of reflection by adding corresponding zero or more successive multiples of the minimum period to the orientation of the initial axis.

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

determining one or more additional axes of reflection based on the initial axis of reflection and the minimum period, wherein said determining one or more additional axes of reflection based on the initial axis of reflection and the minimum period comprises;

computing a respective one or more orientations of the one or more additional axes of reflection by adding successive multiples of the minimum period to the orientation of the initial axis.

57. The memory medium of claim 56,

wherein the specified axis has a first orientation angle such that the initial axis of reflection has an orientation equal to the reflection axis offset.

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

determining one or more additional axes of reflection based on the initial axis of reflection and the minimum period.

42. 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 correlation 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.

43. The method of claim 42, the method further comprising:

receiving the first discrete curve, wherein the first discrete curve comprises a closed discrete curve, and wherein the first discrete curve is interpreted as a curve in a complex plane; and

determining the mapping operator based on the first discrete curve.

44. The method of claim 43, the method further comprising:

preprocessing the first discrete curve prior to said determining the mapping operator, wherein said preprocessing comprises;

normalizing the first discrete curve;

computing the center of mass of the normalized discrete curve;

wherein said determining the mapping operator based on the first discrete curve comprises determining the mapping operator based on the normalized discrete curve; and

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

45. The method of claim 44, 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;

$\begin{array}{cc}\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}}& \mathrm{for}<br><br><br><br>k=0,\mathrm{\dots <br><br>}<br><br>,N\\ w_{k+1}-w_k\cong <br><br>0& \mathrm{for}<br><br><br><br>k=0,\mathrm{\dots <br><br>}<br><br>,N\end{array}$

substantially holds, wherein w<sub>N−

1</sub>=w₁, and wherein δ

_ko is the Kronecker delta.

46. The method of claim 42, wherein said computing a correlation of the mapped discrete curve with each of a plurality of rotationally shifted versions of the second mapped discrete curve 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 d₁ is the first mapped discrete curve, and d₂ is the second mapped discrete curve, and wherein each s_k comprises a respective correlation value between the mapped discrete curve and a respective rotationally shifted version of the second mapped discrete curve.

47. The method of claim 42,

wherein the mapping operator comprises a first mapping operator;

and

wherein the method is further configured to perform;

applying a second mapping operator to a second discrete curve, thereby generating the second mapped discrete curve, wherein the second mapping operator operates to amplify features of the second discrete curve;

wherein the symmetry group comprises a mutual symmetry group of the first and second discrete curves.

48. The method of claim 42, wherein said determining the symmetry group based on the minimum period comprises:

dividing one rotational cycle by the minimum period, thereby generating the symmetry group, wherein the symmetry group comprises a rotational symmetry group.

49. The method of claim 42,

wherein the second mapped discrete curve comprises a reflected version of a third mapped discrete curve about a specified axis of reflection;

and

wherein said determining the symmetry group based on the minimum period comprises;

dividing one rotational cycle by the minimum period, thereby generating the symmetry group, wherein the symmetry group comprises a reflection symmetry group.

50. The method of claim 42,

wherein the second discrete curve and the first discrete curve comprise the same discrete curve;

wherein said computing a correlation of the first mapped discrete curve with each of a plurality of rotationally shifted versions of the second mapped discrete curve comprises computing a correlation of the first mapped discrete curve with each of a plurality of rotationally shifted versions of the first mapped discrete curve; and

wherein said determining a minimum period of the correlation of the first and second discrete curves based on the plurality of correlation values comprises determining a minimum period of the correlation of the first discrete curve, wherein the minimum period indicates a symmetry group of the first discrete curve.

51. The method of claim 50, wherein said determining the symmetry group based on the minimum period comprises:

dividing one rotational cycle by the minimum period, thereby generating the symmetry group, wherein the symmetry group comprises a rotational symmetry group of the first discrete curve.

52. The method of claim 50,

wherein the second mapped discrete curve comprises a reflected version of the first mapped discrete curve about a specified axis of reflection;

and

wherein said determining the symmetry group based on the minimum period comprises;

dividing one rotational cycle by the minimum period, thereby generating the symmetry group, wherein the symmetry group comprises a reflection symmetry group of the first discrete curve.

53. A method for detecting reflection symmetries of discrete curves, the method comprising:

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 correlation based on the plurality of correlation values;

determining a reflection symmetry group of the discrete curve based on the minimum period; and

outputting the determined reflection symmetry group.

54. A computer accessible memory medium that stores program instructions for detecting rotational symmetries of discrete curves, wherein the program instructions are executable by a processor 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 correlation 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.

55. A computer accessible memory medium that stores program instructions for detecting reflection symmetries of a discrete curve, wherein the program instructions are executable by a processor 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 correlation 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.