Efficient flexible digital filtering

Details Efficient flexible digital filtering Efficient flexible digital filtering

1997-11-15

2002-09-24

Malzahn, David H. (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S319000

Reexamination Certificate

active

06457032

ABSTRACT:

FIELD OF THE INVENTION
The invention relates to digital signal processing, and particularly to digital filtering.
BACKGROUND OF THE INVENTION
Digital signals are often filtered to enhance signal components of certain characteristics, and to attenuate components of other characteristics. For example, in digital image processing, a “low-pass” filter may be used to pass coarse image features, and to attenuate fine detail, texture, and noise. A “high-pass” filter may be used to enhance object boundaries, and to attenuate regions of nearly uniform signal intensity. Since signal features can occur over a wide range of characteristics, it is useful to be able to adjust the response of a filter over a wide range.
Digital filters are often implemented by a method in which each signal value is replaced by a weighted average of the signal value and a set of neighboring signal values. This method is known as “convolution”, the set of weights arranged in a particular pattern is known as a “kernel”, and the weights themselves, which can be positive, zero, or negative, are known as “kernel elements”. Convolution is particularly important in digital image processing, where symmetrical, non-causal filters such as Gaussian and Laplacian approximations are common.
The size of a kernel is defined to be the size of the smallest region containing all of the kernel's non-zero elements. The ability to adjust the response of a filter over a wide range is largely dependent on the ability to adjust the size of the corresponding kernel over a wide range, because adjusting the weights without adjusting the size has a relatively small effect on the response.
In the general case, convolution is expensive (i.e., requires excessive computational resources), particularly as kernel size increases, and particularly for 2D signals such as images, where computation cost is proportional to the square of the kernel size. The expensive nature of convolution-style filtering can be ameliorated by several methods used separately or in combination.
One method commonly used with image processors that support small, fixed kernel sizes involves performing the convolution multiple times, in effect cascading the corresponding filters to produce the effect of a filter having a much larger kernel. Although this method saves little or no time for 1D signals, significant time is saved for signals having two and higher dimensions. In general, this method works well only for filters that are approximately Gaussian, and is still too expensive for many practical applications.
Another method (i.e., Burt's method as described in William M. Wells, III, Efficient Synthesis of Gaussian Filters by Cascaded Uniform Filters, IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, Vol. PAMI-8, No. 2 (March 1986) (“Wells”); P. J. Burt, “Fast, hierarchical correlations with Gaussian-like kernels,” Comput. Vision Lab., Univ. Maryland, Tech. Rep. TR-860, January 1980; and P. J. Burt, “Fast algorithms for estimating local image properties,” Comput. Vision, Graphics, Image Processing, vol. 21, pp. 368-382, March 1983, incorporated herein by reference) involves increasing the kernel's size without increasing the computational cost, by inserting zero elements between a fixed number of non-zero elements. With this method, although the computational cost involved is reduced, in practice if a kernel is expanded over more than a small range, the quality of the filter's output becomes unacceptable.
Many methods for implementing multidimensional filters take advantage of the fact that many important filters (including Gaussian and Laplacian approximations) are separable, which means that each dimension of the input signal can be processed separately with a 1D filter that corresponds to the multi-dimensional filter. This reduces the computational cost problem to one of finding inexpensive methods for 1D filtering. The methods described below are based on separable filters.
John F. Canny, Finding Edges and Lines in Images, Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Catalog Number AD-A130824 (June 1983) (“Canny”), incorporated herein by reference, describes a method in which a Gaussian filter is approximated by using recursive filters. The response of a recursive filter can be adjusted over a wide range without affecting the computational cost. Since recursive filters are causal and asymmetric, the Canny method applies them in forwards and backwards directions and sums the results to approximate the symmetric Gaussian. The Canny method also applies the filters twice to improve the quality of the approximation.
Methods for convolving a signal with a uniform kernel (also known as a “boxcar” kernel) have also been developed. The elements of a uniform kernel have uniform values within a region, and have values of zero outside this region. Uniform multidimensional kernels are separable, allowing for uniform 1D convolution that can be performed with a small, fixed number of operations where the small fixed number is independent of the size of the kernel.
Wells describes a method for approximating a Gaussian filter by repeated convolution with uniform kernels. According to Wells, a cascade of uniform filters approximates a Gaussian due to the central limit theorem. It is noted that the approximation improves as the number of repeated convolutions increases, and is good after three such convolutions.
A limitation of the prior art methods is that in order to reduce computational cost, considerable flexibility in choosing the shape of the filter is sacrificed. All of the above described methods in which computational cost is independent of kernel size involve Gaussian approximations or boxcar filters. Although Gaussian filters are important in image processing, and different sized Gaussian filters can be combined to approximate band-pass and high-pass filters, there are often practical reasons to prefer other shapes not readily possible using the prior art methods.
Another limitation is that even when Gaussian filtering is desired, the prior art methods are not well-suited to widely-available, inexpensive digital hardware, including specialized circuits and general purpose computers. Although some researchers have taken computational cost into account, typically this has been only in terms of arithmetic operations such as addition and multiplication. With practical digital hardware, particularly modern general purpose computers that have effectively single-clock-cycle multipliers, the number and pattern of memory accesses has a more significant effect on computational cost than the number of arithmetic operations.
For cost and performance reasons, a digital signal processor (including a general purpose computer being used for that purpose) typically provides at least three levels of memory. The lowest level is a small (typically fewer than 128 bytes) register file having an access computational cost of essentially zero. The next level is a medium-sized bank (typically a few tens of kilobytes) of static random access memory (“SRAM”) having an access computational cost about the same as the computational cost of an addition or multiplication, independent of the pattern of access. The final level is a large, dynamic random access memory (“DRAM”) in which source and destination images are held. Data is copied from DRAM to SRAM to be accessed by the computer's processor. The access computational cost for this copying is typically equivalent to the SRAM access computational cost for long sequential access patterns, but is much higher for short or non-sequential patterns.
The Wells and Canny methods are computationally costly because they generate a significant quantity of intermediate data that is held in memory. For the 1D case, this data does not fit in the register file, so an access cost penalty equivalent to the arithmetic computational cost of an addition or multiplication operation is paid for each piece of data read or written. For separable 2D filtering, data along one dimension (i.e., rows) is sequen

Affiliated with

Also associated with

Rating

Efficient flexible digital filtering does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2862779