In this paper we present an algorithm for image compression which involves adaptively segmenting a block of residuals resulting from pirediction, while encoding them using hierarchical table lookup vector quantization. An optimum decomposition of the block allows an image to be adaptively quantized depending on the statistics of the residual block being encoded. This is useful since most images are nonstationary and have some regions with high detail and some with little. With an optimum decomposition, we can adaptively allocate bits by varying the block size to be quantized. Predictive vector quantization (PVQ) allows us to take advantage of the correlation between adjacent blocks of pixels being encoded by providing memory. The quadtree structure is used to represent the segmentation information and is sent as side information. To reduce encoding complexity, we use hierarchical table lookups so no arithmetic computations have to be performed to find the minimum distortion codeword. To further improve performance, we use a variable rate code to decrease the rate. Also, to improve the subjective quality of the image, we use subjective distortion measures.