Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-09-09
2001-03-06
Malzahn, David H. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C382S262000
Reexamination Certificate
active
06199084
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to digital filters, and more specifically, to methods and apparatus for efficiently implementing weighted median filters.
BACKGROUND OF THE INVENTION
Currently, images, speech, a wide variety of communications signals and numerous other types of information are being represented in the form of digital data.
Unfortunately, due to, e.g., transmission errors, signal interference, etc., digital signals and the sets of digital data represented thereby, often become corrupted by impulse noise. Impulse noise frequently introduces sharp, sudden changes in signal values. For transmitted signals, e.g., audio and/or video signals, this can result in undesired noticeable signal degradation.
In many applications the use of infinite impulse response (IIR) and finite impulse response (FIR) filters can reduce or eliminate some of the undesirable effects of impulse noise. Unfortunately, the use of such filters has undesirable consequences in many applications. for example, the use of FIR and IIR filters on images tends to have the undesirable effect of softening edges within an image and/or blurring images. This is because such filters operate on pixels affected by impulse noise as well as pixel values unaffected by impulse noise.
Median filters have the advantage of modifying a single value at a time, e.g., as a function of adjacent values in a set of digital data values. Median filters replace the value being processed with the median or middle value found in the set of values used to perform the filtering operation. The median value need not be, and in many cases will not be, the average value of the set of values used to perform the filtering operation.
FIG. 1
, illustrates a 4×4 array of values, e.g., pixel values, where letters A through P each represent a different pixel value, e.g., a value used to represent pixel luminance or chrominance information.
Assume a 3×3 median filter were used to filter the pixel value F of FIG.
1
. In such a case, the pixel value F would be replaced by the median value in the set of pixel values A, B, C, E, F, G, I, J, K.
Median filters will normally result in the replacement of pixel values which have been affected by impulse noise. However, when applied to images, they also have the undesirable effect of replacing many pixel values which are unaffected by impulse noise as well.
The use of a weighted median filter can reduce the risk that pixel values which are unaffected by impulse noise will be replaced as a result of a median filtering operation.
FIG. 2
shows a weighting matrix that can be used to implement a weighted median filter. In a weighted median filter, the weight determines the number of times the corresponding value should be included in the set of values used to determine the median. For example, using the filter weights shown in
FIG. 2
to perform a 3×3 weighted median filtering operation on the set of pixel values [A, B, C, E, F, G, I, J, K] would result in a set of 21 values, [A, B, B, B, C, E, E, E, F, F, F, F, F, G, G, G, I, J, J, J, K] the median of which would be used to replace the pixel value F which is being filtered.
Because the weighted median filtering operation allows the pixel value being filtered to be weighted more heavily than other values used in the filtering operation, the chance of the pixel value being changed can be controlled so that it is far less than that which occurs in an unweighted median filtering operation. Accordingly, weighted median filters are well suited for filtering impulse noise from images without excessive “softening” of the image that may occur when regular median filters are used.
When weights are used as part of a filtering operation, the weights can be either static, e.g., fixed at the time the filter is initially designed, or dynamic, whereby the filter weights may change with each filtering operation that is performed.
Numerous known techniques exist for dynamically generating filter weights. As will be discussed below, such known techniques may be used with various embodiments of the present invention.
Difficulties in providing enough storage locations to store the relatively large number of values used in a median filtering operation and the difficulty in implementing dedicated hardware capable of determining the median value to be output have lead to most median filtering operations, and weighted median filtering operations in particular, being implemented in software, e.g., using a general purpose computer.
Image processing, and video processing in particular, often involves the processing of large numbers of pixel values in real time, e.g., the time used to display the images being processed. The relatively slow nature of software implemented weighted median filtering operations is a major disadvantage when attempting to perform fast data processing such as real time image processing.
In view of the above, it becomes apparent that there is a need for new and improved methods of implementing weighted median filters and performing weighted median filtering operations. It is desirable that new weighted median filtering methods be relatively fast at processing data. It is also desirable that any hardware implementations be relatively efficient in the way they are implemented. It is also desirable that at least some hardware implementations be capable of supporting dynamic updating of weight values and use of large weight values without the need to provide large numbers of registers.
SUMMARY OF THE PRESENT INVENTION
As discussed above, the present invention is directed to methods and apparatus for implementing weighted median filters.
In accordance with a first embodiment of the present invention, a weighted median filter is implemented in hardware through the use a number of registers. In such an embodiment the filter apparatus comprises a number of registers equaling the sum of the weights used by the weighted median filter being implemented.
In accordance with a second embodiment of the present invention, the number of registers required to implement a median filter in hardware is greatly reduced to the point where the number of utilized registers can equal or approximately equal the number of data values used to perform the filtering operation. In such an embodiment, the required number of registers is independent of the value of the weights used.
In the second embodiment of the present invention, each data value is stored with an associated weight to be used to perform the median filtering operation. The data and associated weight values are stored, e.g., in memory locations or hardware registers. The contents of the registers are arranged, e.g., in ascending or descending order, according to the data values being used to perform the median filtering operation.
Once sorted, the output of the median filtering operation is determined by sequentially examining the weights associated with the sorted and stored data values.
In one particular embodiment, a median filter output control value (OCV) used in selecting the storage location, from a series of storage locations used to store data and weight values, which contains the data value to be output. The OCV is generated by summing the weights being used to perform the filtering operation and dividing by two. If the resulting value is a non-integer value it may be rounded up or down, as desired, to the nearest integer value so that fractional values need not be used.
In particular embodiment, the data values are sorted in descending order and stored in order in a series of storage devices along with their associated weight values. To determine which data value to output, the weight associated with the data value stored in the first storage device, i.e., the largest data value, is examined and compared to the OCV. If the weight value equals or exceeds the OCV the data value stored in the first storage device is output as the result of the median filtering operation. In the event that the output conditions are not satisfied the first weight is added to
Hitachi America Ltd.
Malzahn David H.
Straub Michael P.
Straub & Pokotylo
LandOfFree
Methods and apparatus for implementing weighted median filters does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for implementing weighted median filters, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for implementing weighted median filters will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2493756