Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-05-11
2004-06-22
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S304000
Reexamination Certificate
active
06754684
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention pertains to digital data processing and, more particularly, to improved methods and apparatus for performing median filter operations.
A wide variety of computing and image processing applications call for the processing of two dimensional images, typically for printing the image or for electronic display such as by display on a computer screen. Very often, the images needing display will have any number of random, impulse or single pixel noise problems that can be corrected using an appropriate filtering technique. One popular filtering technique for addressing these noise issues is median filtering. A median filter computes the output value of each pixel in an image as the median value of pixels in a small neighborhood around the pixel of interest—essentially replacing each pixel output with the median output value of its neighborhood. A common neighborhood used in median filtering is a 9-pixel, 3×3 square centered on the pixel of interest.
Because images can contain large numbers of pixels, and also because some applications call for the filtering of large numbers of images, execution time for calculating medians has a large impact on the performance of the software applications that employ median filtering. One approach to improving the performance of median filters has been to perform the filtering using SIMD processors. In a SIMD (single instruction, multiple data) processor, a single instruction operates on a vector register that holds multiple values. This is in contrast to a conventional processor in which each instruction operates on only a single data value. One class of recent SIMD processors employ the AltiVec™ technology, of Motorola, that is capable of concurrently operating on vectors with 4, 8 or 16 values.
Notwithstanding the benefits of array processors such as the AltiVec™, image processing times can be significantly reduced by even slight improvements in methods for calculating medians or in programming techniques that increase the throughput of median calculations through the array processor, the throughput typically being measured in clock cycles per pixel, or alternatively in clock cycles per (16 byte) vector.
In view of the foregoing, an object of the invention is to provide improved methods and apparatus for digital image processing.
A more particular object is to provide such methods and apparatus as permit the rapid execution of median filtering on a two dimensional data set.
SUMMARY OF THE INVENTION
These and other objects are attained by the present invention which provides, in some aspects, novel methods for calculating median filter values that increase the speed with which the calculation can be performed.
A method according to one aspect of the invention provides for rapidly performing a median filter calculation for a value at a predetermined position in a matrix of values representing a neighborhood about the predetermined position. The method includes ordering the values in each column of the matrix to create an ordered matrix; determining a maximum value for a row of the ordered matrix having the lowest values; determining a median value for a row of the ordered matrix having middle values; and determining a minimum value for a row of the ordered matrix having the highest values. Based on these determinations, the median filter value for the neighborhood can be calculated as a median value of the maximum value for a row of the ordered matrix having the lowest values, median value for a row of the ordered matrix having middle values, and minimum value for a row of the ordered matrix having the highest values. The calculated median filter value can then be output as necessary. The rows of the matrices can conveniently be represented as vectors and the ordering and determining steps can be performed as vector operations.
In a further aspect, the invention provides a method for rapidly performing a plurality of median filter calculations for a value at a predetermined position in a matrix of values representing a 3×3 neighborhood about the predetermined position. The method includes inputting rows for median filtering, the number of rows being one more than the number of rows in the neighborhood; presorting rows that will participate in more than one median filter calculation; separating the input rows into separate matrices, each having the pre-sorted rows and one unsorted row; ordering the values in each column of each matrix to result in ordered matrices; determining a maximum value for a row of each ordered matrix having the lowest values; determining a median value for a row of each ordered matrix having middle values determining a minimum value for a row of each ordered matrix having the highest values; and determining the median filter values as a median value of the previously determined maximum value for a row of each ordered matrix having the lowest values, median value for a row of each ordered matrix having middle values, and minimum value for a row of each ordered matrix having the highest values.
In either aspect, the matrix rows can be represented as vectors that include more than three values, and thus more values than are found in a 3×3 neighborhood for a single median filter calculation. The calculations on the ordered matrices can be performed using vector operations to simultaneously result in a plurality of triplet maximum, median and minimum values stored in a single output vector. The calculation of the median filter value corresponding to the plurality of triplet maximum, median and minimum values can then also be carried out with four vector operations to simultaneously produce a plurality of median filter results. In addition, vector loading and processing instructions can be interleaved to reduce the overall number of clock cycles. An apparatus and computer code product for carrying out the invention are also described.
These and other aspects of the invention have the advantage of permitting rapid median filter calculations without excessive use of system resources.
REFERENCES:
patent: 5900006 (1999-05-01), Yoon
patent: 5912826 (1999-06-01), Bangham et al.
patent: 6058405 (2000-05-01), Kolte et al.
patent: 6160913 (2000-12-01), Lee et al.
patent: 6163324 (2000-12-01), Holder
patent: 6603877 (2003-08-01), Bishop
Kolte, et al., “A Fast Median Filter Using AltiVec,”Proceedings of the IEEE International Conference on Computer Design, Copyright © 1998 Institute of Electrical and Electronics Engineers, Inc.
Performance Table: AltiVec Performance Comparison Table (date of publication Sep. 12, 1997) Internet Printout: wysiwyg://2/http://developer.apple . . . hardware/ve/performance_table.html.
Mai Tan V.
Mercury Computer Systems, Inc.
Nutter McClennen & Fish
Powsner David J.
LandOfFree
Method and apparatus for median filter on SIMD architecture... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for median filter on SIMD architecture..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for median filter on SIMD architecture... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3346425