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

• US 5,119,444 A
• Filed: 07/22/1986
• Issued: 06/02/1992
• Est. Priority Date: 07/22/1986
• Status: Expired due to Fees

• Current Assignee: Schlumberger Systems & Services Incorporated (Schlumberger NV)
• Original Assignee: Schlumberger Technologies Incorporated (SLB)
• Inventors: Nishihara, H. Keith
• Primary Examiner(s): Picard, Leo P.
• Assistant Examiner(s): Donovan, Lincoln
• Application Number:
  US06/888,535
• Time in Patent Office: 2,142 Days
• Field of Search: 364/728, 364/775, 364/822, 364/819, 382/8, 382/41, 382/45
• US Class Current: 382/263
• CPC Class Codes: G06T 5/20 using local operators

Abstract

Apparatus is disclosed for rapidly computing the Gaussian of Laplacian convolution of the point values in an image. Speed and hardward efficiency are achieved through the use of the separability of higher dimensional Gaussians, the binomial approximation to the one-dimensional Gaussian, the zero mean of Laplacian filtered signals, the reduced sampling requirements for low pass filtered signals, and a binary correlator that does many correlations in parallel, allows correction for geometric distortion and variable sampling density.

Claims

1. Apparatus for calculating an approximation of the Laplacian of a selected point in an image of an object, the selected point 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 an integer to produce a product, and wherein the multiplying means comprises a shifter for shifting the digital value of the selected point a number of places to the left the same as the integer;

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, the subtracting means comprising an adder, and the sum is inverted before being supplied to the adder; and

wherein the Laplacian is used to control apparatus for positioning the object.

2. 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 selected point, and wherein the summing means comprises:

a first adder for adding two of the four digital values of the points together; and

a second adder for adding the other two of the four digital values of the points together.

3. Apparatus as in claim 2 wherein the summing 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.

4. Apparatus as in claim 3 wherein the digital value is representative of the intensity of the point.

5. Apparatus for processing an input image of an object 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, the first summing means comprising only shifting means coupled to adding means;

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; and

wherein the Gaussian is used to control apparatus for positioning the object.

6. Apparatus as in claim 5 wherein the plurality of points comprises two points and the selected point is disposed on a straight line extending between the two points.

7. Apparatus as in claim 6 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.

8. 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.

9. Apparatus as in claim 8 further comprising:

a second shifter connected to receive the digital value approximating the Gaussian and shift it one place right to normalize the Gaussian.

10. Apparatus for calculating an approximation of the Gaussian of Laplacian of a selected point in an image of an object, the 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 approximation of the Laplacian of the selected point;

first repeating means for calculating the approximation of the Laplacian for each point in a region of the image;

second summing means connected to receive the Laplacian values of a subset of the point 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;

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; and

using the resulting Gaussian of the Laplacian to control apparatus for position the object in a desired manner.