Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-05-28
2002-05-14
Ngo, Chuong Dinh (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06389441
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the art of digital image processing, and more specifically, to the application of filters to arrays of pixels.
BACKGROUND OF THE INVENTION
There are numerous digital filtering techniques within the prior art that have taught various methods and devices that can be employed towards digital imaging. Among these are a number of one dimensional filters such as U.S. Pat. No. 5,668,895, entitled Digital Filter for Image Processing, which teaches the use of low precision bit-shifting calculations. This prior art design is a one dimensional filter that requires additional multiplication circuits and teaches an algorithm that weights the middle element to minimize the bit-shifting error. This prior art teaching has shortcoming in that the center weighting of the middle element does not match the strict definition of an average filter. Another prior art one dimensional filter taught by U.S. Pat. No. 5,068,818, entitled Hardware implemented Moving Average Processor, that is realistically applicable in hardware only and provides little usefulness for filtering data from two-dimensional data sources. Moreover, this prior art teaching is difficult to implement in software. Still another one dimensional prior art device is U.S. Pat. No. 4,193,118, entitled Low Pass Digital Averaging Filter which is useful in hardware upon analog signals and provides little usefulness towards two-dimensional digital data sources. Furthermore, this prior art teaching does not provide the versatility for the designer to implement the filter in hardware or software. There are numerous one-dimensional filters within the prior art that provide no assistance in towards two dimensional filtering.
Other prior art devices, such as U.S. Pat. No. 4,918,742, entitled Image Processing Using Multipass Convolution with Small Kernels describes a hardware convolution circuit which is not optimized for performing a high-speed average filter. Still other prior art devices, such as U.S. Pat. No. 4,947,446, entitled Method and Circuit for Filtering Signals Representative of a Picture presents a hardware design for performing a convolution on a two-dimensional data source is also not optimized for applying a high speed average filter on a two-dimensional data-source.
Yet, still another prior art device is described in U.S. Pat. No. 5,440,503, entitled Digital Filtering Circuit Operable as a Three Stage Moving Average Filter. This patent describes a design for oversampling and integrating a signal to determine a moving average, however, does not teach a process for optimizing the number of additions, subtractions, and division operations to perform a moving average.
It should be readily apparent from the above discussion, that there remains a need within the prior art for a process that is useful for processing moving averages and can be optimized for that purpose.
SUMMARY OF THE INVENTION
The present invention addresses the foregoing shortcomings within the prior art by providing a two dimensional moving averaging filter that can efficiently average row and columns within a matrix. By reducing the number of calculations required, the concepts of the present invention allow a filter that can provide neighborhood averaging for a pixel more efficiently than prior art devices.
The preferred embodiment employs a computational element that operates on a two dimensional array of matrix values comprising N rows and M columns. A memory, within the computational element, is configured to contain a temporary memory buffer from selected portions of the matrix. The matrix positions placed into the temporary memory buffer are selected to be a subset of the entire matrix. In the preferred embodiment, employing an M×N matrix, the dimensions of the temporary memory buffer is M columns by R+1 rows, where R is some value less than N. The value R is pre-selected in accordance with desired parameters for the averaging filter that are based upon digital imaging criteria for neighborhood pixel averaging. Values for an initial set of R rows are loaded into the temporary memory and an extra row of memory locations is provided by the temporary memory. This extra row is used to hold summated values that are to be averaged. Each of the M columns within the temporary memory is summed and that summated value is placed within the extra row of the temporary memory. The summated values contained within the extra row are then used to define the neighborhood average by summing a predefined number of values from the extra row and dividing by the neighborhood size. The neighborhood employed by the preferred embodiment has the same number of rows as the temporary memory but fewer column representations. The average value for the neighborhood is placed into the image array corresponding to the center position for the neighborhood.
The summated value of the neighborhood is modified by moving one column at a time across the extra row subtracting the oldest sum position and adding the next sum position to the current value of the neighborhood. The average value for the neighborhood is then recalculated and this average value is placed in the corresponding position in the imaging array. After a row is completely filtered, the oldest row is removed from the temporary memory and is replaced by the next sequential row in the imaging array. This process is repeated until the entire image array is processed. The foregoing process illustrates a method and apparatus of filtering an image array that requires a significantly reduced amount of process steps. It will also be readily apparent to those skilled in the relevant art, that the filtering method and apparatus of the present invention can be employed upon any matrix and not only on imaging arrays.
These and other objects of the present invention are provided by the method and apparatus of filtering a two dimensional array comprising of: an electronic version of a two dimensional array of values comprising N rows and M columns; defining a filter neighborhood that is a subset of the two dimensional array having a characteristic of C columns and R rows such that R and C are odd values; duplicating a first set of R rows into a temporary memory buffer; firstly summating the first set of R rows into an extra row having a dimension of M columns; secondly summating a first set of C columns of the extra row into a first summation; averaging the first summation by dividing by the number of elements within the neighborhood filter (R×C); replacing the averaged center into its representative position into the electronic version of the two dimensional array; subtracting the oldest extra row column sum in the secondly summating step and adding the next column sum to occur in the extra row that has not been used in the first summation and repeating the averaging and recalculation until all M columns have been processed; replacing within the firstly summating step the values for the oldest row in the temporary memory buffer with values for the next row in the imaging array and continuing to calculate the averaged center for the set of R rows.
REFERENCES:
patent: 4193118 (1980-03-01), Nash et al.
patent: 4783660 (1988-11-01), Pierce
patent: 4789953 (1988-12-01), Gerrath
patent: 4816914 (1989-03-01), Ericsson
patent: 4918742 (1990-04-01), Simonds
patent: 4947446 (1990-08-01), Jutand et al.
patent: 5068818 (1991-11-01), Uramoto et al.
patent: 5163100 (1992-11-01), Mathieu et al.
patent: 5440503 (1995-08-01), Maruyama
patent: 5668895 (1997-09-01), Yamazaki et al.
patent: 5742355 (1998-04-01), Haan et al.
patent: 6249608 (2001-06-01), Ikeda et al.
Archer Greg L.
Wilkinson Larry W.
Eastman Kodak Company
Ngo Chuong Dinh
Watkins Peyton C.
LandOfFree
Two dimensional moving average 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 Two dimensional moving average filter, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two dimensional moving average filter will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2874679