Feature extraction processor

• US 4,972,495 A
• Filed: 12/21/1988
• Issued: 11/20/1990
• Est. Priority Date: 12/21/1988
• Status: Expired due to Fees

• Current Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Original Assignee: General Electric Company
• Inventors: Blum, Ricky S., Horwedel, Mark S., Rimlinger, Janet L., Blike, James J.
• Primary Examiner(s): Moore, David K.
• Assistant Examiner(s): Jung, Yon
• Application Number:
  US07/287,176
• Time in Patent Office: 699 Days
• Field of Search: 382/49, 382/22, 382/44, 382/45, 382/46, 382/27, 382/55, 382/41, 364/133, 364/715.08, 364/728.02, 364/726, 364/736, 340/721
• US Class Current: 382/304
• CPC Class Codes: G06T 2200/28 involving image processing hardware
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 5/20 using local operators
• CPC Class Codes: G06T 7/12 Edge-based segmentation

Abstract

A data processor includes an array of a plurality of processing elements haivng ports connected to neighboring elements. Elements at each end of a column have interconnected ports so that data can be sequentially cycled through the column elements. Elements at each end of a row have switchably interconnected ports so that in one mode data can be sequentially cycled through the row elements. The processor further includes a shift register switchably coupled to each row and memory apparatus coupled to the shift registers. The shift registers are switchable such that in a second mode data can be sequentially cycled through the shift registers and the corresponding row elements. The processor also includes an input shuffle matrix for reformatting data for facilitating data storage and recall during processing, thereby increasing overall system throughput. A method includes storing data in bit planes and shifting data a plurality of bit positions before writing the shifted data to memory, thereby further increasing throughput. Data processing may be used for edge detection from an image including a plurality of picture elements (pixels).

Claims

1. A data processor, comprising:

a plurality of cells each including at least two row ports and two column ports for transmitting and receiving data signals, each cell having at least one of the two row ports and two column ports connected to a corresponding row and column port of neighboring cells, each cell further for processing data received by the each cell on the row and column ports;

each column having first and second end cells at respective ends of the column and one of the column ports of the first end cell connected to one of the column ports of a corresponding second end cell of the column such that data may be sequentially passed in a loop including all cells of the corresponding column of cells, and each row having a first and second end cell at respective ends of the row;

a plurality of switch means each of the switch means having a common terminal connected to a row port of a corresponding first end cell, each switch means further having a first terminal connected to a row port of a corresponding second end cell, each switch means having a second terminal;

a plurality of shift register means, each of the shift register means having a first port connected to the second switch terminal of a corresponding switch means and further having a second port connected to the row port of the corresponding second end cell; and

memory means coupled to the plurality of shift register means, the memory means for storing data received from the plurality of shift register means and for supplying previously stored data to the plurality of shift register means,

wherein each switch means is operationally functional to connect the respective common terminal and first terminal such that data may be sequentially passed in a loop including all cells of the corresponding row and the corresponding shift register means and further operationally functional to connect the respective common terminal and second terminal such that data may be sequentially passed in a loop including all cells of the corresponding row while bypassing the corresponding shift register means.

2. The data processor as in claim 1, further including control means for controlling data flow between the plurality of cells and the memory means, the control means providing a plurality of shift commands for transferring data from rows of cells to the corresponding shift register means followed by a write command for transferring data from the corresponding shift register means to the memory means.

3. The data processor as in claim 1, wherein the memory means and the plurality of shift register means include a video random access memory.

4. The data processor as in claim 1, wherein each of the first end cells of the columns includes an output for supplying data from the corresponding first end cell and each of the second end cells of the columns includes an input for receiving data by the corresponding second end cell, the data processor further including:

first shuffle matrix means having a plurality of outputs and an input, the plurality of outputs respectively coupled to respective inputs of the second end cells of the columns, the first shuffle matrix for reorganizing bits of data in first data word format such that bits representing the same bit position within each data word are grouped together to form bits of data in second data word format; and

second shuffle matrix means having a plurality of inputs and an output, the plurality of inputs respectively coupled to respective outputs of the first end cells of the columns, the second shuffle matrix for reorganizing bits of data in the second data word format such that the bits are ordered in the first data word format.

5. The data processor as in claim 4, further including:

input buffer means having an output coupled to the input of the first shuffle matrix and an input for receiving data at a first data rate, the input buffer means for supplying the received data to the first shuffle matrix at a second data rate, thereby buffering input data flow to the processor; and

output buffer means having an input coupled to the output of the second shuffle matrix and an output, the output buffer means for making available data received at the input from the second shuffle matrix at the second data rate to the output of the buffer means at the first data rate, thereby buffering output data flow from the processor.

6. The data processor as in claim 1, wherein each of the first end cells of the columns includes an output for supplying data from the corresponding firstend cell and each of the second end cells of the columns includes an input for receiving data by the corresponding second end cell, each cell further including a plurality of registers internally connected to row and column ports and an arithmetic logic unit for processing data by the cell, wherein a set of data may be processed while another set of data is being transferred among the cells.

7. A method for processing digital data, comprising:

obtaining the digital data to be processed, the digital data including a plurality of data words, each data word having data bits arranged in a predetermined first data bit sequence in response to the place value of the data bits for forming a first data bit format;

rearranging the data bits of the data words into a second data bit format, the second data bit format having corresponding data bits with the same place value from the data words grouped together, data bits within each group of data bits having the same place value arranged in a predetermined second data bit sequence in response to the data word of the first data bit format from which the data bit came;

storing the data words of the second bit format in bit planes, wherein a data bit plane includes data bits having the same place value of data words having the first data bit format;

processing data bits by data bit plane for determining a predetermined first function of the data bits of the data bit plane, the predetermined first function represented by data bits in the second data bit format;

reorganizing the data bits of the predetermined first function into data words having the first data bit format, wherein the step of storing includes;

supplying the data words of the second bit format to a bit processor array, the bit processor array including a plurality of cells connected to neighboring cells for forming a predetermined number of rows and columns of cells, data bits of the data words of the second bit format supplied to respective columns of cells, the cells including a respective arithmetic logic unit;

shifting a predetermined plurality of data bits having at least two different place values of the second bit format in a predetermined direction along the rows of the array in response to a plurality of shift commands; and

storing the predetermined plurality of shifted data bits in response to a single write command.

8. The method as in claim 7, wherein the step of processing is performed concurrently with the steps of supplying, shifting and storing the predetermined plurality of shifted data bits.

9. The method as in claim 7, wherein the step of shifting further includes shifting the predetermined plurality of data bits into shift register means, the shift register means coupled to memory means.

10. The method as in claim 9, wherein a port of the cell at one end of each column of cells is connected to a port of the cell at the other end of the corresponding column, and a port of the cell at one end of each row of cells is switchably connected to a port of the cell at the other end of the corresponding row and to a port of a corresponding shift register, the corresponding shift register having another port switchably connected to the port of the cell at the other end of the corresponding row, the step of processing further including:

sequencing data bits in a first loop through columns of cells;

sequencing data bits in a second loop through rows of cells when the port of the cell at the one end of each row is operationally connected to the port at the other end of the corresponding row; and

sequencing data bits in a third loop through rows of cells and corresponding shift registers when the another port of the corresponding shift register is operationally connected to the port of the cell at the other end of the corresponding row, thereby facilitating data bit and intermediate processing data bit storage and retrieval.

11. The method as in claim 7, wherein the predetermined first function includes edges in an image, the image including a plurality of pixels, each pixel represented by the respective data word of the first bit format and the step of processing further includes:

determining the response of a pixel data word to a predetermined second function and to the second derivative of the predetermined second function from a predetermined number of directions;

identifying the pixel as an edge point when both the response to the second function is greater than a predetermined threshold and the response to the second derivative of the second function crosses zero for any one of the predetermined directions.

12. The method as in claim 11, further including the step of thinning the width of neighboring pixels identified as edge points to one pixel width while maintaining the connectivity among the remaining pixels.

13. The method as in claim 12, further including:

disregarding edge points having no neighboring pixels which are also identified as edge points;

disregarding edge points having more than one neighboring pixel identified as an edge point; and

labelling each group of connected edge points in response to a predetermined characteristic of a predetermined one of the edge points of the corresponding group of remaining edge points.

14. The method as in claim 13, further including:

determining the curvature of each group of remaining edge points;

separating a group of remaining edge points into first and second separated groups of edge points at a separation point when the curvature at the separation point is greater than a predetermined curvature threshold;

approximating the group of remaining edge points, first separated group of edge points and second separated group of edge points by a straight line.

15. The method as in claim 14, wherein the steps of determining the curvature and separating are repeated for the first and second separated groups and the step of approximating is repeated for each group formed by the repeated separating step.

16. The method as in claim 14, further including:

determining the point of maximum deviation of the straight line from the corresponding group of edge points;

separating the corresponding group of edge points into third and fourth separated groups of edge points at the point of maximum deviation when the maximum deviation is greater than a predetermined deviation threshold;

approximating the third and fourth separated groups of edge points by a respective straight line.

17. The method as in claim 16, further including repeating for the third and fourth separated groups the steps of determining the point of maximum deviation, separating the group of edge points and approximating the third and fourth separated groups.