체인코드와 기하학적 복잡도 지수에 기반한 가중치 형태 검색

Ⅰ. 서 론

인간의 인지 특성으로 형태 정보는 객체 인식의 중요한 수단 중의 하나가 되고 있다. 우리가 사물을 볼 때 채도나 명도에 의해 사물을 인식하는 것처럼 사물의 외부 형태나 표면의 특징도 같은 방식으로 보게 된다는 것이다. 이것은 선으로 사물의 윤곽을 나타낸 다음에 그 안에 색상을 넣어 표현하거나 색상을 넣은 뒤에 윤곽선을 더하는 그림책과 같은 형식이라고 한다. 이처럼 뇌에 존재하는 단일 신경세포는 이러한 윤곽 정보를 먼저 처리한 후에 내부의 정보를 채워 넣는 식으로 작동하여 실제의 사물을 인식한다는 것이다[1].

일반적인 콘텐츠 기반 영상검색(CBIR, Content Based Image Retrieval)은 색상, 질감, 모양 및 움직임 관계의 네 가지 중요한 기능을 갖는 구성 요소로 되어 있다. 이들 구성 요소 중 형태 정보는 객체의 윤곽을 구분 짓는 특성으로 하나의 객체를 인식하기 위한 기하학적 속성을 제공한다. 이는 객체의 유한요소, 다각형 근사, 윤곽 특징 등으로 표현할 수 있으며 객체의 윤곽선은 객체의 크기나 놓여있는 위치 등에 영향을 받지 않는다는 특성을 갖는다. 그러나 기하학적 속성으로 윤곽 정보를 이용하는 객체에 대한 형태 검색의 여러 장점에도 불구하고 객체의 유사성에 대한 객관적인 형태 정의가 어렵고 형태 모양의 추출 및 모델링이 어렵다는 제한점이 제기되고 있다[2].

본 연구에서는 이러한 문제를 개선하기 위한 연구로서 먼저 질의 영상의 객체 윤곽선을 추출한 후 체인코드 변화 빈도수 대비 윤곽선 길이에 의해 체인코드 지수를 구한다. 다음으로 객체의 윤곽선 길이 대비 면적에 의해 기하학적 복잡도를 구한다. 그리고 체인코드 빈도수와 복잡도에 기반한 적응적 형태 검색에서의 설계 알고리즘을 제안하고자 한다. 그리고 시뮬레이션을 통하여 제안한 알고리즘의 검색 성능이 효율적임을 입증하고자 한다.

이를 위하여 제2장에서는 관련 연구를 고찰하고 제3장에서는 가중치 체인코드 지수와 객체 복잡도 가중치에 기반한 적응적 형태 검색을 제안하고 이에 대한 시뮬레이션과 성능 분석을 하고자 한다. 그리고 제4장에서 결론을 맺는다.

Ⅱ. 관련 연구 및 방법론

뇌 구조가 사물을 인식하는데 윤곽 정보를 먼저 처리한다는 연구 결과가 발표되면서 형태 검색에 대한 많은 관심이 집중되고 있다.

Padmashree Desai 등은 CBIR에 관한 연구에서 형태 정보는 인간이 인지할 수 있는 가장 매력적인 시각 정보를 담고 있는 것으로 보고 CBIR 시스템의 문제점과 과제 그리고 영상검색에서 형태 특징의 중요성을 분석하였고 또한 웨이블릿 기반 형태 특징을 이용한 영상검색 방법도 제안하였다[3].

Minki Kim은 윤곽선 세그먼트의 양 끝점을 잇는 직선과 곡선의 길이의 비율로 윤곽선 변동률을 정의하고, 이로부터 윤곽선의 형태를 기술하는 방법을 제안하였다. 윤곽선 변동률은 윤곽선 세그먼트의 단위 길이에 따라 국소적 또는 전역적인 특징을 나타내므로, 윤곽선 변동률의 분포를 나타내는 특징 벡터로 물체의 형태를 기술하고, 단위 길이별로 특징 벡터를 비교하여 윤곽선 형태의 유사도를 계산하였다[4].

P.K. Kim 등은 윤곽선 특징점 기반 형태 유사도를 이용한 손동작 인식을 발표하였다. 그들의 손 형태 유사도 측정은 윤곽선을 추출한 후 인접 간선들 사이의 거리와 각도 관계로 TSR을 적용하여 손동작의 유사성을 시도하였다[5].

Tsorng-Lin Chia 등은 외부 및 내부 객체 윤곽선에 대한 체인 코드를 생성하기 위해 하향식 윤곽 추적 방법으로 추적할 수 있는 모서리 세트 등을 이용하였다[6]. J.A. Park 등은 프리맨 체인 코드의 통계적 표현에 기반하여 윤곽선을 추출하고 배열 히스토그램 수를 계산한 후 재배열 체인 코드의 평균과 분산을 계산하는 검색 기법[7]과 객체 윤곽선 체인코드의 빈도수 재배열 속성과 기하학적 복잡도에 기반하여 영상을 검색하는 기법을 발표하였다[8]. 그러나 제한적으로 사용된 체인코드의 빈도수와 기하학적 복잡도의 상관관계는 앞으로 해결해야 할 문제로 남겨 놓았다.

Pushpendra Singh도 형태 검색을 위한 특성자로서 영역 기반 기술자와 윤곽 기반 기술자로 구분하고 윤곽 기반에서는 객체의 전체 영역을 분석하고 영역 기반에서는 객체의 경계선을 고려해 형태 기술자를 분석하였다. 그리고 표준 원칙에 따라 영상검색을 위해 몇 가지 모양 설명자로 분류하였다[9].

Ismail Khalid Kazmi 팀은 지난 수십 년 동안 2D 및 3D 형태 기술자를 사용하여 3D 객체 검색 기술을 연구했다. 그리고 그들은 영역 기반 2D 형태 기술자가 3D 형태 검색에서 로컬 기능 정합을 위한 도구라는 것을 발표하고 전역 기능 기반 정합과 로컬 기능 기반 정합 사이의 장단점에 관해 연구하였다[10]. 전역 기능 기반 방식은 전체 구조를 고려하고 전체 모양을 설명하는 기능 벡터를 생성하기 때문에 로컬 또는 부분 매칭에는 적합하지 않으나 계산하기 쉽고 빠르다는 장점을 발표하였다. 그러나 여전히 객관적인 형태 정의가 어렵고 또한 형태 모델링이 어렵다는 한계점을 갖는다.

본 연구에서는 형태 기반 영상검색의 성능을 개선하기 위하여 영상 객체 윤곽선의 체인코드 빈도수를 정규화하여 얻은 지수와 기하학적 복잡도를 기반으로 하는 적응적 가중치를 갖는 형태 검색 기법을 제안한다. 제안된 기법의 영상검색 성능을 확인하기 위하여 Wang DB[11] 영상을 이용하여 시뮬레이션을 수행하고 차분값 기반 체인코드 기법과 비교하여 제안된 기법의 정확도 및 재현율을 비교하여 제안된 형태 검색이 상대적으로 우수한 성능을 가진다는 것을 확인하고자 한다. 제안한 검색 기법은 객체 윤곽선의 체인코드 지수와 복잡도 가중치를 기반으로 간단하게 형태 검색의 리콜률과 정확도를 높일 수 있다. 또한 색상 기반 영상검색 대비 이치 영상으로 연산수를 감소시키게 되므로 검색 속도가 빠르다. 그러므로 형태 검색을 위해 체인코드 빈도수와 기하학적 복잡도 그리고 이들 가중치를 기술자로 이용하여 검색률을 높이고자 한다.

Ⅲ. 체인코드 빈도수와 기하학적 복잡도 기반 알고리즘 설계

3.1 알고리즘 설계

S/W 알고리즘 성능 분석에 시간 복잡도나 공간 복잡도가 사용되듯이 형태 검색 알고리즘을 위한 구성 요소로서 체인코드 지수와 기하학적 복잡도를 도입한다. 이에 따라 제안한 알고리즘은 객체 윤곽선의 체인코드 지수와 기하학적 복잡도를 검색 속성으로 사용하여 그림 1과 같이 구성된다. 여기서 C_N와 w₁은 허용된 오차범위 내 체인코드 지수와 그의 가중치이며 X_C와 w₂는 허용된 오차범위 내 기하학적 복잡도와 그의 가중치이다.

Fig. 1.

Proposed adaptive shape retrieval algorithm

검색 알고리즘을 위한 순서는 그림 1과 같다. 먼저 질의 영상의 객체 윤곽선을 추출하여 체인코드 변화 빈도수 f_c 대비 윤곽선 길이 l_f에 의한 체인코드 지수 C_N를 구한다. 그리고 객체에 대한 윤곽선 길이 l_c 대비 면적 a_c에 의해 기하학적 복잡도 X_c를 구한다. 그리고 상관함수로서 복잡도가 크면 기하학적 복잡도의 가중치 w₂를 크게 산정하고 복잡도가 작으면 체인코드 지수의 가중치 w₁를 크게 산정한다. 이는 인공지능 응용이 가능할 것으로 판단되나 본 논문에서는 검색 가중치 w₁과 w₂를 단윗값으로 정규화하여 0.02 간격으로 상호 순환적으로 적용하여 객체에 대한 최적 가중치를 구하였다. 이와 같이 복잡도에 따른 상관함수로서 검색 가중치를 산정하여 식(4)에 따라 특징 벡터 V_f를 산출하여 유사도를 검색한다.

$\[ C_N=f_c/l_c \]$

(1)

$\[ X_C=l_c/a_c \]$

(2)

$\[ V_f=Cor.\left(w_1{C}_N+w_2{X}_C\right) \]$

(3)

여기서 Cor은 정량화 계수, w₁은 체인코드 지수의 가중치이고 w₂는 기하학적 복잡도의 가중치이다. 실험에서 허용된 오차범위의 체인코드 빈도수 값은 전체 재배열 속성 대비 설정한 오차범위 값으로 하고 오차범위 값은 제거한다.

3.2 실험 및 성능 분석

본 논문에서는 윤곽선 체인코드 지수와 기하학적 복잡도의 가중치에 기반한 적응적 형태 검색 기법을 제안했다. 실험은 Wang DB[11]에서 단순 질의 영상과 복잡 질의 영상으로 나누어서 구성한 후 진행하였다. 단순 질의 영상은 동전, 꽃, 하우스, 공룡 등 배경이 단순하고 객체의 윤곽선이 뚜렷한 RGB 영상 500개로 구성되어 있다. 복잡 질의 영상은 코끼리, 말, 버스 등 배경이 복잡한 RGB 영상 500개로 구성하였다.

실험 환경은 GPU 32TFLOPS(64bit) CPU 2.99GHz 24Core RAM 350GB SSD 200GB와 같고 MATLAB을 이용하였다. 실험 결과는 유사도 우선순위에 따라 나타나도록 하고, DB 내 질의 영상의 유사 영상 개수 평균인 20개를 찾도록 정의하여 놓았다. 그림 2~3의 검색 결과 첫 번째 영상은 질의 영상이자 1순위로 검색된 결과 영상을 나타내고 있다.

Fig. 2.

Retrieval result of the simple query image

Fig. 3.

Retrieval result in the complicated query image

실험 결과 배경도 그림 2(a)와 같이 단순하고 객체의 윤곽선도 뚜렷한 동전 영상의 경우 확대 및 축소의 크기 변화나 회전에도 유사 영상을 잘 찾아내는 것을 확인하였다.

그러나 그림 2(b)와 같이 배경은 단순하지만 객체의 윤곽선이 조금 더 복잡한 꽃 영상의 경우 동전 영상보다는 유사 영상의 정확도가 떨어지지만 데이터베이스 내에 질의 영상과 유사한 영상들이 모두 20개 이내에 검색되는 것을 확인할 수 있었다.

그리고 그림 3과 같이 배경이나 객체 윤곽선이 복잡한 영상의 경우도 회전이나 크기 변화에 강인한 결과를 보이는 것을 확인할 수 있다.

검색 정확도의 효율성을 분석하기 위해 정량적으로 재현율과 정확도의 두 가지 성능 평가 척도를 이용한다. 재현율은 데이터베이스에서 질의와 관련된 영상 중 검색된 영상의 비율이고, 정확도는 검색된 영상 중에서 질의와 관련된 영상의 비율을 나타낸다. 재현율과 정확도는 식 (4), (5)와 같은 조건부 확률로 정의할 수 있다. 여기서, A는 영상 데이터베이스 내에서 관련된 영상의 집합이고, B는 검색된 영상의 집합이다.

$\[ Recall=P\left(\frac{B}{A}\right) \]$

(4)

$\[ Precision=P\left(\frac{A}{B}\right) \]$

(5)

재현율이 크다는 것은 매칭률이 높다는 것을 뜻하고, 정확도가 높다는 것은 잘못 검출된 영상이 많지 않다는 것을 뜻한다.

그림 4는 윤곽선 체인코드와 기하학적 복잡도 지수의 가중치에 따른 재현율과 정확도를 구한 그래프이다. 그래프에서는 다음과 같은 검색 특성을 확인하였다.

Fig. 4.

Recall and precision according to weights of the chaincode index(w1) and geometric complexity index(w2)

• - 간단한 영상에서는 기하학적 복잡도 가중치 w₂가 클 때 재현율이 크게 높아지나 체인코드 지수의 가중치 w₁이 클 때는 정확도가 낮아진다.
• - 복잡한 영상에서는 기하학적 복잡도 가중치 w₂가 클 때 재현율이 크게 낮아지나 체인코드 지수의 가중치 w₁이 클 때는 정확도가 높아진다.
• - 실험에 사용된 질의 영상과 DB로 제한할 때 일반적 가중치 지수는 100을 정규화 척도로 복잡도 가중치 w₂는 30~36 사이, 체인코드 지수의 가중치 w₁은 64~70 사이에서 실험적 최적값에 수렴한다는 것을 확인하였다.

Ⅳ. 결 론

본 연구에서는 객체 윤곽선의 체인코드 빈도수를 재배열한 후 얻는 제한적 속성과 기하학적 복잡도를 산출해 적응적으로 검색 가중치를 적용하는 방법을 제안하였다. 시뮬레이션은 체인코드 빈도수 재배열 속성과 기하학적 복잡도를 구한 후 검색 가중치 w₁와 w₂를 정규화하여 ±0.02 간격으로 상호 역 순환적으로 적용하여 실험 결과를 산출하였다. 실험 결과는 복잡도가 낮은 단순 영상의 검색 결과는 체인코드 지수의 가중치를 크게 산정할 때가 재현율과 정확도가 높아지고, 복잡한 영상에서의 검색 결과는 기하학적 복잡도의 가중치를 크게 산정하면 재현율과 정확도가 높아지는 것을 확인할 수 있다. 일반적 가중치 지수로는 100을 정규화 척도로 할 때 복잡도 가중치는 30~36 사이, 체인코드 지수의 가중치는 64~70 사이에서 실험적 최적값에 수렴한다는 것을 확인하였다. .

Acknowledgments

“2020년도 한국정보기술학회 추계종합학술대회에서 발표한 논문(Weighted assignment in combined shape retrieval based on chaincode frequency and area complexity)[8]을 확장한 것임”

References

• How the Brain Recognizes Objects, KISTI Global Trend Briefing (GTB): https://www.ibric.org/myboard/read.php?Board=news&id=129606/, . [accessed: Jun. 01, 2022]
• Ji-Min Lee, Jong-An Park, and Young-Eun An, "Object Retrieval based on Complexity and Frequency Normalization of Contour Chaincode", Journal of KIIT, Vol. 18, No. 9, pp. 107-113, Sep. 2020. [https://doi.org/10.14801/jkiit.2020.18.9.107]
• Padmashree Desai, Jagadeesh Pujari, and Shweta Parvatikar, "Image Retrieval Using Shape Feature: A Study", International Conference on Computational Intelligence and Information Technology, CIIT 2011, Pune, India, Vol. CCIS 250, pp. 610-614, Nov. 2011. [https://doi.org/10.1007/978-3-642-25734-6_146]
• Minki Kim, "Two-Dimensional Shape Description of Objects using the Contour Fluctuation Ratio", Journal of Korea Multimedia Society, Vol. 5, No. 2, pp. 158-166, Apr. 2002.
• Hong-Ryoul Yi, Chang Choi, and Pan-Koo Kim, "Hand Gesture Recognition Using Shape Similarity Based On Feature Points Of Contour", Proc. of the Korean Institute of Information and Commucation Sciences Conference, pp. 585-588, May 2008.
• Tsorng-Lin Chia, Kuang-Bor Wang, Lay-Rong Chen, and Zen Chen, "A parallel algorithm for generating chaincode of objects in binary images", Elsevier, Information Sciences, Vol. 149, No. 4, pp. 219-234, Feb. 2003. [https://doi.org/10.1016/S0020-0255(02)00267-0]
• J. A. Park, K. M. M. Chisty, J. M. Lee, Y. E. An, and Y. Choi, "Image Retrieval Technique Using Rearranged Freeman Chain Code", 2011 First International Conference on Informatics and Computational Intelligence, Bandung, Indonesia, pp. 283-286, Dec. 2011. [https://doi.org/10.1109/ICI.2011.54]
• J. A. Park, J. M. Lee, J. H. Chun, and Y. E. Lee, "Weighted assignment in combined shape retrieval based on chaincode frequency and area complexity", The Proc. of the 2020 KIIT Conference, Vol. 15, No. 1, pp. 49-51, Oct. 2020.
• Pushpendra Singh, V.K. Gupta, and P.N. Hrisheekesha, "A Review on Shape based Descriptors for Image Retrieval", International Journal of Computer Applications (0975–8887) Vol. 125, No. 10, pp. 27-33, Sep. 2015. [https://doi.org/10.5120/ijca2015906043]
• Ismail Khalid Kazmi, Lihua You, and Jian-Jun Zhang, "A Survey of 2D and 3D Shape Descriptors", Published 6 August 2013 Computer Science, 2013 10th International Conference Computer Graphics, Imaging and Visualization: https://research.tees.ac.uk/ws/files/6383025/621212.pdf, . [accessed: Jun. 01, 2022]
• http://wang.ist.psu.edu/docs/home.shtml, . [accessed: Aug. 01, 2022]