Computer vision architecture

• US 4,809,347 A
• Filed: 07/18/1986
• Issued: 02/28/1989
• Est. Priority Date: 07/18/1986
• Status: Expired due to Term

• Current Assignee: Hughes Electronics Corporation (AT&T, Inc.)
• Original Assignee: Hughes Aircraft Company (Rtx Corporation)
• Inventors: Shu, David B., Nash, James G.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US06/887,847
• Time in Patent Office: 956 Days
• Field of Search: 382/41, 382/49, 382/34, 382/27, 364/133, 364/131, 307/440, 307/446
• US Class Current: 382/240
• CPC Class Codes: G06F 15/8023 Two dimensional arrays, e.g. mesh, torus
• CPC Class Codes: G06T 1/20 Processor architectures; Processor configuration, e.g. pipelining

Abstract

A computer architecture is disclosed for analyzing automatic image understanding problems. The architecture is designed so that it can efficiently perform a wide spectrum of tasks ranging from low level or iconic processing to high level or symbolic processing tasks. A first level (12) of image processing elements is provided for operating on the image matrix on a pixel per processing element basis. A second level (14) of processing elements is provided for operating on a plurality of pixels associated with a given array of first level processing elements. A third level (16) of processing elements is designed to instruct the first and second level processing elements, as well as for operating on a larger segment of the matrix. A host computer (18) is provided that directly communicates with at least each third level processing element. A high degree of parallelism is provided so that information can be readily transferred within the architecture at high speeds.

Claims

1. A computer architecture for an image understanding machine for performing operations on image data in the form of a matrix of pixels, said machine comprising:

a first level of image processing elements having a first construction that enables neighboring processing elements on the first level to operate on different instructions simultaneously;

a second level of processing elements having a different construction than the first level processing elements, said second level processing elements each including means therein enabling processing elements on the second level to operate on different instructions simultaneously, each second level processing element being associated with a group of first level processing elements and communicating therewith as well as with other second level processing elements;

a third level of processing elements having a construction different than the first and second level of processing elements, each third level processing element being associated with a given number of second level processing elements and communicating therewith as well as with other third level processing elements; and

a host computer communicating with at least the third level processing elements whereby different instructions can be transmitted to the processing elements of various levels to enable the computer to operate simultaneously on multiple instructions in each level.

2. The machine of claim 1 wherein the system is constructed on a plurality of circuit boards communicating with the host computer, each board containing:

at least one third level processing element;

a first plurality of second processing elements

a second larger plurality of first processing elements; and

connector means on the circuit board for establishing communication between at least the third level processing element on the board and the host computer through a bus.

3. The machine of claim 2 wherein said bus includes a backplane into which the connectors of the circuit boards are inserted, with the backplane being used as part of a global bus between the third level processors on the individual circuit boards and the host computer.

4. The machine of claim 2 wherein said first plurality of second level processing elements is an N×

N array, where N is greater than 1; and

wherein said second plurality of first processing elements is an mN×

mN array, where m is greater than 1.

5. The machine of claim 4 wherein m equals 8.

6. The machine of claim 1 wherein said first level processing element includes a bit-serial arithmetic logic unit communicating with a random access memory and means for mesh connecting each processing element to its neighboring processing elements of the first level.

7. The machine of claim 1 wherein said second level processing elements each comprise a multi-bit parallel processor.

8. The machine of claim 1 wherein said third level processing elements each comprise a general purpose microprocessor.

9. The machine of claim 1 wherein, an array of first level processing elements is fabricated together with one second level processing element on a single integrated circuit chip.

10. The machine of claim 9 wherein said chip includes at least one dual ported memory bank having input/output lines connected both to the first level processing elements and to processing elements of at least one other level.

11. The machine o f claim 10 wherein said memory bank includes a plurality of cells, each cell containing at least one transistor defining a random access memory.

12. The machine of claim 10 wherein said chip includes first microprogram store means for storing instructions and a first decoder for decoding the instructions for controlling the operation of selected first level processing elements, second microprogram store means for storing different instructions and a second decoder for decoding the different instructions for controlling the operation of the second level processing elements, and wherein the input/output lines of the memory bank are connected to said microprogram store as well as to said first level processing elements.

13. The machine of claim 9 wherein one second level processing element is located on said chip together with means on the chip connecting said second level processing element to an array of 64 first level processing elements.

14. The machine of claim 1 wherein the host communicates with each third level processing element by way of a backplane, each third level processing element communicates with its associated second level processing element by way of a bus provided on a circuit board, and wherein each second level processing element communicates with its associated group of first level processing elements by way of a bus provided on an integrated circuit chip.

15. A method of analyzing an image represented by a matrix of pixels, said method comprising:

loading the pixels into an image understanding machine having first, second and third levels of processing elements in which processing elements in each level have different constructions;

simultaneously performing different operations on selected groups of the pixels with the first level processing elements, there being one first level processing element for each pixel in the matrix;

using the second level processing elements to simultaneously perform other operations on a group of pixels associated with an array of first level processing elements; and

using the third level processing elements to instruct the first and second level processing elements.

16. The method of claim 15 which further comprises:

providing parallel connections between processing elements of each level to thereby maximize communication rates therebetween.

17. The method of claim 16 wherein parallel connection between said first level processing elements is provided by a nearest neighbor mesh, wherein the connection for the second level processing elements is provided by a nearest neighbor mesh, and wherein parallel connections between the third level processing elements is provided by a bused cube connection.

18. The method of claim 17 which further comprises:

establishing communication between a host computer and at least each third level processing element.

19. The method of claim 18 wherein said communication is established by a global bus defined in part by a backplane into which a plurality of circuit boards are inserted.

20. The method of claim 19 which further comprises:

establishing communication between each third level processing element and an associated array of second level processing elements by way of a bus provided on a circuit board.

21. The method of claim 20 which further comprises:

establishing communication between each second level processing element and a group of first level processing elements by way of a bus provided on an integrated circuit chip.

22. The method of claim 15 which further includes:

representing an object in the image by three levels of binary mask representations, each mask corresponding to said first, second and third level of processing elements, respectively.

23. The method of claim 22 wherein each mask contains an array of binary bits, with each binary bit corresponding to a processing element in the given level.

24. The method of claim 15 which further comprises:

fabricating an array of first level processing elements on an integrated circuit chip together with one second level processing element.

25. The method of claim 24 wherein each processing element consists of a module having a central processing unit and memory, and wherein the method further includes:

constructing the memory on the chip with dual ports such that input/output lines thereof can be used to establish communication between the central processing unit of at least both the first and second level processing elements.

26. A machine for performing operations on image data in the form of a matrix of pixels, said machine comprising:

a plurality of circuit boards having connector means thereon pluggable into a backplane of a cabinet; and

N×

N array of integrated circuit chips located on the board, wherein N is an integer, each chip including an mN×

mN array of first level processing elements, wherein mN is an integer, said first level processing elements being mesh connected to neighboring processing elements;

each chip further including a second level processing element connected to each of the first level processing elements and having a different construction therefrom, said chip further including individually addressable first means for controlling selected first level processing elements so that they can operate on different instructions simultaneously, and the chip also including an individually addressable second means for controlling said second level processing element;

a third level processing element of still different construction located on the board and connected to each second level processing element on the board, said third level processing element also being coupled to said connector; and

means including said backplane for defining a global bus connecting each of the third level processing elements with a host computer.

27. The machine of claim 26 wherein each first level processing element includes a bit serial arithmetic logic unit communicating with a random access memory.

28. The machine of claim 26 wherein said each second level processing element comprises a multi-bit parallel processor.

29. The machine of claim 26 wherein each third level processing element comprises a general purpose microprocessor.

30. The machine of claim 26 wherein said first level processing elements are adapted to perform iconic operations on the pixels.

31. The machine of claim 26 wherein said second level processing elements are adapted to perform intermediate level symbolic operations on the pixels.

32. The machine of claim 26 wherein said third level processing elements are adapted to instruct the operation of said first and second level processing elements.

33. The machine of claim 26 wherein each chip contains at least one memory bank having dual ports with input/output lines providing access to the memory by both the first and second level processing elements.

34. A machine for performing operations on image data in the form of a matrix of pixels, said machine comprising:

a circuit board having connector means thereon pluggable into a back plane of a cabinet;

N×

N groups of integrated circuit devices located on the board, wherein N is an integer, each group including an mN×

mN array of first level processing elements, wherein mN is an integer, said first level processing elements being mesh connected to neighboring first level processing elements;

each group further including a second level processing element connected to each of the first level processing elements and having a different construction therefrom, each group further including individually addressable first means for controlling selected first level processing elements so that they can operate on different instructions simultaneously, and each group also including an individually addressable second means for controlling said second level processing element;

said machine further including a third level processing element of still different construction which is connected to each second level processing element on the board, and means including said back plane for defining a bus connection to a host computer.