Spatial median filter

Details Spatial median filter Spatial median filter

2001-01-16

2004-07-06

Malzahn, David H. (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06760737

ABSTRACT:

TECHNICAL FIELD
This invention relates to filters and, more particularly, to determining the median of a plurality of values.
BACKGROUND OF THE INVENTION
A standard prior known approach in finding a median of N values is to fully sort the sequence of N values by arranging the N values in the sequence in either ascending or descending order, e.g., 4, 10, 20, . . . or . . . , 20, 10, 4, respectively, and then picking the middle value of the sorted sequence of N values. The optimal number of comparisons needed to sort N values is in the order of K*N*log(N), where K is some constant independent of N. This process of finding a median is not optimal, because the sorting is more than what is needed to locate the median. Sorting arranges all values in an ascending or a descending order. It produces the location of every value in the sequence, not only the median. In locating a median, only the median itself is of interest, it is not necessary to know the order of other values in the sequence. Therefore, using a full sorting process to locate the median is not optimal, and it requires making significantly more comparisons than are actually necessary.
SUMMARY OF THE INVENTION
The problems and limitations of prior spatial median filters is overcome in determining a median of a plurality of values, in accordance with the invention, by dividing the plurality of values into a plurality of groups of values. The values in each of the groups are sorted to determine its median. Then, the medians of the plurality of groups are fully sorted. Certain sorted values are eliminated from prescribed ones of the groups in accordance with prescribed criteria based on the number of values in the group and the median value of the group values. The remaining values are sorted to determine the median of the plurality of values.
A technical advantage of the invention is that fewer comparisons are required to determine the median of a plurality of values than in prior known arrangements. Consequently, this results in a significantly simpler implementation of a spatial median filter including an embodiment of the invention.
Another technical advantage of the invention is that in the process of determining the median values that are less than or equal and values that are greater than or equal to the median are also identified without any additional processing.


REFERENCES:
patent: 4682230 (1987-07-01), Perlman et al.
patent: 5384865 (1995-01-01), Loveridge
patent: 5737251 (1998-04-01), Kohno et al.
patent: 5900006 (1999-05-01), Yoon
patent: 5968111 (1999-10-01), Bae et al.
patent: 6199084 (2001-03-01), Wiseman

Affiliated with

Also associated with

Rating

Spatial median filter does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Spatial median filter, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spatial median filter will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3245556