Algorithm to measure symmetry and positional entropy of a data set

• US 20080159631A1
• Filed: 03/09/2007
• Published: 07/03/2008
• Est. Priority Date: 01/03/2007
• Status: Active Grant

• Current Assignee: Dennis G. Collins
• Original Assignee: Dennis G. Collins
• Inventors: Collins, Dennis G.
• Granted Patent: US 7,873,220 B2
• Time in Patent Office: Days
• 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 is given to measure the symmetry (SYM=global symmetry) of N points. The algorithm is 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 point. These parameters (SYM and UPED) represent a “MISSING LINK” connecting symmetry with order/disorder with entropy, since for small occupation numbers (1<=k<=4) they come out almost the same. Here the occupation number, k, is the number of equal distances in the figure for a given value d. The algorithm can be added via software to imaging devices, such as computer graphic programs or cameras to solve problems of defect detection, say in gems, or object detection.

Claims

1. A computer program operable in response to an input of a set of N points to measure symmetry among said points, so as to determine positional entropy of said set of N points, 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 from said occupation numbers a total symmetry and un-normalized positional entropy deficit;

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 computer program of claim 1, further comprising the step of determining the order for said set of N points.

4. The program of claim 1, further comprising the step of determining synergy of said data points, said data points comprise a combination of at least two data subsets, wherein said synergy is symmetry of said data points divided by a sum of symmetry of each of said data subsets.

5. The program of claim 1, the step of receiving said coordinates for each of said N points 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, further comprising the step of determining synergy of said data points and said data points comprise a combination of at least two data subsets, wherein said synergy is symmetry of said data points divided by a sum of symmetry 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 computer readable program, said computer program being operable in response to an input of said set of N points to measure symmetry among said points, so as to determine positional entropy of said set of N points, 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 from said occupation number one of the group of total symmetry or un-normalized positional entropy deficit;

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

evaluating at least one characteristic of said image based on the calculated global symmetry and positional entropy.

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

10. The program 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, and said step of determining order for said set of N point further includes identifying, based on the order, rotational symmetry within said regions.

12. The method recited in claim 9, wherein said characteristic comprises scalable symmetry between a pair of regions within said image, and method further includes the step of identifying, based on the order, scalable symmetry between said regions 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, and said characteristic comprises dissimilarities between the image and a stored template, and said method further comprises the step of identifying said dissimilarities based on said calculated total symmetry and positional entropy of said set of N 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 the calculated symmetry and a reference symmetry value of said set of N points, and said method further comprises the step of identifying a fault in said sample based on said difference between the calculated total symmetry and said pre-selected reference symmetry value.