GNOME 2.12 - что день грядущий нам готовит

Можно и так. У меняя вобще миранда стоит. Я ею вполне доволен. Пользуюсь в основном только ICQ, так как знакомых из джаббера нету.

ЗЫ. С линуха я свалил, когда по работе потребовалось использовать MS SQL. Так до сих пор и сижу... Винда и Open Source - окружение.

Миранда - тоже прекрасно. Я ее тоже под винюками пользую сейчас у заказчика в офисе - только она справилась прорубиться через местный ntlm прокси. Только вот сервер лучше таки jabber.ru, не гугловое поделие. Соббсно, тогда Вам и клиент google talks не нужен (опять таки если не пользуетесь голосовыми фичами).

Хотя я обычно иду по немного другому пути. Даю идею, делаю базовую реализацию (прототип) и пытаюсь ею заинтересовать народ. Так и с main.pdf -- это своего рода прототип. Там "в одном месте" собрана информация необходимая для понимания программистом "естественного" интеллекта, естественного распознавания образов... Т.е. как у человека устроено "то", "что" он пытается программировать. Кто заинтересуется, с теми будем доводить теорию до конца и переходить к решению прикладных задач.

Просто OCR или SR -- это не совсем то, что я хочу.

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

> Даю идею, делаю базовую реализацию (прототип) и пытаюсь ею заинтересовать народ

Совершенно здравый подход.

> Просто OCR или SR -- это не совсем то, что я хочу.

Да, я понял. В общем, я даже согласен, что научного интереса в "просто OCR" немного, поэтому прекрасно понимаю отсутствие энтузиазма у Вас. Беда в том, что оно таки нужно. А сделать его реально могут только спецы в этой области, это действительно не свистелки.

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

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

ок. ставлю задачу: распознавание строки печатного текста, набранного одним шрифтом %)

Строка печатного текста - прямоуголиник m*n из элементов изображения, зажанных уровнями серого от 0 до 255. Символ -- элемент k*l, который может появиться в любом месте прямоугольника. Постановка задачи уточняется так: выпонить сегментацию -- разбиение на элементы, в каждом из которых находится один фрагмент, провести классификацию фрагмента в словаре символов. В результатах распознавания выделить слова -- пространсственно структурированные цепочки символов.

Какие механизмы будем использовать для сегментации и классификации ?

Насчет OCR, есть другое решение, можно попробовать изложить теорию, достаточнуч для написания OCR. Хотя я хорошо понимаю , что такое отсутствие времени.

Я бы не сказал, что я загорелся идей ИИ только что. Меня в этом вопросе, для начала интересовала совсем другая часть, меня интересовал ИСТОЧНИК идей. Не то чтобы раньше у меня этого понимания не было, но в процессе дискуссии, для меня самого появилась полная ясность, и поэтому для меня этот вопрос потерял интерес как решенный.

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

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

Не потому, что я все сделаю за пять минут, просто так я воспринимал и воспринимаю :-)

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

Начинаем обрастать подробностями:

1. Шрифт (набор шрифтов?) - параметр. Возможен, если нужно, препроцессинг шрифтов в формат, удобный для OCR)

2. Почему именно строки? Есть некая растровая картинка, хочется ее текстового представления (формат растра - по усмотрению автора, TBD)

3. Я понимаю, что это наглость - но было бы круто как-то научиться сохранять информацию о форматировании.

4. API на C. Минимум внешних зависимостей (все, что можно - через hooks или через память).

Как-то вот так, на вскидку.

Похоже одну и ту же мысль мы высказали одновременно!

> Символ -- элемент k*l

С идеей распознавания векторных шрифтов попрощаться?

Можно ли использовать обратную связь от словарей - т.е. увеличить возможность распознавания "правильных" слов?

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

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

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

>1. Шрифт (набор шрифтов?) - параметр. Возможен, если нужно, препроцессинг шрифтов в формат, удобный для OCR)

какой попадется =)

>2. Почему именно строки? Есть некая растровая картинка, хочется ее текстового представления (формат растра - по усмотрению автора, TBD)

разбиение образа на текстовые строки - достаточно тривиальная задача. Чуть сложнее - форматирование таблицами (и ещё чуть сложнее - форматирование таблицами с невидимыми границами).

>3. Я понимаю, что это наглость - но было бы круто как-то научиться сохранять информацию о форматировании.

наглость %). ты ставишь задачу "сразу и всё". Распознавание _строки_ текста - уже очень неплохо для начала. естественно, алгоритм должен разрабатываться с учетом последующего наращивания функциональности.

форматирование в TeX устроит? =)

>4. API на C. Минимум внешних зависимостей (все, что можно - через hooks или через память).

само-собой С. А зависимости...их кол-во зависит от кол-ва форматов картинок, понимаемых библиотекой. (на самом деле, думаю grayscale pixmap хватит за глаза)

> наглость %). ты ставишь задачу "сразу и всё". Распознавание _строки_ текста - уже очень неплохо для начала. естественно, алгоритм должен разрабатываться с учетом последующего наращивания функциональности.

svu отчасти прав. найденное решение локально поставленной задачи может ограничить развитие архитектуры.

Я предлагаю идти методом "сверху-вниз", учитывая, что возможно, а что нет на нижних уровнях.

В общем, на мой чайниковский взгляд, выходом является:

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

>Я предлагаю идти методом "сверху-вниз", учитывая, что возможно, а что нет на нижних уровнях.

архитектура - сверху вниз. имплементация - снизу вверх

> Главное, чего я не знаю - по мере усложнения задачи как будут "верхние" уровни влиять на "нижние"

Алгоритмизация этого механизма и с моей точки зрения один из самых сложных вопросов.

Давайте пока что за архитектуру говорить...

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

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

эээ...стоп. шрифт+позиция в шрифте не надо. Вряд ли ocr реализованная, как простейший компаратор битмапов - даст правильный результат.

Этого-то я и боялся... И какие нонче модные эвристики? Да, кстати, есть ли среди них незапатентованные?;)

Ну ок, это был взгляд чайника. А как надо?

Насчет запатентованных эвристик -- я о таких не знаю. Структура эфристики зависит от сруктур решаемой задачи. Чаще всего это сводится к ограничению дерева перебора двумя-тремя уровнями.

2ALL

Знаком ли кто-нибудь с метафорой "Информационной достки"?

>Ну ок, это был взгляд чайника. А как надо?

анализ формы символа каким-либо способом. Потом, _после_ распознавания и спеллчека (а ещё лучше - семантической проверки слова) уже можно определить тип шрифта (моноширинный,с засечками, италик и т.д) - но это задачи уже корректного распознавания форматирования.

> Знаком ли кто-нибудь с метафорой "Информационной достки"?

Нет, а что это?

http://khpi-iip.mipk.kharkiv.edu/library/case/buch/ch11.html

2svu: это один из способов формализовать отношения между уровнями абстракции системы.

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

Итеративное распознавание строк? Каждоя строка распознается с новым словарем?

>Итеративное распознавание строк? Каждоя строка распознается с новым словарем?

не...словарь общий для документа. Обычно в документах используют 3-4 начертания.

А, понял. Думаю, лучше использовать не строку, а textbox как в латехе.

>А, понял. Думаю, лучше использовать не строку, а textbox как в латехе.

непринципиально. распознавание-то идет построчно. т.е.

1. делим образ на блоки 2. текстовые блоки делим на строки 3. итеративно передаем строки в функцию распознавания.

перед пунктом 1 _потом_ нужно будет добавить вырваниваение образа по горизонтали.

Да. Это классическая схема OCR, насколько я знаком с этой проблематикой. Вариант беспроигрышный и, что важно, малозатратный. Но, это только для простых документов, не содержащих сложного форматирования и формул. Если потребуются они, придется изначально закладывать боолее сложную архитектуру типа Информационной доски.

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

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

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

Еще один момент -- поворот текста (лист в сканере лежит неправильно, два листа под разным углом). Алгоритм сегментации сильно усложняется...

Сории. Вынужден отлучиться на час.

Жаль, что нельзя сразу и шрифт...

> Еще один момент -- поворот текста (лист в сканере лежит неправильно, два листа под разным углом). Алгоритм сегментации сильно усложняется...

А разве без этого можно? Гарантировать абсолютно точное позиционирование в сканере как бы невозможно...

Первоначальная постановка задачи Geek`ом не учитывала данный аспект.

Давайте добавим?:)

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

Хотя, кто знает, как работает gocr ?

Кстати, хороший вопрос. Вы не смотрели на внутренности gocr?

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

>Еще один момент -- поворот текста (лист в сканере лежит неправильно, два листа под разным углом). Алгоритм сегментации сильно усложняется..

определение угла, под которым лист лежит на сканере возможно ещё на этапе предварительного сканирования. никаких ИИ тут не надо

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

вообще-то можем. Текст и картинка слишком сильно отличаются друг от друга. Сравнить хотя бы частотное распределение. Или учесть то, что у картинки как правило, сильно отличающийся по цвету фон =)

>Жаль, что нельзя сразу и шрифт...

а сразу и не надо. Можно потом пройтись по составленному словарю глифов, определить для начала U|B|S|I глифы, а потом сопоставить глифы имеющимся в системе шрифтам. Скажем так - задача на пару порядков проще, чем собственно распознавание.

Кстати, есть идея для GUI: после распознавания формировать список стилей, и при выборе элемента списка подсвечивать текст, набранный этим стилем в документе. Таким образом, пользователь получит возможность подправить шрифт сразу во всех нужных местах простой правкой стиля.

Как это по ХИГовски оформить?