Python과 OpenCV – 52 : OpenCV에서 K-Means 군집화(Clustering)

이 글의 원문은 https://opencv-python-tutroals.readthedocs.io/en/latest/py_tutorials/py_ml/py_kmeans/py_kmeans_opencv/py_kmeans_opencv.html 입니다.

OpenCV에서 K-Means 알고리즘을 이용한 데이터 군집화는 cv2.kmeans() 함수를 통해 이용 됩니다. 이 함수에 대한 인자는 다음과 같습니다.

  1. samples : np.float32 데이타 타입이며, 각 피쳐(Feature)는 단일 열(Column)으로 저장되어져 있어야 합니다.
  2. nclusters(K) : 군집화할 개수
  3. criteria : 반복을 종료할 조건입니다. 조건이 만족되면 알고리즘의 반복은 중지됩니다. 3개의 인자를 갖는 튜플(Tuple)이며, (type, max_iter, epsilon)입니다. 각각의 대한 인자는 다음과 같습니다.
    • type : 종료 조건의 타입으로 cv2.TERM_CRITERIA_EPS는 주어진 정확도(epsilon 인자)에 도달하면 반복을 중단하고, cv2.TERM_CRITERIA_MAX_ITER는 max_iter 인자에 지정된 횟수만큼 반복하고 중단합니다. cv2.TERM_CRITERIA_EPS + cv2.TERM_CRITERIA_MAX_ITER를 조합해 사용하면 두가지 조건 중 하나가 만족되면 반복이 중단됩니다.
    • max_iter : 최대 반복할 횟수(정수형 타입)
    • epsilon : 정확도
  4. attempts : 다른 초기 라벨링을 사용하면서 실행되는 알고리즘의 실행 횟수를 지정하는 플래그. 알고리즘은 최적의 컴팩트함(Compactness)을 만드는 라벨을 반환합니다. 이 컴팩트함은 출력으로 반환됩니다.
  5. flags : 초기값을 잡을 중심에 대한 플래그로써 cv2.KMEANS_PP_CENTERS와 cv2.KMEANS_RANDOM_CENTERS 중 하나가 사용됩니다.

이 함수의 반환값은 다음과 같습니다.

  1. compactness : 각 포인트와 군집화를 위한 중심 간의 거리의 제곱의 합
  2. labes : 라벨에 대한 배열이며, ‘0’, ‘1’ 같이 이전 글에서 언급한 내용과 같음.
  3. centers : 클러스터의 중심이 저장된 배열

이제 3가지 예를 통해 K-Means 알고리즘이 어떻게 OpenCV에서 사용되는지 살펴봅시다.

1. 하나의 특징(Feature)을 가지는 데이터

오직 하나의 특징을 가지는 데이터, 예를 들어 1차원 데이터 셋을 봅시다. 그러니까 T셔츠의 크기를 결정하기 위해 사람의 키에 대한 특징만을 고려하는 것입니다.

데이터를 생성하고 Matplotlib으로 표시해 보면..

import numpy as np
import cv2
from matplotlib import pyplot as plt

x = np.random.randint(25,100,25) 
y = np.random.randint(175,255,25)
z = np.hstack((x,y))
z = z.reshape((50,1))
z = np.float32(z)
plt.hist(z,256,[0,256]),plt.show()

크기 50개의 배열 z가 있으며, 구성 요소의 값은 0~255 사이입니다. z를 단일 열(column)로 구성합니다. 마지막으로 데이터의 타입을 np.float32로 변환합니다. 결과는 다음과 같습니다.

이제, K-Means 함수를 적용해 봅시다. 알고리즘 종료에 대한 기준 조건을 정해야 합니다. 여기서 기준은 10반 반복과 정확도(epsilon)은 1.0으로 정합니다.

# Define criteria = ( type, max_iter = 10 , epsilon = 1.0 )
criteria = (cv2.TERM_CRITERIA_EPS + cv2.TERM_CRITERIA_MAX_ITER, 10, 1.0)

# Set flags (Just to avoid line break in the code)
flags = cv2.KMEANS_RANDOM_CENTERS

# Apply KMeans
compactness,labels,centers = cv2.kmeans(z,2,None,criteria,10,flags)

위 예제의 cv2.kmeans 함수는 compactness와 labels, centers 변수에 반환값을 넘겨줍니다. 이 경우 centers는 57.92과 114.5이며, labels에는 각 요소에 대해 ‘0’, ‘1’ 중에 하나의 값으로 분류된 라벨값입니다. 여기서 이 라벨값을 기반으로 데이터를 A와 B 변수로 나눠봅시다.

A = z[labels==0]
B = z[labels==1]

그리고 A와 B를 각각 파란색과 빨간색으로 표시하고, 군집화된 중심을 노란색으로 표시해 봅시다.

# Now plot 'A' in red, 'B' in blue, 'centers' in yellow
plt.hist(A,256,[0,256],color = 'r')
plt.hist(B,256,[0,256],color = 'b')
plt.hist(centers,32,[0,256],color = 'y')
plt.show()

결과는 아래와 같습니다.

2. 여러 개의 특징(Feature)을 가지는 데이터

이전 예에서, T셔츠에 대해 오직 키에 대한 특징점만을 고려했습니다. 여기서는 키와 몸무게처럼 2개의 특징점을 고려해 봅시다.

이전 경우에서, 입력 데이터를 단일 열(column) 벡터로 구성했다는 것을 기억해야 합니다. 각 특징은 열로 정렬되어 잇어야 합니다. 예를 들어서, 이 경우 50명의 사람에 대해 키와 몸무게 값으로 구성된 50×2 크기의 테스트 데이터를 구성합니다. 첫번째 열(Column)은 50명에 대한 키 값이고 두번째 열은 이들의 키값입니다. 첫번째 행(Row)는 첫번째 사람의 키와 몸무게 값입니다. 즉, 아래 그림과 같은 구성입니다.

바로 코드를 보면..

import numpy as np
import cv2
from matplotlib import pyplot as plt

X = np.random.randint(25,50,(25,2))
Y = np.random.randint(60,85,(25,2))
Z = np.vstack((X,Y))

# convert to np.float32
Z = np.float32(Z)

# define criteria and apply kmeans()
criteria = (cv2.TERM_CRITERIA_EPS + cv2.TERM_CRITERIA_MAX_ITER, 10, 1.0)
ret,label,center=cv2.kmeans(Z,2,None,criteria,10,cv2.KMEANS_RANDOM_CENTERS)

# Now separate the data, Note the flatten()
A = Z[label.ravel()==0]
B = Z[label.ravel()==1]

# Plot the data
plt.scatter(A[:,0],A[:,1])
plt.scatter(B[:,0],B[:,1],c = 'r')
plt.scatter(center[:,0],center[:,1],s = 80,c = 'y', marker = 's')
plt.xlabel('Height'),plt.ylabel('Weight')
plt.show()

결과는 다음과 같습니다.

3. 색상 양자화(Color Quantization)

색상 양자화는 이미지에서 사용하는 색상의 수를 줄이는 처리입니다. 이러한 처리를 하는 목적 중 하나는 사용하는 메모리를 줄이기 위해서입니다. 색상 양자화를 위해 K-Means 클러스터링을 활용해 보겠습니다.

새롭게 추가되는 새로운 내용은 없습니다. 특징점은 3개인데, 바로 R, G, B입니다. 이미지의 화소 데이터를 Mx3 배열로 만다는데, M은 이미지의 화소 개수입니다. 클러스터링 이후에, 중심점(이 값 역시도 R, G, B 임)값으로 해당 소속되는 화소의 값을 변경합니다. 그리고 다시 Mx3 배열을 원래 이미지의 크기로 재구성하면 됩니다. 코드는 다음과 같습니다.

import numpy as np
import cv2

img = cv2.imread('./data/harleyQuinnA.jpg')
Z = img.reshape((-1,3))

# convert to np.float32
Z = np.float32(Z)

# define criteria, number of clusters(K) and apply kmeans()
criteria = (cv2.TERM_CRITERIA_EPS + cv2.TERM_CRITERIA_MAX_ITER, 10, 1.0)
K = 7
ret,label,center=cv2.kmeans(Z,K,None,criteria,10,cv2.KMEANS_RANDOM_CENTERS)

# Now convert back into uint8, and make original image
center = np.uint8(center)
res = center[label.flatten()]
res2 = res.reshape((img.shape))

cv2.imshow('res2',res2)
cv2.waitKey(0)
cv2.destroyAllWindows()

이미지를 7개의 색상만으로 구성되도록 양자화하는 것으로 결과는 다음과 같습니다.

Python과 OpenCV – 51 : K-Means 군집화(Clustering)의 이해

이 글의 원문은 https://opencv-python-tutroals.readthedocs.io/en/latest/py_tutorials/py_ml/py_kmeans/py_kmeans_understanding/py_kmeans_understanding.html 입니다.

이 글은 K-Means 클러스터링에 대한 개념을 예를 통해 설명합니다.

티셔츠를 만다는 어떤 회사가 있다고 합시다. 이 회사는 새로운 티셔츠를 만들어 시장에 뿌리려고 합니다. 분명이 이 회사는 모든 사람들이 만족하는 다양한 티셔츠 사이즈를 생산해야 합니다. 그래서 이 회사는 사람들의 키와 몸무게의 데이터를 수집해서 아래처럼 그래프로 표현 했습니다.

회사는 모든 사이즈에 대한 티셔츠를 만들 수는 없습니다. 대신에 작은 사이즈, 중간 사이즈, 큰 사이즈와 같이 3가지 사이즈를 만들고 모든 사람이 이 셋 중에 하나를 골라 만족하기를 기대합니다. 사람들을 이 3개의 그룹으로 나누는 것은 K-Means 클러스터링을 통해 가능하며, 이 알고리즘은 모든 사람들이 만족할 수 있는 최적의 3가지 사이즈를 산출해 낼 것입니다. 3가지로 부족하다면 4개로 그룹을 나눌 것이고.. 계속 만족할 만한 개수의 그룹으로 늘려나갈 수 있습니다. 아래 그럼처럼요.

자, 이제 이 K-Means 클러스터링의 알고리즘을 알아 봅시다. 그림을 통해 단계별로 설명하겠습니다.

아래와 같은 데이터셋을 살펴봅시다. 이 데이터셋을 앞서 언급한 티셔츠 데이터라고 할 수 있습니다. 이 데이터를 2개의 그룹으로 군집화(Clustering)해 봅시다.

1단계

무작위로 2개의 중심점을 선택합니다. 이 중심점은 C1과 C2라고 합시다. (그냥 데이터 셋중 2개를 잡아서 그 2개가 C1, C2라고 해도 됩니다)

2단계

데이터셋을 구성하는 각각의 모든 포인트와 C1, C2 사이의 거리를 계산합니다. 만약 해당 포인트(테스트 데이터)가 C1에 더 가깝다면, 그 포인트에 ‘0’이라는 라벨을 붙입니다. 만약 C2에 더 가깝다면 ‘1’이라는 라벨을 붙이구요. (더 많은 중심점이 있다면 ‘2’, ‘3’ 등등이 되겠죠) 우리의 경우, ‘0’ 라벨은 빨간색으로, ‘1’ 라벨은 파란색으로 표시했습니다. 이 단계를 통해 아래와 같은 이미지를 얻을 수 있습니다.

3단계

파란색 포인트 전체와 빨간색 포인트 전체에 대한 각각의 평균을 계산하고 이 평균을 새로운 중심점으로 갱신합니다. 즉 C1과 C2는 새롭게 계산된 중심점으로 이동되겠죠. 그리고 2단계를 다시 수행합니다. 그럼 다음과 같은 결과가 얻어집니다.

2단계와 3단계를 반복하는데, 중심점 C1과 C2가 더 이상 변경되지 않을 때까지 반복합니다. (또는 반복 회수의 제한을 두던지.. 중심점의 변경시 이동 거리에 대한 기준 등을 만족할때까지 반복할 수도 있습니다.) 반복이 멈추게 되면, 중심점과 이들 중심점과 연관된 포인트 간의 거리의 합이 최소가 됩니다. 간단이 말해, 사이의 거리합이 최소입니다.

최종 결과는 아래와 같게 됩니다.

바로 이것이 K-Means 클러스터링에 대한 직관적인 이해이며, K-Means의 최상위 개념입니다. 여기에 다양한 변종과 응용이 추가됩니다. 예를들어 초기 중심점을 어떻게 결정하여 알고리즘의 속도를 향상시킬까 하는 등의 고민이 필요합니다.