Алгоритм для обнаружения “кластеров” [закрытых] точек
Я обычно запускаю git mergetool, и он подскажет мне, хочу ли я сохранить измененный файл или удалить его. Это самый быстрый способ IMHO, поскольку это одна команда вместо нескольких файлов.
15 ответов
Как насчет того, чтобы определить произвольное разрешение для Вашего пространства, и вычисляют для каждой точки в той матрице, мере расстояния от той точки до всех точек, тогда Вы могли сделать "график тепла" и использовать порог для определения кластеров.
Это - хорошее осуществление для обработки, возможно, позже я отправлю решение.
РЕДАКТИРОВАНИЕ:
Здесь это:
//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);
*/
И вывод с (уменьшенный) Кентский образец:
Кластер 3.0 включает библиотеку методов C для обязательства статистической кластеризации. Это имеет несколько различных методов, которые могут или не могут решить Вашу проблему, зависящую от того, какую форму Ваши точечные кластеры принимают. Библиотека доступна здесь здесь и распределяется в соответствии с лицензией Python.
Вы могли использовать генетический алгоритм для этого. При определении "кластера" как, скажем, прямоугольная подобласть с высокой точечной плотностью Вы могли создать начальный набор "решений", каждое из которых состоит из некоторого количества случайным образом сгенерированных, неперекрывающихся прямоугольных кластеров. Вы тогда записали бы "функцию фитнеса", которая оценивает каждое решение - в этом случае, Вы хотели бы, чтобы функция фитнеса минимизировала общее количество кластеров при максимизации точечной плотности в каждом кластере.
Ваш начальный набор "решений" все будет ужасен, скорее всего, но некоторые, вероятно, будут немного менее ужасными, чем другие. Вы используете функцию фитнеса для устранения худших решений, затем создаете следующее поколение решений путем скрещивания "победителей" от последнего поколения. Путем повторения этого поколения процесса поколением необходимо закончить с одним или несколькими хорошими решениями этой проблемы.
Для генетического алгоритма для работы, различные возможные решения пространства задач должны инкрементно отличаться друг от друга с точки зрения того, как хорошо они решают проблему. Точечные кластеры идеально подходят для этого.
Я вычислил бы расстояния от каждой точки до всех других точек. Тогда отсортируйте расстояния. Вопросы, которые имеют расстояние друг от друга, который является ниже порога, рассматриваются Близкий . Группа точек, которая является близка друг другу, является кластером.
проблема состоит в том, что кластер может быть ясен человеку, когда он видит график, но не имеет четкого математического определения. Необходимо определить Ваш близкий порог, вероятно, bu adjustuing это опытным путем, пока результат алгоритма не (более или менее) равен тому, что Вы чувствуете как кластеризируемый.
Я думаю, что это зависит от сколько разделения, там между точками и кластерами. Если расстояния являются большими и неправильными, я был бы первоначально треугольный точки, и затем удалите/скройте все треугольники со статистически большими граничными длинами. Остающиеся подтриангуляции формируют кластеры произвольной формы. Пересечение краев этих подтриангуляций приводит к полигонам, которые могут использоваться для определения, какие отдельные моменты лежат в каждом кластере. Полигоны могут также сравниться, знают формы, такие как торус Kent Fredric, как требуется.
IMO, методы сетки хороши для быстрых и грязных решений, но очень проголодались очень быстро на редких данных. Деревья квадрантов лучше, но БАНКИ являются моим любимым для больше сложного анализа.
Вы могли наложить логическую сетку по своей плоскости. Если сетка имеет определенное число содержавших точек, это считают "плотным" и можно было бы тогда разбавить. Это сделано много в ГИС-приложениях при работе с кластерными допусками. Используя сетку помогает разделить Ваш алгоритм утончения.
Вы могли попытаться создать Дерево квадрантов представление данных. Более короткие пути в графике соответствовали бы областям высокой плотности.
Или, выражаясь более ясно: учитывая Дерево квадрантов и обход порядка уровня, каждый узел низшего уровня, состоявший из "точек", представил бы область высокой плотности. Как уровень увеличений узлов, такие узлы представляют более низкие области плотности "точек"
Как насчет подхода морфологии?
Расширяют пороговое изображение некоторым числом (в зависимости от целевой плотности точек), тогда отмечает точкой в кластере, появится как отдельный объект.
OpenCV поддерживает морфологические операции (как был бы диапазон библиотек обработки изображений):
http://www.seas.upenn.edu/~bensapp/opencvdocs/ref/opencvref_cv.htm#cv_imgproc_morphology
"Области с определенной высокой плотностью" подразумевают, что Вы знаете приблизительно, сколько точек на единичную площадь Вы рассматриваете высоко. Это приводит меня к подходу сетки, где Вы разделяете свою общую площадь на подобласти соответствующего размера, затем считаете количество точек в каждой области. Как только Вы находите области своей сетки около Вашего threshhold, можно искать соседние области сетки также.
Это действительно походит на академический вопрос.
решение, которое приходит на ум, включает r* деревья. Это делит Вашу общую площадь на индивидуально размерный и возможно перекрывающиеся поля. После выполнения этого можно тогда определить, представляет ли каждое поле 'кластер' или не для Вас путем вычисления среднего расстояния.
, Если тот подход становится трудным реализовать Вас, могут быть более обеспеченным разделением Вашего datagrid в подразделения равного размера и определение, если кластер происходит в каждом; необходимо будет очень помнить граничные условия с этим подходом все же. Я предложил бы, чтобы после начального подразделения Вы прошли и повторно объединили области с точками данных в определенном пороге определенного края.
Примените фильтр размытия к копии Вашей 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
"более темные" области теперь определяет кластеры точек.
Для добавления небольшого количества помощника в оператор Trebs я думаю, что он важный для реалистично сначала определяет, каково определение кластера, уверено, "отмечает точкой ближе вместе", это довольно неопределенно.
Берут этот демонстрационный набор, который я генерировал, я знаю, что существует кластерная форма там, я создал его.
Однако программно идентификация этого "кластера" могла бы быть трудной.
человек А мог бы считать, что большой тороидальный кластер, но Ваша автоматизированная программа более вероятно собирается решить его серия меньших кластеров в полунепосредственной близости.
кроме того, обратите внимание, что существуют регионы супервысокоплотных, которые находятся в контексте большего изображения, просто отвлекающие факторы
, необходимо будет рассмотреть это поведение и возможно цепочку вместе кластеры подобной плотности разделенный только незначительными пустотами более низкой плотности, в зависимости от определенного приложения.
Независимо от того, что Вы разрабатываете, я, по крайней мере, интересовался бы тем, как это определяет данные в этом наборе.
(я думаю, изучая технологии позади HDRI ToneMapping, мог бы быть в порядке, потому что они работают более или менее над Легкой плотностью, и существует "локальный" tonemaps и "глобальные" тональные карты, каждый уступающие различные результаты)
Я предложил бы использовать ядро среднего сдвига для нахождения центра плотности точек.
Эти данные показывают, что ядро среднего сдвига (центрируемый первоначально на краю кластера) сходится к точке кластера самой высокой плотности.
В теории (вкратце):
Несколько ответов на это подвергают сомнению, уже намекнул на средний сдвиг способ сделать его:
-
размывание Папы P изображение и нахождение самого темного пятна на самом деле оценка плотности ядра метод (KDE), который является теоретическим основанием среднего сдвига.
-
И j0rd4n и тарифицирует Ящерицу , предложил дискретизировать Ваше пространство в блоки и осмотреть их плотность.
то, Что Вы видите в анимированном числе, является комбинацией этих двух предложений: это использует движущийся "блок" (т.е. ядро) для поиска локально самой высокой плотности.
средний сдвиг является повторяющимся методом, который использует пиксельное окружение, названное ядро (подобный этот ), и использует его для вычисления средний из данных основного изображения. средний в этом контексте пиксельное взвешенное среднее координат ядра.
В каждом повторении ядро, среднее , определяет свои центральные координаты для следующего повторения - это называют сдвиг . Отсюда имя [1 116] средний сдвиг . Условие остановки для повторений состоит в том, когда расстояние сдвига спадает 0 (т.е. мы в самом плотном пятне в окружении).
А всестороннее введение в средний сдвиг (и в теории и в приложении) может быть найдено в это ppt представление.
На практике:
реализация среднего сдвига доступна в OpenCV:
int cvMeanShift( const CvArr* prob_image, CvRect window,
CvTermCriteria criteria, CvConnectedComp* comp );
Приобретение знаний O'Reilly OpenCv (книжные выборки Google) также имеет хорошее объяснение о том, как это работает. В основном просто подайте его Ваше изображение точек (prob_image).
На практике, прием должен выбрать соответствующий размер ядра . Чем меньший ядро, тем ближе необходимо инициировать его к кластеру. Чем больше ядро, тем более случайно Ваше исходное положение может быть. Однако, если существует несколько кластеров точек в Вашем изображении, ядро могло бы сходиться прямо между ними.
- Соответствие функция плотности вероятности к данным. Я использовал бы "смесь Gaussians" и соответствовал бы ему с помощью Максимизации Ожидания, учащейся запущенный алгоритмом K-средств. K-mean отдельно могут иногда быть достаточными без EM. Количество кластеров само должно было бы быть запущено с образцовым алгоритмом выбора порядка.
- Затем каждое очко может быть заработано с p (x) использование модели. Т.е. получите апостериорную вероятность, что точка была сгенерирована моделью.
- Находят, что максимум p (x) находит кластерные центроиды.
Это может быть кодировано очень быстро в инструменте как Matlab с помощью панели инструментов машинного обучения. MoG/EM кластеризация learning/K-Means обсуждена широко на веб-/стандартных текстах. Мой любимый текст является "Классификацией шаблонов" Duda/Hart.
Пробовали ли вы простые готовые решения, такие как ImagXpress от Accusoft Pegasus?
Метод BlobRemoval можно настроить на количество пикселей и плотность, чтобы найти пробивки, даже если они не являются непрерывными. (вы также можете попробовать функцию Dilate, чтобы закрыть пробелы)
Немного поиграв, вы, вероятно, сможете получить нужные вам результаты в подавляющем большинстве случаев с очень небольшим количеством кода или науки.
C #:
public void DocumentBlobRemoval (
Площадь прямоугольника,
int MinPixelCount,
int MaxPixelCount,
короткая MinDensity
)