VSP Connectivity pattern recognition system

• US 4,791,675 A
• Filed: 12/31/1985
• Issued: 12/13/1988
• Est. Priority Date: 12/31/1985
• Status: Expired due to Fees

• Current Assignee: Schlumberger Systems & Services Incorporated
• Original Assignee: Schlumberger Systems & Services Incorporated
• Inventors: Hunt, Neil, Deering, Michael F.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US06/815,476
• Time in Patent Office: 1,078 Days
• Field of Search: 382/41, 382/18, 382/27
• US Class Current: 382/194
• CPC Class Codes: G06V 10/457 by analysing connectivity, e.g. edge linking, connected component analysis or slices

Abstract

An image processing system for computing morphological characteristics of object regions in a binary image frame. The characteristics are generated at the frame rate. One embodiment utilizes an architecture including an interconnected delay component, bit packing component and LUT. The output values provided by the LUT are accumulated over one frame cycle to compute morphological characteristics.

Claims

1. An image processing system for processing frames of binary pixels, with each frame having N lines, 1_n, n=0, . . . , N-1, and each line having R pixel positions, P_r, r=0, . . . , R-1, the pixels being processed at a pixel scan rate, RP, the frames being processed at a frame rate, RF, a frame of pixels processed during a frame cycle, and a line of pixels processed during a line cycle, each frame including object regions of pixels having a first binary value and a background region of pixels having a second binary value, said system comprising:

line delay (LD) means having an LD input port and a set of J LD output ports, where J is a first predetermined integer, for receiving the pixels in a frame and for transferring J pixels, each at the same pixel location in J adjacent lines of said frame, to said J LD output ports;

bit packing means, having J BP input ports, each coupled to a respective one of said J LD output ports, and a set of J×

KBP output ports, including at least a first and a second BP output port, where K is a second predetermined integer, for transferring pixels from a J×

K rectangular region of said frame, including J adjacent lines and K adjacent pixel positions in each line, to said J×

K BP output ports;

a look up table (LUT), having J×

K LUT input ports, each coupled to a respective one of said J×

K BP output ports, for generating a LUT output signal encoding a selected functional value of the pixel values received at said LUT input ports and for transferring said functional values to said LUT output ports at the pixel scan rate, RP;

region labelling (RL) means, having an RL input coupled to a second BP output port and having an RL output port, said RL means for labelling each connected object region of said frame with a numeric label and for transferring the numeric label of each pixel received to said RL output port; and

first multi-statistics gathering (MSG) means, having an increment input port, adapted to receive said LUT output signal, and an index input port coupled to said RL output port and having a plurality of accumulator bins selected by the signal received at said index input port and incremented by the signal received at said increment input port, said MSG means for accumulating the functional values encoded in said output signal generated by said LUT for all pixels in a given numerically labelled region in the accumulator bin indexed by the given numerical label.

2. The invention of claim 1 further comprising:

means for synchronizing the receipt of the numeric label for a given pixel and the functional value for said given pixel at the input ports of said multi-statistics gathering means.

3. The invention of claim 2 wherein the accumulated quantity in each accumulator bin represents a morphological characteristic of an object region and wherein the accumulated quantities are generated at the frame rate FR.

4. The invention of claim 2 or 3 wherein said LUT comprises:

a random access memory (RAM) having a plurality of addressable storage locations, with each of said storage locations for storing a digital word encoding a functional value f(Y) and with each storage location selectable by a unique digital signal (Y) being the pixels transferred to said J×

K BP output ports.

5. The invention of claim 4 wherein:

one, or more, bits of each of said words stored in said LUT is equal to a morphological function of y so that the morphological function may be summed over each pixel in each object region of an image.

6. The invention of claim 5 wherein:

a first selected bit in each word stored a location addressed by Y is equal to the first binary value for all Y indicating that the pixel at the center of the J×

K region (the center pixel) is adjacent to the boundary of an object region in the frame or included in the object region and wherein the first selected bit is equal to the second binary value otherwise, with said first selected bits being the LUT output signal for performing a grow operation.

7. The invention of claim 5 wherein:

a second selected bit in each word stored in a location addressed by Y is equal to the second binary value for all Y indicating that the center pixel is positioned on the boundary of an object region or positioned in the background region and wherein the second selected bit is equal to the first binary value otherwise, with said second selected bits being the LUT output signal for a performing shrink operation.

8. The invention of claim 5 wherein:

a third selected bit in each word stored in a location addressed by Y is equal to one for all Y indicating that the center pixel is on the boundary of an object region and the third selected bit is zero otherwise;

and further comprising;

means for accumulating the values of the third selected bit over one frame cycle to generate a measure of the macroperimeter of an object region.

9. The invention of claim 5 wherein:

fourth and fifth selected bits in each word stored at a location addressed by Y are equal to the binary representation of (+1) for all Y indicating that the center pixel in an object region has one edge adjacent to the background, are equal to the binary representation for (+2) for all Y indicating that a center pixel has two edges adjacent to the background region, is equal to the binary representation for (3+) for all Y indicating that a center pixel has 3 edges adjacent to the background region, and are equal to zero otherwise;

and further comprises;

means for accumulating the values indicated by said fourth and fifth selected bits over one frame cycle to generate a measure of the microperimeter of the object region.

10. The invention of claim 5 wherein:

sixth and seventh selected bits of each word stored in a location addressed by Y are equal to the binary representation of (+1) for all Y indicating that the center pixel is at the top left hand corner of an object region, are equal to the binary representation of (-1) for all Y indicating that the center pixel is at the bottom inside right corner boundary of a hole in an object region, and are equal to zero otherwise;

and further comprising;

means for accumulating the value indicated by said sixth and seventh bits over one frame cycle to generate the Euler number of said object region.

11. The invention of claim 2 further comprising:

second multistatistics gathering having an index port coupled to said RL output port and having a plurality of accumulator bins selected by the signal received at said index port, with said second multistatistics gathering means configured to compute dimensional, positional, or orientational characteristics of said object regions.

12. An image processing system for processing frames of binary pixels, with each frame having N lines, 1_n, n=0, . . . , N-1, and each line having R pixel positions, P_r, r=0, . . . , R-1, the pixels being processed at a frame scan rate, RP, the frames being processed at a frame rate, RF, a frame of pixels processed during a frame cycle, and a line of pixels processed during a line cycle, each frame including object regions of pixels having a first binary value and a background region of pixels having a second binary value, said system comprising:

means for providing a digital signal comprising the pixel values of a J×

K region of the frame;

means for generating desired functional values, at the frame scan rate, RP, for selected values of said digital signal;

means for accumulating said selected functional values over one frame cycle with the accumulated value being the value of a morphological characteristic of an object region;

means for labelling each object region in a frame with a numerical index; and

wherein said means for accumulating comprises;

a first plurality of accumulators labelled by numerical indices; and

routing means for directing the selected functional values of said digital signals corresponding to pixels associated with an object region labelled by a given index to the accumulator in said first plurality labelled by the given index so that the morphological characteristics of each object region in a frame may be computed.

13. The invention of claim 12 further comprising:

a second plurality of accumulators labelled by numerical indices;

means for computing a selected functional value of the (x,y) co-ordinates of the pixels in a frame;

routing means for directing the selected functional values of the pixels in an object region labelled by a given index to the accumulator in said second plurality labelled by said given index so that dimensional, positional, and orientational characteristics of said object regions may be computed at the same time and in parallel to said morphological characteristics.

14. The invention of claim 12 or 13 further comprising:

means for generating data noting equivalence of the labels for mislabelled subregions of a given object region;

means for adding characteristics of the equivalent mislabelled subregion of said given object region to determine the characteristic of the given region.

15. The invention of claim 14 wherein said accumulators, means for directing, and means for adding are disposed in a multi-statistics gathering component.