Image correlation system

• US 4,864,629 A
• Filed: 12/17/1987
• Issued: 09/05/1989
• Est. Priority Date: 12/31/1985
• Status: Expired due to Fees

• Current Assignee: Schlumberger Technologies Incorporated (SLB)
• Original Assignee: Schlumberger Technologies Incorporated (SLB)
• Inventors: Deering, Michael F.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US07/134,590
• Time in Patent Office: 628 Days
• Field of Search: 382/41, 382/49, 382/33, 382/34, 382/27, 382/42, 364/728, 364/728.5, 365/230
• 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 controlling a parallel combination of correlation circuits which compare image pixels. A number of correlation circuits are provided, each having its own memory. The memories are loaded with image data with each memory being assigned a different block (region) of the image. Each memory is also loaded with an overlapping portion of an adjacent block so that a pattern can be stepped across the entire block, including a match of the first column of the pattern with the last column of the block. The loading is done by generating addresses corresponding to addresses for the source image with one or more of the most significant bits modified so that the address sequence received by the second and subsequent memories are identical to the address sequence received by the first memory. This allows the various blocks of the image in the different memories to be later simulataneously accessed in parallel using a single address sequence.

Claims

1. A controller for a plurality of image correlation circuits, each correlation circuit having a memory for storing a portion of a source image to be correlated with a pattern, each said memory having a portion of its address inputs coupled to a common address bus, comprising:

means for generation correlator addresses by adding a predetermined increment to said correlator address while controlling the most significant bit of said correlator addresses, said correlator addresses corresponding to source image addresses with at least one of the most significant bits altered, a portion of each said correlator address being transmitted on said common address bus, said correlator addresses being used for loading said memories so that portions of said source image having different source image addresses with have the same correlator addresses;

first control means for sequentially enabling said memories, said first control means being programmable so that more than one memory can receive said correlator addresses at one time to load overlapping portions of said source image in said memories; and

means for generating correlator addresses for a correlation operation such that a portion of said image corresponding to the size of said pattern is accessed, said means for generating correlator addresses including at least one register, an arithmetic logic unit having a first input coupled to an output of said register, and an accumulator having an input coupled to an output or said arithmetic logic unit and an output coupled to a second input or said arithmetic logic unit.

2. A method for correlating a plurality of overlapping portions of an image to a pattern using a plurality of correlators, each correlator having a memory, said memories having a common address bus for a first portion of the address bits for said memories, comprising the steps of:

enabling a first memory;

loading a first portion of said first memory with a first portion of said image by providing address bits on said common address bus;

enabling a second memory;

loading a second portion of said first memory and a first portion of a second memory simultaneously with a second portion of said image by

providing identical address bits on said address bus,

providing a second portion of an address to said first memory for at least one higher order address bit, and

providing an altered version of said at least one higher order address bit to said second memory so that said second portion of said image is loaded into said first portion of said second memory;

disabling said first memory;

enabling a third memory;

loading a second portion of said second memory and a first portion of said third memory simultaneously with a third portion of said image by

providing identical address bits on said address bus,

providing a second portion of an address to said second memory for at least one higher order address bit, and

providing an altered version of said at least one higher order address bit to said third memory so that said third portion of said image is loaded into said first portion of said third memory;

completing the loading of said memories;

enabling all of said memories; and

providing identical addresses to all of said memories for simultaneous comparison of the contents of said memories to said pattern by said correlators.

3. A method for comparing a pattern to a plurality of portions of an image, data representing said portions having been loaded into a plurality of memories in accordance with claim 2, said data being loaded into said memories at addresses such that each element of a column is sequenced through before the next column is reached as said addresses are linearly incremented, said pattern being smaller than said portions, comprising the steps of:

(a) providing a first address for said memories;

(b) sequentially incrementing the address of said memories by a value equal to a height of said image for a number of times equal to a number of bytes in a first dimension of said pattern plus one;

(c) incrementing the address of said memories by one less the number of bytes in said first dimension of said pattern multiplied by said image height;

(d) repeating steps (b)-(c) for a number of times equal to a second dimension of said pattern.

4. A controller for a plurality of image correlation circuits, each correlation circuit having a memory for storing a portion of an image to be correlated with a pattern, said memories having a common address bus for a portion of the address inputs for said memories, comprising:

first control means for sequentially enabling said memories, said first control means being programmable so that two memories can receive the same data simultaneously to load overlapping portions of said image in said two memories;

second control means for altering at least one higher order address bit for one of said two memories so that said data is loaded into a second portion of one of said two memories and into a first portion of the other of said two memories; and

third control means for generating identical correlator addresses for all of said memories simultaneously for a correlation operation.

5. The controller of claim 4 wherein said second control means comprises means for altering the most significant bit of said image addresses such that said correlator addresses are repeated.

6. The controller of claim 4 wherein said third control means comprises:

at least one register;

an arithmetic logic unit having a first input coupled to an output of said register; and

an accumulator having an input coupled to an output of said arithmetic logic unit and an output coupled to a second input of said arithmetic logic unit.

7. The controller of claim 4 wherein said pattern is stored in a pattern memory and the controller further comprises a counter for addressing said pattern memory.

8. The controller of claim 4 wherein said controller is coupled to a plurality of said correlation circuits, each correlation circuit including one of said image memories and further comprising:

a pattern memory; and

correlation means for simultaneously comparing a plurality of bits from said pattern memory to a plurality of combinations of a plurality of bits from said image memory.

9. The controller of claim 4 wherein said plurality of correlation circuits are coupled to a printed circuit board and further comprising a plurality of said correlation circuit boards coupled to said controller in parallel and a separate enable line coupling each of said correlation boards to said controller.