As in conventional predictive coding, the design goal of the binary tree predictor is to minimize prediction error variance. Every new pel to be predicted is at the center of a square of four equidistant pels from earlier levels or bands. The diagram below illustrates the case where X is in the current level and is surrounded by A, B, C and D from earlier levels.
A B
X
C D
There are three natural candidates as estimators for the value of X using
A, B, C and D: the two linear predictionsAssuming that only the four closest points are going to be used, which of these is best?
The four pels that surround the one to be predicted may come from a relatively homogeneous region of the image, they may surround a single discontinuity such as an edge or a line, or they may come from three or four separate regions. In the latter case, it is hard to argue for any of the three predictors -- perhaps only one or even none of A, B, C and D come from the same region as X. However, this situation is relatively infrequent. In the other cases, based on an assumption about the surface gradient, it is possible to decide on a preferred predictor.
In most areas of the image, including along most edges, the gradient
changes direction slowly. Assuming that within an ABCD square, the
gradient direction (but not its magnitude) is constant, one of the two
diagonals AC, BD is closer to the gradient direction than the other.
Consider, for example, the case of a luminance edge:
The edge is at an arbitrary orientation to the pel grid, and in this case
the diagonal AC is closer to the gradient direction, so BD is in the
direction of lesser sur face slope. If the central point and its four
neighbors are projected onto the plane defined by the gradient, then they
have the arrangement shown on the right of the above figure.
The opposite pels in the direction of least surface slope (in this case B and D) are always closest to the central point in this projection. As long as the ABCD square straddles only a single edge or line, the two opposite pels closest to X in this projection are also always closest in value to X. Furthermore, when there is no second derivative sign change in the ABCD square, the average of the two closest opposite pels is sure to be a better linear estimate of the value at X than the average of the other two pels (and therefore of the 4-pel bilinear average). At a second derivative sign change, the shape of the edge between the surround pels in their projection onto the gradient determines the best linear average; in most cases, the foot of the edge will be blurred in the same way as the shoulder of the edge, and the closest-opposite-pels average will be at least as good as any other average.
How can the pair of opposite pels closest to X in the gradient-direction projection be identified? If the gradient magnitude is of the same sign throughout the ABCD square, that is, if the square is on a smoothly-shaded surface or straddling an edge, then the two opposite pels closest to X on the line of the gradient are closer in value to each other than are the pels of the other diagonal. Furthermore, these two pels have the middle two values of the four predictors. This is the case in the above figures. Equivalently, the highest and lowest values in the prediction square are at tained at opposite corners, and thus the other two pels should be used to form the prediction aver age.
If the ABCD square straddles a line, then the two pels closest to X on
the gradient direction projec tion, although still closest to X in value,
are not necessarily closer in value to each other than the pels of the
other diagonal. Here, for example, is a contrary case:
However, if the second derivative does not change sign within the
predictor square, then the two pels closest to X are sure to be at least
as close to each other as the other pair. The situation of straddling a
line can be de tected because the highest and lowest values are attained
by adjacent pels in the predictor square.
To summarize, if the four surround pels come from a smoothly shaded area of the image or strad dle a single edge, assuming the direction of the gradient changes very little over the surround square, the pair of opposite corner pels that are closest in value to each other are the pair closest to the center point in a projection onto the gradient, and their average is the best estimate of the value at the center. If the four surround pels straddle a line, the best estimate may still be the average of the opposite-corner pair closest in value to each other. However, the likelihood that the best estimate is this pair rather than the other depends on the local cross-section of the line.
There are therefore three possible strategies for prediction, corresponding to the three alternative else clauses below:
If the highest and lowest pel values are opposite each other in the
prediction square
Use the average of the other two opposite pel values, i.e. the middle
two of the four values.
Else
Alternative 1: Take the bilinear average of the four surround pels.
Alternative 2: Use the average of the two opposite pels closest in
value to each other.
Alternative 3: Use the average of the middle two of the four pel values,
irrespective of their positions in the pel square.
For the edge figure above, the if condition is true, and the prediction (B+D)/2 is formed. For the ridge figure, the if condition is not true, so alternative 1 would give the prediction (A+B+C+D)/4, alternative 2 would give the prediction (A+C)/2 and alternative 3 would give the prediction (A+B)/2.
Alternative 1 will be the best if, when the predictor square straddles a line, it also straddles a second-derivative sign change. In this case, neither linear predictor can be shown to be appropriate, so the reasonable approach is to take their average, yielding the bilinear predictor. Alternative 2 will be the best if, in the majority of cases when the predictor square straddles a line, there either is no second-derivative sign change, or if there is, the best predictor pair is still the closest pair. Alternative 3 will be the best if detection of adjacent highest and lowest values is more due to one of those values being noisy, than because of local image surface shape.
Alternatives 2 and 3 have the advantage that they can be implemented without doing the if condition test at all. The predictor can be designed as:
Alternative 2: Always use the average of the two opposite pels closest
in value.
Alternative 3: Always use the average of the middle two of the four pel
values.
These two cases also have an advantage for graphical images. If a limited palette of values is locally in use, then on edges there will be points where three of the predictor pels have the same value. In this case, the smallest value is guaranteed to be adjacent to the highest value, so for alternative 1 the (A+B+C+D)/4 prediction would be formed. For alternatives 2 and 3, the prediction will equal the value that appears three times. This is much more likely to yield 0 prediction error.
The three alternatives were compared with use of the bilinear average everywhere for a variety of test images. In the 32-36dB region, bilinear prediction everywhere is clearly worse than the three alternatives that use linear prediction. The choice between the alternatives is less clear cut, and varies from image to image. On average, alternative 2 emerges as slightly better than either of the others over the image set tested. This contrasts with a result of Howard and Vitter [12] who did empirical testing of a large number of predictors for lossless binary pyramid coding. They found that using the two intermediate values (alternative 3 above) gave the best compression for all but one of their test images. A possible reason for the difference is that flat areas in images often contain noise; in lossless coding this is not "quantized out", and so the advantage of alternative 3 for noise removal overtakes alternative 2's local surface shape advantage.
The shape-based prediction used in BTPC 2 uses a combination of the three alternatives based on local surface shape
. Next (Shape-based prediction) | Previous (Binary trees) | Top (BTPC)