GotAI.NET

Форум: Проблемы искусственного интеллекта

 

Регистрация | Вход

 Все темы | Новая тема Стр.2 (8)<< < Пред. | След. > >>   Поиск:  
 Автор Тема: На: Распознавание символов
Corwin
Сообщений: 1324
На: Распознавание символов
Добавлено: 29 май 07 2:15
>Так эта ведь не шрифтоЗависимая. Она как раз шрифтоНЕзависимая.

Нейронные сети в основном относятся к шрифтоЗависимым алгоритмам (Fixed Font OCR или Multifont OCR).
Вообще НС можно (грубо правда) сравнить с попиксельным сравнением изображений. Для НС не имеет особого значения что подается на вход (символ или логотип). Она распознает изображения так как ее научили. В шрифтоНЕависимых (Omnifont OCR) алгоритмах, что подается на вход имеет очень большое значение. Большинство Omnifont OCR не способно распознавать логотипы, хотя хорошо справляются с распознаванием символов.

>Да, я пробовал только те символы, с которыми у программы могли бы возникнуть сложности. Т.е. я пробовал "Г" и "Т", "О" и "0", "М", "Н" и "И"

Собственно Вы попробовали символы у которых схожие семантические структуры. а для НС семантическая похожесть не имеет особого значения. Так "Г" и "Т" что для НС что для попиксельного сравнения достаточно сильно отличаются, поскольку графически там совпадает только верхушка буквы "Г" что равняется не более 40% (то же правило распространяется и на другие названые Вами символы). При семантическом сравнении буква "Т" более чем на 60% процентов состоит из "Г", поэтому возможное путание таких символов удел именно Omnifont систем. Конечно другой вопрос если вы реализировали НС которая динамически ищет изображения символов. Тогда вполне возможный больший процент похожести этих символов. Хотя у меня впечетление что Вы тестировали именно классическую НС.
[Ответ][Цитата]
Corwin
Сообщений: 1324
На: Распознавание символов
Добавлено: 29 май 07 2:17
Вот кстати через Гугл ( ) нашел статью "Создание приложения для оптического распознавания символов на основе Нейронной Сети"
http://gotai.net/documents/doc-imp-006.aspx
где есть программа (с исходниками) реализирующая OCR на нейронных сетях. Поверхностное изучение программы впечетлило: качество распознавания 100% даже при зашумленном изображении. НО стоит заметить что программа сама нарисовала символ, сама обучилась, и сама распознала ТОТ ЖЕ символ что сама и нарисовала. Нет возможности поменять шрифт или загрузить изображения с файла. Поэтому правильно оценить качество ее работы на разных шрифтах / изображениях не является возможным (нужно будет поиграться с исходниками). Должен заметить что аналогичный результат можно получить обычным попиксельным сравнением распознаваемого изображения и нарисованного символа шрифта.
[Ответ][Цитата]
anatoli
Сообщений: 249
На: Распознавание символов
Добавлено: 29 май 07 3:58
Хех, глянул программку.. Че-то я при уровне шума выше 20% уже ничего разобрать на картинке не смог (во всяком случае, более или менее однозначно, а так - пятна роршаха, думай что хочешь).. А прога, тем не менее, находит и при 70%.. Что-то тут не то..


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

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


> Нейронные сети в основном относятся к шрифтоЗависимым алгоритмам
> В шрифтоНЕависимых (Omnifont OCR) алгоритмах, что подается на вход имеет очень большое значение

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

Я так понимаю, та система, что делал я - это была шрифтоНЕзависимая система, т.к. она могла распознать практически любой шрифт и специально под каждый не тренировалась (тренировалась она на 3-4 шрифтах и на "от руки").
[Ответ][Цитата]
anatoli
Сообщений: 249
На: Распознавание символов
Добавлено: 29 май 07 4:13
> Должен заметить что во всей моей системе «интеллектуальным» можно считать только сравнение семантической структуры символа. В остальном вся программа это реализация машинного зрения.

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

Я сейчас как раз занимаюсь Computer Vision'ом, и, на сколько мне известно, там еще поле непаханное. При том что там-то и идет самая "интеллектуальность".. А OCR по сравнению с этим вообще можно назвать простым статическим алгоритмом. А из ваших слов получается, что наоборот. Или может быть я Вас не так понял?
[Ответ][Цитата]
Corwin
Сообщений: 1324
На: Распознавание символов
Добавлено: 29 май 07 11:02
>Что-то тут не то

Вполне то. Просто вы ищите смысл в целой картине, тогда как прога ищет только отдельные пиксели которые соответствуют символу.

>я больше имел в виду буквы при их написании от руки

Это уже более интересно Хочу спросить: Вы где-нибудь встречали системы распознания символов которые работали бы НС? Если да, то что это за продукты и как их можно протестировать. Поскольку все продукты, что мне попадались, которые распознают символы (начиная от распознания рукописных символов в КПК (правда там в большинстве используются online методы) и до проф OCR) почему-то не используют НС, или используют, но как дополнительный (не основной) метод распознания.

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

Как Вы правильно заметили для НС абсолютно всеравно что на картинке (символ или отпечаток пальца), как и большинству шрифтозависимых систем. Но для шрифтонезаисимых систем, которые распознают символ на основании длины линий, количества и типов ключевых точек, закрытых областях, углов между линиями, разница между символом и отпечатком пальца просто громадна. И подобная важность типа входных данных не является поводом для различия - это просто результаты работы алгоритмов которые дают такую зависимость. Хотя Omnifont OCR создаются именно для распознания символов и распознания разного рода других изображений для них не имеет никакого значения.

>во всей моей системе «интеллектуальным» можно считать только сравнение семантической структуры символа.
>>Что-то мне несколько непонятно то, что Вы написали.

Я имел в виду что алгоритм скелетизации, который лежит в основе работы моей системы не можно считать особо интеллектуальным. Это просто один из способов алгоритмической обработки изображений. Посмотрите хотябы файл figures. И это еще учитывая, что в файле находятся чистые и ровные изображения. После скелетизации даже человек не всегда способен определить что же было нарисовано на картинке. ИМХО считать такой способ распознания интеллектуальным - глубоко ошибаться.
Должен также заметить, что скелетизация в основном используется для обработки и анализа изображений где основу составляют тонкие и длинные линии. В основном это OCR, картография, медицинские системы и т.д. Для распознания других типов изображений (лица, объекты) скелетизациия абсолютно не подходит.
[Ответ][Цитата]
mserg
Сообщений: 258
На: Распознавание символов
Добавлено: 29 май 07 12:18
Вы не поверите, но я доказал существование алгоритма для построения оптимального алгоритма распознавания символов. Суть его заключается в регулярном переборе алгоритмов. Простой перебор, конечно, работать не будет, а вот перебор с отсечениями – весьма вероятно. Итак,
1. Дано множество обучающих примеров
2. Задается некоторый ограниченный набор разрешенных операций. Например: сложение (сумма), вычитание, умножение, деление, условный оператор. Разрешено образование новых функций, рекурсивный вызов функций, а также выделение памяти для переменных алгоритма.
3. Задается функция качества алгоритма, зависящая от:
a. Качества соответствия обучающим примерам
b. Длины формулы (программы)
c. Объема вычислений
d. Объема выделенной памяти
4. Для функции 3 требуется указать функцию оценки нижней границы при фиксированных b, c, и d.
Алгоритм решения задачи весьма прост. Сначала рассчитывается функция качества для тривиального алгоритма (качество – наихудшее, длина формулы 1, объем вычислений 0, объем выделенной памяти 1). За рекорд (наилучший найденный на данный момент алгоритм) берем тривиальный алгоритм. Далее перебираются возможные алгоритмы регулярным способом в порядке увеличения длины. Каждый полученный алгоритм запускается. По ходу выполнения текущего алгоритма подсчитываются объем вычислений и объем выделенной памяти. Делается оценка качества алгоритма (см. п 4), и если она хуже текущей – от выполнение текущего алгоритма прекращается и данный алгоритм исключается из рассмотрения. Если текущий алгоритм завершился, то найден более удачный алгоритм. Теперь этот алгоритм считается рекордным. Перебор алгоритмов продолжается. По мере расширения поиска искомые программы становятся все длиннее и длиннее, и, в конце концов, при некоторой длине все оценки функции качества алгоритмов (см. п.4 ) становятся хуже рекорда – их рассматривать не имеет смысла.
Таким образом, алгоритм поиска оптимального алгоритма распознавания символов конечен. Разумеется, это справедливо при определенной функции качества – функция должно возрастать при увеличении длины формулы, объема вычислений и объема выделенной памяти, и быть тем меньше, чем результаты алгоритма более точно соответствуют обучающим примерам. Есть еще требования, но не будем здесь морочить голову деталями.
Кто читал внимательно, то увидел, что алгоритм создания алгоритмов универсален. Конечно, чтобы он заработал – тут нужно изрядно попотеть.

Частично данная идея использования функции качества была проверена с помощью генетического программирования в системе Easy NP. Там нет рекурсивных функций и выделения памяти – задача ставилась значительно проще. Просто подбиралась формула под данные. Описание одной из тестовых задач в Easy NP выглядит так:

' Подбор формулы L1*B1*H1-L2*B2*H2+1
Func Volume(L1 As Float, B1 As Float, H1 As Float,
L2 As Float, B2 As Float, H2 As Float) As Float
Operators {"+ 2", "- 2", "* 2", "/ 2", "- 1"}
Func Desc(L1 As Float, B1 As Float, H1 As Float,
L2 As Float, B2 As Float, H2 As Float, D As Float) As Float =
(Volume(L1,B1,H1,L2,B2,H2) - D)^2

Con Opt As
Minimize((
Desc( 3, 4, 7, 2, 5, 3, 54) +
Desc( 7,10, 9,10, 3, 1, 600) +
Desc(10, 9, 4, 8, 1, 6, 312) +
Desc( 3, 9, 5, 1, 6, 4, 111) +
Desc( 4, 3, 2, 7, 6, 1, -18) +
Desc( 3, 3, 1, 9, 5, 4,-171) +
Desc( 5, 9, 9, 1, 7, 6, 363) +
Desc( 1, 2, 9, 3, 9, 2, -36) +
Desc( 2, 6, 8, 2, 6,10, -24) +
Desc( 1,10, 7, 5, 1,45,-155) + 1) * exp(0.1*SizeOf(Volume)))

Задача состоит в том, чтобы найти функцию Func, которая может состоять из операторов сложения, вычитания, умножения, деления и суть умножения на -1 (знак минус). Подбираемая функция зависит от шести параметров L1,B1,H1,L2,B2,H2. Обучение происходит на 10 примерах: даются значения этих 6 параметров и значения функции, которая она должна принимать при данных параметрах. Функция качества (это ограничение Opt) равна суммарной квадратичной невязке (см. функцию Desc), умноженной на возрастающую функцию от длины формулы – это SizeOf(Volume). В принципе работает. Только генетическое программирование, мягко говоря, неэффективно для таких задач. Перебор с отсечениями, конечно, даст результат совершенно другого качества.
[Ответ][Цитата]
Corwin
Сообщений: 1324
На: Распознавание символов
Добавлено: 29 май 07 15:40
Вот немного модифицировал программу из вышеназванной статьи (про НС)
http://filesexchange.narod.ru/SimpleOCRRelease.rar
Добавил на 4 страничку три кнопки с выбором шрифта.
Результаты: обученный шрифт распознается с 100% точностью. Изменение шрифта на другой (даже если они визуально схожи (Verdana, Arial)) снижает качество распознания где-то до 10%.

Да и у меня сложилось впечетление что эта программа (как и статья) - просто реклама библиотеки для НС. Похоже что достаточно эффективно на американцев подействовало (судя по отзывам написанным в http://www.codeproject.com)
[Ответ][Цитата]
Corwin
Сообщений: 1324
На: Распознавание символов
Добавлено: 29 май 07 18:50
2 mserg
Я так понимаю (в спрощеном варианте) Вам просто нужно решить уравнение
L1?B1?H1?L2?B2?H2-1 = D,
где вместо "?" нужно найти правильные мат операторы? И сделать Вы это хотите перебором..?
[Ответ][Цитата]
mserg
Сообщений: 258
На: Распознавание символов
Добавлено: 29 май 07 19:08
Цитата:
Автор: Corwin

2 mserg
Я так понимаю (в спрощеном варианте) Вам просто нужно решить уравнение
L1?B1?H1?L2?B2?H2-1 = D,
где вместо "?" нужно найти правильные мат операторы? И сделать Вы это хотите перебором..?

Не... Формула может быть произвольной. Примеры:
Volume(...) = L1*L1
Volume(...) = (L1*H2+L1/L1)/(H2+B2/L2)
Volume(...) = L1*(B1+L1)+H2*L2
и т.п.

Про перебор с отсечениями я не зря завел разговор. Например, если для формулы
Volume(...) = L1+B1+H1+L2+B2+H2
переставлять аргументы, то получим 6! одних и тех же формул. Еще веселее, если разрешено использование констант. Не подбирать же их перебором!
[Ответ][Цитата]
anatoli
Сообщений: 249
На: Распознавание символов
Добавлено: 30 май 07 11:28
> Это уже более интересно Хочу спросить: Вы где-нибудь встречали системы распознания символов которые работали бы НС? Если да, то что это за продукты и как их можно протестировать.

Та программа, о которой я говорю, и есть система распознавания символов (шрифтонезависимо) на чистой НС. Продукт этот - простой, (вроде бы, не точно) обычный персептрон с улучшенными методами обучения (но ничего нового и сложного, типа bp и т.п.). Я основу нашел в инете лет 5-6 назад, внес кое-какие изменения, улучшающие качество, но принцип остался тем же. А брал я ее просто для того, чтобы ознакомиться с различными реализациями НС, и OCR тут чисто случайно попался под руку. Код из инета был на VB, и писал его, вроде бы, какой-то студент из МГУ или Баумана. Да в принципе, там самому-то ее сделать - пара часов (при свободном владении "родным языком")..


>> Что-то тут не то
> Вполне то. Просто вы ищите смысл в целой картине, тогда как прога ищет только отдельные пиксели которые соответствуют символу.

Нее, это уже не распознавание образа на картинке.. а не поймешь, что.. Присутствие отдельных пикселей на картинке не означает распознание объекта. Если мы ищем "С", а у нас "О", так у нас "С" или "О"? Пиксели-то от "С" присутствуют в полном наборе.. Или полностью черный квадрат - это "С"? Пиксели-то снова присутствуют.. Это как распознаем цифру 3:
- 6 - это 3?
- да!
-
- 6 / 2 = 3!


Остальное отвечу в другой раз
[Ответ][Цитата]
Corwin
Сообщений: 1324
На: Распознавание символов
Добавлено: 30 май 07 15:38
>Та программа, о которой я говорю, и есть система распознавания символов (шрифтонезависимо) на чистой НС.

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

>Если мы ищем "С", а у нас "О", так у нас "С" или "О"?

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

2 mserg

А что Вы ожидаете от такой системы? Получение производной функции? И как это можно выразить для распознавания символов?
[Ответ][Цитата]
anatoli
Сообщений: 249
На: Распознавание символов
Добавлено: 31 май 07 1:00
> Может есть возможность что Вы выложите где нибуть эту программу?

Поищу на диске и в инете.. все же 5 лет прошло..


> Если нарисовано "О" тогда претендент "О" получит бОльшую вероятность..

Правильно, я о том и говорю! Если на картинке черного - 90%, и без изменения пикселей на нее можно наложить силуэты любой из букв алфавита, то как тогда можно определить, что там изображена определенная буква? Это то же самое, что в черном квадрате Малевича различить какие-либо сюжеты кроме самого квадрата. Поэтому я и сказал: там что-то не то..
[Ответ][Цитата]
Corwin
Сообщений: 1324
На: Распознавание символов
Добавлено: 31 май 07 2:36
>Если на картинке черного - 90%, и без изменения пикселей на нее можно наложить силуэты любой из букв алфавита

Правильно. Если программа не обучена что черный квадрат это черный квадрат, тогда она просто увидит там множество символов. В таком случае скорее всего выберется тот символ у которого наибольше пикселей. Так само моя программа в отпечатке пальца увидит весь алфавит, поскольку там много линий и закрытых областей.
А по поводу той НС из статьи. Там все-таки не все изображения покрывается шумом и не равномерно. Кстати у меня программа уже после 20% зашумленности дает неудовлетворительные результаты. А то что при 70% находит правильный символ это уже как повезет при распределении шума.
[Ответ][Цитата]
mserg
Сообщений: 258
На: Распознавание символов
Добавлено: 31 май 07 13:56
Для задачи распознавания символов нужно найти функцию g; на вход функции подается матрица изображения X размером N на M; на выходе – код символа c.

Задаем данные для автоматического построения алгоритма распознавания символов:
1. Множество допустимых операций: сложение, вычитание, умножение, деление, условный оператор. Разрешаем использование создание новых функций, рекурсивный вызов функций, использование памяти для хранения промежуточных вычислений (по сути, это дает все возможности для создания того, что называется алгоритмами).
2. Множество K обучающих данных в виде пар: матрица изображения / код символа
3. Функцию, которая должна достигнуть минимума (приведена для примера, может быть другой):
f(g) = (1+sum(k in K, (g(X(k))-c(k))^2)/|K|)*exp(1/M/N*s(g)/|K|)*exp(1/M/N*p(g)/|K|)* exp(1/M/N*r(g)/|K|)
Здесь
X(k) и c(k) – матрица изображения и код символа для k-го обучающего примера
s(g) – длина функции g (и всех вспомогательных в том числе)
p(g) – объем вычислений, возникающий при использовании функции g
r(g) – объем памяти, требуемый при использовании функции g
Все. Больше ничего не требуется.

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

Мне удалось доказать, что алгоритм минимизации f(g) – конечен. Значит, алгоритмы можно создавать автоматически, достаточно задавать то, что указано в п.1-3.
[Ответ][Цитата]
anatoli
Сообщений: 249
На: Распознавание символов
Добавлено: 01 июн 07 2:19
> В таком случае скорее всего выберется тот символ у которого наибольше пикселей

Вообще, это неправильное поведение. Программа должна анализировать результаты. Если все символы дают что-то около 1-3% вероятности, значит мы "не распознали", а не "распознали с вероятностью 3%".


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

Даже не знаю, что и сказать..


> Кстати у меня программа уже после 20% зашумленности дает неудовлетворительные результаты.

Собвственно, я и сам при 20%+ шума даю неудовлетворительные результаты. Точнее, как раз удовлетворительные: я говорю - тут не изображено символов.


Насчет той проги, что я писал. Я дома глянул, не нашел (возможно, код пропал в один из двух смертей партиций, которые случились с моими данными за последние 5 лет, и после которых восстановить удалось не все). Я еще поищу, но пока давайте я Вам помогу ее с нуля составить? Там все очень просто.
[Ответ][Цитата]
 Стр.2 (8)1  [2]  3  4  5  6  ...  8<< < Пред. | След. > >>