Pulse analysis using ordinal value filtering

• US 5,917,733 A
• Filed: 06/30/1995
• Issued: 06/29/1999
• Est. Priority Date: 01/16/1993
• Status: Expired due to Fees

• Current Assignee: Cambridge Solutions Limited (DXC Technology Company)
• Original Assignee: Cambridge Solutions Limited (DXC Technology Company)
• Inventors: Bangham, James Andrew
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US08/492,031
• Time in Patent Office: 1,460 Days
• Field of Search: 364/724.01, 364/724.16, 364/724.17, 364/715.06, 382/262, 382/218
• US Class Current: 708/300
• CPC Class Codes: H03H 17/0263 Rank order filters

Abstract

An image and pulse analysis system and method including a datasieve comprising a succession of ordinal filtering means receiving at least a selected part of a signal conglomerate and filtering the at least a selected part of the signal conglomerate to produce a bandpass filter output, the ordinal filtering means having window lengths increasing from N (less than M) up to M, whereby an input signal to each successive filtering means is formed from the output of the previous filtering means; selection means for selecting a predetermined subset of bandpass filter outputs from outputs of the succession of filtering means; and arithmetic means for adding together the signals of the subset to produce an output signal containing only wanted signals determined by the selection means; data storage means for storing data relating to a sought-for-feature or object which may exist in a field from which data is derived for presenting to the datasieve; comparison means for matching or comparing the stored data with the output signal of the datasieve; and selection means to select from the input signal only data having a high degree of match to the data in the data storage means.

Claims

1. A method of pulse analysis applied to a signal conglomerate represented as a set of data samples in order to remove unwanted signals from wanted signals, comprising the following steps of:

a) ordinal value filtering at least a selected part of the signal conglomerate with a succession of filters of window sizes increasing from N (being less than M) up to M, an input to each successive filter being formed from an output of a previous filter;

b) subtracting a current filter output from the previous filter output for said succession of filters to obtain bandpass outputs, known as granularities, consisting of strings of data points which contain strings of zero-valued data points, known as zero segments, and strings of non-zero-valued data points, known as non-zero segments or granules;

c) selecting a subset of the granularities; and

d) adding together granularities within said subset to produce an output signal containing the granules in said subset.

2. A method according to claim 1, in which said selected subset of granularities contains only granules containing not less than a predetermined number of data points.

3. A method according to claim 1, in which, where the said conglomerate is one dimensional and individual data samples of said signal conglomerate are spaced by distance and/or time, said selected subset of granularities comprises groups of granularities, corresponding to successive filter outputs.

4. A method according to claim 1, in which said signal conglomerate is two dimensional, said selected subset of granularities comprises groups of successive similar arrays of granularities, whereby each group of arrays includes signals from at least two such arrays.

5. A method according to claim 1, in which:

said signal conglomerate is of digital form; and

including the step of processing said digital signal conglomerate before said ordinal value filtering as to reduce the time required for ordinal value filtering of the digital signal conglomerate.

6. A method according to claim 1, in which at least part of the ordinal value filtering step is carried out by weighted median filtering.

7. A method according to claim 1, wherein at least part of the ordinal value filtering step is carried out by a forced root filter.

8. A method according to claim 1, wherein at least part of the ordinal value filtering step is carried out by root median filter.

9. A method according to claim 1, wherein at least part of the ordinal value filtering step is carried out by combinations of max and min filters.

10. A method of pulse analysis according to claim 1, further comprising forming an output of a hybrid filter by combining said output signal and a linear multiscale decomposition.

11. A method of pulse analysis applied to a signal conglomerate including:

flagging segments of the signal conglomerate which are extrema;

identifying those segments which require processing by the length of the flagged segments; and

processing the identified segments by ordinal value filtering where the identified segments are filtered with a succession of filtering stages of increasing window sizes, with an input to each successive filtering stage being formed from an output of a previous filtering stage.

12. A method according to claim 11, wherein said processing of the identified segments by ordinal value filters includes ordinal value filtering said identified segments with extrema of maxima and minima for at least one of the filtering stages.

13. A method according to claim 11, wherein said processing of the identified segments by ordinal value filters includes ordinal value filtering said identified segments separately for minima and maxima.

14. A method according to claim 11, wherein said processing of the identified segments by ordinal value filters includes ordinal value filtering said identified segments with only maxima or minima for at least one of the filtering stages.

15. A method according to claim 11, in which said processing of said identified segments occurs so that the processed value of each identified segment depends only on the length of the identified segment and the lengths of adjacent identified samples.

16. A method according to claim 11, further comprising run length coding the identified segments prior to each successive filtering stage.

17. A method according to claim 11, further comprising flagging upward and downward monotonic regions, and using the flagged regions to limit the extent of said processing.

18. A method of pulse analysis applied to a signal conglomerate including an ordinal value filtering step wherein at least a selected part of the signal conglomerate is filtered with a succession of ordinal value filters of increasing window sizes, an input to each successive ordinal value filter is formed from the output of the previous ordinal value filter, and at least one of the ordinal value filters is a stack filter having stages which contain positive boolean logic for reducing the amount of filtering.

19. A method according to claim 18, further comprising the steps of:

a) threshold decomposing the signal conglomerate to binary signals;

b) at said ordinal value filtering step, filtering the binary signals independently using boolean logic; and

c) adding the ordinal value filter outputs to form a greyscale filtered signal.

20. A method according to claim 18, in which said ordinal value filtering step uses weighted median filters.

21. A method of pattern recognition which comprises the steps of:

a successive ordinal value filtering step to filter data which describes a field containing a plurality of objects using a succession of filters of increasing window sizes, whereby an input to each successive filter is formed from the output of a previous filter so as to produce resulting data;

a matching step involving matching or comparing said resulting data with data describing one particular object which is to be identified according to shape and/or pattern and/or size from the said plurality of objects; and

a generation step wherein an output signal containing data relating only to objects having the characteristics of said particular object is generated.

22. A method as claimed in claim 21, in which said matching step is based on only a subset of the resulting data.

23. A method according to claim 21, in which said ordinal value filtering step is carried out using combinations of max and min filters.

24. A method according to claim 21, in which said ordinal value filtering step is carried out using forced root filters.

25. A method according to claim 21, in which said ordinal value filtering step is performed in two dimensions relative to the objects in the field.

26. A method according to claim 21, in which said matching step is based on size.

27. A method according to claim 21, further comprising scanning a field containing a plurality of objects to obtain the data to be filtered.

28. A datasieve for removing unwanted signals from a signal conglomerate comprising:

a succession of ordinal filtering means receiving at least a selected part of said signal conglomerate and filtering said at least a selected part of said signal conglomerate to produce a bandpass filter output, the ordinal filtering means having window lengths increasing from N (less than M) up to M, whereby an input to each successive ordinal filtering means is formed from the output of the previous ordinal filtering means;

selection means for selecting a predetermined subset of bandpass filter outputs from outputs of the succession of ordinal filtering means; and

arithmetic means for adding together the signals of the subset to produce an output signal containing only wanted signals selected by the selection means.

29. The use of a datasieve as a picture signal decomposition element in an image analysis system adapted to perform pattern recognition, the datasieve comprising:

a succession of ordinal filtering means receiving at least a selected part of a signal conglomerate and filtering at least a selected part of said signal conglomerate to produce a bandpass filter output, the ordinal filtering means having window lengths increasing from N (less than M) up to M, whereby an input to each successive ordinal filtering means is formed from an output of the previous ordinal filtering means;

selection means for selecting a predetermined subset of bandpass filter outputs from said outputs of the succession of ordinal filtering means; and

arithmetic means for adding together the signals of the subset to produce an output signal containing only signals selected by the selection means, where the input to the datasieve is data which describes a field of view containing a plurality of objects.

30. An image analysis system incorporating:

a datasieve comprising;

a succession of ordinal filtering means receiving at least a selected part of a signal conglomerate, said filtering said at least a selected part of said signal conglomerate to produce a bandpass filter output, the ordinal filtering means having window lengths increasing from N (less than M) up to M, whereby an input signal to each successive filtering means is formal from the output of the previous filtering means;

selection means for selecting a predetermined subset of bandpass filter outputs from outputs of the succession of filtering means; and

arithmetic means for adding together the signals of the subset to produce an output signal containing only wanted signals determined by the selection means;

data storage means for storing data relating to a sought-for-feature or object which may exist in a field from which data is derived for presenting to the datasieve;

comparison means for matching or comparing the stored data with the output signal of the datasieve; and

selection means to select from the input signal only data having a high degree of match to the data in the data storage means.

31. An image analysis system according to claim 30, wherein:

the comparison means performs matching or comparing by storing the output from some or all of the filtering means of the datasieve in the data storage means, and matching or comparing the stored data with data obtained from the same filtering means of the datasieve from which the stored data have been derived; and

further comprising thresholding means to exclude from output signals of the comparison means all output signals which have a given level of match in accordance with a predetermined threshold.

37. An image analysis system according to claim 30, wherein the comparison means performs matching or comparing by storing differences between successive outputs from the different filtering means of the datasieve in the data storage means, and matching or comparing the stored data with the differences in data obtained from the same filtering means of the datasieve from which the differences in data have been derived;

and further comprising thresholding means to exclude from output signals of the comparison means all output signals which have a given level of match in accordance with a predetermined threshold.

32. A method of image analysis in which:

a data stream representative of a field of view is analyzed to identify one or more images of objects in the field of view by the following steps of;

a) ordinal value filtering at least a selected part of a signal conglomerate with a succession of filters of window sizes increasing from N (being less than M) up to M, an input to each successive filter being formed from an output of a previous filter;

b) subtracting a current filter output from the previous filter output for said succession of filters to obtain bandpass outputs, known as granularities, consisting of strings of data points which contain strings of zero-valued data points, known as zero segments, and strings of non-zero-valued data points, known as non-zero segments or granules;

c) selecting a subset of the granularities;

d) adding together granularities within said subset to produce an output signal containing the granules in said subset; and

e) matching said output signal with a target or template of a particular object to be identified.

33. A method according to claim 32, in which matching occurs by ANDing said output signal with the target or template using some or all of the granules in the target or template.

34. A method according to claim 32, further comprising obtaining the granularities as a result of multidimensional decomposition.

35. A method according to claim 32, further comprising obtaining the granularities as a result of one dimensional decomposition of images obtained from a plurality of orientations of the objects in the field of view.

36. A method according to claim 32, including means for switching the order of the granularities to enable a mirror image of one or more objects to be recognized at the matching step.

38. A method of pulse analysis, comprising the following steps of:

a) ordinal value filtering at least a selected part of a signal conglomerate with a succession of filters of window sizes increasing from N (being less than M) up to M, an input to each successive filter being formed from an output of a previous filter;

b) subtracting a current filter output from the previous filter output for said succession of filters to obtain bandpass outputs, known as granularities, consisting of strings of data points which contain strings of zero-valued data points, known as zero segments, and strings of non-zero-valued data points, known as non-zero segments or granules;

c) selecting a subset of the granularities;

d) adding together granularities within said subset to produce an output signal containing the granules in said subset;

e) selecting the signals passed by the Mth ordinal filter; and

f) combining the selected signals with only some of the granules obtained from the preceding steps.

39. The use of a method of pulse analysis comprising the following steps of:

a) ordinal value filtering at least a selected part of a signal conglomerate with a succession of filters of window sizes increasing from N (being less than M) up to M and with the filters having different cut-off scales, an input to each successive filter being formed from an output of a previous filter;

b) subtracting a current filter output from the previous filter output for said succession of filters to obtain bandpass outputs, known as granularities, consisting of strings of data points which contain strings of zero-valued data points, known as zero segments, and strings of non-zero-valued data points, known as non-zero segments or granules;

c) selecting a subset of the granularities; and

d) adding together granularities within said subset to produce an output signal containing the granules in said subset so as to preserve sharp signal edges in a smoothed signal.