Encoding system providing discrimination, classification, and recognition of shapes and patterns

• US 7,809,195 B1
• Filed: 10/14/2008
• Issued: 10/05/2010
• Est. Priority Date: 09/18/2008
• Status: Expired due to Fees

• Current Assignee: Ernest Greene
• Original Assignee: Ernest Greene
• Inventors: Greene, Ernest
• Primary Examiner(s): BHATNAGAR, ANAND P
• Application Number:
  US12/251,340
• Time in Patent Office: 721 Days
• Field of Search: 382/100, 382/181, 382/190, 382/195, 382/206, 382/224, 382/225, 382/232, 382/243, 382/244, 382/245, 707/1, 707/708, 707/713, 341/51
• US Class Current: 382/181
• 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
• CPC Class Codes: G06V 10/507 Summing image-intensity values; Histogram projection analysis

Abstract

My system provides summaries of shapes and patterns that are manifested by the states of an array of elements, and methods for comparing them for correspondence. A very basic embodiment provides these summaries in the following manner. The array provides a Cartesian coordinate system address for each element. Each element of the array is polled, and if the element is part of the pattern, described here as being marked, it delivers its address to a processor. The processor calculates the distance from each marked element to a central location, described as a convergence hub, and delivers these distance values to a distributor. The distributor provides a summary distribution, which specifies the number of times a given distance was observed (or numerical adjustments thereof). This distribution is stored and used for comparison against alternative distributions, which provides a basis for assessing similarity or difference among various shapes and patterns.

Claims

1. A method for summarizing a spatial pattern within an array of elements wherein marked elements of said array designate said spatial pattern and distances from a convergence hub to said marked elements are combined into a distribution that provides a summary of said spatial pattern, comprising,

(a) providing an array of elements and the locations of said elements in said array according to a coordinate address system, a subset of said array of elements having a state that represents said spatial pattern, providing a label for said state, and designating said elements of said subset as said marked elements,

(b) polling said elements of said array to determine the coordinate address of each of said marked elements so as to provide a set of coordinate addresses,

(c) a distance processor to measure and calculate the distance of each marked element from a convergence hub, thus providing a set of distance values for said marked elements,

(d) a distributor to combine said set of distance values to form a distance distribution, said distance distribution having an abscissa scale and an ordinate scale,

(f) deriving a plurality of alternative distance distributions from said array, said alternative distance distributions being based on said coordinate address system, said label for said state, said polling, said measuring or calculating of distance, and said combining of said set of distance values into said distance distribution, thereby providing a plurality of alternative distance distributions which in turn provide summaries of said respective plurality of alternative spatial patterns, and

(g) a distribution comparator to quantitatively compare said distance distribution with said plurality of alternative distance distributions,

whereby said quantitative comparison can be used to determine degree of correspondence between said spatial pattern and said plurality of alternative spatial patterns.

2. The method of claim 1 wherein said distance processor is using the Pythagorean theorem, thereby providing a relatively simple method for specifying said distances from said marked elements to said convergence hub.

3. The method of claim 1 wherein said convergence hub is at the center of said array, thereby providing an simple and efficient method for summarizing said spatial pattern.

4. The method of claim 1, further including specifying the location of a centroid for said marked elements, and using said centroid as said convergence hub, thereby providing translation invariance of said spatial pattern and facilitates comparison of said spatial pattern irrespective of size.

5. The method of claim 1, further including specifying the locations of a plurality of additional convergence hubs, and using said plurality of additional convergence hubs to derive a set of multiple-hub distance distributions for said spatial pattern, whereby said spatial pattern is summarized from a number of vantage points.

6. The method of claim 1, further including using said coordinate addresses to specify a set of sectors, each of said sectors consisting of a subset of said elements of said array, such that said distance values provide a distribution for each sector, each distribution being designated as a sector distribution, thereby providing a set of partial summaries of said spatial pattern.

7. The method of claim 6, further including combining said sector distributions to provide a single summary distribution for said spatial pattern, thus providing a more effective summary of said spatial pattern.

8. The method of claim 7, further including a plurality of alternative patterns that are distinguished by a respective plurality of state levels, and further including providing a set of quantitative scale values to label said state levels, and combining said scale values with said distance values into a single distribution, thus providing a summary of said alternative patterns as a single pattern mixture.

9. The method of claim 1 wherein a second subset of said array of elements has a second state that represents a second spatial pattern, and further including determining said distance distributions for said elements of said second subset, thereby providing a summary for a plurality of alternative patterns within said array.

10. The method of claim 1, further including transforming the ordinate and abscissa values of said distance distribution to be proportional to said values, thus improving the comparison of said distance distribution with said alternative distance distributions.

11. The method of claim 1 wherein said quantitatively comparing said distance distribution to said plurality of alternative distance distributions is done by deriving a sum of squared differences value or a Chi Squared test value, thereby allowing correspondence of said spatial pattern to said plurality of alternative spatial patterns to be evaluated.

12. A computational system for summarizing a spatial pattern within an array of elements, wherein marked elements of said array designate said pattern and distances from marked elements to a convergence hub are combined into a distribution that provides a summary of said spatial pattern, comprising,

(a) a marker array that uses a coordinate system of addresses to specify the locations of said elements, provides a label to identify said spatial pattern, and designates said elements of said spatial pattern as marked elements,

(b) a polling mechanism for determining said addresses of said marked elements,

(c) a processor that receives said addresses and determines a distance value for every marked element from a convergence hub,

(d) a distributor that combines said set of distance values to form a distance distribution, said distance distribution having an abscissa scale and an ordinate scale, and

(e) a comparator that quantitatively evaluates said distance distribution in relation to a plurality of alternative distance distributions that were derived using said marker array, said polling mechanism, said processor, and said distributor, thereby providing summaries for a plurality of alternative spatial patterns, and a quantitative basis for judging correspondence of said spatial pattern to said alternative spatial patterns.

13. The system of claim 12, further including a computer and an instructional program for said computer for performing at least some of the operations performed by said marker array, said polling mechanism, said processor, and said distributor, whereby said computer can supplement or replace any or all computations.

14. The system of claim 12 wherein said convergence hub is at the center of said array, and said polling mechanism directly provides said distance value for every marked element, thereby eliminating the requirement for a processor.

15. The system of claim 12 wherein said processor is also arranged to use said address values to determine a centroid for said marked elements, and also to use said centroid as said convergence hub, such that said distance values are calculated in relation to said centroid, thereby providing a summary of said spatial pattern that is more useful.

16. The system of claim 12, further including a filter that uses said address values to specify a set of sectors within said array, each said sector being a subset of said elements of said array, and further deriving a set of sector distributions from within each of said sectors, thereby providing a set of partial summaries of said spatial pattern.

17. The system of claim 12 wherein said array contains a plurality of alternative patterns, and further including a plurality of alternative labels that distinguish said respective plurality of alternative patterns within said array, and a filter that can discriminate among said labels, thereby providing a plurality of distributions for said plurality of alternative patterns.

18. The system of claim 12, further including a storage component for storing a plurality of said distance distributions, thus facilitating said quantitative comparisons.

19. A system for summarizing a spatial pattern within an array of elements, wherein a subset of said elements in said array represents said spatial pattern, and said elements of said subset are designated as marked elements, and for incorporating the distances of said marked elements from a convergence hub into a distribution that provides a summary of said spatial pattern, comprising,

(a) array means for providing a an array of elements, said array means further including a labeling means for labeling a subset of said elements as constituting a spatial pattern, and designating said subset of elements as marked elements,

(b) means for providing a coordinate system of addresses for said marked elements,

(c) means for polling said marked elements to determine said addresses of said marked elements,

(d) means for specifying a location in said array as a convergence hub,

(e) means for determining a distance value for each marked element from said convergence hub,

(f) means for combining said distance values to form a distance distribution, said distance distribution having an abscissa scale and an ordinate scale,

(g) means for deriving a plurality of alternative distance distributions using said array, said addresses, said marked elements, said convergence hub, said means for determining said distance values of said marked element, and said means for combining said distance values, so that said plurality of alternative distance distributions provide summaries of said respective plurality of alternative spatial patterns, and

(h) means for quantitatively comparing said distribution with said plurality of alternative distance distributions,

whereby said comparison can be used to determine the degree of correspondence between said spatial pattern and said plurality of alternative spatial patterns.

20. The system of claim 19, further including means for determining a centroid for said marked elements and specifying said centroid as said convergence hub, thus providing the same said distance distribution irrespective of changes in location of said pattern.

21. The system of claim 19, further including means for selecting a plurality of additional convergence hubs and means for deriving said plurality of distance distributions from said plurality of additional convergence hubs, thereby providing summaries of said spatial pattern from more than one perspective.

22. The system of claim 19, further including a means for specifying a plurality of sectors, each said sector comprising a subset of said elements of said array, and means for deriving said plurality, of distance distributions from said sectors, thereby providing a set of partial summaries of said spatial pattern.

23. The system of claim 22, further including means for combining said plurality of distance distributions to provide a single distribution, thereby providing a more effective single summary of said spatial pattern.

24. The system of claim 22, further including means for providing a plurality of alternative patterns that are distinguished by a respective plurality of state levels, a set of quantitative scale values for labeling said state levels, and means for combining said scale values with said distance values into a single distribution, thus providing a summary of said alternative patterns as a single pattern mixture.

25. The system of claim 19, further including a second subset of said array of elements that represents a second spatial pattern, and further including determining said respective distance distributions for said elements of said second subset, thus providing a summary for a plurality of alternative patterns within said array.

26. The system of claim 19 wherein said distance distribution comprises ordinate and abscissa values and further including means for transforming said ordinate and abscissa values of said distance distribution to be proportional to said distance values, respectively, thus improving the comparison of said distance distribution with said alternative distance distributions.

27. The system of claim 19, further including means for comparing said distance distribution with said alternative distance distributions using a sum of squared differences or a Chi Square test, thereby facilitating judging the correspondence of said pattern to said alternative patterns.

28. A method for summarizing a spatial pattern within an array of elements wherein marked elements of said array designate said spatial pattern and distances from said marked elements to coordinate axes are combined into distributions that provides a summary of said spatial pattern, comprising,

(a) providing an array of elements and the locations of said elements in said array according to a coordinate address system, a subset of said array of elements having a state that represents said spatial pattern, providing a label for said state, and designating said elements of said subset as said marked elements,

(b) polling said elements of said array to determine a coordinate address of each of said marked elements, and designating these as marker addresses, each said marker address consisting of an X value and a Y value,

(c) a distributor for combining said X and Y values to form a plurality of component distributions, each said component distribution having an abscissa scale and an ordinate scale,

(d) combining said plurality of component distributions to form a summary distribution that represents said spatial pattern,

(e) a distribution comparator for deriving a plurality of alternative summary distributions by providing said array having said coordinate address system, said label for said state, said polling, said combining into component distributions, and said combining of said component distributions into said summary distribution, thereby providing a plurality of alternative summary distributions for said respective plurality of alternative spatial patterns, and

(f) quantitatively comparing said summary distribution with said plurality of alternative distributions,

whereby said quantitative comparison can be used to determine degree of correspondence between said spatial pattern and said plurality of alternative spatial patterns.

29. The method of claim 28, further including calculating a mean centroid address comprised of the means of said X and Y values, designating these as mean X and mean Y, adjusting each marker address by subtracting said mean X from each X value to obtain an X difference, subtracting said mean Y from each Y value to obtain a Y difference, designating said X and Y differences as centroid adjusted addresses, and proceeding with said steps (b) through step (f) using said centroid adjusted addresses in the place of the corresponding marker addresses, thereby providing a summary distribution with greater utility.

30. The method of claim 28, further sorting said X and Y components into a plurality of component sets, comprised of a +X set, a −

X set, a +Y set, and a −

Y set, and further deriving said plurality of component distributions from each said set, and further combining said plurality of component distributions into a summary distribution for said spatial pattern, thereby providing for effective comparison to said alternative summary distributions that were derived using the same method.

31. The method of claim 28, further including transforming said ordinate scale and said abscissa scale of said summary distribution, thus improving the comparison of said summary distribution with said alternative summary distributions.

32. The method of claim 28, wherein said quantitatively comparing said summary distribution to said plurality of alternative summary distributions is done by deriving a sum of squared differences value or a Chi Squared test value, thereby allowing correspondence of said spatial pattern to said plurality of alternative spatial patterns to be evaluated.