Метод k-средних в OpenCV / OpenCV / Recog.ru - Распознавание образов для программистов


Метод k-средних в OpenCV

k-means (метод k-средних) – алгоритм кластеризации. Суть в том, что в группе данных найти скопления («кластеры»). Пользователь устанавливает количество кластеров, а алгоритм находит лучшие места для них.
Алгоритм работает следующим образом.
1. Входные данные: (а) набор данных; (б) количество кластеров.
2. Случайно назначаем позиции кластеров.
3. Связываем каждую точку данных с ближайшим центром.
4. Перемещение центра кластера в позицию «центра тяжести».
5. Возврат к шагу 3 до тех пор, пока на шаге 4 не будет изменений.
Не смотря на то, что данный алгоритм является эффективным, у него есть три проблемы:
1. Не гарантируется, что найдется оптимальное местоположение кластеров, однако гарантируется сходимость алгоритма (нет бесконечного движения центров).
2. Метод k-средних не скажет нам, какое оптимальное количество кластеров – их необходимо устанавливать самостоятельно.
3. Метод k-средних предполагает, что ковариация в пространстве или не имеет значения, или данные уже нормализованы.
Решение этих проблем:
1. Запуск алгоритма несколько раз с разным смещением центров, а затем выбрать оптимальный результат как минимум дисперсии вокруг центров.
2. Начните с 1 кластера и прибавляйте по 1. И смотрите, как уменьшается общая дисперсия. Первоначально она должна резко уменьшаться, а потом замедлится – этот момент и будет моментов остановки.
3. Умножьте данные обратной ковариационной матрицы. Например, если входные векторы данных D организованы как строки с одной точкой данных в строке, то нормализуйте данные растягивая их в пространстве для получения нового вектора D* = DΣ^−1/2. (Почитайте подробнее «Learning OpenCV»).

В OpenCV есть одна функция для нахождения центров кластеров и групп элементов входной выборки вокруг кластеров.
double kmeans( const Mat& samples, int clusterCount, Mat& labels,
        TermCriteria termcrit, int attempts,
        int flags, Mat* centers );

Параметры:
samples — Floating-point матрица входной выборки (по одной строке на каждый образец);
clusterCount – количество кластеров;
labels – ссылка на входной/выходной массив, который будет хранить индексы кластера для каждого образца;
termcrit – задает максимальное число итераций и/или точность (расстояние центров может двигаться в пределах между последующими итерациями);
attempts — сколько раз этот алгоритм выполняется с использованием различных начальных меток. Алгоритм возвращает labels, которые дают лучшие характеристик компактности (в соответствии с последним параметром функции);
flags:
KMEANS_RANDOM_CENTERS – в каждой попытке выбираются случайные начальные центры;
KMEANS_PP_CENTERS – используется kmeans++ инициализация центров;
KMEANS_USE_INITIAL_LABELS – во время первой (и возможно единственной попытке) функция использует предоставляемые пользователем labels. Для второй и последующих попыток используются случайные или полу случайные центры;
centers – выходная матрица центров, по одной строке на каждый кластер.
Функция kmeans реализует алгоритм k-средних, который находит центры clusterCount скоплений и групп входных образцов вокруг кластеров. На выходе, labelsi содержит начинающиеся с 0-го индекса кластеры для каждого образца, которые хранятся построчно в матрице образца. Функция возвращает меру компактности, которая вычисляется как


после каждой попытки. Лучший результат сохраняется и возвращается. В принципе пользователь может использовать только ядро функции, установив количество попыток в 1, инициализируя метки каждый раз с помощью своего алгоритма (KMEANS_USE_INITIAL_LABELS), а затем сам выбрать лучший результат.

Пример из OpenCV
#include "opencv2/highgui/highgui.hpp"
#include "opencv2/core/core.hpp"
#include <iostream>

using namespace cv;
using namespace std;

void help()
{
	cout << "\nThis program demonstrates kmeans clustering.\n"
			"It generates an image with random points, then assigns a random number of cluster\n"
			"centers and uses kmeans to move those cluster centers to their representitive location\n"
			"Call\n"
			"./kmeans\n" << endl;
}

int main( int argc, char** argv )
{
    const int MAX_CLUSTERS = 5;
    Scalar colorTab[] =
    {
        Scalar(0, 0, 255),
        Scalar(0,255,0),
        Scalar(255,100,100),
        Scalar(255,0,255),
        Scalar(0,255,255)
    };
        
    Mat img(500, 500, CV_8UC3);
    RNG rng(12345);

    for(;;)
    {
        int k, clusterCount = rng.uniform(2, MAX_CLUSTERS+1);
        int i, sampleCount = rng.uniform(1, 1001);
        Mat points(sampleCount, 1, CV_32FC2), labels;
        
        clusterCount = MIN(clusterCount, sampleCount);
        Mat centers(clusterCount, 1, points.type());

        /* генерируются случайные значения СС использованием нормального распределения*/
        for( k = 0; k < clusterCount; k++ )
        {
            Point center;
            center.x = rng.uniform(0, img.cols);
            center.y = rng.uniform(0, img.rows);
            Mat pointChunk = points.rowRange(k*sampleCount/clusterCount,
                                             k == clusterCount - 1 ? sampleCount :
                                             (k+1)*sampleCount/clusterCount);
            rng.fill(pointChunk, CV_RAND_NORMAL, Scalar(center.x, center.y), Scalar(img.cols*0.05, img.rows*0.05));
        }

        /* перетасовывает элементы случайным образом */
        randShuffle(points, 1, &rng);

        /* вызов алгоритма k-средних */
        kmeans(points, clusterCount, labels, 
               TermCriteria( CV_TERMCRIT_EPS+CV_TERMCRIT_ITER, 10, 1.0),
               3, KMEANS_PP_CENTERS, ¢ers);

        /* очистка изображения */
        img = Scalar::all(0);

        /* вывод точек на изображение*/
        for( i = 0; i < sampleCount; i++ )
        {
            int clusterIdx = labels.at<int>(i);
            Point ipt = points.at<Point2f>(i);
            circle( img, ipt, 2, colorTab[clusterIdx], CV_FILLED, CV_AA );
        }

        /* вывод на экран*/
        imshow("clusters", img);

        /* завершение работы или генерация по новой*/
        char key = (char)waitKey();
        if( key == 27 || key == 'q' || key == 'Q' ) // 'ESC'
            break;
    }

    return 0;
}
  • 0
  • 10 августа 2012, 14:08
  • vidikon

Комментарии (0)

RSS свернуть / развернуть

Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.