Книги по разным темам Pages:     | 1 | 2 | Электронный научный журнал ИССЛЕДОВАНО В РОССИИ 1501 Выбор оптимальных условий аналитического описания контурных объектов в задачах анализа изображений и распознавания образов Куликова Л. И. (Kulikova@impb.psn.ru), Махортых С. А.

Институт математических проблем биологии РАН Введение На настоящий день накоплен огромный опыт решения задач анализа изображений и распознавания образов [1Ц6]. В последнее время помимо общих подходов предлагается довольно широкий спектр новых технологий для решения такого рода задач [7Ц11], применяется большое количество различных специализированных методов, алгоритмов анализа сигналов и распознавания образов, что говорит о большом интересе исследователей к этому классу задач и актуальности проблемы распознавания в совершенствовании информационных технологий. Данная работа основана на использовании обобщенного спектрально-аналитического метода, который предполагает проведение полной обработки данных в пространстве коэффициентов Фурье, вычисляемых при разложении их в ортогональные ряды с использованием модифицированных классических ортонормированных полиномов и функций [12Ц14]. Работая в пространстве коэффициентов разложения и учитывая, что это пространство при правильном выборе системы координат и соответствующего ортогонального базиса отражает все существенные для анализа характеристики изучаемого объекта, задача сводится к выявлению и использованию тех коэффициентов разложения, которые являются наиболее информативными. В процессе исследований, применяя то или иное правило отбора информативных признаков с учетом того, что критерии оценки информативности должны выражать степень различимости объектов разных образов, можно получить наиболее информативные (оптимальные) наборы коэффициентов разложения (признаков) для данного объекта и, таким образом, сформировать из исходного пространства коэффициентов признаковое пространство меньшей размерности.

Отличительной особенностью применения предлагаемого метода является его адаптивность к классу сигналов и изображений и универсальность. Метод базируется на хорошо развитом математическом аппарате. Имеются широкие возможности оптимизации предлагаемых алгоритмов, высокий уровень их адаптации, связанный с Электронный научный журнал ИССЛЕДОВАНО В РОССИИ выбором системы координат и соответствующего ортогонального базиса в функциональном пространстве L2 при аппроксимации сигналов.

Основная часть Выбор оптимальной системы координат при параметрическом описании контурных изображений имеет целью получить аналитическое описание исследуемого изображения возможно более простым, то есть отрезки ортогональных рядов, описывающих проекции изображения, должны быть по возможности наиболее короткими. Пусть функция r(t), задающая кривую на плоскости, представлена в системе координат G параметрическими уравнениями rG (t) = {xG (t), yG (t) (1) в виде цифровых массивов. Пусть система (1) описывается аналитически набором базисных функций B={Xi(t)} y x x (t) = NG Ai X (t), yG (t) = NG X (t).

B G i i i i=1 i= Тогда, если понимать точность описания в определенном смысле (например, в среднеквадратичном), требуется выбрать такую систему координат G и такой x ортогональный базис В, для которых величины NG,y минимальны при одной и той же точности описания (индекс G означает, что требуемая глубина разложения может зависеть от выбранной системы координат).

В задачах распознавания образов помимо простоты аппроксимации данных необходимо учитывать требование простоты реализации алгоритма распознавания.

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

Для выбора оптимальных геометрических координат будет построен алгоритм оценки информативности базиса. Выполнение данного алгоритма, естественно, будет производиться на этапе обучения основной распознающей процедуры. Предположим, имеется M различных изображений. Среди них есть изображения L различных объектов (q1, q2,...., qL). Каждый объект qi (1

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

i, j,l,m =1 i, j,m =il jm Здесь i, l - номера объектов, j, m - номера изображений в подклассе изображений одного и того же объекта (например, ракурс изображения или изображения объекта на разных расстояниях), - номер коэффициента разложения (признака), суммирование ведется по всем признакам (например, по коэффициентам разложения x y обеих проекций контура, всего NG + NG признаков), G - принятая система G координат. Так, Aij, - коэффициент разложения под номером j-того изображения i-того объекта, рассмотренного в системе координат G. Имеется также свободный параметр, по которому можно оптимизировать алгоритм.

Сформулируем условие оптимальности геометрического описания в следующем виде: из всех имеющихся вариантов систем координат {G} используем описание Gm, для которого имеет место максимум функции (2), (3) x y x y NG +NG NG +NG G G G G max (Aij, - Alm, )2 (Aij, - Aim, )2.

G i, j,l,m =1 i, j,m =jm il x y При этом либо число NG + NG фиксировано, либо из всего набора коэффициентов используются лишь некоторые с номерами 1, 2,Е, i,Е Электронный научный журнал ИССЛЕДОВАНО В РОССИИ Пример 1.

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

Пусть каждая из букв представлена тремя изображениями, которые отличаются между собой выбором шрифта, размера, наклона. Таким образом, рассматриваемый класс определен двумя объектами L = 2, а полное число изображений M=6.

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

i,l = j,k =max [(Aij, - Alk, )2 + (Aij, - Alk, )2] 1 1 2, 1 2 i,l =j,k = i l (4) i= j,k =[(Aij, - Amk, )2 + (Aij, - Amk, )2].

- 1 1 2 i=j,k = j k В данном случае i, l - номера объектов (i,l =1,2 ); j, m - номера изображений в подклассе изображений одного и того же объекта ( j,m =1,3); 1, - два признака, по которым ведется поиск максимума функции (4). Для класса, представленного в приводимом примере, допустимые значения параметра удовлетворяют условию 5 20.

Рассматривается параметризация контурных изображений следующего вида:

12 (5) x(t) = AiTi (t), y(t) = Ti (t) - в декартовых координатах, B i i=0 i=11 (6) (t) = Ti (t), (t) = Ti (t) - в полярных координатах, C D i i i=0 i=Электронный научный журнал ИССЛЕДОВАНО В РОССИИ здесь и - радиальная и угловая координаты, суммы (5) и (6) представляют собой разложение проекций по полиномам Чебышева. В качестве признаков используем величины A1, A2,...., A12, B1,...,B12,..., C0,...,C11, D0,...,D11 - всего 48 признаков (в выражении (4) величины 1 и 2 - суть натуральные числа от 1 до 48). Оптимизация по 1 и 2 (из (4)) с перечисленным набором признаков приводит к решению задачи о двух наиболее информативных признаках (следовательно, об оптимальной системе координат) при распознавании в данном классе изображений.

В рассматриваемом случае решающая функция (4) достигает максимума при 1=40, 2=42, которые соответствуют разложению в полярных координатах, а точнее - пятому и седьмому коэффициентам разложения (t). Следовательно, для описания заданных изображений больше подходит полярная система координат. Расположение точек, соответствующих объектам на оптимальной признаковой плоскости, приведено на рис. 1 (во втором и четвертом квадрантах). Здесь же для наглядности приведены и распознаваемые символы. Таким образом, уже на основании знания лишь двух признаков (двух коэффициентов разложения) распознаются оба объекта (рис. 1).

Рис. 1.

Проверку устойчивости решения данной задачи будем проводить следующим образом: дополним рассматриваемую выборку альтернативными написаниями рассматриваемых символов (S, Z). После необходимой предварительной обработки изображений объектов получим требуемые аналитические описания полиномами Чебышева. Полученные коэффициенты разложения будем рассматривать как признаки. Выберем признаки с номерами 1=40, 2=42 и расположим точку с Электронный научный журнал ИССЛЕДОВАНО В РОССИИ координатами, равными выбранным признакам, на оптимальной признаковой плоскости. Эта точка соответствует вновь введенному изображению S (см. рис. 2).

Рис. 2.

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

Устойчивость решения задачи проверялась еще следующим образом:

накладывали шум различного уровня (от 0,2% до 13%) на изображения и пытались распознать их. А конкретно, с помощью генератора псевдослучайных чисел моделировался белый Гауссов шум и аддитивно добавлялся к рассматриваемым изображениям. Получив их аналитическое описание, рассматривая коэффициенты разложения в качестве признаков и вычленив только информативные признаки, при которых функция (4) достигала максимума (1=40, 2=42), на оптимальной признаковой плоскости отражали расположение точек, соответствующих рассматриваемым объектам (см. рис. 4.). Как видно из рисунка, наложение шумов не испортило картину, и предложенная процедура также справилась с поставленной задачей. Для наглядности представим изображения одного из рассматриваемых объектов с наложенным на него шумом (2% и 5% соответственно) (см. рис. 3):

Электронный научный журнал ИССЛЕДОВАНО В РОССИИ Рис. 3.

Рис. 4.

Пример 2.

Рассмотрим другой пример. Попробуем усложнить задачу: определим класс объектов буквами S, I, T, t, f, r, x (L = 7); и пусть каждый объект имеет по 4 различных изображения (М=28). Для наглядности на рисунке 5 представлен весь класс рассматриваемых объектов:

Рис. 5.

Проведем параметризацию в декартовой и полярной системах координат для данных контурных изображений. Так же как и в предыдущем примере, на первом этапе реализации обучающей процедуры рассмотрим случай двухпризнакового пространства и, вычислив максимум решающей функции (4) для данного класса, найдем наиболее информативные признаки. В рассматриваемом случае функция (4) достигает максимума при 1 =30, 2=38, что соответствует разложению в полярных Электронный научный журнал ИССЛЕДОВАНО В РОССИИ координатах. И в этом случае, следовательно, для описания изображения больше подходит полярная система координат. Рассмотрим рис. 6, на котором на оптимальной признаковой плоскости представлены точки, соответствующие объектам рассматриваемого класса. Таким образом, знание двух признаков дает возможность распознать лишь один объект, букву r.

Рис. 6.

Следовательно, необходимо перейти к следующему этапу реализации процедуры и рассмотреть случай трехпризнакового пространства. Причем, сначала поступим так: к двум определенным признакам (1=30, 2=38) подберем третий, вычисляя максимум функции i,l= j,k,n=mi max [(Aij, - Alk, )2 + (Aij, - Alk, )2 + (Aij, - Anj, )2] 3 1 1 2 1,,3 i,l= j,k=iln (5) i= j,k=mi - [(Aij, - Aik,1 )2 + (Aij, - Aik, )2 + (Aij, - Ain, )2].

3 1 2 i= j,k,n=jkn Максимум функции (5) при заданных 1, 2 достигается при 3=40. Таким образом, располагая на оптимальном пространстве точки, соответствующие буквам рассматриваемого класса (см. рис. 7), видим, что, зная три коэффициента разложения по полиномам Чебышева, распознаются следующие буквы.

Электронный научный журнал ИССЛЕДОВАНО В РОССИИ Рис. 7.

Но можно подойти к этой задаче и с другой стороны: оптимизировать сразу по трем признакам 1, 2 и 3 (по (5)) В данном случае функция (5) достигает максимума при 1=30, 2=38, 3=40. То есть, и независимая оптимизация по трем признакам дала те же результаты.

Заключение В свете сказанного появляется возможность существенного сокращения вычислительной работы при распознавании на основе ступенчатого алгоритма. Для каждого этапа (1, 2,...., j,....) (рис. 8) находится оптимальный сокращенный набор признаков {P1}, {P2},..., {Pj}. На каждом этапе распознающий алгоритм использует свой набор. На каждом этапе заведомо распознаются определенные наборы объектов {O1}, {O2},..., {Oj}. Если исходный набор {N}, то после каждого этапа (если на соответствующем этапе результат не достигнут) число возможных объектов сокращается (класс сужается): {N}\{O1}, {N}\{O1}\{O2} и т. д. Как нетрудно проверить, объем вычислений при этом существенно уменьшается (как за счет сокращения вычислений признаков, так и за счет сокращения вычислений расстояний в признаковом пространстве).

Рис. 8.

Pages:     | 1 | 2 |    Книги по разным темам