Вот вдруг возникла такая задача (даже не задача, а пока просто интерес)

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

я знаю, что что-то похожее делает googles (для android), когда решает судоку. 

BSOD, поспрашивай у народа, пользующегося Abbyy form reader, насколько там хорошо распознаются "кривые" сканы таблиц. Если распознаются - то готовое решение можно купить ;)

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

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

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

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

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

т.е. попробовать выделить все места, где рисунок похож на линию и выбрать наиболее подходящее направление (естественно, с точностью до 90 градусов)

ну а потом опять пораспознавать линии и понаходить клеточки(ну и их содержимое, соответственно)

обнаруживать линии можно попробовать с помощью преобразования Хафа: http://en.wikipedia.org/wiki/Hough_transform

Это сообщение отредактировал(а) maxim1000 - 20.3.2011, 21:23

всем Спасибо за ответы! 

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

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