Data processing method and apparatus

• US 6,081,617 A
• Filed: 03/23/1998
• Issued: 06/27/2000
• Est. Priority Date: 06/20/1995
• Status: Expired due to Fees

• Current Assignee: Cambridge Solutions Limited (DXC Technology Company)
• Original Assignee: Cambridge Solutions Limited (DXC Technology Company)
• Inventors: Young, Robert William, Bangham, James Andrew, Bragg, Nigel Lawrence
• Primary Examiner(s): ROGERS, SCOTT A
• Application Number:
  US08/981,599
• Time in Patent Office: 827 Days
• Field of Search: 382/275, 382/173, 382/204, 382/203, 382/205, 382/284, 382/288, 382/286, 382/263, 382/264, 382/260, 382/199, 382/195, 382/192
• US Class Current: 382/173
• CPC Class Codes: G06T 2207/10024 Color image
• CPC Class Codes: G06T 2207/20016 Hierarchical, coarse-to-fine, multiscale or multiresolution image processing; Pyramid transform
• CPC Class Codes: G06T 5/20 using local operators

Abstract

In a data processing method and apparatus, an image signal representative of features in a space of two or more dimensions is progressively filtered at monotonically increasing filtering scales, the signal being input to the first filtering scale, and the input to the or each subsequent filtering scale is the output signal from the previous scale. Each input has a number of data samples each of which represents a respective region of the space, and at each filtering scale those samples are sorted into connected-sets, each of which contains a plurality of substantially equal value to data samples or a respective individual data sample not in other sets. The process then selects those connected-sets which contain data samples having values which are local maxima or local minima and which represent a composite region of a size related in a predetermined way to the current filtering scale. Each selected set is then effectively merged with the adjacent connected-set which contains data samples of a value closest to that of the sample(s) in the selected connected-set. This is achieved by changing the latter'"'"'s value to that of the samples in the adjacent connected set. The output signal for the filtering method is derived from the output of at least one of the filtering scales. In at least one of those scales, both connected-sets having local maxima and connected-sets having local minima are selected, thereby increasing the tolerance of the method to noise.

Claims

1. A method for filtering a signal representative of features in a space of two dimensions, the signal comprising a plurality of data samples, each having a value representative of a predetermined parameter of the signal for a respective region of said space, the method comprising the steps of:

(a) progressively filtering the signal at monotonically increasing filtering scales from S1 up to S2, the input signal to the first filtering scale being the original input signal to the filtering process, while the input signal to the or each subsequent filtering scale is the output signal from the previous filtering scale;

(b) at each filtering scale,

i) identifying one or more connected-sets, each of either a plurality of adjoining data samples having substantially the same value or values lying in a predetermined range or a single respective data sample not in any other set, each set thus having a value equal to the value of the or all the data samples therein or, where the values lie in said range, the average of the values of the data samples therein; and

ii) selecting each of those collected-sets which has an area related in a predetermined way to the current filtering scale and which has a value that is a local maximum or a local minimum compared with those of adjacent connected sets,

and for each selected connected-set,

(c) identifying the adjacent connected-set whose value is closest to the current value of the selected set;

(d) so modifying the value of the selected set that the new value is equal to that of the adjacent connected-set identified in step (c) so that the adjacent connected-set becomes merged with the selected connected-set, thereby forming an extended connected-set of larger area; and

outputting an output signal from at least one of the filtering scales, wherein for at least one of such filtering scales, both connected-sets having local maxima and connected-sets having local minima are selected.

2. A method according to claim 1 in which both connected-sets having local maxima values and connected-sets having local minima values are selected at each filtering scale.

3. A method according to claim 1, in which the method further comprises the step of outputting a further signal representative of parameters describing a "granule" represents the share of the originally selected sets and the change in value of those sets due to said modification.

4. A method according to claim 1, in which a respective output signal is output from each filtering scale once all the connected-sets selected at that scale have been processed.

5. A method according to claim 1 in which the signal is representative of an image containing a number of objects represented by local maxima and minima in the values of the data samples for the regions occupied by the objects, each object being removed from the image if a filtering scale related criterion is satisfied by the area of the object.

6. A method according to claim 5 in which said criterion is satisfied if the area of the object is equal to an "area equivalent" associated with the filtering scale.

7. A method according to claim 5 or claim 6 in which the criterion is satisfied if the area of the object is less than an "area equivalent" associated with the filtering scale.

8. A method according to claim 5 or claim 6 in which said criterion is satisfied if the area of the object is greater than an "area equivalent" associated with the filtering scale.

9. A method according to claim 1 in which the signal is an image signal, the value of each data sample representing the intensity and/or colour of a respective pixel.

10. A method according to claim 1 in which the number of data samples in a connected-set is used as a measure of the area of volume of the composite region represented by that set.

11. A method according to claim 1 in which the value of each selected connected-set is only modified at a given filtering scale if that value satisfies a predetermined further criterion.

12. A method according to claim 11 in which said further criterion is based on the difference between the value of the selected connected-set under consideration, and the value of an adjacent connected-set having the closest value to that of the set under consideration.

13. A method according to claim 12 in which said values represent amplitudes or intensities, the further criterion therefore being the contrast between the connected-set under consideration and the surrounding connected-sets.

14. A method according to claim 1 in which, if said adjacent connected-set having a value which is closest to that of the selected set is one of a plurality of such adjacent connected-sets, either all such connected-sets are merged with the selected connected-set to form a single composite set whose area is the sum of the areas of all the merged connected-sets, or only one such adjacent connected-set is merged with the selected connected-set at that filtering scale, with the or each other such adjacent connected-set being merged at higher filtering scales.

15. A method according to claim 14, in which, at a given filtering scale, the selected connected-set is merged with all adjacent connected-sets having values which lie within a predetermined range of values which includes the value of the selected connected-set.

16. A method according to claim 1 in which the method further comprises the steps of subtracting an output signal of one filtering scale from an output signal of a different filtering scale and outputting the difference to any subsequent processing or to a display, the method thereby separating features in a certain range of sizes from other features.

17. A method according to claim 1, in which the method further comprises the steps of subtracting the output signal of one filtering scale from the input signal to that scale, and outputting the difference to any subsequent processing or to a display, the method thereby removing larger scale features.

18. A method according to claim 1, in which the method further comprises the steps of outputting signals from a number of filtering scales, each said signal describing the location and/or change in value of any selected connected-sets that were processed at the corresponding scale, and passing the signals to any subsequent processing or to a display, the method thereby decomposing the signal by placing features into different groups, each of which contains only features of a respective size or a size lying within a respective range of sizes.

19. A method according to claim 1 in which, at any filtering scale, the selected sets are processed in the order in which they appeared in the input signal to that filtering scale.

20. A method according to claim 1 in which, at any filtering scale, all the selected connected-sets which represent local maxima are processed before those representing local minima, or vice-versa.

21. A method according to claim 1, in which said modifications to the values of selected connected-sets are made directly to the input data for a filtering scale, and are not stored in a separate output buffer.

22. A method for filtering a signal representative of features in a space of three dimensions, the signal comprising a plurality of data samples, each having a value representative of a predetermined parameter of the signal for a respective region of said space, the method comprising the steps of:

(a) progressively filtering the signal at monotonically increasing filtering scales from S1 up to S2, the input signal to the first filtering scale being the original input signal to the filtering process, while the input signal to the or each subsequent filtering scale is the output signal from the previous filtering scale;

(b) at each filtering scale,

i) identifying one or more connected-sets, each of either a plurality of adjoining data samples having substantially the same value or values lying in a predetermined range or a single respective data sample not in any other set, each set thus having a value equal to the value of the or all the data samples therein or, where the values lie in said range, the average of the values of the data samples therein; and

ii) selecting each of those collected-sets which has a volume related in a predetermined way to the current filtering scale and which has a value that is a local maximum or a local minimum compared with those of adjacent connected sets,

and for each selected connected-set,

(c) identifying the adjacent connected-set whose value is closest to the current value of the selected set;

(d) so modifying the value of the selected connected-set that the new value is equal to that of the adjacent connected-set identified in step (c) so that the adjacent connected-set becomes merged with the selected connected-set, thereby forming an extended connected-set of larger volume; and

outputting an output signal from at least one of the filtering scales, wherein for at least one of such filtering scales, both connected-sets having local maxima and connected-sets having local minima are selected.

23. A method for filtering a signal representative of features in a space of two or more dimensions, the signal comprising a plurality of data samples each having a value representative of a predetermined parameter of the signal for a respective region of said space, the method comprising the following steps:

(a) progressively filtering the signal at monotonically increasing filtering scales from S1 up to S2, the input signal to the first filtering scale being the original input signal to the filtering process, while the input signal to the or each subsequent filtering scale is the output signal from the previous filtering scale;

(b) at each filtering scale,

i) identifying one or more connected-sets, each of either a plurality of adjoining data samples having substantially the same value or values lying in a predetermined range or a single respective data sample not in any other set, each set thus having a value equal to the value of the or all the data samples therein or, where the values lie in said range, the average of the values of the data samples therein; and

ii) selecting each of those collected-sets which has a size and/or colour, a parameter or combination of parameters of which is related in a predetermined way to the current filtering scale and which has a value that is a local maximum or a local minimum compared with those of adjacent connected sets,

and for each selected connected-set,

(c) identifying the adjacent connected-set whose value is closest to the current value of the selected set;

(d) so modifying the value of the selected connected-set that the new value is equal to that of the adjacent connected-set identified in step (c) so that the adjacent connected-set becomes merged with the selected connected-set, thereby forming an extended connected-set of larger size; and

outputting the output signal from at least one of the filtering scales, wherein for at least one of such filtering scales, both connected-sets having local maxima and connected-sets having local minima are selected.

24. A method according to claim 23 in which, in step (b) a single parameter, related to the size of a region represented by a connected-set is considered, and in which said single parameter comprises any one of the perimeter, width, height, moment about some point, greatest distance between any two points or geodesic distance.

25. A method according to claim 24 in which the distance, perimeter, width, height or depth of a composite region are determined by counting the number of data samples in the connected-set representing that region.

26. A method according to claim 23 in which step (b) involves a consideration of a combination of parameters relating to the size of the region represented by a connected-set, and in which said combination comprises any one or more of the perimeter, width, height, moments about some point, greatest distance between any two points or geodesic distance of the composite region.

27. Apparatus for filtering a signal, the apparatus comprising:

(a) first circuit means for identifying connected-sets in an input signal;

(b) comparator circuit means for determining whether the value of a connected-set is a local maximum or minimum by comparing that value with the value of adjacent connected-sets;

(c) integration circuit means for determining one or more parameters related to the sizes of connected sets whose value is a local maximum or local minimum;

(d) selection circuit means for comparing said parameter or parameters with a filtering scale thereby to determine whether such connected-sets require processing;

(e) means for reading the values of the connected-sets that are adjacent to selected connected-sets;

(f) further comparator means for determining which adjacent connected-set is closest in value to that of any selected connected-set;

(g) means for modifying the value of a selected connected-set to that of the closest value adjacent connected-set;

(h) output means for outputting a signal following filtering at a predetermined scale; and

(i) means for determining when processing is finished.

28. Apparatus according to claim 27, in which the apparatus includes input and output buffers, control circuitry and additional memory for storing intermediate results and other information used in the processing.

29. Apparatus according to claim 28, in which the apparatus includes additional storage means for storing information that describes the local maxima and minima found in the signal.

30. Apparatus according to claim 29, in which the storage means is used to hold any or all of the following data:

the location of at least one of the data samples having a local maximum or minimum value;

a list of the locations of all such data samples in a connected-set;

the area of such a set;

the value of the data samples in the set;

a list of other connected-sets or data samples that are adjacent to said connected-set;

a flag that indicates whether each maximum or minimum value is a maximum or a minimum.

31. Apparatus according to claim 30, in which the storage means stores information on connected-sets of data samples having local maximum values in one list and sets of samples having local minimum values in another list.

32. Apparatus according to claim 29, in which, in order to further improve processing speed, the apparatus includes additional storage means for storing information that describes the connected-sets found in the signal.

33. Apparatus according to claim 32, in which the storage means is used to hold any or all of the following data:

the location of at least one of the data samples in the connected-set;

a list of the locations of all the data samples in the connected-set;

the area of the connected-set the value of the connected-set;

a list of other connected-sets or data samples that are adjacent to the connected-set;

a list of data samples that are contained within the connected-set and lie along the perimeter of the connected-set, possibly including a flag for each such data sample to indicate in which direction a data sample from a neighbouring connected-set can be found.

34. Apparatus according to claim 32, in which, in order further to improve processing speed, further additional storage means is provided in order to identify the connected-set to which each data sample in the signal belongs at each stage in the processing.

35. Apparatus according to claim 27, in which the means for determining when processing is finished comprises a counter for holding the current filtering scale and means for comparing the current filtering scale with the maximum filtering scale.

36. Apparatus according to claim 27, in which the means for determining when processing is finished comprises means for determining the minimum area of any selected connected-set or composite connected-set formed by merging selected connected-sets with adjacent connected-sets and means for comparing this area with the maximum filtering scale.

37. Apparatus according to claim 27, in which the selection circuit means comprises means for comparing the total area of the region or composite region represented by any connected-set with a filtering scale, the integration circuit means being operable to determine the total areas represented by connected-sets.

38. Apparatus according to claim 37, in which the selection circuit means further comprises means for holding connected-sets, having values which are local maxima or minima, of different areas in different lists, such that only the list corresponding to a particular scale needs to be processed at that scale.

39. Apparatus according to claim 27, in which the output means employs a comparator to determine when the desired filtering scale has been reached.

40. Apparatus according to claim 27, in which the selection circuit means comprises means for comparing one or more of perimeter, width, height, moments about some point, greatest distance between any two points in the region, geodesic distance with a filtering scale, the integration circuit means being operable to determine said one or more parameters for connected-sets.

41. Apparatus according to claim 27, in which the selection circuit means is also operable to compare the value of data samples in a given set with those of samples in adjacent connected regions to determine whether the connected-set being tested should be processed at a given filtering scale.