본 논문에서는 식물 잎 모양을 기반으로 이미지를 표현하고 검색하는 식물 잎 이미지 검색 시스템을 보인다. 보다 효과적인 잎의 모양 표현을 위하여, MPP(Minimum Perimeter Polygons) 알고리즘을 개선하였고, 처리시간을 줄이기 위하여, NN(Nearest Neighbor) 검색을 개선한 동적 매칭알고리즘을 제안하였다. 본 시스템은 사용자에게 질의 이미지를 업로드하는 인터페이스를 제공하거나 모양 특징에 기반한 질의를 생성하는 도구를 제공하고 유사도에 따른 이미지를 검색한다. 검색의 편의성을 위해, 웹상에서 잎 모양과 잎차례를 스케치하여 손쉽게 질의할 수 있게 하였다. 실험에서는, 한국에 자생하는 식물 이미지 데이터베이스를 구축하였으며, 질의를 통해 검색된 유사한 이미지의 개수를 기반으로 성능을 평가하였다.
본 논문에서는 식물 잎 모양을 기반으로 이미지를 표현하고 검색하는 식물 잎 이미지 검색 시스템을 보인다. 보다 효과적인 잎의 모양 표현을 위하여, MPP(Minimum Perimeter Polygons) 알고리즘을 개선하였고, 처리시간을 줄이기 위하여, NN(Nearest Neighbor) 검색을 개선한 동적 매칭알고리즘을 제안하였다. 본 시스템은 사용자에게 질의 이미지를 업로드하는 인터페이스를 제공하거나 모양 특징에 기반한 질의를 생성하는 도구를 제공하고 유사도에 따른 이미지를 검색한다. 검색의 편의성을 위해, 웹상에서 잎 모양과 잎차례를 스케치하여 손쉽게 질의할 수 있게 하였다. 실험에서는, 한국에 자생하는 식물 이미지 데이터베이스를 구축하였으며, 질의를 통해 검색된 유사한 이미지의 개수를 기반으로 성능을 평가하였다.
In this paper, we present a leaf image retrieval system that represents and retrieves leaf images based on their shape. For more effective representation of leaf images, we improved an existing MPP algorithm. Also, in order to reduce the response time, we proposed a new dynamic matching algorithm at...
In this paper, we present a leaf image retrieval system that represents and retrieves leaf images based on their shape. For more effective representation of leaf images, we improved an existing MPP algorithm. Also, in order to reduce the response time, we proposed a new dynamic matching algorithm at basically revises the Nearest Neighbor search. The system provides users with an interface for uploading query images or tools to generate queries based on shape features and retrieves images based on their similarity. For convenience, users are allowed to easily query images by sketching leaf shape or leaf arrangement on the web. In the experiment, we constructed an image database of Korean native plants and measured the system performance by counting the number of similar images retrieved for queries.
In this paper, we present a leaf image retrieval system that represents and retrieves leaf images based on their shape. For more effective representation of leaf images, we improved an existing MPP algorithm. Also, in order to reduce the response time, we proposed a new dynamic matching algorithm at basically revises the Nearest Neighbor search. The system provides users with an interface for uploading query images or tools to generate queries based on shape features and retrieves images based on their similarity. For convenience, users are allowed to easily query images by sketching leaf shape or leaf arrangement on the web. In the experiment, we constructed an image database of Korean native plants and measured the system performance by counting the number of similar images retrieved for queries.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서 제안하는 알고리즘의 성능을 분석하기 위해서 이미지 기반의 검색 시스템을 개발하였다. 검색 시스템은 Xeon CPU 2.
본 논문에서는 한국에 자생하는 식물의 잎에 대하여 이러한 조건을 만족하는 검색 시스템을 구현하였다. (그림 1)에서 보는 바와 같이 식물 잎의 경우, 색상이 대부분 초록색이고, 사진으로는 잎의 거칠고 매끈함을 알 수가 없기 때문에, 관찰에 의한 동정(identification)이나 식물명의 결정시, 식물의 색상이나 질감보다는 잎의 모양을 이용하는 것이 더 효과적이다.
본 연구에서는 식물의 잎을 검색하기 위하여 모양을 기반으로 한 이미지 검색 시스템을 구현하였다. 잎 모양을 표현하기 위해 개선된 MPP 알고리즘을 사용하여 이미지의 외곽선에서 우세점을 추출하였으며 검색을 다양화하고 정확도를 높이기 위해 잎차례를 인덱싱에 사용하였다.
본 절에서는 식물의 잎을 검색하기 위한 웹 기반의 인터페이스를 보이고 여러가지 실험결과를 기술하고 평가한다.
제안 방법
검색시간을 최소화하기 위해 동적으로 매칭할 수 있도록 하였다. 우선 식물의 잎이 좌우대칭이라는 특징을 이용하여 우세점들 S) 중에 가장 긴 거리를 갖는 직선(축)을 기준으로 한쪽 면의 점들(을 )만을 이용한다.
또한, 유사도 계산시에 유사도가 특정 임계값을 초과하면 더 이상 매칭 프로세스를 진행하지 않고 다음 이미지의 유사도를 계산한다. 예를 들어 임계값이 200(pixel)이고 우세점 100개중 50번째 점까지의 유사도가 200(pixel)이 넘었을 경우에 매칭을 중단하고 다음 이미지와의 매칭을 시작한다.
비교에 사용된 표현기법으로는 논문에서 제안한 개선된 MPP, MPP, Fourier Descriptor, CSSD, CCD, Moment Invariants 이다. 그림에서 알 수 있듯이 제안한 알고리즘이 다른 알고리즘의 비해 더 좋은 성능을 보이고 있다.
스케치 이미지가 정면이 아닌 0°~90°범위에서 보는 각도가 다르게 묘사되어 있어, 모든 이미지의 보는 각도를 0°로 통일시켜 재포맷화하였다.
차이는 크지 않다는 것을 알 수 있다. 위의 실험 자중에 가장 낮은 평가를 한 5번 실험자와 가장 좋은 평가를 한 6번 실험자를 제외한 8명의 실험자를 대상으로 질의에 따른 유사한 이미지의 개수를 평가하였다.
유사도를 계산하기 위해 2.4절의 (식 5)의 유클리드 거리를 사용하였으며, 아래의 (식 8)과 같이 질의한 이미지의 점들(G과 데이터베이스에 저장된 이미지의 점들(勿과의 거리에서 최소값을 가지는 거리를 이용하여 계산하였다.
포함되어 있다. 이러한 점들을 간결화하기 위해 각 점들의 각도를 계산하여 임계값의 범위를 벗어나는 점들은 병합하였다. 아래의<표 2>는 이러한 점들의 병합 여부를 판단하는 알고리즘이다.
MPP를 찾기 위해서는 우선 그 이미지를 셀 (cell)로 쪼개어 좀 더 단순화된 형태의 매트릭스(matrix)로 만든다. 이렇게 단순화된 매트릭스에서 특정한 각도 이상의 점들을 찾아서 볼록점 (convex)과 오목점 (concave)들을 찾은 후, 이 점들을 순회(travel)하면서 점들의 오목하고 볼록한 특징을 통해 이미지의 형태를 단순화한다. 이때, 이미지의 형태를 결정하는데 중요하지 않은 점들은 제거하며, 단순화된 형태의 매트릭스에서 (X, Y)좌표의 집합이 바로 MPP가 된다.
예를 들어, 잎이 세로인 경우와 가로인 경우, 모양에 대한 표현 값은 동일해야 한다. 이를 위해, 우세점들 간의 거리에서 가장 최대거리에 있는 점 2개를 주맥(主脈, main vein)의 양 끝점으로 간주하고, 두 개의 점을 이은 선을 기준으로 각도를 보정한다. (그림 6)에서처럼 원본이미지 (a)에서 가장 거리가 먼 2개의 점을 이은 선을 기준으로 하여, (b)에서 보는 바와 같이 시계방향으로 각도 0 만큼 회전을 시켜 각도를 보정한다.
한 이미지 검색 시스템을 구현하였다. 잎 모양을 표현하기 위해 개선된 MPP 알고리즘을 사용하여 이미지의 외곽선에서 우세점을 추출하였으며 검색을 다양화하고 정확도를 높이기 위해 잎차례를 인덱싱에 사용하였다. 성능평가에서 본 시스템의 개선된 알고리즘을 사용했을 때 기존의 방법보다 더 좋은 성능을 얻을 수 있었다.
대상 데이터
실험방법은 10명의 참가자에게 10번의 질의를 하고 셀 크기가 5, 7, 9에 대한 결과를 각각 보였다. 가장 유사한 이미지 순서대로 20개를 보였으며, 이 중에 비슷한 이미지의 개수를 측정하였다. (그림 9)는 실험 참여자와 셀 사이즈에 따른 추출 이미지중 유사한 이미지의 개수를 보여주고 있다.
검색의 정확도를 측정하기 위해, 20대의 참가자 10명을 대상으로 실험하였다. 실험방법은 10명의 참가자에게 10번의 질의를 하고 셀 크기가 5, 7, 9에 대한 결과를 각각 보였다.
성능평가를 위해 국내에서 자생하고 있는 식물들을 수록하고 있는 대한식물도감[29]에서 1032종의 잎 이미지를 발췌하여 500x500 픽셀의 크기로 스케치하여 사용하였다. 스케치 이미지가 정면이 아닌 0°~90°범위에서 보는 각도가 다르게 묘사되어 있어, 모든 이미지의 보는 각도를 0°로 통일시켜 재포맷화하였다.
이론/모형
MPP 알고리즘은 MATLAB12기으로 구현하였으며, 아래 의 작업 순서대로 점들의 시퀀스(sequence)를 찾는다.
본 논문에서는 가우시안 마스크를 이용하여 노이즈를 제거한 후, 소벨 마스크와 같은 윤곽선 검출 마스크를 수행하는 캐니 윤곽선 검출(Canny Edge Detection) 알고리즘[16] 을 사용하였다.
본 논문에서는 함수식 5인 유클리드 거리를 사용한다.
알고리즘에서 의 세 점 4尻。의 각도를 도출하기 위해 (식 6)과 같이 코사인 제 2법칙 (the second law of cosines)을 사용하였다.
성능/효과
다섯째, 모양을 표현하는 알고리즘은 계산 비용면에서 효율적이어야 한다. 즉, 인덱싱과 매칭 알고리즘의 시간복잡도 T는 T< Ogogn、)을 만족해야 한다.
둘째, 이미지에 포함될 수 있는 왜곡이나 노이즈가 표현에 영향을 주어서는 안 되며, 단순화 과정에서 무시될 수 있어야 한다.
반면, 저장된 이미지도 노이즈 필터링, 윤곽선 검출, 모양 표현을 거쳐 우세점을 추출한다. 마지막으로, 질의한 이미지의 우세점과 이미지 데이터베이스의 우세점에 대한 각각의 유사도를 계산하여 가장 유사한 순서로 결과를 보여준다.
잎 모양을 표현하기 위해 개선된 MPP 알고리즘을 사용하여 이미지의 외곽선에서 우세점을 추출하였으며 검색을 다양화하고 정확도를 높이기 위해 잎차례를 인덱싱에 사용하였다. 성능평가에서 본 시스템의 개선된 알고리즘을 사용했을 때 기존의 방법보다 더 좋은 성능을 얻을 수 있었다. 향후 연구 과제로는 좀 더 개선된 알고리즘을 개발하고, 잎 모양 뿐만 아니라 잎 내부의 잎맥을 이용하여 검색할 수 있도록 구현하는 것이다.
셋째, 이미지의 이동(translation), 조정(scaling), 회전(rotation), 보는 각도(view angle)의 변환, 좌우 또는 위아래 대칭 (symmetric transformation)에 대해서 표현 값은 변함이 없어야 한다(invariance).
일곱째, 닫힌 곡선(closed curve) 뿐만 아니라 열린 곡선 (open curve)에 대해서도 일관성 있는 표현 기법이 사용되어 야 한다. 닫힌 곡선은 곡선 AiShapeA = {a1, a2 .
후속연구
성능평가에서 본 시스템의 개선된 알고리즘을 사용했을 때 기존의 방법보다 더 좋은 성능을 얻을 수 있었다. 향후 연구 과제로는 좀 더 개선된 알고리즘을 개발하고, 잎 모양 뿐만 아니라 잎 내부의 잎맥을 이용하여 검색할 수 있도록 구현하는 것이다.
참고문헌 (29)
Ballard, D.H. and Brown, C.M. Computer Vision, Prentice-Hall, 1982
Sundar, H., Silver, D., Gagvani, N., Dickinson, S., 'Skeleton based shape matching and retrieval,' Shape Modeling International, p.130, 2003
Nishida, H., 'Structural feature indexing for retrieval of partially visible shapes,' Pattern Recognition, Vol.35, No.1, pp.55-67, 2002
Chang, C., Wenyin, L. and Zhang, H., 'Image Retrieval Based on Region Shape Similarity,' 13th SPIE symposium on Electronic Imaging Storage and Retrieval for Image and Video Databases, 2001
Han, M. H. and Jang, D., 'The use of maximum curvature. points for the recognition of partially occluded objects,' Pattern. Recognition, Vol.23, pp.21-23, 1990
Siddiqi, K., Shokoufandeh, A., Dickinson, SJ., & Zucker, SW., 'Shock Graphs and Shape Matching,' International Journal of Computer Vision, Vol.35, No.1, pp.13-32, 1999
Gottschalk, PG, Turney, JL, Mudge, TN, 'Efficient Recognition of Partially Visible Objects Using a Logarithmic Complexity Matching Technique,' The International Journal of Robotics Research, Vol.8, No.6, pp.110-131, 1989
Bebis, G., Papadourakis, GM. and Orphanoudakis, S., 'Curvature Scale Space Driven Object Recognition with an Indexing Scheme based on Artificial Neural Networks,' Pattern Recognition, Vol.32, pp.1175-1201, 1999
Petrakis, E., Diplaros, A. and Milios, E., 'Matching and Retrieval of Distorted and Occluded Shapes Using Dynamic Programming', IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.24, No.11, pp.1501-1516, 2002
Gonzalez, Rafel C., Woods, Richard C., Digital Image Processing, Addison-Wesley, 1992
Lin, H. J., Kao, Y. T., 'A prompt contour detection method,' International Conference On the Distributed Multimedia Systems, 2001
Michael Heath, et al., 'A Robust Visual Method for Assessing the Relative Performance of Edge Detection Algorithms,' IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.19, No.12, pp.1338-1359, 1997
Mokhtarian F, Abbasi S, Kittler J. 'Efficient and robust retrieval by shape content through curvature scale space,' Int Workshop on Image DataBases and Multimedia Search, Amsterdam, The Netherlands, pp.35-42, 1996
Kurozumi Y., Davis W.A., 'Polygonal approximation by the minimax method,' Computer Vision, Graphics and Image Processing, pp.248-264, 1982
Veltkamp, R., 'Shape matching: similarity measures and algorithms,' Technical Report UU-CS-2001-03, Utrecht University, the Netherlands, 2001
Efrat, A. and Itai, A., 'Improvements on bottleneck matching and related problems using geometry,' The 12th Symposium on Computational Geometry, pp.301-310, 1996
Alt, H., Behrends, B. and Blomer, J., 'Approximate matching of polygonal shapes,' Ann. Math. Artif. Intell., Vol.13, pp.251-266, 1995
The MathWorks-MATLAB and Simulink for Technical Computing http://www.mathworks.com
Indyk, P., Motwani, R., 'Approximate nearest neighbors: towards removing the curse of dimensionality,' The 30 annual ACM symposium on Theory of computing, pp.604-613, 1998
※ AI-Helper는 부적절한 답변을 할 수 있습니다.