Advanced
Convergence Complexity Reduction for Block-based Compressive Sensing Reconstruction
Convergence Complexity Reduction for Block-based Compressive Sensing Reconstruction
Journal of Broadcast Engineering. 2014. Mar, 19(2): 240-249
Copyright © 2014, The Korean Society of Broadcast Engineers
  • Received : February 10, 2014
  • Accepted : March 03, 2014
  • Published : March 30, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
영균 박
혁재 심
병우 전
bjeon@skku.edu

Abstract
압축센싱 이론에 따르면 표본화 될 신호가 일련의 조건을 만족하는 성긴 신호라면 나이퀴스트 표본화주파수보다 적은 수의 측정 샘플들만 가지고도 원 신호를 완벽하게 복원할 수 있다. 그러나 압축센싱 이론을 실제 영상에 활용하기 위해서는, 신호 복원에 필요한 계산 복잡도와 메모리 요구량을 줄일 필요가 있다. 이런 관점에서 블록압축센싱(Block-based Compressive Sensing)에 기반한 Smooth Projected Landweber (BCS-SPL) 방법이 개발되었지만, 이 또한 복원과정의 계산 복잡도가 여전히 큰 문제가 있다. 본 논문에서는 기존의 BCS-SPL 복원 알고리즘의 수렴을 보다 빠르게 하기 위하여, 반복복원 중지조건, 허용 오차, 수렴 조절 인자를 개선한 수렴 복잡도 저감 방법을 제시한다. 제시한 방법은 기존 BCS-SPL 방법보다 낮은 수의 반복복원 횟수내로 수렴하면서도 동시에 복원 화질도 개선시키는 실험 결과를 보였다.
Keywords
Ⅰ. 서 론
압축센싱 이론에 따르면, 일정한 조건을 만족하는 성긴(sparse) 신호의 경우, 기존의 나이퀴스트 표본화주파수보다 더 적은 수의 샘플로도 손실 없이 원 신호의 완벽한 복원이 가능하다 [1] - [3] . 압축센싱 기술을 이용하면 표본화주파수를 더욱 낮출 수 있으므로, 다양한 응용에 이를 활용하기 위하여 많은 연구가 수행되고 있지만 [4] , 데이터량이 많은 영상 분야에서 본격적인 실용화를 위하여 해결하여야 할 문제가 아직도 매우 많은 상태이다. 한편, 압축센싱 이론을 영상획득에 적용한 단일 화소 카메라 [5] 실험데모가 발표된 바 있다. 압축센싱된 적은 수의 샘플 데이터로부터 원 영상을 충실히 복원하기 위하여 다양한 최적화 기법들이 필요하며, 이를 위하여 L1 optimization [6] , Orthogonal Matching Pursuit (OMP) [7] , Gradient Projection Sparse Reconstruction (GPSR) [10] 와 같은 많은 압축센싱 복원 알고리즘들이 개발되었다. 이런 다양한 알고리즘들은 대체로 Convex Optimization 기법과 Greedy pursuit 기법으로 분류될 수 있는데, Convex Optimization 기법은 복원 과정에서 높은 계산 복잡도를 요구하기 때문에 선호되지는 않는다 [7] . 대신, Greedy pursuit 기법은 신호 복원 시 높은 정확도와 상대적으로 빠른 신호 복원능력 때문에 널리 사용되고 있다. 대부분의 Greedy pursuit 기법들은 크게, 최선의 해를 찾기 위한 반복적인 복원 과정과 신호와 잡음을 분류하기 위한 문턱값 적용이라는 두 단계의 과정을 수행한다. Greedy pursuit 기법은 다른 방법들과 비교하여 상대적으로 낮은 복잡도를 가지지만, 아직도 그 자체로 여전히 높은 복잡도를 지닌다.
압축센싱의 신호센싱 및 복원복잡도를 줄이기 위한 방법으로, 압축센싱을 영상프레임 단위로 하는 것이 아니라 매 영상프레임을 작은 단위로 나누어 처리하는 블록기반 압축센싱 (BCS: Block-based Compressed Sensing) 기술이 소개되었다 [8] . 이 BCS 방법은 큰 영상 프레임을 작은 블록 단위들로 나눈 후, 동일한 압축센싱 과정을 각 블록들에 순차적으로 적용하는 것이다. 또한, BCS 방법으로 압축된 센싱데이터로부터 원 신호를 효과적으로 복원하기 위하여, SPL(Smooth Projected Landweber) 방법 [8] 을 추가로 적용한 BCS-SPL 방법 [12] 이 개발되었다. SPL 방법은 필터링 과정, 투영 과정, 하드 문턱값 적용과정등 크게 세 단계로 이루어 진다. BCS-SPL 방법을 사용하면, 종래의 영상프레임기반 기술과 비교하여 상대적으로 더욱 간단하고 빠르게 압축센싱 및 복원을 할 수 있으며, 또한 압축센싱 및 복원과정에 소요되는 저장 공간도 줄일 수 있다.
압축센싱 복원기법에 관한 중요한 실용화 연구 주제 중 하나는 좋은 복원 영상 품질을 유지하면서도 복원에 소요되는 계산 복잡도를 줄이는 것이다. 모든 Greedy pursuit 기법들은 반복적으로 동일한 과정을 반복하면서 복원된 신호가 최적 해로 더욱 가까이 수렴하기를 바란다. 그러나 비록 복원을 여러 번 반복 수행하지만, 이에 따르는 복원 영상 품질의 향상 정도는 지극히 적은 경우가 종종 발생한다. 따라서, 신호 복원 과정의 종료 조건들은 얻어지는 복원 영상이 되도록 정확한 값에 가까워지도록 하면서도 동시에 너무 정확한 해를 찾기 위해 과도한 연산이 수행되는 것을 방지하도록 고려되어야 한다 [10] . 즉, 계속되는 반복 횟수에 비하여 영상 개선정도가 크지 않다면 반복 과정을 조기 종료하는 것이 더욱 실용적이다. 이와 같은 목적으로, 반복적 복원과정의 지속 여부를 결정하기 위하여 문턱 값을 적절히 조절하는 방법 [9] 이 발표된 바 있다. 이 방법을 적용함으로써, Greedy pursuit 기법은 더 짧은 수렴 시간 이내에 신호 복원과정을 종료할 수 있게 된다.
본 논문에서는 압축센싱 복원 과정에서의 비효율적인 수렴과정을 줄이기 위하여 Greedy pursuit 기법의 반복 횟수를 줄일 수 있는 좀 더 개선된 복원 과정 종료 방법을 제시한다. 이 목적을 이루기 위해, 먼저 SPL 방법 적용시 발생하는 수렴 구간에서의 문제점과, 복원 신호 변화량 대비 복원 영상 품질간의 상관 관계를 분석하였으며, 이를 근거로 영상 특성에 따른 복원 과정의 조기 종료가 가능한 수렴 복잡도 저감 방법을 설계하였다.
본 논문의 구성은 다음과 같다. 제 Ⅱ장에서는 압축센싱과 BCS-SPL 구조에 대해 간략히 설명하고, 제 Ⅲ장에서는 복원 과정에서의 수렴 문제점, 신호변화량과 복원 영상 품질간의 상관 관계에 대해 분석한다. 그리고, 제 Ⅳ장에서는 반복 횟수를 줄이는 제안방법에 대하여 기술한다. 제 Ⅴ장에서는 제안 방법의 성능평가를 위한 실험 및 결과를 제시하고, 마지막으로 제 Ⅵ장에서 본 논문의 결론을 맺는다.
Ⅱ. 압축센싱 이론
- 1. 기본 압축센싱 이론
압축센싱의 전체구조는 센싱과 복원의 두 과정으로 구성된다. 센싱 과정에서, 입력 신호 x 는 식 (1)을 통하여 센싱되는 동시에 압축된다.
PPT Slide
Lager Image
여기서 x 는 실수 값을 가지는 원 영상 신호를 일차원 벡터로 표시한 것으로 N ×1 행렬이고, y 는 입력신호 x 를 측정 기저 Փ 를 사용하여 측정한 압축센싱 신호를 일차원 벡터로 표시한 M × 1 행렬이다. 식 (1)의 Փ 는 측정행렬 (measurement matrix)이라고 불리우는 M × N 행렬로서, 일반적으로 Gaussian Random 기저벡터로 구성된다. 일반적으로, 주어진 영상자체와 측정신호를 일차원화 하여 벡터 x y 를 구성하기 때문에 M N 의 값은 매우 크다. 따라서, M × N 의 측정행렬 Փ 역시 매우 큰 행렬이 되어 이를 저장하기 위한 메모리량도 매우 크다. 한편, M N 의 관계가 있기 때문에 압축과 센싱이 동시에 된다는 의미에서 압축센싱이라고 불리우며, 벡터 x 를 구성하는 N 개의 데이터대신, 식 (1)을 통하여 얻어지는 M 개의 데이터로 구성되는 y 벡터로부터, 원 신호 x 를 손실 없이 복원해 낼 수 있다는 것이 압축센싱의 기본 개념이다. 그러나, M N 의 관계가 있으므로 y 로부터 x 를 복원해 내는 것은 일반적으로는 무수히 많은 해를 지니는 ill-posed 문제이다. 또한, M / N 의 비율은 압축센싱에서 subrate 또는 측정율 (measurement rate)이라고 불린다. 원 영상신호 x 가 성긴 (sparse) 신호일 경우, 성김 (sparsity)을 만족하는 측정율 하에서는 완벽한 신호 복원이 가능함이 수학적으로 증명되었다 [1] - [3] . 여기서, 성긴신호라는 것은 주어진 신호벡터를 구성하는 벡터 요소 (element)들이 상당히 많은 zero 값을 갖는 것을 말한다. 좀 더 정확한 개념 설명을 위하여 K-sparse의 용어가 정의되었다. 즉, 주어진 신호벡터의 요소들이 최대 K 개까지만 non-zero 값을 갖는 신호벡터를 K-sparse 하다고 한다. 자연계의 일반적인 신호는 그 자체로 K-sparse 하지 않더라도, 특정 영역으로 신호변환을 하였을 경우 에너지가 몇 개의 축으로 집중되기 때문에 성긴 신호가 될 수 있다. 또한, 신호가 정확히 K-sparse 하지 않더라도 몇 개의 큰 값을 갖는 요소들을 제외하고 나머지는 매우 작은 크기만을 갖는다면, 이를 zero 값으로 간주하는 K-term Approximation을 할 수 있다. 이렇게 특정 변환영역에서 신호를 K-term Approximation 할 수 있는 신호를 Compressible 신호라고 한다. 영상신호의 경우 DCT (Discrete Cosine Transform) 또는 WT (Wavelet Transform)을 사용하여 신호 변환하였을 경우 우수한 신호 에너지 집중화 현상으로 인하여 성긴 신호의 특성이 매우 잘 나타나므로, Compressible 신호의 아주 좋은 예가 된다. 식 (2a)와 같이 주어진 신호 x 가 Compressible 하다고 하고, 이를 위한 변환을 Ψ 라고 하자.
PPT Slide
Lager Image
여기서 α 는 변환 후 얻어진 성긴 신호를 나타낸다. 따라서, 원래의 압축센싱을 나타내는 식 (1)은 다음과 같이 변경된다.
PPT Slide
Lager Image
여기서 ( ՓΨ ) 자체를 새로운 측정행렬로 보면, 식 (2b)는 식 (1)과 결국 동일한 형태가 된다. 따라서, 변환영역에서 압축센싱을 하던지 원 신호 영역에서 압축센싱을 하던지에 상관하지 않고 일반적으로 식 (1)만을 사용하여 압축센싱의 이론 전개가 가능함을 알 수 있다.
- 2. BCS-SPL 구조
압축센싱 이론을 실제 영상신호에 적용하기 위하여, 압축센싱의 연산 복잡도와 저장 공간 요구량의 문제점을 해결하기 위한 블록 기반 알고리즘(BCS) [8 , 12] 이 소개된 바 있다. 이에 따르면, 블록 압축센싱 과정에서 입력 영상은 작은 블록 영상으로 나뉘어지고, 각각의 나뉘어진 블록 영상을 블록 크기와 측정율에 따라 설정된 측정행렬에 사영시켜 블록별 측정 신호 y 가 얻어진다. 이 블록 기반 압축센싱 방법을 통해 측정행렬을 더욱 작게 만들 수 있게 되어 계산 복잡도와 측정행렬을 저장하기 위한 저장 공간 요구량을 동시에 상당히 줄일 수 있다.
블록기반 압축센싱 신호의 복원을 위하여 사용되는 SPL 복원 방법 [8 , 12] 은 반복적으로 위너 필터링 [13] , Projected Landweber (PL), 하드 문턱 값 적용등의 과정을 수행한다. 그림 1 은 BCS-SPL 알고리즘 구조를 나타내며 [12] , PL 과정은 식 (3)과 같다.
PPT Slide
Lager Image
BCS-SPL 구조도[8,12] Fig. 1. BCS-SPL Scheme[8,12]
PPT Slide
Lager Image
여기서 ՓB 은 블록단위의 측정행렬이며, xi (k) 는 k번째 반복복원과정을 통하여 얻은 i번째 블록 신호, yi 는 i번째 블록 신호에 대한 측정치 벡터이다. 문턱값 적용과정에서는 복원되고 있는 영상신호내의 잡음 정도를 변환 도메인에서 추정하고, 이 추정된 값보다 작은 값을 가지는 복원 영상 계수들을 0으로 설정한다. 이러한 과정들은 소정의 종료 조건들을 만족시키기 전까지 반복적으로 수행된다.
Ⅲ. SPL 복원 알고리즘 분석
압축센싱기술을 실제 응용에 적용하기 위하여 해결하여야 하는 중요한 문제 중 하나는 빠른 복원 알고리즘을 개발하는 것이다. 이런 측면에서 압축센싱된 신호로부터 복원되는 영상의 품질 저하 없이도 복원반복 횟수를 줄이는 것에 대해 연구할 가치는 매우 크다. 본 논문에서는 현재 많이 활용되는 BCS-SPL 복원알고리즘의 수렴과정에서 관찰되는 문제점을 분석하여 이의 수렴속도를 높이기 위한 방법을 제시한다.
- 1. 잔차 신호 에러 진동
잔차 신호 에러 진동은 예측된 복원 영상과 실제 입력 영상 간의 차이 값이 반복적으로 변동하는 현상을 말한다. SPL 복원 알고리즘이 이러한 현상을 보이는 것은, SPL 방법이 최적 해를 찾기 위하여 사용하는 Gradient descent 최적화 방법의 특정 성질과 사용되는 종료 조건 때문이다. Gradient descent 최적화 방법은 최적의 해로 수렴하기 위한 복원에 적절한 방향성을 zigzag pursuit [14] 방법을 사용하여 계산한다. 그런데, 만일 최적의 해가 평탄하지 않은 영역에 존재하는 경우, zigzag pursuit 방법은 복원에 적절한 안정된 방향성을 찾지 못하므로 최적의 해를 쉽게 찾지 못하는 특성을 갖는다. 따라서, Gradient descent 방법을 이용하는 SPL방법의 복원 과정도 역시 이와 같은 zigzag pursuit 방법 때문에 잔차 신호 에러 진동의 문제를 지닌다.
- 2. 허용 오차 (Tolerance)
허용 오차는 복원되는 영상 신호가 충분히 높은 정확도를 얻었는지 판단하여 신호 복원 과정을 조기에 종료시킬지 여부를 결정하는데 사용되는 중요한 파라미터이다. 압축센싱 복원과정에 사용하는 대부분의 Greedy 기법들은 원 입력 신호로부터 어느 정도 범위내에 존재하는 근사 최적해를 얻기 위해 특정한 측정 허용 오차 값을 사용하고 있다. 따라서, 이 허용 오차 값은 복원된 영상의 정확도와 복원 수행 시간과의 관계에 직접적인 영향을 미친다. 즉, 작은 허용 오차만을 허락하면 복원 영상의 정확도는 좋아지지만, 복원을 위한 수렴 과정에 소요되는 반복 과정 횟수가 증가하게 된다. 특히, 어느 정도 반복 이후의 수렴 과정에서는 복원 영상의 정확도의 향상 정도가 극히 적을 수 있기 때문에 지나치게 긴 수렴 과정은 비효율적일 수 있다. 그러므로, 수렴 과정에 소요되는 반복 횟수를 적절히 줄이는 것이 계산 복잡도를 줄이면서 복원 영상의 정확도를 확보하는데 매우 중요하다.
- 3. 문턱 값 적용과정 (Thresholding)
문턱 값 적용은 크게 SureShrink [15] 방법적용과 하드 문턱 값 적용 [16] 의 두 단계로 수행된다. SureShrink 방법은 변환 도메인에서의 계수 값들을 이용하여 잡음의 최대값을 추정한 후 이를 사용하여 식 (4)와 같이 문턱 값을 예측한다 [15] .
PPT Slide
Lager Image
이때, τ 는 예측된 문턱 값이고, λ 는 수렴 조절 인자, 그리고
PPT Slide
Lager Image
는 미디언 절대 편차를 이용하여 추정된 잡음 최대 값을 나타낸다. 하드 문턱 값 적용 단계에서는 식 (4)를 사용하여 얻어진 문턱 값보다 복원과정에서 얻어지는 신호의 계수의 크기가 작으면 그 계수들을 0으로 설정한다. 여기서, 수렴 조절 인자 λ 는 한번 예측된 문턱 값을 복원 과정내에서 추가로 조절하기 위해 설정되는데, 미디언 절대 편차를 이용하여 추정된 잡음 값인
PPT Slide
Lager Image
가 잡음의 최대치이기 때문에 이 수렴 조절 인자는 1 이상일 필요가 없다.
- 4. 복원신호 변화량과 복원 영상간의 상관 관계
복원 과정을 거치면서 얻어지는 영상은 주로 저주파 성분을 중심으로 복원되어진다. 이는 SPL 복원과정에 적용되는 위너필터가 저주파통과 필터의 특성을 지니기 때문이다. 반복된 복원과정을 통하여 신호의 변환 계수값들의 변화량은 점차 줄어들게 되고 이에 따라 문턱 값 적용과정으로 0으로 새롭게 설정되는 값들의 수는 점차로 줄어들어 마침내 수렴된 복원 영상 결과가 얻어진다. 따라서, 수렴과정중에 얻어지는 신호의 변화량과 복원 영상의 정확도간에 특정한 관련성이 있을 것으로 예상된다. 이를 확인하기 위하여, 일반적 신호에 대하여 사용하는 MSE (mean-squared-error) 척도가 아닌, 인간 시각특징을 고려한 로그 영역척도인 PSNR을 사용하여 복원 영상의 정확도 계산을 하였다.
표 1 은 반복 복원 과정에서의 신호 변화량과 복원 영상 정확도 간의 상관 관계를 영상별, 측정율 별로 비교하여 나타낸 것이다. 대부분의 값이 –1에 가까우며, 이를 통해 변화량과 복원 영상 정확도 간에는 뚜렷한 음적 선형 관계를 가지고 있음을 확인할 수 있다. 즉, 복원 영상의 정확도가 좋아질수록 변화량은 작아지는 관계가 성립함을 알 수 있다.
복원 과정에서 신호변화량과 복원 영상 정확도간의 상관 관계
PPT Slide
Lager Image
Table 1. Correlation between signal variance in change and accuracy of reconstructed image
Ⅳ. 복원과정의 수렴복잡도 감소를 위한 제안방법
지금까지 기술된 문제점들과 수렴과정중의 신호변화량과 복원되는 영상간의 상관관계에 근거하여, 복잡도를 줄이면서도 영상 특성에 맞춰 조기 종료를 가능하게 하도록 몇 가지 개선된 방법을 제시한다. 우선적으로, 잔차 신호 에러진동에 의해 발생되는 수렴 시간의 증가를 방지하기 위해 새로운 종료 조건을 설정하였다. 그림 1 에서 Stopping Criterion 으로 표시된 기존의 종료 조건은 식 (5a)와 같다.
PPT Slide
Lager Image
여기서, D는 제곱 평균으로 계산된, 문턱 값 적용 이전과 이후의 복원 영상간의 차이이다. 식 (5a)의 기존 종료 조건을 활용하는 경우, 특정한 상황에서는 영상 품질의 개선이 전혀 없는 상태로 복원계산이 반복되면서도 수렴 조건을 만족시키지 못하여, 불필요한 복원과정이 계속 반복되는 최악의 상황이 발생한다. 즉, 잔차 신호 에러진동 현상으로 문턱 값이 오작동되며, 이에 따라 복원 과정이 의미 없이 지속되게 되는 것이다. 이를 방지하기 위해 본 연구에서 제시하는 개선된 종료 조건은 식 (5b)와 같다.
PPT Slide
Lager Image
식 (5a)의 기존 조건에서는 현재와 바로 이전의 D값만을 사용하여 수렴의 종료여부를 결정하는데, 만일 D (k) 값이 D (k-1) , D (k-2) 값보다 크거나 같다면, 더 많은 반복 과정은 무의미하다. 따라서, 식 (5b)의 두 가지 조건을 새로운 종료 조건으로 이용함으로써 문턱 값 적용과정이 반복 과정에서 정상 기능하고 있는지 확인할 수 있으며, 동시에 zigzag pursuit에 의한 비수렴 문제를 방지할 수 있다.
또한, 압축센싱 복원의 복잡도를 감소하기 위하여, 허용오차 (tolerance) 값이 복원된 영상을 기준으로 매 반복 단계에서 변화하도록 하여 주어진 영상에 맞추어 수렴속도를 개선하도록 설계하였다. 즉, SPL 복원 과정내의 변환 도메인에서 계산한 복원 신호 변화량을 식 (6)과 같이 사용하여 허용 오차 값이 복원된 영상을 기준으로 매 반복 단계에서 적응적으로 변화하도록 하였다.
PPT Slide
Lager Image
여기서 var(•)는 신호 변화량이며, x *은 복원 과정의 문턱 값 적용 시 변환 도메인에서 획득할 수 있는 변환된 전체 계수 값들이다. 변환된 계수들을 이용하여 계산된 허용 오차 값을 매 단계에 적용함으로써, 영상의 특성에 따른 허용 오차를 복원 알고리즘에서 적응적으로 적용 가능할 수 있게 된다. 따라서, 기존 방법과 같이 고정된 값을 이용하는 것보다 수렴 구간에서 소요되는 시간을 줄이면서도 영상 특성을 반영한 효과적인 복원이 가능하다.
마지막으로 식 (4)에서의 수렴 조절 인자 λ 를 최대 잡음값 예측 방법을 토대로 개선하도록 하여 압축센싱의 복원 복잡도를 감소시켰다. 기존 방법에서는 수렴 조절 인자 λ 값을 비교적 큰 값인 6에서 시작하여 1보다 작은 값인 0.7776까지 매 단계 60%씩 감소하는 방식으로 조절한다. 하지만, 큰 수렴 조절 인자 값은 대부분의 변환 계수 값들을 하드 문턱 값 적용 과정에서 0으로 만들어 버리게 되므로 연산 과정에서 무의미한 낭비를 초래할 수 있다. 수렴 조절 인자를 1로만 설정하여도 잡음의 최대치를 예측할 수 있으며 가우시안 랜덤 잡음 특성과 미디언 평균화를 근거 [12] 로 하여 기존의 수렴 조절 인자 조정을 두 단계로만 제한하고 그 값을
PPT Slide
Lager Image
과 같이 설정하였다.
Ⅴ. 실험결과 및 분석
본 논문에서 제안한 압축센싱 복원 복잡도 저감 방법의 성능을 확인하기 위하여, 512 × 512 표준시험 [17] 흑백영상인 Lena, Mandrill, Peppers, Boat, Man을 사용하여 기존 BCS-SPL [12] 방법과 성능을 비교하는 실험을 수행하였다. 기존 방법과 제안 방법 모두 이산 코사인 변환(DCT)을 사용하였으며, 입력 영상은 32 × 32 크기의 블록단위들로 처리되었다. 측정 행렬으로는 기존 BCS 방법과 동일한 가우시안 랜덤 행렬을 사용하였고, 평균 신호 대비 잡음비 (PSNR)을 이용하여 측정율 0.1부터 0.5까지 0.1 간격으로 증가시켜 가면서 실험을 수행하였다. 또한, 동일 조건의 실험과정을 각각 10번씩 수행한 후 이를 평균화하여 최종 결과값을 산출하였다.
표 2 는 BCS-SPL 방법과 비교하여 제안된 방법에서의 반복횟수 절감율을 보여주고있다. 복원시 요구되는 반복횟수 절감율 (AS: Average_Saving)은 식 (7)과 같이 계산되었다.
복원 과정에 소요된 반복 횟수와 기존 방법 대비 반복 절감율(%)
PPT Slide
Lager Image
Table 2. Required number of iterations and saving ratio in reconstruction (AS(%))
PPT Slide
Lager Image
표 2 에 표시된 AS 값을 계산하기 위하여 사용한 식(7)에서, I 특정방법 는 주어진 특정방법 (BCS_SPL 또는 proposed)을 적용하였을 경우 소요된 반복횟수 (단위: 회) 이다. 표 2 를 보면 제안된 방법은 모든 실험영상에서 각각 평균적으로 반복 횟수를 47.52%, 77.66%, 70.06%, 51.00%, 48.06% 저감시킴을 알 수 있다.
표 3 에서는 기존 방법 대비 제안된 방법의 복원 시간 절감율을 제시하였다. 표 3 에 표시된 AS를 계산하기 위하여 사용한 식(7)에서, I 특정방법 는 주어진 특정방법 (BCS_SPL 또는 proposed) 을 적용하였을 경우 영상 한 장을 복원하는데 소요된 연산시간 (단위: 초) 이다. 표 3 은 각각 49.62%, 74.46%, 68.96%, 51.94%, 47.90%의 평균 시간 절감율을 보인다. 이는 연산시간과 반복 횟수간의 비례 관계를 보여준다. 이와 같은 실험 결과를 통해 제안된 방법이 계산 복잡도를 기존 BCS-SPL 방법 대비 50% 이상 줄여줌을 확인하였다.
복원 과정에 소요된 시간과 시간 절감율
PPT Slide
Lager Image
Table 3. Required time and saving ratio in reconstruction (sec, AS(%))
제안된 방법의 감소된 계산복잡도에 따른 복원된 영상 화질에 문제가 없음을 확인하기 위하여 표 4 와 같이 복원 영상화질을 분석하였다. 표 4 는 각 실험영상에 대하여 측정율에 따른 기존방법과 제안방법의 평균신호 대비 잡음비를 비교한 것이다. 표 4 에서 나타난 바와 같이 제안된 방법이 기존방법보다 더 빠른 속도를 보이는 데도 불구하고 미소하지만 더 나은 화질을 보임을 확인할 수 있다. 또한, Peppers 영상에서는 zigzag pursuit 과정 때문에 발생하는 비수렴 문제를 해결함으로써 두드러지는 화질 개선이 확인되었다.
복원 영상의 PSNR 화질 [dB] 비교 분석
PPT Slide
Lager Image
Table 4. PSNR performance [dB] of reconstructed image
Ⅵ. 결 론
본 논문에서는 블록 기반 압축센싱 SPL 방법의 수렴 구간을 단축하는, 영상 특성에 따른 적응적인 수렴 복잡도 저감 방법을 제시하였다. 즉, 복원 과정에서 소요되는 반복 횟수 및 시간 복잡도를 줄이면서 영상 복원 결과에 따른 적응적 반복횟수 조절을 통해 영상 복원의 연산 효율성을 향상시킨다. 제안하는 방법은 복원 과정에서 오작동을 방지하고, 수렴 구간을 단축시키는 효과를 지닌다. 제시하는 방법은 기존의 BCS-SPL 방법에 비해 평균적으로 58.9%의 반복 횟수 절감, 58.6%의 복원시간 절감율을 얻을 수 있음을 보였다. 또한, 0.50dB의 화질 개선 효과도 얻었다. 본 논문에서 제시된 방법은 다양한 Greedy 최적화 알고리즘에 적절하게 적용될 수 있으며, 복원 알고리즘의 실용화에 도움이 될 것으로 예상된다. 앞으로 보다 다양한 알고리즘에 적용 및 효율적인 복원 알고리즘 개발에 대한 추가적인 연구가 필요하다.
BIO
박 영 균
- 2012년 : 성균관대학교 전자전기공학과 졸업 (학사)
- 2014년 : 성균관대학교 IT융합학과 졸업 (석사)
- 2014년 ~ 현재 : 삼성전자 연구원
- 주관심분야 : 멀티미디어 영상압축, 신호처리
심 혁 재
- 2000년 : 성균관대학교 전자공학과 졸업 (학사)
- 2002년 : 성균관대학교 정보통신공학부 졸업 (석사)
- 2013년 : 성균관대학교 정보통신공학부 졸업 (박사)
- 2013년 ~ 현재 : 성균관대학교 정보통신공학부 박사 후 과정
- 주관심분야 : 멀티미디어 영상압축, 신호처리
전 병 우
- 1985년 : 서울대학교 전자공학과 졸업 (학사)
- 1987년 : 서울대학교 전자공학과 졸업 (석사)
- 1992년 : Purdue Univ, School of Elec. 졸업 (공학박사)
- 1993년 ~ 1997년 : 삼성전자 신호처리연구소 수석연구원
- 1997년 ~ 현재 : 성균관대학교 정보통신공학부 교수
- 주관심분야 : 멀티미디어 영상압축, 영상인식, 신호처리
References
Donoho D. L. 2006 "Compressed sensing," IEEE Trans. Inf. Theory 52 (4) 1289 - 1306    DOI : 10.1109/TIT.2006.871582
Candes E. J. , Wakin M. B. 2008 "An introduction to compressive sampling," IEEE Signal Processing Mag. 21 (3) 21 - 30    DOI : 10.1109/MSP.2007.914731
Candes E. J. , Romberg J , Tao T 2006 "Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information," IEEE Trans. on Info. Theory 52 (2) 489 - 509    DOI : 10.1109/TIT.2005.862083
Smith L. N. 2013 "How to find real-world applications for compressive sensing," in Proc. of SPIE Defense, Security and Sensing. Int. Society for Optics and Photonics May 87170Q-81170Q-10
Takhar Dharmpal , Laska Jason N. , Wakin Michael B. , Duarte Marco F. , Baron Dror 2006 "A new compressive imaging camera architecture using optical-domain compression" in Proc. SPIE 6065, Computational Imaging IV, 606509 Feb.
Eldar C. , Kutyniok G. 2012 Compressed sensing: Theory and applications ambridge University Press
Fornasier M. , Rauhut H. 2011 "Compressive Sensing," in Handbook of athematical Methods in Imaging Springer Heigelberg, Germany
Gan L. 2007 "Block compressed sensing of natural images," in Proc. of International Conference on Digital Signal Processing Jul. 403 - 406
Tavakoli A. , Pourmohammad A. 2012 "An efficient iterative thresholding method for compressed sensing," Int. Journal of Comuter Theory and Engineering 4 (2) 270 - 273    DOI : 10.7763/IJCTE.2012.V4.464
Figueiredo M. A. T. , Nowak R. D. , Wright S. J. 2007 "Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems," IEEE Journal on Selected Areas in Comm. 1 (4) 586 - 597
Razavi S. A. , Ollila E. , Koivunen V. 2012 "Robust greedy algorithms for compressed sensing," in Proc. IEEE Conf., European Signal Processing Aug. 969 - 973
Mun S. , Fowler J. E. 2009 "Block compressed sensing of images using directional transforms," in Proc. IEEE Int. Conf. on Image processing (ICIP) Nov. 3021 - 3024
Gonzalez R. C. , Woods R.E. 1992 Digital Image Processing 2nd ed. Addison-Wesley, Reading, MA
Yuan Y. X. 2008 "Step-sizes for the gradient method," in Proc. of the 3rd Int. Congress of Chinese Mathematicians, AMS/IP Studies in Advanced Mathematics 785 - 796
Donoho D. L. 1995 "De-noising by soft thresholding," IEEE Trans. Info. Theory 41 (3) 613 - 627    DOI : 10.1109/18.382009
Blumensath T. , Davies M. E. 2009 "Iterative hard thresholding for compressed sensing," Appl. Computat. Harmon. Anal. 27 (3) 265 - 274    DOI : 10.1016/j.acha.2009.04.002
The USC-SIPI image database http://sipi.usc.edu/database/