Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > поиск монотонного прямоугольник на изображении


Автор: blackbanny 15.7.2013, 11:34
Доброго времени суток!
Имеется отсканированные изображения(ч/б), на них нужно находить пустые(без надписей) прямоугольники 20x50мм, т.е. белого цвета(небольшой шум в виде точек допускается... Подскажите, алгоритм или где исходники посмотреть можно?

Автор: _Y_ 15.7.2013, 12:35
Вам нужно искать белые прямоугольные объекты, расположенные на небелом фоне или выделять чистые прямоугольные области на изображении, где на белом фоне имеются небелые объекты?

Автор: blackbanny 15.7.2013, 13:03
Цитата(_Y_ @  15.7.2013,  12:35 Найти цитируемый пост)
выделять чистые прямоугольные области на изображении, где на белом фоне имеются небелые объекты


Автор: mrgloom 15.7.2013, 14:00
искать 4 линии-отрезка через преобразование хафа, в opencv даже есть пример.

Автор: blackbanny 15.7.2013, 15:05
Цитата(mrgloom @ 15.7.2013,  14:00)
искать 4 линии-отрезка через преобразование хафа, в opencv даже есть пример.

мне без сторонних библиотек нужно реализовать...

Автор: mrgloom 15.7.2013, 15:14
ну реализуйте http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A5%D0%B0%D1%84%D0%B0 с нуля, потом найдите список линий, найдите пересекающиеся линии, угол между которыми близок к 90 и потом найдите прямоугольники.

http://stackoverflow.com/questions/1364976/rectangle-detection-with-hough-transform

http://opencv-code.com/tutorials/automatic-perspective-correction-for-quadrilateral-objects/

Автор: _Y_ 15.7.2013, 15:32
Вариантов решения может быть множество. Хоть известные алгоритмы брать, хоть свои изобретать.

Например, можно соорудить что-то вроде такого.
1. Случайным образом выбираем точку на изображении.
2. Если точка не белая, повторяем п.1
3. Считаем, что найденная точка это прямоугольник размером 1х1 пиксель.
4. Случайным образом увеличиваем размер прямоугольника на один пиксель в одну из сторон.
5. Если прямоугольник белый (в рамказ заданных условий белости), повторяем п.4.
6. Если прямоугольник не белый возвращаемся к последнему найденному белому прямоугольнику. Записываем его в базу найденных прямоугольников.
7. Если количество найденных прямоугольников нам не нравится - возвращаемся к п.1.

Автор: blackbanny 15.7.2013, 16:59
Цитата(_Y_ @ 15.7.2013,  15:32)
Вариантов решения может быть множество. Хоть известные алгоритмы брать, хоть свои изобретать.

Например, можно соорудить что-то вроде такого.
1. Случайным образом выбираем точку на изображении.
2. Если точка не белая, повторяем п.1
3. Считаем, что найденная точка это прямоугольник размером 1х1 пиксель.
4. Случайным образом увеличиваем размер прямоугольника на один пиксель в одну из сторон.
5. Если прямоугольник белый (в рамказ заданных условий белости), повторяем п.4.
6. Если прямоугольник не белый возвращаемся к последнему найденному белому прямоугольнику. Записываем его в базу найденных прямоугольников.
7. Если количество найденных прямоугольников нам не нравится - возвращаемся к п.1.

довольно интересный вариант, но  трудоемкий)

Автор: _Y_ 15.7.2013, 19:12
Цитата(blackbanny @  15.7.2013,  16:59 Найти цитируемый пост)
довольно интересный вариант, но  трудоемкий) 

Бесспорно. Это я привел просто как кондовый такой пример решения "в лоб".

Автор: Earnest 16.7.2013, 06:40
Не такой уж трудоемкий. А в программировании - гораздо проще Хафа. 
Только я бы предложила убрать случайность, а просто последовательно сканировать строки, для каждого необработанного белого пиксела выполнить флуд-фил (рекурсивно собрать все смежные белые пикселы), посмотреть, что за область получилась (оконтурить область и посмотреть, насколько она на прямоугольник тянет). Ну там мелкие дырки внутри выкинуть, понятно. И т.д.

Автор: _Y_ 16.7.2013, 08:39
Earnest, если выкинуть случайность, получится полный перебор вариантов. Боюсь, будет работать только для очень маленьких изображений (ну и для изображений с очень мелкими белыми областями). Чуть больше - и программа будет рушиться из-за переполнения ИМХО.

Автор: mrgloom 16.7.2013, 08:49
Цитата

Только я бы предложила убрать случайность, а просто последовательно сканировать строки, для каждого необработанного белого пиксела выполнить флуд-фил (рекурсивно собрать все смежные белые пикселы), посмотреть, что за область получилась (оконтурить область и посмотреть, насколько она на прямоугольник тянет). Ну там мелкие дырки внутри выкинуть, понятно. И т.д. 



это типа выделение блобов- связных областей, можно потом посмотреть на моменты Ху(хотя они вроде чувствительны к шуму и к волнообразной границу контура например) насколько фигура похожа на прямоугольник.
http://en.wikipedia.org/wiki/Connected-component_labeling

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

Автор: blackbanny 16.7.2013, 10:38
я сделал тоже по простому smile ищу пустой прямоугольник только по левому краю страницы, т.к. во всех изображения такое возможно.
по высоте перебираю координаты с верху в низ, из каждой такой координаты строю линию толщиной в 1 пиксель и длинной 300 пикселей, если она белая, то накручиваю счетчик, если нет, то обнуляю счетчик, если найдено 120 подряд таких линий, то завершаю перебор - прямоугольник найден  smile 
в принципе, скорость меня устраивает smile

Автор: Earnest 17.7.2013, 06:41
Не будет это долго, если доступ к растру нормально организовать (а не через GDI::GetPixe; smile
В принципе, связные области можно построить и по-другому, побыстрее. Через граф смежности строк, например. Да мало ли.

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

Автор: Queuego 5.11.2022, 12:36
Модератор: Сообщение скрыто.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)