Multi-Mode Image Compression for Frame Memory Reduction

Abstract

In modern TV sets such as LCD TVs and OLED TVs, techniques that require a frame memory suffer from increasing memory requirements because of the steady increase in the resolution of modern TVs. Thus, reducing the frame data size is considered necessary to achieve a sufficient decrease in the memory requirements. As a result, image compression algorithms are employed to achieve the required data reduction. The employed image compression algorithms are required to compress the frame data below a given target size because the whole frame data must be stored within a limited memory. Block truncation coding (BTC) algorithms are good candidates for that purpose because of their fixed encoded size. BTC algorithms divide the given image into non-overlapping blocks and perform a two-level quantization on each block. The encoded size is identical to all blocks and is determined by the block size. However, BTC algorithms have some critical drawbacks caused by the two-level quantization. For example, the preservation of gradual edges is low because they cannot be represented by only two levels. Similarly, the image quality degrades rapidly as the block size increases because two levels will be insufficient to represent the contents of large blocks. To overcome these drawbacks, multimode algorithms have been introduced. The multimode algorithms employ multiple encoding modes that differ in the number of quantization levels. Generally, the encoded size increases with the increase of the number of quantization levels. Thus, an optimum selection of encoding modes exists that minimizes the encoding error whereas the accumulated size of the compressed blocks does not exceed the target size. Unfortunately, the mode selection of the existing multimode algorithms is not optimal. To solve the above problem, I propose a multimode image compression algorithm that selects the encoding modes near-optimally. For that purpose, the encoding mode selection of a multimode image compression algorithm is first formulated as a multiple-choice knapsack problem (MCKP). The proposed multimode image compression algorithm takes advantage of the MCKP-formulated mode selection problem. Because MCKP is NP-hard, the proposed algorithm solves the linear relaxation of MCKP (LMCKP) to determine the encoding mode of each block. In addition, a memory-efficient implementation of the LMCKP-based mode selection algorithm is proposed. To emphasize the effect of the LMCKP-based mode selection, the proposed multimode image compression algorithm adopts encoding modes from conventional multimode image compression algorithms. In experiments using the Kodak test image set, the proposed algorithm outperformed benchmark algorithms by 2.4-7.7 dB in the average peak signal-to-noise ratio when the target compression ratio is 1/6.

LCD TV나 OLED TV와 같은 평판 디스플레이 TV에 적용되는 각종 기술 중에서 프레임 메모리의 사용이 필요한 기술들은 TV 해상도의 증가에 따라 메모리 크기 및 데이터 전송폭이 증가하는 문제에 직면하고 있다. 이러한 메모리 요구량의 증가를 완화시키기 위해서는 저장해야 하는 프레임 데이터의 크기를 줄일 필요가 있다. 이처럼 요구되는 프레임 데이터의 크기를 저감시키기 위해서 영상 압축이 적극적으로 사용 된다. 이 때, 압축된 프레임 데이터가 프레임 메모리에 모두 저장되어야 하기 때문에 프레임 메모리를 저감시키기 위해서 적용되는 영상 압축 알고리즘들은 프레임 데이터가 주어진 목표 크기 이하로 압축되는 것을 보장할 수 있어야 한다. Block truncation coding (BTC) 기반의 알고리즘들은 주어진 영상을 고정된 크기로 압축하기 때문에 프레임 메모리 저감을 위해서 사용하기에 적합한 특성을 가진다. 실제로 LCD overdrive 기술에서는 BTC 기반의 영상 압축 알고리즘을 많이 사용하였다. BTC 계열의 알고리즘들은 영상을 여러 개의 블록으로 나눈 후에 각 블록을 2개 값으로 양자화해서 표현하며, 압축된 크기는 사용하는 블록 크기에 의해서 결정된다. 그러나 BTC 알고리즘은 블록 내의 모든 픽셀값을 두 개의 대표값으로 표현하기 때문에 블록의 정보를 표현하는데 한계를 가진다. 예를 들면, 단계적으로 변하는 경계선이나 크기가 큰 블록을 사용할 때는 표현하지 못하는 정보가 많아지게 되면서 전체적인 화질이 떨어지게 된다. 이러한 BTC 알고리즘의 문제점을 극복하기 위해서 다중 모드 영상 압축 알고리즘들이 다수 개발되었다. 이들 다중 모드 영상 압축 알고리즘들은 양자화 레벨의 수가 다른 여러 압축 모드를 가지며, 일반적으로 압축된 크기는 양자화 레벨의 수가 많아지면 증가하게 된다. 따라서, 압축에 의한 데이터 손실을 최소화하면서 압축된 블록들의 크기 총합이 목표 크기 이하가 되도록 하는 최적의 압축 모드 할당이 존재한다. 그러나 기존의 다중 모드 영상 압축 알고리즘에서는 압축 모드 선택이 최적화되지 않아서 추가적인 개선이 가능하다. 최적화되지 않은 압축 모드 사용에 의해서 제한되는 효과를 극대화하기 위해서 본 논문에서는 최적의 압축 모드를 선택하는 다중 모드 영상 압축 알고리즘을 제안하였다. 이를 위해서, 압축 모드 선택을 최적화 문제 중 하나인 multiple choice knapsack problem (MCKP)로 변환한 후, MCKP기반으로 압축 모드를 선택하는 다중 모드 영상 압축 알고리즘을 제안하였다. 제안한 알고리즘에서는 MCKP기반의 압축 모드 선택을 효율적으로 해결하기 위해서 MCKP를 제약조건을 linear relaxation한 MCKP (LMCKP)로 변환해서 풀었다. 그리고 제안하는 LMCKP 기반의 압축 모드 선택을 효과적으로 구현할 수 있는 방법도 함께 제안하였다. 제안하는 구현 방식에서는 LMCKP에서 고려하는 블록의 집합을 여러 개의 부분 집합으로 나눈 후에 각 부분 집합에 대해서 LMCKP 기반으로 압축 모드를 일차적으로 결정하게 된다. 일차적으로 결정한 각 부분 집합의 압축 모드는 보정 과정을 통해서 전체 집합의 압축 모드로 보정된다. 제안하는 알고리즘에서는 압축 모드 선택에 따른 성능 변화를 강조하기 위해서 기존의 방식들과 유사한 압축 모드를 사용하였다. 목표 압축률을 1/6으로 설정해서 실험한 결과에서 제안하는 알고리즘이 벤치마크 알고리즘들보다 평균 PSNR이 2.4~7.7 dB 높게 나오는 것을 확인 할 수 있었다.