클러스터링 알고리즘을 이용한 효과적인 그림자 영역 검출 방법

Ⅰ. 서 론

그림자(shadow)는 광원(light)과 객체(object) 간의 상호작용으로 생성되는 자연 현상으로 광원이 존재하는 곳에서 흔하게 발견할 수 있다. 또한, 그림자는 디지털 영상에서 객체의 구조, 광원의 위치, 빛의 강도 등의 유용한 정보를 제공할 수 있다. 하지만, 그림자는 영상 속 일부 표면에 색상과 강도의 변화를 초래하여 객체 인식, 객체 추적 및 객체 분할 등의 영상처리 분야에서 부정적인 영향을 미쳐 알고리즘의 실패를 초래할 수 있다. 따라서, 이러한 영상처리 알고리즘의 성능 저하를 회피하기 위해서는 그림자 영역의 검출과 제거는 전처리 과정에서 필수적으로 진행되어야 한다[1][2].

그림자 검출 연구는 다양하게 진행 중이며, 최근에 딥러닝의 성능 및 관심이 증가함에 따라 딥러닝 기반의 그림자 검출 기법의 연구가 활발히 진행 중이다. 초기 연구들로는 대부분 영상의 색도(chromaticity) 또는 조도 불변(illumination invariant) 등의 색을 기반으로 한 물리적 모델을 이용하였지만, 고품질의 영상에서만 효과적으로 검출된다는 단점이 있었다. 이를 해결하기 위하여 에지(edge)와 픽셀(pixel) 정보를 기반으로 한 질감(texture), 기울기(gradient), 강도(intensity), 영역확장(region growing), 분류기(classification) 등의 다양한 검출 방법들이 제안되었다[3][4].

본 논문에서는 단일 자연 영상 내부의 그림자 영역과 그림자가 아닌 영역(non-shadow region)의 구분을 위하여 SLIC(simple linear iterative clustering)과 k-mean++ 알고리즘을 이용하여 픽셀들을 비슷한 특성끼리 묶어 단순하면서도 속도가 빠른 기계학습 방법을 적용하였다[5][6]. 또한, 참조(reference) 영상을 사용하지 않는 단일 자연 영상에서의 그림자 검출에 초점을 두었으며, 이를 효과적으로 검출하는 방법에 관하여 기술하였다.

본 논문의 구성으로는 2장에서 그림자 검출을 위해 적용된 SLIC과 k-mean++ 알고리즘을 서술하였으며, 3장에서 제안하는 그림자 검출 방법을 기술하였다. 4장에서 실험 및 고찰을 수행하고, 5장에서 결론 및 향후 연구에 관하여 기술한다.

Ⅱ. 관련 알고리즘

본 장에서는 디지털 영상에 포함된 그림자 영역 검출을 위해 적용된 클러스터링(clustering) 알고리즘들에 관하여 기술한다.

2-1 SLIC superpixels

SLIC(simple linear iterative clustering)은 대표적인 슈퍼픽셀(superpixels) 분할 알고리즘 중 하나이다. 슈퍼픽셀이란 분류기(cluster)를 이용하여 영상의 픽셀들을 연결된 작은 단위로 단순화하는 작업, 즉 유사한 색상과 그레이레벨(gray-level) 간의 연결된 픽셀 그룹을 의미한다[7][8]. 슈퍼픽셀을 이용한 영상분할은 객체 위치 측정, 다중 분할, 광학 흐름, 객체 추적, 깊이 추정과 같은 여러 분야에서 활용되고 있다. 이렇듯 슈퍼픽셀이 다양한 분야에서 활용되는 이유로는 4가지 특징이 있기 때문이다. 먼저, 계산 효율성(calculation effectiveness)이 뛰어나 수십만 개의 픽셀들을 연결해 수백 개의 슈퍼픽셀로 만들어 이미지의 복잡성을 줄인다. 두 번째로는 표현 효율성(expression effectiveness)이 뛰어나다. 즉, 픽셀 그리드(grid)의 인접한 픽셀에 대해서만 계산을 하여서 효율이 떨어졌었지만, 슈퍼픽셀로 만들어 픽셀끼리 연결하였을 경우 슈퍼픽셀 사이에서 픽셀 간의 훨씬 긴 거리의 상호작용을 할 수 있다. 세 번째는 슈퍼픽셀들이 유사한 크기로 연결되어 균일성(uniformity)이 뛰어나며, 마지막으로 유사한 픽셀끼리 연결되는 밀집성(compactness)이다. SLIC은 위의 4가지 특징을 만족하는 슈퍼픽셀 생성 능력과 높은 효율성 때문에 슈퍼픽셀 분할에서 널리 사용되고 있는 알고리즘이다[9][10].

SLIC 알고리즘은 픽셀의 색상 유사성과 이미지 평면의 근접성에 따라 클러스터링하여 슈퍼픽셀을 생성하며, 이것은 5차원 공간인 [l,a,b,x,y]에서 이루어진다. 여기서, [l,a,b]는 컬러 공간 CIE L*a*b*의 색 벡터를 의미하며, [x,y]는 픽셀의 위치를 나타낸다[5]. 먼저 영상을 CIE L*a*b공간으로 변환한 후 영상분할에 사용되는 슈퍼픽셀의 수인 변수 K를 입력한다. 다음으로 식 (1)과 같이 슈퍼픽셀의 그리드 간격 S를 구한다.

$\[ S=\sqrt{N/K}. \]$

(1)

식 (1)에서 N은 입력된 영상의 픽셀의 수이다. 초기 클러스터 중심인 c_i = [l_i,a_i,b_i,x_i,y_i]^T는 그리드 간격 S와 컬러 공간 CIE L*a*b에서의 픽셀값들로 초기화하고, 이때 i는 [1,K]를 의미한다. 그 뒤에 각각의 클러스터 중심에서 3×3 영역의 그래디언트(gradient)가 가장 작은 위치로 중심을 이동시켜주며, 이는 슈퍼픽셀이 가장자리에 집중되는 것을 방지하기 위해서이다. 다음 단계에서는 영상의 모든 픽셀을 가장 거리가 가까운 클러스터로 라벨링(labeling)하며, 이때 범위는 각각의 클러스터를 중심으로 2S×2S 이내의 것들로 하며, 식 (2)와 식 (3)에서 j는 2S 범위 내에 있는 픽셀의 인덱스를 나타낸다. 또한, 가까운지 판단을 하기 위해 픽셀과 클러스터 중심 사이의 거리 값 D는 식 (2)부터 식(4)를 이용하여 계산할 수 있다[5].

$\[ D_c=\sqrt{{\left(l_i-l_j\right)}^2+{\left(a_i-a_j\right)}^2+{\left(b_i-b_j\right)}^2}. \]$

(2)

$\[ D_s=\sqrt{{\left(x_i-x_j\right)}^2+{\left(y_i-y_j\right)}^2}. \]$

(3)

$\[ D=\sqrt{{\left(\frac{D_c}{N_c}\right)}^2+{\left(\frac{D_s}{N_s}\right)}^2}. \]$

(4)

여기서, D_c는 픽셀들의 색상 거리, D_s는 좌표 거리, N_s는 슈퍼픽셀의 간격, N_c는 컬러 공간에서 가장 큰 거리를 의미한다. 모든 픽셀에 레이블이 할당되면 클러스터를 중심으로 클러스터에 속하는 모든 픽셀의 평균으로 갱신한다. 이후에 픽셀을 가장 가까운 클러스터 중심과 연결하고, 클러스터 중심을 다시 계산하는 절차를 반복한다. 마지막으로, 연결되지 못한 픽셀들은 가장 가까운 픽셀로 연결하여 작업을 마무리한다면 그림 1과 같은 결과를 얻을 수 있다[5][9][11].

Fig. 1.

Image segmentation using SLIC algorithm

2-2 k-means++

k-mean 알고리즘은 자율 학습(unsupervised learning)의 일종으로 입력된 데이터를 사용자가 정한 특정 개수의 클러스터로 반복적인 최적화 기법을 통해 데이터를 집합 또는 분류시키는 알고리즘이며, 단순하고 빠른 계산속도라는 장점으로 영상처리 분야에서 일반적으로 사용되고 있다[7][12]. 그러나, k-mean 알고리즘은 초기 클러스터 중심이 어떻게 설정 되냐에 따라 결과가 완전히 다르게 나타날 수 있다. 이러한 단점을 보완하기 위하여 k-means++ 알고리즘을 제안되었으며[6], k-means++ 알고리즘은 클러스터링 기반 알고리즘 중에서도 널리 사용되고 있는 k-means 알고리즘의 정확도 향상을 위해 개량된 알고리즘이다[7]. k-means++ 알고리즘은 먼저 데이터 지점 x에서 가장 근접한 클러스터 중심까지의 거리 P(x)를 정의하고[13], 주요 알고리즘 순서는 아래와 같다.

(a) X에서 무작위로 초기 중심 c₁을 선택한다.
(b) 다음 클러스터 중심 c_i를 P(x^′)² / Σ_x∈XP(x)²의 확률로부터 c_i = x^′ ⊂ X 로 정의한다.
(c) k개의 중심을 선택할 때까지(b)의 과정을 반복한다.
(d) 선택된 k개의 클러스터 중심들을 초기값으로 하여 데이터 집합의 요소들을 가까운 클러스터에 할당한다.
(e) (d)의 결과를 클러스터 중심들을 다시 계산한다.
(f) 각 클러스터의 결과가 바뀌지 않을 때까지 (d)와 (e)의 과정을 반복한다.

k-means++ 알고리즘은 초기값을 구하기 위해 추가적인 시간이 요구되지만, 클러스터의 중심을 넓게 분포시켜 최적의 해를 찾는 것이 보장된다[13]. 그림 2는 그림 1의 각 영상들에 k-means++ 알고리즘을 적용하여 라벨링한 결과 영상들이다.

Fig. 2.

Image labeling using k-means++ algorithm

Ⅲ. 제안하는 그림자 영역 검출 알고리즘

본 논문에서는 SLIC superpixel과 k-means++ 알고리즘을 이용한 클러스터링 기반의 그림자 검출 방법을 제안하며, 전체 파이프라인(pipeline)은 그림 3과 같다. 먼저, RGB 컬러 영상을 CIE L*a*b 컬러 공간으로 변환한 후 SLIC 알고리즘을 적용하여 그림 3(c)와 같이 슈퍼픽셀로 구성한다. 그림 3(c)의 영상을 k-means++ 알고리즘을 이용하여 클러스터링하며, 본 논문에서는 초기 클러스터의 수를 4개로 하여 실험을 진행하였다. 클러스터링된 결과를 RGB 컬러로 레이블링하면 그림 3(d)와 같이 그림자 후보영역의 윤곽을 확인할 수 있다. 여기서 입력 영상을 슈퍼픽셀로 구성하지 않고, k-means++ 알고리즘만 적용한 경우에는 그림 4와 같이 원치 않는 결과를 얻을 수 있다.

Fig. 3.

Pipeline of proposed shadow detection method

Fig. 4.

Result images of label segmentation

그림 4에서 보여주듯이 입력 영상을 슈퍼픽셀로 만들지 않는 경우, 즉 k-means++ 알고리즘만 적용한 그림자 영역 검출은 후보영역의 정확도가 떨어져 그림자 영역이 아닌 부분까지도 포함 시킬 수 있다. 따라서, 그림자 영역 검출의 정확도를 올리기 위해서라도 SLIC 알고리즘을 전처리 과정으로 수행하였다. 그림 3(e)는 그림 3(d)의 라벨링된 영역에서 해당 영역이 그림자인지 아닌지를 판단하기 위해 입력 영상에 각각의 레이블 영역을 마스크 형태로 필터링한 결과 영상들을 나타낸다. 그림자 영역은 클러스터링 과정에서 어두운 특성끼리만 뭉쳤기 때문에 다른 영역보다 상대적으로 픽셀값이 낮다. 따라서, 그림 3(e)에서 해당 영역이 그림자인지 아닌지를 판단하기 위해 각각의 이미지의 최대 픽셀값을 구한 후 그 중 최대 픽셀값이 가장 낮은 이미지를 그림자 영역으로 판단하였으며, 최종적으로 그림자 영역이라고 판단된 영상은 그림 3(e)의 2번째 영상이다. 검출한 그림자 후보영역을 이진화한 후 형태학적 처리를 통해 잡음을 제거하면[14], 그림 3(f)와 같이 최종 그림자 영역을 검출할 수 있다.

Ⅳ. 실험 및 고찰

본 장에서는 제안하는 방법의 그림자 검출의 성공 및 실패 사례를 분석하였으며, 제안 방법의 성능평가를 위해 선행연구들의 검출 결과를 비교하였다. 먼저, 그림 3과 같이 제안하는 방법의 단계별 주요 결과 영상들은 그림 5에서 보여주고 있으며, 높은 그림자 후보영역의 검출 정확도의 결과를 보인다. 또한, 제안 방법의 성능을 평가하기 위해 CIE L*a*b 와 YCbCr의 컬러 공간에서 밝기 정보와 임계치(threshold)를 이용한 그림자 검출 방법들과 MCE(minimum cross entropy) 알고리즘의 그림자 검출 영상을 비교하였다[15][16][17].

Fig. 5.

Step-by-step result images of proposed method

컬러 공간에서 색상과 밝기 정보를 이용한 그림자 영역 검출 방법들은 고품질의 컬러 영상일 경우 높은 정확도로 그림자를 검출할 수 있으나, 그림자와 배경의 강도(intensity) 또는 물체의 색상과 배경 모두 어두운 경우에는 그림자의 검출에 실패할 확률이 높다. 또한, 임계치를 이용하는 그림자 검출의 경우 쉽고 빠르다는 장점이 갖는다. 그러나 그림자 검출 결과가 불확실하거나 흐리게 나올 수 있으며, 결과 영상에 잡음이 있을 확률이 높아 정확한 그림자 영역을 검출하기 위해서는 후처리가 요구된다. 실험결과, 그림 6에서 보여주듯이 본 논문에서 제안하는 클러스터링을 기반으로 한 그림자 검출 방법이 기존의 방법들보다 높은 정확도로 그림자 후보영역이 검출됨을 보였다.

Fig. 6.

Comparison of shadow detection results with proposed method and previous studies

그림 7은 제안하는 그림자 검출 방법의 실패 사례들이며, 크게 두 가지의 이유로 사료된다. 먼저, 그림자 영역 내부에서 특성이 다른 영역이 존재하여 클러스터링 중에 그림자 영역이 분리된 경우와 그림자 영역이 배경과 함께 클러스터링 되는 경우이다. 두 번째로는 그림자 영역과 비슷한 특성을 가진 객체가 존재하여 클러스터링 과정에서 객체를 그림자 영역이라 판단하고 같이 클러스터링해버린 경우이다. 향후, 그림 7과 같은 실패 사례들의 특징들을 분석하여 그림자 검출의 오류율을 낮추고, 딥러닝 기법을 접목하여 제안하는 방법의 그림자 검출 정확도를 향상시키는 연구를 계속 진행 및 제안하고자 한다.

Fig. 7.

Result images of label segmentation

V. 결 론

본 논문에서는 참조 영상이 필요 없이 단일 자연 영상에 포함된 그림자 후보영역을 검출하는 것에 초점을 두었으며, SLIC superpixel과 k-means++ 알고리즘을 기반으로 하는 그림자 검출 방법을 제안하였다. 먼저, 입력 영상을 CIE L*a*b 컬러 공간으로 변환한 후 픽셀값이 유사한 그룹끼리 슈퍼픽셀로 클러스터링을 수행하였으며, 4개의 클러스터로 k-means++ 기반의 반복적인 최적화 기법을 통해 데이터를 분류 및 라벨링 하였다. 또한, 라벨링된 영역에서 해당 영역이 그림자인지 아닌지를 판단하기 위해 입력 영상에 각각의 레이블 영역을 마스크 형태로 필터링하여 이진화된 그림자 후보영역을 검출하였다. 실험결과, 제안하는 클러스터링 기반의 그림자 검출 방법이 기존의 방법들보다 효과적으로 그림자가 검출됨을 보였다. 향후, 제안 방법의 정확도 개선과 딥러닝 기법을 이용한 효과적인 그림자 검출 및 제거 연구를 계속하고자 한다.

Acknowledgments

이 성과는 2019년도 정부(과학기술정보통신부)의 재원으로 한국연구재단의 지원을 받아 수행된 연구임 (No. 2017R1C1B5018143).

참고문헌

• S. Murali, V.K Govindan and S. kalady, “A Survey on Shadow Detection Techniques in a Single Image,” Journal of Information Technology and Control, Vol. 47, No. 1, pp. 75-92, 2018. [https://doi.org/10.5755/j01.itc.47.1.15012]
• N. Singh and A.A. Maxton, “A Survey on Shadow Detection Methods,” International Journal of Advanced Research in Computer Engineering & Technology (IJARCET), Vol. 3, No. 4, April. 2014.
• Q. Zheng, X. Qiao, Y. Cao and R. W. H. Lau “Distraction-aware Shadow Detection,” The IEEE Conference on Computer Vision and Pattern Recognition (CVPR),“ pp. 5167-5176, 2019. [https://doi.org/10.1109/CVPR.2019.00531]
• K. H. Park and Y. S. Lee, “Definition and Analysis of Shadow Features for Shadow Detection in Single Natural Image,” Journal of Digital Contents Society, Vol. 19, No. 1, pp. 165-171, Jan. 2018.
• R. Achanta, A. Shaji, K. Smith, A. Lucchi, P. Fua, and S. Susstrunk, “SLIC Superpixels Compared to State-of-the-art Superpixel Methods,”. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 34, No. 11, pp. 2274-2282, May. 2012. [https://doi.org/10.1109/TPAMI.2012.120]
• D. Arthur and S. Vassilvitskii. "k-means++: The Advantages of Careful Seeding." Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. New Orleans, LA, pp. 1027–1035, Jan. 2007.
• C. G. Woo, K. H. Park and Y. H. Kim, “Shadow Area Detection based on Slic Superpixel and K-mean Algorithm”, Proceedings of KIIT Conference, Jun, 2019.
• J. H. Lee, "A Setting of Initial Cluster Centers and Color Image Segmentation Using Superpixels and Fuzzy C-means(FCM) Algorithm," Journal of Korea Multimedia Society, Vol. 15, No. 6, pp. 761-769, Jun. 2012. [https://doi.org/10.9717/kmms.2012.15.6.761]
• R. Achanta and S. Susstrunk; “Superpixels and Polygons Using Simple Non-Iterative Clustering,” The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 4651-4660, 2017. [https://doi.org/10.1109/CVPR.2017.520]
• X. Ren and J. Malik, “Learning a Classification Model for Segmentation,” Proceedings Ninth IEEE International Conference on Computer Vision(ICCV 03), vol 1, pp. 10-17, Oct. 2003. [https://doi.org/10.1109/ICCV.2003.1238308]
• Y. J. Yoo and D. W. Lee, “Adaptive Superpixel Algorithm based on Image Complexity,” The Institute of Electronics and Information Engineers, pp.458-461, Nov. 2015.
• Wikipedia. k-mean clustering [Internet]. Available: https://en.wikipedia.org/wiki/K-means_clustering, .
• S. W. Lee, “Fast Search Algorithm for Determining the Optimal Number of Clusters using Cluster Validity Index,” in Journa of the Korea Contents Association, Vol. 9, No. 9, pp. 80-89, Sep. 2009. [https://doi.org/10.5392/JKCA.2009.9.9.080]
• R. C. Gonzalez, R. E. Woods, S. L. Eddins, Digital image processing using MATLAB, 1st ed. Chapter 6, New Jersey, NJ: Pearson Prentice Hall, 2004.
• S. Murali and V. K. Govindan, “Shadow Detection and Removal from a Single Image Using LAB Color Space,” CYBERNETICS AND INFORMATION TECHNOLOGIES Vol. 13, No. 1, March 2013. [https://doi.org/10.2478/cait-2013-0009]
• K. Deb and A. H. Suny, “Shadow Detection and Removal based on YCbCr Color Space,” Journal of Smart Computing Review, Vol. 4, No. 1, pp. 23-33, Feb. 2014. [https://doi.org/10.6029/smartcr.2014.01.003]
• K. H. Park, J. H. Kim and Y. H. Kim, “Shadow detection using chromaticity and entropy in colour image,” Int. J. Information Technology and Management, Vol. 17, 2018. [https://doi.org/10.1504/IJITM.2018.089454]