1. Histogram Processing
이미지 중 Intensity r_k의 개수 n_k를 histogram function h로 나타낸 것을 다음과 같이 나타낸다.
이를 정규화 한 것을 다음과 같이 표현한다.
이처럼 히스토그램으로 나타내면 복잡한 연산 없이, hisgoram-based techniques를 적용하여 빠르고 적합한 implementation이 가능하다. 이러한 장점때문에 real-time image processing으로 자주 쓰인다고 한다. 어떤것이 어떻게 쓰이는지 알아보자.
히스토그램의 모형은 이미지의 외형에 따라 결정된다. 만약 검정색이 지배적이면 히스토그램의 대부분이 낮은 곳에 집중적으로 분포되고 만약 경계가 뚜렷한(contrast가 높은) 이미지라면 히스토그램이 모든 히스토그램이 균일하게 도출될 것이다.
왜 균일하게, 넓게 분포되어있으면 contrast가 높을까? 왜냐하면 gray tone이 다양하고, intensity의 범위가 넓게 분포되면 두 물체의 intensity차이가 많아져 대비가 뚜렷해지기 때문이다. 여기에서 목표는 이러한 히스토그램의 특징을 바탕으로, input image의 히스토그램을 변형하여 원하는 효과를 얻는 것이다. 이걸 어떻게하는지 알아보자.
1-1. Histogram equalization
이 키워드는 현재 Histogram을 나타내는 Pr의 CDF를 나타내고자 하는 Histogram Pz의 CDF로 변환하는 것이다. (r -> T(r) 즉, s -> G-1(s) -> z / 여기서 T는 r의 CDF함수, G는 z의 CDF)
histogram 변형을 위해 input intensity인 r을 output intensity인 s로 변형해주는 연속 함수 T가 다음과 같이 정의되어 있다고 가정하자.
그렇다면 T(r)을 정의하기 위해서는 몇가지 조건이 충족되어야 한다.
1. T(r)이 단조 증가 함수여야 한다.
2. 0 <= r <= L-1인 입력 r에 대해 0 <= T(r) <= L-1를 띄어야 한다.
3. Inverse가 존재해야 한다 (즉, strictly monotonic increasing function이어야 한다)
다음은 세번째 조건에 대한 이미지이다.
Inverse가 존재한다는 것은 output이 input과 1대1로 매칭되어야 함을 의미한다. 따라서 단조함수로는 부족하여 3과 같은 조건이 붙게 된 것이다.
이제 저 조건들을 만족하면서 히스토그램을 평탄화해줄 T를 알아보자.
s = T(r)인 관계에서 입력의 PDF인 Pr과 출력의 PDF/인 Ps가 있고, T가 모든 영역에 대해 연속함수이며 미분 가능할 때 다음이 성립한다.
여기에 히스토그램 평탄화를 위한 함수(A transformation function of particular importance in image processing)인 T(r)의 정의로 나타낸다. 이는 임의의 변수 r에 대한 Cumulative distribution function(CDF)로, 더미 변수읜 w에 대해 Pr(w)이 언제나 참이므로, CDF인 T(r)또한 언제나 단조함수이다. 또한, PDF의 전체 영역에 대한 합은 1이므로 (L-1)을 곱해주면 범위에 대한 조건도 만족한다. 이를 식으로 나타내면,
이다. 이제 T(r)이 정의되었으니, dr/ds를 정의해보자. dr/ds는 ds/dr의 역수이고, ds는 dT(r)인데, 이를 식으로 푼 이후 여기에 Leibniz's rule에 의해 미분과 적분을 함께 소거하면, ds/dr를 구할 수 있다.
이를 바탕으로 Ps를 나타내면,
모든 영역에 대해 Ps가 1/L-1임이 증명된다. 이는 Ps에 독립적인 결과로, 어떠한 Ps가 오더라도 A transformation function of particular importance in image processing로 Transformation한다면 모든 영역의 Ps가 평탄화 됨을 확인할 수 있었다.
이러한 transformation을 통해 분포를 평탄화 할 수 있었다.
하지만 우리가 평탄화 하고자 하는 것은 Discrete한 Histogram이므로 이에 대한 변형을 거쳐야 한다. PDF였던 Pr을 확률로 나타내면 다음과 같다.
또한, CDF로 나타냈던 A transformation function of particular importance in image processing또한 Discrete하게 나타내면,
이다. 이 Transformation을 거치고 Round한 결과 값을 사용하면 Continuous했을 때 처럼 증명이 가능하진 않지만, 충분히 이미지의 Histogram 분포를 평탄화 할 수 있다. 이를 Histogram equalization 혹은 Histogram linearization transformation이라고 부른다.
이를 직관적으로 이해하자면, 실제 들쭉날쭉하던 분포에서 분포가 별로 없는 (즉 Pr이 작은) 연속된 히스토그램은 서로 묶고 (왜냐하면 매우 작은 값들이 더해지면 Histogram의 축척값인 Sk값의 반올림이 변하지 않으므로) 분포가 매우 많은 (즉 Pr이 매우 큰)히스토그램 사이를 명확히 구분시켜 주는(왜냐하면 Histogram의 축척값인 Sk가 급증하므로) 효과를 갖는다. 이를 예시로 보면,
이러한 결과를 확인할 수 있다. 분포가 큰 0, 1, 2, 3에서 Sk값이 급변하므로 Ps의 1, 3, 5, 6으로 바로 매핑됨을 확인할 수 있고, 분포가 작은 rk = 4, 5, 6, 7은 다른 히스토그램에 붙어 히스토그램의 평탄화를 이룸을 확인할 수 있다.
1-2. Histogram matching (specification)
이전에서는 uniform한 histogram을 자동으로 만들고자 했었다 하지만 이것이 적합하지 않은 application이 존재하고, 어떠한 application에서는 특정한 histogram의 분포를 유도해야할 필요성이 있었다. 이럴때 특정 Histogram과 같이 입력 이미지의 Histogram을 변형해주는 테크닉인 Histogram matching(혹은 Histogram specification)을 사용한다.
여기서도 Continuous한 경우에 대해 먼저 살펴보고 증명해보자.
Pr(r)을 입력 이미지에서 intensity r에 대한 확률을 표현하는 PDF으로, Pz(z)를 매칭하고자 하는 특정 PDF라고 하자. 쉽게 말하자면 Pr의 CDF와 Pz의 CDF를 동일하게 만드는 것이다. 이를 다음과 같이 표현해보자.
이제 r으로 z로 매핑하기 위해서, r으로 z를 구하는 식을 G의 역함수와 T(r)로 만들면,
이다. r -> T(r) 즉, s -> G-1(s) -> z로 하여 Pz가 내포하는 Hisogram으로 변환할 수 있는 것이다. 다만 Continuous한 G에서 inverse를 구하기는 쉽지 않지만 Discrete한 영역에서는 0~L-1을 직접 대입하고 찾으면 되기 때문에 문제가 되지 않는다.
이제 Discrete한 Hisogram에서의 변환에 대해 알아보자. Hisogram equalization에서와 같이 PDF를 Histogram의 합으로 나타내고
변환하고자 하는 히스토그램 또한 동일하게 나타내고,
G의 역함수를 취하여 rk가 변환될 output을 구한다.
여기서 Inverse가 존재한다는 의미는 변환하고자 하는 Histogram인 Pz에 0이 존재해서는 안된다는 것을 의미한다.
1-3. Histogram equalization과 Histogram specification의 비교
왜 Specification을 사용하는걸까? 다음 예시를 확인해보자.
한쪽에 몰려있기 때문에 이에 대한 Equalization의 결과는
이렇다. Pr의 연속합을 나타내다가, 첫 P0의 개수가 너무 많아 처음부터 높은 T값을 가지다보니 매핑되는 값 자체가 높아져서 표현되는 색 자체가 높아져버린다. 그렇기 때문에, 이러한 이미지의 특성을 이용하여 가장 낮은 Intensity에 많은 값을 두고 나머지 부분에서 평탄화 하는 Histogram에 specification한다.
훨씬 더 디테일하고, 평탄한 히스토그램을 도출한다.
1-4. Local histogram processing
지금까지는 모두 전체 이미지의 분포로 Histogram을 조작하였다. 이는 overall enhancement에 적합하지만, 목적이 특정 작은 영역에 대한 디테일 향상이라면 적합하지 않다. 그렇기 때문에 이는 갱신하고자 하는 픽셀의 주위 intensity distiribution을 이용하여 값을 갱신하는 것이다. 그리고 그 픽셀을 이동시키면서 분포를 갱신하고, 값을 바꾸는 것이다. 이에 대한 실험적 결과는 다음과 같다
1-5. Histogram Statistic을 이용한 Image enhancement
전체 Image의 평균과 분산을 구하고 변환하고자 하는 점을 중심으로하는 슬라이드 내의 평균과 분산을 다음과 같이 구한다.
그리고, 전체 이미지의 특성과 부분 이미지의 특성을 비교하며 그 슬라이딩이 변환하고자 하는 특성을 내포하는지 확인하고, 만약 내포한다면 Intensity를 변환한다
이를 예를 들어 확인해보자.
만약 내가 원하는 것이 "어두운 영역 내의, 대비가 매우 작은 패턴을 밝게하여 돋보이게 한다"라면, k0와 k1을 작게 (즉 평균보다 Intensity가 적게, 즉 어둡게)하고, k2와 k3를 적게 (즉, 평균보다 분산이 적게, 즉 대비가 적게)설정하여 변환하고자 하는 패턴을 명시하고, C를 높게하여 밝은 값으로 변환되게 한다.
2. Fundamentals of spatial filtering
convolution은 correlation을 180도 뒤집은 것이다. 이는 중앙의 값 하나만 1이고 나머지가 0인 discrete Unit impulse에다가 correlation을 시행해주면 convolution이 된다. 이 impulse는 Lineary system theory의 fundamental이며, Discrete impulse of strength(amplitude)는 중간에 들어갈 값을 의미하고 떨어진 위치와 함께 다음과 같이 나타낸다.
correlation의 연산을 다음과 같이 표현한다고 하자.
convolution은 이를 180도로 돌린것과 같기 때문에 이를 수식으로 나타내면,
이러한 연산들이 내적에 합이기 때문에 linear spatial filtering이라고 불리고, spatial convolution과 동의어를 이루기도 한다. filter의 중심이 모든 이미지의 픽셀을 지난다고 가정할 때
와 같이 간소화 한다. (이때 padding엔 m(filter의 width/2)-1만큼씩 되어야 한다고 한다.)
correlation으로 convolution과 같은 결과를 나타낼 수 있지만(커널을 180도 돌리면) 이 교환법칙과 결합법칙을 만족하지 않아, 연산의 순서가 바뀌면 결과에 차이를 만들기 때문에 이에 조심해야 한다.
왜 이게 성립하는지는 아래 추가자료를 확인하면 쉽게 이해가 된다.
2-1. Separable filter kernel
2D convolution을 연산하는 것 보다 2D convolution을 2개의 1D convolution으로 분해하여 나타내어 연산하면 연산량이 적어진다는 것이다. 예를들어 아래의 kernel이 존재한다고 가정해보자
이는 다음과 같이 분배될 수 있다.
이러한 계산적 장점은 convolution의 교환법칙과 결합법칙의 성립 때문이다.
만약 맨 왼쪽처럼 연산한다면 MNmn의 연산량이 나타나는데, 맨 오른쪽 처럼 연산한다면 MN(m+n)의 연산량만 나온다. 이는 당연한데, 한 원소당 mn의 연산했던 전자와 다르게, 후자는 한번은 m번 이어서 n번 하여 m + n연산을 하기 때문이다.
이렇게 분배하는 법에 대해서 알아보자. 0이 아닌 원소 값 E를 가지고, 동일 형태 Vector c와 r을 만든다. 그리고 각각 E를 한곳에 포함시킨다. 그리고 분배 식에 따라 v=c / 그리고 w = r/E로 나타낸다.
2-2. Comparison between filtering in the spatial and frequency domains
image domain의 transformation과 frequency domain의 fourier transform의 비교이다. 이 두개는 서로 밀접한 연관이 있다. image domain의 특정 transformation을 위해 frequency domain으로 투영하고, fourier transform을 거친 후 frequency domain의 역투영을 하는 것으로 대체할 수 있다. 이것의 중요한 점은 특정 frequency band를 이미지의 특성과 연관지을 수 있다는 것이다. 예를 들어 edge와 같이 값이 급변하는 곳에서는 frequency가 높을 것이고, 이러한 점의 특징은 spatial domain에서 intensity의 변화가 클 것이다.
이러한 특징을 이용해 frequency domain에서 높은 frequency component를 줄이면 spatial dojmain에서 blur효과를 가져올 것이다. 이처럼 linear filtering을 위해 spatial domain에서는 convolution filtering을, frequency domain에서는 multiplicative filter를 시행한다. 위에