Комментарии 16
Поправьте если я ошибаюсь, но на сколько я помню, то в университете этот метод классификации используется часто и даже не локально на каком-то одном предмете, не могло же только мне повезти. И заявление о недостатке литературы какое-то странное, ввиду этого.
K — means довольно быстрый как метод сегментации (кластеризации), но не стабильный из-за случайной выборки затравок :(. Это легко увидеть обработав им видео-последовательность. Правильная выборка затравок и количества сегментов — это отдельная и очень сложная задача.
Mean shift «en.wikipedia.org/wiki/Mean_shift» медленней, но стабильней и проще параметризуется.
Mean shift «en.wikipedia.org/wiki/Mean_shift» медленней, но стабильней и проще параметризуется.
А зачем Вы на C++ писали на C? Вот такая конструкция в C++ смотрится откровенно странно:
На мой вкус она и на C так.., но это уже, конечно, дело вкуса.
typedef struct {
double r;
double g;
double b;
} rgb;На мой вкус она и на C так.., но это уже, конечно, дело вкуса.
Просто в универе сейчас Си учим, а С++ сам изучаю, вот и комбинирую что знаю))) Думаю на саму суть это не влияет.
Влияет. И в C, и в C++ Вы создали нечто с именем, известным только компилятору, а потом задали для этого нечто алиас. Гляньте в отладчике, лучше не в самом умном, но точном: там будет что-то наподобие struct Anonymous (если писали на C) или какая-то случайная комбинация символов. В C такая практика довольно распространена, поскольку иначе нужно объявлять как struct some_name, что не всегда удобно. Поэтому делают typedef. Но даже в этом случае лучше не экономить нажатия на клавиши и прописывать явный «тэг» структуры.
В C++ такое объявление поддерживается для совместимости с C, но режет глаза. Незачем всем объявлять, что Вы не совсем понимаете, что делаете))))
В C++ такое объявление поддерживается для совместимости с C, но режет глаза. Незачем всем объявлять, что Вы не совсем понимаете, что делаете))))
А зачем для сравнения расстояний от пикселей до центров использовать расстояние, а не квадрат расстояния?
Извлечение корня квадратного будет в данном случае лишней операцией.
Извлечение корня квадратного будет в данном случае лишней операцией.
В свое время, лет так 25 назад занимался из любви к искусству кластеризацией цветов изображений. А все потому, что видеокарточка была VGA с максимальной глубиной цвета 8-bit, а фотографии 15-bit, 16-bit и 24-bit уже появлялись.
Какие я только методы кластеризации не перепробовал. И плоские и иерархические.
Неплохой результат давал метод квантования цветового пространства.
Суть его примерно такая:
1. Для всего множества пикселей находится такая ось в цветовом пространстве RGB, сумма квадратов расстояний от которой до цветовых координат пикселей является наименьшей.
2. Пиксели проецируются на эту ось. Просто каждому пикселю присваивается координата проекции.
3. Массив пикселей сортируется по координате проекции.
4. Отсортированный массив разбивается на два подмассива, таких что сумма квадратов отклонений проекций от центра тяжести соответствующего подмассива была минимальна.
5. Разбиение повторяется рекурсивно для каждого подмассива, пока число разбиений не станет равным заданному.
6. В каждом кластере все цвета заменяются на координаты центра тяжести кластера.
Метод достаточно хороший в плане приближения цветов. Но очень-очень долгий.
Можно существенно его упростить. Не находить на каждом шаге проективную ось, а выбрать одну из осей R, G, B. Например такую, максимальный разброс оттенков по которой является наибольшим. И провести медианное разбиение (с учетом весов — количества пикселей каждого оттенка).
Так будет существенно быстрее, но несколько уступать в точности цветопередачи.
Хотя, последующий дайзеринг нивелирует эту погрешность.
Какие я только методы кластеризации не перепробовал. И плоские и иерархические.
Неплохой результат давал метод квантования цветового пространства.
Суть его примерно такая:
1. Для всего множества пикселей находится такая ось в цветовом пространстве RGB, сумма квадратов расстояний от которой до цветовых координат пикселей является наименьшей.
2. Пиксели проецируются на эту ось. Просто каждому пикселю присваивается координата проекции.
3. Массив пикселей сортируется по координате проекции.
4. Отсортированный массив разбивается на два подмассива, таких что сумма квадратов отклонений проекций от центра тяжести соответствующего подмассива была минимальна.
5. Разбиение повторяется рекурсивно для каждого подмассива, пока число разбиений не станет равным заданному.
6. В каждом кластере все цвета заменяются на координаты центра тяжести кластера.
Метод достаточно хороший в плане приближения цветов. Но очень-очень долгий.
Можно существенно его упростить. Не находить на каждом шаге проективную ось, а выбрать одну из осей R, G, B. Например такую, максимальный разброс оттенков по которой является наибольшим. И провести медианное разбиение (с учетом весов — количества пикселей каждого оттенка).
Так будет существенно быстрее, но несколько уступать в точности цветопередачи.
Хотя, последующий дайзеринг нивелирует эту погрешность.
видеокарточка была VGA с максимальной глубиной цвета 8-bit, а фотографии 15-bit, 16-bit и 24-bit уже появлялись.
8 бит же палитра у нее была, а цветовое пространство 18 бит, по 6 на цвет.
Ну да, прошу прощения за неточность. Конечно, 8 бит — размер индекса палитры. Т.е. цветов можно было вывести много, но одновременно — не более 256. А в Windows 3.x — не более 236, т.к. 20 индексов были зарезервированы под палитру самой Винды. Их тоже можно было заменить, но это приводило к тому, что шрифты, рамки, шапки окон — все меняло цвет. И работать было невозможно.
Но их можно было тоже включить в общую палитру без замены цветов. Но это уже чуть усложняло алгоритм оптимизации палитры. Хотя, она при этом становилась более адекватной, т.к. системные цвета лежали на границах цветового куба, т.е. хорошо подхватывали цвета, которые выбивались из кластеров в сторону границ.
Но их можно было тоже включить в общую палитру без замены цветов. Но это уже чуть усложняло алгоритм оптимизации палитры. Хотя, она при этом становилась более адекватной, т.к. системные цвета лежали на границах цветового куба, т.е. хорошо подхватывали цвета, которые выбивались из кластеров в сторону границ.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Реализация алгоритма k-means (k-средних) на примере работы с пикселями