Clustering is usually formulated as an optimization problem with objective functions which have several local minima. Real image segmentation techniques using numerous control parameters may not apply several images uniformly because the parameters interact in a nonlinear fashion. Therefore, most of results are not always crisp nor correct
In this thesis, we propose new clustering and image segmentation method based on genetic algorithm to solve those problems. The genetic algorithm is used as a tool to search a good or usable clustering and image segmentation, which maximizes the quality of regions or clusters generated by split-and-merge processing.
For clustering, we propose new measure function based on structural relationship by the nearest neighbor clusters, and by a degree of relative separations among clusters. Furthermore, we propose an objective function for image segmentation which measures a degree of separation and compactness between and within finely segmented regions, and an edge strength along boundaries of all regions. These measures based on the fuzzy decision by fuzzy membership function, might be used in many applications such as pattern recognition, classification and image understanding as well as to image segmentation.
To efficiently apply the clustering and image segmentation, we newly modify several operations of the existed genetic operators, and propose new genetic model which is elite-based subpopulation model to improve the performance of the genetic algorithm.
We present several experimental results to demonstrate the capability of the proposed approach. The new approach provides useful results without the need for critical parameters or threshold values, iterative visual interaction, or a priori knowledge of test pattern and image.
일반적으로, 클러스터링은 유사한 성질을 갖는 데이타 패턴끼리 서로 결합하여 하나의 집합을 형성하는 알고리즘으로 패턴인식이나 특징추출, 최적화 문제 등 다방면에 이용된다. 그러나 가장 널리 알려진 Fuzzy-C-Means(FCM) 알고리즘은 항상 지역국부(local optimum)에 빠지는 성질, 즉 최적의 해를 찾을 수 없는 단점을 가지고 있다. 또한 영상분할문제에 있어서는 그 영상 특징들이 애매모호(ambiguity)하고, 비선형 특성과 불완전한 성질을 가지기 때문에 이 문제를 불확실성(uncertainty) 문제로 정의하고 있다.
본 논문은 이러한 여러가지 문제점들을 개선하기 위한 접근방식으로써, 퍼지 개념에 기반을 둔 유전자 알고리즘을 이용하여 새로운 클러스터링과 영상분할 기법을 제안하고 있다. 먼저, 유전자 알고리즘에서의 목적함수(objective function)를 정의하기 위해 주변 클러스터들간의 기하학적 성질과 상대적 분리정도, 이웃하는 클러스터의 정의등을 통해 클러스터의 결합을 위한 결정기준을 정의하였다. 영상분할에서는, 영상 분할 정도를 평가하기 위해, 영역간의 인접 정도와 에지 강도를 이용하여 퍼지 개념에 기반을 둔 새로운 목적함수를 정의하며, 이 함수를 유전자 알고리즘내 적합도(fitness)와 영상분할 과정에서 영역들을 분할할 것인지 혹은 결합할 것인지를 결정하는 기준으로 사용한다. 그리고 임의탐색 및 동시 처리가 가능한 유전자 알고리즘을 통해 특별한 결정 파라메터, 분할과정에서의 지식 정보, 사람의 주관적인 판단없이 자율적으로 영상을 분할하게 된다.
또한 유전자 알고리즘에서 지역적 인접성이 고려된 교접 동작기와 영상 영역의 결합과 분할이 동적으로 일어나는 돌연변이 동작기를 새롭게 정의하였으며, 엘리터(elite)에 기반을 둔 부 모집단 (subpopulation)에 의한 병렬처리 알고리즘을 제안하였다.
제안된 분할 알고리즘을 실험하기 위해 널리 알려진 클러스터 데이타와 하나의 영상을 다양하게 변화시킨 영상, Lena 및 자연 영상을 가지고 효과적인 클러스터링과 영상 분할 과정을 보이고, 유전자 알고리즘에 의해 발생되는 여러가지 현상을 분석하였다.
