алгоритм для анализа изображения

← →
ford © (2012-09-07 10:46) [0]

Доброго времени суток!
Печатается бланк строго-определенного вида, на котором человек заполняет графы. Хотелось немного автоматизировать процесс обработки таких бланков, путем применения фотоаппарата, для "сканирования" заполненных бланков и дальнейшей обработки изображения. Т.е. хотябы проверить заполнен бланк полностью или нет.
Покопался в интернете в поисках алгоритмов которые могут помочь в решении задачи, вроде бы все понятно. Первое что необходимо сделать с изображением, это привести его к Ч/Б виду и далее по наличию и количеству черных точек в определенных местах изображения, можно определить есть там текст или нет. Но споткнулся на том, что до всего этого надо каким-то образом правильно позиционировать изображение. Т.е. например перевернуть его и/или увеличить/уменьшить.

Помогите, советом или ссылкой на описание алгоритма, при помощи которого можно правильно отпозиционировать и преобразовать отсканированное изображение.

Я пытался применить алгоритм, который используют для распознования штрих кодов, т.е. нахождения в одной линии строго чередующихся последовательностей означающих 666, но как-то не очень получается :( ибо для штрих кода достаточно одной полоски пикселей, а тут получается надо всё изображение крутить :(
т.е. представьте 800х600 точек и относительно каждой из этих 48000 точек можно повернуть на 360 градусов, т.е. для того чтобы найти на изображении штрих код надо произвести 172800000 итераций.
И это еще если не учитывать что одно и то-же изображение может быть по разному "отсканировано", наверняка встречали когда пользователи сканирую фотографию 9х12 на весь размер сканера.

← →
Давайте будем жрать! (2012-09-07 11:02) [1]

Купить Abbyy Form Reader будет дешевле в итоге.

← →
GanibalLector © (2012-09-07 11:26) [2]

2 Давайте будем жрать! (07.09.12 11:02) [1]
Во-первых, Form Reader уже давно похоронили, т.к. вышел Flexi Capture. Но и тут беда, Flexi Capture родился мертвым.

2 ford © (07.09.12 10:46)
Насколько профессионально вы хотите этим заниматься? Если серьезно, то надо начать с покупки сканера. Второе, пришлите бланк, погляжу что с ним можно сделать. Ну а далее будете решать самостоятельно: либо покупка софта (от $5000 и это не Abbyy), либо покупка услуги (в среднем 0.05$ с листа), либо самостоятельно.

Бланк можно выслать сюда: ocr.ukraine[собака]ukr.net

Удачи!

← →
ford © (2012-09-07 12:27) [3]

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

К стати для распознавания текста можно попробовать использовать свободное ПО CuneiForm, там же есть и библиотеки с исходниками.

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

← →
brother © (2012-09-07 12:34) [4]

> Во-первых, Form Reader уже давно похоронили, т.к. вышел
> Flexi Capture. Но и тут беда, Flexi Capture родился мертвым.

какие смелые заявления...

← →
Давайте будем жрать! (2012-09-07 12:52) [5]

> brother © (07.09.12 12:34) [4]
Про "родился мёртвым" спорить не буду, неинтересно, а про ФормРидер согласен в целом. Запамятовал, что кроме end-user Form Reader есть ещё Flexi Capture, который именно для интеграции распознавания в свой софт.

> использовать вэб камеру как "сканер", поднес листочек к
> камере
Малое разрешение + повороты по трём координатам + неравномерность освещения.

> Да и распознавать буквы я не собирался, а только показать
> есть ли в определенных местах бланка текст или нет.
В студенчестве с напарником ~1.5 года на это потратили, на построении скелетной модели объектов обломались (я открыл для себя инет, а к напарнику супруга приехала) %-)

← →
GanibalLector © (2012-09-07 13:24) [6]

2 brother © (07.09.12 12:34) [4]

> какие смелые заявления...

Это не заявления, а факты. Ковырял не один месяц.

← →
Дмитрий С © (2012-09-07 13:38) [7]

Допустим на бланке 6 квадратов. По их расположению можно понять где верх где низ (например те что посередине они чуть ближе к верху).
Ищешь все темные области на светлом.
Находишь среди них свои квадраты (зная их взаимное расположение).
Поворачиваешь изображение и обрезаешь лишнее.

Я бы с этого начал.

← →
Давайте будем жрать! (2012-09-07 13:43) [8]

> Дмитрий С © (07.09.12 13:38) [7]
Сие называется "реперные точки".

← →
GanibalLector © (2012-09-07 14:02) [9]

2 Давайте будем жрать! (07.09.12 13:43) [8]

> Сие называется "реперные точки".

Это понятие вводит Abbyy. Кстати, в некоторых продуктах нет такого понятия и можно "регистрировать" лист по любым областям формы, что гораздо удобнее.

← →
Давайте будем жрать! (2012-09-07 14:18) [10]

> Это понятие вводит Abbyy
http://ru.wikipedia.org/wiki/Реперная_точка

← →
QAZ (2012-09-07 14:42) [11]

> привести его к Ч/Б виду и далее

это уже ошибка,приводящая к увеличению гемороя

← →
GanibalLector © (2012-09-07 14:50) [12]

2 Давайте будем жрать! (07.09.12 14:18) [10]

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

← →
знайка (2012-09-07 14:54) [13]

Есть же спец программы, с ридерами.
Создаешь шаблон, по нему печатается документ, а ридер считывает информацию.
Человек отметил чегото, ридер считал, данные отдал, вроде так..

← →
ford © (2012-09-07 15:24) [14]

> это уже ошибка,приводящая к увеличению гемороя

Почему?
ведь тогда будут только два цвета, черный и белый (мне кажется что finereader так и делает)
если учитывать оттенки то вообще застрелиться можно

← →
ford © (2012-09-07 15:39) [15]

> Дмитрий С © (07.09.12 13:38) [7]
>
> Допустим на бланке 6 квадратов. По их расположению можно
> понять где верх где низ (например те что посередине они
> чуть ближе к верху).
> Ищешь все темные области на светлом.
> Находишь среди них свои квадраты (зная их взаимное расположение).
>
> Поворачиваешь изображение и обрезаешь лишнее.
>
> Я бы с этого начал.

Это понятно, только вот КАК?
Ведь после сканирования и урезания до Ч/Б от квадратов могут остаться не совсем квадраты :) все зависит от уровня Threshold. Конечно можно сделать несколько уровней порога и искать квадратики на каждом полученом изображении но опять таки см. п. выше. Из квадратиков могу получиться не совсем квадратики :(
Может:
1. задаем расстояние между "квадратами". и к=100
2. определить что такое "темная область", как (100-к)х(100-к) черные пикселя
3. по определению из п. 2 выбрать все непересекающиеся области изображения.
4. если по определению из п.1 найдены две области то закончить иначе к=к-1 и если к<100 то повторить с п.2

← →
Дмитрий С © (2012-09-07 15:54) [16]

> Это понятно, только вот КАК?

Во-первых не делай Ч/Б.

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

Например, можно искать по три примерно равные по форме темные области находящиеся на 1 прямой. Искать среди все темных областей на светлом. Причем можно заранее отсеять заведомо неподходящие области.
К тому же вряд ли тебе понадобится распознавать листы повернутые на 45 градусов. На деле угол будет очень маленький и черные квадраты будут достаточно близки к краям.

← →
картман © (2012-09-07 16:00) [17]

> QAZ (07.09.12 14:42) [11]
>
>
> > привести его к Ч/Б виду и далее
>
> это уже ошибка,приводящая к увеличению гемороя

finereader так делает...

> ford © (07.09.12 15:24) [14]

> ведь тогда будут только два цвета, черный и белый (мне кажется
> что finereader так и делает)

что является его большим недостатком.

> ford © (07.09.12 15:39) [15]

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

← →
Давайте будем жрать! (2012-09-07 16:18) [18]

> Ведь после сканирования и урезания до Ч/Б от квадратов могут
> остаться не совсем квадраты
Особенно если лист не перпердикулярен веб-камере.

> все зависит от уровня Threshold
Просто после перевода в ЧБ надо ещё через высокочастотный фильтр прогнать, чтоб мелкий шум отсечь. После этого сегментировать и оконтурить, хехехе.

← →
Труп Васи Доброго © (2012-09-07 16:35) [19]

> что является его большим недостатком.

С такой лёгкостью рассуждать о "больших" недостатках программы - мирового лидера в области распознавания текстов может разработчик по крайней мере более качественной программы. У меня FR 2009 (то есть давно устаревший), я ему недавно подсунул работёнку распознать и перекинуть в EXCEL 56 .tif файлов, содержащих в общей сложности 1560 страниц текста (таблицы с данными, одинаковой структуры, но не одинакового размера). Отсканированы они были разными людьми, на разных сканерах, соответственно и ориентация картинок была разная: и прямо, и боком, и вверх ногами и под углом.
Так эта "плохая" программа со всеми своими "большими" недостатками (дилетанты же делали, с Картманом не советовались) сама прекрасно определила на всех картинках правильную ориентацию текста, сама "развернула" в правильное положение и, естественно, сама всё прекрасно распознала и правильно передала результат в Excel. Жаль, что не было под рукой великолепной беспроблемной программы Картмана (а вообще кто-то видел его программы?), она бы наверняка лучше справилась.

← →
Pavia © (2012-09-07 17:39) [20]

FR 2009 гораздо лучше работает всех его предшественников. Как по скорости так и по качеству распознавания.

Правда по качеству меня не устраивает многое:
- С таблицами стала работать гораздо лучше, но процент брака меня не устраивает.
- Формулы не распознаёт.
- При создании точной копии точная копия не получается. С геометрически - искажениями от линзы фото аппаратными бороться не умеет. Книгу разрезает плохо.
- Алгоритм бинаризации могли бы и по лучше использовать.

> Труп Васи Доброго © (07.09.12 16:35) [19]
>
> > что является его большим недостатком.
>
> С такой лёгкостью рассуждать о "больших" недостатках программы
> - мирового лидера в области распознавания текстов может
> разработчик по крайней мере более качественной программы.

" Но я же могу рассуждать о качестве омлета, хотя еще ни разу не снёс ни одного яйца."

и, потом, это было не мое мнение, а научного консультанта ABBYY:
http://www.intuit.ru/department/expert/vmodelbpt/6/

мое мнение об этой программе сложилось, в основном, после попытки распознать буквари в pdf-, djvu- форматах: как можно было слова вроде "алгоритм" распознать как "флгоритм"(точно букву не помню, но получившегося слова в русском языке не существует, да и буквосочетаний тоже) и так по всем текстам для любых слов. Это для среднего качества сканов, про зашумленные говорить и вовсе не приходится - это как раз из-за приведения к двубитному восприятию. А формулы?

> - Алгоритм бинаризации могли бы и по лучше использовать.

в задницу его!

> как можно было слова вроде "алгоритм"

У тебя автомобиль есть? Ты его купил и сразу сел и поехал? Или ты всё-же учился и экзамены сдавал? А там всего один руль, три педали и один рычаг передач. Так вот если FR немного подучить (есть такая функция), то он великолепно распознает практически любого качества скан. Мы его обучали распознавать машинописный текст (где чернила от старости уже расплылись), так после пятого листа он освоился и остальные 2к листов схрумкал без единой ошибки. Вы наверное пытаетесь использовать его не по назначению. FR при всей его мощи не предназначен для редкого распознавания 0.5 страниц текста непонятного шрифта раз в год, это можно и ручками перебить. Или ты его для таких целей купил? Или не покупал? А вот когда тебе необходимо тысячу - другую сканов распознать за сутки, то тут ты будешь петь оды и воздавать хвалу тем "суровым парням", которые создали это чудо. На данный момент я ничего лучшего не знаю (да меня и FR вполне устраивает).

> Давайте будем жрать! (07.09.12 12:52) [5]
> В студенчестве с напарником ~1.5 года на это потратили,
> на построении скелетной модели объектов обломались (я открыл
> для себя инет, а к напарнику супруга приехала) %-)

Полтора года без супруги! Вот что значит молодость и задор.

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

> Вот что значит молодость и задор.
Вот что значит расстояние между Вьетнамом и Украиной... ;-)

← →
>|< (2012-09-11 18:08) [26]

2 ford
Недавно закончил подобную систему, которая обрабатывала пачки отсканированных школьных бланков. Дизайн бланков можно было менять на этапе проектирования.
Расскажу в двух словах, как это работает:
Для определения угла 90, 180, 270 градусов достаточно 3 опорных квадратов в трех из четырех углах. Подобным образом устроен QR-код. Достаточно прочитать один раз 4 угла и в зависимости, от того, какие углы закрашены черным - определить угол поворота.
Потом необходимо было определить незначительный угол поворота 1-2 градуса, потому что бланки в пачке могли быть неровно сложены. Это уже определяется по разнице высот опорных квадратов, которые лежат на одной линии.
По поводу бинаризации - можно использовать Адаптивный Порог. Как он вычисляется - Гугл в помощь.
Ну и советую обратить внимание на библиотеку OpenCV, которая заточена на работу с изображениями.

← →
уважаемый форумчанин (2012-09-11 18:25) [27]

> >|< (11.09.12 18:08) [26]
Но у тебя ж классический сканер был, а не фотографирование на камеру?

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

← →
>|< (2012-09-12 17:51) [28]

> А OpenCV из делфи использовал? А то где-то тут на днях темка
> появлялась, якобы использование этой библиотеки в делфи
> сопряжено с инвалид поинтер оперейшнами и аксес виолейшнами.
> ..

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

← →
>|< (2012-09-13 12:10) [29]

OpenCV нужен, если критична производительность кода и вместо написания функции в несколько страниц кода и дней работы можно использовать уже готовую и безглючную реализацию.
Например, в одной из задач было необходимо реализоваь определение границ сканов паспортов на странице A4. Паспорта могли быть как на белом, так и на черном фоне и иногда вокруг скана бывает тень самого паспорта, которая мешает определить границы паспорта. С учетом всех этих требований мне пришлось разрабатывать около двух недель более-менее сносный алгоритм, который выдавал приемлемые результаты.
А в OpenCV уже есть готовая функция, которая умеет искать контуры изображения и последовательности точек одного цвета. Да и бинаризацию она делает быстрее. И таких функций для работы с изображениями, особенно для его анализа(детекция лица, нахождение прямоугольников и т.д.)порядка 500.
Вот почему и порекомендовал разобраться с этой библиотекой.

алгоритм для анализа изображения Найти похожие ветки