Image analysis – Image compression or coding – Parallel coding architecture
Reexamination Certificate
1995-02-21
2001-10-02
Coulter, Kenneth R. (Department: 2154)
Image analysis
Image compression or coding
Parallel coding architecture
C382S240000
Reexamination Certificate
active
06298162
ABSTRACT:
BACKGROUND
The present invention pertains to implementation of a method for fast image compression and expansion in a Single Instruction-Multiple Datastream (SIMD) array processor, and provides real-time spatial resolution image compression and expansion processing.
Spatial resolution compression and expansion are necessary in multiresolution image processing. Existing methods for image compression and expansion require too many instructions, and may not be suitable for certain types of real-time applications.
For the purpose of this discussion, the terms compression and expansion have the following meanings. Compression means sub-sampling or reducing the spatial resolution of the given image by a factor K, where K is some small positive integer. It is equivalent to low-pass filtering. Expansion means magnifying or increasing the size of the given image by a factor K. For convenience, the methods will be explained using an example with K=2. Let I(m,n) be the original image containing 2M×2N pixels, where m=1, 2, . . . , 2M; n=1, 2, . . . 2N; M and N are positive integers. The compression of I(m,n) by a factor of 2 in both dimensions of the image yields
C(j,k)=I(2j,2k)
where C(j,k) is the compressed image; j=1, 2, . . . , M; and k=1, 2, . . . , N. Some applications may require local averaging to be performed on I(m,n) prior to the compression.
There are varying methods for achieving expansion or compression. One type of method is a sequential method; another is a parallel method such as can be implemented on a parallel processor. The complexity of a sequential method may be expressed as O(M×N), on the order of magnitude of M×N or proportional to M×N. The sequential method involves the copying of M×N selected pixels, one pixel at a time, from I(2j,2k) to C(j,k). Using a parallel method, however, image compression is performed in two stages; first, with respect to rows, and then with respect to columns. To compress the rows, image I(2j,2k) is shifted until row 2j of image I(2j,2k) aligns with row j of compressed image C(j,k) before all pixels in row 2j are copied simultaneously into compressed image C(j,k), as shown in FIGS.
12
(
a
)-(
q
) for M=16. After all selected M rows are copied, a similar process is applied to the columns. The complexity of such a parallel method may thus be expressed as O(M+N). The total number of GAPP instructions (clock cycles) required by this method for compressing a 108×384 pixel image, 8 bits per pixel, down to a 54×192 pixel image, 8 bits per pixel, is 20,316.
General mathematical properties of image compression and other digital image processing techniques are presented, for example, in
Digital Image Processing
(Addison-Wesley, 1992) by R. Gonzalez and R. Woods, and in “The Manipulation of Raster-based Topographic Data on a Parallel Processor,”
Proceedings of IEEE Computer Society Conference on Pattern Recognition and Image Processing, PRIP
-82, pp.
396-404, by T. A. Adams and K. A. Smith.
The parallel method is an example of certain data processing tasks that require that substantially identical logical or arithmetical operations be performed on large amounts of data. One approach to carrying out such tasks which is drawing increasing attention is massively parallel processing. In parallel processing, each element or cell of an array processor made up of such cells processes its own bit of data at the same time as all other cells of the array processor perform the same process on their own bit of data. Such machines are referred to by several names, including Single Instruction-Multiple Datastream (SIMD), and massively parallel array processors.
A common arrangement for such a machine is as a rectangular array of cells, with each interior cell connected to its four nearest neighboring cells and each edge cell connected to a data input/output device. Each cell is connected as well to a master controller which coordinates the movement of data through the array by providing appropriate instructions to the processing elements. When used in high resolution image processing, such processors handle the image pixels as a data matrix which can be loaded into and processed quickly and efficiently by the processor array.
Although based upon the same generic concept of an array of cells all performing the same function in unison, parallel processors vary in details of cell interconnection and design. For example, U.S. Pat. No. 4,215,401 to Holsztynski et al. discloses a cell which includes a random access memory (RAM), a single bit accumulator, and a simple logical gate. The disclosed cell is extremely simple and, hence, inexpensive and easily fabricated. A negative consequence of this simplicity, however, is that some complex computational operations are quite cumbersome so that it may require many basic operations (instructions) to perform a complex task.
U.S. Pat. No. 4,739,474, to Holsztynski et al., represents a higher level of cell complexity, in which the logic gate is replaced by a full adder capable of performing both arithmetic and logical functions. Pressing the full adder into dual service creates an efficiency which more than offsets the added complexity and cost incurred by including a full adder in each cell.
Parallel processors may also vary in the manner of cell interconnection. As mentioned above, cells are typically connected to their nearest physical neighbors. All cells except those at the edge of the entire array are connected to four neighbors. Significant benefits may, however, flow from providing for alternate paths of interconnection and, specifically, in providing programmable, flexible interconnection between cells.
SUMMARY
A fast method with logarithmic complexity for image compression and expansion is provided, implementable on a fine-grained, mesh-connected Single Instruction-Multiple Datastream (SIMD) array processor such as Martin Marietta's Geometric Arithmetic Parallel Processor (GAPP). Efficient decomposition of the original image into multiple subimages exploits the parallelism of the SIMD computer for implementing powerful multiresolution pyramid and hierarchical image processing techniques.
While the complexity (execution time) of known parallel methods is O(M+N), the complexity of the new fast parallel method of the present invention may be expressed as O(log
2
(M+1)+log
2
(N+1)), where the size of the original image is 2M×2N. The compression and expansion (for post-processing) of a 108×384×8-bit image requires about forty thousand GAPP instructions using the previously known method. The new method of the present invention requires only about eleven thousand instructions, in one exemplary embodiment.
The fast image compression and expansion implementations of the present invention are suitable for a parallel data processor comprised of an array of identical cells concurrently performing identical operations under the direction of a central controller, and incorporating one or more special cell architectures such as a segmented memory, conditional logic for preliminary processing, circuitry for indicating when the cell is active, and programmable cell interconnection including cell bypass and alternate connection of edge cells. The fast image compression and expansion implementations of the present invention are also suitable for a single instruction-multiple datastream (SIMD) systolic array processor having provision for local address generation, direct access to external devices, and programmable cell interconnectivity for providing great versatility while at the same time retaining the advantages of the SIMD architecture.
Applications include use of the fast image compression and expansion methods of the present invention for compressing and/or expanding optical images in both one and two dimensions. Results to date demonstrate compression superior (several times faster) to previously attempted compression methods. The improvement in compression (or expansion) speed will i
Long Dan T.
Sutha Surachai
Burns Doane , Swecker, Mathis LLP
Coulter Kenneth R.
Lockheed Martin Corporation
LandOfFree
Image compression/expansion using parallel... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Image compression/expansion using parallel..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image compression/expansion using parallel... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2613934