System for expedited computation of laplacian and gaussian filters and correlation of their outputs for image processing

Claim 2

Apparatus for calculating an approximation of the Laplacian of a selected point in an image having n nearby points, the selected point and the nearby points each having a digital value representative of an aspect of the point, the apparatus comprising: summing means connected to receive the digital values of the nearby points and add them together to produce a sum; multiplying means connected to receive the digital value of the selected point and multiply it by n to produce a product; and subtracting means connected to receive the product and the sum, and subtract the sum from the product to thereby provide an approximation of the Laplacian.

Claim 3

Apparatus as in Claim 1 wherein the n nearby points comprise four points respectively disposed above, below, to the left, and to the right of the se­lected point, and wherein the summing means comprises: a first adder for adding two of the four dig­ital values of the points together; and a second adder for adding the other two of the four digital values of the nearby points together.

Claim 4

Apparatus as in Claim 2 wherein the sum­ming means further comprises a third adder connected to receive signals from each of the first and second adders and in response thereto produce the sum.

Claim 5

Apparatus as in Claim 1 wherein n = 2 x , where x is an integer, and wherein the multiplying means comprises a shifter for shifting the digital value of the selected point x places to the left.

Claim 6

Apparatus for processing an input image to provide a filtered image approximating a Gaussian of the input image, the apparatus comprising: means for determining a digital value for a selected point and for each of a plurality of points disposed about the selected point in the input image; first summing means connected to receive the digital values of each of the plurality of points for weighting the digital value of each of the plurality by a power of two and adding the resulting weighted values together to provide a weighted sum; second summing means connected to receive the weighted sum and the digital value of the selected point and add them together to thereby provide a digital value approximating a Gaussian for a point in the filtered image.

Claim 7

Apparatus for processing an input image to provide a filtered image approximating a Gaussian of the input image, the apparatus comprising: means for determining a digital value for a selected point and for each of a plurality of points disposed about the selected point in the input image; first summing means connected to receive the digital values of each of the plurality of points for weighting the digital value of each of the plurality by a power of two and adding the resulting weighted values together to provide a weighted sum; second summing means connected to receive the weighted sum and the digital value of the selected point and add them together to thereby provide a digital value approximating a Gaussian for a point in the filtered image.

Claim 8

Apparatus as in Claim 5 wherein the first summing means comprises only shifting means coupled to adding means.

Claim 9

Apparatus as in Claim 5 wherein the first summing means comprises: a first adder connected to receive the digital values of the two points and add them together to provide a first sum; and a first shifter connected to receive the first sum and shift it one place right to provide the weighted sum.

Claim 10

Apparatus as in Claim 7 wherein the second summing means comprises: a second adder connected to receive the digital value of the selected point and the weighted sum and add them to provide the digital value approximating the Gaussian.

Claim 11

Apparatus for calculating an approxima­tion of the Gaussian of Laplacian of a selected point in an image having n nearby points arranged in rows and columns, the selected point and the nearby points each having a digital value, the apparatus comprising: summing means connected to receive the digital values of the nearby points and add them together to produce a first sum; first multiplying means connected to receive the digital value of the selected point and multiply it by n to produce a first product; subtracting means connected to receive the first product and the first sum and subtract the first sum from the first product to thereby provide an ap­proximation of the Laplacian of the selected point; first repeating means for calculating the approximation of the Laplacian for each point in a re­gion of the image; second summing means connected to receive the Laplacian values of a subset of the points in the region of the image and add them, the subset of nearby points comprising a plurality of points along a line extending through the selected point, the second summing means also including weighting means for weighting the digital values of the nearby points according to their position with respect to the selected point to thereby provide a weighted sum; third summing means connected to receive the digital value of the Laplacian of the selected point and the weighted sum and add them together to thereby provide an approximation of the Gaussian of the Laplacian of the selected point; and second repeating means for repeating selected ones of the above steps to thereby provide the Gaussian of the Laplacian for each point in the image.

Claim 12

Apparatus for calculating an approxima­tion of the Gaussian of Laplacian of a selected point in an image having n nearby points arranged in rows and columns, the selected point and the nearby points each having a digital value, the apparatus comprising: summing means connected to receive the digital values of the nearby points and add them together to produce a first sum; first multiplying means connected to receive the digital value of the selected point and multiply it by n to produce a first product; subtracting means connected to receive the first product and the first sum and subtract the first sum from the first product to thereby provide an ap­proximation of the Laplacian of the selected point; first repeating means for calculating the approximation of the Laplacian for each point in a re­gion of the image; second summing means connected to receive the Laplacian values of a subset of the points in the region of the image and add them, the subset of nearby points comprising a plurality of points along a line extending through the selected point, the second summing means also including weighting means for weighting the digital values of the nearby points according to their position with respect to the selected point to thereby provide a weighted sum; third summing means connected to receive the digital value of the Laplacian of the selected point and the weighted sum and add them together to thereby provide an approximation of the Gaussian of the Laplacian of the selected point; and second repeating means for repeating selected ones of the above steps to thereby provide the Gaussian of the Laplacian for each point in the image.

Claim 15

A method as in Claim 10 wherein the Gaussian filter comprises a one-dimensional Gaussian filter and the method further comprises: repeating the step of applying a one-dimensional Gaussian filter a selected number of times, each time using the result of the preceding time, to thereby provide an expanded Gaussian filtered third region.

Claim 18

A method as in Claim 12 further comprising: applying a second one-dimensional Gaussian filter to a part of the expanded Gaussian filtered region, the second one-dimensional filter being orthogonal to the first one-dimensional filter; and repeating the step of applying a second one-­dimensional filter a selected number of times, each time using the result of the preceding time, to provide a second expanded Gaussian filtered region.

Claim 19

A method as in Claim 11 further comprising: applying a second one-dimensional filter to a part of the third region to provide a Gaussian filtered fourth region, the second one-dimensional Gaussian filter being orthogonal to the first one-dimensional Gaussian filter; and repeating the step of applying a second one-­dimensional Gaussian filter a selected number of times, each time using the result of the preceding time, to provide an expanded Gaussian filtered fourth region.

Claim 20

A method as in Claim 14 wherein the step of applying a Laplacian filter to a selected region of the input image comprises on a point-by-point basis in the input image: calculating the sum of the digital values of four points disposed adjacent the selected point; and subtracting the result from four times the value of the selected point.

Claim 21

A method as in Claim 10 further comprising following the step of repeating the step of applying the first one-dimensional Gaussian filter a step of comprising: repeating the step of applying the first one-­dimensional Gaussian filter three times to every other point in the image, each time using the results of the preceding time.

Claim 22

Apparatus for correlating a first image with a second image comprising: first storage means for storing the first image; second storage means for storing the second image; first comparison means connected to both the first and second storage means for receiving portions of the first and second images and comparing them with each other, and in response thereto supplying an output signal; first address generating means connected to the first storage means for generating a first address to control which portion of the first stored image is supplied to the comparison means; second address generating means connected to the second storage means for generating a second address, a second address controlling which portion of the second stored image is supplied to the comparison means; and first measurement means connected to the com­parison means for recording the output signals.

Claim 23

Apparatus for correlating a first image with a second image comprising: first storage means for storing the first image; second storage means for storing the second image; first comparison means connected to both the first and second storage means for receiving portions of the first and second images and comparing them with each other, and in response thereto supplying an output signal; first address generating means connected to the first storage means for generating a first address to control which portion of the first stored image is supplied to the comparison means; second address generating means connected to the second storage means for generating a second address, a second address controlling which portion of the second stored image is supplied to the comparison means; and first measurement means connected to the com­parison means for recording the output signals.

Claim 24

Apparatus as in Claim 17 further compris­ing: third address generating means connected to the first storage means for generating a third address, the third address controlling the location in the first storage means at which the first image is stored; and fourth address generating means connected to the second storage means for generating a fourth address, the fourth address controlling the location in the second storage means at which the second image is stored.

Claim 25

Apparatus as in Claim 17 wherein the portions of the first and second images compared by the comparison means comprise a single point from each of the first and second images.

Claim 26

Apparatus as in Claim 19 wherein the comparison means supplies a first level signal whenever the points correspond and a second level signal whenever they do not.

Claim 27

Apparatus as in Claim 17 further compris­ing: at least one-third storage means for storing the copy of the first image; second comparison means connected to receive from both the second and third storage means portions of the second image and the copy of the first image for comparing them with each other and in response thereto supplying an output signal; fifth address generating means connected to the at least one-third storage means for generating a fifth address, the address thereby generating and con­trolling what portion of the first stored images sup­plied to the comparison means; and second measurement means connected to the at least one-third comparison means for recording the out­put signals.

Claim 28

Apparatus as in Claim 21 wherein a dif­ferent portion of the first image is compared to the second image by the first comparison means than the portion of the first image compared to the second image by the second comparison means.

Claim 29

Apparatus as in Claim 17 wherein the first address generating means comprises: first means for defining a center point of the portion of the first stored image; and second means for defining a sampling pattern about the center point of the portion of the first stored image.