*종신회원, 안양대학교 디지털미디어공학과(교신저자)
**준회원, 안양대학교 정보통신공학과
접수일: 2015년 2월 9일, 수정완료일: 2015년 4월 29일 게재확정일: 수정완료일: 2015년 6월 12일
Received: 9 February, 2015 / Revised: 29 April, 2015 / Accepted: 12 June, 2015
*Corresponding Author: [email protected]
Dept. of Digital Media Engineering, Anyang Univ., Korea http://dx.doi.org/10.7236/JIIBC.2015.15.3.77
JIIBC 2015-3-11
패턴을 이용한 블록 절단 부호화 기반의 영상 압축
BTC-based Image Compression using Pattern
김천식*, 오재환**
Cheonshik Kim
*, Jae-Whan Oh
**요 약 블록절단 코딩 또는 BTC(Block Truncation Coding)는 회색 영상을 위한 손실 영상 압축 기술의 일종이다.
이 방법은 원본 영상을 여러 개의 블록으로 나누고 각 블록에 대해서 평균과 표준편차를 계산하여 각 블록에서의 회색 레벨의 수를 줄인다. BTC는 비디오 압축에 적합하도록 만들어졌다. BTC의 변형된 것으로 AMBTC (Absolute Moment Block Truncation Coding)가 있다. AMBTC는 BTC보다 계산이 간편하다. 본 논문에서는 압축 성능과 이미 지 해상도를 높이기 위해서 패턴을 활용한 BTC 기반의 이미지 압축방법을 제안하고자 한다. 이 방법은 여러 이미지의 BTC에 빈도수가 높은 패턴 36개와 64개를 추출하여 코드 북을 만든다. 이미지를 압축할 때 해당 블록과 패턴을 비교 해서 일치하는 패턴의 인덱스를 압축에 이용하는 방법이다. 제안한 방법을 실험하였고 36개의 패턴을 활용할 경우 1.37bpp의 압축 성능을 보였다. 본 논문에서 제안한 방법은 BTC 압축보다 높은 성능을 보였다. 제안한 방법의 성능은 표준 이미지를 이용하여 실험하였다.
Abstract Block Truncation Coding, or BTC, is a type of lossy image compression technique for grayscale images.
It divides the original images into blocks and then reduces the number of grey levels in each block to compute the mean and standard deviation. BTC has also been adapted to video compression. Another variation of BTC is Absolute Moment Block Truncation Coding. AMBTC is computationally simpler than BTC. In this paper, we proposed new image compression method based on BTC, which is applied patterns to improve compression rate and image quality. This method make two codebooks to extract 36 and 64 patterns from the highest frequency patterns in BTC. When you are compressing an image, you compare many block patterns to that of codebook and use to compress indexes of identical patterns. We experiment our proposed scheme with 36 patterns and the experimental results showed the compression rate of 1.37 bpp. In this paper, our proposed scheme showed higher compression rate rather than that of BTC. In experiment, we used standard images for the performance evaluation.
Key Words : BTC, AMBTC, compresstion, codebook, pattern
Ⅰ. 서 론
인터넷의 성능 개선에서 불구하고 네트워크에 전달되 는 데이터의 크기는 인터넷의 성능에 영향을 준다[1,2]. 예 를 들어서 큰 용량의 이미지를 네트워크를 통해서 전달
한다면 작은 크기의 이미지를 전달할 경우보다 많은 시 간이 요구된다[3]. 이미지 압축 기술은 네트워크를 통해 전달되거나 검색되는 비용을 감소시키는데 사용된다. 이 미지 압축의 기본적인 목적중의 하나는 데이터의 크기를 감소시키는데 있다. 이미지 압축의 두 가지 기술이 있다:
손실압축과 무 손실 압축. 손실 압축은 중요하지 않은 데 이터의 일부를 제거하여 압축 성능을 높이는 방법으로 압축된 데이터를 원본으로 복원이 불가능하다. 반면 무 손실 압축은 데이터를 압축하고 필요한 경우 데이터의 손실이 없이 원본을 복원할 수 있는 기술이다. 일반적으 로 손실 압축 기술에 의한 압축 성능이 무 손실 압축 성 능 보다 높다[3].
손실 압축 기술에 의해서 압축된 이미지의 대표적인 것은 JPEG[4]이고 무 손실에 의해서 압축된 이미지의 대 표적인 형태는 JPEG2000이다[5].
중복(重複, redundant) 정보는 손실 이미지 압축 방법 에서 압축(壓縮)과정에서 압축 알고리즘에 의해서 축소 되거나 제거된다. 손실 압축 방법 중 하나인 BTC [2,3, 6-9]
압축 방법은 비교적 단순하며 계산이 복잡하지 않기 때 문에 비교적 많이 사용되는 기술 중 하나이다. 압축된 이 미지는 원본 이미지의 근사치 값을 사용하기 때문에 인 간의 시각시스템으로는 원본이미지와 압축된 이미지를 쉽게 구분하기 어렵다. 다양한 형태의 BTC[2-15]가 더 높 은 압축 효율을 목적으로 제안되고 있다. 대표적인 방법 으로 중앙값 필터링 (median filtering), 벡터 양자화 (vector quantization), DCT(discrete cosine trans- form)[16], 보간법(interpolation)][9] 등이 있다. BTC 알고 리즘은 영상을 하위 블록으로 나누고, 평균, 표준편차 그 리고 비트맵정보를 전송하여, 보내진 영상과 재구성될 영상사이에 1차 및 2차 값이 같도록 재구성하는 원리에 의해서 수신측에서 이 변수들로서 영상을 재구성하는 방 법이다.
본 논문에서는 패턴코드 북을 이용하여 높은 수준의 압축 성능을 개선하고 이미지 훼손을 최대한 적개 하는 방법을 제안하고자 한다.
Ⅱ. 관련 연구
1. BTC (Block Truncation Coding)
본 절에서 BTC 방법에 대한 간단한 알고리즘을 설명 하고자 한다. 우선 이미지를 4×4 픽셀 블록으로 나눈다.
각 블록에 대해, 평균( )과 표준편차()를 계산한다. 수 식 (1)(2)에서 × 은 한 블록의 픽셀의 수이고 는 블록의 각 픽셀 값이다[2].
(1)
(2)
각 픽셀의 값이 평균보다 작은 경우 0-비트를 배정하 고 그렇지 않으면 1-비트를 배정해서 대치한다.
각 블록에 대해서 대표 값 와 를 수식 (3)과 (4)로 계산한다. 대표 값은 디코딩 과정에서 압축된 값을 원본 에 근사한 값을 만드는데 필요하다.
(3)
(4) 수식 (3)(4)에서 (=16)은 블록에서 픽셀의 합계이고
는 블록에서 1-비트의 개수이다. 기본 양자 알고리즘의 다양한 방법들이 있다. 압축하는 과정에서 기본 구성은 ( ,,B)이고, 이 구성에서 는 평균, 는 표준편차, B는 비트 플래인(plane)으로 그림 1과 같다.
그림 1. BTC 방법에 의한 1 블록 압축
Fig. 1. Compress 1 block based on BTC method
그림 1의 첫 번째 블록은 원본 이미지의 한 블록이다.
이 블록에 대해서 수식 (1)과 (2)를 적용하여 평균과 표 준편차를 각각 계산한다. 블록의 평균 값 7.94 보다 작은 픽셀들은 0으로 바꾸고 평균보다 큰 픽셀들은 1로 바꾼 다. 그 결과 그림 1의 두 번째 이미지가 이를 수행한 결과 이다. 이 블록에서 는 1의 개수를 의미한다. 그림 1의 세 번째 블록은 평균, 표준편차, 비트집합을 이용하여 원 본 영상의 근사 값을 복원한 형태를 보인 것이다.
2. AMBTC (absolute moment block truncation coding)
Lema와 Mitchell(1984)[12-14]이 제안한 AMBTC는 회
색과 컬러이미지를 위한 손실압축 알고리즘들 중 하나의 버전이다. BTC 알고리즘을 위한 처리시간은 다소 많은 시간이 소요된다. 따라서 시간이 중요한 문제가 되는 응 용에 대해서는 일반적으로 추천하지 않는다. AMBTC 역 시 BTC 방법과 유사하게 인코딩되는 회색영상을 중첩되 지 않게 (4×4) 혹은 (8×8) 형태로 분리한다. 분리된 블록 에 대해서 수식 (5)와 같이 평균을 계산한다.
×
(5)
수식 (5)에서 W와 H는 각각 블록의 폭과 넓이를 의미 하고 N은 블록내의 픽셀의 수이고 는 픽셀을 의미한 다. 회색영상에서 픽셀 하나는 8비트로 구성되지만 BTC 에서는 1비트 나타낸다. 그러므로 수식 (6)을 적용하여 픽셀의 형태를 이진 형태로 변환하는 과정이 요구된다.
≥ (6) 수식에서 는 BTC 변환 후의 픽셀들을 의미한다. 즉, 각 원본 이미지의 픽셀 가 보다 크다면 1을 에 배정 하고 그렇지 않으면 0을 배정한다. 블록에서 대표가 되는 픽셀 즉 평균보다 큰 값들 중 대표되는 픽셀과 평균보다 작은 값들의 대표가 되는 값을 계산한다.
≥
(7)
×
(8)
수식 (7)에서 는 한 블록의 픽셀의 개수를 의미한다.
따라서 는 평균보다 큰 값들의 평균을 의미한다. 수식 (8)의 는 평균보다 작은 값들의 평균을 의미한다. 즉 블 록에서 대표 값을 계산한 것이다. 수식 (9)는 AMBTC 방 법으로 압축된 데이터를 이용하여 원본 이미지에 근접한 형태의 회색이미지를 생성하는 과정이다.
(9)=1 이면 에 를 배정하고 =0이면 에 를 배 정하는 방법으로 회색이미지를 생성할 수 있다. 압축률 은 2이다.
3. 적응적 AMBTC
적응적 AMBTC는 AMBTC의 압축 성능을 픽셀 블록 의 형태에 적응적으로 데이터를 압축하는 방법이다. 예 를 들어 어떤 블록은 모두 같은 값의 픽셀들로 구성될 수 있다. 적어도 평균보다 큰 픽셀들로 이루어진 경우가 있 다면 이 경우 블록의 대표 값은 하나면 충분할 수 있는데 이와 같은 상황들을 찾아서 적합한 방법들을 찾아 압축 하는 방법이다. 적응적 인코딩방법은 다음과 같은 과정 으로 가능하다.
단계 1 : 이미지를 4×4 블록(16개 화소)으로 나눈다.
단계 2 : 해당 블록에 대해 평균값( )를 구한다.
단계 3 : 수식 (9)(10)(11)를 이용하여 와 값을 구한다.
(9)
(10)
(11)
수식 (9)(10)(11)에서 는 평균, 은 전체 화소의 수 이고 는 블록에서 1의 개수이다.
단계 4: 와 의 값에 따라서 3가지 모드로 구분하여 처리한다.
모드 A: 만일 ≤이면, 비트맵을 생략하고, 만 저장한다. 즉 변화가 적은 블록에 대해서 평균값만 을 저장한다.
모드 B: 만일 이고
≤ 이면 AMBTC와 동일하게 압축한다.
모드 C: 모드 A, B에 속하지 않으면, 4×4 블록을 2×2 블록으로 분할하여 각 2×2 블록에 대해서 AMBTC를 적 용한다.
Ⅲ. 제안방법
본 장에서는 패턴을 이용하여 AMBTC와 유사한 성능을 제공하는 방법을 제안하고자 한다.
1. 인코딩 과정
입력: 회색이미지 이미지 (G),
출력: 인코딩 이미지
단계 1: 회색 이미지를 × 크기의 블록 단위로 나 눈다.
단계 2: 순서대로 × 픽셀 블록을 읽어 에 값들 을 배정한다. 를 수식 (6)을 적용하여 를 계산 한 다. 예를 들어 그림 1의 원본 블록에서 는 7.94이고 7.94보다 큰 값은 1이고 나머지는 0이 된다. 그림에서 Bit-plane을 그림 2의 패턴 북에서 찾아서 인덱스를 기록한다. 그림 2에서 2번째 줄 두 번째 블록이 가장 유사한 블록이다. 이를 X와 Y인덱스로 표기할 경우 2 행2열에 있기 때문에 X(010),Y(010) -> 010010으로 나타낼 수 있다.
단계 3: 수식 (7)(8)을 적용해서 와 를 계산한다. 그 림 1에서 =2.7이고, =12이다.
단계 4: 다음의 수식과 같이 에 , , X, Y를 누적해 서 압축한다. 마지막 블록이 아니면 2단계부터 반복 적용한다. 마지막 블록이면 5단계로 이동한다.
단계 5: 압축된 변수 를 반환한다.
그림 2. 이미지 압축을 위한 36 패턴
Fig. 2. 36 pattern for image compression
2. 디코딩 과정
본 절에서 압축이미지로부터 원본이미지에 근사한 이 미지를 복원하는 과정을 설명한다.
입력: 압축 데이터(),
출력: 복원한 이미지 G'
단계 1: 압축 데이터 를 26비트씩 분리한다.
단계 2: 분리된 각 블록 (, , X, Y)을 읽는다. 예를 들어 인코딩과정에서 만들어진 블록을 다음과 같이 읽어 들인다. 즉, =(2.7, 12, 010, 010).
단계 3: 단계 2에서 구한 X, Y에 해당하는 블록을 그 림 2에서 찾는다. 수식 (12)와 같이 CODE는 그림 2의 집합을 의미하며 해당 블록의 (i,j)에 해당하는 값이 0 이면 값을, 1이면 의 값을 이미지에 배정한 다. 즉, 이미지 G의 I번째 블록의 (i,j) 픽셀에 값을 배 정한다. 마지막 블록에 도달하지 않았다면 단계 2로 이동하고 그렇지 않으면 단계 4로 이동한다.
(12) 단계 4: 알고리즘을 종료하고 G를 반환한다.그림 3. 이미지 압축을 위한 64 패턴
Fig. 3. 64 pattern for image compression
압축을 위해서는 그림 2의 패턴을 사용하고 이미지의 화질을 고려한다면 그림 3의 패턴을 사용하면 된다.
Ⅳ. 실험 및 결과
제안한 패턴을 이용한 BTC 기반의 이미지 압축방법을 평가하기 위해서 MATLAB 7.0을 사용하여 실험하였다.
실험에 사용한 회색 원본 이미지는 8개는 그림 4와 같다.
실험에서 중요한 2가지 요소는 압축 이미지의 압축률과 압축된 이미지를 디코딩 한 후의 이미지와 원본 이미지 와 비교를 통한 화질의 평가 성능이다. 이러한 평가 기준 은 BTC 기반의 이미지 압축 시스템의 성능을 평가하는 데 보편적으로 활용되고 있다. 본 논문에서는 이러한 평 가를 보다 객관적으로 증명하기 위해서 PSNR (Peak Signal to Noise Ratio)[1]을 사용한다.
×
(13)즉, 수식(13)에서 MSE는 원본 영상 I와 디코딩 후의 복원 영상 I'의 차이 값에 수식(14)를 적용한다.
′ (14)
여기서 M은 이미지의 폭이고 N은 높이를 의미한다.
블록 크기 2×2 3×3 4×4 5×5 8×8
MSE 7.69 23.56 35.54 46.44 72.36
bpp 5.00 2.79 2.00 1.66 1.25
표 1. 다양한 블록의 Lena 이미지를 이용한 압축 성능 비교.
Table 1. Compare compression performance with various block of Lena image
수식(13)의 평가의 결과 PSNR의 수치가 클수록 압축 영상이 원본 영상과 유사함을 나타내고, 반대의 경우 디 코딩 후의 복원 영상이 원본 영상과 차이가 커짐을 의미 한다.
그림 4. 블록 크기에 따른 압축 성능 비교.
Fig. 4. Compare performance based on block size
일반적으로 PSNR이 30dB 이상인 경우 복원영상의 잡음
(noise)을 사람의 시각 시스템으로 탐지하기 어렵다는 것 을 나타낸다.
(a) Lena (b) baboon
(c) pepper (d) babara
(e) airplane (f) goldhill
(g) elaine (h) boat
그림 5. 실험에 사용한 원본 이미지
Fig. 5. Original image for our experiment
대부분의 BTC 압축과 변형된 압축방법에서 4×4 크기 로 고정시킨다. 하지만 다양한 블록의 크기로 적용할 경 우 다음과 같은 결과를 얻을 수 있다 (표 1).
블록의 크기가 이미지의 화질과 압축 성능에 영향을 준다. 블록의 크기를 크게 하면 압축 성능을 높일 수 있 고 반면에 화질이 떨어지는 것을 볼 수 있다. 가장 작은
블록 크기인 4×4와 2×2이다. 2×2는 bpp가 가장 높고(그 림 4) 4×4의 경우 이미지 질이 가장 놓은 것으로 나타났 다. 표 2에서 BTC, AMBTC, 그리고 제안한 방법의 성능 을 비교한 것이다. BTC와 AMBTC는 모두 bpp가 2.00의 성능을 보이고 있다. BTC와 AMBTC의 평균 PSNR은 각각 26.1082와 26.5658의 성능을 보였다. 제안한 방법은 압축 성능이 1.37bpp로 BTC와 AMBTC보다 높다. 이와 같이 압축 성능을 위해서 그림 2의 36 패턴을 사용하였 다. 압축 성능을 높이고 싶은 경우 36패턴을 사용해서 압 축률을 높이고, 반면에 PSNR을 높이고 싶다면 다양한 패턴으로 구성된 64 패턴을 사용하여 성능을 개선할 수 있다.
이미지 BTC AMBTC 제안한 방법
PSNR bpp PSNR bpp PSNR bpp
Lena 28.3477 2.00 28.8053 2.00 27.9338 1.37 Baboon 21.2463 2.00 21.7039 2.00 20.8324 1.37 Pepper 28.6807 2.00 29.1383 2.00 28.2668 1.37 Babara 22.0478 2.00 22.5054 2.00 21.6339 1.37 Airplane 27.0483 2.00 27.5059 2.00 26.2565 1.37 Goldhill 27.2640 2.00 27.7216 2.00 26.4722 1.37 Elaine 27.8942 2.00 28.3518 2.00 27.1024 1.37 Boat 26.3367 2.00 26.7943 2.00 25.5449 1.37 평균 26.1082 2.00 26.5658 2.00 25.5053 1.37 표 2. BTC, AMBTC, 그리고 제안한 방법의 성능비교 Table 2. Compare performance among BTC, AMBTC, and proposed method
그림 6은 제안한 방법으로 실험한 결과의 이미지들을 보인 것이다. PSNR은 표 2의 내용과 같다. 즉, Lena의 PSNR은 27.9338이다. 비록 PSNR이 30dB 미만이지만 사 람의 시각시스템에 의한 원본 영상과 제안한 방법에 의 한 영상이 크게 차이가 없음을 알 수 있다.
Ⅴ. 결 론
본 논문에서 제안한 패턴을 이용한 BTC 기반의 영상 압축을 제안하였다. 인터넷의 발달로 많은 미디어의 데 이터를 인터넷을 이용하여 전달한다. 이 경우 많은 양의 데이터를 짧은 시간에 전달하기 위해서는 인터넷 자체의 성능이 우수해야하지만 아무리 인터넷이 초고속의 우수 한 성능을 가진 시스템일 지라도 데이터 자체가 클 경우 인터넷의 성능에 무리를 줄 수 있다. 이런 이유로 본 논
문에서는 회색의 정지 영상에 대해서 BTC 기반의 압축 방법을 제안하였다.
특히 본 논문에서는 발생빈도가 높은 패턴의 그룹을 모아 36패턴 그리고 64패턴을 각각 만들어서 실험하였다.
36패턴을 사용할 경우 bpp가 1.37로 기존의 방법인 BTC 방법 보다 월등이 높은 편이다. 64패턴을 사용할 경우 1.5bpp로 압축 성능은 다소 낮지만 이미지의 PSNR을 높 이고자 할 경우 사용할 수 있다.
그림 6. 제안한 방법에 의한 실험 결과 이미지
Fig. 6. Result image according to our proposed method
References
[1] C. Kim, "Data Hiding Based on BTC using EMD,"
The Journal of The Institute of Internet, Broadcasting and Communication (IIBC), vol.14, no.2, pp.11-16, 2014.
[2] Meftah M.Almrabet, Amer R. Zerek, Allaoua Chaoui and Ali A. Akash, "Image Compression using Block Truncation Coding," International Journal of Sciences and Techniques of Automatic control & computer engineering, vol.3, no.2, pp.1046-1053, 2009.
[3] Pasi Franti, Olli Nevalainen, Timo Kaukoranta,
"Compression of Digital Images by Block Truncation Coding: A Survey," The Computer Journal, vol.37, no.4, pp.308-332, 1994.
[4] W.B.Pennebaker and J.L.Mitchell, "JPEG Still Image Data Compression Standard," New York, Van Nosttrand Reinhold, ISBN:0442012721, 1992.
[5] M.Rabbani and R.Joshi, "An overview of the JPEG 2000 Still Image Compression Standard," Signal Processing and Image Communication, vol. 17, pp.
3-48, 2002.
[6] K.Somasundram and S.Vimala, "Efficient Block Truncation Coding," International Journal on Computer Science and Engineering, Vol. 02, No.
06, pp.2163-2166, 2010.
[7] G.Arce and N.C.Jr.Gallagher, "BTC Image Coding using Median Filter Roots," IEEE Transactions on Communication, vol. 31, no. 6, pp. 784-793, 1983.
[8] Yung-Gi Wu, "Block Truncation Image Bitplane Coding," SPIE, Optical Engineering, vol. 41, no. 10, pp. 2476-2478, 2002.
[9] Pasti Franti and Olli Nevalainen, "Block Truncation Coding with Entropy Coding," IEEE Transaction on Communications, vol.43, no.2, 1995.
[10] Lucas Hui, “An Adaptive Block Truncation Coding Algorithm for Image Compression," Acoustics, Speech, and Signal Processing (ICASSP-90), vol.4, pp.2233-2235, 1990.
[11] Y.V.Ramana Rao and C.Eswaran, "A new algorithm for BTC image bit plane coding," IEEE Transactions on Communications, vol.43, no.6, pp.2010-2011, 1995.
[12] Maximo D.Lema, O.Robert Mitchell, "Absolute Moment Block Truncation Coding and its Application to Color Images," IEEE Transactions on Communications, vol.32, no.10, pp.1148-1157, 1984.
[13] Madhu Shandilya and Rajesh Shandilya,
"Implementation of Absolute moment Block Truncation Coding Scheme Based on Mean Square Error Criterion," SDR 03 Technical
Conference and Product Exposition.
[14] K.Somasundaram and I.Kaspar Raj, "Low Computational Image Compression Scheme based on Absolute Moment Block Truncation Coding,"
World Academy of Science, Engineering and Technoloy, vol. 19, pp. 166-171, 2006.
[15] N.M.Nasrabadi and R.B.King, "Image Coding using Vector Quantization: A Review," IEEE Transactions on Communication, vol.36, no.8, pp.
957-971, 1998.
[16] B.H. Lee, "Technique for production and encoding of New dot-type Print Watermark Pattern,"
Journal of the Korea Academia Industrial cooperation Society, vol.10, no.5, pp.979-984, 2009.
저자 소개
김 천 식 (종신회원)
∙1997년 : 한국외국어대학교 컴퓨터 및 정보통신공학과 (공학석사)
∙2003년 : 한국외국어대학교 컴퓨터 및 정보통신공학과 (공학박사)
∙2010년 ～ 2012년 : 세종대학교 교수
∙2013년 ∼ 현재 : 안양대학교 교수
∙2007년 ∼ 2009년 : 대한전자공학회 컴퓨터소사이어티 멀티미디어 분과위원장
∙2012년 : UMAS 워크샵 프로그램 의장
∙2013년 : GPC 2013 프로그램 의장
∙2014년 : FutureTech 2014 프로그램 의장
∙2015년 : IoP2015 TPC 위원
∙2015년 : 3PGCIC 2015 세션 의장
∙2012년 ～ 현재 : TACT 영문 저널편집 위원
∙2015년 : 대한전자공학회 컴퓨터분과 협동부회장 <주관심분야 : 데이터베이스, 데이터마이닝, Steganography,
영상처리, e-Learning>
오 재 환 (준회원)
∙2010년 ～ 현재 : 안양대학교 정보통 신공학과 (학사과정)
<주관심분야 : 멀티미디어, 영상처리>
