분할된 부분 윤곽선의 주파수 공간에서의 표현과 형상 정합

Ⅰ. 서 론

물체 추출은 컴퓨터 비전 및 패턴 인식에서 중요한 문제로서, 사물 인식, 의료 영상, 형상 분석, 로봇 등 다양한 분야에서 폭넓게 응용되고 있다. 물체 추출은 영상에서 필요한 정보만을 얻기 위해 전처리 과정이 필요하다. 이는 불필요한 정보로 인한 손실을 줄이기 위해서이다. 특히, 필터나 이진화 등의 전처리 과정을 거쳐 윤곽선을 추출하거나 라벨링될 수 있다[1].

추출된 윤곽선은 형태 기술자(Shape context)[2], MPP(Minimum Perimeter Polygons)[3] 그리고 푸리에 기술자(Fourier descriptor)[4] 등과 같이 표현되고, 이들의 정합(Matching)을 통해 특정한 물체로 추출된다. 이 방법들은 형상의 위치를 기반으로 처리하는 윤곽선 기반 처리 기술이다[5]-[7]. 윤곽선은 빛이나 방향에 따라 다양하게 나타나며, 완전한 형태의 윤곽선을 얻기 힘들 수가 있다[8]. 따라서 획득된 영상에서 원하는 물체 형상의 윤곽선은 형상의 일부분 또는 원하지 않는 부분과 연결되어 나타날 수 있다.

전체 또는 부분적으로 나타난 윤곽선의 표현과 정합에는 새로운 기술이 요구된다. 부분 윤곽선의 표현과 정합을 위한 다양한 시도가 있었다. 이 중에서 TCDs(Triangular Centroid Distances)[9]는 최근에 제안된 주파수 변환을 이용하여 윤곽선을 표현하는 방법으로서, 정합 성능도 우수하다. 이는 윤곽선을 크기, 위치 및 회전에 무관하게 주파수 영역으로 표현하여 효과적인 형상 정합이 되도록 하는 방법이다[10][11].

또한 TCDs는 분할된 윤곽선의 특징을 조합하여 형상을 비교 정합시킬 수 있다. 그러나 분할된 윤곽선의 경우, 형상을 정합시키는 과정에서 다양한 길이를 가진 윤곽선 샘플링 개수가 많아질수록 정합을 반복적으로 수행함으로써 많은 자원을 소모하는 문제가 있다.

본 논문에서는 형상의 윤곽선을 전체 또는 일부분으로 나누어 샘플링 개수에 따른 부분 윤곽선을 표현하고, 표현된 정보에 따라 학습 패턴과 정합시켜 학습된 물체를 추출하는 방법을 제안한다. 제안된 방법은 전체 윤곽선의 표현뿐만 아니라 부분 윤곽선도 정합을 통해 추출할 수 있다. 실험을 통해 부분 윤곽선을 표현하고 이들의 정합을 통해 제안하는 방법으로 다양한 윤곽선을 추출할 수 있는 타당성을 검토한다.

Ⅱ. 윤곽선의 주파수 표현

주어진 영상으로부터 관심 있는 물체를 추출하기 위해서는 윤곽선이 먼저 추출되어야 한다. 그리고 추출된 윤곽선은 정합을 위하여 올바르게 표현되어야 한다. 본 논문에서는 OpenCV에서 제공하는 에지 추출 함수를 이용하여 윤곽선을 추출하였다.

추출된 윤곽선은 정합을 위한 올바르게 표현되어야 한다. 본 논문에서는 TCDs를 이용하여 주파수 공간으로 표현하는 방법을 이용하였다. 이는 전술한 바와 같이 추출된 윤곽선의 2차원 공간 위치인 좌표 점을 기반으로 하고 있다.

그림 1은 점 P_i = (x_i,y_i), i = 1,2,...,N 인 좌표점과 삼각형을 이용하는 TCD를 보여주고 있다. 윤곽선 내의 시작점 P_i와 임의의 좌표점 P_j, 그리고 윤곽선 전체의 무게 중심점 G에 의해 삼각형 모양을 이루게 된다. 이 삼각형의 무게 중심점 G_ij = (x_gij,y_gij)는 다음과 같다. 즉,

이 된다.

Fig. 1.

Contour and TCD with triangle

특징 벡터는 그림과 같이 하나의 시작점과 윤곽선 위를 지나는 모든 좌표 점들과의 무게 중심점을 순서에 따라 나열하여 얻을 수 있다. 즉, 각 중심점과 시작점과의 거리를 나열하면 (N-1)개 점에 대한 거리 벡터를 얻는다. 얻어진 거리 벡터는 정규화되어 하나의 이산 패턴으로 구성된다. 이산 패턴들은 푸리에 변환되어 주파수 공간의 특징 벡터로 변환된다. 따라서 하나의 시작점에서 시작된 윤곽선은 주파수 공간으로 표현될 수 있다.

이처럼 또 다른 시작점과 윤곽선은 순서에 따라 반복되어 주파수 공간으로 표현될 수 있다. 마지막 좌표 점까지 같은 과정은 반복된다. 따라서 N개의 시작점에 대하여 (N, N-1)의 거리 벡터를 얻을 수 있으며, 마찬가지로 (N, N-1) 공간의 주파수 공간 벡터를 얻을 수 있다.

여기에서 주파수 공간은 그 특성에 따라 (N, Nf)의 벡터로 축약된 공간으로 표현될 수 있다. 윤곽선의 주파수 정보가 작은 고조파 영역을 제외하여 N-1 > Nf로 공간 크기를 축소할 수 있다. 또한, 주파수 공간의 특성은 회전, 위치에 무관하게 표현될 수 있으며, 정규화를 통해 크기에도 무관한 벡터로 표현할 수 있다. 그림 2는 하나의 윤곽선을 주파수 공간 벡터로 표현한 예를 보여주고 있다. 이때 주파수 공간의 크기 Nf=16으로 하였다.

Fig. 2.

Representation of the frequency space, (a) Contour, (b) Vector in the frequency space

Ⅲ. 분할된 윤곽선의 표현과 정합

전술한 바와 같이 TCDs는 주어진 윤곽선을 주파수 공간으로 표현하는 방법이라고 하였다. 이 방법은 부분 윤곽선도 같은 방법을 적용할 수 있으며, 부분 윤곽선을 주파수 공간으로 표현하는 방법이다. 그러나 이는 윤곽선 위의 샘플링되는 개수에 따라 유사도 측정에 어려움이 있다. 따라서 본 논문에서는 고정적인 샘플링 개수에 따라 분할 윤곽선으로 표현하고자 한다. 이렇게 함으로써 샘플링 개수가 일정하게 되어 효율적인 유사도 정합 과정을 가질 수 있다. 더불어 이로 인해 부분 윤곽선을 일정한 샘플링 개수로 처리될 수 있다.

3.1 윤곽선의 분할

부분 윤곽선은 복잡도에 따라 2, 4, 8분할된 다양한 패턴으로 만들 수 있다. 그림 3은 4분할된 윤곽선 구성을 시각적으로 표현한 그림이다. 이를 통해 1/4, 2/4, 3/4 및 4/4(완전한 윤곽선) 부분 윤곽선을 얻을 수 있다. 1/4, 2/4, 3/4 부분 윤곽선은 전체 윤곽선에서 4개를 각각 얻을 수 있다. 따라서 하나의 윤곽선은 4분할인 경우, 13개의 부분 윤곽선을 얻을 수 있다.

Fig. 3.

Four division for the partial contours

영상에서 추출된 윤곽선은 모든 좌표점 대신 일정한 개수로 샘플링된 좌표점을 이용한다. 이는 윤곽선 정합을 더 쉽게 하기 위해서이다.

그림 4는 샘플링 개수가 100개인 4분할된 부분 윤곽선들을 보여주고 있다. 그림에서 1/4, 2/4, 3/4의 부분 윤곽선은 4개씩 각각 구성된다. 특히, 2/4와 3/4는 시작점이 전체 윤곽선 길이의 1/4씩 겹치도록 윤곽선을 구성하였다. 그리고 좌표점 개수는 1/4인 경우 25개, 2/4인 경우 50개, 3/4인 경우 75개로 각각 설정하였다.

Fig. 4.

4 Divided partial contours with 100 points

또한 정합에 사용되는 입력 윤곽선은 마찬가지로 25개, 50개, 75개 및 100개로 각각 샘플링되어야 한다. 그리고 정합시 1/4의 경우 25개, 2/4 50개, 3/4 75개, 4/4의 경우 100개인 벡터와 서로 정합시켜야 한다. 따라서 입력되는 윤곽선의 좌표점 개수가 25개보다 작은 경우에는 의미가 없는 윤곽선이 될 가능성이 크다.

3.2 부분 윤곽선의 주파수 공간 표현

주어진 윤곽선은 TCDs 알고리즘에 따라 주파수 공간으로 변환시켜야 한다. 그림 5는 1/4 부분 윤곽선에 대한 주파수 공간 벡터의 예를 보여주고 있다.

Fig. 5.

Representation in the frequency space for 1/4 partial contours, respectively

그림에서 보면, 1/4 부분 윤곽선의 샘플링 개수는 25개이며, 부분 윤곽선의 수는 4개이다. 그리고 본 논문에서 사용하는 푸리에 변환의 Nf=10로 하였다. 따라서 하나의 윤곽선은 (25, 10)의 주파수 공간 벡터로 표현됨을 알 수 있다.

Ⅳ. 실험 결과 및 고찰

제안한 방법의 타당성을 확인하기 위하여 몇 가지 실험을 진행하였다. 그림 6은 두 개의 형상에 대한 좌측의 학습 형상과 좌표점을 이동시켰을 때 정합된 윤곽선과의 유사도를 측정하였다. 그림으로 볼 때 윤곽선의 좌표점이 이동할 때마다 윤곽선의 형상이 달라지지만 복잡한 형상을 가지지 않아 유사도가 크게 차이 나지 않는다. 반면 닭 형상은 그보다 급격하게 커브를 가지기 때문에 윤곽선의 좌표점이 이동했을 때 유사도의 차이가 벌어지는 것을 볼 수 있다.

Fig. 6.

Similarity when the contours are moved

그림 7은 형상 (a)를 학습시키고 (b), (c), (d), (e)의 부분 윤곽선을 제안한 방법으로 수행하여 유사도를 측정하였다.

Fig. 7.

(a) Learned contour and the given contours, (b) 1/4, (c) 2/4, (d) 3/4, (e) 4/4

그림 8은 측정된 유사도를 보여주고 있다. 그림을 보면 1/4 부분 윤곽선은 13개의 패턴과의 차이가 점점 크게 나타나며, 2/4와 3/4 패턴과의 유사도가 비슷하게 나타난다. 또한, 4/4 패턴과의 유사도는 하락하는 추세를 가지고 있다. 이를 통해 부분 윤곽선과의 차이를 예측할 수 있다. 유사도가 0.3 부근에서 같은 부분 윤곽선인지 판단될 수 있다.

Fig. 8.

Similarity

다음은 유사도의 임계치 D_th를 찾기 위해 그림 9와 같이 같은 종(낙타)을 입력하여 유사도를 측정하였다. 표 1은 측정한 결과를 보여주고 있다. 결과를 보면 학습 패턴과 같은 1번은 유사도가 0이다. 그리고 주로 3/4 부분 윤곽선과 매칭된 개수가 많이 나타남을 확인할 수 있다. 이는 형상들이 3/4만큼 비슷하지만 1/4이 차이가 있음을 알 수 있다. 표에서 별도로 4/4 부분 윤곽선과의 유사도를 측정하였는데, 틀린 부분에 대해 유사도가 차이가 있음을 보여주고 있다.

Fig. 9.

Various camel shapes

Table 1.

Result of comparing the camels with the shape combination

표로부터 같은 낙타 형상이지만 형상에 따라 유사도는 최대 0.51로 나타난다. 반면 제안된 방법의 유사도는 최대 0.35로, 이는 3/4 부분 윤곽선과 정합이 이루어짐을 알 수 있다.

만약 D_th=0.35라 설정했다면 기존의 4/4 정합에서는 9개의 형상이 다른 종류로 판단되는 인식 결과를 가져온다. 그러나 제안된 방법은 3/4 부분 윤곽선으로 인식될 수 있다.

그림 10은 패턴 11, 패턴 13에 대한 100개의 각 좌표점에 해당하는 주파수 공간 벡터(Nf=10)의 같은 시작점에 대한 모든 벡터의 합을 나타낸 결과이다. 즉, 두 벡터의 위치에 대한 차이를 보여주고 있다. 그림에서 알 수 있듯이 패턴 1은 패턴 11과 큰 차이가 없지만, 패턴 13과 큰 차이를 보여주고 있다. 이 차이는 시작 부분과 끝나는 부분에서 크게 나타나며 낙타의 다리 부분임을 알 수 있다.

Fig. 10.

Comparison of position sum of the frequency vector for contour 1, 11 and 13

그림 11은 주파수 공간 벡터의 주파수 측에서의 합을 나타낸 결과이다. 그림을 보면 5와 9에서 차이가 있음을 보여주고 있다. 따라서 모양에 따라 다양한 차이를 보인다는 것을 알 수 있다.

Fig. 11.

Comparison of frequency sum of the frequency vectors for contour 1, 11, and 13

Ⅴ. 결 론

본 논문에서는 부분 윤곽선의 효율적인 정합을 위해 주어진 윤곽선을 분할시켜 정합시키는 방법을 제안하였다. 분할된 부분 윤곽선의 주파수 특성 공간의 특징을 추출하고, 정합은 같은 샘플링에 의한 주파수 공간 벡터와 유사도를 이용하였다. 4분할의 경우 13개의 부분 윤곽선을 가지며, 각 샘플링 개수에 따라 부분 윤곽선들의 정합이 가능하다.

부분 윤곽선들은 유사도가 경계치 D_th보다 작으면 정합이 되었다고 할 수 있다. 원 형태에서는 D_th가 0.3 부근이 적당하게 나타났으며, 낙타 형상에 대해 D_th=0.35인 경우, 제안된 방법은 3/4 부분 윤곽선으로 인식되었다. 따라서 입력으로 사용된 윤곽선이 온전하거나 일부분만 가져도 제안된 방법을 이용하여 정합을 시킬 수 있음을 확인하였다.

Acknowledgments

이 논문은 2018년도 정부(교육부)의 재원으로 한국연구재단의 지원을 받아 수행된 기초연구사업임(No. 2018R1D1A1B07045565)

References

• I. J. Cho and S. W. Yeom, "Long Distance Face Detection with Region of Interest Extraction", Korean Institute of Intelligent Systems, Vol. 28, No. 3, pp. 281-286, Jun. 2018. [https://doi.org/10.5391/JKIIS.2018.28.3.281]
• N. Gherabi, A. G. Gherabi, and M. Bahaj, "A new algorithm for shape matching and pattern recognition using dynamic programming", International Conference on Multimedia Computing and Systems, Ouarzazate, Morocco, pp. 1-6, Apr. 2011. [https://doi.org/10.1109/ICMCS.2011.5945671]
• Y. Y. Nam and E. J. Hwang, "A Representation and Matching Method for Shape-based Leaf Image Retrieval",  The Korean Institute of Information Scientists and Engineers, Vol. 32,  No. 11, pp. 1013-1021, Nov. 2005.
• D. Zhang and G. Lu, "Shape-based Image Retrieval Using Generic Fourier Discriptor", Signal Processing: Image Communication, Vol. 17, No. 10, pp. 825-848, Nov. 2002. [https://doi.org/10.1016/S0923-5965(02)00084-X]
• M. S. Sim, J. H. Kwak, and C. H. Lee, "Fast Shape Matching Algorithm Based on the Improved Douglas-Peucker Algorithm", KIPS Transactions on Software and Data Engineering, Vol. 5, No. 10, pp. 497-502, Aug. 2016. [https://doi.org/10.3745/KTSDE.2016.5.10.497]
• C. H. Noh, S. L. Lee, and C. W. Chung, "SOSiM: Shape-based Object Similarity Matching using Shape Feature Descriptors", Journal of KIISE : Databases, Vol. 36, No. 2, pp. 73-83, Apr. 2009.
• C. Veltkamp, "Shape matching:Similarity measures and algorithms", Shape Modeling and Applications, SMI 2001 International Conference, Genova, Italy, pp. 188-197, May 2001.
• J. H. Lee, C. H. Park, and Y. S. Seo, "Development of Vehicle Sealing Inspection System Using Geometry Matching Method", Journal of the Korean Society of Manufacturing Technology Engineers, Vol. 22, No. 1, pp. 150-155, Feb. 2013. [https://doi.org/10.7735/ksmte.2013.22.1.150]
• C. Yang, H. Wei, and Q. Yu, "A Novel Method for 2D Nonrigid Partial Shape Matching", Neuro Ccomputing, Vol. 275, pp. 1160-1176, Jan. 2018. [https://doi.org/10.1016/j.neucom.2017.09.067]
• J. M. Lee and S. J. Kim, "Object detection of shape matching using the multiple partial contours", KITT Conference, Jeju, Korea, pp. 154-156, Jun. 2021.
• S. J. Kim, H. S Kwon, and J. M. Kim, "A Recognition of Lip Commands Using a Motion Shape Descriptor", The Journal Of KIIT, Vol. 18, No. 11, pp. 1-7, Nov. 2020. [https://doi.org/10.14801/jkiit.2020.18.11.1]