Databases Reference
In-Depth Information
Notice that even with a block size of 8, the image is clearly recognizable as a person.
Therefore, if the user was looking for a house, they would probably skip over this image after
seeing the first approximation. If the user was looking for a picture of a person, they could
still make decisions based on the second approximation.
Finally, when an image is built line by line, the eye tends to follow the scan line. With the
progressive transmission approach, the user gets a more global view of the image very early
in the image formation process. Consider the images in Figure
7.4
. The images on the left are
the 8
2 approximations of the Sena image. On the right, we show howmuch
of the image we would see in the same amount of time if we used the standard line-by-line
raster scan order.
×
8
,
4
×
4, and 2
×
We would like the first approximations that we transmit to use as few bits as possible
yet be accurate enough to allow the user to make a decision to accept or reject the image
with a certain degree of confidence. As these approximations are lossy, many progressive
transmission schemes use well-known lossy compression schemes in the first pass.
The more popular lossy compression schemes, such as transform coding, tend to require
a significant amount of computation. As the decoders for most progressive transmission
schemes have to function on a wide variety of platforms, they are generally implemented in
software and need to be simple and fast. This requirement has led to the development of
a number of progressive transmission schemes that do not use lossy compression for their
initial approximations. Most of these schemes have a form similar to the one described in
Example 7.6.1, and they are generally referred to as
pyramid schemes
because of the manner
in which the approximations are generated and the image is reconstructed.
When we use the pyramid form, we still have a number of ways to generate the approxima-
tions. One of the problems with the simple approach described in Example 7.6.1 is that if the
pixel values vary a lot within a block, the “representative” value may not be very representa-
tive. To prevent this from happening, we could represent the block by some sort of an average
or composite value. For example, suppose we start out with a 512
×
512 image. We first
divide the image into 2
2 blocks and compute the integer value of the average of each block
[
93
,
94
]. The integer values of the averages would constitute the penultimate approximation.
The approximation to be transmitted prior to that can be obtained by taking the average of
2
×
2 averages and so on, as shown in Figure
7.5
.
Using the simple technique in Example 7.6.1, we ended up transmitting the same number
of values as the original number of pixels. However, when we use the mean of the pixels as
our approximation, after we have transmitted the mean values at each level, we still have to
transmit the actual pixel values. The reason is that when we take the integer part of the average,
we end up throwing away information that cannot be retrieved. To avoid this problem of data
expansion, we can transmit the sum of the values in the 2
×
2 block. Then we only need to
transmit three more values to recover the original four values. With this approach, although
we would be transmitting the same number of values as the number of pixels in the image,
we might still end up sending more bits because representing all possible values of the sum
would require transmitting 2 more bits than was required for the original value. For example,
if the pixels in the image can take on values between 0 and 255, which can be represented by
8 bits, their sum will take on values between 0 and 1024, which would require 10 bits. If we
×
