 |
Claims  |
|
|
What is claimed is:
1. An imaging computer system comprising:
an image input device disposed to form an analog image signal corresponding
to objects in a predefined space;
an analog to digital conversion device connected to said image input device
for converting said analog image signal into a series of digital numbers
having a predetermined number of bits, thereby forming a digital pixel
image;
an image memory connected to said analog to digital converter for storing
said digital pixel image;
a programmable image processing device disposed on a single integrated
circuit configured to receive said digital pixel image of objects in the
predefined space, identify any hand signs within said digital pixel image,
assign a meaning to any identified hand signs and generate a coded digital
output corresponding to said assigned meaning.
2. The imaging computer system as claimed in claim 1, wherein:
said programmable image processing device includes
a master processor for controlling operation of said imaging processing
device, said master processor operating on an instruction cycle,
a plurality of parallel processors each capable of performing independent
image operations on digital image data including movement of said digital
image data to and from a plurality of addressable memory spaces, each of
said parallel processors operating on said instruction cycle,
a transfer processor connected to said image memory for transferring data
between said image memory and said image processing device, said transfer
processor operating on said instruction cycle,
a plurality of memories forming a plurality of addressable memory spaces,
and
a crossbar switch matrix connected to said master processor, each of said
parallel processors, said transfer processor and each of said memories,
said crossbar switch matrix reconfigurable each instruction cycle for
granting said master processor, each of said parallel processors and said
transfer processor access to said plurality of memories.
3. The imaging computer system as claimed in claim 1, wherein:
said image input device includes a video camera.
4. The imaging computer system as claimed in claim 1, further comprising:
a digital output bus connected to said image processing device for
transmitting said coded digital output corresponding to said assigned
meaning.
5. The imaging computer system as claimed in claim 1, further comprising:
a visual display device connected to said image processing device; and
said image processing device further configured to generate a human
readable text output corresponding to said coded digital output and to
generate a visual output signal for display via said visual display
device, said visual output signal corresponding to said human readable
text output overlain upon said image.
6. The imaging computer system as claimed in claim 1, further comprising:
a transmission sender connected to said image input device for transmitting
said image; and
a transmission receiver connected to said transmission sender and said
image processing device and disposed remotely from said transmission
sender for receiving said transmitted image and supplying said received
transmitted image to said image processing device.
7. The imaging computer system as claimed in claim 1, wherein:
said image processing device further configured to interpret said coded
digital output as a user input command and to perform at least one task
corresponding to said user input command.
8. The imaging computer system as claimed in claim 1, further comprising:
a latch circuit connected to said image processing device and an external
controlled mechanism for control of the controlled mechanism; and
said image processing device further configured to operate said latch
circuit corresponding to said coded digital output thereby controlling the
controlled mechanism corresponding to said identified hand signs within
said digital pixel image.
9. The imaging computer system as claimed in claim 1, wherein:
said hand signs identified by said image processing device include deaf
communication signs.
10. An imaging computer system comprising:
an image input device disposed to form an analog image signal corresponding
to objects in a predefined space;
an analog to digital conversion device connected to said image input device
for converting said analog image signal into a series of digital numbers
having a predetermined number of bits, thereby forming a digital pixel
image;
a programmable image processing device disposed on a single integrated
circuit including
a master processor for controlling operation of said imaging processing
device, said master processor operating on an instruction cycle,
a plurality of parallel processors each capable of performing independent
image operations on digital image data including movement of said digital
image data to and from a plurality of addressable memory spaces, each of
said parallel processors operating on said instruction cycle,
a transfer processor connected to said image memory for transferring data
between said image memory and said image processing device, said transfer
processor operating on said instruction cycle,
a plurality of memories forming a plurality of addressable memory spaces,
and
a crossbar switch matrix connected to said master processor, each of said
parallel processors, said transfer processor and each of said memories,
said crossbar switch matrix reconfigurable each instruction cycle for
granting said master processor, each of said parallel processors and said
transfer processor access to said plurality of memories;
a user input device connected to said image processing device for input of
user commands;
an image information bus connected to said image processing device for
transfer of data corresponding to images being processed;
a display connected to said image information bus for display of image data
to a user; and
a print assembly connected to said image information bus for producing
documents corresponding to image data.
11. The imaging computer system as claimed in claim 10, wherein:
said image input device includes optics and a charge coupled device.
12. The imaging computer system as claimed in claim 11, further comprising:
a controller engine connected to said charge coupled device, said
programmable image processing device and said print assembly for providing
timing signals to said charge coupled device and said print assembly.
13. An imaging computer system comprising:
a first and a second charge coupled device disposed to detect position
information of a user's hand within a predetermined space; a programmable
image processing device disposed on a single integrated circuit including
a master processor for controlling operation of said imaging processing
device, said master processor operating on an instruction cycle,
a plurality of parallel processors each capable of performing independent
image operations on digital image data including movement of said digital
image data to and from a plurality of addressable memory spaces, each of
said parallel processors operating on said instruction cycle,
a transfer processor connected to said image memory for transferring data
between said image memory and said image processing device, said transfer
processor operating on said instruction cycle,
a plurality of memories forming a plurality of addressable memory spaces,
and
a crossbar switch matrix connected to said master processor, each of said
parallel processors, said transfer processor and each of said memories,
said crossbar switch matrix reconfigurable each instruction cycle for
granting said master processor, each of said parallel processors and said
transfer processor access to said plurality of memories;
said programmable image processing device configured to receive said
position information of a user's hand within the predetermined space,
assign a meaning to said position information and correspondingly control
said imaging computer system;
a memory connected to said programmable image processing device; and
a flat panel display connected to said programmable image processing device
for display of image data to a user.
14. The imaging computer system as claimed in claim 13, further comprising:
a video camera connected to said programmable image processing device for
generating an image of objects in a predefined space.
15. The imaging computer system as claimed in claim 13, further comprising:
a printer port connected to said programmable image processing device for
controlling a printer.
16. The imaging computer system as claimed in claim 13, further comprising:
a host computer port connected to said programmable image processing device
for communication with a host computer.
17. An imaging computer network comprising:
a host computer for collecting and distributing image information;
a plurality of imaging computers, each imaging computer including
a buffer memory connected to said host computer for receiving image
information from said host computer,
a data bus connected to said buffer memory,
a memory connected to said data bus,
a programmable image processing device connected to said data bus and
disposed on a single integrated circuit including
a master processor for controlling operation of said imaging processing
device, said master processor operating on an instruction cycle,
a plurality of parallel processors each capable of performing independent
image operations on digital image data including movement of said digital
image data to and from a plurality of addressable memory spaces, each of
said parallel processors operating on said instruction cycle,
a transfer processor connected to said data bus for transferring data
between said data bus and said image processing device, said transfer
processor operating on said instruction cycle,
a plurality of memories forming a plurality of addressable memory spaces,
and
a crossbar switch matrix connected to said master processor, each of said
parallel processors, said transfer processor and each of said memories,
said crossbar switch matrix reconfigurable each instruction cycle for
granting said master processor, each of said parallel processors and said
transfer processor access to said plurality of memories.
18. The imaging computer network as claimed in claim 17, wherein:
at least one of said imaging computers further includes
a printer interface connected to said data bus, and
a print assembly connected to said printer interface for producing
documents corresponding to image information.
19. The imaging computer network as claimed in claim 17, wherein:
at least one of said imaging computers further includes
a scanner for acquiring image information, and
a front end processor connected to said scanner and said data bus for
processing acquired image information from said scanner. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
TECHNICAL FIELD OF THE INVENTION
This invention relates generally to imaging systems and more particularly
to such systems and methods in which the incoming image is subject to
interpretation.
CROSS REFERENCE TO RELATED APPLICATIONS
All of the following patent applications are cross-referenced to one
another, and all have been assigned to Texas Instruments Incorporated.
These applications have been concurrently filed and are hereby
incorporated in this patent application by reference.
______________________________________
U.S.
Pat. App.
Title
______________________________________
437,591 Multi-Processor With Crossbar Link of
Processors and Memories and Method of
Operation
437,858 SIMD/MIMD Reconfigurable Multi-Processor and
Method of Operation
437,856 Reconfigurable Communications for Multi-
Processor and Method of Operation
437,852 Reduced Area of Crossbar and Method of
Operation
437,853 Synchronized MIMD Multi-Processors, System
and Method of Operation
437,946 Sliced Addressing Multi-Processor and Method
of Operation
437,857 Ones Counting Circuit and Method of
Operation
437,851 Memory Circuit Reconfigurable as Data Memory
or Instruction Cache and Method of Operation
437,875 Switch Matrix Having Integrated Crosspoint
Logic and Method of Operation
______________________________________
BACKGROUND OF THE INVENTION
A picture is worth a thousand words is as true today as it ever was. Visual
images form a fundamental part of our lives, from body language to
subliminal messages buried in a picture. Therein lies the challenge;
namely, to have a computer "read" visual images and interpret the true
message of the image.
The usefulness of such intelligent visual imaging computers is far
reaching. On a simple level, the imaging computer could be built into a
copy machine (or a facsimile machine) and used to clean the copied image.
This could be accomplished, for example, by having the computer scan the
image, determine the proper outlines or other pertinent characteristics of
the image, and then enhance those characteristics while removing any
imperfections, such as extraneous dots and dark marks.
Other practical applications of such an imaging computer could be to
monitor the physical movements of a person's extremities, such as a hand
or arm, and determine from the movements what the person is saying. This
type of action would also require image processing of a high degree.
Still other applications of such a processing system would be the
understanding of symbols and relationships so that the symbols in a
document, whether taken singularly or as a whole, would be "understood" by
the imaging processor and used for creating the appropriate response as an
output.
To accomplish such a formidable task, the image processing computer would
have to process a vast amount of image pixel data in real time and
manipulate those pixels in conjunction with many data bases. When it is
understood that each image line of a typical visual image screen contains
1024 pixels, (high definition imaging systems have over 2000 pixels) with
each pixel containing, perhaps as many as thirty-two data bits, with a
typical image containing perhaps 1,000 lines, the magnitude of this task
can be appreciated. Coupled with this, some of the pixels must be compared
with other pixels, some pixels must be manipulated in certain ways, while
still other pixels must be transformed according to special algorithms.
All of this results in a magnitude of operations heretofore only
accomplished by the largest, fastest computers.
In addition, because of the different types of operations such an imaging
processor would be called upon to perform, very different internal
structures must be utilized. In one situation it is desirable to have many
processors, each capable of working independently on different parts of an
image. This independence then presumes a parallel processing structure
with the different processors having concurrent access to any memory area.
However, in situations where all of the image must be processed dependent
upon pixel information of many other parts of the image, an operating
structure is required where many processors, or a single processor, has
access to one or more memories, perhaps on an exclusive basis. Making
matters even more difficult is the fact that during the actual processing
of an image, several different competing internal operating structures may
be necessary, thereby requiring close internal system communication.
It is thus a desirable objective to create an image processing system
capable of fast, efficient image pixel manipulations while doing so at a
cost and at a size where the processing can be incorporated easily into
daily life.
Thus, it is desirable to have a relatively compact processing system having
large memory capacity as well as large processing capacity while still
maintaining the flexibility of accomplishing a myriad of diverse and
structurally competitive processing feats.
SUMMARY OF THE INVENTION
These problems have been solved by designing a multi-processing system to
handle image processing and graphics and by constructing a crossbar switch
capable of interconnecting any processor with any memory in any
configuration for the interchange of data. The system is capable of
connecting n parallel processors to m memories where m is greater than n.
In one embodiment, the entire processing system is constructed on a single
silicon chip.
The image processing system contains several independently addressable
memories all connectable via the cross bar switch to any processor. The
processors can run independently in the multiple instruction, multiple
data (MIMD) mode or in the single instruction, multiple data (SIMD) data
mode. Close internal communication between the processors allows them to
efficiently switch between one or the other modes. The memories can be
shared by all processors or certain processors may, for periods of time,
gain exclusive access to one or more memories.
The image processor has been incorporated into an imaging system which can
analyze image pixel information using any number of algorithms. Different
ones of these algorithms, which can be used to process all of an image or
parts of an image, can run simultaneously on the same data using different
processors. This then allows the image to be examined, for example, to
determine the meaning of the image.
Using this approach, the movements of a hand in front of a camera can be
interpreted by the imaging system. This allows the image processing system
to operate in a "signing" mode to provide intelligent information to a
user of the system.
One example of such a system would be a system that cleans documents by
removing the extraneous marks on a page. This would be accomplished by
passing the image of the page through certain algorithms in real time
thereby determining exactly what the new page should look like.
Another example would be to provide audible or other command information
from the received video images, for example from a TV screen. This could
be used in commercial broadcasting (or consumer products) where certain
video movements could trigger remote operations or in facsimile
transmission where the received image is passed through the processor for
image clarification purposes. The video image itself would be enhanced
using the image processor to compare the individual pixel information to
other received pixel information and to correct some pixels according to a
certain set of algorithms.
BRIEF DESCRIPTION OF THE DRAWINGS
For a more complete understanding of the present invention and for further
advantages thereof, reference is now made to the following detailed
description taken in conjunction with accompanying drawings in which
FIGS. 1 and 2 show an overall view of the elements of the image processing
system;
FIG. 3 shows a series of image processing systems interconnected together
into an expanded system;
FIG. 4 shows details of the crossbar switch matrix interconnecting the
parallel processors and the memories;
FIGS. 5 and 6 show prior art configurations;
FIG. 7 shows an improved configuration;
FIGS. 8 and 9 show prior art schematic representations of processor memory
interaction;
FIG. 10 shows some reconfigurable modes of operations of an improved
multi-processor;
FIG. 11 is a graph showing some algorithms and control for the image
processing system;
FIGS. 12-15 show image pixel flow for SIMD and MIMD operational modes;
FIG. 16 shows the interrupt polling communication between the processors;
FIG. 17 shows a schematic representation of the layout of the processors
and memory interconnected by the crossbar switch;
FIGS. 18 and 19 show details of the crosspoints of the crossbar switch;
FIG. 20 is a graph of wave forms of the contention logic for memory access;
FIGS. 21-23 show the synchronization control between processors;
FIGS. 24-27 show details of the sliced addressing technique;
FIG. 28 shows details of the rearrangement of the instruction data memory
for the SIMD/MIMD operational modes;
FIG. 29 shows details of a master processor;
FIGS. 30-34 show details of the parallel processors;
FIGS. 35-45 show figures useful in understanding methods of operation of
the parallel processor;
FIGS. 46-48 show an image processor operating as a personal computer;
FIGS. 49-52 show system arrangements for use of the imaging system on a
local and remote basis;
FIG. 53 is a functional block diagram of an imaging system;
FIG. 54 is a logic schematic of the ones counting circuit matrix;
FIG. 55 is a logic schematic of a minimized matrix of the ones counting
circuit;
FIG. 56 is an example of an application of a ones counting circuit;
FIG. 57 shows a block diagram of the transfer processor;
FIG. 58 shows a block diagram of the parallel processor system used with a
VRAM; and
FIGS. 59-64 show various operational mode relationships.
DETAILED DESCRIPTION OF THE INVENTION
Prior to beginning a discussion of the operation of the system, it may be
helpful to understand how parallel processing systems have operated in the
prior art.
FIG. 5 shows a system having parallel processors 50-53 accessing a single
memory 55. The system shown in FIG. 5 is typically called a shared memory
system where all of the parallel processors 50-53 share data in and out of
the same memory 55.
FIG. 6 shows another prior art system where memory 65-68 is distributed
with respect to processors 60-63 on a one-for-one basis. In this type of
system, the various processors access their respective memory in parallel
and thus operate without memory contention between the processors. The
system operating structures shown in FIGS. 5 and 6, as will be discussed
hereinafter, are suitable for a particular type of problem, and each is
optimized for that type of problem. In the past, systems tended to be
either shared or distributed.
As processing requirements become more complex and the speed of operation
becomes critical, it is important for systems to be able to handle a wide
range of operations, some of which are best performed in the shared memory
mode, and some of which are best performed in a distributed memory mode.
The structure shown in FIGS. 1 and 2 accomplishes this result by allowing
a system to have parallel processing working both in the shared and in the
distributed mode. While in these modes, various operational arrangements
such as SIMD and MIMD can be achieved.
Multi-Processors and Memory Interconnection
As shown in FIG. 1, there is a set of parallel processors 100-103 and a
master processor 12 connected to a series of memories 10 via a cycle-rate
local connection network switch matrix 20 called a crossbar switch. The
crossbar switch, as will be shown, is operative on a cycle by cycle basis
to interconnect the various processors with the various memories so that
different combinations of distributed and shared memory arrangements can
be achieved from time to time as necessary for the particular operation.
Also, as will be shown, certain groups of processors can be operating in a
distributed mode with respect to certain memories, while other processors
concurrently can be operating in the shared mode with respect to each
other and with respect to a particular memory.
Another view of the system is shown in FIG. 2 in which the four parallel
processors 100, 101, 102, 103 are shown connected to memory 10 via switch
matrix 20 which is shown in FIG. 2 as a distributed bus. Also connected to
memory 10 via crossbar switch 20 is transfer processor 11 and master
processor 12. Master processor 12 is also connected to data cache 13 via
bus 171 and instruction cache 14 via bus 172. The parallel processors 100
through 103 are interconnected via communication bus 40 so that the
processors, as will be discussed hereinafter, can communicate with each
other and with master processor 12 and with transfer processor 11.
Transfer processor 11 communicates with external memory 15 via bus 21.
Also in FIG. 2, frame controllers 170 are shown communicating with transfer
processor 11 via bus 110. Frame controllers 170 serve to control image
inputs and outputs as will be discussed hereinafter. These inputs can be,
for example, a video camera, and the output can be, for example, a data
display. Any other type of image input or image output could also be
utilized in the manner to be more fully discussed hereinafter.
Crossbar switch 20 is shown distributed, and in this form tends to mitigate
communication bottlenecks so that communications can flow easily between
the various parts of the system. The crossbar switch is integrated on a
single chip with the processors and with the memory thereby further
enhancing communications among the system elements.
Also, it should be noted that fabrication on a chip is in layers and the
switch matrix may have elements on various different layers. When
representing the switch pictorially, it is shown in crossbar fashion with
horizontals and verticals. In actual practice these may be all running in
the same direction only separated spatially from one another. Thus, the
terms horizontal and vertical, when applied to the links of the switch
matrix, may be interchanged with each other and refer to spatially
separated lines in the same or different parallel planes.
Digressing momentarily, the system can operate in several operational
modes, one of these modes being a single instruction multiple data (SIMD)
mode where a single instruction stream is supplied to more than one
parallel processor, and each processor can access the same memory or
different memories to operate on the data. The second operational mode is
the multiple instruction, multiple data mode (MIMD) where multiple
instructions coming from perhaps different memories operate multiple
processors operating on data which comes from the same or different memory
data banks. These two operational modes are but two of many different
operational modes that the system can operate in, and as will be seen, the
system can easily switch between operational modes periodically when
necessary to operate the different algorithms of the different instruction
streams.
Returning briefly to FIG. 1, master processor 12 is shown connected to the
memories via crossbar switch 20. Transfer processor 11, which is also
shown connected to crossbar switch 20, is shown connected via bus 21 to
external memory 15. Also note that as part of memory 10, there are several
independent memories and a parameter memory which will be used in
conjunction with processor interconnection bus 40 in a manner to be more
fully detailed hereinafter. While FIG. 2 shows a single parameter memory,
in actuality the parameter memory can be several RAMS per processor which
makes communication more efficient and allows the processors to
communicate with the RAMS concurrently.
FIG. 4 shows a more detailed view of FIGS. 1 and 2 where the four parallel
processors 100-103 are shown interconnected by communication bus 40 and
also shown connected to memory 10 via crossbar switch matrix 20. The
various crosspoints of the crossbar switch will be referred to by their
coordinate locations starting in a lower left corner with 0-0. In the
numbering scheme, the vertical number will be used first. Thus, the lower
left corner crosspoint is known as 0-0, and the one immediately to the
right in the bottom row would be 1-0. FIG. 19 which will be discussed
hereinafter, shows the details of a particular crosspoint, such as
crosspoint 1-5. Continuing now in FIG. 4, the individual parallel
processors, such as parallel processor 103, are shown having a global data
connection (G), a local data connection (L) and an instruction connection
(I). Each of these will be detailed hereinafter, and each serves a
different purpose. For example, the global connection allows processor 103
to be connected to any of the several individual memories of memory 10,
which can be for data from any of the various individual memories.
The local memory ports of the parallel processors can each address only the
memories that are served by three of the vertical switch matrix links
immediately opposite the processors. Thus, processor 103 can use verticals
0, 1 and 2 of crossbar 20 to access memories 10-16, 10-15 and 10-14 for
data transfer in the MIMD mode. In addition, while in the MIMD mode,
memory 10-13 supplies an instruction stream to processor 103. As will be
seen, in SIMD mode all of the instructions for the processors come from
memory 10-1. Thus, instruction memory 10-13 is available for data. In this
situation, the switch is reconfigured to allow access via vertical 4 of
crossbar 20. The manner in which crossbar 20 is reconfigured will be
discussed hereinafter.
As shown in FIG. 4, each parallel processor 100-103 has a particular global
bus and a particular local bus to allow the processor access to the
various memories. Thus, parallel processor 100 has a global bus which is
horizontal 2 of crossbar 20, while parallel processor 101 has a global bus
which is horizontal 3 of crossbar 20. Parallel processor 102 has as its
global bus horizontal 4, while parallel processor 103 has as its global
bus horizontal 5.
The local buses from all of the processors share the same horizontal 6.
However, horizontal 6, as can be seen, is separated into four portions via
three-state buffers 404, 405 and 406. This effectively provides isolation
on horizontal 6 so that each local input to each processor can access
different memories. This arrangement has been constructed for efficiency
of layout area on the silicon chip. These buffers allow the various
portions to be connected together when desired in the manner to be
detailed hereinafter for the common communication of data between the
processors. This structure allows data from memories 10-0, 10-2, 10-3 and
10-4 to be distributed to any of the processors 100-103.
When the processor is operating in the MIMD operational mode, the
instruction port of the processors, for example, the instruction port of
processor 103, is connected through crosspoint 4-7 to instruction memory
10-13. In this mode crosspoints 4-2, 4-3, 4-4, 4-5 and 4-6, as well as
4-1, are disabled. In this mode crosspoint 4-0 is a dynamically operative
crosspoint, thereby allowing the transfer processor to also access
instruction memory 10-13, if necessary. This same procedure is available
with respect to crosspoint 9-7 (processor 102) and crosspoint 14-7
(processor 101).
When the system is in the SIMD mode crosspoint 4-7 is inactive, and
crosspoints 4-2 through 4-6 may be activated, thereby allowing memory
10-13 to become available for data to all of the processors 100-103 via
vertical 4 of crossbar 20. Concurrently, while in the SIMD mode buffers
401, 402 and 403 are activated, thereby allowing instruction memory 10-1
to be accessed by all of the processors 100-103 via their respective
instruction inputs. If buffer 403 is activated, but not buffers 401 and
402, then processors 100 and 101 can share instructor memory 10-1 and
operate in the SIMD mode while processors 102 and 103 are free to run in
MIMD mode out of memories 10-13 and 10-9 respectively.
Crosspoints 18-0, 13-0, 8-0 and 3-0 are used to allow transfer processor 11
to be connected to the instruction inputs of any of the parallel
processors. This communication can be for various purposes, including
allowing the transfer processor to have access to the parallel processors
in situations where there are cache misses.
FIG. 7 is a stylized diagram showing the operation of parallel processors
100-103 operating with respect to memories 55 and 55A in the shared mode
(as previously discussed with respect to FIG. 5) and operating with
respect to memories 65-68 in the distributed mode (as previously discussed
with respect to FIG. 6). The manner of achieving this flexible arrangement
of parallel processors will be discussed and shown to depend upon the
operation of crossbar switch 20 which is arranged with a plurality of
links to be individually operated at crosspoints thereof to effect the
different arrangements desired.
Before progressing to discuss the operation of the crossbar switch, it
might be helpful to review FIG. 3 and alternate arrangements where a bus
34 can be established connected to a series of processors 30-32, each
processor having the configuration shown with respect to FIGS. 1 and 2.
External memory 35 is shown in FIG. 2 as a single memory 15, the same
memory discussed previously. This memory could be a series of individual
memories, both local and located remotely. The structure shown in FIG. 3
can be used to integrate any number of different type of processors
together with the image system processor discussed herein, assuming that
all of the processors access a single global memory space having a unified
addressing capability. This arrangement also assumes a unified contention
arrangement for the memory access via bus 34 so that all of the processors
can communicate and can maintain order while they each perform their own
independent operations. Host processor 33 can share some of the policing
problems between the various processors 30-32 to assure an orderly flow of
data via bus 34.
Image Processing
In image processing there are several levels of operations that can be
performed on an image. These can be thought about as being different
levels with the lowest level being simply to message the data to perform
basic operations without understanding the contents of the data. This can
be, for example, removal of extraneous specks from an image. A higher
level would be to operate on a particular portion of the data, for
example, recognizing that some portion of the data represents a circle,
but not fully understanding that the circle is one part of a human face. A
still higher operational aspect of image processing would be to process
the image understanding that the various circles and other shapes form a
human image, or other image, and to then utilize this information in
various ways.
Each of these levels of image processing is performed most efficiently with
the processors operating in a particular type of operational mode. Thus,
when operations are performed on data locally grouped together without an
attempt to understand the entire image, it is usually more efficient to
use the SIMD operational mode where all, or a group of, processors operate
from a single instruction and from multiple data sources. When operating
in a higher mode where image pixel data is required from various aspects
of the entire image in order to understand the entire image, the most
efficient operational mode would be the MIMD mode where the processors
each operate from individual instructions.
It is important to understand that when the system is operating in the SIMD
mode, the entire pixel image can be processed through the various
processors operating from a single instruction stream. This would be, for
example, when the entire image is to be cleaned, or the image is enhanced
to show various corners or edges. Then all of the image data passes
through the processors in the SIMD mode, but at any one time data from
various different areas of the image cannot be processed in a different
manner for different purposes. The general operational characteristic of a
SIMD operation is that at any period of time a relatively small amount of
the data with respect to the entire image is being operated on. This is
followed, in sequential fashion, by more data being operated on in the
same manner.
This is in contrast to the MIMD mode where data from various parts of the
image is being processed concurrently, some using different algorithms. In
this arrangement, different instructions are operating on different data
at the same time to achieve a desired result. A simple example would
include many different SIMD algorithms (like clean, enhance, extract)
operating concurrently or pipelined on many different processors. Another
example with MIMD would include the implementation of algorithms with the
same data flow although using unique arithmetic or logical functions.
FIGS. 8 and 9 show the prior art form of the SIMD and MIMD processors with
their respective memories. These are the preferred typologies for
SIMD/MIMD for image processing. The operational modes of the system will
be discussed more fully with respect to FIGS. 59-64. In general, data
paths 80 of FIG. 8 corresponds to data paths 6010, 6020, 6030 and 6040 of
FIG. 60, while processors 90 of FIG. 9 corresponds to processors 5901,
5911, 5921, 5931 of FIG. 59. The controller (6002 of FIG. 60) for the data
paths is not shown in FIG. 8.
Reconfigurable SIMD/MIMD
FIG. 10 shows the reconfigurable SIMD/MIMD topology of this invention where
several parallel processors can be interconnected via crossbar switch 20
to a series of memories 10 and can be connected via a transfer processor
11 to external memory 15, all on a cycle by cycle basis.
One of the problems of operating in the MIMD topology is that data access
can require high bandwidth as compared to operation in the SIMD mode where
the effective data flow is on a serial basis or is emulated in the
topology. Thus, in the SIMD mode, the data typically flows sequentially
through the various processors from one processor to the next. This can be
a blessing as well as a problem. The problem arises in that all of the
data of the image has to be processed in order to arrive at a certain
point in the processing. This is accomplished in the SIMD mode in a serial
fashion. However, the MIMD mode solves this type of a problem because data
from the individual memories can be obtained at any time in the cycle, as
contrasted to the operation in the SIMD where the shared memory can only
be accessed upon a serial basis as the data arrives.
However, the MIMD mode has operational bottlenecks when it is required to
have interprocessor communication since then one processor must write the
data to a memory and then the other processor must know the information is
there and then access that memory. This can require several cycles of
operational time and thus large images with vast pixel data could require
high processing times. This is a major difficulty. In the structure of
FIG. 10, as discussed, these problems have been overcome because the
crossbar switch can serve to, on a cycle by cycle basis if necessary,
interconnect various processors together to work from a single instruction
for a period of time or to work independently so that data which is stored
in a first memory can remain in that memory while a different processor is
for, one cycle or for a period of time, connected to that same memory. In
essence, in some of the prior art, the data must be moved from memory to
memory for access by the various processors, which in the instant system
the data can remain constant in the memory while the processors are
switched as necessary between the memories. This allows for complete
flexibility of processor and memory operation as well as optimal use of
data transfer resources.
A specific example of the processing of data in the various SIMD and MIMD
modes can be shown with respect to FIGS. 12 and 13. In FIG. 12 there is
shown an image 125 having a series of pixels 0-n. Note that while in the
image a row is shown having only four pixels, this is by way of example
only, and a typical image would have perhaps a thousand rows, each row
having a thousand pixels. At any one point in time the number of pixels in
a row and the number of rows will vary. For ou | | |
