디지털 영상 처리 - 히스토그램 지정(Histogram Matching)

 안녕하세요. 지난 포스팅의 디지털 영상 처리 - 히스토그램 평활화(Histogram Equalization)에 이어서 조금 더 일반화된 히스토그램 기반 영상 처리 방법인 히스토그램 지정에 대해서 알아보도록 하겠습니다. 

 

 기존의 히스토그램 평활화는 이론적으로 임의의 픽셀 강도 확률 분포를 가지는 입력 영상을 균등확률분포을 가지는 출력 영상으로 변환시키게 된다는 것을 알 수 있었습니다. 여기서 확장하여 균등확률분포가 아니라 저희가 원하는 임의의 확률분포를 가지는 출력 영상으로  변환시킬 수 있지 않을까요? 해당 방법이 바로 히스토그램 지정(Histogram Matching)입니다. 

 

 이전에 히스토그램 평활화를 설명할 때 도입했던 $p_{r}(r), p_{z}(z)$를 다시 한번 사용하도록 하겠습니다. 일단은 두 확률분포 모두 연속적인 PDF라고 가정하도록 하겠습니다. 지난 포스팅에서도 느끼셨겠지만, 대부분의 영상 처리에 관한 이론은 어떤 넓은 개념에서 시작하여 좁은 개념으로 줄이는 방향을 선택하고 있습니다. 지금처럼 연속적인 PDF라고 하였지만 최종적으로 저희는 디지털 영상을 다루고 있기 때문에 이산적인 PMF에 그대로 적용하는 것도 같은 이유입니다. 하여튼, $p_{r}(r)$은 입력 영상에 대한 확률분포이며, $p_{z}(z)$는 출력 영상이 갖게 되기를 원하는 지정된 확률밀도 함수입니다.

 

 이때, $s = T(r) = (L - 1)\int_{0}^{r} p_{r}(w) \; dw$라고 가정하겠습니다. 지난 포스팅을 보시면 아시겠지만 해당 변환은 히스토그램 평활화의 연속 버전입니다. 

 

 그 다음으로 랜덤 변수 $z$가 $G(z) = (L - 1)\int_{0}^{z} p_{z}(t)\; dt = s$를 만족한다고 가정하도록 하겠습니다. 방금의 2가지 가정에 의해서 저희는 $G(z) = s = T(r)$임을 알 수 있으며 역변환이 유일하게 존재한다는 가정하여 아래의 식을 유도할 수 있습니다.

$$z = G^{-1}[T(r)] = G^{-1}(s)$$ 

 

 사실 지금까지 말한 것이 히스토그램 지정의 모든 것입니다. 하지만 뭔가 찜찜합니다. 조금 더 자세히 이를 Step-by-Step으로 진행을 해보도록 하겠습니다. 

 

1. 입력 영상으로부터 $p_{r}(r)$을 얻는다.
2. $s = T(r) = (L - 1)\int_{0}^{r} p_{r}(w) \; dw$로부터 평활화된 출력 영상인 $s$를 얻는다.
3. 미리 정의된 내가 지정하고자 하는 확률분포인 $p_{z}(z)$와 $G(z) = (L - 1)\int_{0}^{z} p_{z}(t) \; dt$를 이용해서 변환 함수 $G(z)$를 얻는다. 즉, $s = G(z)$이다.
4. 유일하게 존재하는 역변환을 통해서 $z = G^{-1}(s)$를 얻는다. 이는 $z$가 $s$로부터 얻어지는 것으로 $s$로부터 $z$로의 매핑(mapping)이라고 볼 수 있다.

 아직 명확하게 이해가 가지 않으신 분들을 위해서 한 가지 예제를 실제로 풀어보도록 하겠습니다. 입력 영상이 $0 \le r \le L - 1$에서는 $p_{r}(r) = \frac{2r}{(L - 1)^{2}}$, 나머지에서는 $p_{r}(r) = 0$을 가진다고 하겠습니다. 그리고 저희가 지정되기를 원하는 확률분포인 $p_{z}(z)$는 $0 \le z \le L - 1$에서는 $p_{z}(z) = \frac{3z^{2}}{(L - 1)^{3}}$, 나머지에서는 $p_{z}(z) = 0$을 가진다고 하겠습니다. 이를 정리하면 아래와 같습니다.

 

• $p_{r}(r) = \begin{cases} \frac{2r}{(L - 1)^{2}} & 0 \le r \le L - 1 \\ 0 & \text{Otherwise} \end{cases}$
• $p_{z}(z) = \begin{cases} \frac{3z^{2}}{(L - 1)^{3}} & 0 \le z \le L - 1 \\ 0 & \text{Otherwise }\end{cases}$

 가장 먼저 진행할 것은 입력 영상에 대한 히스토그램 평활화입니다. 이는 저희가 지난 포스팅에서 자세히 배웠기때문에 해당 단계는 수식으로 대체하도록 하겠습니다. 

 

$$s = T(r) = (L - 1)\int_{0}^{r} p_{r}(w) \; dw \frac{2}{(L - 1)}\int_{0}^{r} w \; dw = \frac{r^{2}}{L - 1}$$

 

 입력 영상에 대한 히스토그램 평활화 변환 함수를찾았다면 그 다음 단계는 $[0, L - 1]$에 대한 $G(z) = (L - 1)\int_{0}^{z} p_{z}(t) \; dt$를 찾아야합니다.

 

$$G(z) = (L - 1)\int_{0}^{z} p_{z}(t) \; dt = \frac{3}{(L - 1)^{2}}\int_{0}^{z} t^{2} \; dt = \frac{z^{3}}{(L - 1)^{2}}$$

 

 마지막으로 $G(z) = s$가 되어야하므로 $G(z) = \frac{z^{3}}{(L - 1)^{2}} = s$이기 때문에 역변환으로 정리하면 $z = \left[(L - 1)^{2}s\right]^{\frac{1}{3}}$을 얻을 수 있습니다. 즉, 히스토그램 평활화된 화소에 $(L - 1)^{2}$를 곱하고 $\frac{1}{3}$승을 취하면 구간 $[0, L - 1]$ 내에서 밝기 $z$가 $p_{z}(z) = \frac{3z^{2}}{(L - 1)^{3}}$인 PDF를 가지는 영상이 될 것입니다. 그리고 저희는 이미 $s = \frac{r^{2}}{L - 1}$임을 알고 있기 때문에 이를 대입하여 정리하면 아래와 같습니다.

 

$$z = \left[(L - 1)^{2}s\right]^{\frac{1}{3}} = \left[(L - 1)^{2}\frac{r^{2}}{(L - 1)}\right]^{\frac{1}{3}} = \left[(L - 1)r^{2}\right]^{\frac{1}{3}}$$

 

 다시 한번 더 정리하면 입력 영상 $r$을 히스토그램 평활화를 하여 평활화된 출력 영상 $s$을 얻습니다. 그 다음으로 저희가 지정하고자 하는 어떤 확률분포 $p_{z}(z)$에 대해서 $s = G(z)$를 계산하여 $r \rightarrow s \rightarrow z$로 감으로서 저희가 지정하고자하는 확률분포를 가지는 출력 영상 $z$를 만들게 되는 것이죠.

 

 하지만, 저희가 원하는 것은 디지털 영상에 대한 히스토그램 지정이기 때문에 이를 이산화하여 표현할 필요가 있습니다. 운이 좋게도 기존의 연속 버전보다 이산 버전의 히스토그램 지정이 더 단순합니다. 왜냐하면 애초에 연속 버전에서는 임의의 분포(불연속이 존재하는 경우)를 가지는 경우에는 더 복잡해지기 때문입니다. 

 

 먼저, 연속 버전에서도 보았다싶이 히스토그램 평활화의 이산 버전을 적용하도록 하겠습니다.

 

$$s_{k} = T(r_{k}) = (L - 1)\sum_{j = 0}^{k} p_{r}(r_{j}) = \frac{(L - 1)}{MN}\sum_{j = 0}^{k} n_{j}$$

 

 그리고 저희 지정하고자 하는 밝기값인 $z_{q}$가 주어져있다고 가정하면 $s_{k}$를 히스토그램 평활화 단계에서 이미 구했기 때문에  $G(z_{q})$를 구하는 공식과 $s_{k}$와의 관계식을 아래와 같이 쓸 수 있습니다.

 

$$G(z_{q}) = (L - 1)\sum_{I = 0}^{q} p_{z}(z_{i}) = s_{k} \Rightarrow z_{q} = G^{-1}(s_{k})$$

 

 이 단계에서 저희는 역변환 $G^{-1}$를 계산해야 성공적인 히스토그램 지정을 할 수 있습니다. 하지만, 실제 구현에서는 그럴 필요 없는 데, 그 이유를 아래의 예제를 보시면 더 명확해지실 것입니다.

 먼저, (a)와 같은 확률분포를 가지는 입력 영상이 있다고 가정하겠습니다. 그리고 저희는 입력 영상이 (b)와 같은 확률분포를 가지도록 만들고 싶다고 하겠습니다. 해당 예제 중 히스토그램 평활화 단계는 이전 포스팅과 완벽하게 일치하기 때문에 결과만 가지고 오도록 하겠습니다. 결과적으로 히스토그램 평활화를 진행하면 $r \rightarrow s$의 매핑은 아래와 같이 진행하면 됩니다. 

 

$k$	$r_{k} = k$	$s_{k} = T(r_{k})$
$k = 0$	$r_{0} = 0$	$s_{0} = T(r_{0}) = 1$
$k = 1$	$r_{1} = 1$	$s_{1} = T(r_{1}) = 3$
$k = 2$	$r_{2} = 2$	$s_{2} = T(r_{2}) = 5$
$k = 3$	$r_{3} = 3$	$s_{3} = T(r_{3}) = 6$
$k = 4$	$r_{4} = 4$	$s_{4} = T(r_{4}) = 6$
$k = 5$	$r_{5} = 5$	$s_{5} = T(r_{5}) = 7$
$k = 6$	$r_{6} = 6$	$s_{6} = T(r_{6}) = 7$
$k = 7$	$r_{7} = 7$	$s_{7} = T(r_{7}) = 7$

또한 저희는 이를 통해 아래와 같은 그림을 얻을 수 있다고 언급하였습니다.

 매핑 테이블까지 저희가 얻었기 때문에 저희가 다음으로 진행해야할 것은 변환 함수 $G$를 얻는 것입니다. 이를 위해서는 미리 정의된 $z_{q}$값에 대한 테이블이 필요합니다. 이는 아래와 같은 테이블로 주어져있다고 가정하고 시작하겠습니다. 가장 오른쪽 열은 실제로 히스토그램 지정 알고리즘을 끝냈을 때 결과이기 때문에 저희는 가운데 열만 보면 됩니다.

 

$$G(z_{0}) = 7\sum_{j = 0}^{0} p_{z}(z_{j}) = 7p_{z}(z_{0}) = 0.00$$

$$G(z_{1}) = 7\sum_{j = 0}^{1} p_{z}(z_{j}) = 7(p_{z}(z_{0}) + p_{z}(z_{1})) = 0.00$$

$$G(z_{2}) = 7\sum_{j = 0}^{2} p_{z}(z_{j}) = 7(p_{z}(z_{0}) + p_{z}(z_{1}) + p_{z}(z_{2})) = 0.00$$

$$G(z_{3}) = 7\sum_{j = 0}^{3} p_{z}(z_{j}) = 7(p_{z}(z_{0}) + p_{z}(z_{1}) + p_{z}(z_{2}) + p_{z}(z_{3})) = 1.05$$

$$G(z_{4}) = 7\sum_{j = 0}^{4} p_{z}(z_{j}) = 7(p_{z}(z_{0}) + p_{z}(z_{1}) + p_{z}(z_{2}) + p_{z}(z_{3}) + p_{z}(z_{4})) = 2.45$$

$$G(z_{5}) = 7\sum_{j = 0}^{5} p_{z}(z_{j}) = 7(p_{z}(z_{0}) + p_{z}(z_{1}) + p_{z}(z_{2}) + p_{z}(z_{3}) + p_{z}(z_{4}) + p_{z}(z_{5})) = 4.55$$

$$G(z_{6}) = 7\sum_{j = 0}^{5} p_{z}(z_{j}) = 7(p_{z}(z_{0}) + p_{z}(z_{1}) + p_{z}(z_{2}) + p_{z}(z_{3}) + p_{z}(z_{4}) + p_{z}(z_{5}) + p_{z}(z_{6})) = 5.95$$

$$G(z_{7}) = 7\sum_{j = 0}^{5} p_{z}(z_{j}) = 7(p_{z}(z_{0}) + p_{z}(z_{1}) + p_{z}(z_{2}) + p_{z}(z_{3}) + p_{z}(z_{4}) + p_{z}(z_{5}) + p_{z}(z_{6}) + p_{z}(z_{7})) = 7.00$$

 

 하지만 저희는 현재 디지털 영상을 다루고 있기 때문에 각 결과를 반올림하여 정수로 만들어줍니다. 

 

$$G(z_{0}) = G(z_{1}) = G(z_{2}) = 0$$

$$G(z_{3}) = 1, G(z_{4}) = 2, G(z_{5}) = 5, G(z_{6}) = 6, G(z_{7}) = 7$$

 

 이를 테이블로 정리하면 아래와 같습니다.

 하지만 현재 큰 문제가 생겼습니다. 바로 변환 $G$가 엄밀 단조 증가 함수가 아니라는 점이죠. 엄밀 단조 증가 함수가 아니기 때문에 역변환 함수가 유일하지 않으며 이는 모호성에 대한 문제로 발전하게 됩니다. 따라서 이를 처리하는 새로운 방법이 필요합니다. 이를 위해서 제안하는 방법은 값 $G(z_{q})$가 $s_{k}$에 가장 가깝게 만드는 가장 작은 $z_{q}$값을 찾아야합니다. 이를 모든 $s_{k}$에 반복하여 $s \rightarrow z$로의 필요한 매핑 테이블을 구성합니다. 예를 들어서, 히스토그램 평활화 테이블에 의해서 $s_{0} = 1$입니다. 그리고 해당 값과 가장 가까운 $z_{q}$는 $G(z_{3}) = 1$ 입니다. 따라서, 매핑 테이블을 구성할 때, $s_{0} \rightarrow z_{3}$으로의 매핑을 시키면 됩니다. 즉, 평활화된 영상 내에 밝기 값이 1인 모든 픽셀들은 히스토그램 지정된 영상 내에 밝기값이 3으로 매핑될 것입니다. 이를 각 $s_{k}$에 대해서 적용해보도록 하겠습니다. 

 

$$s_{1} = 3 \approx G(z_{4}) \Rightarrow s_{1} \rightarrow z_{4}$$

$$s_{2} = 5 = G(z_{5}) \Rightarrow s_{2} \rightarrow z_{5}$$

$$s_{3} = 6 = G(z_{6}) \Rightarrow s_{3} \rightarrow z_{6}$$

$$s_{4} = 6 = G(z_{6}) \Rightarrow s_{4} \rightarrow z_{6}$$

$$s_{5} = 7 = G(z_{7}) \Rightarrow s_{5} \rightarrow z_{7}$$

$$s_{6} = 7 = G(z_{7}) \Rightarrow s_{6} \rightarrow z_{7}$$

$$s_{7} = 7 = G(z_{7}) \Rightarrow s_{7} \rightarrow z_{7}$$

 

 이를 테이블로 정리하면 아래와 같습니다.

 위와 같은 알고리즘을 이용해서 매칭을 수행하면 모호성 문제를 방지할 수 있습니다. 마지막으로 이를 이용해서 최종 매핑 테이블을 구성해보도록 하겠습니다. 총 4개의 매핑 테이블을 활용합니다. 먼저 2개는 이전 포스팅의 $r \rightarrow s$로의 변환을 위한 테이블이고 남은 2개는 상단의 $s \rightarrow z$로의 역변환 테이블과 이를 확률 분포로 나타내기 위한 테이블이 필요합니다. 

 

<$r \rightarrow s$ Table>

$k$	$r_{k} = k$	$s_{k} = T(r_{k})$
$k = 0$	$r_{0} = 0$	$s_{0} = T(r_{0}) = 1$
$k = 1$	$r_{1} = 1$	$s_{1} = T(r_{1}) = 3$
$k = 2$	$r_{2} = 2$	$s_{2} = T(r_{2}) = 5$
$k = 3$	$r_{3} = 3$	$s_{3} = T(r_{3}) = 6$
$k = 4$	$r_{4} = 4$	$s_{4} = T(r_{4}) = 6$
$k = 5$	$r_{5} = 5$	$s_{5} = T(r_{5}) = 7$
$k = 6$	$r_{6} = 6$	$s_{6} = T(r_{6}) = 7$
$k = 7$	$r_{7} = 7$	$s_{7} = T(r_{7}) = 7$

<$s$ Table>

$k$	$s_{k} = k$	$n_{s_{k}}$	$p_{s}(s_{k})=\frac{n_{s_{k}}}{MN}$
$k = 0$	$s_{0} = 0$	$n_{s_{0}} = 0$	$p_{s}(s_{0})=\frac{n_{s_{0}}}{4096} = 0$
$k = 1$	$s_{1} = 1$	$n_{s_{1}} = n_{0} = 790$	$p_{s}(s_{1})=\frac{n_{s_{1}}}{4096} = 0.19$
$k = 2$	$s_{2} = 2$	$n_{s_{2}}  = 0$	$p_{s}(s_{2})=\frac{n_{s_{2}}}{4096} = 0$
$k = 3$	$s_{3} = 3$	$n_{s_{3}} = n_{1} = 1023$	$p_{s}(s_{3})=\frac{n_{s_{3}}}{4096} = 0.25$
$k = 4$	$s_{4} = 4$	$n_{s_{4}} = 0$	$p_{s}(s_{4})=\frac{n_{s_{4}}}{4096} = 0$
$k = 5$	$s_{5} = 5$	$n_{s_{5}} = n_{2} = 850$	$p_{s}(s_{5})=\frac{n_{s_{5}}}{4096} = 0.21$
$k = 6$	$s_{6} = 6$	$n_{s_{6}} = n_{3} + n_{4} = 985$	$p_{s}(s_{6})=\frac{n_{s_{6}}}{4096} = 0.24$
$k = 7$	$s_{7} = 7$	$n_{s_{7}} = n_{5} + n_{6} + n_{7} = 448$	$p_{s}(s_{6})=\frac{n_{s_{7}}}{4096} = 0.11$

<$s \rightarrow z$ Table>

 

$k$	$s_{k} = k$	$z_{q}$
$k = 0$	$s_{0} = 0$	없음
$k = 1$	$s_{1} = 1$	$z_{3}$
$k = 2$	$s_{2} = 2$	없음
$k = 3$	$s_{3} = 3$	$z_{4}$
$k = 4$	$s_{4} = 4$	없음
$k = 5$	$s_{5} = 5$	$z_{5}$
$k = 6$	$s_{6} = 6$	$z_{6}$
$k = 7$	$s_{7} = 7$	$z_{7}$

<$z$ Table>

$q$	$z_{q} = q$	$n_{z_{q}}$	$p_{z}(z_{q})=\frac{n_{z_{q}}}{MN}$
$q = 0$	$z_{0} = 0$	$n_{z_{0}} = 0$	$p_{z}(z_{0})=\frac{n_{z_{0}}}{4096} = 0$
$q = 1$	$z_{1} = 1$	$n_{z_{1}} = 0$	$p_{z}(z_{1})=\frac{n_{z_{1}}}{4096} = 0$
$q = 2$	$z_{2} = 2$	$n_{z_{2}} = 0$	$p_{z}(z_{2})=\frac{n_{z_{2}}}{4096} = 0$
$q = 3$	$z_{3} = 3$	$n_{z_{3}} = n_{s_{1}} = 790$	$p_{z}(z_{3})=\frac{n_{z_{3}}}{4096} = 0.19$
$q = 4$	$z_{4} = 4$	$n_{z_{4}} = n_{s_{3}} = 1023$	$p_{z}(z_{4})=\frac{n_{z_{4}}}{4096} = 0.25$
$q = 5$	$z_{5} = 5$	$n_{z_{5}} = n_{s_{5}} = 850$	$p_{z}(z_{5})=\frac{n_{z_{5}}}{4096} = 0.21$
$q = 6$	$z_{6} = 6$	$n_{z_{6}} = n_{s_{6}} = 985$	$p_{z}(z_{6})=\frac{n_{z_{6}}}{4096} = 0.24$
$q = 7$	$z_{7} = 7$	$n_{z_{7}} = n_{s_{7}} = 448$	$p_{z}(z_{7})=\frac{n_{z_{7}}}{4096} = 0.11$

 

 이와 같이 계산한 결과를 아래의 원래 정의된 $z_{q}$와 실제로 계산된 $z_{q}$를 비교해보도록 하겠습니다. 약간 다르긴 하지만 그래도 나름 유사한 것을 관찰할 수 있습니다.

이제 실제 응용된 영상을 보도록 하겠습니다. 

상단의 (a)와 같이 전체적으로 어두운 영상이 있습니다. 이를 히스토그램으로 변환하면 (b)와 같이 전체적으로 0에 대부분 분포되어 있음을 알 수 있습니다. 이제 이 영상의 대비를 늘리기 위해서 히스토그램 평활화를 적용해보도록 하겠습니다. 

상단의 (a)는 히스토그램 평활화 변환 함수 $T$를 그래프로 나타낸 것입니다. 히스토그램 평활화를 진행했음에도 불구하고 (b), (c)를 보면 회색조가 강한 영상이 되었습니다. 이러한 문제가 발생하는 이유는 0에 너무 많이 쏠려서 애초에 히스토그램 평활화를 하더라도 이상한 영상이 나오게 됩니다. 이를 방지하기 위해서 어떤 확률 분포를 가지도록 하는 히스토그램 매칭이 효과적으로 쓰일 수 있습니다. 예시에서는 수동으로 지정된 분포로써 이를 이용하여 변환을 수행하도록 하겠습니다.

 상단에서 (a)는 수동으로 지정한 $p_{z}(z)$를 의미합니다. 그리고 (b)의 (1)번 함수는 $G(z)$, (2)번 함수는 $G^{-1}(s)$를 의미합니다. 히스토그램 지정 알고리즘에서는 (1)을 구한 뒤 역변환 함수인 (2)를 이용해서 $s \rightarrow z$로 변환했던 것을 기억하실겁니다. 그 결과 기존의 영상과 비교했을 때 어두웠던 영상이 전체적으로 밝아졌으며 (d)의 히스토그램을 보면 단순한 히스토그램 평활화 알고리즘에 비해서 그레이 스케일이 더 밝은 영역을 향해서 오른쪽으로 이동되었다는 것을 관찰할 수 있었습니다.