Implantable medical device fast median filter

• US 6,941,332 B2
• Filed: 04/23/2002
• Issued: 09/06/2005
• Est. Priority Date: 04/23/2002
• Status: Expired due to Fees

• Current Assignee: Medtronic Incorporated (Medtronic Plc)
• Original Assignee: Medtronic Incorporated (Medtronic Plc)
• Inventors: Jensen, Steven L.
• Primary Examiner(s): MALZAHN, DAVID H
• Application Number:
  US10/128,021
• Publication Number:
  US 20030200242A1
• Time in Patent Office: 1,232 Days
• Field of Search: 708/304, 708/202
• US Class Current: 708/304
• CPC Class Codes: A61N 1/025 Digital circuitry features of electrotherapy devices, e.g. memory, clocks, processors
• CPC Class Codes: A61N 1/3605 Implantable neurostimulators for stimulating central or peripheral nerve system
• CPC Class Codes: A61N 1/37252 Details of algorithms or data aspects of communication system, e.g. handshaking, transmitting specific data or segmenting data
• CPC Class Codes: G16H 20/40 relating to mechanical, radiation or invasive therapies, e.g. surgery, laser therapy, dialysis or acupuncture
• CPC Class Codes: G16H 40/63 for local operation
• CPC Class Codes: G16Z 99/00 Subject matter not provided for in other main groups of this subclass

Abstract

A method for fast median filtering in an implantable medical device is disclosed that provides rapid filtering using computational mechanisms with following elements. A new sample value is received into a buffer. An oldest sample value location is identified in a MIN-heap and a MAX-heap. A new sample value location is identified in either the MIN-heap or the MAX-heap by comparing the new sample value to a median value. The new sample value is placed into the oldest sample value location, if the MIN-heap or MAX-heap identified for the new sample value location is the same as the MIN-heap or MAX-heap identified for the oldest sample value location. A MIN-heap top or MAX-heap top is moved from the heap not containing the oldest value into the location of the oldest sample and the new sample is placed into the location of the MIN-heap top or MAX-heap top moved from the heap not containing the oldest value, if the heap identified for the new sample is not the same as the heap identified for the oldest sample. The MAX-heap is rebalanced so the MAX-heap top contains the highest value in the MAX-heap and the MIN-heap is rebalanced so the MIN-heap top contains the lowest value in the MIN-heap. The median value is calculated by averaging the MIN-heap top plus the MAX-heap top. The method for fast median filtering in an implantable medical device can also be expressed as a computer software product that includes a medium readable by a processor.

Claims

1. A method for median filtering in an implantable medical device, comprising:

receiving a new sample value into a buffer;

identifying an oldest sample value location in a MIN-heap and a MAX-heap;

identifying a new sample value location in either the MIN-heap or the MAX-heap by comparing the new sample value to a median value;

placing the new sample value into the oldest sample value location, if the MIN-heap or MAX-heap identified for the new sample value location is the same as the MIN-heap or MAX-heap identified for the oldest sample value location;

moving a MIN-heap top or MAX-heap top from the heap not containing the oldest value into the location of the oldest sample and placing the new sample into the location of the MIN-heap top or MAX-heap top moved from the heap not containing the oldest value, if the heap identified for the new sample is not the same as the heap identified for the oldest sample;

rebalancing the MAX-heap so the MAX-heap top contains the highest value in the MAX-heap and rebalancing the MIN-heap so the MIN-heap top contains the lowest value in the MIN-heap; and

,

calculating the median value by averaging the MIN-heap top plus the MAX-heap top.

2. The method as in claim 1 wherein the MAX-heap and MIN-heap are binary heaps.

3. The method as in claim 1 wherein the time required to calculate the median value is expressed by the equation, O(2 log n/2) where O is on the order of time and n is the number of total samples.

4. The method as in claim 1 wherein the average running time to calculate the median value is expressed by the equation 1.5(log n/2) where n is the number of total samples.

5. The method as in claim 1 wherein the MAX-heap and MIN-heap are arranged in a single array with the MAX-heap occupying locations 1 through n/2 samples and MIN-heap occupying locations n/2+1 through n where n is the number of total samples.

6. The method as in claim 1 further comprising a First-In-First-Out (FIFO) array of n elements containing indexes that correspond to the MAX-heap and the MIN-heap where n is the number of total samples.

7. The method as in claim 1 further comprising an Index (IDX) array of n elements containing back pointer indexes to corresponding First-In-First-Out (FIFO) elements where n is the number of total samples.

8. A method for median filtering in an implantable medical device, comprising:

means for receiving a new sample value into a buffer;

means for identifying an oldest sample value location in a MIN-heap and a MAX-heap;

means for identifying a new sample value location in either the MIN-heap or the MAX-heap by comparing the new sample value to a median value;

means for placing the new sample value into the oldest sample value location, if the MIN-heap or MAX-heap identified for the new sample value location is the same as the MIN-heap or MAX-heap identified for the oldest sample value location;

means for moving a MIN-heap top or MAX-heap top from the heap not containing the oldest value into the location of the oldest sample and placing the new sample into the location of the MIN-heap top or MAX-heap top moved from the heap not containing the oldest value, if the heap identified for the new sample is not the same as the heap identified for the oldest sample;

means for rebalancing the MAX-heap so the MAX-heap top contains the highest value in the MAX-heap and rebalancing the MIN-heap so the MIN-heap top contains the lowest value in the MIN-heap; and

,

means for calculating the median value by averaging the MIN-heap top plus the MAX-heap top.

9. A computer software product that includes a medium readable by a processor, the medium having stored thereon instructions for median filtering in an implantable medical device, comprising:

a first sequence of instruction when executed by the processor, causes the processor to receive a new sample value into a buffer;

a second sequence of instruction when executed by the processor, causes the processor to identify an oldest sample value location in a MIN-heap and a MAX-heap;

a third sequence of instruction when executed by the processor, causes the processor to identify a new sample value location in either the MIN-heap or the MAX-heap by comparing the new sample value to a median value;

a forth sequence of instruction when executed by the processor, causes the processor to place the new sample value into the oldest sample value location, if the MIN-heap or MAX-heap identified for the new sample value location is the same as the MIN-heap or MAX-heap identified for the oldest sample value location;

a fifth sequence of instruction when executed by the processor, causes the processor to move a MIN-heap top or MAX-heap top from the heap not containing the oldest value into the location of the oldest sample and placing the new sample into the location of the MIN-heap top or MAX-heap top moved from the heap not containing the oldest value, if the heap identified for the new sample is not the same as the heap identified for the oldest sample;

a sixth sequence of instruction when executed by the processor, causes the processor to rebalance the MAX-heap so the MAX-heap top contains the highest value in the MAX-heap and rebalancing the MIN-heap so the MIN-heap top contains the lowest value in the MIN-heap; and

,

a seventh sequence of instruction when executed by the processor, causes the processor to calculate the median value by averaging the MIN-heap top plus the MAX-heap top.