Bitplane area correlator

• US 5,163,101 A
• Filed: 09/26/1989
• Issued: 11/10/1992
• Est. Priority Date: 10/07/1985
• Status: Expired due to Fees

• Current Assignee: Schlumberger Technologies Incorporated (Schlumberger NV)
• Original Assignee: Schlumberger Technologies Incorporated (Schlumberger NV)
• Inventors: Deering, Michael F.
• Primary Examiner(s): Moore, David K.
• Application Number:
  US07/412,619
• Time in Patent Office: 1,141 Days
• Field of Search: 382/30, 382/31, 382/32, 382/42, 382/46
• US Class Current: 382/216
• CPC Class Codes: G06F 17/153 Multidimensional correlation or convolution
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

A method and apparatus for simultaneously correlating a mask to a series of shifted positions of an image. A series of bits from a field representing an image are supplied to a number of buffer registers. A number of overlapping combinations of bits from the buffer registers are simultaneously compared with the mask bits and a signal is produced indicating the results of such comparison for each of the image bit combinations. Algebraic functions are applied to the separate combinations to relate individual comparisons. A statistical analysis is performed to determine a best fit of an image to a mask.

Claims

1. A semiconductor chip for comparing an image formed by a plurality of pixels to a mask formed by a plurality of pixels, comprising:

a first memory for storing a plurality of bits representing a contiguous plurality of said mask pixels;

a second memory for storing a plurality of bits representing a contiguous plurality of said image pixels larger in number than said plurality of mask pixels;

a plurality of input lines coupled to data inputs of said second memory;

a plurality of means for comparing said mask pixel bits to a combination of said image pixel bits;

first bus means for coupling said first memory to all of said means for comparing;

second bus means for coupling each output of said second memory to a plurality of said means for comparing such that each portion of said image pixel bits representing a single pixel is coupled to a different position in each of a plurality of said means for comparing, whereby a different combination of said image pixel bits is provided to each of said means for comparing, such that simultaneous comparisons, without requiring additional inputs, are provided for different offsets of groups of pixels in said image;

means for counting the number of digital ones or zeroes in a result of said comparison and producing a digital tally of said number for each said combination;

means for accumulating said tallies separately for each said combination;

means for algebraically combining a tally of a second mask comparison with said accumulated tally for said combination; and

means for selecting from among said accumulated tallies for said combinations a best match of said image to said masks and providing said best match to an output line.

2. A semiconductor chip for comparing an image formed by a plurality of pixels to a mask formed by a plurality of pixels, comprising:

a first memory for storing a plurality of bits representing a contiguous plurality of said mask pixels;

a second memory for storing a plurality of bits representing a contiguous plurality of said image pixels larger in number than said plurality of mask pixels;

a plurality of input lines coupled to data inputs of said second memory;

a plurality of means for comparing said mask pixel bits to a combination of said image pixels bits;

first bus means for coupling said first memory to all of said means for comparing;

second bus means for coupling each output of said second memory to a plurality of said means for comparing such that each portion of said image pixel bits representing a single pixel is coupled to a different position in each of the plurality of said means for comparing, whereby a different combination of said image pixel bits is provided to each of said means for comparing, such that simultaneous comparisons, without requiring additional inputs, are provided for different offsets of groups of pixels in said image; and

means for producing a signal indicating the results of said comparison for each said combination.

3. The apparatus of claim 2 wherein said means for producing a signal comprises means for counting the number of digital ones or zeros in said results of said comparison and producing a digital tally of said number for each said combination.

4. The apparatus of claim 2 further comprising:

means for accumulating the results of said comparison separately for each said combination; and

means for selecting from among said accumulated results for said combinations a best match of said image to said mask.

5. The apparatus of claim 4 further comprising means for algebraically combining the results of a second mask comparison for each said combination with said accumulated results for said combination.

6. The apparatus of claim 5 wherein said means for algebraically combining comprises an accumulator and an add/subtract circuit.

7. The apparatus of claim 4 further comprising means for shifting at least a portion of said accumulated results to alter the relative significance of the pixels corresponding to said portion of accumulated results.

8. The apparatus of claim 4 further comprising means for repeating said steps for a plurality of masks and means for determining a best match for said masks to said image from among said best match for each said combination.

9. The apparatus of claim 8 wherein all of said means are combined on a single semiconductor chip, and further comprising means for providing a first signal to a first output of said chip indicating a combination having said best match and means for providing a second signal to a second output of said chip indicating a value of said best match.

10. The apparatus of claim 2 wherein said means for comparing comprises means for performing a Not Exclusive OR function on each pair of bits from said image and said mask.

11. The apparatus of claim 2 wherein each said pixel is represented by at least two bits to give a grey scale and further comprising means for repeating said storing and comparing steps for a second bit of each of said pixels.

12. The apparatus of claim 2 wherein each said means for comparing comprises a boolean arithmetic logic unit.

13. The apparatus of claim 2 wherein said means for accumulating comprises a 32-bit accumulator and an add/subtract circuit.

14. The apparatus of claim 2 wherein each said first mentioned means for comparing comprises a plurality of second means for comparing a portion of said mask pixel bits representing a single pixel to a portion of said combination of image pixel bits representing a single pixel.