Binary image pyramids

The binary image pyramid, used in BTPC, has previously been reported in two guises: one as a subband decomposition for lossy coding [8], and the other as an ordering of predictions for lossless coding [9-12]. In subband decomposition terms, the binary pyramid uses filtering followed by downsampling to yield two channels, L and H, each with half the number of points of the original. The downsampling is done by removing every even pel on every odd-numbered row and every odd pel on every even-numbered row. The result is a square lattice oriented at 45š to the original pel grid, with spacing of ˆ2 between points. The lowpass channel is then further filtered and subsampled, each iteration rotating the sampling lattice. With an eight level pyramid, the channels L8, H8, H7, H6, H5, H4, H3, H2, H1 are transmitted.

When the binary pyramid is used for predictive coding, the L channels are subsamplings of the original image without prefiltering, and the H channels are the differences between the true values of the intervening pels, and the predicted values based on neighboring L pels. To illustrate the process, consider the decoding of the last four levels of the pyramid in the block of pels shown in the diagram below. 

        L4    H1    H3    H1    L4


        H1    H2    H1    H2    H1


        H3    H1    H4    H1    H3


        H1    H2    H1    H2    H1


        L4    H1    H3    H1    L4

The pels labeled L4 have already been recovered from earlier stages. The decoder makes a prediction for the value of the pel at the center of the L4 square using the four surrounding L4 pels (and possibly more distant L4 pels). It receives the value for H4, which is the prediction error for the pel at the center of the L4 square. This value is added to the prediction to recover the value at that location. Following transmission of the entire H4 level, all the L4 and H4 pels become the predictors for the next band -- they may be relabeled L3. The H3's are recovered from their four surrounding L3's. In the diagram above, the H3's are on the edges of the block; their predictions would involve L3's from adjacent blocks too. When the H3's have been recovered, they and the L3's become L2's, and the process continues to recover the H2's and, finally, the H1's.

The same four levels of the binary pyramid are shown for a picture here .

Because the predictive binary pyramid is not a true frequency-domain subband representation (the L bands are not lowpass, but subsampled versions of the original), this documentation uses the term "subsampled band" for the L's and "difference band" for the H's. To avoid confusion with Hn being a "higher" band than Hn+1, it uses terms of sampling granularity. Thus H1 is the finest difference band, because it contains most points, and H8 is the coarsest difference band (in an 8-level pyramid). L8, which is the only L band transmitted (the others are progressively recovered from L8 and the H bands), is the coarsest subsampled band.

Next (Binary trees) | Previous (Image pyramids) | Top (BTPC)