Algorithm to measure symmetry and positional entropy of a data set

• US 7,873,220 B2
• Filed: 03/09/2007
• Issued: 01/18/2011
• Est. Priority Date: 01/03/2007
• Status: Active Grant

• Current Assignee: Dennis G. Collins
• Original Assignee: Dennis G. Collins
• Inventors: Collins, Dennis G.
• Primary Examiner(s): Le; Vu
• Assistant Examiner(s): MACKOWEY, ANTHONY M
• Application Number:
  US11/715,909
• Publication Number:
  US 20080159631A1
• Time in Patent Office: 1,411 Days
• Field of Search: 382141-152, 382/195, 382/199, 382/201, 382/203, 382/206, 382/209, 382/212, 382216-222, 382/278, 382294-298
• 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

Abstract

A method and algorithm for measuring the symmetry (SYM=total symmetry) of N points based on counting the number of “elementary symmetric recognition acts”, or having two distances d(A,B) and d(C,D) be equal within a given tolerance t. The same algorithm can be adapted to measure un-normalized positional entropy deficit (UPED) and positional entropy of N points. These parameters (SYM and UPED) come out almost the same for small occupation numbers (1<=k<=4). Here the occupation number k is the number of equal distances in the figure for a given value d. The algorithm can be incorporated into an imaging device, such as computer graphic programs or cameras, to solve problems of defect detection, say in gems, or object detection.

Claims

1. A non-transitory computer readable medium storing a program for determining positional entropy of a set of N points resulting from a measurement, said program comprising the steps of:

receiving coordinates for each of said N points;

calculating a set of a maximum of N(N−

1)/2 pairs of distances within said points;

calculating local symmetry;

calculating global symmetry to determine a set of occupation numbers;

determining a total symmetry and an un-normalized positional entropy deficit for said points from said occupation numbers; and

determining a positional entropy value of said set of N points.

2. The program of claim 1, wherein said data points are received as discrete coordinate points.

3. The program of claim 1, further comprising the step of determining the order for said set of N points.

4. The program of claim 1, wherein said set of N data points consists of a combination of at least two data subsets, said program further comprising the steps of:

determining total symmetry values for each of said data subsets;

determining synergy of said data points by dividing the total symmetry of said set of N data points by a sum of the total symmetry values for each of said data subsets; and

evaluating, based on the synergy, if said combination of data subsets is a lock-and-key fit.

5. The program of claim 1, wherein the step of receiving said coordinates for each of said N points further comprises the steps of:

receiving a continuous function;

interpolating coordinates of N points within said function; and

creating said set of N points from said interpolated coordinates.

6. The program of claim 5, further comprising the step of determining order for said set of N points.

7. The program of claim 5, wherein said set of N data points comprise a combination of at least two data subsets, said program further comprising the steps of:

determining total symmetry values for each of said data subsets; and

determining synergy of said data points by dividing the total symmetry of said set of N data points by a sum of the total symmetry values for each of said data subsets.

8. A method for image analysis, comprising the steps of:

capturing an image with an imaging apparatus;

transforming said image into a set of N data points;

transmitting said data points to a non-transitory computer readable medium storing a program for determining positional entropy of said set of N points;

executing said program, comprising the steps of;

receiving coordinates for each of said N points;

calculating a set of a maximum of N(N−

1)/2 pairs of distances within said points;

calculating local symmetry;

calculating global symmetry to determine a set of occupation numbers;

determining a total symmetry and an un-normalized positional entropy deficit of said points from said occupation numbers;

determining a positional entropy value of said set of N points; and

evaluating at least one characteristic of said image based on the calculated total symmetry and positional entropy value of said set of N points.

9. The method of claim 8, further comprising the step of determining order for said set of N points.

10. The method of claim 8, further comprising the step of determining synergy of said data points.

11. The method recited in claim 9, wherein said characteristic comprises rotational symmetry between a pair of regions within said image, said method further comprising the step of identifying rotational symmetry within said regions based on said order.

12. The method recited in claim 9, wherein said characteristic comprises scalable symmetry between a pair of regions within said image, said method further comprising the steps of:

identifying scalable symmetry between said regions based on said order; and

identifying said regions as copies in different scales.

13. The method recited in claim 8, wherein said image represents the combination of a template and a sample, said characteristic comprises dissimilarities between the image and at least one stored template, and said method further comprises the step of identifying said dissimilarities based on said total symmetry and positional entropy of said set of points.

14. The method recited in claim 9, wherein said image represents the combination of a template and a sample, said characteristic comprises a difference between said total symmetry of said set of N points and a pre-selected reference symmetry value, and said method further comprises the step of identifying a fault in said sample based on said difference between said total symmetry and said pre-selected reference symmetry value.