System and method for extracting image data

• US 6,041,148 A
• Filed: 02/19/1998
• Issued: 03/21/2000
• Est. Priority Date: 10/17/1997
• Status: Expired due to Term

• Current Assignee: Microscan Systems Inc (Omron Corporation)
• Original Assignee: Acuity Brands, Inc.
• Inventors: Wilt, Michael J.
• Primary Examiner(s): Au, Amelia
• Assistant Examiner(s): Wu, Jingge
• Application Number:
  US09/025,937
• Time in Patent Office: 761 Days
• Field of Search: 382/171, 382/173, 382/180, 382/205, 382/206, 382/303, 382/307, 382/308, 382/284, 382/304
• US Class Current: 382/308
• CPC Class Codes: G06F 13/4027 using bus bridges G06F13/4022 takes precedence
• CPC Class Codes: G06T 1/60 Memory management
• CPC Class Codes: G06T 3/4007 based on interpolation, e.g. bilinear interpolation image demosaicing G06T3/4015; edge-driven or edge-based scaling G06T3/403
• CPC Class Codes: G06T 5/20 using local operators

Abstract

A data extraction processor receives data, such as image data, at a high rate of speed and generates processed results, generally at a much lower overall data rate. This sort of processing is particularly useful for machine vision image data, because it can reduce a large image data set to a much smaller data set that is more immediately useful for the currently running application. The data extraction processor may include a segmentation processor, a gradient processor, or other similar types of data extraction processors. The disclosed data extraction processor includes a data flow controller which provides image data to the processors and receives the results from the processors. The data flow controller includes at least one FIFO (first-in, first-out) memory, which allows for the provision of data to the data extraction processor and the receipt of result data therefrom to occur at different rates. Since data extraction algorithms usually generate much less data that they receive, the data flow controller stalls the flow of output data while the analysis proceeds through the data. In some image-dependent situations, however, the analysis may generate more data than it receives. In these situations, the data flow controller stalls the incoming data while the additional results are generated.

Claims

1. A data extraction system comprising:

at least one data storage memory for storing data formatted into a plurality of data samples, each of said plurality of data samples having multiple bits;

a data extraction processor, for receiving said data from said data storage memory one processor word at a time, wherein a processor word includes at least two of said data samples, for simultaneously processing said at least two of said data samples in each said processor word, and for generating at least one result record containing information extracted from said data samples in at least one said processor word, said data extraction processor comprising a segmentation processor including;

a label computation engine, coupled to said data flow controller, for simultaneously receiving said data samples in each said processor word, for identifying transitions between said data samples and generating transition bit signals for each potential transition, and for computing a label code for each said potential transition using said transition bit signals;

a label row FIFO shifter, coupled to said label computation engine, for receiving and storing said label code for each said potential transition;

a neighborhood computation unit, coupled to said label computation engine and to said label row FIFO shifter, for receiving current row labels from said label computation engine and previous row labels from said label row FIFO shifter, and for computing connecting relationships to segments in a previous row;

a segment processor controller, coupled to said data flow controller, for providing a current segment length; and

a segment record generator, coupled to said label computation engine, said segment processor controller and said neighborhood computation unit, for receiving said current row labels, said current segment length, and information about said connecting relationships, and for generating at least one segment record for each transition event; and

a data flow controller, coupled between said at least one data storage memory and said data extraction processor, for controlling the flow of processor words into said data extraction processor and the flow of said result records out of said data extraction processor.

2. The data extraction system as claimed in claim 1, wherein said data includes image data, and wherein each said data sample corresponds to an image pixel represented with said multiple bits in said data sample.

3. The data extraction system as claimed in claim 1, wherein said data flow controller comprises at least one internal first-in, first-out (FIFO) memory;

and

control logic to manage the flow of data through said system.

4. The image data extraction system as claimed in claim 2, wherein said data extraction processor is a gradient data extraction processor including:

a plurality of registers, said plurality of registers arranged in series and including a first set of registers, a second set of registers and a third set of registers, wherein each of said registers receives one of said data samples corresponding to an image pixel;

a plurality of gradient calculators, coupled to said plurality of registers, for computing gradient values corresponding to at least some of said data samples;

at least one neighborhood comparator unit, coupled to said plurality of gradient calculators, for identifying a local maximum gradient value which is greater than neighboring gradient values and for indicating a winning gradient point;

a gradient sub-pixel information selection multiplexer, coupled to said at least one neighborhood comparator unit, for selecting absolute gradient values for said winning gradient point; and

a gradient data reporting engine, coupled to said gradient sub-pixel information selection multiplexer, for generating a gradient data output record.

5. A method of extracting segment data from image data and generating records reporting said segment data, said method comprising the steps of:

zeroing a current label at the beginning of a current row of image data;

receiving image pixel data samples from image memory, one processor word at a time, said processor word including at least two said image pixel data samples; and

processing each said processor word according to the following steps;

simultaneously determining if each said image pixel data sample in said processor word is in the foreground or background;

simultaneously identifying any foreground/background transitions between each of said image pixel data samples and neighboring image pixel data samples and generating a transition bit signal for each possible transition;

adding each said transition bit signal to said current label to compute a correct label code for each possible transition;

receiving label codes for a row previous to said current row;

computing connection relationships to segments in said row previous to said current row;

if a transition is identified, reporting at least one record containing information about said identified transition within said processor word; and

updating said current label by adding the total number of identified transitions.

6. The method of claim 5, wherein the step of receiving image pixel data samples from image memory is stalled when said transition is identified.

7. The method of claim 5, wherein each said processor word includes four image pixel data samples.

8. A method of extracting gradient data from image data and generating records reporting said gradient data comprising the steps of:

receiving a plurality of pixel data samples packed into a single processor word of data simultaneously;

computing gradient values between each of said pixel data samples using convolution weights;

comparing said gradient values with neighbor gradient values to identify a local maximum gradient value greater than said neighbor gradient values;

reporting a winning gradient data point by generating a first gradient data word comprising at least one of the maximum gradient value, the gray value of the central pixel, bits to indicate first point in a row, positive, negative and column coordinate; and

generating a second gradient data word comprising a numerator and a denominator which may be used to compute the fractional position of the gradient data point.

9. The method of claim 8, further including the steps of:

setting a winning gradient point signal for said winning gradient data point after identifying said local maximum gradient value; and

selecting absolute gradient values for said winning gradient point.

10. The method of claim 8, wherein the step of receiving image pixel data samples from image memory is stalled when a gradient data point is detected.

11. The method of claim 10 wherein said first and second gradient data words require two clock cycles to report, and wherein the step of receiving image pixel data samples from image memory is stalled for one clock cycle.

12. The method of claim 8, wherein each said processor word includes four pixel data samples corresponding to four image pixels, wherein said computed gradient values include gradient values for each of said image pixels and gradient values on either side of said image pixels.

13. An image data extraction system comprising:

at least one data storage memory for storing image data formatted into a plurality of data samples, each of said plurality of image data samples corresponding to an image pixel having multiple bits;

a data flow controller, coupled between said at least one data storage memory and a data extraction processor, for controlling the flow of processor words into said data extraction processor and the flow of result records out of said data extraction processor; and

a data extraction processor, for receiving said image data from said data storage memory one processor word at a time, wherein a processor word includes at least two of said image data samples, for simultaneously processing said at least two of said image data samples in each said processor word, and for generating at least one result record containing information extracted from said at least two image data samples in at least one said processor word, said data extraction processor comprising a segmentation processor including;

a label computation engine, coupled to a data flow controller, for simultaneously receiving said at least two image data samples in each said processor word, for identifying transitions between said at least two image data samples and generating transition bit signals for each potential transition, and for computing a label code for each said potential transition using said transition bit signals;

a label row FIFO shifter, coupled to said label computation engine, for receiving and storing said label code for each said potential transition;

a neighborhood computation unit, coupled to said label computation engine and to said label row FIFO shifter, for receiving current row labels from said label computation engine and previous row labels from said label row FIFO shifter, and for computing connecting relationships to segments in a previous row;

a segment processor controller, coupled to said data flow controller, for providing a current segment length; and

a segment record generator, coupled to said label computation engine, said segment processor controller, and said neighborhood computation unit, for receiving said current row labels, said current segment length, and information about said connecting relationships, and for generating at least one segment record for each transition event.