Method of detecting, interpreting, recognizing, identifying and comparing n-dimensional shapes, partial shapes, embedded shapes and shape collages using multidimensional attractor tokens

• US 6,747,643 B2
• Filed: 09/27/2002
• Issued: 06/08/2004
• Est. Priority Date: 06/03/2002
• Status: Expired due to Fees

• Current Assignee: Omnikon Technologies Ltd.
• Original Assignee: Omnikon Technologies Ltd.
• Inventors: Happel, Kenneth M.
• Primary Examiner(s): Santiago, El
• Assistant Examiner(s): Santiago, Enrique L
• Application Number:
  US10/260,868
• Publication Number:
  US 20040037474A1
• Time in Patent Office: 620 Days
• Field of Search: 345/419, 345/420, 345/421, 345/422, 345/423, 345/424, 345/426, 345/427, 345/428, 345/586, 345/441, 345/467, 345/622, 382/159, 382/160, 382/165, 382/181, 382/187, 382/190, 382/191, 382/197, 382/199, 382/201, 382/203, 382/205, 382/206, 382/209, 382/216, 382/218, 382/219, 382/220, 382/221, 703/2
• US Class Current: 345/419
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06V 10/469 Contour-based spatial representations, e.g. vector-coding
• CPC Class Codes: G06V 10/752 Contour matching
• CPC Class Codes: G06V 10/754 involving a deformation of the sample pattern or of the reference pattern; Elastic matching
• CPC Class Codes: G06V 30/1985 Syntactic analysis, e.g. using a grammatical approach syntactic image representation G06V30/18171

Abstract

A method of detecting, interpreting, recognizing, identifying and comparing N-dimensional shapes, partial shapes, embedded shapes and shape collages is disclosed. One embodiment of the invention allows for the characterization of shapes as sequences of unit vector descriptions, attributes of unit vector descriptions, shape segments, and shape segment collages whereby the detection, interpretation, recognition, identification, comparison and analysis of one- to n-dimensional shapes in one- to n-dimensional spaces can be accomplished using multidimensional attractor tokens. These attractor processes map the sequence from its original sequence representation space (OSRS) into a hierarchical multidimensional attractor space (HMAS). The HMAS can be configured to represent equivalent symbol distributions within two symbol sequences or perform exact symbol sequence matching. The mapping process results in each sequence being drawn to an attractor in the HMAS. Each attractor within the HMAS forms a unique token for a group of sequences with no overlap between the sequence groups represented by different attractors. The size of the sequence groups represented by a given attractor can be reduced from approximately half of all possible sequences to a much smaller subset of possible sequences. The mapping process is repeated for a given sequence so that tokens are created for the whole sequence and a series of subsequences created by repeatedly removing a symbol from the one end of sequence and then repeating the process from the other end. The resulting string of tokens represents the exact identity of the whole sequence and all its subsequences ordered from each end.

Claims

1. A method for characterizing an m-dimensional shape in an n-dimensional space, comprising the steps of:

a) configuring a device in at least one of hardware, firmware and software to characterize said m-dimensional shape, said configuring comprising;

defining labels for a plurality of facial directions of a polytope in said n-dimensional space, said polytope being of k dimensions;

defining a unit vector for each of said facial directions; and

defining a polytope tiling map for said n-dimensional space;

b) tiling said m-dimensional shape with said k-dimensional polytope within said n-dimensional space;

c) mapping a shape into a sequence of tile addresses;

d) configuring said device to carry out an attractor process for mapping a source multiset to an attractor space, said attractor process being an iterative process which causes elements in said source multiset to converge on one of at least two different behaviors defined within said attractor space as a result of said iterative process, said configuring step including inputting a characterization of the source multiset to input to said device the number of distinct elements of said source multiset;

e) using said device, executing said mapping of said sequence of tile addresses to one or more coordinates of said attractor space, each of said coordinates corresponding to a different behavior in the attractor space; and

f) mapping said attractor space coordinates into a target space representation, said target space representation including at least the attractor space coordinates.

2. The method of claim 1 wherein said target space and said attractor space are collapsed onto a single space.

3. The method of claim 1 further comprising the step of:

g) mapping said target space representation into a shape analytical space representation; and

h) comparing said shape analytical space representation with one or more stored shape representations.

4. The method of claim 3 wherein two or more of said target space, said analytic space and said attractor space are collapsed onto a single space.

5. The method of claim 1 wherein said domain space is of two dimensions.

6. The method of claim 5 wherein polytope is a triangle.

7. The method of claim 5 wherein polytope is a hexagon.

8. The method of claim 5 wherein polytope is a square.

9. The method of claim 1 wherein said polytope has (2n−

2) faces.

10. The method of claim 1 wherein m equals one, n is two or more, and k is two or more.

11. The method of claim 1 wherein m equals two, n is two or more, and k is two or more.

12. The method of claim 1 wherein m equals one or more, n is equal to or greater than m, and k is two or more.

13. The method of claim 1 wherein m equals one or more, n is equal to or less than m, and k is two or more.

14. A method for characterizing an m-dimensional shape in an n-dimensional space, comprising the steps of:

a) configuring a device in at least one of hardware, firmware and software to characterize said m-dimensional shape, said configuring comprising;

defining labels for a plurality of facial directions of a polytope in said n-dimensional space, said polytope being of k dimensions;

defining a unit vector for each of said facial directions;

defining a polytope tiling map for said n-dimensional space; and

defining labels for a plurality of angle types between two or more combinations of said unit vectors;

b) tiling said m-dimensional shape with said k-dimensional polytope within said n-dimensional space;

c) mapping a shape into a sequence of angle types;

d) configuring said device to carry out an attractor process for mapping a source multiset to an attractor space, said attractor process being an iterative process which causes elements in said source multiset to converge on one of at least two different behaviors defined within said attractor space as a result of said iterative process, said configuring step including inputting a characterization of the source multiset to input to said device the number of distinct elements of said source multiset;

e) using said device, executing said mapping of said sequence of tile addresses to one or more coordinates of said attractor space, each of said coordinates corresponding to a different behavior in the attractor space; and

f) mapping said attractor space coordinates into a target space representation, said target space representation including at least the attractor space coordinates.

15. The method of claim 14 wherein said target space and said attractor space are collapsed onto a single space.

16. The method of claim 14 further comprising the step of:

g) mapping said target space representation into a shape analytical space representation; and

h) comparing said shape analytical space representation with one or more stored shape representations.

17. The method of claim 16 wherein two or more of said target space, said analytic space and said attractor space are collapsed onto a single space.

18. The method of claim 14 wherein said domain space is of two dimensions.

19. The method of claim 18 wherein polytope is a triangle.

20. The method of claim 18 wherein polytope is a hexagon.

21. The method of claim 18 wherein polytope is a square.

22. The method of claim 14 wherein said polytope has (2n−

2) faces.

23. A method for characterizing an m-dimensional shape in an n-dimensional space, comprising the steps of:

a) placing a k-dimensional polytope on a starting point of the m-dimensional shape, said shape being a contour, said polytope having a plurality of faces, each of said faces being associated with an address label;

b) determining an intersecting face of said polytope intersecting with said shape at an intersecting point;

c) adding a label corresponding to said intersecting face to a sequence of address labels;

d) centering said polytope at said intersecting point;

e) determining an intersecting face of said polytope intersecting with said shape at an intersecting point;

f) adding a label corresponding to said intersecting face to a sequence of address labels;

g) repeating steps d) to f) until the entire shape has been addressed, thereby providing a sequence of addresses; and

h) processing said sequence of addresses through an attractor process to obtain a string of one or more tokens, said tokens being indicative of attractor process states resulting from interaction of said attractor process with said sequence.

24. The method of claim 23, further comprising the steps of:

i) repeating steps a) through h) for a second m-dimensional shape to obtain a second string of tokens; and

j) comparing said string of tokens for first shape with said second string of tokens for said second shape.

25. The method of claim 23, wherein said attractor process is an iterative process which causes elements in a source multiset to converge on one of at least two different behaviors defined within an attractor space as a result of an iterative process.

26. The method of claim 23, wherein said processing said sequence of addresses through an attractor process includes taking said labels in said sequence one at a time.

27. The method of claim 23, wherein said processing said sequence of addresses through an attractor process includes taking said labels in said sequence more than one at a time.

28. The method of claim 23, wherein said processing said sequence of addresses through an attractor process includes inserting new labels for one or more predetermined features in said sequence.

29. The method of claim 28, wherein said predetermined features include concave regions and convex regions.

30. The method of claim 28, wherein said predetermined features include turns from each of said faces of said polytope to all other faces of said polytope.

31. The method according to claim 23, further comprising the step of:

generating one or more additional sequences by defining one or more additional labels, each of said additional labels corresponding to a predetermined feature of said shape.

32. The method according to claim 31, wherein said feature includes a shape segment, said segment having a plurality of identical labels.

33. The method according to claim 31, wherein said feature includes a turn from one address label to another address label.

34. The method according to claim 23, further comprising the step of:

normalizing a scalar size of said polytope.

35. The method according to claim 23, further comprising the step of:

normalizing an orientation of said polytope.

36. A method for analyzing an m-dimensional shape in an n-dimensional space, comprising the steps of:

a) placing a k-dimensional polytope on a starting point of the m-dimensional shape, said shape being a contour, said polytope having a plurality of faces, each of said faces being associated with an address label;

b) determining an intersecting face of said polytope intersecting with said shape at an intersecting point;

c) adding a label corresponding to said intersecting face to a sequence of address labels;

d) centering said polytope at said intersecting point;

e) determining an intersecting face of said polytope intersecting with said shape at an intersecting point;

f) adding a label corresponding to said intersecting face to a sequence of address labels;

g) repeating steps d) to f) until the entire shape has been addressed, thereby providing a sequence of addresses; and

h) processing said sequence of addresses through an attractor process to obtain one or more tokens, said tokens being indicative of attractor process states resulting from interaction of said attractor process with said sequence; and

i) analyzing said tokens to recognize or compare said shape with a set of predetermined shapes.

37. A method for characterizing an m-dimensional shape in an n-dimensional space, comprising the steps of:

a) placing a pre-determined point of a k-dimensional polytope on a starting point at an edge of the m-dimensional shape, said polytope having a plurality of faces (k) and a reference point, each of said faces being associated with an address label;

b) orienting said polytope to place said reference point of said polytope on said edge of said shape

c) determining an intersecting face of said polytope intersecting with said edge of said shape at an intersecting point;

d) adding a label corresponding to said intersecting face to a sequence of address labels;

e) centering said polytope at said intersecting point;

f) repeating steps b) to e) until the entire shape has been addressed, thereby providing a sequence of addresses; and

g) processing said sequence of addresses through an attractor to obtain a string of one or more tokens, said tokens being indicative of attractor states resulting from said sequence.

38. The method of claim 37, further comprising the steps of:

h) repeating steps a) through g) for a second m-dimensional shape to obtain a second string of tokens; and

i) comparing said string of tokens for first shape with said second string of tokens for said second shape.

39. The method of claim 37, wherein said attractor process is an iterative process which causes elements in a source multiset to converge on one of at least two different behaviors defined within an attractor space as a result of an iterative process.

40. The method of claim 37, wherein said processing said sequence of addresses through an attractor process includes taking said labels in said sequence one at a time.

41. The method of claim 37, wherein said processing said sequence of addresses through an attractor process includes taking said labels in said sequence more than one at a time.

42. The method of claim 37, wherein said processing said sequence of addresses through an attractor process includes inserting new labels for one or more predetermined features in said sequence.

43. The method of claim 42, wherein said predetermined features include concave regions and convex regions.

44. The method of claim 42, wherein said predetermined features include turns from each of said faces of said polytope to all other faces of said polytope.

45. The method according to claim 37, further comprising the step of:

generating one or more additional sequences by defining one or more additional labels, each of said additional labels corresponding to a predetermined feature of said shape.

46. The method according to claim 45, wherein said feature includes a shape segment, said segment having a plurality of identical labels.

47. The method according to claim 45, wherein said feature includes a turn from one address label to another address label.

48. The method according to claim 37, further comprising the step of:

normalizing a scalar size of said polytope.

49. The method according to claim 37, further comprising the step of:

normalizing an orientation of said polytope.

50. A method for analyzing an m-dimensional shape in an n-dimensional space, comprising the steps of:

a) placing a pre-determined point of a k-dimensional polytope on a starting point at an edge of the m-dimensional shape, said polytope having a plurality of faces (k) and a reference point, each of said faces being associated with an address label;

b) orienting said polytope to place said reference point of said polytope on said edge of said shape

c) determining an intersecting face of said polytope intersecting with said edge of said shape at an intersecting point;

d) adding a label corresponding to said intersecting face to a sequence of address labels;

e) centering said polytope at said intersecting point;

f) repeating steps b) to e) until the entire shape has been addressed, thereby providing a sequence of addresses;

g) processing said sequence of addresses through an attractor to obtain one or more tokens, said tokens being indicative of attractor states resulting from said sequence; and

h) analyzing said tokens to recognize or compare said shape with a set of predetermined shapes.

51. A device for analyzing an m-dimensional shape in an n-dimensional space, comprising:

a) means for placing a pre-determined point of a k-dimensional polytope on a starting point at an edge of the m-dimensional shape, said polytope having a plurality of faces (k) and a reference point, each of said faces being associated with an address label;

b) means for orienting said polytope to place said reference point of said polytope on said edge of said shape

c) means for determining an intersecting face of said polytope intersecting with said edge of said shape at an intersecting point;

d) means for adding a label corresponding to said intersecting face to a sequence of address labels;

e) means for centering said polytope at said intersecting point;

f) means for repeating steps b) to e) until the entire shape has been addressed, thereby providing a sequence of addresses;

g) means for processing said sequence of addresses through an attractor to obtain one or more tokens, said tokens being indicative of attractor states resulting from said sequence; and

h) means for analyzing said tokens to recognize or compare said shape with a set of predetermined shapes.

52. A device for analyzing an m-dimensional shape in an n-dimensional space, comprising a programmed digital computer programmed to perform the steps of:

a) placing a pre-determined point of a k-dimensional polytope on a starting point at an edge of the m-dimensional shape, said polytope having a plurality of faces (k) and a reference point, each of said faces being associated with an address label;

b) orienting said polytope to place said reference point of said polytope on said edge of said shape

c) determining an intersecting face of said polytope intersecting with said edge of said shape at an intersecting point;

d) adding a label corresponding to said intersecting face to a sequence of address labels;

e) centering said polytope at said intersecting point;

f) repeating steps b) to e) until the entire shape has been addressed, thereby providing a sequence of addresses;

g) processing said sequence of addresses through an attractor to obtain one or more tokens, said tokens being indicative of attractor states resulting from said sequence; and

h) analyzing said tokens to recognize or compare said shape with a set of predetermined shapes.