Здрасте. Интересует реально рабочий алгорит позволяющий распознать цифры, например: Вижу два способа: o Описание контуров. o Описание частей занимающих наибольшую площадь. Всякие нейросети, использование матриц и прочая бесполезная ерунда не интересует.
О, давно обдумываю эту задачу. Есть идейки. Могу изложить. Кода не писал. Могу совместо пейсать на асм или си. ps Задача старая, возможно уже есть фришный код.
Mentor Помехи на фоне это другая задача, будем считать что фон однотипный, пусть белый. Цифры любым шрифтом, под любым углом, например написанные от руки.
Clerk Экспериментировал, удавалось разбивать все числа на 3 группы 5,6,8,9 почти не отличались 1 похожа на 7. По этому принципу и работает классические нейронные сети поэтому и результат распознавания 50%. В PM скинул ссылку которая дает 99% распознавание. Mentor Задача в общем случае решена.
Clerk Его там и нет, там люди распознают по цене $1 за 1000 картинок. Ситуация следующая. В общем случае задача распознавания _произвольных_ образов не решаема. Я могу написать цифру так, что ее человек не распознает. Возьмите, например, рецепт любого врача. Если ограничить задачу набором шрифтов и каким-то набором функций, применяемых к символам (вращение, скручивание, сжатие-растяжения, перспектива), то можно распознавать с достаточно высоким выходом. Вас интересуют частные решения?
Сложная задача. Если не мудрить с нейросетями и прочим адским матаном, то на сколько мне известно существуют такие способы: 1) Весьма оригинальный способ, с помощью анализа топологии http://habrahabr.ru/blogs/algorithm/101446/ Задумка интересная, но пойдет разве что для четко-написанных букв. Тем не менее, имеет право на жизнь. 2) Классическое сравнение с образами. Создается огромный файл, содержащий в себе всевозможные варианты начертания цифр. Для каждой цифры - сотни видов ее начертаний. Примерно так (тут в разнобой, но чтобы было понятно): Затем происходит сравнивание и на основе расстояния Хемминга (или как то так) выносится решение. Формула что-то типа x = 10000/y*y+1, где y - количество совпавших символов. Кстати, где-то такой файлик с образами цифр можно готовый качнуть в инете. Занимает что-то около 50Mb. Если вспомню где видел, напишу. Минусы - тормоза, нужно большое количество памяти для таскания с собой базы изображений.
Как я полагаю, решения могут быть двух типов: брутфорс (перебор вариантов цифр пока не совпало) и обратно: попытка восстановить цифру по изображению. Возможно симбиотичные решения. Остановлюсь пока на первом варианте. Полагаем что функция генерации искаженной цифры 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) и дуги (может быть эллипсы?). Таким образом мы начинаем анализ с поиска линий и дуг, под линией наверное точнее понимать прямоугольник. Если мы по критерию (выше) нашли (или не нашли как для восьмерки) один или более прямоугольников - мы делаем выводы.
И еще идейки: 3) Замкнутные области. Цифры 6,8 и 9 имеют замкнутые области (см функцию floodfill). Если найдена - перебор только среди них. 4) Интегральный критерий. Находим центр масс и описывающий прямогульник (Xr,Yr) с центром в центре масс. Далее берем прямогульник с тем же центром но растянутый на Kr (уточннение!). Далее считаем отношение числа черных точек ко всем точкам внутри прямоугольника. Полагаю это может коррелировать и из заданного набора 0-9 картинок (один шрифт) все они имеют достаточно разрешенные значения.
Pavia На сколько я понял там описан всё тотже брутфорс, но в сложной матобёртке, более того без примеров, так что под сомнением что оно вобще работает. На картинках сдвиг изображения в произвольную сторону, это чтение строк в выбранном направлении. Так как между пикселями могут быть разрывы, то вероятно используется множество таких направлений. Tronix PSR1257 1. Не эффективно. 2. Не универсально.
++ Да, могу продолжить про интегральные критерии. Возможно считать также первый, второй момент, третий ... (сумма первых, квадратов, кубов, ... до центра масс) - если каждая цифирь обладает уникальным моментом, то это может прокатить. Например восьмерка имеет (все?) моменты ноль (она симметрична).
если без помех, то несложный, но достаточно эффективный способ - метод потенциальных функций: http://citforum.univ.kiev.ua/programming/delphi/recognition_2/
Мои 5к PS: ИМХО стои всётаки копнуть в сторону нейросетей(в "естественной" реализации это работает вполне приемлемо).
