Advanced
An Efficient Method to Compute a Covariance Matrix of the Non-local Means Algorithm for Image Denoising with the Principal Component Analysis
An Efficient Method to Compute a Covariance Matrix of the Non-local Means Algorithm for Image Denoising with the Principal Component Analysis
Journal of Broadcast Engineering. 2016. Jan, 21(1): 60-65
Copyright © 2016, The Korean Society of Broadcast Engineers
  • Received : October 14, 2015
  • Accepted : December 10, 2015
  • Published : January 30, 2016
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
정 환 김
제 창 정
jjeong@hanyang.ac.kr

Abstract
본 논문에서는 영상에 존재하는 잡음 (noise) 들을 제거하는 방법 중 하나인 비 지역적 평균 (non-local means, NLM) 알고리즘을 먼저 소개하고 비 지역적 평균 알고리즘의 개선된 방법 중 하나인 주성분 분석 (principal component analysis, PCA) 기반의 알고리즘에 대해서도 소개한다. 주성분 분석을 활용하기 위해서는 선행적으로 공분산 행렬 (covariance matrix)을 구해야 하는데, 영상의 모든 픽셀들을 대상으로 하였을 때 이 공분산 행렬을 구하기 위해서는 큰 크기를 가지는 행렬 곱 연산이 필요하다. 만약 비 지역적 평균 알고리즘의 영상 패치 (neighborhood patch) 의 크기를 S × S = S 2 , 영상 전체의 픽셀 수를 Q 라고 한다면 공분산 행렬을 구하기 위해서는 S 2 × Q 크기의 행렬 곱 연산이 필요하게 된다. 이는 영상의 특성을 고려하면 비효율적인 연산이다. 따라서 본 논문에서는 공분산 행렬을 효율적으로 구하기 위해, 영상 패치들간의 일정 간격을 유지하면서 샘플링을 하는 방법을 제안하고자 한다. 최종적으로, 샘플링 후에는 S 2 × floor ( Width / l ) × ( Height / l ) 크기를 가진 행렬의 곱 연산으로 공분산 행렬을 구할 수 있다.
Keywords
Ⅰ. 서 론
카메라를 이용하여 이미지를 획득하게 되면, 취득한 영상에는 일반적으로 잡음(noise) 도 같이 따라오기 마련이다. 이런 영상에서 잡음을 제거하는 기법을 디노이징 (denoising) 이라고 하며 영상처리 분야에서 지금까지 가장 많이 연구되어 온 분야이다. 그 중 ‘비 지역적 평균(non-local means, NLM)’ 알고리즘은 다른 알고리즘들 [5] [6] [7] 에 비해 비교적 쉬운 구현에 비해 뛰어난 성능을 가지고 있어서 가장 많이 사용되는 디노이징기법중 하나이다. 비지역적 평균 알고리즘은 다른 디노이징 기법과 마찬가지로 이미지의 특성인 한 픽셀(pixel) 과 주변 픽셀들이 비슷하다는 특성을 이용하여 잡음을 제거하는데, 따라서 잡음을 제거하기 위해서 비 지역적 평균 알고리즘은 영상의 모든 픽셀들을 처리해야 하고, 그만큼 영상의 해상도가 커질수록 계산 복잡도가 커지게 된다. 이런 비 지역적 평균 알고리즘의 복잡도를 줄이기 위한 방법중 하나로 주성분 분석 (principal component analysis, PCA)을 이용하여 알고리즘의 계산 량을 줄이는 방법이 있는데, PCA를 이용하기 위해서는 필수적으로 공분산 행렬 (covariance matrix) 계산이먼저수행되어야한다. 본 논문에서는 이 공분산 행렬 계산을 효과적으로 하는 방법을 제안하고자 한다.
본 논문은 다음과 같이 구성되어 있다. 2장에서는 비 지역적 평균 알고리즘을 소개하고, 이어서 주성분 분석을 활용한 수정된 비 지역적 평균 알고리즘을 소개한다. 4장에서는 공분산 행렬을 효과적으로 계산하는 방법을 제안하고, 마지막으로 5장에서는 실험을 통하여 제안한 알고리즘의 성능을 보여준다.
Ⅱ. 비 지역적 평균 알고리즘 (Non-local means algorithm)
잡음에 의해서 오염된 영상 (관측된 영상) v ( i )는 다음과 같이 수학적으로 모델링을 할 수 있다.
PPT Slide
Lager Image
u ( i )는 원본 영상, η ( i )잡음 항으로 일반적으로 가산성 백색 가우시안 잡음 (additive white Gaussian noise, AWGN) 으로 모델링 한다. i 는 픽셀 인덱스 (index) 로 영상 전체의 픽셀 개수를 Q 라고 하면 i = {1, 2, ⋯, Q }이다. 영상 에 존재하는 잡음을 제거하는 디노이징 기법은 관측된 영상 v ( i )를 이용하여 원본 영상을 추정하는 것으로 비 지역적 평균 알고리즘 [1] 은 픽셀 i 를 중심으로 S × S 의 크기를 가지는 영상 패치 (neighborhood patch)를 이용하여 픽셀 i 주변의 픽셀들 간의 비슷한 정도를 측정한 후 가중 평균을 취해 원본 영상 u ( i )를 추정하게 된다. 비 지역적 평균 알고리즘의 정의는 다음과 같다.
PPT Slide
Lager Image
N i 는픽셀 i 를 중심으로 S × S 크기를가지는영상패치, Ω i 는 픽셀 i 를 중심으로 R × R 크기 안에 들어오는 픽셀들의 집합 (searching window),
PPT Slide
Lager Image
는 원본 영상의 추정치,
PPT Slide
Lager Image
는 정규화 (normalization)항이다. h 는 는 가중 평균 합을 조절하는 사용자 매개변수(parameter) 이다. h 값에 따라 디노이징 결과의 큰 영향을 주기 때문에 상황에 맞는 적절한 값이 필요하다. [1] 에서는 만약 백색 가우시안 잡음의 분산 값 σ 2 을 알 수 있다면, 대략적으로 h =10 × σ 을 정의했으나, 다른 연구에 의하면 [2] 최대 신호 대 잡음비 (peak signal-to-noise ratio, PSNR) 관점에서 보다 더 좋은 결과를 얻기 위해서는 다른 선택이 필요하다는 것을 알 수 있다.
비 지역적 평균 알고리즘의 복잡도는 O ( Q × S 2 × R 2 ) 이다. 조절 불가능한 전체 픽셀 개수 Q 를 제외하면 비 지역적 평균 알고리즘 알고리즘의 복잡도는 S R 의 영향을 받게 된다. 처음 비 지역적 평균 알고리즘 알고리즘을 제안한 [1] 에서는 영상의 모든 픽셀들을 대상으로 알고리즘을 수행하지만 알고리즘의 복잡도를 위하여 R 을 제한하는 것이 일반적이다. 언뜻 보기에는 R 이 클수록 높은 최대 신호 대 잡음비를 얻을 수 있을 것 같지만, [3] 에 의하면 비슷한 패턴의 반복으로 이루어진 이미지와 같은 몇몇 예외를 제외하면, R ≥ 15 인 경우에는 오히려 최대 신호대 잡음비가 감소한다고 한다. S R 보다 결과값에 영향을 덜 미치는 매개변수로 주로 5 ≤ S ≤ 9를 선택한다 [3] .
Ⅲ. 주성분 분석 기반 비 지역적 평균 알고리즘 (Principal neighborhood dictionary non-local means)
여전히 비 지역적 평균 알고리즘의 복잡도에서 가장 큰 영향을 주는 Q 를 조절할 수 없기에, 큰 영상의 경우에는 많은 알고리즘 수행시간이 필요하다. [2] 는 기존의 두 이미지 패치의 L 2 거리를 계산하는 대신에, 주성분 분석 [4] 를 이용하여 패치의 차원 (dimensions) 을 낮춰서 L 2 거리를 계산함으로써 비 지역적 평균 알고리즘의 복잡도를 줄이면서 더 좋은 결과를 얻을 수 있다고 한다. 먼저 주 성분 분석을 활용하기 위해서 영상 패치들의 공분산 행렬을 계산해야 한다. 행렬 M ∈ R S2×Q 을 다음과 같이 정의하자.
PPT Slide
Lager Image
pi ( k ), i = {1, 2, ⋯, Q }, k = {1, 2, ⋯, S 2 }는 한 영상 패치를 열 벡터 (column vector)로 나타낸 것이며,
PPT Slide
Lager Image
는 벡터 pi 의 평균 값이다. 따라서 공분산 행렬 C ∈ R S2×S2 는 다음과 같이 정의 된다.
PPT Slide
Lager Image
공분산행렬 C의고유값(eigenvalues)을구하고고유값의 크기를기준으로고유벡터(eigenvectors) { wd : 1 ≤ d S 2 }를 내림차순으로 정렬한다. 이 고유 벡터들을 이용하여 S 2 차원을 가진 기존의 영상 패치 N i d 차원으로 축소함으로써 비 지역적 평균 알고리즘의 복잡도를 줄일 수 있게 된다. 최종적으로 수정된 비 지역적 평균 (principal neighborhood dictionary non-local means, PND NLM) [2] 알고리즘의 정의는 다음과 같다.
PPT Slide
Lager Image
vd (N i )는 차원이 축소되어 d 차원을 가진 이미지 패치이며,
PPT Slide
Lager Image
이다. 주 성분 기반 비 지역적 평균 알고리즘의 복잡도는 O ( Q × d × R 2 )가 되며, d = S 2 인 경우에는 기존의 알고리즘과 동일하다.
Ⅳ. 효율적인 공분산 행렬 계산
앞서 보듯이, 영상의 모든 패치들을 대상으로 공분산 행렬 계산을 하기 위해서는 매우 큰 차원을 가진 행렬 곱 연산이 수행되어야 한다. 하지만 영상 특성상 이웃한 패치들은 매우 비슷하기 때문에 모든 패치를 대상으로 공분산 행렬을 구하는 것은 비효율적이다. [2] 에서는 전체 샘플 개수의 10% 의 샘플을 가지고 공분산 행렬 계산을 하는 것이 효율적이라고 언급이 되어 있으나 구체적으로 어떻게 샘플링을 하는지, 샘플 개수에 따른 알고리즘의 성능의 변화는 설명되어 있지 않다. 따라서 본 논문에서는 구체적인 샘플링 방법과 샘플링에 따른 성능을 비교해보고자 한다. 샘플링 방법은 다음과 같다.
그림 1 과 같이 일정 간격 l Z 을 유지하면서 픽셀을 샘플링을 한다. 즉, l = 1인 경우에는 공분산 행렬 계산에 모든 영상 패치들을 고려하는 것이며, l ≥ 2인 경우에는 샘플링을 하여 행렬 M의 차원이 다음과 같이 줄어들게 된다.
PPT Slide
Lager Image
PPT Slide
Lager Image
픽셀 샘플링 Fig. 1. Pixel sampling
floor (‧)는 바닥 함수 (floor function) 이며, Width Height 는 각각 영상 v 의 폭과 넓이 이다 ( Q = Width × Height ).
Ⅴ. 실험 결과
표 1 은 샘플링 간격 l 에 따른 최대 신호 대 잡음비 공분산 행렬 C 계산에 필요한 시간을 측정한 것이다. 모든 실험은 Intel® i5-2500, 4GB RAM, MATLAB R2011a 환경에서 수행 되었으며, 표 1 의 세 번째 열은 공분산 행렬 계산에 걸린 시간이며, 네 번째 열은 공분산 행렬 계산을 포함하여 전체 알고리즘 수행 시간이다. 두 열 모두 l = 1일 때 걸린 시간을 기준으로 나타내었다. 표에서 나타나듯이 l 이 커짐에도 불구하고 최대 신호 대 잡음비의 변화는 거의 없지만 계산 량은 확연하게 줄어드는 것을 알 수 있다. 오히려 l = 64인 경우에 최대 신호 대 잡음비가 소폭 상승하였는데 이는 적절한 샘플링을 통해서 더 효율적인 주축 (basis) 을 구할 수 있음을 알 수 있다. 따라서 적절한 샘플을 취함으로써 최대 신호 대 잡음비와 계산 속도 시간 모두 향상시킬 수 있음을 알 수 있다. 그림 2 표 1 에대한 주관적 화질 비교 이다. 다만 l 이 일정 수준을 넘어가면 최대 신호 대 잡음비 크게 감소하며, 감소하는 시점은 영상에 존재하는 잡음 레벨이 커질수록 더 빨라진다. 샘플링 간격에 따른 몇몇 표준 영상에 대한 실험 결과는 그림 3 에 나타나 있다. σ = 10 일 때, 샘플링 간격이 l ≤ 20 경우에는 최대 신호 대 잡음비의 변화가 거의 없지만, l ≥ 50 이 되면 샘플링 간격에 따라 최대 신호 대 잡음비의 변동폭이 심해진다. σ = 25 일 때에도 σ = 10 와 비슷한 양상을 보인다. 다른 점은 최대 신호 대 잡음비의 변동폭이 심해지는 구간 ( l ≥ 35) 이 빨라지는 것을 알 수 있다. σ = 50 이 되면 이 현상이 더욱 더 가속화 된다. 이런 현상들은 획득한 영상에 존재하는 잡음 레벨에 의해 영상의 정보가 왜곡 되면서 주성분 분석에 많은 영상 패치들이 필요하다는 것을 의미한다. 이 실험을 바탕으로 대략적인 최적의 샘플링 간격 l 은 식 (7)과 같이 추정해 볼 수 있다. 보다 일반적으로는 잡음 레벨에 따른 최적의 샘플링 간격 l σ , S , R , h 에 대한 함수 식으로 나타낼 수 있을 것이다.
PPT Slide
Lager Image
샘플 거리에 따른 공분산 행렬 계산 시간와 PSNR 비교Table 1. PSNRs and computation time of the covariance matrix with increasingl
PPT Slide
Lager Image
512×512 Lena, σ = 10, S = 7, R = 13, h = 42, d = 6
PPT Slide
Lager Image
표 1의 주관적 화질 비교 (왼쪽부터 차례대로 l = 1, 16, 64, 128). Fig. 2. Comparison of subject results of the table 1 (From left to right, l = 1, 16, 64, 128).
PPT Slide
Lager Image
잡음 레벨과 샘플 거리에 따른 몇몇 표준 이미지들에 대한 PSNR 결과(S = 7, R = 13, h = 42, 84, 156, d = 6) Fig. 3. PSNRs for several standard images with varying noise level and distance between samples(S = 7, R = 13, h = 42, 84, 156, d = 6)
Ⅵ. 결 론
본 논문에서는 주성분 분석 기반 비 지역적 평균 알고리즘에서 간단한 샘플링 방법을 이용하여 효율적으로 공분산 행렬을 구하는 방법을 소개하였다. 비록 표 1 에서 보듯이 전체 알고리즘에서 공분산 행렬 계산이 차지하는 부분은 전체 알고리즘 수행 시간에 비해 미미하지만, 모바일 환경과 같은 전력 효율이 중요한 환경에서는 작은 부분이라도 개선 시키는 것이 바람직할 것 이다. 또한 계산 시간 이외에도 일정 수준의 잡음 레벨 ( σ ≤ 25) 에서는 적절한 샘플링을 통해서 오히려 최대 신호 대 잡음비가 높아지는 경우도 있음을 실험을 통해서 밝혀졌다. 본 논문을 바탕으로 더 효율적인 공분산 행렬 구하는 방법이 연구되었으면 한다.
BIO
김 정 환
- 2014년 2월 : 한양대학교 융합전자공학부 졸업
- 2014년 3월 ~ 현재 : 한양대학교 전자컴퓨터통신공학과 석사과정
- ORCID : http://orcid.org/0000-0002-9812-7338
- 주관심분야 : 영상처리, 영상압축
정 제 창
- 1980년 2월 : 서울대학교 전자공학과 졸업
- 1982년 2월 : KAIST 전기전자공학과 석사
- 1990년 : 미국 미시간대학 전기공학과 공학박사
- 1980년 ~ 1986년 : KBS 기술연구소 연구원 (디지털 및 뉴미디어 연구)
- 1990년 ~ 1991년 : 미국 미시간대학 전기공학과 연구교수 (영상 및 신호처리 연구)
- 1991년 ~ 1995년 : 삼성전자 멀티미디어 연구소 (MPEG, HDTV, 멀티미디어 연구)
- 1995년 ~ 현재 : 한양대학교 전자컴퓨터통신공학과 교수 (영상통신 및 신호처리 연구실)
- 1998년 11월 : 과학기술자상 수상
- 1990년 12월 : 정보통신부장관상 수상
- 2007년 : IEEE Chester Sall Award 수상
- 2008년 : ETRI Journal Paper Award 수상
- 2011년 5월 : 제46회 발명의 날 녹조근정훈장 수훈
- ORCID : http://orcid.org/0000-0002-3759-3116
- 주관심분야 : 영상처리, 영상압축, 3DTV
References
Buades A. , Coll B. , Morel J.-M. 2005 “A non-local algorithm for image denoising,” CVPR 2 60 - 65
Tasdizen T. 2009 “Principal neighborhood dictionaries for nonlocal means image denoising,” IEEE Trans., Image processing 18 (12) 2649 - 2660    DOI : 10.1109/TIP.2009.2028259
Salmon J. 2010 “On two parameters for denoising with non-local means,” IEEE Signal processing letters 17 (3) 269 - 272    DOI : 10.1109/LSP.2009.2038954
Smith L. I 2002 “A tutorial on principal components analysis,” http://www.cs.otago.ac.nz/cosc453
Tomasi C. , Manduchi R. 1998 “Bilateral filtering for gray and color images,” ICCV 839 - 846
Dabov K. , Foi A. , Katkovnik V. , Egiazarian K. 2007 “Image denoising by sparse 3D transform-domain collaborative filtering,” IEEE Trans., Image processing 16 (8) 2080 - 2095    DOI : 10.1109/TIP.2007.901238
Chang S. G. , Yu B. , Vetterli M. 2000 “Adaptive wavelet thresholding for image denoising and compression,” IEEE Trans. Image processing 9 (9) 1532 - 1546    DOI : 10.1109/83.862633