| IMAGE COMPRESSION
Massive Raster Imagery
A new standard for compressing and displaying files is born
By John R. Grizz Deal Have you ever wished you could put gigabytes of raster imagery on a single CD ROM? Or move that same data set across the Internet instantly? Or really make use of a large raster image inside your favorite GIS software? Although seemingly impossible, a new technology achieves all that and more by borrowing from some of the greatest mathematical minds in the world.
The amount of digital raster geospatial data is growing virtually every minute. While this more detailed imagery provides an amazing perspective on the planet for both professional and novice users, it also brings with it ever-increasing demands on computational and capital resources. Viewing and manipulating more than a single orthophoto or satellite scene requires either the patience of Job or a fresh perspective on techniques employed.
Just a few years ago, user expectations were such that just getting a set of aerial photos at an affordable price was enough. Users now expect digital versions of the data in a usable format that allows them to explore the entire dataset in an efficient manner.
Digital data providers and vendors have developed a wealth of techniques to minimize cost and computational requirements. Although many are quite useful, there are significant drawbacks: poor image quality; access to only a small sample of the entire data set. Neither are acceptable to users and sometimes seem worse than a stack of photos in a file cabinet. A Standard Born-Out of Frustration
The Multi-resolution Seamless Image Database technology was born at Los Alamos National Laboratory (LANL) in the Computer Research and Applications group. The LANL team, led by Dr. Jonathan Bradley, consisted of members with diverse backgrounds in such fields as image processing for GIS, document libraries, and image database applications. The U.S. Federal Bureau of Investigation (FBI) selected the group's wavelet-based approach to compressing fingerprint images for its massive archive (known as WSQ). This approach became the FBI standard.
What the LANL team did was merge several innovative signal processing techniques to do the following:
1. compress an image of (virtually) any size;
2. highly compress the image without causing a decrease in quality;
3. instantly decompress and open the image, even across a network. Is this starting to sound like a visual effect in some movie? You bet it is! One of the most thrilling effects in movies such as "Patriot Games" and "Men in Black" is when Harrison Ford or Tommy Lee Jones zooms into an image and instead of getting big, blocky pixels, they see better and better resolution and detail. Such functionality is the genesis behind the development of Multi-resolution Seamless Image Database, or MrSID for short.
In order to understand the problems the LANL team tackled, it's helpful to look at other techniques that attempt to solve the problems associated with instantly pushing around millions of pixels. The three traditional procedures used in solving the "big images, real fast" dilemma employ image compression, tiling schemes, and/or multi-resolution pyramids. Image Compression
The Tagged Image File Format (TIFF) was developed by the Aldus Corporation (now Adobe Systems) in order to create a standard file format for the desktop publishing market. The main issue solved by TIFF was the ability to read images across different operating systems. Since its advent, TIFF has been expanded to include many other capabilities including different color models (CMYK) and integrated LZW lossless compression.
The challenge with TIFF (and virtually every other file format) is that you have to open the entire file in order to use the data. Although lossless, LZW is very slow (both in compression and decompression) and the file size reduction is minimal. The result: TIFF files are virtually impossible to use on all but the most expensive workstations. Tiling schemes solve a bit of the TIFF aches felt in the industry, but it created others-big, slow, bulky files (see Tiling Schemes below).
The LANL team knew from experience that while TIFF was useful for what they felt were "small" images (50Mb or less), it wouldn't be efficient for storing and accessing large files needed for GIS applications (hundreds of megabytes up to tens of gigabytes). Other lossless encoding methods suffer from the same speed limitations and minimal compression ratios because images contain very little redundant data. Lossy compression provides much smaller file sizes, however, there are pitfalls in the quality of the compressed file and the ability to read the file fast.
The Joint Photographic Expert Group (JPEG) standard is based on the Discrete Cosine Transform and is an excellent attempt at trying to reduce file storage requirements and increase transmission speed. However, JPEG uses an approach that creates artifacts unacceptable for most mission critical applications.
JPEG compresses imagery by first breaking the image down into small blocks and encoding these blocks. Unfortunately when these blocks are put back together again, the edge of each block is different and the image becomes a patchwork of pieces that no longer fit together. The artifacts created by JPEG are easily seen. Your eye is wonderful at detecting edges of things (so you don't bump into doorways), and this is why the edges created by JPEG are so visible.
The other problem the LANL scientists saw with JPEG is the amount of time required to display a JPEG image. Because JPEG uses symmetrical compression, decoding takes as long as encoding and therefore takes a very long time to open a big image.
Fractals were another approach investigated by the LANL team. Fractal compression converts image data into a multi-resolution representation of the image. If you decompose the data far enough, you'll save disk space. Although Fractals provide quick decompression, they require tons of computational time and literally move geographic features. LANL quickly realized a compression technique that is not geometrically accurate wouldn't be acceptable to industry professionals.
Based on all of the above, and their success with the FBI project, Bradley and the LANL group knew that a wavelet-based compression approach was the only way to go. Wavelet mathematics encode data based on the concept of breaking down the file into different energy components and then encoding those components. Unlike JPEG, wavelet compression treats the entire image as one big block and thus avoids edge artifacts.
Preliminary tests showed that, while a wavelet-based solution provided the highest quality, they required enormous computational resources and time for both compression and decompression. Other groups had solved the quality issues, but still had not managed to solve the "big images, real fast" problem. Tiling Schemes
One way to get big images real fast is to use a lossless or lossy compressor and just break the files into small pieces. This is like building a patchwork of your image. When a lossy compressor is used, the edge of each tile is clearly visible. If tiling is used with a lossless compressor, then the size of the tile becomes a real issue. During the LANL group's survey of techniques, ArcView and other GIS software supported TIFF tiles, but again, users expressed dissatisfaction. Multi-resolution Pyramids
Image pyramids have been around for years with the approach integrated into many raster image editing packages. It has also been modified for consumer-level solutions such as FlashPix. The idea is to take the original image and then create multiple copies at smaller and smaller resolutions, interpolating the data to reduce the physical size of each level in the pyramid. While this provides the ability to zoom in and out of a large image, the data is altered and, coupled with a lossy compressor, results in an inaccurate representation of data. LANL scientists also discovered another issue: the creation of the pyramid resulted in a file significantly larger than the original (from 133 percent to 150 percent larger). This meant the compressor employed must work harder to reduce the data to something manageable. Collaboration
Bradley began to search for test data sets and discovered an ally in the U.S. Geological Survey (USGS). At that time the Survey had begun an aggressive campaign to sell their Digital Orthophoto Quadrangles (DOQ). The USGS settled on a new file standard (DOQ) and decided to use JPEG to compress imagery for distribution via CD ROM. The DOQs were based on the same system as their popular 7.5 minute topographic quadrangles.
In order to make the DOQs accessible using a personal computer, the USGS further divided their digital photo product into quarter quads (this is why when you order a DOQ from the USGS, you get four files). The images sold poorly in part as a result of the limited viewing software and the loss of image quality.
USGS personnel were frustrated and initiated the same technology evaluation and inventory as the LANL team had for alternate methods of compressing and distributing high resolution raster geo-spatial imagery. The Los Alamos scientists knew the Holy Grail of image compression for GIS applications was to be able to compress massive images using standard desktop computers and then be able to instantly display those images using a single file format across any operating system.
Several years of development followed. Interaction with the USGS, San Diego Data Processing Corporation, and others in the industry drove the LANL team to innovate at every turn. The result was a completely new approach to compressing and displaying large raster images. MrSID met all of the team's criteria: high quality, geometrically accurate compression of massive images; instant access; and multi-resolution zooming and panning of the data. A patent was applied for and granted in mid 1997. Commercialization
Using the Federal Technology Transfer acts, LANL and the University of California were empowered to select a firm as the primary commercialization vehicle for MrSID because a commercial company, motivated by profit and challenged by the market, would ensure wide distribution and use of a licensed technology. The licensee would also pay a royalty on the technologies to help fund research projects that solve unique problems and increase US competitiveness.
LANL solicited proposals and awarded LizardTech the rights to MrSID. As a spin-off from LANL, LizardTech was in a unique position to commercialize the MrSID technology.
LizardTech developed a business model based on selling MrSID encoding and compression software and giving away (or providing for a nominal cost) viewers and decompressors. In an effort to provide a complete and open solution for the industry, LizardTech makes available a MrSID decompressor software developer kit which provides the ability to read a .sid file in virtually any software package. By partnering with industry-leading software publishers and engineers LizardTech has been able to implement the MrSID technology in a broad manner, in a relatively short amount of time.
MrSID viewers are now available for ArcView by ESRI, AutoCAD Map, Adobe Photoshop, ERDAS Imagine, popular web browsers and as part of complete data packages from Space Imaging/EOSAT, Paradata, International Land Systems and Euromap. European distribution of MrSID was awarded in the Fall of 1997 to GAF (The Company for Applied Remote Sensing) based in Munich, Germany. GAF is the leading European distributor of geo-spatial data products.
After five long years of work, MrSID was released last June to rave reviews and broad industry acceptance. The United States Library of Congress Geography and Map division is putting their entire archive of maps on the Internet using MrSID and the National Geographic is using MrSID to put over 100 years of wall-sized maps on a single CD ROM. The USGS is employing MrSID as a way to distribute digital orthophotos. Earthdata International is using MrSID to compress 38Gb of aerial photos onto a single CD ROM for the U.S. Army.
Given these commercial successes, its more apparent than ever that LizardTech's efforts to commercialize and expand on the original MrSID technology (licensed from LANL) is providing a fresh perspective on what has seemed for years and insurmountable problem - big images, real fast. About the Author:
John R. Grizz Deal is the president and CEO of LizardTech, Inc. Deal holds undergraduate and graduate science degrees in geography from Texas A&M University and is a former consultant at Los Alamos National Laboratory. Back |
