Определение границ максимальной плотности точек

← →
>|< (2012-11-13 20:51) [0]

Уважаемые мастера!
Подскажите, с помощью какого алгоритма можно определить границы распределения точек? То есть, у меня на плоскости есть область с повышенной плотностью и несколько удаленных точек от этой области.
Необходимо получить прямоугольник, который очерчивает регион с максимальной плоскостью.
Пока подумываю рассматривать проекции точек и считать расстояния между ними, но тут надо как-то связать эти проекции между собой, потому что в одной проекции точка может быть в пределах региона максимальной плоскости, а в другой - выбегать из него. Возможно, стоит считать расстояния между точками, но тут такое дело - точки не идут последовательно друг за другом и расстояние между двумя точками может равняться границам интересующего региона или выбегать на такое расстояние из этого региона. Как определить, вот в чем вопрос. То есть нужно посчитать какую-то статистическую функцию распределения и потом уже относительно нее рассчитывать расстояние каждой точки до центра распределения.
Кто силен в данной области вычислений - подскажите название алгоритма или как он должен работать, а сам код я уже сам напишу.
Заранее благодарен за любую помощь!

← →
брат Птибурдукова (2012-11-13 20:58) [1]

Э... Ищем центр тяжести (арифметическое среднее координат), ищем дисперсию, отсекаем по дельте, по двум, трём дельтам...

← →
брат Птибурдукова (2012-11-13 21:02) [2]

А вообще, по-хорошему, надо погуглить в яндексе на тему "теория планирования экспериментов" — и дальше по ссылкам.

← →
Pavia © (2012-11-14 06:29) [3]

Метод фагоцита.

← →
>|< (2012-11-14 12:21) [4]

> Метод фагоцита

к сожалению Гугл не знает о таком методе. Можно поподробней?

← →
Jeer © (2012-11-14 12:33) [5]

Была похожая задача, но не прямоугольник, а многоугольник(и).
Разбивал область на квадраты, подсчитывал плотность в каждом, сортировал по плотности, выполнял кластеризацию, склеивал квадраты по кластерам, раскрашивал.
Применимо при достаточно большом числе точек ( были сотни и тысячи ).

← →
AV © (2012-11-14 14:42) [6]

> Необходимо получить прямоугольник, который очерчивает регион
> с максимальной плоскостью.

не понятно,
размерность прямоугольника, как понимаю, неизвестна. Мы ее сами вычислить должны.
Тогда каков критерий максимальности?
Отношение площади прямоугольника к кол-ву точек внутри?

← →
Jeer © (2012-11-14 14:51) [7]

Введя понятие относительной дифференциальной плотности p ( плотность в ограниченном пространстве ) от 0 до 1 и выбирая уровень отсечки 0 < p < 1 можно определить границы прямоугольника, интегральная плотность в котором не менее p.

← →
>|< (2012-11-14 14:58) [8]

> > Необходимо получить прямоугольник, который очерчивает
> регион
> > с максимальной плоскостью.

ошибся. надо читать как "с максимальной плотностью"

← →
>|< (2012-11-14 15:19) [9]

вот ссылка на изображение
http://savepic.su/2884490.htm
Зеленый прямоугольник - это желаемый результат работы алгоритма

← →
>|< (2012-11-14 15:21) [10]

вот еще один пример
http://savepic.su/2901901.htm

← →
AV © (2012-11-14 15:25) [11]

пока смотрел нейронные сети, на хабре что-то видел подобное

http://habrahabr.ru/qa/14837/
и
http://habrahabr.ru/post/135332/

может, подойдет?

← →
брат Птибурдукова (2012-11-14 15:32) [12]

> >|< (14.11.12 15:19) [9]
Чем [1] не устраивает?

← →
MBo © (2012-11-14 15:36) [13]

На тех наборах данных, что на картинках, замечательно отработает K-means

← →
AV © (2012-11-14 15:42) [14]

> MBo © (14.11.12 15:36) [13]

угу

Кстати,

>
> http://habrahabr.ru/qa/14837/
> и
> http://habrahabr.ru/post/135332/
>

очень похоже на сеть

"над" плоскостью с точками строим матрицу, 1:1
Каждая точка увеличивает счетчик элемента матрицы "над" и соседних с ним, в определенном радиусе. (назовем это Digital-проекция, DP)
Затем несколько раз декреминируем все элементы, отличные от 0, на 1.
DP отдаленных точек исчезнут, останутся только в скоплении.
Остается обвести это дело прямоугольником.

← →
>|< (2012-11-14 15:58) [15]

вот еще два примера
http://savepic.su/2898819.htm
http://savepic.su/2887552.htm

← →
>|< (2012-11-14 16:03) [16]

> На тех наборах данных, что на картинках, замечательно отработает
> K-means

Спасибо за идею!
Попробую ее реализовать.

← →
Очень Злой (2012-11-14 17:19) [17]

> Необходимо получить прямоугольник, который очерчивает регион
> с максимальной плоскостью.

Это прямоугольник внутри которого находится 1 точка, а длины его сторон стремятся к 0.

← →
брат Птибурдукова (2012-11-14 18:19) [18]

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

← →
Очень Злой (2012-11-14 18:27) [19]

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

угу, а если площадь стремиться к 0 то плотность точек в этом прямоугольнике будет стремиться к бесконечности

← →
брат Птибурдукова (2012-11-14 18:28) [20]

> Необходимо получить прямоугольник, который очерчивает регион
> с максимальной плоскостью.

← →
Pavia © (2012-11-14 19:05) [21]

> > Метод фагоцитак сожалению Гугл не знает о таком методе.
> Можно поподробней?

http://courses.graphicon.ru/files/courses/vision/2006/lectures/lect02_06.ppt
64 слайд.

← →
Очень Злой (2012-11-14 19:09) [22]

> брат Птибурдукова (14.11.12 18:28) [20]
>
>
> > Необходимо получить прямоугольник, который очерчивает
> регион
> > с максимальной плоскостью.

вобще-то "плотностью"

> >|< (14.11.12 14:58) [8]
>
>
> > > Необходимо получить прямоугольник, который очерчивает
> > регион
> > > с максимальной плоскостью.
>
> ошибся. надо читать как "с максимальной плотностью"

Но если я не прав в [17] , то дайте определение понятию "плотность" в рамках данной задачи, ибо я так понял что это отношение кол-ва точек в прямоугольнике к площади этого прямоугольника...

← →
>|< (2012-11-15 13:44) [23]

> Но если я не прав в [17] , то дайте определение понятию
> "плотность" в рамках данной задачи, ибо я так понял что
> это отношение кол-ва точек в прямоугольнике к площади этого
> прямоугольника...

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

← →
Аббат Пиккола (2012-11-15 14:53) [24]

Проблема пока с постановкой задачи, а не с ее решением.

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

Это что?

Зашумленные буквы или иероглифы, изначально имеющие фиксированное прямоугольное знакоместо с некоторыми заранее известными свойствами?

Если автор уже решил абстрагироваться от предметной области именно таким образом, определив задачу, как "поиск прямоугольного скопления точек", то, наверно, он уже имел в виду некий путь решения своей задачи, который ему показался перспективным?

Но если вообще он видит пока самого пути, то с чего он решил, что именно эта абстракция адекватна поставленной задаче на предметном уровне?

Или же в данном случае это секрет? Но если это топсекретно, стоит ли это начинать это на форуме обсуждать?
Вопросов больше, чем ответов...

Проще, ИМХО, прямо сообщить публике, о какой предметной области идет речь. И, возможно, ссылки на решения посыпятся как из рога изобилия.

← →
БарЛог © (2012-11-15 14:59) [25]

> Проще, ИМХО, прямо сообщить публике, о какой предметной области идет речь.

Имеются gps-координаты телефонов друзей. В пятницу вечером программно необходимо определить, "на какой раён рулить".

> БарЛог © (15.11.12 14:59) [25]

друзья в бане, а вещи сперли и везут в направлении выгона телят деда Макара.
"на какой раён рулить"? :)

хотя.. судя по картинкам, самое время рулить в часть, что бы к построению не опоздать :)

← →
>|< (2012-11-15 16:42) [28]

> Проще, ИМХО, прямо сообщить публике, о какой предметной
> области идет речь. И, возможно, ссылки на решения посыпятся
> как из рога изобилия.

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

← →
>|< (2012-11-16 15:00) [29]

Проблемы алгоритма k-means:

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

← →
Очень Злой (2012-11-16 15:39) [30]

А скан паспорта как размещен на изображении?
стороны скана приблизительно параллельны границам изображения или скан паспорта может располагаться под любым углом?

← →
>|< (2012-11-16 15:48) [31]

> А скан паспорта как размещен на изображении?
> стороны скана приблизительно параллельны границам изображения
> или скан паспорта может располагаться под любым углом?

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

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

Планирую вычислять границы паспорта по выделению границ фона, на котором он изображен.
Вот таким методом http://robocraft.ru/blog/computervision/365.html , например.

← →
Очень Злой (2012-11-16 16:31) [32]

> допустимы незначительные углы поворота,

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

← →
>|< (2012-11-16 16:46) [33]

> если углы незначительные, то почему бы не построить 2 гистограммы
> вдоль координатных осей и находить зону наибольшего "совокупления"
> точек отдельно по координате X и Y , т.е. уже не в плоскости,
> а на двух прямых?
>

я так и думал в самом начале:

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

Если рассчитывать среднее проекций, то точки с максимальным выбегом будут вносить помехи в среднее.
И как определять зону максимальной плотности? Необходимо наверное разбивать на какие-то отрезки и считать количество проекций в данном отрезке. Потом выбирать отрезки с минимальным отклонением от максимального... Надо будет попробовать.

← →
Аббат Пиккола (2012-11-16 17:13) [34]

Я бы попробьовал разные вещи. Например, целую гистограмму ради поиска границы делать лениво. Но можно сделать гистограмму частично. Представим себе одну полоску этой самой гистограммы. Полоска имеет 3 параметра:

1. "номер стороны" (0..3) будущего прямоугольника
2. ширину
3. угол наклона (относительно будущей "стороны")

Далее организуем 3 вложенных цикла:

цикл1 - номер стороны 0..3
цикл2 - угол с некоторым шагом -10..10 * "шаг угла"
цикл3 - "движение" с некоторым "шагом по оси x (для сторон 0;2) или y (для сторон (1;3)"
{
В этом цикле с некоторым фиксированным шагом "двигаем" полоску, (в зависимости от "номера стороны", в определенном направлении - например для "левой стороны" слева-направо). И подсчитываем число точек внутри полоски. Как только это число становится выше некоторого небольшого порога (параметр, который следует подобрать экспериментально), выходим из цикла, поместив результат в массив, адресуемый углами
}

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

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

Как-то так.

← →
Аббат Пиккола (2012-11-16 17:16) [35]

Надеюсь, эта база не государственного типа?

← →
>|< (2012-11-16 17:20) [36]

> Надеюсь, эта база не государственного типа?

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

Определение границ максимальной плотности точек Найти похожие ветки