Ⅰ. 서 론
현재 가장 널리 이용되고 있는 정지 영상 압축 방식인 JPEG(Joint Photo Graphic Expert Group)등과 같은 기존의 표준은 8*8 블록에 대한 DCT(Discrete Cosine Transform)를 기반으로 하고 있어 낮은 비트 율에서 블록의 경계가 두드러지는 블로킹 현상 (Block Effect)이 단점으로 지적되고 있다[1][2][3]. JPEG의 DCT 변환을 대신해서 웨이블렛 변환 영상 의 효율적인 부호화 방법 또한 연구가 진행되어 왔 고, JPEG2000등에서 사용되고 있다. 입력 영상을 고주파 통과 필터와 저주파 통과 필터를 사용하여 다중 해상도 영상을 표현한다. 영상분석이나 압축 등의 여러 분야에서 많은 이점을 가진다[3][4][5].
임베디드 제로트리 웨이블렛(EZW; Embedded Zerotree Wavelet)알고리즘은 웨이블렛 변환된 영상을 효과적으로 부호화 하는 알고리즘이다[6]. 이 기법은 연속 근사 양자화(Successive Approximation Quantization), 제로트리 구조(Zerotree-structure), 임베디드 부호화 (Embedded coding)와 같은 특성을 갖는 알고리즘으 로 단순하면서도 압축효율이 높은 효과적인 기법이 다. 임베디드 제로트리 웨이블렛 알고리즘을 수행 할 때에 4개의 부호를 사용하여 부호화를 하는데, 4가지 부호는 중요한 계수를 나타내는 P, N과 중요 계수의 위치정보를 나타내기 위해 사용되는 Z, T로 나눌 수 있다. 제로트리 부호화 과정에서 피라미드 형태로 된 계수 값들은 부모와 자식 간의 관계를 이룬다. 부모와 자식 간의 관계를 반복적으로 검사 해서 임계값을 기준으로 중요한 계수와 중요하지 않은 계수를 판별한다. Z부호는 현재 임계값에서는 중요하지 않은 계수이지만, 해당 계수의 하위 계층 의 자식노드에는 중요계수가 존재한다. 따라서 중 요한 계수의 검출을 위해서 항상 후손 계수를 부호 화 하는 과정이 따른다.
본 논문에서는 기존 임베디드 제로트리 웨이블 렛 알고리즘을 이용하여 주부호화 과정(dominant pass)에서 사용된 4가지 부호에 새롭게 4가지 부호 를 추가한 향상된 알고리즘을 제시한다. 즉, 기존 임베디드 제로트리 웨이블렛 알고리즘에 사용하는 4가지 부호 P = positive coefficient, N = Negative coefficient, Z = isolate Zero, T = Zerotree와 제안된 확장 임베디드 제로트리 웨이블렛 (EEZW : Extended Embedded Zerotree Wavelet)에 새로 추가된 T1 = Zerotree 1, T2 = Zerotree 2, Z1 = isolate zero 1, Z2 = isolate zero 2의 4가지 부호를 추가한다. T2 는 연속된 T 가 발생시 T 의 재 정의를 하여 압축 률을 높이는 새로운 알고리즘이다. 예를 들어 순열 이PNZT /PTTT /TZTT /TTTT /TPTT 라고 나 왔을 때 반복되는 부호에 대한 TT 를 T1 으로 TTT를 T2라고 대체할 수 있다. 제안된 확장 임베디드 제로트 리 알고리즘으로 주 부호화 과정을 통한 부호의 순 열은 PNZT /PT2/TZT2/T2/TPT1로 대체된다. 기 존 임베디드 제로트리 웨이블렛 알고리즘 보다 부 호를 나타내는 비트수가 2비트에서 3비트로 증가를 했지만 주 부호화 과정에서 반복되는 부호에 대한 데이터 수를 새로운 부호로 대체하여 데이터의 수 를 줄일 수 있다.
Ⅱ. 임베디드 제로트리 웨이블렛(EZW) 알고리즘
웨이블렛을 기반으로 한 영상압축의 가장 효율 적인 알고리즘의 하나인 임베디드 제로트리 웨이블렛 알고리즘(이하 EZW : Embedded Zerotree Wavelet)은 Shapiro가 제로트리(zerotree) 기법을 사용하여 효율 높은 압축 알고리즘을 제안 하였다. 이는 임계값 (threshold)을 설정하여 계수(coefficient)의 절대치가 주어진 임계치보다 작은 경우를 중요하지 않은 계 수 (insignificant coefficient)로, 반대의 경우를 중요 한 계수(significant coefficient)로 정의 하였다. 또한 중요하지 않은 계수로 구성된 공간트리를 제로트리 로 정의하였다. 이를 기반으로 제안된 알고리즘이 EZW이다[6][8].
1. 2차원 영상의 웨이블렛 변환
영상을 웨이블렛 변환하게 되면 <그림 1>과 같이 서로 다른 단계의 다중 해상도 부대역(Multi- resolution subband) 영상들로 나눌 수 있다. 영상 처리를 위한 2차원 웨이블렛 변환은 분석단에서 영상의 행을 따 라 두개의 대역을 분할하는 필터를 사용하여 다운 샘플링을 하며, 열 변환으로 이 과정을 반복한다. h[n]과 g [n]은 필터를 의미하며 합성 단에서는 분석 단의 반대 과정을 통해 x′[n]를 복원한다.
부대역 부호화(Subband coding)는 <그림 2>와 같이 영상을 필터에 통과시켜 영상의 집합으로 만드는 것을 말한다. 각각의 부 영상은 공간적 주파수의 제한된 구간을 포함하고 있으며 이들 각각의 영상 집합을 부대역(subband)이라고 부른다.
이산 웨이블렛 변환(DWT：Discrete Wavelet Transform) 은 필터 뱅크(Filter Bank) 개념으로 실행되는데 이 필터 뱅크는 원 영상을 <그림 3>과 같이 수평(HL: High Low), 수직(LH : Low High), 대각(HH :High High), 그리고 기본대역(LL : Low Low)의 부대역으 로 분해된다. 각각의 부대역은 원 영상의 1/4 크기 로 된다. 그리고 기본대역은 4개의 부대역으로 재 분해할 수 있다.
2. 제로트리 구조 및 자기상과 관계
EZW 기법에서는 압축효율을 높이기 위해서 앞 에서 말한 제로트리라 정의된 데이터 구조를 정의 하였다. 이것은 어떤 스케일의 웨이블렛 계수의 절 대 값이 임계 값 T보다 작으면, 그 계수를 중요도 가 낮은 계수라고 하고, 나머지 하위 스케일에서 같은 방향 같은 위치에 나타나는 웨이블렛 계수들 은 모두 임계값 T에 대하여 중요도가 낮다고 가정 을 한다[6].
<그림 3>은 영상에 대한 이산 웨이블렛 변한을 이용한 다중 해상도 분해를 보여준다. HH3 대역에 있는 계수 ‘1’은 직선 형태로 갖는 하위 대역의 HH2에 4개의 후손계수를 가지고, HH2의 하위 대 역의 HH1에서는 16개의 후손 계수를 가지게 된다. 다른 상위 대역도 같은 형태를 가지는 후손계수를 가지게 된다. 이렇게 영상의 같은 위치를 복원하게 되는 부모-후손 계수들 간에는 서로 연관성을 가지 고 있고 일반적으로 부모 계수에서 후손 계수로 갈 수록 계수의 값이 작아지고, 부모계수의 값이 크면 후손계수의 값도 클 확률이 높고, 부모계수의 값이 작으면 후손계수들의 값도 작을 확률이 높다. 이것 이 이산 웨이블렛 분해된 영상의 계수에 대한 자기 상관관계를 말한다.
2. 부호화 과정
EZW 압축 방법은 제로트리 양자화의 부모-자식 관계를 이용하여 대응하는 웨이블렛 계수들을 예측 한다. EZW 부호화에서 주 부호화 과정은 웨이블렛 변환된 계수에 대하여 임계값을 기준으로 중요도를 판별하고 계수를 부호화 시키는 과정이다.
부호화 혹은 복호화 과정에서, 웨이블렛 계수들 은 2개의 분리된 목록인 중요 목록(dominant list)과 종속목록(subordinate list)을 갖는다. 즉 부호화 혹은 복호화 과정에서 발생한 중요 목록에는 아직까지 중요한 계수로 판명되지 않은 계수들의 좌표 값을 포함하고 있다. 종속 목록에는 중요한 계수로 판명 된 계수들의 크기 값을 포함한다. 이와 같이 중요 도 판별의 기준이 되는 임계값의 설정이 필요한데 초기 임계값(initial threshold, T0)는 식 (1-1) 같이 정의 할 수 있다.
여기서 Cmax는 가장 큰 웨이블렛 계수 값으로 정한다.
1) 주 부호화 과정
주 부호 과정에서는 웨이블렛 계수를 부호화하 기 위하여 제로트리 구조를 4가지의 부호로 표시했 는데 각각의 부호에 대한 정의는 <표 1>과 같다.
주 부호화 과정에서 중요도를 판별하기 위한 검 색 방법은 <그림 4>와 같은 Morton 검색 방법을 이 용한다.
이는 영상의 정보가 많이 포함된 저주파 대역에 서 시작하여 고주파 대역으로 진행하고, 웨이블렛 의 계수 값과 임계값을 비교하여 <표 1>의 EZW 부호화를 수행한다. 부호화는 입력된 계수를 비교 하여 중요한 계수로 판별 되어 부호화 되면, 그 계 수의 크기 값은 ‘0’으로 변환한다. 보다 작은 임계 값을 가지는 다음 주 부호화과정에서 제로트리 발 생을 방지한다.
2) 종속 부호화 과정
종속 부호화 과정은 종속 목록에 포함 되어진 값들을 검색 하면서, 복호화기 에서 복원될 값을 부가의 비트 정밀도를 갖도록 보다 세밀히 양자화 한다. 이는 종속 부호화 과정 동안에, 복호화된 값 의 불확실 구간(uncertainty interval)을 결정하는 양 자화 스텝의 크기를 절반으로 줄이는 효과가 있다. 이를 통하여 양자화 값과 실제 계수의 차이에 대해 실제 계수 값이 불확실 구간의 상위에 포함된 것 을 나타내기 위해 부호 ‘1’로 부호화 하고, 실제 계 수의 값이 하위 구간에 포함된다는 것을 나타내기 위해 부호 ‘0’ 으로 부호화 한다. 종속 부호화 과정 이 끝나면, 종속 목록의 크기 값들을 내림차순으로 정렬한다.
Ⅲ. 웨이블렛 변환 계수의 제로트리를 이용한 영상압축 알고리즘
주부호화 과정에서 주요한 부호인 P, N은 계수 의 절대값이 임계값 보다 큰 데이터를 표현하는 부 호로써, 임의의 2차원 데이터에 대해 임의의 비트 율에서 정지하지 않는 완전 복원 압축의 경우에 식 (2-1) 같은 최대값을 가지게 된다.
하지만T 는 주보호화 과정의 종료인자로써 반복 추가되고, Z 는 자식 계수의 데이터가 임계값을 넘 어 섬에 따라 반복적으로 추가된다.
따라서, 본 논문에서 이러한 반복적으로 들어가 는 T , Z 의 계수의 수를 줄이기 위해 2bit의 부호화 데이터의 크기를 3bit로 확장하고, 추가되는 부호를 통해 T , Z의 수를 줄여줌으로써, 압축효율을 향상 시킬 수 있는 수정된 임베디드 제로트리 알고리즘 을 제안하고 이를 확장 임베디드 제로트리 웨이블 렛(EEZW : Extended Embedded Zerotree Wavelet) 알 고리즘이라고 명명한바 있다.
1. 부호의 확장
2bit의 데이터 크기를 3bit로 확장하게 되면 추가 로 표현할 수 있는 부호의 개수는 4개가 늘어난다. 이때 4개의 확장된 부호를 <표 2>와 같이 확장한 다. 또한, 임베디드 제로트리 웨이블렛 알고리즘의 주부호화 데이터 순열의 특징을 반영한 것으로 T , Z 부호의 반복성을 고려하여 선정하였다. Z1은 자신은 Z를 의미하고 다음 데이터가 Z임을 의미하 는 추가된 부호이다. 이와 같은 방법으로 T2는 자 신은 T 이고 다음 2개의 데이터가 T 임을 표현한 부 호이다. 다음과 같이 데이터를 줄일 수 있다.
2. 확장 임베디드 제로트리 웨이블렛(EEZW)을 이용한 영상 압축 알고리즘의 구현
제안된 확장 임베디드 제로트리 웨이블렛 알고 리즘은 주부호화 과정에서 T , Z 부호에 대해 부호 의 중복도를 저장하는 변수의 추가와 각부호의 저 장 전에 기존의 T , Z 부호의 중복도 변수에 대해 적용하는 부분을 추가함으로써, 기존의 주 부호화 과정 알고리즘의 큰 변화 없이 구현할 수 있다. <그림 5>는 확장 임베디드 제로트리 웨이블렛 알 고리즘의 구현 블록도이다. <그림 5>의 각 부호의 부호화 과정 전에 Z, T 의 중복 계수를 판단하는 부 분만을 추가하여 기존의 임베디드 제로트리 웨이블 렛 알고리즘의 구조를 수정 할 필요 없이 간단하게 구현할 수 있다. 주 부호를 복원하는 과정에서는 각 중복 계수 부호만큼 부호를 추가해 주면서 복원 하면 추가 과정 없이 알고리즘을 구현할 수 있다.
3. 확장 임베디드 제로트리 웨이블렛(EEZW)과 임베디드 제로트리 웨이블렛(EZW) 알고리 즘의 주부호화 데이터 비교
<표 3>은 주 부호화 데이터를 이용한 확장 임베 디드 제로트리 알고리즘으로 어느 정도의 중복성을 줄일 수 있는 지를 표현하고 있다. 변환된 데이터는 실제로 다음과 같이 데이터가 축소됨을 확인 할 수 있다.
주요한 특징은 주부호의 데이터의 개수가 전체 적으로 37% 줄어들고 있다. 데이터의 총 비트수는 6.5% 정도 줄어들고 있다. <표 3>의 결과는 기본 데이터의 비트(bit)수가 2에서 3으로 확장됨으로써, 데이터 자체를 표현해야 할 데이터의 양이 늘어나 는 단점이 있으나 주 부호화 과정과 종속 부호화 과정이 증가 할수록 전체적인 비트수는 줄어든다. 끝에 정렬이 되도록 정렬을 양쪽 배분으로 한다.
Ⅳ. 실 험
실험은 기존의 임베디드 제로트리 웨이블렛 알 고리즘과 본 논문에서 제안된 확장-임베디드 제로 트리 웨이블렛(3bit) 알고리즘을 이용하여 Lena, Barbara, Goldhill, 영상에 대한 부호화 과정 후 복호 화 과정까지 수행한 결과물을 사용하여 제안한 방 법이 제대로 복호화가 가능한지를 비교하고 성능을 확인하는 순서로 진행하였다[8].
본 논문의 실험에 사용된 영상은 모두 256*256 크기의 흑백 (Grayscale, 8bit) 영상을 사용하였으며, 이산 웨이블렛 변환 분해를 6번 시도한 후 실험에 적용하였다. 실험에 사용된 영상의 원본은 실제 Lena, Barbara, Goldhill 영상에 EEZW를 적용함에 있어 3bit경우와 4bit경우의 결과를 비교 검토해 보 였다. 각각의 영상은 256*256의 흑백(Grayscale, 8bit)데이터이며, 6단계 이산 웨이블렛 변환을 적용 한 결과를 확장 임베디드 제로트리 웨이블렛 알고 리즘에 적용한 것이다.
사용한 성능지표는 오차의 제곱의 평균에 대한 상대적인 수치인 PSNR(PSNR : Peak Signal To Noise Rate)을 사용한다. 식 (3-1)은 PSNR의 수식이 다. 동일한 형식으로 결론을 작성한다. 식 (3-1)은 PSNR의 수식이다.
평균자승오차(MSE : Mean Squire Error)는 원래 의 영상과 복원된 영상의 화소값 간의 평균자승 오 차이다. 본 지표는 높을수록 원본과 가까운 영상임 을 나타낸다.
개별적인 영상에 있어 정량적인 PSNR 수치의 증가는 확연히 드러나고 있다. 또한, 영상의 전영역 의 향상은 아니지만 부분별로 영상의 복원력이 증 강되었음을 확인 할 수 있었다.
주요한 특징은 주부호의 데이터의 개수가 전체 <표 4>에 3가지 영상별 고정된 bpp값의 변화에 대 한 EZW, EEZW 알고리즘의 PSNR수치를 비교하여 <표 4>에 나타냈다. 이들 결과로부터 확인해 보면, 모든 경우에 EEZW가 높은 PSNR 수치를 보이는 것을 확인 할 수 있다.
Ⅴ. 결 론
본 논문에서는 기존의 임베디드 제로트리 웨이 블렛(EZW : Embedded Zerotree Wavelet) 알고리즘 을 개선하여 웨이블렛 변환 계수를 이용한 영상 압 축을 위한 확장-임베디드 제로트리 웨이블렛(EEZW : Extended Embedded Zerotree Wavelet)을 새로이 제 안하였다. 본 연구의 알고리즘은 기존의 임베디드 제로트리 웨이블렛 알고리즘의 주 부호화 과정에서 발생하는 동일한 부호의 중복을 기호화 하여 수록 용량을 축소하는 방법을 제시함으로써, 압축 효율 을 증가시킬 수 있었다.
본 논문의 영상 압축을 위한 확장-임베디드 제로 트리 알고리즘을 통해 다양한 영상에 적용하여 기 존 알고리즘 보다 성능의 우수함을 입증해 보였다. 실험에 적용한 모든 영상에 대해 대략 0.5dB의 PSNR(Peak Signal To Noise Rate)수치 증가를 보였 으며, 각 영상이 동일한 압축율을 갖는 경우도 PSNR수치의 증가를 보임으로서 향상된 기법임을 객관적으로 검증하였다.
