Алгоритм обнаружения «скоплений» точек [закрыт]

У меня есть 2D-область с «точками», распределенными по этой области. Сейчас я пытаюсь обнаружить «скопления» точек, то есть областей с определенной высокой плотностью точек.

Любые мысли (или ссылки на статьи с мыслями), как элегантно обнаружить эти области?

10.12.2008 13:28:26
Там отличный учебник кластеризации алгоритмов здесь , они обсуждают K-средства и K-Гаусс , .
Mike Caron 11.12.2008 15:19:11
16 ОТВЕТОВ
РЕШЕНИЕ

Как насчет определения произвольного разрешения для вашего пространства и вычисления для каждой точки в этой матрице меры расстояния от этой точки до всех точек, тогда вы можете составить «тепловой график» и использовать пороговое значение для определения кластеров.

Это хорошее упражнение для обработки, может позже я выложу решение.

РЕДАКТИРОВАТЬ:

Вот:

//load the image
PImage sample;
sample = loadImage("test.png");
size(sample.width, sample.height);
image(sample, 0, 0);
int[][] heat = new int[width][height];

//parameters
int resolution = 5; //distance between points in the gridq
int distance = 8; //distance at wich two points are considered near
float threshold = 0.5;
int level = 240; //leven to detect the dots
int sensitivity = 1; //how much does each dot matters

//calculate the "heat" on each point of the grid
color black = color(0,0,0);
loadPixels();
for(int a=0; a<width; a+=resolution){
  for(int b=0; b<height; b+=resolution){
    for(int x=0; x<width; x++){
      for(int y=0; y<height; y++){
        color c = sample.pixels[y*sample.width+x];        
        /**
         * the heat should be a function of the brightness and the distance, 
         * but this works (tm)
         */
        if(brightness(c)<level && dist(x,y,a,b)<distance){
          heat[a][b] += sensitivity;
        }
      }
    }
  }
}

//render the output
for(int a=0; a<width; ++a){
  for(int b=0; b<height; ++b){
    pixels[b*sample.width+a] = color(heat[a][b],0,0);
  }
}
updatePixels();
filter(THRESHOLD,threshold);

РЕДАКТИРОВАТЬ 2 (чуть менее неэффективный код, но тот же вывод):

//load the image
PImage sample;
sample = loadImage("test.png");
size(sample.width, sample.height);
image(sample, 0, 0);
int[][] heat = new int[width][height];
int dotQ = 0;
int[][] dots = new int[width*height][2];
int X = 0;
int Y = 1;


//parameters
int resolution = 1; //distance between points in the grid
int distance = 20; //distance at wich two points are considered near
float threshold = 0.6;
int level = 240; //minimum brightness to detect the dots
int sensitivity = 1; //how much does each dot matters

//detect all dots in the sample
loadPixels();
for(int x=0; x<width; x++){
 for(int y=0; y<height; y++){
   color c = pixels[y*sample.width+x];
   if(brightness(c)<level) {
       dots[dotQ][X] += x;
       dots[dotQ++][Y] += y;
   }
 }
}

//calculate heat
for(int x=0; x<width; x+=resolution){
 for(int y=0; y<height; y+=resolution){
   for(int d=0; d<dotQ; d++){
     if(dist(x,y,dots[d][X],dots[d][Y]) < distance)
       heat[x][y]+=sensitivity;
   }
 }
}

//render the output
for(int a=0; a<width; ++a){
 for(int b=0; b<height; ++b){
   pixels[b*sample.width+a] = color(heat[a][b],0,0);
 }
}
updatePixels();
filter(THRESHOLD,threshold);

/** This smooths the ouput with low resolutions
* for(int i=0; i<10; ++i) filter(DILATE);
* for(int i=0; i<3; ++i) filter(BLUR);
* filter(THRESHOLD);
*/

И вывод с (уменьшенным) образцом Кента:

24
19.10.2012 15:51:13
Да, для квадрата из nxn точек это o (n ^ 4), или для более низких разрешений r, o (n ^ 2 * ((n / r) ^ 2)). Может быть, как метод грубой силы для небольших изображений, но не как общее решение.
SmacL 10.12.2008 16:22:55
Конечно, я бы не стал использовать это для серьезных целей, просто для того, чтобы подчеркнуть, что если подход полезен, его можно оптимизировать многими способами.
krusty.ar 10.12.2008 16:27:05
@kent: интересно было бы сгруппировать точки в соответствии с областями, это просто облегчает понимание того, что области действительно есть. @smacl: твой комментарий заставил меня чувствовать себя плохо, поэтому я обновил его, чтобы сделать его менее уродливым.
krusty.ar 11.12.2008 11:24:47
@kent: я согласен. Кстати классное изображение осталось, но процесс занимает некоторое время.
Mike Caron 11.12.2008 14:55:19

Вы можете попробовать создать представление данных Quadtree . Более короткие пути на графике соответствуют областям с высокой плотностью.

Или, чтобы выразиться более четко: с учетом Quadtree и обхода уровня порядка каждый узел нижнего уровня, состоящий из «точек», будет представлять область высокой плотности. Когда уровень узлов увеличивается, такие узлы представляют области с более низкой плотностью «точек»

10
10.12.2008 13:40:34
Мне это нравится. Я могу подумать о некоторых изящных алгоритмах для определения того, принадлежат ли другие четырехъядерные ячейки на текущем уровне к текущему «кластеру», но, к сожалению, это поле комментариев слишком мало ...
Paul Tomblin 10.12.2008 13:49:02
Это действительно хорошая идея, если кластеры выпуклые.
Rich 10.12.2008 22:42:06
Есть ли ссылки на реализации Quadtree? Как быстро это будет?
Mike Caron 11.12.2008 14:56:20

Я бы рассчитал расстояния от каждой точки до всех остальных точек. Затем сортируйте расстояния. Точки, расстояние между которыми ниже порога, считаются Ближними . Группа точек, которые находятся рядом друг с другом, является кластером.

Проблема в том, что кластер может быть понятен человеку, когда он видит график, но не имеет четкого математического определения. Вам нужно определить свой близкий порог, возможно, его корректируя эмпирически, пока результат вашего алгоритма (более или менее) не будет равен тому, что вы воспринимаете как кластеризованный.

0
10.12.2008 13:37:20
Это n * (n + log (n))!
P Daddy 10.12.2008 14:01:42
@P Папа, если используется более быстрый алгоритм, но он не возвращает правильных ответов, это не то, что вы хотите использовать. Некоторые проблемы просто NP завершены. Вот только как это.
Kent Fredric 10.12.2008 14:07:00
Это не один из них.
P Daddy 10.12.2008 14:40:26
@P папа. Идея Треба может быть реализована намного быстрее. Посмотрите любую книгу по вычислительной геометрии (например, Shamos & Preparata, Hoey или O'Rourke) на «множестве всех ближайших соседей».
SmacL 10.12.2008 14:50:53
Справедливо. Я предположил, что идея была хорошей, просто реализация была слабой и могла быть улучшена. Кстати, последний символ в вашем вступительном слове означает факториал или это признак раздражения;)
SmacL 10.12.2008 15:11:57

Как насчет морфологического подхода?

Расширьте пороговое изображение на некоторое число (в зависимости от целевой плотности точек), после чего точки в кластере появятся как один объект.

OpenCV поддерживает морфологические операции (как и ряд библиотек обработки изображений):

http://www.seas.upenn.edu/~bensapp/opencvdocs/ref/opencvref_cv.htm#cv_imgproc_morphology

5
10.12.2008 13:38:00

«Области с определенной высокой плотностью» подразумевают, что вы приблизительно знаете, сколько точек на единицу площади вы считаете высокой. Это подводит меня к сеточному подходу, где вы разделяете свою общую площадь на подобласти соответствующего размера, а затем подсчитываете количество точек в каждой области. Как только вы найдете области своей сетки рядом с порогом, вы можете также искать соседние области сетки.

3
10.12.2008 13:40:48
Преимущество подхода quadtree по сравнению с этим подходом состоит в том, что quadtree не нужно заранее определять единицу площади, а только количество точек, которые вы бы назвали «кластером».
Paul Tomblin 10.12.2008 13:46:23
Мне нравится подход Quadtree, я проголосовал за него, но область юнитов - часть проблемы. Кластер - это не просто число точек, это количество точек, расположенных близко друг к другу, то есть в определенной области.
Bill the Lizard 10.12.2008 13:49:11

Чтобы добавить немного помощника к заявлению Требса , я думаю, что важно сначала реалистично определить, что такое определение кластера, конечно, «точки ближе друг к другу», что довольно смело.

Возьмите этот сэмпл, который я сгенерировал, я знаю, что там есть форма кластера, я его создал.

Однако программно определить этот «кластер» может быть сложно.

Человек может посчитать, что это большой тороидальный кластер, но ваша автоматизированная программа, скорее всего, решит, что это серия небольших кластеров в полузакрытой близости.

Кроме того, обратите внимание, что есть области сверхвысокой плотности, которые в контексте общей картины являются просто отвлекающими

Вам нужно будет рассмотреть это поведение и, возможно, связать воедино кластеры одинаковой плотности, разделенные только незначительными пустотами более низкой плотности, в зависимости от конкретного применения.

Что бы вы ни разрабатывали, меня по крайней мере интересовало бы, как оно идентифицирует данные в этом наборе.

(Я думаю, что стоит рассмотреть технологии, лежащие в основе HDRI ToneMapping, потому что они более или менее работают с плотностью света, и есть «локальные» карты тонов и «глобальные» карты тонов, каждая из которых дает разные результаты)

13
23.05.2017 12:17:23
Смотрите мой ответ ниже о генетических алгоритмах. В этом случае, если вы заранее знали, что тороидальные кластеры (или любая необычная форма) возможны, вы могли бы просто встроить эту возможность в свой механизм генерирования решений и в свою фитнес-функцию.
MusiGenesis 10.12.2008 14:34:51
@Kent, если вы используете решение на основе TIN, вы можете сгруппировать треугольники по порядку величины самой длинной длины ребра, чтобы решить эту проблему. Таким образом, хотя мы видим тор, в вашей сверхплотной области может быть много других интересных фигур, достойных их собственного анализа. Гугл мульти-разрешение TIN или Вороной.
SmacL 10.12.2008 15:08:30

Примените фильтр размытия к копии вашей 2D-области. Что-то вроде

1 2 3 2 1
2 4 6 4 2
3 6 9 6 3
2 4 6 4 2
1 2 3 2 1

«Более темные» области теперь идентифицируют группы точек.

12
10.12.2008 13:57:14
Интересно. Интересно, будет ли этот подход распространен на более чем 2 измерения ...
Drew Noakes 5.01.2009 18:43:05
Конечно, но ваша матрица также растет в геометрической прогрессии. например, 3D-матрица будет использовать 125 элементов вместо 25. Чтобы достичь эффекта, аналогичного описанному выше (назовем это M) для 2D, вы должны использовать M, где z = 0 и z = 4, и M * 2, где z = 1 и z = 3, а M * 3, где z = 2. Аналогично с более высокими размерами.
P Daddy 5.01.2009 22:05:28

Вы можете наложить логическую сетку на вашу плоскость. Если сетка имеет определенное количество содержащихся точек, она считается "плотной" и может быть затем прорежена. Это много делается в ГИС-приложениях при работе с кластерными допусками. Использование сетки помогает разделить ваш алгоритм прореживания.

0
10.12.2008 14:02:17

Это действительно звучит как академический вопрос.

Решение, которое приходит на ум, включает г * деревья. Это делит вашу общую площадь на отдельные размеры и, возможно, перекрывающиеся поля. После этого вы можете определить, представляет ли каждое поле «кластер» или нет, рассчитав среднее расстояние.

R * Деревья

Если такой подход становится трудным для реализации, вам может быть лучше разделить вашу сетку данных на подразделения одинакового размера и определить, есть ли кластер в каждом; с таким подходом вы должны быть очень внимательны к крайним условиям. Я хотел бы предложить, чтобы после начального деления вы прошли и рекомбинировали области с точками данных в пределах определенного порога определенного края.

4
10.12.2008 14:02:38

Вы можете использовать генетический алгоритм для этого. Если вы определяете «кластер» как, скажем, прямоугольную подобласть с высокой плотностью точек, вы можете создать начальный набор «решений», каждое из которых состоит из некоторого числа случайно сгенерированных непересекающихся прямоугольных кластеров. , Затем вы должны написать «фитнес-функцию», которая оценивает каждое решение - в этом случае вы хотели бы, чтобы фитнес-функция минимизировала общее количество кластеров при максимизации плотности точек в каждом кластере.

Ваш первоначальный набор «решений» будет, скорее всего, ужасным, но некоторые, скорее всего, будут несколько менее ужасными, чем другие. Вы используете функцию пригодности, чтобы исключить наихудшие решения, а затем создаете решения следующего поколения путем скрещивания «победителей» последнего поколения. Повторяя этот процесс из поколения в поколение, вы должны получить одно или несколько хороших решений этой проблемы.

Чтобы генетический алгоритм работал, различные возможные решения проблемного пространства должны постепенно отличаться друг от друга с точки зрения того, насколько хорошо они решают проблему. Точечные кластеры идеально подходят для этого.

0
10.12.2008 14:30:25

Я думаю, что это зависит от того, насколько велико разделение между точками и кластерами. Если расстояния большие и нерегулярные, я сначала триангулирую точки, а затем удаляю / скрываю все треугольники со статистически большой длиной ребер. Оставшиеся субтриангуляции образуют кластеры произвольной формы. Обход ребер этих субтриангуляций дает полигоны, которые можно использовать для определения того, какие конкретные точки лежат в каждом кластере. Полигоны также можно сравнить с известными формами, такими как тор Кента Фредрика, по мере необходимости.

IMO, сеточные методы хороши для быстрых и грязных решений, но очень быстро проголодались на редких данных. Четырехъядерные деревья лучше, но TIN - мой личный фаворит для более сложного анализа.

2
10.12.2008 16:08:41
Является ли «трингуляция» специализированным термином для определенного типа триангуляции или просто опечатка?
Paul Tomblin 10.12.2008 15:34:10

Я бы предложил использовать ядро среднего сдвига, чтобы найти центр плотности ваших точек.

Иллюстрация среднего смещения http://cvr.yorku.ca/members/gradstudents/kosta/compvis/file_mean_shift_path.gif

На этом рисунке показано, как ядро ​​среднего смещения (первоначально с центром на краю скопления) сходится к точке скопления с наибольшей плотностью.

Теоретически (в двух словах):

Несколько ответов на эти вопросы уже намекали на способ среднего смещения:

То, что вы видите на анимированном рисунке, является комбинацией этих двух предложений: он использует движущийся «блок» (то есть ядро), чтобы искать локально самую высокую плотность.

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

В каждой итерации среднее значение ядра определяет его центральные координаты для следующей итерации - это называется сдвигом . Отсюда и название означает сдвиг . Условие остановки для итераций - когда расстояние сдвига падает до 0 (т.е. мы находимся в самом плотном месте в окрестности).

Подробное введение в среднее смещение (как в теории, так и в применении) можно найти в этой презентации на ppt.

На практике:

Реализация среднего сдвига доступна в OpenCV :

int cvMeanShift( const CvArr* prob_image, CvRect window,
                 CvTermCriteria criteria, CvConnectedComp* comp );

Изучение OpenCv О'Рейли (отрывки из книги Google) также дает хорошее объяснение того, как это работает. В основном просто накормить его своим точечным изображением (prob_image).

На практике хитрость заключается в том, чтобы выбрать подходящий размер ядра . Чем меньше ядро, тем ближе вам нужно инициировать его в кластер. Чем больше ядро, тем более случайной может быть ваша начальная позиция. Однако, если в вашем изображении несколько кластеров точек, ядро ​​может сходиться между ними.

23
23.05.2017 12:09:29
Это звучит интересно, хотя (поправьте меня, если я ошибаюсь), этот подход не является детерминированным и поэтому не подходит в некоторых случаях. Хорошая рецензия.
Drew Noakes 5.01.2009 19:00:53
Спасибо. Если детерминистический означает, что алгоритм всегда дает один и тот же выход для данного входа, то он является детерминированным.
Ivan 5.01.2009 21:45:53
Хороший ответ. Но поправьте меня, если я ошибаюсь, это даст вам только «основной кластер» в случае OP, где ему нужно получить разные кластеры. Не так ли?
Btc Sources 14.05.2015 09:46:52
  1. Подберите функцию плотности вероятности для данных. Я бы использовал «смесь гауссианов» и подгонял ее, используя обучение по максимизации ожиданий, запрограммированное алгоритмом K-средних. K-средства сами по себе иногда могут быть достаточными без EM. Количество кластеров само по себе должно быть заполнено алгоритмом выбора порядка модели.
  2. Затем каждая точка может быть оценена с помощью p (x) с использованием модели. Т.е. получить апостериорную вероятность того, что точка была сгенерирована моделью.
  3. Найдите максимальное значение p (x), чтобы найти скопления центроидов.

Это можно очень быстро кодировать в таком инструменте, как Matlab, используя набор инструментов машинного обучения. Обучение MoG / EM / кластеризация K-Means широко обсуждаются в сети / стандартные тексты. Мой любимый текст - «Классификация узоров» Дуда / Харт.

4
4.02.2009 19:06:12

Кластер 3.0 включает в себя библиотеку методов C для проведения статистической кластеризации. У него есть несколько различных методов, которые могут решить или не решить вашу проблему, в зависимости от того, какую форму принимают ваши точечные кластеры. Библиотека доступна здесь здесь и распространяется под лицензией Python.

0
25.02.2009 12:32:05

Вы пробовали простые готовые решения, такие как ImagXpress от Accusoft Pegasus?

Метод BlobRemoval можно настроить для подсчета количества пикселей и плотности, чтобы находить дыроколы, даже если они не являются непрерывными. (вы также можете попробовать функцию Dlate, чтобы закрыть пробелы)

Немного поиграв в игру, вы, вероятно, сможете получить нужные вам результаты в подавляющем большинстве случаев, с очень небольшим количеством кода или науки.

C #:
открытый void DocumentBlobRemoval (прямоугольник, int MinPixelCount, int MaxPixelCount, короткий MinDensity)

0
15.06.2009 18:41:36

Позвольте мне организовать это в качестве исследовательской работы

а. Постановка задачи

Процитируем Epaga : «У меня есть 2D-область с« точками », распределенными по этой области. Сейчас я пытаюсь обнаружить« скопления »точек, то есть областей с определенной высокой плотностью точек».

Обратите внимание, что нигде не упоминается, что точки взяты из изображения. (Хотя они могут быть заказаны как один).

Метод случая 1. Если точки являются просто точками (точки = точки в 2D-пространстве). В этом сценарии у вас уже будут оба местоположения x & y для всех точек. Проблема сводится к одному из кластеризации точек. Иван проделал большую работу, предложив решение. Он также суммировал другие ответы подобного аромата. Мой 2cts в дополнение к его посту состоит в том, что вы считаете, знаете ли вы количество кластеров априори или нет. Алгоритмы (контролируемая или неконтролируемая кластеризация может быть выбрана соответственно).

Случай 2: если точки действительно происходят из изображения. Здесь проблема должна быть прояснена. Позвольте мне объяснить, используя это изображение. альтернативный текст Если не делается никаких различий по серому значению точек, группы 1, 2, 3, 4 и 5 являются «отдельными группами». Однако, если различие сделано на основе значения серого, кластер 5 является хитрым, поскольку у точки есть различные значения серого.

Несмотря на это, эту проблему можно свести к случаю 1 путем растрового сканирования изображения и сохранения координат ненулевых (не белых) пикселей. Алгоритмы кластеризации, как предлагалось ранее, могут затем использоваться для вычисления количества кластеров и центров кластеров.

3
23.05.2017 12:25:16