Зинченко А.Е., асс. Козаченко А.А.

Национальный горный университет, Украина

Обзор основных методов распознавания образов в компьютерных системах

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

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

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

Для неоднородно окрашенных (полихромных) камней качественным показателем является рисунок, обусловленный сочетанием участков различного цвета (пятен, полос). Рисунок это характерный декоративный и диагностический признак камня.

Ювелирно-поделочные и поделочные камни представляют собой моно- или полиминеральные образования, отличающиеся большим разнообразием текстур и структур. Понятие текстура отражает совокупность форм, размеров и характер расположения минеральных агрегатов. Для ювелирно-поделочных и поделочных камней макротекстура – это, прежде всего рисунок. Некоторым видам камней в равной степени свойственны две, три текстуры, а иногда и более. Для систематики разнообразных по окраске и рисунку ювелирно-поделочных и поделочных камней наиболее удобен текстурный принцип.

При определении характера рисунка текстуры используются методы распознания образов. Рассмотрим методы распознания образов для определение наиболее оптимальных при решении данной задачи.

Методы функций близости

Методы данной группы основаны на использовании функций, оценивающих меру близости между распознаваемым образом с вектором x^*=(x^*₁,….,x^*_n), и эталонными образами различных классов, представленными векторами xⁱ=(xⁱ₁,…,xⁱ_n), i=1,…,N, где i – номер класса образов.

Процедура распознавания согласно данному методу состоит в вычислении расстояния между точкой распознаваемого образа и каждой из точек, представляющих эталонный образ, т.е. в вычислении всех значений d_i , i=1,…,N . Образ относится к классу, для которого значение d_i имеет наименьшее значение среди всех i=1,…,N .

Функция, ставящая в соответствие каждой паре векторов xⁱ, x^* вещественное число как меру их близости, т.е. определяющая расстояние между ними может быть достаточно произвольной. В математике такую функцию называют метрикой пространства. Она должна удовлетворять следующим аксиомам:

r(x,y)= r(y,x);

r(x,y) > 0, если x не равен y и r(x,y)=0 если x=y;

r(x,y) <= r(x,z)+ r(z,y)

Часто в качестве функции близости выбирают среднеквадратическую разность координат распознаваемого образа и эталона.

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

Указанные деформации пространства признаков преследуют цель такого размещения точек эталонных образов, которое соответствует наиболее надёжному распознаванию в условиях значительного разброса образов каждого класса в окрестности точки эталонного образа.

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

Методы дискриминантных функций

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

Общий вид линейной решающей функции задается формулой

d(x)=w₁ x₁ + w₂ x₂ +…+ w_n x_n + w_n+1 = Wx+w_n

где x – вектор образа, w=( w₁, w₂,…w_n) – вектор весовых коэффициентов.

Разновидностью метода дискриминантных функций является метод решающих функций. В нем при наличии m классов предполагается существование m функций d_i(x), называемых решающими, таких, что если x принадлежит X_i, то d_i(x) > d_j(x) для всех j не равных i,т.е. решающая функция d_i(x) имеет максимальное значение среди всех функций d_j(x), j=1,…,n.

Достоинством метода дискриминантных функций является простая структура распознающей машины, а также возможность её реализации преимущественно посредством линейных решающих блоков.

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

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

Лингвистические (стуктурные) методы

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

Для различных классов объектов выделяются не производные (атомарные) элементы (подобразы, признаки) и возможные отношения между ними. Грамматикой называют правила построения объектов из этих не производных элементов. Таким образом, каждый объект представляется совокупностью не производных элементов, “соединённых” между собой теми или иными способами или, другими словами, “предложением” некоторого “языка”. Путём синтаксического анализа (грамматического разбора) “предложения” устанавливается его синтаксическая “правильность” или, что эквивалентно, - может ли некоторая фиксированная грамматика (описывающая класс) породить имеющееся описание объекта. Грамматический разбор производится так называемым “синтаксическим анализатором”, который представляет полное синтаксическое описание объекта в виде дерева грамматического разбора, если объект является синтаксически правильным (принадлежит классу, описываемому данной грамматикой). В противном случае, объект либо отклоняется, либо подвергается анализу с помощью других грамматик, описывающих другие классы объектов. Известны бесконтекстные, автоматные и другие типы грамматик.

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

Метод группового учёта аргументов (МГУА)

Заимствование алгоритмов переработки информации у природы является одной из основных идей кибернетики. "Гипотеза селекции" утверждает, что алгоритм массовой селекции растений или животных является оптимальным алгоритмом переработки информации в сложных задачах. При массовой селекции высевается некоторое количество семян. В результате опыления образуются сложные наследственные комбинации. Селекционеры выбирают некоторую часть растений, у которых интересующее их свойство выражено больше всего (эвристический критерий). Семена этих растений собирают и снова высевают для образования новых, ещё более сложных комбинаций. Через несколько поколений селекция останавливается и её результат является оптимальным. Если чрезмерно продолжать селекцию, то наступит <инцухт> - вырождение растений. Существует оптимальное число поколений и оптимальное количество семян, отбираемых в каждом из них.

Алгоритмы МГУА воспроизводят схему массовой селекции. В них есть генераторы усложняющихся из ряда в ряд комбинаций и пороговые самоотборы лучших из них. Так называемое <полное> описание объекта.

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

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

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

Сложность модели увеличивается от ряда к ряду селекции как по числу учитываемых аргументов, так и по степени. Степень полного описания быстро растет. На первом ряду - квадратичные описания, на втором - четвертой степени, на третьем - восьмой и т. д. В связи с этим минимум критерия селекции находится быстро, но не совсем точно. Кроме того, имеется опасность потери существенного аргумента, особенно на первых рядах селекции. Для реализации этого метода требуется большие вычислительные мощности.

Нейросетевые методы

Нейросетевые методы - это методы, базирующиеся на применении различных типов нейронных сетей (НС). Основные направления применения различных НС для распознавания образов и изображений: применение для извлечение ключевых характеристик или признаков заданных образов, классификация самих образов или уже извлечённых из них характеристик (в первом случае извлечение ключевых характеристик происходит неявно внутри сети), решение оптимизационных задач.

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

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

Нейросетевые методы обеспечивают быстрое и надёжное распознавание изображений. Однако при применении этих методов к изображениям трёхмерных объектов возникают трудности, связанные с пространственными поворотами и изменением условий освещённости. Изображения для различных углов поворота объекта существенно различаются, часть информации на изображении теряется, возникает новая, специфическая для данного угла. Такие ограничение обычно преодолеваются путём предъявления всевозможных вариаций изображения (различные повороты и освещённость) при обучении, но построение такого обучающего набора – трудная задача, и чаще всего такие наборы недоступны.

Заключение

Дан обзор основных методов распознавания образов. Рассмотрены достоинства и недостатки этих методов. Исходя из посылки что текстуры камней являются вариативними и сложно формализуются наиболее пригодным являются нейросетевые методы.

Литература

1. Горелик А.Л.,Скрипкин В.А. Методы распознавания. Учебное пособ. для вузов. М.: ВШ. 1989.-231с.

2. Кузин Л.Т. Основы кибернетики. Т.2. Учебное пособ. М.: Энергия. 1979.-584с.

3. Ту Дж., Гонсалес Р. Принципы распознавания образов. Изд. Мир, М.,1978.-411с.

4. Фор А. Восприятие и распознавание образов. С фр. М.: Машиностроение. 1989.-272с.

5. Головко В.А. Нейроинтеллект: Теория и применения. Книга 1. Организация и обучение нейронных сетей с прямыми и обратными связями – Брест:БПИ, 1999, - 260с.

6. Головко В.А. Нейроинтеллект: Теория и применения. Книга 2. Самоорганизация, отказоустойчивость и применение нейронных сетей – Брест:БПИ, 1999, - 228с.