Формализация алгоритма сравнения образов в рамках Теории разумных систем.

Данный доклад я представил на

Международной научно-практической конференции-конкурса научных докладов студентов, аспирантов и молодых исследователей.

Формализация алгоритма сравнения образов в рамках Теории разумных систем.

Безобразов М.В.

Теоретическая часть.

В данном докладе приводится оригинальный алгоритм сравнения образов и пример его тестирования на графических образах. Этот алгоритм является частью “Теории разумных систем”, над которой я работаю. Целью является создание подробного описания алгоритма функционирования любой разумной системы.

1. 1. Классическое и оригинальное понятие образа.

Чаще всего под образом понимают класс, т.е. группу конкретных образов, объединенных некоторыми общими признаками. Например, в класс “Животные” входит подкласс “собака” и т.п. При этом задача сравнения образов сводится к отнесению сравниваемого образца к некоторой группе, к классу образов.

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

1. 2. Определение образа:

Образ – это подмножество некоего изначального множества.

Поясню на примере: Существуют различные Органы Чувств (ОЧ), периферия центральной нервной системы, через которую в разум попадают образы. Каждый ОЧ – это некоторое множество элементов. Например, орган зрения человека – это множество около 180 млн. клеток – нейронов сетчатки. Когда мы видим некий конкретный образ – активируется часть нейронов из этого множества. Т.е. любой образ – это подмножество некоего изначального множества. Причем каждый элемент множества имеет двоичную природу – либо активен, либо нет (0 или 1)

1. 3. Определение близости элементов образа.

Фактически каждый элемент множества Органа Чувств является отдельным образом. Предлагается, что мера сравнения двух образов основана на совокупной мере похожести (близости) активных элементов этих образов.

Мера похожести элементов носит ассоциативный характер, т.е. более похожи элементы, которые чаще активировались вместе:

Б (Эт;Эл) = КОтл / Кот

Б (Эт;Эл) – близость элемента Эт и Эл.

КОтл - кол-во образов из памяти П, в которых присутствовали оба элемента Эт и Эл.

КОт - количество образов, в которых присутствовал элемент Эт.

Пример. Множество органа чувств состоит из 3 элементов. В памяти разума содержится 4 образа, каждый образ можно сравнить с картинкой в 3 пикселя:

1

0

1

Образ 1

0

1

1

Образ 2

1

0

1

Образ 3

1

1

1

Образ 4

Рассчитаем близость первого и третьего элемента Б(1,3). Всего в памяти 1 элемент активизировался 3 раза. Одновременно 1 и 3 элемент активизировались 3 раза.

Б(1,3) = 3/3 = 1.

Аналогичным образом получим все близости элементов. Матрица близости элементов:

1. 4. Определение коэффицента сравнения образов.

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

Формула сравнения образов:

С (От, Ол) = ∑а от 1 до Ат (∑ г от 1 до Ал (Б (а, г))) / Ат * Ал,

С – мера сравнения и близости двух образов.

От – образ Т.

Ол – образ Л.

где Ат и Ал – соответственно количество активных элементов в образах От и Ол.

Б (а, г) – близость элементов а и г.

Комментарии к формуле: попарно суммируются все близости активных элементов образов. Если, например, в каждом образе по 10 активных элементов, то будет суммировано 100 близостей. Потом эта сумма делится на количество близостей, которые в нее входят, т.е. на 100. Таким образом, коэффициент сравнения двух разных образов – это средняя близость активных элементов данных образов.

Рассчитаем коэффициент сравнения 1 и 2 образа.

С (О1, О2) = (Б(1,2) + Б(1,3) + Б(3,2) + Б(3,3) ) / 2*2 = (0,333 +1 + 0,5 + 1) / 4 = 0,70825

Рассчитав коэффициенты сравнения сравниваемого образа со всеми образами из памяти – найдем самый похожий на него образ. Т.е. решим задачу сравнения образов.

Некоторые свойства операции сравнения образов:

1. Операция вычисления похожести элементов образов не является коммутативной функцией, т.е. Б (Эт;Эл) ≠ Б (Эл;Эт). Tакже не является коммутативной Операция вычисления похожести самих образов - С (От, Ол).

1. Результаты вычисления близости элементов образов и, соответственно, похожести самих образов, полностью зависят от опыта субъекта. Т.е. нет никакой априорной, изначальной метрики.

1. При работе с “графическими образами” важную роль играет выбор метода бинаризации изображений. Т.е. в целом, метод репрезентации информации в разуме играет важную роль.

1. Качество распознавания (точности сравнения) зависит от количества образов в памяти и от сложности образов (размерности Множества элементов образа).

Практическая часть.

Для тестирования своего алгоритма я сделал программу Сравнение Образов в среде Delphi (соавтор Поведайко Александр). Данная программа воспринимает образы в виде текстовых файлов со значениями (0 либо 1) через запятую. Все файлы образов из выбранной папки загружаются в массив в программе. Выбирается сравниваемый образ.

Существует процедура расчета матрицы близости элементов образа.

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

Тестирование алгоритма я начал с графических образов. Для бинаризации изображений я использовал программу Pictures написанную на C# (автор Гламаздин Юрий Викторович). Входными данными являются фалы jpeg, выходными фалами являются txt файлы, в которых через запятую находятся 1 и 0, т.е. в формате, необходимом для программы сравнения образов.

Была выбрана база данных полутоновых изображений 20 предметов COIL-20, подготовленная в Колумбийском университете. Адрес базы: http://www1.cs.columbia.edu/CAVE/software/softlib/coil-20.php

База содержит изображения 20 предметов. Каждый предмет представлен серией из 72 изображений, сделанных при разных положениях камеры относительно предмета. Изображения в базе полутоновые, с 256 градациями яркости. Формат изображений — PNG. Размеры изображения — 128x128 пикселей.

Тест 1.

Все изображения базы изображений (1440 шт.) бинаризируются в программе Pictures со следующими параметрами: Разрешение 50 * 50, количество единичек в выходном файле – 1250.

Случайным образом выбираются 20 изображений, по одному изображению каждого предмета. Это будут тестовые образцы. Остальные 1420 загружаются в программу Сравнение Образов в качестве обучающей базы. После этого вычисляем для каждого изображения из тестовых – 5 самых похожих изображений базы данных.

Приведу результат для первых 7 – ми тестовых образов:

1. Для тестового изображения obj1__61:

Вычислено самое похожее изображение obj14__54:

1. Для тестового изображения obj2__28:

Вычислено самое похожее изображение obj14__55:

1. Для тестового изображения obj3__50:

Вычислено самое похожее изображение obj3__49:

1. Для тестового изображения obj4__70:

Вычислено самое похожее изображение obj2__17:

1. Для тестового изображения obj5__50:

Вычислено самое похожее изображение obj12__43:

1. Для тестового изображения obj6__27:

Вычислено самое похожее изображение obj6__1:

1. Для тестового изображения obj7__54:

Вычислено самое похожее изображение obj7__55:

В результате расчета самых похожих образов на 20 тестовых образов 7 раз алгоритм угадал принадлежность образа, т.е. средний % успешных сравнений составил 35%.

При этом вероятность случайного угадывания 1 из 20 образов составляет 1/20 = 5%, т.е. в 7 раз меньше.

Тест 2.

С следующем тесте я взял уже не по 72 а по 3 примера каждого образа. Т.е. в тестовом наборе образов было 20 изображений, а в обучающей базе – 2*20 =40 изображений.

При этом разрешение картинок при бинаризации было увеличено до 70*70 пикселей.

В данном случае результат успешного сравнения составил 75 %.

Тест 3.

Было выбрано разрешение картинок, как в Тесте 2 (70*70), только уже использованы все 72 картинки для каждого образа. В обучающей базе – 71*20=1420 образов.

Результат успешного сравнения составил 35 %.

Тест 4.

Была выбрана аналогичная база данных полутоновых изображений 100 предметов COIL-100, подготовленная в Колумбийском университете. Адрес базы: http://www1.cs.columbia.edu/CAVE/software/softlib/coil-100.php

Были выбраны первые 50 предметов, по 5 изображений каждого предмета. После бинаризации всех изображений программой Pictures (разрешение 45*45), были удалены все плохо бинаризированные (нераспознаваемые изображения). В итоге осталось 38 предметов в базе; соответственно в тестовом наборе 38 изображений; в обучающей базе = 38*4 =152 изображения.

Результат успешного сравнения составил 55%.

Выводы.

Результаты тестирования данного алгоритмы сравнения образов не являются однозначными. При этом очевидно, что они есть.

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

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

Данный алгоритм сравнения является “абсолютно пустым”, т.е. не содержит никаких эвристик, преднастроек, никакой информации об образах, которых ему придется сравнивать. Т.е. он может без предварительных настроек работать абсолютно с любой базой образов. Поэтому данные результаты (55% распознавания) являются успешными.

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