Shape-based prediction for BTPC

BTPC 2 improves the closest-opposite-pair prediction strategy by adjusting its choice of predictor pels based on local image surface shape.

An extensive set of experiments was conducted to compare closest-opposite-pair prediction with other possible predictors on the basis of image surface shape. First the possible orderings of pels around the four-point prediction square were enumerated. There are fourteen of these, corresponding to fourteen surface shapes. Next, over a range of test images, prediction performance per shape was measured for a variety of predictors. The table below summarizes the results qualitatively. The comments column explains the implications of a particular local shape and summarizes the relative performance of the closest-opposite pair predictor.

The four values a, b, c, d are ordered as a < b < c < d.

Num Name Surround Closest-opp-pair Comment
square prediction

0 Flat a a a Probably graphics.
a a Good prediction.

1 High a a a Probably graphics.
point a b Usually good pred.

2 Line a b a or b Probably graphics.
b a Sending flag bit
to select predictor
may be worthwhile.

3 Aligned a a (a+b)/2 Probably graphics.
edge b b Could use previous
pel in current band
to choose a or b.

4 Low a b b Probably graphics.
b b Usually good pred.

5 Twisted a a (a+b)/2 Usually good pred.
edge b c

6 Valley a b a (a+b)/2 often
c a better.

7 Edge a b b Good prediction.
b c

8 Doubly a b (a+b)/2 or (b+c)/2 b often better.
twisted c b
edge

9 Twisted a b (b+c)/2 Usually good pred.
edge c c

10 Ridge a c c (b+c)/2 often
c b better.

11 Edge a b (b+c)/2 Most common on
c d photos. Good pred.

12 Doubly a b (a+c)/2 or (b+d)/2 Fairly common on
twisted d c photos. Sometimes
edge (b+c)/2 is better.

13 Line a c (a+b)/2 or (c+d)/2 Fairly good, but
d b choice of pred on
basis of closest
opposite pair is
unreliable.

The first step in exploiting local shape, reported in [2], was for case 3 above (aligned edge). Consider a wider region around the current pel X. In the diagram below, A, B, C, D are X's four neighbors, P, Q, R, S are other nearby pels from earlier levels and U and V are earlier pels from the same level.

P Q

R A B

V X

S C D

At an aligned edge, either A = B and C = D or A = C and B = D. X is likely to be one or the other of the two values taken by the surround pels, not their average. To exploit information from the current band, a new ten-point predictor is therefore defined:

If A equals B and C equals D

	if A equals R and C equals S

		then prediction = V

	else

		prediction = (A+B+C+D)/4

else if A equals C and B equals D

	if A equals P and B equals Q

		then prediction = U

	else

		prediction = (A+B+C+D)/4

else

	prediction = average of closest opposite pair, as before.

In experiments, this predictor performed the same as the four-point predictor on photographic images, and far better on graphics.

Subsequent improvement to the predictor addressed the problems of shapes 2, 6, 10, 13, all of which are lines of some kind. As hinted in the comments for shape 2, the approach was to encode a predictor-selection bit which signals which of the two possible predictors is better. This is not used in all cases: if the range of values is small (less than two quantization levels), then the four-point bilinear average is used instead. The range threshold was determined empirically, and the use of the bilinear average rather than a closest-opposite-point average was for computational efficiency reasons - in practice the performance is indistinguishable for such shapes.

Finally, the doubly twisted edges (8, 12) turn out to be more effectively predicted with the middle-two-values approach - i.e. using b for 8 and (b+c)/2 for 12. Since shape interpretation must be implemented for the two improvements discussed above, there is little overhead in detecting shapes 8 and 12 as well, and using the appropriate predictor.

Next (Quantization) | Previous (BTPC 1 Prediction) | Top (BTPC)