Efficient flexible digital filtering

A method for digitally processing a one-dimensional signal so as to provide for adjustment over a range of performance characteristics, the method comprising:

• providing a family of related one-dimensional discrete piecewise polynomial convolution kernels, wherein the convolution kernels are specified by at least one selectable parameter, wherein a plurality of the convolution kernels are at least 2nd order piecewise polynomials, and wherein for a plurality of convolution kernels, each has more non-zero elements than its (n+1)th difference, where ‘n’ is the order of the convolution kernel;
• selecting, based on desired performance characteristics, said at least one selectable parameter, thereby selecting a convolution kernel determined by said at least one selectable parameter, the convolution kernel being of order n;
• convolving the digital one-dimensional signal with a function that is the (n+1)th difference of the convolution kernel so as to provide a second one-dimensional digital signal;
• and
• performing discrete integration n+1 times on the second one-dimensional digital signal to produce a processed signal.

A method for digitally processing a multi-dimensional signal so as to provide for adjustment over a range of performance characteristics, the method comprising:

• for at least one dimension of the multi-dimensional signal, providing a corresponding family of related one-dimensional discrete piecewise polynomial convolution kernels, the convolution kernels being specified by at least one selectable parameter, a plurality of the convolution kernels being at least 2nd order piecewise polynomials, and for a plurality of convolution kernels, each convolution kernel having more non-zero elements than its (n+1)th difference, where ‘n’ is the order of the convolution kernel;
• for each family, selecting said at least one selectable parameter based on desired performance characteristics, thereby selecting a convolution kernel determined by said at least one selectable parameter, the convolution kernel being of order ‘n’;
• for each family, convolving the digital multi-dimensional signal along a corresponding dimension with a function that is the (n+1)th difference of the convolution kernel so as to provide a second multi-dimensional digital signal;
• and
• for each family, performing discrete integration n+1 times along the corresponding dimension of the second multi-dimensional digital signal to produce a processed signal.

A method for processing a digital image comprising rows and columns of data, the method comprising:

• storing the digital image in a first memory;
• providing (n+1) rows of column accumulators stored in a second memory;
• providing (m+1) row accumulators stored in a third memory;
• processing the digital image in a sequence of row coordinates;
• for each row coordinate, selecting a fixed number of rows at fixed offsets from the row coordinate;
• processing the selected rows in a sequence of column coordinates;
• for each column coordinate, fetching from the first memory data stored at the column coordinate of each selected row;
• multiplying data fetched from the first memory by corresponding coefficients and summing resulting products to produce a sequence of column values corresponding to the sequence of column coordinates, said coefficients being the non-zero elements of a function that is the (n+1)th difference of an nth order discrete piecewise polynomial kernel, ‘n’ being at least 2, the polynomial kernel having at least one non-linear piece, and where the function has fewer non-zero elements than the polynomial kernel has non-zero elements;
• using the (n+1) rows of column accumulators to integrate the sequence of column values (n+1) times;
• for each row coordinate, convolving the (n+1)th column accumulator with a function that is the (m+1)th difference of an mth order discrete piecewise polynomial kernel so as to provide a one-dimensional signal, ‘m’ being at least 2, the polynomial kernel having at least one non-linear piece, the function having fewer non-zero elements than the polynomial kernel has non-zero elements;
• and
• using the (m+1) row accumulators to integrate the one-dimensional signal (m+1) times to produce a processed image.

Computer software, residing on a computer-readable storage medium, including instructions for use in a computer system to digitally process a one-dimensional signal so as to provide for adjustment over a range of performance characteristics, the instructions for causing:

• providing a family of related one-dimensional discrete piecewise polynomial convolution kernels, wherein the convolution kernels are specified by at least one selectable parameter, wherein a plurality of the convolution kernels are at least 2nd order piecewise polynomials, and wherein for a plurality of convolution kernels, each has more non-zero elements than its (n+1)th difference, where ‘n’ is the order of the convolution kernel;
• selecting, based on desired performance characteristics, said at least one selectable parameter, thereby selecting a convolution kernel determined by said at least one selectable parameter, the convolution kernel being of order n;
• convolving the digital one-dimensional signal with a function that is the (n+1)th difference of the convolution kernel so as to provide a second one-dimensional digital signal;
• and
• performing discrete integration n+1 times on the second one-dimensional digital signal to produce a processed signal.

Computer software, residing on a computer-readable storage medium, including instructions for use in a computer system to digitally process a multi-dimensional signal so as to provide for adjustment over a range of performance characteristics, the instructions for causing:

• for at least one dimension of the multi-dimensional signal, providing a corresponding family of related one-dimensional discrete piecewise polynomial convolution kernels, the convolution kernels being specified by at least one selectable parameter, a plurality of the convolution kernels being at least 2nd order piecewise polynomials, and for a plurality of convolution kernels, each convolution kernel having more non-zero elements than its (n+1)th difference, where ‘n’ is the order of the convolution kernel;
• for each family, selecting said at least one selectable parameter based on desired performance characteristics, thereby selecting a convolution kernel determined by said at least one selectable parameter, the convolution kernel being of order ‘n’;
• for each family, convolving the digital multi-dimensional signal along a corresponding dimension with a function that is the (n+1)th difference of the convolution kernel so as to provide a second multi-dimensional digital signal;
• and
• for each family, performing discrete integration n+1 times along the corresponding dimension of the second multi-dimensional digital signal to produce a processed signal.

Computer software, residing on a computer-readable storage medium, including instructions for use in a computer system to digitally process a digital image comprising rows and columns of data, the instructions for causing:

• storing the digital image in a first memory;
• providing (n+1) rows of column accumulators stored in a second memory;
• providing (m+1) row accumulators stored in a third memory;
• processing the digital image in a sequence of row coordinates;
• for each row coordinate, selecting a fixed number of rows at fixed offsets from the row coordinate;
• processing the selected rows in a sequence of column coordinates;
• for each column coordinate, fetching from the first memory data stored at the column coordinate of each selected row;
• multiplying data fetched from the first memory by corresponding coefficients and summing resulting products to produce a sequence of column values corresponding to the sequence of column coordinates, said coefficients being the non-zero elements of a function that is the (n+1)th difference of an nth order discrete piecewise polynomial kernel, ‘n’ being at least 2, the polynomial kernel having at least one non-linear piece, and where the function has fewer non-zero elements than the polynomial kernel has non-zero elements;
• using the (n+1) rows of column accumulators to integrate the sequence of column values (n+1) times;
• for each row coordinate, convolving the (n+1)th column accumulator with a function that is the (m+1)th difference of an mth order discrete piecewise polynomial kernel so as to provide a one-dimensional signal, ‘m’ being at least 2, the polynomial kernel having at least one non-linear piece, the function having fewer non-zero elements than the polynomial kernel has non-zero elements;
• and
• using the (m+1) row accumulators to integrate the one-dimensional signal (m+1) times to produce a processed image.

Apparatus for digitally processing a one-dimensional signal so as to provide for adjustment over a range of performance characteristics, the apparatus comprising:

• a source of a family of related one-dimensional discrete piecewise polynomial convolution kernels, wherein the convolution kernels are specified by at least one selectable parameter, wherein a plurality of the convolution kernels are at least 2nd order piecewise polynomials, and wherein for a plurality of convolution kernels, each has more non-zero elements than its (n+1)th difference, where ‘n’ is the order of the convolution kernel;
• a selector selecting, based on desired performance characteristics, said at least one selectable parameter, thereby selecting a convolution kernel determined by said at least one selectable parameter, the convolution kernel being of order n;
• a convolver convolving the digital one-dimensional signal with a function that is the (n+1)th difference of the convolution kernel so as to provide a second one-dimensional digital signal;
• and
• an integrator performing discrete integration n+1 times on the second one-dimensional digital signal to produce a processed signal.

Apparatus for digitally processing a multi-dimensional signal so as to provide for adjustment over a range of performance characteristics, the apparatus comprising:

• a kernel source, for at least one dimension of the multi-dimensional signal, providing a corresponding family of related one-dimensional discrete piecewise polynomial convolution kernels, the convolution kernels being specified by at least one selectable parameter, a plurality of the convolution kernels being at least 2nd order piecewise polynomials, and for a plurality of convolution kernels, each convolution kernel having more non-zero elements than its (n+1)th difference, where ‘n’ is the order of the convolution kernel;
• a selector, for each family, selecting said at least one selectable parameter based on desired performance characteristics, thereby selecting a convolution kernel determined by said at least one selectable parameter, the convolution kernel being of order ‘n’;
• a convolver, for each family, convolving the digital multi-dimensional signal along a corresponding dimension with a function that is the (n+1)th difference of the convolution kernel so as to provide a second multi-dimensional digital signal;
• and
• for each family, performing discrete integration n+1 times along the corresponding dimension of the second multi-dimensional digital signal to produce a processed signal.

Apparatus for processing a digital image comprising rows and columns of data, the apparatus comprising:

• first memory storing the digital image;
• a second memory storing (n+1) rows of column accumulators;
• a third memory storing (m+1) row accumulators;
• a processor processing the digital image in a sequence of row coordinates;
• a selector, for each row coordinate, selecting a fixed number of rows at fixed offsets from the row coordinate;
• a processor processing the selected rows in a sequence of column coordinates;
• a fetcher, for each column coordinate, fetching from the first memory data stored at the column coordinate of each selected row;
• a multiplier multiplying data fetched from the first memory by corresponding coefficients and summing resulting products to produce a sequence of column values corresponding to the sequence of column coordinates, said coefficients being the non-zero elements of a function that is the (n+1)th difference of an nth order discrete piecewise polynomial kernel, ‘n’ being at least 2, the polynomial kernel having at least one non-linear piece, and where the function has fewer non-zero elements than the polynomial kernel has non-zero elements;
• an integrator using the (n+1) rows of column accumulators to integrate the sequence of column values (n+1) times;
• a convolver, for each row coordinate, convolving the (n+1)th column accumulator with a function that is the (m+1)th difference of an mth order discrete piecewise polynomial kernel so as to provide a one-dimensional signal, ‘m’ being at least 2, the polynomial kernel having at least one non-linear piece, the function having fewer non-zero elements than the polynomial kernel has non-zero elements;
• and
• an integrator, using the (m+1) row accumulators to integrate the one-dimensional signal (m+1) times to produce a processed image.