Spatial filter for surface texture navigation

• US 6,049,338 A
• Filed: 04/01/1998
• Issued: 04/11/2000
• Est. Priority Date: 04/01/1998
• Status: Expired due to Term

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.), Hewlett-Packard Company (HP Inc.), Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Anderson, Mark A., Moore, Charles E.
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US09/053,294
• Time in Patent Office: 741 Days
• Field of Search: 345/419, 345/420, 345/429, 345/430, 345/433, 345/118, 345/121
• US Class Current: 382/260
• CPC Class Codes: G06T 5/20 using local operators

Abstract

A spatial filter having coefficients selected and distributed within an array, so that when the array is divided non-diagonally into four equal quadrants, (1) the coefficients are of constant sign within each quadrant; (2) coefficients in diagonally opposed quadrants have like sign; and (3) coefficients in non-diagonally neighboring quadrants have unlike sign. In a preferred embodiment, coefficients cause the array to form a "saddle" shape when the coefficient values are representative of the local slope on a surface described by the array. This "saddle" shape enables improved filtration properties. The inventive spatial filter is further advantageously embodied in architecture comprising an array of individual calculation modules corresponding to the filter array. Rows of modules are coupled together in parallel. The input signal is fed to each row concurrently via FIFO buffers, enabling concurrent calculation operations. After calculation, output values for each module are accumulated and summed, the result being placed into an output stream. The FIFO buffers then present the next input values in the input stream to the calculation modules, and so on. The result is a low-latency "streaming" filtration that is further economical on hardware, requiring only FIFO storage resources. Advantageously, the entire inventive filter may be conveniently deployed as a digital signal processor ("DSP") on a unitary integrated circuit chip.

Claims

1. A spatial filter for filtering a pixelated input image, comprising:

means for transforming the input image into an input array of pixel values each representative of a color shade of a corresponding pixel in the input image;

a filter array of filtration coefficients, the filter array not greater in any dimension than the input array and smaller than the input array in at least one dimension, the coefficients for multiplication with corresponding pixel values when the filter array is overlaid on the input array relative to a selected reference pixel value;

the coefficients distributed within the filter array so that when the filter array is divided into four equal non-diagonal quadrants, (1) coefficients are of constant sign within each quadrant, (2) coefficients in diagonally opposing quadrants have like sign, and (3) coefficients in non-diagonally neighboring quadrants have unlike sign;

means for calculating an output value for the selected reference pixel value, the output value being the numeric sum of said multiplications of coefficients and corresponding pixel values;

means for establishing an output array of output values, the output array formed by overlaying the filter array on the input array for a selected group of reference pixel values; and

means for transforming the output array into a signal representative of an output image.

2. The spatial filter of claim 1, in which the input array, the means for transforming the input image, the filter array, the means for calculating an output value, the means for establishing an output array, and the means for transforming the output array are all deployed on a unitary integrated circuit chip.

3. The spatial filter of claim 2, in which the chip is a CMOS chip.

4. The spatial filter of claim 1, in which the filter array is selected from the group consisting of:

space="preserve" listing-type="tabular">______________________________________ (a) -4 -2 2 4 -2 -1 1 2 2 1 -1 -2 4 2 -2 -4 ;

(b) -1 -1 1 1 -1 -1 1 1 1 1 -1 -1 1 1 -1 -1 ;

(c) 0 0 0 0 0 -1 1 0 0 1 -1 0 0 0 0 0 ;

(d) 0 0 0 0 -2 -1 1 2 2 1 -1 -2 0 0 0 0 ;

(e) -2 -1 1 2 2 1 -1 -2 ;

(f) -1 0 1 0 0 0 1 0 -1 ; and

(g) -4 -2 0 2 4 -2 -1 0 1 2 0 0 0 0 0 2 1 0 -1 -2 4 2 0 -2 -4 . ______________________________________

5. The spatial filter of claim 1, in which the coefficients are further distributed within the filter array to form a saddle shape when said coefficients are representative of the local slope of a surface described by the filter array.

6. The spatial filter of claim 1, in which the coefficients are 8 bits wide and the output values are no more than 4 bits wide.

7. Deployed on a unitary CMOS chip, a spatial filter for filtering a pixelated input image, comprising:

means for transforming the input image into an input array of pixel values each representative of a color shade of a corresponding pixel in the input image;

a filter array of filtration coefficients, the filter array not greater in any dimension that the input array and smaller than the input array in at least one dimension, the coefficients for multiplication with corresponding pixel values when the filter array is overlaid on the input array relative to a selected reference pixel value;

the filter array selected from the group consisting of;

space="preserve" listing-type="tabular">______________________________________ (a) -4 -2 2 4 -2 -1 1 2 2 1 -1 -2 4 2 -2 -4 ;

(b) -1 -1 1 1 -1 -1 1 1 1 1 -1 -1 1 1 -1 -1 ;

(c) 0 0 0 0 0 -1 1 0 0 1 -1 0 0 0 0 0 ;

(d) 0 0 0 0 -2 -1 1 2 2 1 -1 -2 0 0 0 0 ;

(e) -2 -1 1 2 2 1 -1 -2 ;

(f) -1 0 1 0 0 0 1 0 -1 ;

and (g) -4 -2 0 2 4 -2 -1 0 1 2 0 0 0 0 0 2 1 0 -1 -2 4 2 0 -2 -4 ;

______________________________________

means for calculating an output value for the selected reference pixel value, the output value being the numeric sum of said multiplications of coefficients and corresponding pixel values;

means for establishing an output array of output values, the output array formed by overlaying the filter array on the input array for a selected group of reference pixel values; and

means for transforming the output array into a signal representative of an output image.

8. The spatial filter of claim 7, in which the coefficients are 8 bits wide and the output values are no more than 4 bits wide.

9. A method for spatially filtering a pixelated input image, comprising the steps of:

(a) transforming the input image into an input array of pixel values each representative of a color shade of a corresponding pixel in the input image;

(b) applying a filter array of filtration coefficients to the input array, the filter array not greater in any dimension than the input array and smaller than the input array in at least one dimension, the coefficients distributed within the filter array so that when the filter array is divided into four equal non-diagonal quadrants, (1) coefficients are of constant sign within each quadrant, (2) coefficients in diagonally opposing quadrants have like sign, and (3) coefficients in non-diagonally neighboring quadrants have unlike sign;

(c) indexing movement of the filter array over the input array to a corresponding selected group of reference pixel values, each different location that the filter array may be overlaid on the input array indexed to a separate unique reference pixel value in the group;

(d) overlaying the filter array on the input array in a position corresponding to a selected one in the group of reference pixel values;

(e) multiplying the filtration coefficients with corresponding pixel values thereunder when the filter array is in said position in step (d);

(f) numerically summing products obtained in step (e) into an output value for said selected one in the group of reference pixel values;

(g) repeating steps (d), (e) and (f) for each reference pixel value in the group so as to establish a corresponding output array of output values wherein the output array describes movement of the filter array over the input array; and

(h) transforming the output array into a signal representative of an output image.

10. The method of claim 9, in which steps (b) through (g) are performed by a digital signal processor deployed on an integrated circuit chip.

11. The method of claim 9, in which the filter array is selected from the group consisting of:

space="preserve" listing-type="tabular">______________________________________ (a) -4 -2 2 4 -2 -1 1 2 2 1 -1 -2 4 2 -2 -4 ;

(b) -1 -1 1 1 -1 -1 1 1 1 1 -1 -1 1 1 -1 -1 ;

(c) 0 0 0 0 0 -1 1 0 0 1 -1 0 0 0 0 0 ;

(d) 0 0 0 0 -2 -1 1 2 2 1 -1 -2 0 0 0 0 ;

(e) -2 -1 1 2 2 1 -1 -2 ;

(f) -1 0 1 0 0 0 1 0 -1 ; and

(g) -4 -2 0 2 4 -2 -1 0 1 2 2 1 0 -1 -2 4 2 0 -2 -4 . ______________________________________

12. The method of claim 9, in which the coefficients are further distributed within the filter array to form a saddle shape when said coefficients are representative of the local slope of a surface described by the filter array.

13. A computer program product having computer-readable logic recorded thereon for enabling a digital signal processor (DSP) to spatially filter a pixelated input image, the computer program product comprising:

a storage medium accessible and readable by the DSP; and

a computer program stored on the storage medium, the computer program comprising;

means for receiving an input array of pixel values each representative of a color shade of a corresponding pixel in the input image;

a filter array of filtration coefficients, the filter array not greater in any dimension than the input array and smaller than the input array in at least one dimension, the coefficients for multiplication with corresponding pixel values when the filter array is overlaid on the input array relative to a selected reference pixel value;

the coefficients distributed within the filter array so that when the filter array is divided into four equal non-diagonal quadrants, (1) coefficients are of constant sign within each quadrant, (2) coefficients in diagonally opposing quadrants have like sign, and (3) coefficients in non-diagonally neighboring quadrants have unlike sign;

means for calculating an output value for the selected reference pixel value, the output value being the numeric sum of said multiplications of coefficients and corresponding pixel values; and

means for establishing an output array of output values, the output array formed by overlaying the filter array on the input array of a selected group of reference pixel values, the output array representative of a filtered output image.

14. The computer program product of claim 13, in which the DSP is deployed on a unitary integrated circuit chip.

15. The computer program product of claim 14, in which the chip os a CMOS chip.

16. The computer program product of claim 13, in which the filter array is selected from the group consisting of:

space="preserve" listing-type="tabular">______________________________________ (a) -4 -2 2 4 -2 -1 1 2 2 1 -1 -2 4 2 -2 -4 ;

(b) -1 -1 1 1 -1 -1 1 1 1 1 -1 -1 1 1 -1 -1 ;

(c) 0 0 0 0 0 -1 1 0 0 1 -1 0 0 0 0 0 ;

(d) 0 0 0 0 -2 -1 1 2 2 1 -1 -2 0 0 0 0 ;

(e) -2 -1 1 2 2 1 -1 -2 ;

(f) -1 0 1 0 0 0 1 0 -1 ; and

(g) -4 -2 0 2 4 -2 -1 0 1 2 0 0 0 0 0 2 1 0 -1 -2 4 2 0 -2 -4 . ______________________________________

17. The computer program product of claim 13, in which the coefficients are further distributed within the filter array to form a saddle shape when said coefficients are representative of the local slope of a surface described by the filter array.