Method and apparatus for rapidly processing data sequences

• US 5,315,700 A
• Filed: 02/18/1992
• Issued: 05/24/1994
• Est. Priority Date: 02/18/1992
• Status: Expired due to Fees

• Current Assignee: Tripath Imaging Incorporated (Becton, Dickinson & Co)
• Original Assignee: NeoPath, Inc. (Becton, Dickinson & Co)
• Inventors: Budak, Paul V., Lee, Shih-Jong J., Johnston, Richard S., Schmidt, Robert C.
• Primary Examiner(s): Shaw, Dale M.
• Assistant Examiner(s): Tung, Kee M.
• Application Number:
  US07/838,070
• Time in Patent Office: 826 Days
• Field of Search: 395/100, 395/118, 395/162, 395/163, 395/164.varies.166, 395/141, 382/49, 382/54, 340/728, 340/750, 340/798-799, 345/185, 345/201
• US Class Current: 345/502
• CPC Class Codes: G06T 1/60 Memory management

Abstract

Improved method and apparatus are provided for performing parallel and pipeline processing of data sequences. The apparatus includes a plurality of memory circuits and a plurality of data processors wherein each data processor is constructed for parallel and pipeline processing of data sequences. Address controllers are provided for routing data between the memory circuits and the pixel processors. The address controllers are capable of directly coupling any memory circuit to any pixel processor so that data may be simultaneously transferred from a plurality of memory circuits to a plurality of pixel processors. Further, the pixel processors are provided with processing elements for performing data processing on neighboring data words of a data sequence. The address controller is constructed for providing data from the memory circuits in a plurality of sequences so that the data may be provided to the pixel processor first and second times in respective first and second sequences to enable two dimensional processing of the data sequence. A feature processor is provided for extracting specific information from the processed image data, relating to features of objects contained therein.

Claims

1. Apparatus for rapidly processing data sequences comprising:

a plurality of memory circuits for storing the data sequences wherein each of said plurality of memory circuits includes a memory input and a memory output;

a plurality of processing circuits for processing the data sequences wherein each of said plurality of processing circuits includes a data output for providing an output data sequence, each of said plurality of processing circuits further including a first multiplexer circuit for receiving a plurality of input data sequences wherein said first multiplexer circuit is responsive to a first select control signal for selecting at least one of the plurality of input data sequences to be processed to provide the output data sequence;

a plurality of controller circuits, each associated with a respective one of said plurality of memory circuits for simultaneously transferring the data sequences between one of said plurality of memory circuits and each of said plurality of processing circuits, said plurality of controller circuits each including a second multiplexer circuit for receiving the plurality of output data sequences and being responsive to a second select control signal for selecting at least one of the plurality of output data sequences to be stored in its respective one of said plurality of memory circuits; and

central processor means responsive to user provided input for providing said first and second select control signals to control the transfer of the data sequences between said plurality of memory circuits and said plurality of processor circuits.

2. The apparatus as recited in claim 1 wherein each of said plurality of memory circuits is responsive to an X and Y address for storing and recalling the data sequences and wherein each of said plurality of controller circuits further comprises:

first and second registers for providing said X and Y addresses to said plurality of memory circuits, said first and second registers being responsive to register control signals received from said central processor means for providing said X and Y addresses in increasing and decreasing order, said first and second registers being programmable in response to program addresses received from said central processor means, said central processor means being further constructed to provide said register control signals so that said first and second registers provide said X and Y addresses consecutively and so that said first and second registers provide said X and Y addresses in a manner such that said X and Y addresses increase and decrease by a constant factor.

3. The apparatus as recited in claim 1 wherein said plurality of processing circuits includes a feature processing circuit, said apparatus further comprising:

a feature memory circuit constructed for receiving and storing data from said feature processor circuit, said feature memory circuit being further constructed to provide output to said feature processing circuit and said central processing means so that the data sequences are transferable from said plurality of memory circuits to said central processing circuit via said feature processing circuit and said feature memory circuit.

4. The apparatus as recited in claim 1 wherein one of said plurality of processing circuits further includes a multiplexing circuit including first and second control inputs and a plurality of data inputs and wherein said multiplexing circuit is constructed to provide one of said plurality of data inputs and a multiplexing circuit output in response to the data present at said first and second control inputs, said multiplexing circuit being constructed to receive first and second data inputs at said first and second control inputs, respectively, and to receive a control word at said plurality of data inputs so that the data provided at said multiplexing circuit output is an arithmetic logic function of the respective values of said first and second data inputs and so that the arithmetic logic function is determined by the value of said control word.

5. The apparatus as recited in claim 1 wherein each of said plurality of address controllers comprises:

boundary shift register means for providing boundary data to be added to the data sequences, said boundary shift register means being programmable by said central processing means so that said boundary data is determined by said central processing means, said boundary shift register means being responsive to shift register control signals received from said central processing means for combining said boundary data with the data sequences.

6. The apparatus as recited in claim 5 wherein said boundary shift register means further comprises multiplexer means constructed to receive the data sequences and to receive said boundary data, said multiplexer means being responsive to said shift register control signals for providing either said boundary data or the data sequence as its output.

7. The apparatus as recited in claim 1 further comprising selection register means for selecting a portion of the data sequences to be transferred to said plurality of processing circuits, said selection register means being responsive to region of interest signals received from said central processing means for skipping an initial portion of the data sequences and being responsive to said region of interest signals for providing a predetermined portion of the data sequence and for skipping an intermediate portion of the data sequence.

8. The apparatus as recited in claim 7 wherein said selection register means comprises:

boundary shift register means responsive to said central processor means for providing boundary data to be added to the data sequences, said boundary shift register means being programmable by said central processing means so that said boundary data is determined by said central processing means;

multiplexer means constructed to receive the data sequences and to receive said boundary data, said multiplexer means being constructed for providing said boundary data and the data sequence as its output;

a delay register for determining a length of the initial portion of the data sequence to be skipped, said multiplexer means being responsive to said delay register so that said boundary data is provided as the output of said multiplexer means while the initial portion of the data sequence is being skipped; and

an extension register for determining the length of the intermediate portion of the data sequence to be skipped, said multiplexer means being responsive to said extension register so that said boundary data is provided as the output of said multiplexer means while the intermediate portion of the data sequence is being skipped.

9. The apparatus as recited in claim 1 wherein each of said plurality of processing circuits comprises:

first and second data paths each programmable to perform a shift operation to transfer any digit of a multiple bit data word to a predetermined bit position and each said first and second data path begin further programmable to perform a threshold operation on a multiple bit data word;

first and second data processing block means programmable to perform data processing on said input data sequences, and

output multiplexer means for receiving the output from said first and second data paths and programmable to provide the output from the first and second data paths to said first and second data processing blocks.

10. Apparatus for multi-dimensional processing of data sequences having values, wherein the data sequence includes a plurality of data words, said apparatus comprising:

memory means for storing the data sequences, said memory means having an output which is responsive to memory control signals, said output providing the data sequences in at least a first and second order;

processing means responsive to configuration control signals for processing the data sequences provided by said output to alter the value of at least a portion of the data words in the data sequence in response to the value of immediate and non-immediate neighboring data words; and

data processor means for providing said memory control signals and said configuration control signals to control the operation of said memory means and said processing means, said data processing means being constructed to provide said memory control signals a first time to access the data sequences in the first order so that the value of at least a portion of the data words in the data sequence is altered in response to immediate and non-immediate neighboring data words in a first dimension and to provide said memory controls signals a second time to access the data sequences in the second order so that the value of at least a portion of the data words in the data sequence is altered in response to immediate and non-immediate neighboring data words in a second dimension.

11. The apparatus as recited in claim 10 wherein said processing means comprises means for binomial filtering of the data sequences.

12. The apparatus as recited in claim 10 wherein said processing means comprises means for performing morphological operations on the data sequences.

13. The apparatus as recited in claim 10 wherein said memory means comprises:

a memory unit for storing the data words of the data sequences, said memory unit being responsive to address signals for providing the stored data words as the output of said memory means, and

a memory controller responsive to said memory control signals for providing said address signals to access said memory unit, said memory controller being constructed to provide said address signals so that the data sequence is provided in the at least first and second order.

14. A method for multi-dimensional processing of data having values, wherein the data includes a plurality of data words combined in a data sequence, said method comprising the steps of:

providing the data in a first sequence to a processing engine wherein the processing engine is constructed to process the data to alter the value of a subject data word based upon the value of immediate and non-immediate neighboring data words; and

providing the data in a second sequence to the processing engine so that the processing engine processes the data to alter the value of a subject data word based upon the value of immediate and non-immediate neighboring data words and so that the result is to process the data in two dimensions.