Image compression/expansion using parallel decomposition/recomposition

• US 6,298,162 B1
• Filed: 02/21/1995
• Issued: 10/02/2001
• Est. Priority Date: 12/23/1992
• Status: Expired due to Term

• Current Assignee: Hanger Solutions, LLC (IP Investments Group LLC)
• Original Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Inventors: Long, Dan T., Sutha, Surachai
• Primary Examiner(s): Coulter, Kenneth R.
• Application Number:
  US08/391,263
• Time in Patent Office: 2,415 Days
• Field of Search: 395/375, 358/426, 382/232, 382/233, 382/234, 382/240
• US Class Current: 382/234
• CPC Class Codes: G06T 1/20 Processor architectures; Processor configuration, e.g. pipelining

Abstract

A fast method with logarithmic complexity for image compression and expansion is provided, implementable on the Geometric Arithmetic Parallel Processor (GAPP) or any similar fine-grained, mesh-connected Single Instruction-Multiple Datastream (SIMD) array processor. Efficient decomposition of the original image into multiple subimages enables the method to exploit the parallelism of the SIMD computer for implementing powerful multiresolution pyramid and hierarchical image processing techniques on a massively parallel processor.

Claims

1. A method for implementing a compressive transformation of a first representation of a pattern of information made up of a plurality of picture elements into a second representation of the pattern of information, the method comprising the steps of:

first parallel aggregation of selected ones of said plurality of picture elements into first aggregates, wherein each of said first aggregates includes a copy of more than one of said picture elements; and

second parallel aggregation of said first aggregates into second aggregates, wherein each second aggregate includes a copy of more than one of said first aggregates.

2. A method for implementing an expansive transformation of a first representation of a pattern of information made up of a plurality of picture elements into a second representation of the pattern of information, the method comprising the steps of:

first parallel separation of selected ones of said plurality of picture elements into first aggregates, wherein each of said first aggregates includes copies of fewer of said plurality of picture elements than said first representation; and

second parallel separation of said first aggregates into second aggregates, wherein each second aggregate includes copies of fewer of said plurality of picture elements than each of said first aggregates.

3. A device for transforming a first representation of an information pattern made up of a plurality of picture elements into a second representation of the information pattern, the device comprising:

first means for parallel aggregation of selected ones of said plurality of picture elements into first aggregates, wherein each of said first aggregates includes a copy of more than one of said picture elements; and

second means for parallel aggregation of said first aggregates into second aggregates, wherein each second aggregate includes a copy of more than one of said first aggregates.

4. A device for implementing a compressive transformation of a first representation of a pattern of information made up of a plurality of picture elements into a second representation of the pattern of information, the device comprising:

first means for parallel aggregation of selected ones of said plurality of picture elements into first aggregates, wherein each of said first aggregates includes a copy of more than one of said picture elements; and

second means for parallel aggregation of said first aggregates into second aggregates, wherein each second aggregate includes a copy of more than one of said first aggregates.

5. A device for implementing an expansive transformation of a first representation of a pattern of information made up of a plurality of picture elements into a second representation of the pattern of information, the device comprising:

first means for parallel separation of a set of said plurality of picture elements of said first representation into first subsets, wherein each of said first subsets includes copies of fewer of said picture elements than said set; and

second means for parallel separation of said first subsets into second subsets, wherein each of said second subsets includes copies of fewer picture elements than said first subset from which said second subset was obtained.

6. A method of scaling a digital representation of an image, said image being divided into M rows and N columns of P picture elements, M and N being positive integers and P being the product of M and N, said digital representation comprising P digital values each respectively indicative of a characteristic of an associated one of said P picture elements, into a scaled digital representation of said image, said scaled digital representation comprising Q digital values, Q being the product of P and a scaling factor L, said method comprising the steps of:

loading said digital representation into a processor comprising an array of at least M rows and N columns of processing elements so that each of said processing elements stores an associated loaded one of said P digital values as a stored value;

controlling each row of at least two pairs of rows of processing elements, paired rows being separated by S rows, S being related to L, to operate in parallel to cause each processing element in said each row to replace its associated loaded value as its stored value with the associated loaded digital value from a processing element in the same column at a preselected number of rows away, at least one row of each pair being one of said M rows; and

controlling each column of at least two pairs of columns of processing elements, paired columns being separated by S columns, to operate in parallel to cause each processing element in said each column to replace its associated loaded value as its stored value with the associated loaded digital value from a processing element in the same row at a preselected number of columns away, at least one column of each pair being one of said N columns.

7. The method of claim 6, wherein said scaling is a compression of said digital representation of an image, said image being divided into M rows and N columns of P picture elements, M and N being positive integers and P being the product of M and N, said digital representation comprising P digital values each respectively indicative of a characteristic of an associated one of said P picture elements, into a scaled digital representation of said image, said scaled digital representation comprising Q digital values, Q being the product of P and a scaling factor L, said method comprising the steps of:

loading said digital representation into a processor comprising an array of at least M rows and N columns of processing elements so that each of said processing elements stores an associated loaded one of said P digital values as a stored value;

controlling each row of at least two pairs of rows of processing elements, paired rows being separated by S rows, S being related to L, to operate in parallel to cause each processing element in said each row to replace its associated loaded value as its stored value with the associated loaded digital value from a processing element in the same column at a preselected number of rows away, at least one row of each pair being one of said M rows; and

controlling each column of at least two pairs of columns of processing elements, paired columns being separated by S columns, to operate in parallel to cause each processing element in said each column to replace its associated loaded value as its stored value with the associated loaded digital value from a processor in the same row at a preselected number of columns away, at least one column of each pair being one of said N columns.

8. A device for transforming a first representation of an information pattern made up of a plurality of picture elements into a second representation of the information pattern, the device comprising:

first means for parallel aggregation of selected ones of said plurality of picture elements into first aggregates, wherein each of said first aggregates includes a copy of more than one of said plurality of picture element; and

second means for parallel aggregation of said first aggregates into second aggregates, wherein each second aggregate includes a copy of more than one of said first aggregates;

wherein said first and second means for parallel aggregation further comprise a parallel data processor having a plurality of substantially identical cells for processing digital data signals, said parallel data processor further comprising;

a controller for generating control signals in response to program instructions; and

a plurality of substantially identical interconnected cells each including a full adder having two data input terminals, a carry input terminal, a sum output terminal, and a carry output terminal, and a plurality of memories connected to said full adder and said controller, the memories each being individually controllable to supply selected ones of a plurality-of predetermined data signals to the input terminals of said full adder in response to control signals from the controller, the memories being connected to the full adder and the controller such that both logical and arithmetic operations are performed by the full adder.

9. A device for transforming a first representation of an information pattern made up of a plurality of picture elements into a second representation of the information pattern, the device comprising:

first means for parallel aggregation of selected ones of said plurality of picture elements of said first representation into first aggregates, wherein each of said first aggregates includes a copy of more than one of said plurality of picture elements; and

second means for parallel aggregation of said first aggregates into second aggregates, wherein each second aggregate includes a copy of more than one of said first aggregates;

wherein said first and second means for parallel aggregation further comprise a parallel data processor having a plurality of substantially identical cells for processing digital data signals, said parallel data processor further comprising;

a controller for generating control signals; and

a plurality of identical cells, each of said identical cells being connected to at least one neighboring cell and responsive to said controller, and adapted to process data from said at least one neighboring cell in accordance with said control signals, said cell including a memory segmented into at least two blocks to be able to perform more than one read/write operation per clock cycle at the direction of said controller.

10. A device for transforming a first representation of an information pattern made up of a plurality of picture elements into a second representation of the information pattern, the device comprising:

first means for parallel aggregation of selected ones of said plurality of picture elements of said first representation into first aggregates, wherein each of said first aggregates includes a copy of more than one of said plurality of picture elements; and

second means for parallel aggregation of said first aggregates into second aggregates, wherein each second aggregate includes a copy of more than one of said first aggregates;

wherein said first and second means for parallel aggregation further comprise a parallel data processor having a plurality of substantially identical cells for processing digital data signals, said parallel data processor further comprising;

a controller for generating control signals; and

a plurality of identical cells, each of said identical cells being connected to at least one neighboring cell and responsive to said controller, and adapted to process data from said at least one neighboring cell in accordance with said control signals, said cell including a memory having at least two ports to be able to perform more than one read/write operation per clock cycle at the direction of said controller.