Image Compression - Past, Present and Future
What will be the Role of Hard Disk Recording Technologies?

By Simon Cope

Since the early beginnings of digital imagery people have used various forms of compression. The primary driver for this was almost always size related because imagery takes up a lot of space - doubling the resolution of vector data has little real effect on data sizes, whereas doubling the resolution of imagery increases storage requirements four fold.

Figure 1: Single untiled wavelet pyramid.

Compression Ratios

Spatial imagery usually involves very large volumes of data. Therefore compression efficiency becomes important both in terms of compression ratios achievable for a certain quality result and throughput of the codec. This is a set of instructions capable of performing encoding and decoding on a digital data stream or signal. In this case, the codec are the instructions telling the computer how to compress or uncompress an image. Until about a decade ago most compression codec’s used were either LZW, a universal lossless data compression algorithm, or DCT, discrete cosine transform, based. LZW compression is used for lossless compression giving relatively small compression ratios but retaining 100 per cent of the original quality.  LZW compression is used with TIF images. DCT, or discrete cosine transform, style codecs are used by the venerable JPEG format. DCT allows significant file size compression – by removing “redundant” pixels from the image. This can dramatically affect the quality of the image though.

Wavelet Based Formats
The introduction of DWT (Wavelet) based compression formats was really somewhat of a revelation as suddenly ratios as high as 35:1 were achievable whilst retaining sufficient quality in the compressed imagery for the majority of uses. Wavelet based formats also have another major benefit – the multi-resolution pyramid provides the basis needed to efficiently extract arbitrary views, something lacking in common graphics formats such as TIFF and JPEG which were never designed for large images. The better wavelet formats, including ECW, also resolved a number of other limitations such as supporting files over 4GB in size, and supporting arbitrary numbers of image bands. We at ER Mapper believe the ECW format is a major factor in the acceptance of highly compressed imagery. ECW offers good compression ratios, quality and performance, free compressors, application plug-ins and viewers, and we made Software Development Kits’s  available free to other companies very early on under very liberal licensing terms. This licensing regime meant that other application developers could put ECW support into their application without charge. In many countries over 90 per cent of all aerial imagery sold today is shipped in ECW format. Other vendors tried to build business models around selling basic compression and decompression and that was never going to work because you are exposed to someone giving the stuff away, which is exactly what we did. 

Figure 2: Multiple small tile wavelet pyramids.

ISO JPEG 2000
Late in 2000 the ISO JPEG 2000 format was finally ratified. JPEG 2000 provides a plethora of features intended to enable the format into be used in almost any conceivable imagery application from digital cameras to spatial imagery and medical. It took about four years to really gain any momentum due to factors such as incompatibilities between various JPEG 2000 implementations, lack of market demand, lackluster performance from many implementations, and lack of metadata standards for specific markets. The needs for spatial imagery are significantly more demanding than most applications of JPEG 2000, yet unfortunately many of the implementations available are shoehorned into spatial software with little regard for addressing their many shortcomings. Most have problems dealing with the image sizes we typically deal with on a daily basis. We actually do a fair bit of business selling our JPEG 2000 SDK to other spatial software vendors to replace their existing solution because a lot of them benchmark well on a 50MB file but are completely useless with 2TB files, despite everyone claiming compliance with the specifications. The compliance test is actually easy to pass, and passing it doesn’t mean your software will actually work on real data.

Quantity Over Quality?
Compatibility problems are exasperated by the complexity of the format, and vendors simply providing users with too many of the available JPEG 2000 options. There are many possible encoding parameters available and many combinations of them produce images that are not very suitable for a lot of uses. Unfortunately many software vendors seem to believe in quantity over quality when it comes to providing options to their end users. As a simple example, JPEG 2000 files can consist of one or more tiles. A tile can be quite small up to extremely large – 2^32 pixels in each dimension. Some of the poorly written JPEG 2000 implementations actually require the use of tiles as they are memory bound and have to hold the entire tile in memory to perform the wavelet transform (it is actually possible to perform the DWT transform using as little as approximately 18*Width bytes of memory). 

Untiled and Tiled
Although tiling the image may sound like a reasonable process, in fact it imposes severe limitations on the use of the file. Consider the two diagrams, see figures 1 and 2, which represent the wavelet pyramid for an untiled and tiled wavelet compressed image. In the untiled case a number of operations are quite efficient. Extracting a low-resolution thumbnail for instance is usually a single data read from the file. In the tiled case the lowest resolution level from each pyramid must be read and then reassembled into the thumbnail – considerably more work. Similar problems exist extracting arbitrary views as they typically intersect more than one pyramid and this adds considerable Input/Output burden on the computer as the data for each tile is generally spread throughout the file. The real use for tiling JPEG 2000 files is to enable efficient ‘chipping’ of the file, for example by placing the tile boundaries at map sheet boundaries an arbitrary standalone image can be relatively easily extracted. In practice this will represent an extremely small percentage of overall usage. There are several other features of JPEG 2000 that have similar pitfalls for unwary users, and this is the reason we provide so few encoding options in ER Mapper’s software. We actually produce JPEG 2000 files as similar in structure as possible to ECW as this has been found to work best for most spatial imagery applications. Extra options would simply cause more problems than they solve.

Cost of Disk Storage
In the future compression will most likely become even more important, despite the rapidly dropping price of disk storage. The reason for this is that the IOps cost of disk is not changing, and in fact is almost constant irrespective of drive technology and capacity at around $2 per IO per second. So 10TB of disk may only cost $5000 using 500GB SATA drives but providing enough IOps to serve that data to 10,000 concurrent users requires a lot more than 20 disks. Higher compression ratios help relieve IO pressure because the data is closer together on disk resulting in more IOps all else equal. Disk seek rates are measured as the average seek time from the center track to each edge and might measure 5ms for a SCSI disk and 12ms for SATA drives, but track-to-track seek times may be as low as 0.2ms, so placing the data closer together effectively improves the seek time of the drive because it reduces the average track seek span. The actual processing resources required to compress and decompress the imagery will become irrelevant in the future. The sheer computing power available in the near term will effectively render Central Processing Unit (CPU) a free resource. Trading CPU against IO costs will remain a winning proposition for the foreseeable future. The future need for compression will also be driven by the rapid uptake of digital aerial cameras, some of which can produce several TB of data per day. Effective exploitation of this type of data may require producing several mosaics of a given area of interest using different parts of each frame, each frame having very high overlap. Use of this imagery requires very efficient delivery to the end user and thus compression is an additional benefit when either copying or streaming imagery around networks.

Future Compression Algorithms
It will be interesting to see what future compression algorithms are like. Although wavelet compression seems relatively recent, wavelets as a mathematical method actually date back over 100 years. All we are really seeing now is more functionality around existing compression concepts, JPEG 2000 really doesn’t compress any better than previous proprietary formats but certainly has a lot of other useful features. When you research something like hard disk recording technologies and the strategies they employ to encode the data on the magnetic platters you begin to realize we are probably only scratching the surface of what might be possible in the future.

Simon Cope (Simon.cope@ermapper.com) is a Chief Software Architect with ER Mapper, www.ermapper.com.