1. Если вы только начинаете программировать на ассемблере и не знаете с чего начать, тогда попробуйте среду разработки ASM Visual IDE
    (c) на правах рекламы
    Скрыть объявление

Распознавание цифр.

Тема в разделе "WASM.A&O", создана пользователем Clerk, 14 ноя 2010.

  1. Clerk

    Clerk Забанен

    Публикаций:
    0
    Регистрация:
    4 янв 2008
    Сообщения:
    6.689
    Адрес:
    РБ, Могилёв
    Здрасте.
    Интересует реально рабочий алгорит позволяющий распознать цифры, например:
    [​IMG]
    Вижу два способа:
    o Описание контуров.
    o Описание частей занимающих наибольшую площадь.

    Всякие нейросети, использование матриц и прочая бесполезная ерунда не интересует.
     
  2. PSR1257

    PSR1257 New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2008
    Сообщения:
    939
    О, давно обдумываю эту задачу. Есть идейки. Могу изложить. Кода не писал. Могу совместо пейсать на асм или си.

    ps Задача старая, возможно уже есть фришный код.
     
  3. Clerk

    Clerk Забанен

    Публикаций:
    0
    Регистрация:
    4 янв 2008
    Сообщения:
    6.689
    Адрес:
    РБ, Могилёв
    PSR1257
    Изложите плз ваши идеи.
     
  4. Mentor

    Mentor New Member

    Публикаций:
    0
    Регистрация:
    13 окт 2010
    Сообщения:
    67
    Цифры любые? i.e. любым шрифтом, любого цвета? Фон всегда белый/однотонный?
     
  5. Clerk

    Clerk Забанен

    Публикаций:
    0
    Регистрация:
    4 янв 2008
    Сообщения:
    6.689
    Адрес:
    РБ, Могилёв
    Mentor
    Помехи на фоне это другая задача, будем считать что фон однотипный, пусть белый. Цифры любым шрифтом, под любым углом, например написанные от руки.
     
  6. Mentor

    Mentor New Member

    Публикаций:
    0
    Регистрация:
    13 окт 2010
    Сообщения:
    67
    Задача в общем виде нерешаема. Есть достаточно эффективные решения для частных случаев
     
  7. Mentor

    Mentor New Member

    Публикаций:
    0
    Регистрация:
    13 окт 2010
    Сообщения:
    67
    Вообще, вру насчет неразрешимости в общем случае.
    Очень даже разрешима через, например, antigate.com
     
  8. Clerk

    Clerk Забанен

    Публикаций:
    0
    Регистрация:
    4 янв 2008
    Сообщения:
    6.689
    Адрес:
    РБ, Могилёв
    Mentor
    Не нашёл на том сайте описание алгоритма.
     
  9. Pavia

    Pavia Well-Known Member

    Публикаций:
    0
    Регистрация:
    17 июн 2003
    Сообщения:
    2.398
    Адрес:
    Fryazino
    Clerk
    Экспериментировал, удавалось разбивать все числа на 3 группы 5,6,8,9 почти не отличались 1 похожа на 7.

    По этому принципу и работает классические нейронные сети поэтому и результат распознавания 50%.
    В PM скинул ссылку которая дает 99% распознавание.
    Mentor
    Задача в общем случае решена.
     
  10. Mentor

    Mentor New Member

    Публикаций:
    0
    Регистрация:
    13 окт 2010
    Сообщения:
    67
    Clerk
    Его там и нет, там люди распознают по цене $1 за 1000 картинок.

    Ситуация следующая. В общем случае задача распознавания _произвольных_ образов не решаема. Я могу написать цифру так, что ее человек не распознает. Возьмите, например, рецепт любого врача. Если ограничить задачу набором шрифтов и каким-то набором функций, применяемых к символам (вращение, скручивание, сжатие-растяжения, перспектива), то можно распознавать с достаточно высоким выходом.

    Вас интересуют частные решения?
     
  11. Mentor

    Mentor New Member

    Публикаций:
    0
    Регистрация:
    13 окт 2010
    Сообщения:
    67
    Pavia
    Разберете любую рукописную цифру? ню-ню
     
  12. Tronix

    Tronix Member

    Публикаций:
    0
    Регистрация:
    10 сен 2010
    Сообщения:
    122
    Сложная задача. Если не мудрить с нейросетями и прочим адским матаном, то на сколько мне известно существуют такие способы:
    1) Весьма оригинальный способ, с помощью анализа топологии http://habrahabr.ru/blogs/algorithm/101446/ Задумка интересная, но пойдет разве что для четко-написанных букв. Тем не менее, имеет право на жизнь.
    2) Классическое сравнение с образами. Создается огромный файл, содержащий в себе всевозможные варианты начертания цифр. Для каждой цифры - сотни видов ее начертаний. Примерно так (тут в разнобой, но чтобы было понятно):
    [​IMG]
    Затем происходит сравнивание и на основе расстояния Хемминга (или как то так) выносится решение. Формула что-то типа x = 10000/y*y+1, где y - количество совпавших символов.
    Кстати, где-то такой файлик с образами цифр можно готовый качнуть в инете. Занимает что-то около 50Mb. Если вспомню где видел, напишу.
    Минусы - тормоза, нужно большое количество памяти для таскания с собой базы изображений.
     
  13. PSR1257

    PSR1257 New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2008
    Сообщения:
    939
    Как я полагаю, решения могут быть двух типов: брутфорс (перебор вариантов цифр пока не совпало) и обратно: попытка восстановить цифру по изображению. Возможно симбиотичные решения.

    Остановлюсь пока на первом варианте. Полагаем что функция генерации искаженной цифры f(D)-D' (D' - Digit') имеет возможности:

    1) Увеличивать или растягивать изображение в двух направлениях с коэффициентами K1 и K2 (в общем случае K1!=K2);
    2) Поворачивать картинку на угол Alpha;
    3) Перемещать картинку по двум направлениям: dX,dY;
    4) Выбирать начальное изображение из конечного массива шрифтов (Fonts[N]), N полагаю невелико, ~10-100;
    5) Какие-то еще искажения (?) - DistortionUnknown().

    Предполагаем что мы обладаем всеми Fonts[], если будет найден новый - мы добавим его в алгоритм. Теперь мы выполняем брутфорс по всем параметрам - возможно под вопросом DistortionUnknown, но если мы узнаем ее то мы тоже добавляем в брутфорс.

    Брутфорсу нужен критерий и я предлагаю использовать упрощенный Хи-квадрат - сумма разностей квадратов между значением цвета картинки и пробной картинки. Упрощенный потому, что веса всех точек одинаковы. Если картинка черно-белая то сумма квадратов вообще вырождается в сумму модулей а точнее просто сумму 1 или 0 - цвет не совпал или совпал.

    В общем случае брутфорс возможно довольно емкий по вычислениям, так как нужно перебирать по параметрам 1-4. Однако тут можно более хитро:

    3) Перемещение. Предполагаем что мы имеем поле точек {X,Y} в общем случае достаточно большое. Мы быстро находим описывающий квадрат далее работаем только внутри него (нет точек за его пределами). Возможно лучше прямоугольник (Xr,Yr - длины сторон) или может более сложное;
    3.1) Вычисляем центр масс точек (Xc,Yc). Предполагаем что поиск смещений dX,dY можно сильно ограничить, например Xc+-Xr/10 (требуется уточнение);
    2) Поворот. Полагаю (нужно проверить) что если мы имеем абсолютно совмещенные пробную и истинную картинки за исключением того, что пробная повернута относительно истенной на Alpha, то функция критерия (выше) от Alpha будет иметь один максимум и она будет довольно гладкая (равномерно нарастать и спадать при прохождении максимума), таким образом делением отрезка пополам довольно быстро можно определить Alpha.

    Подобное и с другими.

    Также возможно искать примитивы на которые, полагаю, можно разбить любую цифру (пусть приближенно) - это отрезки (линии kx+b) и дуги (может быть эллипсы?). Таким образом мы начинаем анализ с поиска линий и дуг, под линией наверное точнее понимать прямоугольник. Если мы по критерию (выше) нашли (или не нашли как для восьмерки) один или более прямоугольников - мы делаем выводы.
     
  14. PSR1257

    PSR1257 New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2008
    Сообщения:
    939
    И еще идейки:

    3) Замкнутные области. Цифры 6,8 и 9 имеют замкнутые области (см функцию floodfill). Если найдена - перебор только среди них.

    4) Интегральный критерий. Находим центр масс и описывающий прямогульник (Xr,Yr) с центром в центре масс. Далее берем прямогульник с тем же центром но растянутый на Kr (уточннение!). Далее считаем отношение числа черных точек ко всем точкам внутри прямоугольника. Полагаю это может коррелировать и из заданного набора 0-9 картинок (один шрифт) все они имеют достаточно разрешенные значения.
     
  15. Clerk

    Clerk Забанен

    Публикаций:
    0
    Регистрация:
    4 янв 2008
    Сообщения:
    6.689
    Адрес:
    РБ, Могилёв
    Pavia
    На сколько я понял там описан всё тотже брутфорс, но в сложной матобёртке, более того без примеров, так что под сомнением что оно вобще работает. На картинках сдвиг изображения в произвольную сторону, это чтение строк в выбранном направлении. Так как между пикселями могут быть разрывы, то вероятно используется множество таких направлений.
    Tronix
    PSR1257
    1. Не эффективно.
    2. Не универсально.
     
  16. PSR1257

    PSR1257 New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2008
    Сообщения:
    939
    Clerk

    Посмотрите еще мой последний пост, может быть лучше?
     
  17. PSR1257

    PSR1257 New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2008
    Сообщения:
    939
    ++ Да, могу продолжить про интегральные критерии. Возможно считать также первый, второй момент, третий ... (сумма первых, квадратов, кубов, ... до центра масс) - если каждая цифирь обладает уникальным моментом, то это может прокатить. Например восьмерка имеет (все?) моменты ноль (она симметрична).
     
  18. Clerk

    Clerk Забанен

    Публикаций:
    0
    Регистрация:
    4 янв 2008
    Сообщения:
    6.689
    Адрес:
    РБ, Могилёв
    PSR1257
    Спасибо, вы много написали и мне нужно время чтоб обдумать.
     
  19. vptrlx

    vptrlx New Member

    Публикаций:
    0
    Регистрация:
    2 сен 2009
    Сообщения:
    15
    если без помех, то несложный, но достаточно эффективный способ - метод потенциальных функций:
    http://citforum.univ.kiev.ua/programming/delphi/recognition_2/
     
  20. AlexCab

    AlexCab New Member

    Публикаций:
    0
    Регистрация:
    8 сен 2008
    Сообщения:
    142
    Мои 5к

    PS: ИМХО стои всётаки копнуть в сторону нейросетей(в "естественной" реализации это работает вполне приемлемо).