K-평균 알고리즘(K-means algorithm)은 주어진 데이터를 k개의 클러스터로 묶는 알고리즘으로, 각 클러스터와 거리 차이의 분산을 최소화하는 방식으로 동작한다.
이 알고리즘은 자율 학습의 일종으로, 레이블이 달려 있지 않은 입력 데이터에 레이블을 달아주는 역할을 수행한다.
이 알고리즘은 EM 알고리즘을 이용한 클러스터링과 비슷한 구조를 가지고 있다.
알고리즘 순서만 보면..
1. 각 점들을 k개 집합으로 나눈다. 이때 임의로 나누거나, 어떤 휴리스틱 기법을 사용할 수도 있다.
2. 그 다음 각 집합의 무게 중심을 구한다.
3. 각각의 점들을 방금 구한 무게중심 가운데 제일 가까운 것에 연결지음으로써 새로이 집합을 나눌 수 있다.
4. 이 작업(2,3)을 반복하면 점들이 소속된 집합을 바꾸지 않거나, 무게중심이 변하지 않는 상태로 수렴될 수 있다.
자세한 알고리즘 설명은 다음을 참조
example.1
아래의 이미지를 사용하여 하얀 타원의 크기를 기준으로 k-means clustering 을 실행해 본다.
cv::Mat source = cv::cvarrToMat(img);
cv::Mat output(source);
cv::Mat sourceGray;
cv::cvtColor(source, sourceGray, CV_RGB2GRAY);
cv::blur(sourceGray, sourceGray, cv::Size(3, 3));
cv::Mat detectedEdges;
int lowThreshold = 50;
int ratio = 3;
int kernelSize = 3;
cv::Canny(sourceGray, detectedEdges, lowThreshold, lowThreshold * ratio, kernelSize);
int width = detectedEdges.cols;
int height = detectedEdges.rows;
std::vector<Target> candiatesTargets;
// 후보 타겟 선정;
{
std::vector<std::vector<cv::Point>> contours;
std::vector<cv::Vec4i> hierarchy;
cv::findContours(detectedEdges, contours, hierarchy, CV_RETR_TREE, CV_CHAIN_APPROX_NONE, cv::Point(0, 0));
std::vector<cv::RotatedRect> minRect(contours.size());
std::vector<cv::RotatedRect> minEllipse(contours.size());
for (int i = 0; i < contours.size(); i++)
{
minRect[i] = cv::minAreaRect(cv::Mat(contours[i]));
if (contours[i].size() <= 5) continue;
minEllipse[i] = cv::fitEllipse(cv::Mat(contours[i]));
if (hierarchy[i][2] != -1)
{
//ellipse(output, minEllipse[i], cv::Scalar(0, 255, 0), 1, 8);
}
else
{
float w = minEllipse[i].size.width;
float h = minEllipse[i].size.height;
if (w > 50 || w < 7) continue;
if (h > 50 || h < 7) continue;
float temp_ratio = w / h;
if (temp_ratio > 2 || temp_ratio < 0.5) continue; // 좌우로 긴 모양;
//ellipse(output, minEllipse[i], cv::Scalar(0, 0, 255), 1, 8);
Target t;
t.ellipse = minEllipse[i];
candiatesTargets.push_back(t);
}
}
}
// clustering - random partition
const int numCandiates = candiatesTargets.size();
const int K = 5;
const int maxIter = 20;
cv::Vec2f k_ellipseSize[K];
cv::Vec2f k_ellipseSize_backup[K];
int cntK[K] = { 0, };
// 초기화, 랜덤 배분;
for (int i = 0; i < numCandiates; i++)
{
candiatesTargets[i].k = -1;
cv::Vec2i dxy(candiatesTargets[i].ellipse.size.width, candiatesTargets[i].ellipse.size.height);
k_ellipseSize[i % K][0] += (float)dxy[0]; // 원이 발견된 순서대로 번갈아가며 K 번째에 넣는다;
k_ellipseSize[i % K][1] += (float)dxy[1];
cntK[i % K]++;
}
for (int i = 0; i < K; i++)
{
if (cntK[i] == 0) continue; // 원이 하나도 없을때;
k_ellipseSize[i] /= (float)cntK[i];
}
int turn = 0;
while (1)
{
for (int i = 0; i < numCandiates; i++)
{
cv::Vec2i dxy(candiatesTargets[i].ellipse.size.width, candiatesTargets[i].ellipse.size.height);
// 각 집합의 평균 크기와 자신의 크기가 가장 비슷한 집합으로 옮긴다;
float min = FLT_MAX;
for (int _k = 0; _k < K; _k++)
{
cv::Vec2f _dxy;
_dxy[0] = (float)dxy[0] - k_ellipseSize[_k][0];
_dxy[1] = (float)dxy[1] - k_ellipseSize[_k][1];
float d = (_dxy[0]) * (_dxy[0]) + (_dxy[1]) * (_dxy[1]);
if (min > d)
{
min = d;
candiatesTargets[i].k = _k;
}
}
}
// 초기화;
for (int i = 0; i < K; i++)
{
k_ellipseSize[i] = cv::Vec2f(0.f, 0.f);
cntK[i] = 0;
}
// 집합의 평균값을 다시 계산;
for (int i = 0; i < numCandiates; i++)
{
if (candiatesTargets[i].k < 0) continue;
cv::Vec2i dxy(candiatesTargets[i].ellipse.size.width, candiatesTargets[i].ellipse.size.height);
k_ellipseSize[candiatesTargets[i].k][0] += (float)dxy[0];
k_ellipseSize[candiatesTargets[i].k][1] += (float)dxy[1];
cntK[candiatesTargets[i].k] += 1;
}
bool re = true;
for (int i = 0; i < K; i++)
{
if (cntK[i] == 0) continue;
k_ellipseSize[i] /= (float)cntK[i];
// 각 집합의 평균값이 거의 변동이 없으면 re = true로 셋하고 while문을 빠져나간다;
if (fabs(k_ellipseSize_backup[i][0] - k_ellipseSize[i][0]) > 0.001 && fabs(k_ellipseSize_backup[i][1] - k_ellipseSize[i][1]) > 0.001) re = false;
}
if (re) break;
if (turn > maxIter) break;
for (int i = 0; i < K; i++)
{
k_ellipseSize_backup[i] = k_ellipseSize[i];
}
turn++;
}
// 크기 순서대로 k를 정렬;
{
std::vector<std::pair<int, float>> kList;
for (int i = 0; i < K; i++)
{
kList.push_back(std::pair<int, float>(i, k_ellipseSize[i][0] * k_ellipseSize[i][0] + k_ellipseSize[i][1] * k_ellipseSize[i][1]));
}
std::sort(kList.begin(), kList.end(), [](std::pair<int, float>& a, std::pair<int, float>& b){ return a.second > b.second; });
for (int i = 0; i < numCandiates; i++)
{
if (candiatesTargets[i].k < 0) continue;
for (int _k = 0; _k < K; _k++)
{
if (candiatesTargets[i].k == kList[_k].first)
{
candiatesTargets[i].k = _k;
break;
}
}
}
}
cv::Scalar cols[7];
cols[0] = cv::Scalar(0, 0, 255);
cols[1] = cv::Scalar(0, 255, 255);
cols[2] = cv::Scalar(0, 255, 0);
cols[3] = cv::Scalar(255, 255, 0);
cols[4] = cv::Scalar(255, 0, 0);
cols[5] = cv::Scalar(255, 0, 255);
cols[6] = cv::Scalar(255, 255, 255);
for (int i = 0; i < numCandiates; i++)
{
ellipse(output, candiatesTargets[i].ellipse, cols[candiatesTargets[i].k], 2, 8);
}
끝.
댓글 없음:
댓글 쓰기