Комментарии 39
Отлично, только собирался по кластеризации искать статьи.
Только учтите что алгоритм самодельный, и скорее всего есть более эффективные реализации. Например тут показан совершенно другой подход, более обоснованный по алгоритмам кластеризации данных.
> Берется список ячеек в него входят: ячейка с точкой и соседние с ней.
Каким способом это реализовано? Я из статьи не понял. Но может невнимательно читал.
Мне кажется для этого хорошо подходит Диаграмма Вороного + Fortune's Sweeping Line.
Вот ссылки:
JS implementation 1
Описание в псевдокоде и имплементации
Каким способом это реализовано? Я из статьи не понял. Но может невнимательно читал.
Мне кажется для этого хорошо подходит Диаграмма Вороного + Fortune's Sweeping Line.
Вот ссылки:
JS implementation 1
Описание в псевдокоде и имплементации
Реализовано через использование регулярной сети. Пространство разбивается сеткой с ячейками одинакового размера, поиск ячейки в которую входит точка осуществляется по формуле:
Xc=x>>k
Yc=y>>k, где [x;y] — координаты точки, k — степень двойки, по которой расчитывается размер ячейки, a=2^k
Соответственно координаты соседних ячеек и текущей будут следующими:
[Xc-1; Yc-1], [Xc; Yc-1], [Xc+1; Yc-1]
[Xc-1; Yc], [Xc; Yc], [Xc+1; Yc]
[Xc-1; Yc+1], [Xc; Yc+1], [Xc+1; Yc+1]
При условии что R < 2^k
Xc=x>>k
Yc=y>>k, где [x;y] — координаты точки, k — степень двойки, по которой расчитывается размер ячейки, a=2^k
Соответственно координаты соседних ячеек и текущей будут следующими:
[Xc-1; Yc-1], [Xc; Yc-1], [Xc+1; Yc-1]
[Xc-1; Yc], [Xc; Yc], [Xc+1; Yc]
[Xc-1; Yc+1], [Xc; Yc+1], [Xc+1; Yc+1]
При условии что R < 2^k
С диаграмой Вороного уже сталкивался, когда делал какой-то алгоритм для игры, но здесь вариант попроще. Главной задачей было обойтись без операции деления, в алгоритме где требуется вычислять срединный перпендикуляр для каждой пары точек это вряд ли получится. Ну и в итоге это был бы совершенно другой способ поиска кластеров.
> когда делал какой-то алгоритм для игры
Подробнее можно? Интересно чрезвычайно!
Подробнее можно? Интересно чрезвычайно!
Можно. Даже нашел статью по которой делал. Требовалось для расчета пересечений объектов. В приведенной статье 8 пример. Вообще прекрасная статья для тех кто сам моделирует столкновения.
Спасибо! В мемы…
Правда определение полигона вороного там некорректное на мой взгляд:
«Область Вороного — это множество точек, расположенных ближе к данному, чем к какому-либо другому фрагменту многоугольника. Фрагментом многоугольника называется его вершина или сторона. Область Вороного формирует область пространства, „прилежащую“ к ближайшему фрагменту. Набор областей Вороного для всех фрагментов многоугольника называется диаграммой Вороного. „
У многоугольника есть вершины, есть грани. Ни то, ни другое не является тем, что названо “фрагментом». Есть множество заданных точек, называемых вершинами ячеек. Границы ячеек — отрезки, на которых точки равноудалены от двух соседних вершин. А принадлежность точки ячейке означает то, что она располагается ближе к вершине данной ячейки, чем к вершинам остальных ячеек на диаграмме.
Правда определение полигона вороного там некорректное на мой взгляд:
«Область Вороного — это множество точек, расположенных ближе к данному, чем к какому-либо другому фрагменту многоугольника. Фрагментом многоугольника называется его вершина или сторона. Область Вороного формирует область пространства, „прилежащую“ к ближайшему фрагменту. Набор областей Вороного для всех фрагментов многоугольника называется диаграммой Вороного. „
У многоугольника есть вершины, есть грани. Ни то, ни другое не является тем, что названо “фрагментом». Есть множество заданных точек, называемых вершинами ячеек. Границы ячеек — отрезки, на которых точки равноудалены от двух соседних вершин. А принадлежность точки ячейке означает то, что она располагается ближе к вершине данной ячейки, чем к вершинам остальных ячеек на диаграмме.
Спасибо. Очень познавательно.
Вот тут еще парни для 3D библиотеку с кластеризацией делают. Вполне себе работоспособная, хотя работает не оптимально (видно из исходников).
Вот тут еще парни для 3D библиотеку с кластеризацией делают. Вполне себе работоспособная, хотя работает не оптимально (видно из исходников).
> проверяемая точка уже принадлежит какому-то кластеру, отличному от текущего => кластер с большим
> количеством точек поглощает кластер с меньшим.
Мне кажется, что в этот момент при более-менее равномерно расположенных точек алгоритм начнет лажать. Собственно, оно видно на самой первой картинке.
> количеством точек поглощает кластер с меньшим.
Мне кажется, что в этот момент при более-менее равномерно расположенных точек алгоритм начнет лажать. Собственно, оно видно на самой первой картинке.
При полностью равномерном расположении точек и задании R больше или равного расстоянию между ними, получим один кластер, при R меньшем чем расстояние между точками получим N кластеров, где N = числу точек. На первой картинке расположение случайное, и алгоритм отработал правильно. Выделены разными цветами области в которых расстояние между точками не превышает заданного R. Поясните что подразумевается под лажать?
В такой постановке все верно.
Но я считал, что кластеризация должна производиться не на основе расстояния между точками, а на основе расстояния между точкой и «центром масс» кластера. По картинке интуитивно чувствуется, что фиолетовый кластер в верхнем правом углу должен быть разбит на еще два.
Есть еще претензия по поводу контуров: вообще решением задачи кластеризации является так называемое «решающее правило», которое в будущем будет относить новые точки к конкретным кластерам. Контуры по уже существующим точкам никак найти это правило не помогут, тут нужно что-то вроде диаграм Вороного (да и нагляднее гораздо).
Но я считал, что кластеризация должна производиться не на основе расстояния между точками, а на основе расстояния между точкой и «центром масс» кластера. По картинке интуитивно чувствуется, что фиолетовый кластер в верхнем правом углу должен быть разбит на еще два.
Есть еще претензия по поводу контуров: вообще решением задачи кластеризации является так называемое «решающее правило», которое в будущем будет относить новые точки к конкретным кластерам. Контуры по уже существующим точкам никак найти это правило не помогут, тут нужно что-то вроде диаграм Вороного (да и нагляднее гораздо).
Да, по поводу кластеризации мы исходим просто из разных постановок, здесь именно рассчет расстояния между точками, а центр масс расчитывается уже для прикладной задачи поиска контура.
Насчет новых точек, определение к какому кластеру она будет относиться проходит крайне просто, аналогично приведенному алгоримту определяется список проверяемых ячеек регулярной сетки, проверяются соседние точки, и быстро находится или не находится кластер в который она войдет. Единственное придется учесть что новая точка может объединить два уже существующих кластера, что в принципе тоже реализовано.
Насчет новых точек, определение к какому кластеру она будет относиться проходит крайне просто, аналогично приведенному алгоримту определяется список проверяемых ячеек регулярной сетки, проверяются соседние точки, и быстро находится или не находится кластер в который она войдет. Единственное придется учесть что новая точка может объединить два уже существующих кластера, что в принципе тоже реализовано.
Скажите, а для решения каких задач может применяться кластеризация с таким критерием?
Строчку про непрерывные изображения видел, но не понимаю причем там кластеризация. Для выделения областей на фотографиях обычно используются совсем другие методы, например, на основе определения фрактальных размерностей областей.
Строчку про непрерывные изображения видел, но не понимаю причем там кластеризация. Для выделения областей на фотографиях обычно используются совсем другие методы, например, на основе определения фрактальных размерностей областей.
Насчет задач точно не отвечу, лично для меня это решение только подготовка к следующей задаче. Но я думаю что найти можно, в кластеризации данных не зря же есть алгоритмы для поиска кластеров среди точек заданных координатами. Можно например искать созведия на карте неба)
Про непрерывные изображения имелось в виду не использование кластеризации, а использование общего подхода к решению задач. Т.е. планирую использовать решение похожее на кластеризацию. Если получится сделать, опишу подробнее.
Про непрерывные изображения имелось в виду не использование кластеризации, а использование общего подхода к решению задач. Т.е. планирую использовать решение похожее на кластеризацию. Если получится сделать, опишу подробнее.
Ну как бы, «точки заданные координатами» — это только одна из интерпретаций. Вектор признаков может быть задан кучей разных способов, самый простой — вектор из нулей и единиц (булевых переменных). Например, так можно описать пользователя в интернет-магазине, который купил или не купил какой-то набор товаров. А расстояние между двумя «точками» — это не обязательно геометрическое расстояние в пространстве, это может быть просто сумма признаков с весовыми координатами, или еще что-нибудь интересное. И алгоритмы кластеризации вполне продолжают работать. Меня поэтому и смущает упор на изображениях ;)
По поводу непрерывных изображений — да, очень интересно, что получится ;)
Спасибо за ответы на вопросы.
По поводу непрерывных изображений — да, очень интересно, что получится ;)
Спасибо за ответы на вопросы.
Согласен, на изображениях как раз и хочу сделать вместо расстояния оценку по яркости, цвету и прочим характеристикам, которая и позволит выявлять области.
Мы что-то подобное делали на основе фрактальных размерностей растров (как я писал выше), но распознавание делали на основе байесовского подхода для уже известных классов.
А как выделили области? Я как-то делал расчет фрактальной размерности для растра, но в моей задаче требовался подсчет размерности для всей области, для чего выделялись контура на изображении, и вычислялась размерность путем наложения сеток с равномерными ячейками и подсчетом попаданий в ячейки.
Т.е. вы получали размерность для отдельных частей изображения и сопоставляли с шаблонными? Я просто не понимаю как в этом случае найти границы.
Т.е. вы получали размерность для отдельных частей изображения и сопоставляли с шаблонными? Я просто не понимаю как в этом случае найти границы.
Резали по сетке на большом количестве фотографий с известными типами областей (ручками сначала выделяли области). На основе полученных значений учили байесовский фильтр.
При распознавании — так же резали по сетке, и байесовский фильтр уже размечал ячейки по типам.
При распознавании — так же резали по сетке, и байесовский фильтр уже размечал ячейки по типам.
Понятно. Спасибо. Очень рессурсоемкая задача в плане времени, это уже на производственные нужды тянет.
Т. е. коэффициент считался для каждой ячейки сетки отдельно.
Контура не выделяли, так как нашли алгоритм считающий размерность сразу по растру.
Контура не выделяли, так как нашли алгоритм считающий размерность сразу по растру.
Велосипед для построения выпуклого описывающего контура называется "qhull". Надеюсь просвятил…
Да, просветили. Спасибо. Правда вставлять не буду, т.к. пишу на .NET, а использование unmanaged dll ухудшает читабельность кода. И приятно было самому подумать над реализацией.
Я сейчас диаграмму вороного грызу через форчуна и тоже на шарпе. От Вороного доя триангуляции Делоне недалеко. А все вместе это в КуХулл входит. Пока серьезно в сишном коде не разбирался, но, кажется, через триангуляцию там все и сделано. Так что, Бог даст, допилю/выложу, там и посмотрим.
Кстати, есть еще один алгоритм:
1) Выбрать самую крайнюю по Ох точку
2) Вращать луч, направленный из нее вверх, против часовой до столкновения с первой точкой
3) Построить ребро
4) продолжать процедуру пока не вернешься в исходную позицию.
Где-то натыкался на описание.
Кстати, есть еще один алгоритм:
1) Выбрать самую крайнюю по Ох точку
2) Вращать луч, направленный из нее вверх, против часовой до столкновения с первой точкой
3) Построить ребро
4) продолжать процедуру пока не вернешься в исходную позицию.
Где-то натыкался на описание.
НЛО прилетело и опубликовало эту надпись здесь
есть очень эффективный алгоритм построения выпуклой оболочки — aлгоритм Грэхема
у вас идея похожа, но там проще
у вас идея похожа, но там проще
А вот было бы интереснее не с оптимизациями побитовыми смещениями, а наоборот —
с обобщением координат до векторов и метрикой пространства.
с обобщением координат до векторов и метрикой пространства.
Насколько я понимаю, это, по-сути, одна из реализаций k-means по принципу «дальнего соседа» с Евклидовым расстоянием, только вместо n-кластеров исходно задаётся максимальное расстояние, и количество кластеров уже получаем как результат.
Уважаемый автора, не могли бы Вы выложить исходники? Те что выложены ранее, к сожалению удалены.
Как ни удивительно смог даже найти.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Кластеризация точек на основе регулярной сети