There are very few people at CUHK who do not use a word processor. But a 'picture is worth a thousand words', and indeed pictures are much more costly to process, transmit and store. For example, this article has about 1,000 words, and can be represented by about 40,000 bits. A floppy disk stores about 10 million bits, or 10 Mb, good for 250 articles of this length. One TV picture, on the other hand, is made up of some 250,000 little pixels, which will require 6 Mb to store, about 60 per cent of a floppy disk. As pictures are renewed 25 times a second on the TV screen, we are talking about 150 Mb per second. If that is hard to grasp, it means 54,000 floppy disks for storing one hour's worth of programme, not a very practical solution.

The transmission of pictures faces a similar problem. It is true that optical fibres can now carry thousands of Mb per second, but this would accommodate only a handful of TV channels if pictures are transmitted 'raw' or untreated. People are now talking about 'video on demand', in which a million households can in theory dial up and ask for a million different programmes to be fetched and transmitted, each to the TV set that demands it. New consumer products such as high definition TV (HDTV) and video phones will also need to transmit a large volume of data. The information highway provided by optical fibres would thus see a traffic jam worse than that of our Cross Harbour Tunnel.

The problem is compounded in the space programme. Many pictures of the pock-marked face of the Moon or the 'snow'-capped polar regions of Mars have been transmitted back to earth via radio waves by various spacecrafts. The Galileo spacecraft, for example, was launched by the US National Aeronautics and Space Administration (NASA) in October 1989 to probe the outer reaches of the solar system, and will soon reach Jupiter and transmit the first close-up pictures of that planet. But the high-performance antenna on Galileo has failed, and it is left with a spare low-performance antenna that transmits only 10 bits per second, hardly enough for many pictures. To make matters worse, the computer on board the Galileo was developed in those days when small PCs were only beginning to appear. It is therefore not powerful enough to handle complicated calculations required for image processing.

One answer to all these problems is image compression - any technique to store and transmit pictures using fewer bits of data. The Chinese University of Hong Kong, as a leading centre of research into information science and technology, has many on-going research projects in this area. One project that has borne fruit and received international recognition and acclaim is the work on integer cosine transform (ICT) by Dr. W.K. Cham, senior lecturer in the Department of Electronic Engineering.

Transform coding

Transform coding, the technique involved in image compression, is hardly new. The idea is based on the work of 19th century French mathematician Fourier. Take an 'irregular' wave such as that in Fig. 1a; think of it as a plot of greyness versus position. Fourier showed that it can be expressed as a sum of the 'regular' waves in Fig. 1b; the latter are called cosines (and in fact also sines). All one has to do is to specify how much (i.e. the amplitude) of each cosine and sine to take and add up; the sum is called a Fourier series. Using such a theory, scientists developed cosine transfroms in 1974. They could use about 60,000 amplitudes to specify a typical TV picture (250,000 pixels) with good effect, a saving of a factor of 4.

However, to convert a picture into the cosine amplitudes (i.e. forward transform), or vice versa (i.e. backwards transform), requires a lot of multiplications and additions. Futhermore, the amplitudes of the consines are not in integers. Most need to be represented in decimal numbers to be accurate. As a TV set displays 25 pictures every second, literally millions of multiplications may be involved in that second, an onerous task for the computer.

Integer cosine transforms (ICT)

Dr. Cham's major contribution in this area is to simplify the calculations involved. First, he replaces real number multiplications by integer multiplications. As a finite number of shades of grey are sufficient to define a good picture, the greyness can be represented as integer rather than a continuous decimal number. So one only need to multiply (and add) integers rather than decimals, hence the name integer cosine transforms. Secondly, multiplication by 10 (or 100, 1000, ...) is especially easy for humans, who count on ten fingers. Computers count on two fingers, and find it especially easy to multiply by 2 or 4. Dr. Cham showed, in a now-famous paper published in the IEE Proceedings in 1989, that one can rearrange the arithmetic so that nearly all the multiplications required can be reduced effectively to multiplication by 2 or 4, something which the computer on board the Galileo can easily handle. Dr. Cham, together with another colleague Dr. Raymond Yeung of the Department of Information Engineering, was invited to join the team of consultants at the Jet Propulsion Laboratory, NASA, for the Galileo project in mid-1993, and submitted his research report to the laboratory earlier this year.

Dr. Cham's reseach findings also make image compression on earth that much easier. Using integer cosine transforms, one can achieve a compression ratio of 20. Fig. 2a shows an untreated image. Fig. 2b is the corresponding image recovered after compression by a factor of 20.

Specialist CPUs

Given the importance of cosine transform in image coding and Dr. Cham's contribution to a much improved algorithm, it becomes a logical and natural step to study how computer hardware can facilitate and speed up ICTs. The objective is to design Application Specific Integrated Circuits (ASIC) that can perform ICT calculations very fast. In this task, Dr. Cham teamed up with Dr. C.S. Choy, a colleague in the Department of Electronic Engineering. They have now developed and fabricated an ASIC chip which can compute nearly a million ICTs every second. They have also designed and fabricated a data sequencer chip which is to be used with the ICT chip to transform the pixels of a TV picture twice _ once in the horizontal direction and once in the vertical direction. If one has a factor of 4 compression in each direction, the overall result will be a factor of 16. This is called a two-dimensional transform, and is used in international standards such as H.261, JPEG, MPEG1 and MPEG2. Most recently, Dr. Choy and Dr. Cham have designed a single chip that integrates the ICT and data sequencer functions, doing the two-dimensional transform in one step. New design techniques and faster chips are the planetary photos, better TV pictures, and cheaper video phones.