Method for characterizing dynamical systems

• US 5,712,801 A
• Filed: 09/25/1995
• Issued: 01/27/1998
• Est. Priority Date: 09/25/1995
• Status: Expired due to Term

• Current Assignee: Pacesetter Incorporated (Abbott Laboratories Incorporated)
• Original Assignee: Pacesetter Incorporated (Abbott Laboratories Incorporated)
• Inventors: Turcott, Robert
• Primary Examiner(s): Voeltz, Emanuel T.
• Assistant Examiner(s): PEESO, THOMAS R
• Application Number:
  US08/533,292
• Time in Patent Office: 855 Days
• Field of Search: 364/413.02, 364/413.05, 364/551.01, 364/550, 364/578, 395/924, 128/661.04, 128/700, 128/705
• US Class Current: 702/158
• CPC Class Codes: A61B 5/35 by template matching

Abstract

A method for characterizing the degree of similarity between phase space representations of trajectories of different dynamical systems. This method provides a computationally efficient technique for comparing different dynamical systems, or different dynamics exhibited by the same system. A first trajectory is designated as a template against which other trajectories are compared. A test trajectory is characterized by providing a measure based on determining the smallest distance between each point of the test trajectory to the template and then determining the largest of these smallest distances. The similarity of the two trajectories is quantified by establishing a lattice or grid for the phase space. For each lattice point, the distance, as given by a metric defined for the space, is calculated to the nearest point of the template trajectory. The minimum distance is retained and associated in a memory for each lattice point. The test trajectory is generated in the phase space with each data point of the test trajectory landing in a bin having a lattice point at its center. The previously determined shortest distance of that lattice point to the template trajectory is fetched from memory to provide an approximation of the closest distance of each point in the test trajectory to the template trajectory. The maximum of these distances among all points in the test trajectory serves as the distance between the two trajectories, and hence as a measure of degree of similarity between the two trajectories.

Claims

1. A method for characterizing a degree of similarity between phase space representations of trajectories arising from different dynamical systems comprising the steps of:

designating a first one of said trajectories as a template against which others of said trajectories are to be compared;

determining a measure of a shortest distance in phase space of each point of a second trajectory to said template trajectory; and

determining the largest of said shortest distances to provide a characterizing value.

2. The method of claim 1 wherein said step of determining a measure of a shortest distance comprises computing a square of a Euclidean norm in phase space.

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

obtaining a set of points in phase space generated by said template;

partitioning said phase space into a grid of bins;

determining a measure of a shortest distance of each bin to a closest point of said template and storing such measure for each bin in a memory; and

determining for each point of said phase space representation of said second trajectory the bin into which it falls and fetching from said memory the measure of said shortest distance for said bin;

wherein said step of determining a measure of a shortest distance includes to determining which of said bins each point of said second trajectory falls into and fetching from said memory the measure of said shortest distance for said bin.

4. The method of claim 3 and further including the step of setting to zero said measure for those points of said template trajectory which represent the least relevant system information.

5. The method of claim 1 wherein said phase space representations are generated by plotting a trajectory in an m-dimensional phase space from a sequence of samples {x_i } provided as amplitude data points of an electrogram by forming a sequence of vectors {x_j }={ x_j, x_j-l, . . . , x_j-(m-1)l !}, where l is a lag time.

6. A method for characterizing a degree of similarity between phase space representations of trajectories of different dynamical systems comprising the steps of:

designating a first trajectory as a template against which other trajectories are compared;

establishing a lattice for the phase space;

determining a measure of a distance from each lattice point to a closest point of said template trajectories and storing said measure in a memory;

determining a closest lattice point for each data point of a second trajectory and fetching said distance measure from said lattice point from said memory; and

determining a largest of said measures fetched from said memory to characterize said test trajectory.

7. The method of claim 6 wherein said step of determining a closest lattice point includes generating an m-dimensional bin around each of said lattice points and determining which of said bins each of said second trajectory data points falls into.

8. The method of claim 6 wherein said step of determining a measure of a distance from each lattice point includes the step of setting to zero said measure for those points of said template trajectory which represent the least relevant system information.

9. A system for characterizing a degree of similarity between phase space representations of trajectories arising from different dynamical systems comprising:

means for designating a first one of said trajectories as a template against which others of said trajectories are to be compared;

means for determining a measure of a shortest distance in phase space of each point of a second trajectory to said template trajectory; and

means for determining the largest of said shortest distances to provide a characterizing value.

10. A method for characterizing a degree of similarity between phase space representations of trajectories arising from different dynamics of a dynamical system comprising the steps of:

designating a first one of said trajectories as a template against which others of said trajectories are to be compared;

determining a measure of a shortest distance in phase space of each point of a second trajectory to said template trajectory; and

determining the largest of said shortest distances to provide a characterizing value.

11. The method of claim 10 wherein said step of determining a measure of a shortest distance comprises computing a square of a Euclidean norm in phase space.

12. The method of claim 10 further comprising the steps of:

obtaining a set of points in phase space generated by said template;

partitioning said phase space into a grid of bins;

determining a measure of a shortest distance of each bin to a closest point of said template and storing such measure for each bin in a memory; and

determining for each point of said phase space representation of said second trajectory the bin into which it falls and fetching from said memory the measure of said shortest distance for said bin;

wherein said step of determining a measure of a shortest distance includes determining which of said bins each point of said second trajectory falls into and fetching from said memory the measure of said shortest distance for said bin.

13. The method of claim 12 and further including the step of setting to zero said measure for those points of said template trajectory which represent the least relevant system information.

14. The method of claim 10 wherein said phase space representations are generated by plotting a trajectory in an m-dimensional phase space from a sequence of samples {x_i } provided as amplitude data points of an electrogram by forming a sequence vectors {x_j }={ x_j, x_j-l, . . . , x_j-(m-1)l !}, where l is a lag time.

15. A method for characterizing a degree of similarity between phase space representations of trajectories of different dynamics of a dynamical system comprising the steps of:

designating a first trajectory as a template against which other trajectories are compared;

establishing a lattice for the phase space;

determining a measure of a distance from each lattice point to a closest point of said template trajectory and storing said measure in a memory;

determining a closest lattice point for each data point of a second trajectory and fetching said distance measure from said lattice point from said memory; and

determining a largest of said measures fetched from said memory to characterize said test trajectory.

16. The method of claim 15 wherein said step of determining a closest lattice point includes generating an m-dimensional bin around each of said lattice points and determining which of said bins each of said second trajectory data points falls into.

17. The method of claim 15 wherein said step of determining a measure of a distance from each lattice point includes the step of setting to zero said measure for those points of said template trajectory which represent the least relevant system information.

18. A system for characterizing a degree of similarity between phase space representations of different trajectories of a given dynamical system comprising:

means for designating a first one of said trajectories as a template against which others of said trajectories are to be compared;

means for determining a measure of a shortest distance in phase space of each point of a second trajectory to said template trajectory; and

means for determining the largest of said shortest distances to provide a characterizing value.