Processing system and method for enhancing image data

• US 4,979,136 A
• Filed: 03/01/1988
• Issued: 12/18/1990
• Est. Priority Date: 03/01/1988
• Status: Expired due to Fees

• Current Assignee: Transitions Research Corp.
• Original Assignee: Transitions Research Corp.
• Inventors: Pong, William, Weiman, Carl F. R.
• Primary Examiner(s): Gruber, Felix D.
• Assistant Examiner(s): Ramirez, Ellis B.
• Application Number:
  US07/162,752
• Time in Patent Office: 1,022 Days
• Field of Search: 364/572, 364/574, 364/715.01, 364/900, 364/521, 382/54, 382/51, 382/27, 382/36, 358/36, 358/167, 358/43
• US Class Current: 382/169
• CPC Class Codes: G06T 5/20 using local operators

Abstract

A non-linear digital filter system for image data or other signal data suppresses undesirable noise while enhancing significant characteristics of the data. Data elements in a neighborhood (window) defined around and including an input data element are classified into characteristic classes based on their parameter value range. The class with the maximum population is selected as most representative of the neighborhood. A data value associated with that class is chosen as the output of the filter for the input data element around which the neighborhood is defined, to thereby form a plurality filter.

As an alternative, the class holding more than half the data elements in the neighborhood is chosen as most representative, to form a majority filter. In case there is no class containing more than half the elements in a neighborhood, the output of the filter equal the value characteristic of the class in which the input pixel itself falls. In a further heterogeneity filter version, a data element for whose neighborhood there is no majority class is replaced by a "1"; a pixel for whose neighborhood there is a majority class is replaced by a "0". In the case of image data, the "1" value may represent a black intensity or a white intensity, in which case the "0" represents the opposite intensity.

Claims

1. In a method for processing a sequence of data elements each having a parameter value, the totality of such values being within a pre-determined range of values, the steps comprising

(a) defining a pre-determined set of classes of parameter values, where each class corresponds to a sub-range of said range of parameter values, and where each parameter value lies within a respective sub-range corresponding to one such class,

(b) for each individual data element of said sequence, selecting a pre-determined multiplicity of neighboring data elements,

(c) determining the sub-range for the parameter value of said individual data element and for the parameter value of each of said neighboring elements and increasing a count corresponding to the respective pre-determined class associated with that determined sub-range,

(d) selecting without regard to rank order of parameter value a single one of said classes whose count is not exceeded by the count of any other class, and

(e) replacing the parameter value of said individual element with a replacement value characteristic of said selected parameter value class.

2. A method as in claim 1 wherein each sub-range corresponds to a plurality of parameter values.

3. In a method for processing a sequence of data elements each having a parameter value, the totality of such values being within a pre-determined range of values, the steps comprising

(a) defining a pre-determined set of classes of parameter values, where each class corresponds to a sub-range of said range of parameter values, and each parameter value lies within a respective sub-range corresponding to one such class,

(b) for each individual data element of said sequence, selecting a pre-determined multiplicity of neighboring data elements,

(c) determining the sub-range for the parameter value of said individual data element and for the parameter value of each of said neighboring elements and increasing a count corresponding to the respective pre-determined class associated with that determined sub-range,

(d) selecting without sorting by rank a single one of said classes whose count has a pre-determined relation to all said counts, and

(e) replacing the parameter value of said individual element with a replacement value characteristic of said selected parameter value class,

(f) said pre-determined relation being any of (i) the maximum of all said counts or (ii) a count which is at least a pre-determined fraction of the number of said neighboring data elements.

4. In a method for processing a sequence of data elements each having a parameter value, the totality of such values being within a predetermined range of values, the steps comprising

(a) defining a pre-determined set of classes of parameter values, where each class corresponds to a sub-range of said range of parameter values, and each parameter value lies within a respective sub-range corresponding to one such class,

(b) for each individual data element of said sequence, selecting a pre-determined multiplicity of neighboring data elements,

(c) determining the sub-range for the parameter value of said individual data element and for the parameter value of each of said neighboring elements and increasing a count corresponding to the respective pre-determined class associated with that determined sub-range,

(d) selecting without sorting by rank a single one of said classes whose count has a pre-determined relation to all said counts, and

(e) replacing the parameter value of said individual element with a replacement value characteristic of said selected parameter value class,

(f) said replacement parameter value being that parameter value associated with the class whose count is greatest, to provide a plurality filter.

5. In a method for processing a sequence of data elements each having a parameter value, the totality of such values being within a pre-determined range of values, the steps comprising

(a) defining a pre-determined set of classes of parameter values, where each class corresponds to a sub-range of said range of parameter values, and each parameter value lies within a respective sub-range corresponding to one such class,

(b) for each individual data element of said sequence, selecting a pre-determined multiplicity of neighboring data elements,

(c) determining the sub-range for the parameter value of said individual data element and for the parameter value of each of said neighboring elements and increasing a count corresponding to the respective pre-determined class associated with that determined sub-range,

(d) selecting without sorting by rank a single one of said classes whose count has a pre-determined relation to all said counts, and

(e) replacing the parameter value of said individual element with a replacement value characteristic of said selected parameter value class,

wherein, for such a class whose count is more than a pre-determined portion of the total number of data elements in the neighborhood, said replacement parameter value is a "one", and in the absence of such a count, then said replacement parameter value is a "zero", to provide a heterogeneity filter.

8. The method of any of claims 6, 7 or 5 in which said sequence of data elements is a series of digitized data elements of a signal, each data element having an intensity value constituting said parameter value.

9. The method of any of claims 6, 7 or 5 for non-linearly filtering an image processing system in which the image is a composite of a multiplicity of digitized pixels constituting said data elements, each data element having a gray-scale intensity value constituting said parameter value.

14. The method of claim 9 in which the sequence of data elements represents a two-dimensional image and in which the said window is a two-dimensional window about a target pixel and in which the shifting of the window in step (g) (i) causes several pixels to be deleted from said window and causes their contributions to be subtracted from the counts of said bins, and (ii) causes several new pixels to be included in said window and causes their contributions to be added to the counts of said bins.

6. In a method for processing a sequence of data elements each having a parameter value, the totality of such values being within a pre-determined range of values, the steps comprising

(a) defining a pre-determined set of classes of parameter values, where each class corresponds to a sub-range of said range of parameter values, and each parameter value lies within a respective sub-range corresponding to one such class,

(b) for each individual data element of said sequence, selecting a pre-determined multiplicity of neighboring data elements,

(c) determining the sub-range for the parameter value of said individual data element and for the parameter value of each of said neighboring elements and increasing a count corresponding to the respective pre-determined class associated with that determined sub-range,

(d) selecting without sorting by rank a single one of said classes whose count has a pre-determined relation to all said counts, and

(e) replacing the parameter value of said individual element with a replacement value characteristic of said selected parameter value class,

(f) said replacement parameter value being that parameter value associated with the class whose count is equal to at least half of the total number of data elements in the said neighborhood.

7. A method as in claim 6 wherein, in the absence of such a class whose count is at least half of the number of data elements in the neighborhood, then said replacement value is that value associated with the class into which the said individual data element was itself classified.

10. The method as in claim 6 wherein, in the absence of such a class whose count equal more than half the number of data elements in the window, then the replacement value is the original value of the target data element truncated to m bits and padded by zeros.

11. In a non-linear digital filter system of processing a signal comprising a sequence of digitized data elements having various digital data values, the method comprising the steps of:

a) selecting a window for enclosing a portion of at least one sub-sequence of said signal having a multiplicity of data elements;

b) selecting the beginning and the end of the sequence of data elements to be processed;

c) locating said window at the beginning of said sequence;

d) providing a histogram having a plurality of bins, each bin comprising a counter representing a respective value of the data elements, and causing each bin to have a count corresponding to the total number of data elements within said window having the value represented by the respective bin;

e) designating the centermost data element within said window as a target data element;

f) replacing the original value of the target data element with the value represented by the bin having the maximum count of all bins to provide a plurality filter.

12. The method of claim 11, where the replacement value in said step (f) is replaced by that value which is represented by the bin having a count representing more than half of the number of data elements in the window, to provide a majority filter.

13. The method of claim 11, further including the steps of

g) shifting the window one data element closer to the end of the sequence, thereby causing a new data element to be enclosed by said window, and causing a previously included data element to be deleted from said window;

h) changing said histogram by adding the contribution of the new element and subtracting the contribution of the deleted element; and

i) repeating steps (e), (f), (g), and (h) in an iterative manner to the end of said sequence of data elements being processed.

15. The method of claim 11 wherein said step (d) further includes the steps of:

d1) selecting only m most significant bits of each data element value for processing wherein m is less than the total number of bits for the largest data value; and

d2) providing 2^m bins for said histograms, each representing a sub-range of the entire range of possible data element values.

16. The method of claim 15 further including in step (f) the step of appending to each replacement data element value a number of zero bits equal to q-m, where q is the number of bits representing the original data element value.

17. The method of claim 15, in which the replacement value is replaced by "one " if one bin holds a count equal to more than a predetermined fraction of half the number of data elements, and "zero" otherwise, to provide a heterogeneity filter.

18. Apparatus for processing a set of data elements, each element having an individual parameter value, said apparatus comprising:

(a) a multiplicity of counters, each counter corresponding to a bin of a histogram and also corresponding to a respective sub-range of parameter values;

(b) means responsive to each said data element to increment the one of said counters which corresponds to the sub-range within which falls the parameter value of said data element to provide in said counter a count equal to the number of data elements having a parameter value within the sub-range corresponding to the respective histogram counter;

(c) a reference counter circuit which holds a value equal to the highest count in any of said counters;

(d) means for comparing the count value within each of said histogram counters against the value within the reference counter;

(e) means for incrementing said reference counter when its value is less than any of said histogram counter values; and

(f) means for providing an output responsive to the histogram counter whose count is not exceeded by the count of any other such histogram counter, after all data elements of said set have been processed.

19. An apparatus as in claim 18, wherein said reference circuit contains a count substantially equal to at least half of the number of data elements of said set.

20. An apparatus as in claim 18, further including:

means for modifying said set of data elements to include one or more new elements and to exclude a like number of previously included elements,

means for decrementing the counter or counters of said histogram corresponding to values of said excluded data element or elements, and for incrementing the counter or counters of said histogram corresponding to values of said newly included data element or elements; and

means responsive to a condition where all of said histogram counters have counts less than that of said reference counter for decrementing said reference circuit output value.

21. An apparatus as in claim 20, wherein said decrementing means include an AND circuit connected to the outputs of all said histogram counters.

22. An apparatus as in claim 20, wherein said incrementing means includes an OR circuit connected to the outputs of all said histogram counters.

23. Apparatus in claim 22, further including

means for providing an output responsive to the histogram counter whose count is not exceeded by the count of any other such histogram counter, after all data elements of said set have been processed.

24. An apparatus as in claim 23, wherein said output-providing means includes a means for deriving an output based on which of said histogram counters have a count equal to the count in the said reference circuit output.

25. A digital image-processing system, comprising:

a control parameter selector for selecting (a) a window width for a window enclosing a portion of at least one line having a plurality of pixels of an image to be processed, one of said pixels being a target pixel, and (b) the beginning and end of the domain of the line or lines of pixels to be processed;

means for locating the window at the beginning of the domain;

a histogram device comprising a multiplicity of counters, with each counter both (1) corresponding to a bin of said histogram, and (2) representing a respective sub-range of intensity values of said pixels, each counter being caused to have a count equivalent to the total number of pixels within said window having a value within the sub-range associated with that counter;

substitution means for selectively changing the intensity value of a target pixel of said window to a value associated with the sub-range corresponding to one of said counters;

shifting means for repetitively moving the window at least one pixel closer to the end of the domain, thereby causing one or more additional pixels adjacent the leading edge of said window to be enclosed by said window, and one or more pixels adjacent a trailing edge of said window to be excluded from said window;

updating means for changing said histogram by incrementing the counter or counters associated with the intensity value or values of the additional pixel or pixels, and decrementing the counter or counters associated with the intensity value or values of the excluded pixel or pixels;

said substitution means being responsive to said updating means for changing the value of the new target pixel of each new window position; and

a controller including clock means for cyclically operating said shifting means, said updating means and said substitution means.

26. A digital image-processing system for suppressing noise components and enhancing dominant features of an image represented by a data signal which comprises a succession of groups of most-significant data bits of predetermined number, each group of bits representing an intensity value of a digitized pixel in gray-scale scanned within a predetermined window of said image, said system comprising:

clock means for producing first, second and third clock signals, said first and second clock signals being of the same repetition rate and phase-separated with respect to one another, said third clock signal occurring periodically after the successive occurrence of a predetermined number of said first and second clock signals;

a buffer responsive to said first clock signal for successively receiving said digitized pixel data groups, and for outputting data corresponding to a last-received digitized pixel;

a FIFO shift register corresponding in number of stages to the number of pixels in said predetermined window, and coupled to said buffer for receiving as an input each successive digitized pixel data outputted from said buffer, and responsive to said second clock signal for outputting a digitized pixel corresponding to a pixel of the window of said image being processed;

a decoder coupled to said buffer and to said register and having an input port for receiving the digitized pixel data outputted from one of said buffer and said FIFO register, and having a multiplicity of output signal lines equal in number to 2^m where m is equal to the selected number of most-significant bits representing each one of said digitized pixels, such decoder being adapted to activate a single output line corresponding to the numerical value of the m most significant bits of the digitized pixel data at the input port;

2^m up/down counters, each one having (i) an input terminal connected to a respective one of said plurality of output signal lines of said decoder, (ii) an up-count input terminal for receiving said first clock signals, (iii) a downcount input terminal for receiving said second clock signals, and (iv) an output port for outputting an m-bit binary signal corresponding to its count, each one of said counters representing a different bin of a histogram;

2^m comparators, each having (i) first and second inputs and (ii) first, second and third outputs, said first comparator output providing a signal indicating that said first input is greater than said second input, said second comparator output providing a signal indicating that said first input is less than said second input, and said third comparator output providing a signal indicating that said first and second inputs are equal,

each of said comparator first inputs being connected to the output of a respective one of said up/down counters,

a reference circuit comprising a counter and input logic gates, having (i) a first input connected to said first comparator output, (ii) a second input connected to said second comparator output terminals, and (iii) an output connected to each second input of said comparators,

said reference circuit being adapted to increment its count upon receipt of a signal from any first output of said comparators, and being adapted to decrement its count upon receipt of second outputs from all said comparators,

whereby said third comparator output indicates which up/down counter has a count equal to the count in said reference circuit counter, which count is thereby maximum count.

27. Apparatus as in claim 26 further including:

a priority encoder (i) having a plurality of inputs each connected respectively to one of said third comparator outputs and (ii) an output for providing an m-bit signal corresponding to the value corresponding to a bin whose count is the maximum of all the bins.

28. Apparatus as in claim 27 further including:

an output latch circuit having a first input for receiving said third clock signal, and a second input connected to the output of said priority encoder, said latch circuit being responsive to said third clock signal for both (1) latching the output signal from said priority encoder, and (2) providing at an output terminal an output signal corresponding to the processed value of the digitized pixel provided as in input to said system.

29. The digital image-processing system of claim 27, wherein said priority encoder further includes means responsive to more than one of said counters having a total count equal to the count of said maximum bin counting means, for selecting the one of said first counters of equal count corresponding to the parameter value of the highest intensity value.

30. Apparatus for selecting a maximum data value element from a set of data elements having differing values, comprising

a group of counters, each adapted to have supplied to it data elements of said set having a respective individual value, each counter having an output representing the number of data elements of said set supplied to it which have its respective individual value, and

a corresponding group of comparators, each comparator having a first input supplied from a respective counter output, and having a second input,

each said comparator providing a first output responsive to said first comparator input being greater than said second comparator input, and a second output responsive to said first and second comparator inputs being equal,

a reference circuit having an output supplied to all of said comparator second inputs, and

an output circuit providing an output signal after all said data elements have been supplied to said counters, said signal being responsive to any of said first comparator inputs being at least equal to said second comparator input.

31. Apparatus as in claim 30, wherein

said reference circuit is a reference counter;

said reference counter having an input and including means responsive to a signal supplied to said input for incrementing its count; and

a circuit supplying said incremented count to all said comparator second inputs.

32. Apparatus as in claim 31, including a circuit connected to all of said comparator first outputs and adapted to supply to said reference counter a signal to increment said counter.

33. Apparatus as in claim 31 including

each said comparator including a third output responsive to its first comparator input being less than its second comparator input, and

a circuit connected to all of said third comparator outputs for supplying an output signal responsive to all of said first comparator inputs being less than said second comparator inputs for decrementing said reference counter.

34. Apparatus as in claim 31 including

a circuit responsive to all of said first comparator inputs being less than their respective second comparator inputs for decrementing said reference counter,

a circuit responsive to an output signal from any of said comparator first outputs for incrementing said reference counter, and

an output circuit responsive to a signal from one of said second comparator outputs.