본 논문에서는 영상에 존재하는 잡음 (noise) 들을 제거하는 방법 중 하나인 비 지역적 평균 (non-local means, NLM) 알고리즘을 먼저 소개하고 비 지역적 평균 알고리즘의 개선된 방법 중 하나인 주성분 분석 (principal component analysis, PCA) 기반의 알고리즘에 대해서도 소개한다. 주성분 분석을 활용하기 위해서는 선행적으로 공분산 행렬 (covariance matrix)을 구해야 하는데, 영상의 모든 픽셀들을 대상으로 하였을 때 이 공분산 행렬을 구하기 위해서는 큰 크기를 가지는 행렬 곱 연산이 필요하다. 만약 비 지역적 평균 알고리즘의 영상 패치 (neighborhood patch) 의 크기를 S × S = S ² , 영상 전체의 픽셀 수를 Q 라고 한다면 공분산 행렬을 구하기 위해서는 S ² × Q 크기의 행렬 곱 연산이 필요하게 된다. 이는 영상의 특성을 고려하면 비효율적인 연산이다. 따라서 본 논문에서는 공분산 행렬을 효율적으로 구하기 위해, 영상 패치들간의 일정 간격을 유지하면서 샘플링을 하는 방법을 제안하고자 한다. 최종적으로, 샘플링 후에는 S ² × floor ( Width / l ) × ( Height / l ) 크기를 가진 행렬의 곱 연산으로 공분산 행렬을 구할 수 있다. 카메라를 이용하여 이미지를 획득하게 되면, 취득한 영상에는 일반적으로 잡음(noise) 도 같이 따라오기 마련이다. 이런 영상에서 잡음을 제거하는 기법을 디노이징 (denoising) 이라고 하며 영상처리 분야에서 지금까지 가장 많이 연구되어 온 분야이다. 그 중 ‘비 지역적 평균(non-local means, NLM)’ 알고리즘은 다른 알고리즘들 [5] [6] [7] 에 비해 비교적 쉬운 구현에 비해 뛰어난 성능을 가지고 있어서 가장 많이 사용되는 디노이징기법중 하나이다. 비지역적 평균 알고리즘은 다른 디노이징 기법과 마찬가지로 이미지의 특성인 한 픽셀(pixel) 과 주변 픽셀들이 비슷하다는 특성을 이용하여 잡음을 제거하는데, 따라서 잡음을 제거하기 위해서 비 지역적 평균 알고리즘은 영상의 모든 픽셀들을 처리해야 하고, 그만큼 영상의 해상도가 커질수록 계산 복잡도가 커지게 된다. 이런 비 지역적 평균 알고리즘의 복잡도를 줄이기 위한 방법중 하나로 주성분 분석 (principal component analysis, PCA)을 이용하여 알고리즘의 계산 량을 줄이는 방법이 있는데, PCA를 이용하기 위해서는 필수적으로 공분산 행렬 (covariance matrix) 계산이먼저수행되어야한다. 본 논문에서는 이 공분산 행렬 계산을 효과적으로 하는 방법을 제안하고자 한다. 본 논문은 다음과 같이 구성되어 있다. 2장에서는 비 지역적 평균 알고리즘을 소개하고, 이어서 주성분 분석을 활용한 수정된 비 지역적 평균 알고리즘을 소개한다. 4장에서는 공분산 행렬을 효과적으로 계산하는 방법을 제안하고, 마지막으로 5장에서는 실험을 통하여 제안한 알고리즘의 성능을 보여준다. 잡음에 의해서 오염된 영상 (관측된 영상) v ( i )는 다음과 같이 수학적으로 모델링을 할 수 있다. 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 )를 추정하게 된다. 비 지역적 평균 알고리즘의 정의는 다음과 같다. N _i 는픽셀 i 를 중심으로 S × S 크기를가지는영상패치, Ω _i 는 픽셀 i 를 중심으로 R × R 크기 안에 들어오는 픽셀들의 집합 (searching window), 는 원본 영상의 추정치, 는 정규화 (normalization)항이다. h 는 는 가중 평균 합을 조절하는 사용자 매개변수(parameter) 이다. h 값에 따라 디노이징 결과의 큰 영향을 주기 때문에 상황에 맞는 적절한 값이 필요하다. [1] 에서는 만약 백색 가우시안 잡음의 분산 값 σ ² 을 알 수 있다면, 대략적으로 h =10 × σ 을 정의했으나, 다른 연구에 의하면 [2] 최대 신호 대 잡음비 (peak signal-to-noise ratio, PSNR) 관점에서 보다 더 좋은 결과를 얻기 위해서는 다른 선택이 필요하다는 것을 알 수 있다. 비 지역적 평균 알고리즘의 복잡도는 O ( Q × S ² × R ² ) 이다. 조절 불가능한 전체 픽셀 개수 Q 를 제외하면 비 지역적 평균 알고리즘 알고리즘의 복잡도는 S 와 R 의 영향을 받게 된다. 처음 비 지역적 평균 알고리즘 알고리즘을 제안한 [1] 에서는 영상의 모든 픽셀들을 대상으로 알고리즘을 수행하지만 알고리즘의 복잡도를 위하여 R 을 제한하는 것이 일반적이다. 언뜻 보기에는 R 이 클수록 높은 최대 신호 대 잡음비를 얻을 수 있을 것 같지만, [3] 에 의하면 비슷한 패턴의 반복으로 이루어진 이미지와 같은 몇몇 예외를 제외하면, R ≥ 15 인 경우에는 오히려 최대 신호대 잡음비가 감소한다고 한다. S 는 R 보다 결과값에 영향을 덜 미치는 매개변수로 주로 5 ≤ S ≤ 9를 선택한다 [3] . 여전히 비 지역적 평균 알고리즘의 복잡도에서 가장 큰 영향을 주는 Q 를 조절할 수 없기에, 큰 영상의 경우에는 많은 알고리즘 수행시간이 필요하다. [2] 는 기존의 두 이미지 패치의 L ² 거리를 계산하는 대신에, 주성분 분석 [4] 를 이용하여 패치의 차원 (dimensions) 을 낮춰서 L ² 거리를 계산함으로써 비 지역적 평균 알고리즘의 복잡도를 줄이면서 더 좋은 결과를 얻을 수 있다고 한다. 먼저 주 성분 분석을 활용하기 위해서 영상 패치들의 공분산 행렬을 계산해야 한다. 행렬 M ∈ R ^S2×Q 을 다음과 같이 정의하자. p_i ( k ), i = {1, 2, ⋯, Q }, k = {1, 2, ⋯, S ² }는 한 영상 패치를 열 벡터 (column vector)로 나타낸 것이며, 는 벡터 p_i 의 평균 값이다. 따라서 공분산 행렬 C ∈ R ^S2×S2 는 다음과 같이 정의 된다. 공분산행렬 C의고유값(eigenvalues)을구하고고유값의 크기를기준으로고유벡터(eigenvectors) { w_d : 1 ≤ d ≤ S ² }를 내림차순으로 정렬한다. 이 고유 벡터들을 이용하여 S ₂ 차원을 가진 기존의 영상 패치 N _i 를 d 차원으로 축소함으로써 비 지역적 평균 알고리즘의 복잡도를 줄일 수 있게 된다. 최종적으로 수정된 비 지역적 평균 (principal neighborhood dictionary non-local means, PND NLM) [2] 알고리즘의 정의는 다음과 같다. v_d (N _i )는 차원이 축소되어 d 차원을 가진 이미지 패치이며, 이다. 주 성분 기반 비 지역적 평균 알고리즘의 복잡도는 O ( Q × d × R ² )가 되며, d = S ² 인 경우에는 기존의 알고리즘과 동일하다. 앞서 보듯이, 영상의 모든 패치들을 대상으로 공분산 행렬 계산을 하기 위해서는 매우 큰 차원을 가진 행렬 곱 연산이 수행되어야 한다. 하지만 영상 특성상 이웃한 패치들은 매우 비슷하기 때문에 모든 패치를 대상으로 공분산 행렬을 구하는 것은 비효율적이다. [2] 에서는 전체 샘플 개수의 10% 의 샘플을 가지고 공분산 행렬 계산을 하는 것이 효율적이라고 언급이 되어 있으나 구체적으로 어떻게 샘플링을 하는지, 샘플 개수에 따른 알고리즘의 성능의 변화는 설명되어 있지 않다. 따라서 본 논문에서는 구체적인 샘플링 방법과 샘플링에 따른 성능을 비교해보고자 한다. 샘플링 방법은 다음과 같다. 그림 1 과 같이 일정 간격 l ∈ Z 을 유지하면서 픽셀을 샘플링을 한다. 즉, l = 1인 경우에는 공분산 행렬 계산에 모든 영상 패치들을 고려하는 것이며, l ≥ 2인 경우에는 샘플링을 하여 행렬 M의 차원이 다음과 같이 줄어들게 된다. 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 에 대한 함수 식으로 나타낼 수 있을 것이다. 본 논문에서는 주성분 분석 기반 비 지역적 평균 알고리즘에서 간단한 샘플링 방법을 이용하여 효율적으로 공분산 행렬을 구하는 방법을 소개하였다. 비록 표 1 에서 보듯이 전체 알고리즘에서 공분산 행렬 계산이 차지하는 부분은 전체 알고리즘 수행 시간에 비해 미미하지만, 모바일 환경과 같은 전력 효율이 중요한 환경에서는 작은 부분이라도 개선 시키는 것이 바람직할 것 이다. 또한 계산 시간 이외에도 일정 수준의 잡음 레벨 ( σ ≤ 25) 에서는 적절한 샘플링을 통해서 오히려 최대 신호 대 잡음비가 높아지는 경우도 있음을 실험을 통해서 밝혀졌다. 본 논문을 바탕으로 더 효율적인 공분산 행렬 구하는 방법이 연구되었으면 한다. 김 정 환 - 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