Method for solving waveform sequence-matching problems using multidimensional attractor tokens

• US 20070093942A1
• Filed: 07/11/2006
• Published: 04/26/2007
• Est. Priority Date: 06/03/2002
• Status: Abandoned Application

• Current Assignee: Omnikon Technologies Ltd.
• Original Assignee: Omnikon Technologies Ltd.
• Inventors: Happel, Kenneth
• Application Number:
  US11/485,073
• Publication Number:
  US 20070093942A1
• Time in Patent Office: Days
• US Class Current: 700/294
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 2218/08 Feature extraction
• CPC Class Codes: G06F 2218/12 Classification; Matching
• CPC Class Codes: G06V 10/469 Contour-based spatial representations, e.g. vector-coding
• CPC Class Codes: G06V 30/1985 Syntactic analysis, e.g. using a grammatical approach syntactic image representation G06V30/18171
• CPC Class Codes: G16B 30/00 ICT specially adapted for sequence analysis involving nucleotides or amino acids
• CPC Class Codes: G16B 30/20 Sequence assembly

Abstract

An improved method is provided for solving waveform description, matching and comparison problems using attractor-based processes to extract identity tokens that indicate sequence and subsequence symbol content and order of the waveform or waveform segments. The waveform is described with a suitable alphabet to extract the ontology of the waveform, and syntactical rules are applied to direct pattern extraction using the alphabet. The patterns are extracted in a hierarchical, embedded manner according the global or local maximia and minimia so that the resulting statements are compatible with analysis in catastrophe theory. The attractor processes map the resulting waveform 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 or group of symbols 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 of waveform comparison comprising:

(a) mapping, through an attractor process, at least first and second waveform sequence source multisets, from an original representation space (ORS) into an attractor behavior space;

(i) each of said at least first and second waveform sequence source multisets being a plurality of subsets of a first and second waveform sequence and each subset having a plurality of waveform sequence elements;

(ii) said attractor process being an iterative process which causes first and second waveform sequences source multisets in the ORS to converge to at least two distinct behaviors in said attractor behavior space;

(iii) wherein each behavior in said attractor behavior space is assigned a distinct symbol from a symbol scheme,

(iv) said mapping resulting in a first and second token string, each consisting of a series of said symbols, corresponding to said first and second waveform sequence source multisets respectively;

(b) mapping, through said attractor process and into said attractor behavior space, a plurality of first and second waveform subsequences source multisets of said first and second waveform sequences respectively,

(i) said plurality of first and second waveform subsequence source multisets each being a plurality of subsets of a different one of a plurality of first and second waveform subsequence of said first and second waveform sequence and each having a number of waveform sequence elements;

(ii) said mapping resulting in a plurality of first and second subsequence token strings, each consisting of a series of said symbols, corresponding to said plurality of first and second waveform subsequence source multisets respectively; and

(c) comparing said first token string and said plurality of first subsequence token strings with said second token string and said plurality of second subsequence token strings to determine a match among said first and second waveform sequence source multisets and said plurality of first and second waveform subsequences source multisets.

2. The method as recited in claim 1 further including the step of forming said at least first and second waveform sequence source multisets by, for each of said first and second waveform sequences:

(a) removing j sequence elements, where j is an integer initially equal to one, from one end of said waveform sequence;

(b) iteratively repeating step (a) at least once for j=j+1 at each iteration, and at most for j equal to the number of sequence elements in said waveform sequence.

3. The method as recited in claim 2 further including the step of forming said at least first and second waveform sequence source multisets by, for each of said first and second waveform sequences:

(c) removing k sequence elements, where k is an integer initially equal to one, from the other end of said waveform sequence; and

(d) iteratively repeating step (c) at least once for k=k+1 at each iteration, and at most for k equal to the number of sequence elements in said waveform sequence.

4. The method as recited in claim 3 further including the step of forming said at least first and second waveform subsequence source multisets by, for each of said plurality of first and second waveform subsequences:

(e) removing j sequence elements, where j is an integer initially equal to one, from one end of said waveform subsequence;

(f) iteratively repeating step (e) at least once for j=j+1 at each iteration, and at most for j equal to the number of sequence elements in said waveform subsequence.

5. The method as recited in claim 4 further including the step of forming said at least first and second waveform subsequence source multisets by for each of said plurality of first and second waveform subsequences:

(g) removing k sequence elements, where k is an integer initially equal to one, from the other end of said waveform subsequence; and

(h) iteratively repeating step (g) at least once for k=k+1 at each iteration, and at most for k equal to the number of sequence elements in said waveform subsequence.

6. The method as recited in claim 1 wherein said mapping of said at least first and second waveform sequence source multisets is performed taking said sequence elements of each of said subsets of each of said first and second waveform sequence source multisets one-at-a-time and mapping the resulting one-at-a-time elements through said attractor process to form one-at-a-time tokens, sequences of said one-at-a-time tokens forming at least portions of said first and second token strings.

7. The method as recited in claim 1 wherein said mapping of said at least first and second waveform sequence source multisets is performed taking said sequence elements of each of said subsets of each of said first and second waveform sequence source multisets two-at-a-time and mapping the resulting two-at-a-time elements through said attractor process to form two-at-a-time tokens, sequences of said two-at-a-time tokens forming at least portions of said first and second token strings.

8. The method as recited in claim 1 wherein said mapping of said at least first and second waveform sequence source multisets is performed taking said sequence elements of each of said subsets of each of said first and second waveform sequence source multisets three-at-a-time and mapping the resulting three-at-a-time elements through said attractor process to form three-at-a-time tokens, sequences of said three-at-a-time tokens forming at least portions of said first and second token strings.

9. The method as recited in claim 6 wherein said mapping of said at least first and second waveform sequence source multisets is performed taking said sequence elements of each of said subsets of each of said first and second waveform sequence source multisets two-at-a-time and mapping the resulting two-at-a-time elements through said attractor process to form two-at-a-time tokens, sequences of said two-at-a-time tokens together with said one-at-a-time tokens forming at least portions of said first and second token strings.

10. The method as recited in claim 9 wherein said mapping of said at least first and second waveform sequence source multisets is performed taking said sequence elements of each of said subsets of each of said first and second waveform sequence source multisets three-at-a-time and mapping the resulting three-at-a-time elements through said attractor process to form three-at-a-time tokens, sequences of said three-at-a-time tokens, together with said two-at-a-time tokens and said one-at-a-time tokens forming at least portions of said first and second token strings.

11. The method as recited in claim 1 wherein said mapping of each of said plurality of first and second waveform subsequence source multisets is performed taking said sequence elements of each of said subsets of each of said plurality of first and second waveform subsequence source multisets one-at-a-time and mapping the resulting one-at-a-time elements through said attractor process to form one-at-a-time tokens, sequences of said one-at-a-time tokens forming at least portions of said plurality of first and second subsequence token strings.

12. The method as recited in claim 1 wherein said mapping of each of said plurality of first and second waveform subsequence source multisets is performed taking said sequence elements of each of said subsets of each of said plurality of first and second waveform subsequence source multisets two-at-a-time and mapping the resulting two-at-a-time elements through said attractor process to form two-at-a-time tokens, sequences of said two-at-a-time tokens forming at least portions of said plurality of first and second subsequence token strings.

13. The method as recited in claim 1 wherein said mapping of each of said plurality of first and second waveform subsequence source multisets is performed taking said sequence elements of each of said subsets of each of said plurality of first and second waveform subsequence source multisets three-at-a-time and mapping the resulting three-at-a-time elements through said attractor process to form three-at-a-time tokens, sequences of said three-at-a-time tokens forming at least portions of said plurality of first and second subsequence token strings.

14. The method as recited in claim 11 wherein said mapping of each of said plurality of first and second waveform subsequence source multisets is performed taking said sequence elements of each of said subsets of each of said plurality of first and second waveform subsequence source multisets two-at-a-time and mapping the resulting two-at-a-time elements through said attractor process to form two-at-a-time tokens, sequences of said two-at-a-time tokens forming, together with said one-at-a-time tokens, at least portions of said plurality of first and second subsequence token strings.

15. The method as recited in claim 14 wherein said mapping of each of said plurality of first and second waveform subsequence source multisets is performed taking said sequence elements of each of said subsets of each of said plurality of first and second waveform subsequence source multisets three-at-a-time and mapping the resulting three-at-a-time elements through said attractor process to form three-at-a-time tokens, sequences of said three-at-a-time tokens forming, together with said one-at-a-time tokens and said two-at-a-time tokens, at least portions of said plurality of first and second subsequence token strings.

16. The method as recited in claim 1 wherein said waveform sequence elements of each subset of each of said first and second waveform sequence source multisets is assigned using FIG. 10.

17. The method as recited in claim 1 wherein said waveform sequence elements of each subset of each of said first and second waveform sequence source multisets are derived by:

(a) representing a waveform of interest as a series of discrete points, each point having an amplitude value;

(b) assigning an alphabet symbol from an alphabet characterized by describing, for a given discrete point, the relative amplitude value of a point to the right and left of the given point such that the local shape of the waveform may be described relative to the given point.

18. The method as recited in claim 17 wherein the alphabet comprises the alphabet shown in FIG. 10.

19. The method as recited in claim 17 wherein said waveform comprises a plurality of waveform segments and each waveform segment is defined by a group of said waveform sequence elements, said mapping in steps (a) and (b) and said comparing in step (c) taking place individually for each of said waveform segments:

20. The method as recited in claim 19 wherein the alphabet comprises right and left terminator points for describing the right and left end points respectively of each segment, said terminator point indicating whether the segment is part of an interior region of a waveform or a beginning or end portion of a waveform.

21. The method as recited in claim 1 wherein said waveform sequence elements of each subset of each of said first and second waveform sequence source multisets are derived by:

(a) representing a first and second waveform of interest as a series of discrete points, each point having an amplitude value;

(b) defining each of said first and second waveforms between right and left terminator points, said terminator points having amplitude values;

(c) selecting, for each of said first and second waveforms, the global maximum and global minimum points according to their amplitude values, said global maximum and global minimum selected between said right and left terminator points;

(d) assigning an alphabet symbol to represent the selected global maximum, global minimum and terminator points, said alphabet symbol assigned to characterize said points based on amplitude values of adjacent ones of said global maximum, global minimum and terminator points, while ignoring all other points;

(e) dividing each of said first and second waveforms into regions according to the respective selected global maximum and global minimum points and the terminator points;

(f) within each region, selecting a local maximum and minimum points according to their amplitude values;

(g) within each region and for each of said first and second waveforms, assigning an alphabet symbol to represent the selected local maximum and local minimum points, said symbol assigned to characterize said local maximum and local minimum points based on amplitude values of adjacent ones of said local maximum, said local minimum, said global maximum, said global minimum, and said terminator points, if any, while ignoring all other points; and

(h) forming said first and second waveform sequence by combining said alphabet symbols assigned in steps (d) and (g).

22. The method as recited in claim 1 wherein said waveform sequence elements of each subset of each of said first and second waveform sequence source multisets are derived by:

(a) representing a first and second waveform of interest as a series of discrete points, each point having an amplitude value;

(b) defining each of said first and second waveforms between right and left terminator points, said terminator points having amplitude values;

(c) selecting, for each of said first and second waveforms, the global maximum and global minimum points according to their amplitude values, said global maximum and global minimum selected between said right and left terminator points;

(d) assigning an alphabet symbol to represent the selected global maximum, global minimum and terminator points, said alphabet symbol assigned to characterize said points based on amplitude values of adjacent ones of said global maximum, global minimum and terminator points, while ignoring all other points;

(e) dividing each of said first and second waveforms into regions according to the respective selected global maximum and global minimum points and the terminator points;

(f) selecting, for each of said first and second waveforms, the next global maximum and next global minimum points according to their amplitude values;

(g) assigning an alphabet symbol to represent the selected next global maximum and next global minimum points, said alphabet symbol assigned to characterize said points based on amplitude values of adjacent ones of said next global maximum, said next global minimum, said global maximum, said global minimum, and said terminator points, if any, while ignoring all other points; and

(h) forming a first sequence of symbols by combining the symbols assigned in steps (d) and (g).

23. A method of waveform comparison comprising:

(a) mapping, through an attractor process, a first waveform sequence source multiset, from an original representation space (ORS) into an attractor behavior space;

(i) said first waveform sequence source multisets being a plurality of subsets of a first waveform sequence and each subset having a plurality of waveform sequence elements;

(ii) said attractor process being an iterative and contractive process which causes first waveform sequences source multisets in the ORS to converge to at least two distinct behaviors in said attractor behavior space;

(iii) wherein each behavior in said attractor behavior space is assigned a distinct symbol from a symbol scheme,

(iv) said mapping resulting in a first token string consisting of a series of said symbols, corresponding to said first waveform sequence source multisets respectively;

(b) mapping, through said attractor process and into said attractor behavior space, a plurality of first waveform subsequences source multisets of said first waveform sequences respectively,

(i) said plurality of first waveform subsequence source multisets being a plurality of subsets of a different one of a plurality of a first waveform subsequence of said first waveform sequence and each having a number of waveform sequence elements;

(ii) said mapping resulting in a plurality of first subsequence token strings, each consisting of a series of said symbols, corresponding to said plurality of first waveform subsequence source multisets respectively; and

(c) mapping, through an attractor process, a second waveform sequence source multiset, from an original representation space (ORS) into an attractor behavior space;

(i) said second waveform sequence source multisets being a plurality of subsets of a second waveform sequence and each subset having a plurality of waveform sequence elements;

(ii) said attractor process being an iterative and contractive process which causes second waveform sequences source multisets in the ORS to converge to at least two distinct behaviors in said attractor behavior space;

(iii) wherein each behavior in said attractor behavior space is assigned a distinct symbol from said symbol scheme,

(iv) said mapping resulting in a second token string consisting of a series of said symbols, corresponding to said second waveform sequence source multisets respectively;

(d) mapping, through said attractor process and into said attractor behavior space, a plurality of second waveform subsequences source multisets of said second waveform sequences respectively,

(i) said plurality of second waveform subsequence source multisets being a plurality of subsets of a different one of a plurality of a second waveform subsequence of said second waveform sequence and each having a number of waveform sequence elements;

(ii) said mapping resulting in a plurality of second subsequence token strings, each consisting of a series of said symbols, corresponding to said plurality of second waveform subsequence source multisets respectively; and

(e) comparing said first token string and said plurality of first subsequence token strings with said second token string and said plurality of second subsequence token strings respectively to determine a match among said first and second waveform sequence source multisets and said plurality of first and second waveform subsequences source multisets.

24. A method of waveform comparison comprising:

(a) representing a first waveform as a first series of discrete points, each point having a value, a first waveform sequence source multiset being at least a portion of said first series of discrete points and a plurality of subsets of said portion of said first series of discrete points, and each subset having a plurality of said discrete points as waveform sequence elements;

(i) mapping, through an iterative and contractive process, said first waveform sequence source multiset into an attractor behavior space having at least two distinct behaviors with each behavior assigned a distinct symbol;

(ii) said mapping resulting in a first token string consisting of a series of said symbols, corresponding to said first waveform sequence source multisets;

(b) representing a second waveform as a second series of discrete points, each point having a value, a second waveform sequence source multiset being at least a portion of said second series of discrete points and a plurality of subsets of said portion of said second series of discrete points, and each subset having a plurality of said discrete points as waveform sequence elements;

(i) mapping, through said iterative and contractive process, said second waveform sequence source multiset into said attractor behavior space;

(ii) said mapping resulting in a second token string consisting of a series of said symbols, corresponding to said second waveform sequence source multisets;

(c) comparing said first token string and with said second token string to determine a match among said first and second waveform sequence source multisets.

25. The method as recited in claim 24 further comprising:

(a) mapping, through said iterative and contractive process into said attractor behavior space, a plurality of first waveform subsequences source multisets of said first waveform sequences respectively,

(i) said plurality of first waveform subsequence source multisets being a plurality of subsequences of said first series of discrete points and, for each subsequence, a plurality of subsets said first series of discrete points which belong so said subsequences, each subset having a plurality of said discrete points as waveform sequence elements

(ii) said mapping resulting in a plurality of first subsequence token strings, each consisting of a series of said symbols, corresponding to said plurality of first waveform subsequence source multisets respectively;

(b) mapping, through said iterative and contractive process into said attractor behavior space, a plurality of second waveform subsequences source multisets of said second waveform sequences respectively,

(i) said plurality of second waveform subsequence source multisets being a plurality of subsequences of said second series of discrete points and, for each subsequence, a plurality of subsets of said second series of discrete points which belong so said subsequences, each subset having a plurality of said discrete points as waveform sequence elements

(ii) said mapping resulting in a plurality of second subsequence token strings, each consisting of a series of said symbols, corresponding to said plurality of second waveform subsequence source multisets respectively;

(c) comparing said first token string and said plurality of first subsequence token strings with said second token string and said plurality of second subsequence token strings respectively to determine a match among said first and second waveform sequence source multisets and said plurality of first and second waveform subsequences source multisets.

26. The method as recited in claim 25 further including the step of forming said at least first and second waveform sequence source multisets by, for each of said first and second waveforms s:

(a) removing j sequence elements, where j is an integer initially equal to one, from one end of said waveform sequence;

(b) iteratively repeating step (a) at least once for j=j+1 at each iteration, and at most for j equal to the number of sequence elements in said waveform.

27. The method as recited in claim 26 further including the step of forming said at least first and second waveform subsequence source multisets by, for each of said plurality of first and second waveform subsequences:

(a) removing j sequence elements, where j is an integer initially equal to one, from one end of said waveform subsequence;

(b) iteratively repeating step (e) at least once for j=j+1 at each iteration, and at most for j equal to the number of sequence elements in said waveform subsequence.

28. The method as recited in claim 24 further including the step of forming said at least first and second waveform sequence source multisets by, for each of said first and second waveforms s:

(a) removing j sequence elements, where j is an integer initially equal to one, from one end of said waveform sequence;

(b) iteratively repeating step (a) at least once for j=j+1 at each iteration, and at most for j equal to the number of sequence elements in said waveform.

29. A method of comparing at least a first and second waveform comprising the steps of:

(a) representing the first waveform as a series of discrete points;

(b) setting k initially equal to “

first”

where k is an ordinal number;

(c) selecting a k plurality of points based on a k resolution examination of said series of discrete points;

(d) assigning symbols from an alphabet of symbols to represent the k plurality of points at said k resolution examination;

(e) incrementing k such that k=k+1;

(f) repeating steps (c) and (d) at least once;

(g) forming a sequence of symbols by combining the assigned symbols formed in steps (d);

(h) mapping said sequence with an iterative, contractive process which causes said sequence to converge on one of at least two different behaviors, and assigning a first token indicative of said behavior;

(i) representing the second waveform as a series of discrete points;

(j) setting m initially equal to “

first”

where m is an ordinal number;

(k) selecting a m plurality of points based on a m resolution examination of said series of discrete points;

(l) assigning symbols from said alphabet of symbols to represent the m plurality of points at said m resolution examination;

(m) incrementing m such that m=m+1;

(n) repeating steps (k) and (l) at least once;

(o) forming a sequence of symbols by combining the assigned symbols formed in steps (l);

(p) mapping said sequence with an iterative, contractive process which causes said sequence to converge on one of at least two different behaviors, and assigning a second token indicative of said behavior;

(q) comparing said first and second waveforms by comparing the first and second tokens.

30. The method as recited in claim 29 wherein said selecting steps (c) and (k) are performed by selecting successive maxima and minima points at each iteration of steps (f) and (n) respectively.