Faster lossless rotation of JPEG images

Details Faster lossless rotation of JPEG images Faster lossless rotation of JPEG images

2001-07-02

2004-11-16

Johns, Andrew W. (Department: 2621)

Image analysis

Image compression or coding

Lossless compression

C382S297000

Reexamination Certificate

active

06819803

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to image data compression and image data processing and, more particularly, to compression of image data in accordance with JPEG, MPEG or other image data standards in connection with reconstruction or other processing of information such as for merge, shift, rotation and the like.
2. Description of the Prior Art
Pictorial and graphics images contain extremely large amounts of information and, if digitized to allow transmission or processing by digital data processors, often requires many millions of bytes to represent respective pixels of the image or graphics with good fidelity. The purpose of image data compression is to represent images with less data in order to save storage costs or transmission time and costs. The most effective compression is achieved by approximating the original image, rather than reproducing it exactly. The JPEG standard, discussed in detail in “JPEG Still Image Data Compression Standard” by Pennebaker and Mitchell, published by Van Nostrand Reinhold, 1993, which is hereby fully incorporated by reference, allows the interchange of images between diverse applications and opens up the capability to provide digital continuous-tone color images in multi-media applications.
JPEG is primarily concerned with images that have two spatial dimensions, contain gray scale or color information, and possess no temporal dependence, as distinguished from the MPEG (Moving Picture Experts Group) standard which additionally exploits redundancy between frames for additional compression to meet motion picture and/or television frame rate demands. The JPEG standard has been developed as a flexible system for potentially providing the highest possible image fidelity for a given amount of data while allowing the amount of data representing the image to be reduced by a substantially arbitrary factor. The JPEG standard also allows substantial exploitation of relative sensitivities and insensitivities of human visual perception and it is not unusual for the JPEG standard to allow image data compression by a factor of twenty or more without significant perceptible image degradation.
At the same time, virtually no constraints are placed on processor resources or data processing methodologies so that improvements therein that result in reduced processing time will allow increased throughput and additional processing to be achieved in environments such as high speed printers where the printer will eject blank pages if the next complete page is not ready. Nevertheless, substantial data processing is required for encoding and decoding, particularly due to the need for statistical analyses of converted image values (e.g. discrete cosine transform (DCT) coefficients) in order to assure substantial data compression in accordance with the concept of entropy coding.
The concept of entropy coding generally parallels the concept of entropy in the more familiar context of thermodynamics where entropy quantifies the amount of “disorder” in a physical system. In the field of information theory, entropy is a measure of the predictability of the content of any given quantum of information (e.g. symbol) in the environment of a collection of data of arbitrary size and independent of the meaning of any given quantum of information or symbol.
This concept provides an achievable lower bound for the amount of compression that can be achieved for a given alphabet of symbols and, more fundamentally, leads to an approach to compression on the premise that relatively more predictable data or symbols contain less information than less predictable data or symbols and the converse that relatively less predictable data or symbols contain more information than more predictable data or symbols. Thus, assuming a suitable code for the purpose, optimally efficient compression can be achieved by allocating fewer bits to more predictable symbols or values (that are more common in the body of data and include less information) while reserving longer codes for relatively rare symbols or values.
By the same token, however, the JPEG standard and other image data compression standards have substantially no implications in regard to efficiency of data processing for encoding, decoding or other desired image manipulations beyond those expected from alteration of the volume of data to be processed, transmitted or stored. On the contrary, the very flexibility of coding provided by the JPEG standard requires substantial processing to determine details of the manner in which data is to be decoded, particularly in regard to portions of the coded data which represent variable length codes necessary to efficient data compression in accordance with the principles of entropy coding.
It has been found that some processing is, in fact, complicated by some intermediate data formats which are compatible with entropy encoding into the JPEG standard but not others which are similarly compatible. These standards specify the data streams but not the intermediate formats.
It should also be appreciated that image data compression standards such as the JPEG standard are principally directed toward facilitating exploitation of the trade-off between image fidelity and data transmission and processing time or required storage capacity. However, at the current time, some applications such as high performance printers and image browsers place high demands on both image fidelity and rapid data conversion. For example, high resolution color printers are foreseeable having such high printing speed that processing power at or exceeding the limits of current practicality is required. Such applications may also require additional processing such as image rotation or size change prior to image decoding for which, as a practical matter, no time is available.
Further, it should be appreciated that some loss of fidelity is unavoidable due to the quantization of image data for digital processing. Therefore, coding and decoding is, to some degree, lossy. This lossiness is acceptable for a single coding and decoding process since the nature of quantization can be freely chosen. However, multiple coding and decoding processes which may be necessitated by a need to perform certain image manipulations, such as rotation, on decoded data (that must again be encoded and decoded for efficient processing and storage and acceptable data processing time to reconstruct the image) generally cause substantial and readily perceptible image degradation as well as requiring substantial processing time that may not be reasonably or economically available.
Rotation is often necessary since digitization of an image (including initial image capture), as a practical matter, must develop a serial data stream which necessarily corresponds to image orientation (e.g. as initially captured). The orientation of the image, as digitized, may not correspond to the desired orientation or dimensional format (e.g. so-called landscape or portrait formats in which the longer dimensions are horizontally and vertically oriented, respectively) for image reproduction by, for example, display or printing and where the image dimensions must be accommodated by the reproduction medium.
Rotation processing, in particular, has generally required operations to be performed on decoded image data which are necessarily lossy for that reason. While theoretically possible, lossless rotation of coded image data performed in the transform domain, has required extremely complex techniques with prohibitive levels of data processing.
In this regard, it should be appreciated that the JPEG standard provides an increased likelihood of grouping of zero and near-zero valued orthogonal transform coefficients (e.g. DCT coefficients) by ordering them by approximate (increasing) spatial frequency in the horizontal and vertical directions within a block of data in order to exploit relative insensitivities of human perception. As applied to a matrix of transform coefficient values, this order is referred to as a zig-zag order. It

Affiliated with

Also associated with

Rating

Faster lossless rotation of JPEG images does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Faster lossless rotation of JPEG images, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Faster lossless rotation of JPEG images will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3336384