Advanced
Color Image Compression based on Inverse Colorization with Meanshift Subdivision Calculation
Color Image Compression based on Inverse Colorization with Meanshift Subdivision Calculation
Journal of Broadcast Engineering. 2013. Nov, 18(6): 935-938
Copyright © 2013, The Korean Society of Broadcast Engineers
  • Received : August 29, 2013
  • Accepted : October 29, 2013
  • Published : November 30, 2013
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
태경 유
석호 이
petrasuk@gmail.com

Abstract
본 레터논문에서는 컬러라이제이션(Colorization)기반 영상압축방법을 위해 평균이동기반의 영상분할법을 사용하여 컬러라이제이션 행렬을 분할하는 방법을 제안한다. 실험을 통해 제안한 방법을 사용할 경우 계산 속도는 대략 30배 이상 빨라지고, 기존의 역컬러라이제이션 기반의 압축방법에서 생기는 번짐(smearing) 현상도 많이 제거가 되는 것을 볼 수 있었다.
Keywords
Ⅰ. 서 론
최근에 컬러라이제이션(Colorization) [1] [2] 을 이용한 새로운 컬러영상 압축기법이 제안되었다 [3] - [5] . 이것은 컬러영상의 색도(色度)성분에 대한 압축방법이다. 즉, 휘도성분에 대해서는 기존의 JPEG 또는 JPEG2000의 1-채널 압축방법 등으로 압축을 수행하고, 색도성분에 대해서는 역(逆)컬러라이제이션 (inverse colorization)기법을 사용하여 압축을 수행한다. 역컬러라이제이션 기법이란 컬러영상으로부터 나중에 전체 컬러를 재구성할 수 있는 대표픽셀(Represen-tative Pixels : RP)들을 추출하는 방법을 말한다. 인코더(Encoder)에서 RP를 추출한 후 이를 디코더(Decoder)로 보내면 디코더에서는 휘도성분과 RP를 사용하여 전체 컬러를 재구성하게 된다. 본 레터논문에서는 컬러리제이션 계산시의 계산량을 줄이기 위해 평균이동분할(Meanshift Segmentation)방법 [6] 을 이용하는 알고리즘을 제안한다. 평균이동분할 방법을 사용하면 컬러라이제이션을 수행하는 행렬을 여러 개의 부(部)행렬들로 분할할 수 있게 되어 인코더에서 RP를 추출하는 계산 과정과 디코더에서 전체 컬러를 재구성하는 계산 과정을 여러 개의 작은 부행렬들에 대한 병렬계산으로 수행할 수 있어 전체적으로 인코딩과 디코딩 계산이 빨라지게 된다.
Ⅱ. 선행연구
- 1. 컬러라이제이션(Colorization)
컬러라이제이션이란 흑백영상에 색상을 입히는 기술로 수동으로 몇 개의 픽셀들에 대한 색상정보를 주면 자동으로 모든 픽셀들의 색상정보가 결정이 되는 기술을 말한다 [1] [2] . Levin은 최적화를 이용한 컬러라이제이션 방법을 제안하였다 [1] . 이는 다음과 같은 에너지항을 최소화함으로써 얻어진다:
PPT Slide
Lager Image
위의 에너지항은 Cb와 Cr성분에 대해서 각각 따로 존재한다. 여기서 Ω 은 색상정보가 주어진 영역을 말하며, r 은 현재 고려중인 픽셀을 의미하며, N ( r )은 r 의 주변에 있는 픽셀들을 말하며 s N ( r )에 속한 픽셀이다. x r 픽셀에 대한 함수이며 r 픽셀이 RP이면 x ( r )은 그 픽셀에서의 색상성분값(Cb 또는 Cr값)을 갖고, RP가 아니면 0을 값으로 갖는다. u 는 구하고자 하는 해가 된다.
이때 가중치인 wrs 은 휘도영상으로부터 계산되는데, 보통 wrs e −(y(r)−y(s))2/σ2 으로 놓는다. 여기서 y 는 휘도영상이고, σ 2 은 스케일링을 위해 들어간 양수값이다. 식 (1)은 행렬식으로 표현이 된다. 즉,
PPT Slide
Lager Image
로 표현할 수 있다. 여기서 A = I - W 인데, 여기서 A , I , W 는 모두 N × N 행렬이며, N 은 전체영상의 픽셀의 갯수를, I 는 단위행렬을 말하며, W 는 ( r , s )위치에 다음과 같이 정의되는 rs 값을 가진 행렬이다:
PPT Slide
Lager Image
식 (2)의 A 행렬은 역행렬이 존재한다는 것이 증명이 되었다 [1] . 그러므로 J ( u )를 최소화하는 u u = A - 1 x 에의해 구할 수 있다.
- 2. 역컬러라이제이션을 이용한 컬러 영상압축
역컬러라이제이션을 이용한 컬러영상압축은 인코더에서 컬러라이제이션의 반대 과정인 역컬러라이제이션을 수행하는 압축방법이다 [3] - [5] . 인코더는 휘도성분을 기존의 압축방법, 즉, JPEG이나 JPEG2000등으로 압축하고, 색상성분은 역컬러라이제이션을 수행하여 RP를 추출한다. 보통 RP의 갯수는 매우 적기 때문에 압축의 효과가 나타난다. 그러나 RP추출법은 최종의 RP집합이 나올 때까지 반복해서 행렬 A 의 역행렬을 구해야 하는데 A 가 크기 때문에 계산량이 많이 요구된다는데 문제가 있다. 또 행렬 A 의 구성을 잘못하게 되면 디코더에서 색상값을 재구성할 때 색이 섞이는 번짐현상이 발생한다. 그러므로 본 레터논문에서는 평균이동기반의 영상분할을 사용하여 A 행렬을 여러 개의 작은 부행렬들로 분할하여 계산하는 방법을 제안한다.
Ⅲ. 제안하는 방법
평균이동기반 영상분할을 사용하여 전체 영상의 영역 S S = S 1 S 2 ⋃ … ⋃ S m … ⋃ S M 으로 분할할 수 있게 된다. 제안한 방법에서는 이렇게 영상의 영역을 분할시킨 후에 각 분할된 영역에 대한 컬러라이제이션 부행렬을 구성하여 색상정보를 얻는 방법을 취한다. 즉, 분할된 영역 Sm 내에 속한 RP집합을 Ω m 이라 할 때, 즉, Ω m Sm 일 때, 각 분할된 영역 Sm 에 대해 다음의 에너지항들, 즉 J 1 ( u ), J 2 ( u ), .... JM ( u )들을 최소화시킨다:
PPT Slide
Lager Image
PPT Slide
Lager Image
이다. 위의 에너지항들을 최소화하여 얻게 되는 색상정보 u ( r ) ( r Ωm , m = 1,2,… M )가 원래영상의 색상정보를 잘 재현한 색상정보가 되게 하려면 Ω m 의 RP들이 Sm 내에 있는 픽셀들에 대해서만 영향을 미치고, 그외의 다른 영역내의 픽셀들에 대해서는 영향을 미치지 않아야 한다. 그런데 평균이동기반의 분할에 의해 얻어지는 Sm 영역들은 색상기반의 분할법이면서 색상간의 경계선에서 확실하게 구분하면서 영역을 분할하기 때문에 이런 조건을 잘 만족한다.
식 (4)도 행렬식들로 표현할 수 있다. 즉, um Sm xm Rm 일때 xm = Amum ( m = 1.. M )이 성립한다. 즉, 평균이동기반의 영역분할에 의해 분할된 영역의 갯수만큼의 행렬식들로 표현이 된다. 여기서 부행렬 Am 들은 식 (4)의 행렬 A 와 같은 방법으로 구성이 되는데, Sm 내에 있는 픽셀들과 Ω m 의 RP들만 가지고 구성된다는 점이 다르다. 행렬 A 과 부행렬 Am 들의 관계는 그림 2 에 나타나있다. 행렬 Am A 의 원소들 중 Sm 영역내에 있는 픽셀들의 색상값과 RP들간의 관계를 나타내는 원소들로만 구성이 된다.
PPT Slide
Lager Image
컬러라이제이션 행렬의 분할 Fig. 2. Dividing the colorization matrix
A 행렬의 원소들 중 다른 영역에 있는 RP가 끼치는 영향을 나타내는 원소 ( 그림 2 A 행렬의 원소들 중 회색으로 표시된 부분)들은 분할되는 과정에서 제외가 되어 번짐현상이 제거되어 색상의 재구성 성능이 좋아진다.
그림 3 은 제안한 방법을 컬러라이제이션에 사용한 전체 시스템도를 나타내고 있다.
PPT Slide
Lager Image
전체 시스템도 Fig. 3. Overall system diagram
Ⅳ. 실험 결과
본 실험에서는 RP추출방법으로는 단순 랜덤 RP추출, 논문 [3] - [5] 의 방법을 각각 사용하고, 컬러라이제이션 방법으로는 Levin의 방법과 제안한 분할계산법을 사용한 결과를 비교하였다. 컬러라이제이션의 방법으로 제안한 분할계산법을 사용할 경우 RP추출방법으로 어떤 방법을 사용하더라도 속도와 성능이 향상이 된다. 논문 [5] 도 평균이동방법을 사용하고 있으나 RP를 추출하는 방법으로 사용하고 있다는 점에서 본 레터논문과 내용이 다르다. 그림 4 는 각각의 방법에 대한 영상결과를 보여주고 있고, 표 1 은 SSIM과 PSNR의 값을 비교하고 있다. 4:1:1포맷을 적용할 때 원색상 정보량은 128×128×2= 32768byte (128×128 에 Cb,Cr을 1 byte씩 할당)가 된다. 방법1의 경우 RP를 319개이므로 319×4= 1276 byte(319개의 RP에 대해 Cb,Cr값 1byte씩, x,y좌표 1byte씩 할당)되어 색상 압축률은 1276/32768=3.9%가 된다. JPEG은 QP=19일 때랑 (색상정보 1362byte) 비교하였다. 표 1 의 압축률은 전체컬러영상의 압축률이 아니라 색상정보만의 압축률을 나타내고 있다.
제안한 방법과 Levin의 방법의 실험결과 정리
PPT Slide
Lager Image
Table 1. Comparison results between the various methods
PPT Slide
Lager Image
결과비교 : 그림 (a)~(f)은 각각 표 1의 방법 1~6의 결과 Fig. 4. Experimental Comparison
제안한 방법을 사용할 경우 번짐 현상이 적어지고 속도가 개선이 되는 것을 확인할 수 있다. 계산량의 감소는 다음과 같다. 행의 갯수가 N 인 행렬의 역행렬의 계산량(덧셈과 곱셈의 수)은 가우스 소거법을 사용할 경우 대략
PPT Slide
Lager Image
이 된다. 그러므로 만약 N 개의 픽셀 갯수를 가진 영상을 같은 수의 픽셀을 가진 M 개의 영역을 분할하였다고 가정하면 계산량은
PPT Slide
Lager Image
이 된다. 실제로 실험을 통해 알고리즘을 돌려본 결과 계산 속도는 약 30배 빨라졌다.
References
Levin A. , Lischinski D. , Weiss Y. 2004 “Colorization using Optimization,” ACM Transactions on Graphics 23 689 - 694    DOI : 10.1145/1015706.1015780
Yatziv L. , Sapiro G. 2006 “Fast image and video colorization using chrominance blending,” IEEE Trans. Image Processing 15 (5) 1120 - 1129    DOI : 10.1109/TIP.2005.864231
Cheng L. , Vishwanathan S.V.N. 2007 “Learning to Compress Images and Videos,” Proc. ICML 227 161 - 168
He X. , Ji M. , Bao H. 2009 “A Unified Active and Semisupervised Learning Framework for Image Compression IEEE CVPR 65 - 72
Ryu Taekyung , Lee Byung Gook , Lee Suk-Ho “Image Compression System using Colorization and Meanshift Clustering Methods,” to appear in Proc. CUTE 2013 Danang Dec.
Comaniciu D. , Meer P. 2002 “Mean Shift : A Robust Approach toward Feature Space Analysis,” IEEE Trans. PAMI 24 603 - 619    DOI : 10.1109/34.1000236