Попробуем создать распознавалку графических образов (цифр) на принципах человеческого восприятия (как я их понимаю), невзирая на скорость работы алгоритма. Т.е. там, где в биологическом распознавателе действует принцип параллельности, в программном распознавателе будем использовать последовательный перебор вариантов.
В программу заложены следующие идеи.
В каждый момент времени распознавания обязательно есть 2 объекта: над-объект и под-объект.
В начальный момент времени над-объект - это прямоугольный битмап (очевидно, что без этого над-объекта никак нельзя, даже когда мы сканируем строки изображения, мы уже должны располагать информацией о ширине, высоте, палитре - т.е. обладать какой-то информацией о над-объекте, значит уже распознать его). Начальный под-объект - это квадратный пиксель, который может быть белого или чёрного цвета.
Важно. В каждый момент распознавания у нас всего один над-объект. Под-объектов в рамках текущего над-объекта у нас всегда больше чем один и они обязательно
не равны по некоторому признаку. В данном случае под-объекты равны по 2-м признакам: размеру (все пиксели - это равные квадратики) и по признаку принадлежности к над-объекту (все пиксели принадлежат битмапу). И не равны тоже по 2-м признакам - цвету и месторасположению.
Этап 1.
В начальный момент времени у нас один над-объект (битмап, "лист бумаги") и много под-объектов (квадратные пиксели). Вся совокупность под-объектов в точности соответствует над-объекту. Т.е. они являются взаимозаменяемыми описаниями друг-друга. Это важно т.к. в восприятии человека нет никаких разрывов-зазоров, рецепторное поле человека в каждой своей точке обязательно заполнено каким-то объектом.
Этап 2.
Мы
объединяем (синтезируем) под-объекты в новый над-объект по некоторому
новому фильтру-признаку, которого не было изначально. Этот новый фильтр может использовать
только неравенство под-объектов по какому-то признаку. Под-объекты (пиксели), как мы уже выяснили, не равны по цвету и координатам. Поэтому я использовал такой фильтр - если вокруг пикселя на единичном расстоянии есть пиксель с таким же цветом, то они тождественны. Т.е. объединяю пиксели по признаку восьмисвязности. В итоге все пиксели объединяются в отдельные "островки".
Поиграться можно
здесь. Числа показывают количество точек в островке. Картинку можно двигать мышкой. Работает только с bmp-файлами.
Кому интересно, в общем виде алгоритм выглядит так:
- сканируем строки и находим связанные блоки из последовательных тёмных пикселей,
- если над блоком, в предыдущей строке сверху, нет ни одного объекта -
создаём новый объект и запоминаем верхнюю координату Y этого объекта,
- если над блоком есть один или несколько объектов то сливаем их все в один объект, именуя их по самому верхнему объекту.
Теперь смотрим, что у нас получилось. Введя новый фильтр (равенство цветов + расстояние) мы создали новый слой абстракции. Теперь над-объект - это битмап. И он состоит из новых под-объектов "островков", которые в свою очередь являются над-объектами для под-объектов - пикселей. Изначально у нас было 2 слоя (битмап, пиксели), теперь стало 3 слоя (битмап, островки, пиксели).
Следующие шаги распознавания можно рекурсивно разделить между этими слоями и строить над-объекты из островков в рамках битмапа, и над-объекты из пикселей в рамках островков. Отметим, что как и на первом этапе каждый над-объект по прежнему целиком и полностью описывается под-объектами, без "зазоров". Но островки (как под-объекты битмапа) теперь равны по двум другим признакам - цвет и принадлежность над-объекту. Размеры и формы у островков разные и это дополнительные признаки, по которым мы теперь можем изобрести для них какие-то другие
новые фильтры-признаки.
У пикселей теперь тоже появился новый признак - принадлежность к островку.
Мы пока не будем усложнять до предела и запускать на рекурсию всё это дело. Попробуем разобраться с механикой построения новых признаков-фильтров в рамках одного "островка".
Введём новый фильтр-признак и выделим (объединим, синтезируем) последующие под-объекты в рамках островков.
Этап 3.
Как мы уже выяснили, чтобы создать новый фильтр-признак нам нужны только те признаки, по которым под-объекты (в данном случае - пиксели) могут быть нетождественны в данном над-объекте. Пиксели в рамках одного островка (над-объекта) тождественны по размеру и цвету. Они не тождественны по координатам и по цвету соседей (есть крайние пиксели и внутренние пиксели). Значит нам нужен новый фильтр-признак, разделяющий их по координатам и/или по признаку соседства. Самый простой фильтр - соединить рядом-стоящие пиксели если они равны между собой по тому признаку, что их цвет не равен цвету соседних пикселей. Т.е. выделить крайние точки.
После этого в рамках каждого "островка" у нас появляется от одного до N дополнительных под-объектов в зависимости от графического образа. Например у образа "1" появится один дополнительный под-объект, а у "8" - 3 дополнительных под-объекта. Но в таком случае остальная масса точек "островка" остаётся незадействованной. После многих экспериментов я пришёл к выводу, что эти внутренние точки малоинформативны и дают сведения только о "массе" или "жирности" образа. Наиболее информативным под-объектом для быстрого различения формы оказался внешний контур.
Этап 4.
В рамках объекта "внешний контур" мы очень ограничены в фильтрах и по сути можем отличать одни пиксели контура от других только углом поворота и длиной похожих участков. Я сделал простой фильтр, отличающий правые повороты от левых поворотов и фиксирующий их длину. Распознавалку рукописных цифр на этом принципе можно скачать
здесь. Она неплохо опознаёт цифры 0, 3, 8 и 9, остальные кое-как. Цифры можно рисовать мышкой или загружать из файла. Рисовать - левой кнопкой, двигать битмап - правой.
Для улучшения качества опознавания нам нужно плодить всё новые и новые фильтры, которые позволят соотносить каждый пиксель со всё большим и большим количеством разных под-объектов и совершенно понятно, что для любого, привычного нашему глазу, образа набор этих под-объектов-признаков-фильтров вполне характерен и определён. Для того чтобы распознавалка работала в человеческом стиле она должна сравнивать просто две кучи под-объектов - "правильную" кучу (эталон) и кучу "того, что есть". По количеству одинаковых под-объектов в кучах можно будет судить о том, похожи ли объекты в целом. А по неодинаковым под-объектам - чем они отличаются.
Выводы.1. Для распознавания всегда нужно минимум 2 объекта - над-объект и под-объект.
2. Человеческое распознавание глубоко рекурсивно и использует признаки с разных уровней рекурсии (абстракции) для хорошего распознавания.
3. Новые признаки-фильтры можно создавать только из тех признаков, по которым под-объекты не тождественны в рамках над-объекта.
4. Под-объекты самого нижнего уровня ("пиксели") содержат в себе всю информацию (помнят) о том, к каким над-объектам они относятся.
Отличие этой распознавалки от человеческой в том, что все новые дополнительные признаки я подбирал эвристически и жёстко задавал программно. Программа не может их модифицировать. Полноценный же ИИ должен новые признаки-фильтры генерировать сам, по какому-то единому универсальному принципу.