Image analysis – Image enhancement or restoration – Image filter
Reexamination Certificate
1998-08-20
2001-03-27
Rogers, Scott (Department: 2624)
Image analysis
Image enhancement or restoration
Image filter
C382S262000, C382S264000, C708S300000, C708S304000, C708S308000
Reexamination Certificate
active
06208764
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to a rank filter methodology suitable for use in real-time signal processing and image processing applications.
BACKGROUND OF THE INVENTION
Digital filtering is a class of image processing. Rank filtering is one type of digital filtering which is widely used in image processing, for example, for eliminating/reducing noise in an image. It is a technique for performing non-linear smoothing of a single- or multi-dimensional signal consisting of discrete samples.
An output sample is generated by the filter for each such input sample, using a window size and a rank value to specify the characteristics of the filter. The rank filter is a sorting algorithm in which data values (e.g., pixels) within the window are sorted in numerical order. The output value is the nth lowest data value within the window, where n is the rank order of the filter. When n is the median sample, the rank-order filter could be referred to as a median filter. More particularly, a rank filter replaces a data value, corresponding to a predetermined rank, among multiple data values within the window. The data set value corresponding to the center position of the window is replaced. Accordingly, there can only be an odd number of data values in the window since the result of the filter is stored in the location on which the window is centered.
Using two examples, the concept of a rank filter is briefly explained in order to help in understanding a rank filter.
FIG. 1
shows a first example of performing a rank filtering in the case of data values within a 3×3 window. If the data values (shown at the left of the figure) are arranged starting with the largest number and ending with the smallest number, they become: 15, 12, 11, 10, 7, 6, 5, 5, 2. If a predetermined rank of 5 is selected, the data position corresponding with the center position of the 3×3 window (which has a value of 2), is replaced with the value of 7, since 7 is the magnitude corresponding to the 5
th
value (i.e., rank of 5) of the nine data values (as shown at the right of the figure). For this particular example, since the value of 7 is a median value of the nine data values, the filter could be referred to as a median filter.
FIG. 2
shows a second example of performing a rank filter in a case of data values within a 5×1 window. If the data values (shown at the left of the figure) are arranged starting with the largest number and ending with the smallest number, they become: 11, 10, 7, 6, 5. If a predetermined rank of 3 is selected, the data position corresponding with the center position of the 5×1 window (which has a value of 10), is replaced with the value of 7, since 7 is the magnitude corresponding to the 3rd value (i.e., rank of 3) of the five data values. The ranked data values are shown at the right of the figure.
Numerous designs exist in the prior art for both one-dimensional and two-dimensional rank filters. U.S. Pat. No. 5,408,675 is directed to a hardware implementation of a programmable rank order filter using a first-in-first-out approach to track the values and the rank number for each corresponding value. U.S. Pat. No. 5,315,171 determines the rank value by the summation from comparator of the inputs to the feedback value. U.S. Pat. No. 5,113,484 determines the rank element by comparing in order the rank desired with occurrences of each possible value.
While such apparatus may have achieved certain degrees of success in their particular applications, because of the constant sorting of the data value in the window, the processing of an image using this technique can be compute intensive. In addition, memory requirements to perform the filtering may require space for both the original image and the processed image. Further, such filtering may be limited to a particular window size or rank element, or require that the filter be implemented solely in hardware or solely in software.
Accordingly, a need continues to exist for a rank filter which does not consume significant processing time, is not limited to a particular window size or rank element, does not require significant computer memory, and can be implemented in both hardware and software.
SUMMARY OF THE INVENTION
An object of the present invention is to provide a rank filter which does not consume significant processing time.
Another object of the invention is to provide such a rank filter which is not limited to a particular window size or rank element.
Still another object of the invention is to provide such a rank filter which does not require significant computer memory.
Yet another object of the invention is to provide such a rank filter which can be implemented in both hardware and software.
These objects are given only by way of illustrative example. Thus, other desirable objectives and advantages inherently achieved by the disclosed invention may occur or become apparent to those skilled in the art. The invention is defined by the appended claims.
According to one aspect of the invention, there is provided a method for performing a rank filter. A predetermined target rank n is selected. A memory array of a predetermined window size s is generated, as is a linked-list linking the elements of the memory array. The target rank n is selected as being less than or equal to the window size s. After initializing each element of the memory array, a data value from a data set is sequentially inputted into the memory array. Each time a data value is sequentially inputted into the memory array, it is compared with the data values of the elements of the memory array, and inserted into the linked-list so as to be in numerical order. Accordingly, after the data values have been inserted, the linked-list links the elements within the memory array in numerical order. The rank value of the memory array is returned and replaces a value in the data set corresponding to the center of the window.
According to another aspect of the invention, there is provided a rank filter. The rank filter includes a memory array of a predetermined window size s. A predetermined target rank n is selected so as to be less than or equal to the window size s. A linked-list links the elements of the memory array. Input means sequentially inputs a data value from a data set into the memory array, while filtering means performs numerical ordering of the data values contained within the memory array each time a data value is inputted into the memory array. The rank filter further includes means for updating the linked-list after the data values have been filtered such that the linked-list links the elements disposed within the memory array in numerical order. Means replacing a data value of the data set with the rank value are also included.
The present invention provides a rank filter which does not consume significant processing time, is not limited to a particular window size or rank element, does not require significant computer memory, and can be implemented in both hardware and software.
REFERENCES:
patent: 4802108 (1989-01-01), Bagdis et al.
patent: 4949389 (1990-08-01), Allebach et al.
patent: 5113484 (1992-05-01), Jeong
patent: 5315171 (1994-05-01), Blauer et al.
patent: 5319583 (1994-06-01), Wildes
patent: 5408675 (1995-04-01), Florentino et al.
patent: 5532948 (1996-07-01), Kohno et al.
patent: 5668895 (1997-09-01), Yamazaki et al.
patent: 5708595 (1998-01-01), Connell
patent: 5737251 (1998-04-01), Kohno et al.
patent: 5870584 (1999-02-01), Bennet
“Algorithms C++”, by Robert Sedgewick, 1992, pp. 115-119.
Archer Greg L.
Wilkinson Larry W.
Eastman Kodak Company
Parulski Susan L.
Rogers Scott
LandOfFree
Rank filter using a linked-list to link elements in a memory... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Rank filter using a linked-list to link elements in a memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rank filter using a linked-list to link elements in a memory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2471831