경계선 강도를 이용한 허프 변환의 개선

허경용,이광의,우영운,Heo, gyeong-Yong,Lee, Kwang-Eui,Woo, Young-Woon 한국정보통신학회 2006 한국정보통신학회논문지 Vol.10 No.11

디지털 영상에서 기하학적인 요소들을 찾아내는 일은 컴퓨터 비전 분야에서 기본적인 작업 중 하나이며, 허프변환(Hough transform)은 파라미터로 표현되는 기하학적 요소 추출을 위 해 널리 사용되고 있는 방법 중 하나이다. 하지만 허프 변환은 영상의 한 픽셀이 허프 공간의 한 방정식에 대응되는 일대다 특성으로 인해 잡음에 민감한 특성을 갖는다. 이 논문에서는 이러한 잡음 민감성을 줄이는 방법으로 경계선 강도를 이용한 허프 변환을 제안하고, 이를 허프 공간에서의 피크 비(peak ratio)를 이용하여 증명하였다. 또한 직선을 대상으로 한 실험을 통하여 이를 확인하였다. 실험 결과, 제안한 경계선 강도 허프 변환은 기존의 허프 변환에 비해 잡음에 의해 검출되는 직선의 수가 줄어드는 것을 확인할 수 있었다. The detection of geometric primitives from a digital image is one of the basic tasks in computer vision area and the Hough transform is a well-known method for detecting analytical shape represented by a number of free parameters. However the basic property of the Hough transform, the one-to-many mapping from an image space to a Hough space, causes the innate problem, the sensitivity to noise. In this paper, we proposed Edge Strength Hough Transform which uses edge strength to reduce the sensitivity to noise and proved the insensitivity using the ratio of peaks in a Mough space. We also experimented the proposed method on lines and got small number of peaks in a Hough space compared to traditional Hough transform, which supports the noise insensitivity of the proposed method.

경계선 강도 허프 변환에서 직선 왜곡의 최소화 방안

허경용,최세운,박충식,우영운,Heo, Gyeong-Yong,Choe, Se-Woon,Park, Choong-Shik,Woo, Young-Woon 한국정보통신학회 2008 한국정보통신학회논문지 Vol.12 No.2

허프 변환(Hough transform)은 영상에서 몇 개의 파라미터로 표현되는 기하학적 요소 추출을 위해 널리 사용되고 있는 방법 중 하나이다. 하지만 허프 변환은 영상의 한 픽셀이 허프 공간(Hough space)의 한 방정식에 대응되는 일대다 특성으로 인해 잡음에 민감한 특성을 갖는다. 이러한 잡음 민감성은 검출되는 직선의 개수뿐만이 아니라 검출된 직선의 품질에도 영향을 미칠 수 있다. 즉, 실제 직선에서 벗어난 직선이 검출되거나 하나의 실제 직선에 대해 여러 개의 직선이 검출되는 등의 직선 왜곡이 발생할 수 있다. 이러한 직선 왜곡은 잡음 이외에도 허프 공간의 설정, 특히 각 해상도의 설정에 영향을 받는다. 따라서 본 논문에서는 기존의 허프 변환에서 발생하는 이러한 직선 왜곡을 분석하고, 잡음 민감성을 줄이기 위해 제안된 경계선 강도 허프 변환(Edge Strength Hough Transform, ESHT)에서 이러한 왜곡이 적게 발생함을 보인다. 하지만 허프 공간의 크기는 허프 변환 이전에 정해지므로, 정해진 허프 공간에 대해 왜곡의 발생이 최소가 되도록 하는 방법을 제시한다. 또한 경계선 강도 허프 변환의 경계선 확장과 강도 설정 과정을 통해 경계선 강도 허프 변환에서만 발생할 수 있는 직선 왜곡을 분석하고 이를 해결하는 방법을 제시한다. 실험 결과에서는 제시한 방법이 직선의 왜곡이 감소하는 것을 확인하였다. Though the Hough transform(HT) is a well-known method for detecting analytical shape represented by a number of free parameters, the basic property of the HT, the one-to-many mapping from an image spare to a Hough space, causes the innate problem, the sensitivity to noise. This basic problem also deteriorates the quality of detected lines and makes the detected line deviated from the real one or generates some bogus, multiple lines where only one real line exists. The size of Hough space also affects the quality of detected lines. In this paper, we analyzed the line distortions in the traditional Hough transform and showed that the distortions are relieved in the edge strength Hough transform(ESHT), which is a modified HT. However the usage of expanded edge and edge strength in ESHT can cause some new line distortions which do not exist in the HT. These new ones can be solved by a proper setting of decreasing and broadening parameter values and the optimal values can be determined only by some pre-determined values. We also illustrated several examples to show the distortion-decreasing property of ESHT.

커널 밀도 추정을 이용한 Fuzzy C-Means의 초기화

허경용,김광백,Heo, Gyeong-Yong,Kim, Kwang-Baek 한국정보통신학회 2011 한국정보통신학회논문지 Vol.15 No.8

Fuzzy C-Means (FCM)는 군집화를 위해 널리 사용되는 알고리듬 중 하나로 다양한 응용 분야에서 성공적으로 사용되어 왔다. 하지만 FCM은 여러 가지 단점을 가지고 있으며 초기 원형 설정이 그 중 하나이다. FCM은 국부 최적해에 수렴하므로 초기 원형 설정에 따라 군집화의 결과가 달라진다. 따라서 초기 원형의 설정은 군집화 결과 향상을 위해 중요하다. 이 논문에서는 이러한 FCM의 초기 원형 설정 문제를 해결하는 방안으로 커널 밀도 추정을 활용하는 방법을 제안한다. 커널 밀도 추정은 비모수적 분포들에도 사용할 수 있어 국부적인 데이터 밀도 추정에 유용하다. 제안한 방법에서는 커널 밀도 추정을 수행한 후 밀도가 높은 지역에 클러스터의 초기 원형을 설정하고 원형이 설정된 영역의 밀도를 감소시키는 과정을 반복함으로써 효율적으로 초기 원형을 선택할 수 있다. 제안된 방법이 일반적으로 사용되는 무작위 초기화 방법에 비해 효율적이라는 사실은 실험 결과를 통해 확인할 수 있다. Fuzzy C-Means (FCM) is one of the most widely used clustering algorithms and has been used in many applications successfully. However, FCM has some shortcomings and initial prototype selection is one of them. As FCM is only guaranteed to converge on a local optimum, different initial prototype results in different clustering. Therefore, much care should be given to the selection of initial prototype. In this paper, a new initialization method for FCM using kernel density estimation (KDE) is proposed to resolve the initialization problem. KDE can be used to estimate non-parametric data distribution and is useful in estimating local density. After KDE, in the proposed method, one initial point is placed at the most dense region and the density of that region is reduced. By iterating the process, initial prototype can be obtained. The initial prototype such obtained showed better result than the randomly selected one commonly used in FCM, which was demonstrated by experimental results.

잡음 민감성이 개선된 퍼지 주성분 분석

허경용,우영운,김성훈,Heo, Gyeong-Yong,Woo, Young-Woon,Kim, Seong-Hoon 한국정보통신학회 2010 한국정보통신학회논문지 Vol.14 No.5

주성분 분석(PCA)은 데이터의 차원을 줄이면서 최대의 데이터 변이를 보존하는 기법으로 차원 축소나 피처 추출을 위해 널리 사용되고 있다. 하지만 PCA는 잡음에 민감한 단점이 있으며, 이러한 잡음 민감성을 해결하기 위해 여러 가지 PCA 변형이 제안되었다. 그 중 robust fuzzy PCA(RF-PCA)는 퍼지 소속도를 사용하여 잡음의 영향을 효과적으로 줄일 수 있음이 입증되었다. 하지만 RF-PCA 역시 몇 가지 문제점이 있고, 수렴성이 그 중 하나이다. RF-PCA는 소속도와 주성분을 갱신할 때 서로 다른 목적 함수를 사용하므로 수렴 속도가 느리고 구해지는 해가 국부 최적 해임을 보장하지 않는다. 이 논문에서는 RF-PCA의 문제점을 해결하기 위해 하나의 목적 함수를 이용해 소속도와 주성분을 갱신할 수 있는 방법을 제안한다. 제안한 방법, RF-PCA2는 반복 최적화를 이용함으로써 국부 최적해에 수렴함을 보장하며, RF-PCA에 비해 빠른 수렴 속도를 가지고, 잡음 민감성이 줄어든다. 이러한 사실들은 실험 결과를 통해 확인할 수 있다. Principal component analysis (PCA) is a well-known method for dimension reduction while maintaining most of the variation in data. Although PCA has been applied to many areas successfully, it is sensitive to outliers. Several variants of PCA have been proposed to resolve the problem and, among the variants, robust fuzzy PCA (RF-PCA) demonstrated promising results. RF-PCA uses fuzzy memberships to reduce the noise sensitivity. However, there are also problems in RF-PCA and the convergence property is one of them. RF-PCA uses two different objective functions to update memberships and principal components, which is the main reason of the lack of convergence property. The difference between two functions also slows the convergence and deteriorates the solutions of RF-PCA. In this paper, a variant of RF-PCA, called RF-PCA2, is proposed. RF-PCA2 uses an integrated objective function both for memberships and principal components. By using alternating optimization, RF-PCA2 is guaranteed to converge on a local optimum. Furthermore, RF-PCA2 converges faster than RF-PCA and the solutions found are more similar to the desired solutions than those of RF-PCA. Experimental results also support this.

X-means 확장을 통한 효율적인 집단 개수의 결정

허경용,우영운,Heo, Gyeong-Yong,Woo, Young-Woon 한국정보통신학회 2008 한국정보통신학회논문지 Vol.12 No.4

K-means는 알고리즘의 단순함과 효율적인 구현이 가능함으로 인해 군집화를 위해 현재까지 널리 사용되는 방법 중 하나이다. 하지만 K-means는 집단의 개수가 사전에 결정되어야 하는 근본적인 문제점이 있다. 이 논문에서는 BIC(Bayesian information criterion) 점수를 이용하여 효율적으로 집단의 개수를 추정할 수 있는 X-means 알고리즘을 확장한 두 가지 알고리즘을 제안한다. 제안한 방법은 기본적으로 X-means 방법을 따르면서 집단이 임의의 분산 행렬을 가질 수 있도록 함으로써 X-means 알고리즘이 원형 집단만을 허용함에 따른 over-fitting을 개선한다. 제안한 방법은 하나의 집단에서 시작하여 계속해서 집단을 나누어가는 하향식 방법으로, BIC score를 최대로 증가시키는 집단을 분할해 나간다. 제안한 알고리즘은 Modified X-means(MX-means)와 Generalized X-means(GX-means)의 두 가지로, 전자는 K-means 알고리즘을, 후자는 EM 알고리즘을 사용하여 현재 주어진 집단들에서 최적의 분할을 찾아낸다. MX-means는 GX-means보다 그 속도에서 앞서지만 집단들이 중첩 된 경우에는 올바른 집단을 찾아낼 수 없는 단점이 있다. GX-means는 실행 속도가 느린 단점이 있지만 집단들이 중첩된 경우에도 안정적으로 집단들을 찾아낼 수 있다. 이러한 점들은 일련의 실험을 통해서 확인할 수 있으며, 제안한 방법들이 기존의 방법들에 비해 나은 성능을 보임을 확인할 수 있다. K-means is one of the simplest unsupervised learning algorithms that solve the clustering problem. However K-means suffers the basic shortcoming: the number of clusters k has to be known in advance. In this paper, we propose extensions of X-means, which can estimate the number of clusters using Bayesian information criterion(BIC). We introduce two different versions of algorithm: modified X-means(MX-means) and generalized X-means(GX-means), which employ one full covariance matrix for one cluster and so can estimate the number of clusters efficiently without severe over-fitting which X-means suffers due to its spherical cluster assumption. The algorithms start with one cluster and try to split a cluster iteratively to maximize the BIC score. The former uses K-means algorithm to find a set of optimal clusters with current k, which makes it simple and fast. However it generates wrongly estimated centers when the clusters are overlapped. The latter uses EM algorithm to estimate the parameters and generates more stable clusters even when the clusters are overlapped. Experiments with synthetic data show that the purposed methods can provide a robust estimate of the number of clusters and cluster parameters compared to other existing top-down algorithms.

PFCM 클러스터링 기법의 개선

허경용,최세운,우영운,Heo, Gyeong-Yong,Choe, Se-Woon,Woo, Young-Woon 한국정보통신학회 2009 한국정보통신학회논문지 Vol.13 No.1

Cluster analysis or clustering is a kind of unsupervised learning method in which a set of data points is divided into a given number of homogeneous groups. Fuzzy clustering method, one of the most popular clustering method, allows a point to belong to all the clusters with different degrees, so produces more intuitive and natural clusters than hard clustering method does. Even more some of fuzzy clustering variants have noise-immunity. In this paper, we improved the Possibilistic Fuzzy C-Means (PFCM), which generates a membership matrix as well as a typicality matrix, using Gath-Geva (GG) method. The proposed method has a focus on the boundaries of clusters, which is different from most of the other methods having a focus on the centers of clusters. The generated membership values are suitable for the classification-type applications. As the typicality values generated from the algorithm have a similar distribution with the values of density function of Gaussian distribution, it is useful for Gaussian-type density estimation. Even more GG method can handle the clusters having different numbers of data points, which the other well-known method by Gustafson and Kessel can not. All of these points are obvious in the experimental results. 클러스터링은 주어진 데이터 포인트들을 주어진 개수의 그룹으로 나누는 비지도 학습의 한 방법이다. 클러스터링의 방법 중 하나로 널리 알려진 퍼지 클러스터링은 하나의 포인트가 모든 클러스터에 서로 다른 정도로 소속될 수 있도록 함으로써 하나의 클러스터에만 속할 수 있도록 하는 K-means와 같은 방법에 비해 자연스러운 클러스터 형태의 유추가 가능하고, 잡음에 강한 장점이 있다. 이 논문에서는 기존의 퍼지 클러스터링 방법 중 소속도(membership)와 전형성(typicality)을 동시에 계산해 낼 수 있는 Possibilistic Fuzzy C-Means(PFCM) 방법에 Gath-Geva(CG)의 방법을 적용하여 PFCM을 개선한다. 제안한 방법은 PFCM 장점을 그대로 가지면서도, GG의 거리 척도에 의해 클러스터들 사이의 경계를 강조함으로써 분류 목적에 적합한 소속도를 계산할 수 있으며 전형성은 가우스 형태의 분포에서 생성된 포인트들의 분포 함수를 정확하게 모사함으로써 확률 밀도 추정의 방법으로도 사용될 수 있다. 또한 GG 방법은 Gustafson-Kessel 방법과 달리 클러스터에 포함된 포인트의 개수가 확연히 차이나는 경우에도 정확한 결과를 얻을 수 있다. 이러한 사실들은 실험 결과를 통해 확인할 수 있다.

Fuzzy c-means의 문제점 및 해결 방안

허경용(Gyeong-Yong Heo),서진석(Jin-Seok Seo),이임건(Im-Geun Lee) 한국컴퓨터정보학회 2011 韓國컴퓨터情報學會論文誌 Vol.16 No.1

클러스터링은 주어진 데이터 집합을 균일한 특성을 가지는 몇 개의 그룹으로 묶는 대표적인 비교사 학습 방법 중 하나로 지금까지 다양한 형태의 알고리듬이 개발되어 다양한 응용 분야에서 사용되어 왔다. 이 중 fuzzy c-means (FCM)는 분할 기반의 클러스터링 기법에 속하는 알고리듬으로 1970년대에 정립된 이후 지금까지 사용되고 있는 대표적인 클러스터링 알고리듬 중의 하나이다. 하지만 FCM에는 여러 가지 문제점이 있으며 이를 해결하기 위해 지금까지도 다양한 FCM의 변형이 제안되고 있다. 이 논문에서는 먼저 FCM의 문제점을 살펴보고 이를 해결하기 위해 제안된 방법들을 통해 연구 방향을 제시하고자 한다. FCM의 문제점을 해결하고자 하는 대부분의 FCM 변형은 주어진 문제 영역의 지식을 활용하고 있다. 하지만 이 논문에서는 문제 영역을 한정하지 않고 모든 문제에 적용할 수 있는 일반적인 방안을 제시하는데 초점을 둔다. 제시하는 방안은 앞으로 더 많은 연구가 필요하지만 클러스터링을 연구하고자 하는 이들에게 최근의 연구 동향과 더불어 출발점을 제시할 수 있을 것으로 기대한다. Clustering is one of the well-known unsupervised learning methods, in which a data set is grouped into some number of homogeneous clusters. There are numerous clustering algorithms available and they have been used in various applications. Fuzzy c-means (FCM), the most well-known partitional clustering algorithm, was established in 1970's and still in use. However, there are some unsolved problems in FCM and variants of FCM are still under development. In this paper, the problems in FCM are first explained and the available solutions are investigated, which is aimed to give researchers some possible ways of future research. Most of the FCM variants try to solve the problems using domain knowledge specific to a given problem. However, in this paper, we try to give general solutions without using any domain knowledge. Although there are more things left than discovered, this paper may be a good starting point for researchers newly entered into a clustering area.

Support Vector Machine을 이용한 문맥 인지형 융합

허경용(Gyeong-Yong Heo),김성훈(Seong-Hoon Kim) 한국컴퓨터정보학회 2014 韓國컴퓨터情報學會論文誌 Vol.19 No.6

앙상블 분류기는 여러 개의 분류기에서의 예측 결과를 결합함으로써 단일 분류기에 비해 신뢰성 높은 예측 결과를 얻을 수 있는 방법으로 널리 사용되고 있다. 앙상블 분류기를 위해서는 여러 가지 방법이 사용되고 있으며 흔히 사용되는 방법으로는 부스팅이 있다. 하지만 부스팅은 단계적인 학습을 통해 이전 단계에서 잘못 분류된 샘플들을 다음 단계에서 다시 분류하는 방식으로 이전 단계로의 피드백이 불완전한 순차적인 방법이라는 한계가 있다. 이 논문에서는 단일 분류기 중 가장 성능이 좋은 것으로 알려진 SVM을 기본분류기로 사용하여 동시에 여러개의 SVM을 학습하는 문맥 감지형 SVM 앙상블알고리즘을 제안한다. 제안하는 방법에서는 특징 공간을 문맥으로 나누는 클러스터링과 SVM 학습을 동시에 진행하므로 특징 공간 분할과 학습이 서로의 결과를 사용할 수 있어 기존 앙상블학습에 비해 더 나은 결과를 얻을 수 있으며 이는 실험 결과를 통해 확인할 수 있다. An ensemble classifier system is a widely-used multi-classifier system, which combines the results from each classifier and, as a result, achieves better classification result than any single classifier used. Several methods have been used to build an ensemble classifier including boosting, which is a cascade method where misclassified examples in previous stage are used to boost the performance in current stage. Boosting is, however, a serial method which does not form a complete feedback loop. In this paper, proposed is context sensitive SVM ensemble (CASE) which adopts SVM, one of the best classifiers in term of classification rate, as a basic classifier and clustering method to divide feature space into contexts. As CASE divides feature space and trains SVMs simultaneously, the result from one component can be applied to the other and CASE achieves better result than boosting. Experimental results prove the usefulness of the proposed method.

행렬기반의 정합 알고리듬에 의한 음악 기호의 인식

허경용(Heo Gyeong Yong),장경식(Jang Kyung Sik),장문익(Jang Moon IK),김재희(Kim Jai Hie) 한국정보처리학회 1998 정보처리학회논문지 Vol.5 No.8

In pattern recognition and image analysis applications, a graph is a useful tool for complex object representation and recognition. However it takes much time to pair proper nodes between the prototype graph and an input data graph. Futhermore it is difficult to decide whether the two graphs in a class are the same because real images are degraded in general by noise and other distortions. In this paper we propose a matching algorithm using a matrix. The matrix is suitable for simple and easily understood representation and enables the ordering and matching process to be convenient due to its predefined matrix manipulation. The nodes which constitute a graph are ordered in the matrix by their geometrical positions and this makes it possible to save much comparison time for finding proper node pairs. For the classification, we defined a distance measure that reflects the symbol's structural aspect that is the sum of the node distance and the relation distance; the former is from the parameters describing the node shapes, the latter from the relations with other node in the matrix. We also introduced a subdivision operation to compensate node merging which is mainly due to the preprocessing error. The proposed method is applied to the recognition of musical symbols and the result is given. The result shows that almost all, except heavily degraded symbols are recognized, and the recognition rate is approximately 95 percent.

커널을 이용한 전역 클러스터링의 비선형화

허경용(Gyeong-Yong Heo),김성훈(Seong-Hoon Kim),우영운(Young-Woon Woo) 한국컴퓨터정보학회 2010 韓國컴퓨터情報學會論文誌 Vol.15 No.4

Fuzzy c-means(FCM)는 퍼지 집합을 응용한 간단하지만 효율적인 클러스터링 방법 중 하나이다. FCM은 여러 응용 분야에서 성공적으로 활용되어 왔지만, 초기화와 잡음에 민감하고 볼록한 형태의 클러스터들만 다룰 수 있는 문제점이 있다. 이 논문에서는 이러한 FCM의 문제점을 해결하기 위해 전역 클러스터링(global clustering) 기법과 커널 클러스터링(kernel clustering) 기법을 결합하여 새로운 비선형 클러스터링 기법인 커널 전역 FCM(kernel global fuzzy c-means, KG-FCM)을 제안한다. 전역 클러스터링은 클러스터링의 초기화를 위한 방법 중 하나로, 순차적으로 클러스터를 하나씩 추가함으로써 초기화에 민감한 FCM의 한계를 극복할 수 있도록 해준다. FCM의 잡음 민감성과 볼록한 클러스터들만 다룰 수 있는 한계를 극복하기 위한 방법은 여러 가지가 있으며 커널 클러스터링이 그 중 하나이다. 커널 클러스터링은 사용하는 커널을 바꿈으로써 쉽게 확장이 가능하므로 이 논문에서는 커널 클러스터링을 사용하였다. 두 방법을 결합함으로써 제안한 방법은 위에서 언급한 문제점들을 해결할 수 있으며, 이는 가상 및 실제 데이터를 이용한 실험 결과를 통해 확인할 수 있다. Fuzzy c-means (FCM) is a simple but efficient clustering algorithm using the concept of a fuzzy set that has been proved to be useful in many areas. There are, however, several well known problems with FCM, such as sensitivity to initialization, sensitivity to outliers, and limitation to convex clusters. In this paper, global fuzzy c-means (G-FCM) and kernel fuzzy c-means (K-FCM) are combined to form a non-linear variant of G-FCM, called kernel global fuzzy c-means (KG-FCM). G-FCM is a variant of FCM that uses an incremental seed selection method and is effective in alleviating sensitivity to initialization. There are several approaches to reduce the influence of noise and accommodate non-convex clusters, and K-FCM is one of them. K-FCM is used in this paper because it can easily be extended with different kernels. By combining G-FCM and K-FCM, KG-FCM can resolve the shortcomings mentioned above. The usefulness of the proposed method is demonstrated by experiments using artificial and real world data sets.