A new variable block size segmentation for image compression is proposed. The decision whether or not the given image block is homogeneous is based on a model-fitting criterion. More specifically, calculating the maximum log-likelihoods for all predetermined block patterns with respect to the given image data, we apply a modified Akaike information criteria (AIC) to select a best match. Then we can classify a given image block into one of texture, monotone, and various edges according to the characteristics of the selected pattern. Having classified nonoverlapping small square blocks, we can cluster homogeneous blocks to have a variable block size segmentation. Since the gray-level distribution in the block (i.e., the maximum log-likelihood) is considered in the model-fitting criterion, the proposed algorithm can differentiate edges from textures. Moreover, edge blocks can be further classified as having vertical, horizontal, or diagonal edges. Also, since the contextual information among neighboring blocks is considered to eliminate isolated blocks and to connect broken edges, we can have larger homogeneous blocks to guarantee a more efficient coding.