Vector quantization (VQ) is an attractive image compression technique. VQ utilizes the high correlation between neighboring pixels in a block, but disregards the high correlation between the adjacent blocks. Unlike VQ, side-match VQ (SMVQ) exploits codeword information of two encoded adjacent blocks, the upper and left blocks, to encode the current input vector. However, SMVQ is a fixed bit rate compression technique and doesn't make full use of the edge characteristics to predict the input vector. Classified side-match vector quantization (CSMVQ) is an effective image compression technique with low bit rate and relatively high reconstruction quality. It exploits a block classifier to decide which class the input vector belongs to using the variances of neighboring blocks' codewords. As an alternative, this paper proposes three algorithms using gradient values of neighboring blocks' codewords to predict the input block. The first one employs a basic gradient-based classifier that is similar to CSMVQ. To achieve lower bit rates, the second one exploits a refined two-level classifier structure. To reduce the encoding time further, the last one employs a more efficient classifier, in which adaptive class codebooks are defined within a gradient-ordered master codebook according to various prediction results. Experimental results prove the effectiveness of the proposed algorithms.