k-d Tree-Segmented Block Truncation Coding for Image Compression

• Main Authors: Fernandez, Proceso L, Jr, Daga, Ryan Rey M
• Format: text
• Published: Archīum Ateneo 2016
• Subjects: Computer Sciences; Theory and Algorithms
• Online Access: https://archium.ateneo.edu/discs-faculty-pubs/87; https://archium.ateneo.edu/cgi/viewcontent.cgi?article=1086&context=discs-faculty-pubs
• Institution: Ateneo De Manila University

Block truncation coding (BTC) is a class of image compression algorithms whose main technique is the partitioning of an image into pixel blocks that are then each encoded using a representative set of pixel values. It is commonly used because of its simplicity and low computational complexity. The Quadtree-segmented BTC (QTS-BTC), which utilizes a dynamic hierarchical segmentation technique, is among the most efficient in the BTC class. In this study, we propose a new BTC variant that introduces two ideas: (1) the use of a k-d tree for segmentation and (2) the use of a Mean Squared Error (MSE) threshold for dynamically determining the granularity of the blocks. We refer to this new BTC variant as the k-d Tree Segmented BTC (KTS-BTC), and we test this against some of the existing BTC variants by running the algorithms on a standard image compression dataset. The results show that the proposed variant yields low bit rates of the compressed images, even outperforming the state-of-the-art QTS-BTC, without a significant reduction in image quality as measured using the Peak Signal-to-Noise Ratio (PSNR). The utilization of k-d tree for image segmentation is further shown to have more impact than that of employing the MSE thresholding scheme as a block activity classifier.