Стронгин Р.Г (ред.) Высокопроизводительные параллельные вычисления на кластерных системах

Подождите немного. Документ загружается.

341

ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ РАСПОЗНАВАНИЯ

ИЗОБРАЖЕНИЙ НА ОСНОВЕ АНАЛИЗА ХАРАКТЕРНЫХ

ОБЛАСТЕЙ

А.В. Шлянников

Казанский государственный университет

Аннотация

Предложен метод идентификации фотографий лиц, основанный на

неортогональном wavelet-преобразовании. Материнская функция

преобразования представлена матрицами ранга 1, что позволяет

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

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

кадрированию фотографии. Для реализации процедуры распознавания

предложен вариант распараллеливания вычислений. Приведены

результаты экспериментов.

Математическая модель

Решается задача распознавания образов в следующей форме.

Имеется база данных, содержащая некоторое количество фотографий,

и конкретный образец. Требуется выделить в базе ту из фотографий

(или целый класс фотографий), обладающую наибольшей схожестью с

представленным образцом.

Для описания сравниваемых изображений применяется метод их

аппроксимации с помощью стандартных компонентов, находящихся в

специальном словаре.

Суть данного метода состоит в сжатом

представлении заданного набора векторов одной размерности. В

результате процедуры сжатия понижается размерность векторов, после

чего применяется тот или иной алгоритм идентификации. Для этого

используется неортогональное wavelet-преобразование на основе

базисных функций специального вида.

Пусть имеется два изображения, для которых необходимо

определить меру их соответствия друг другу

. Для определения

наиболее характерных областей фотографии и аппроксимации

изображения используется метод, предложенный в [1]. Множество

базисных векторов, по которому ведется разложение, состоит из

матриц вида

βα

, где

),,( cwmVec

∈

),,( cwnVec

′

∈

представляющих собой изображения колоколообразной формы.

342

Вектор

),,( centerwNVec∈

размерности N получен из нулевого вектора

путем помещения в него вектора

)(wSn

)1(

sin)(

⎟

⎠

⎞

⎜

⎝

⎛

22,...,0

−

таким образом, что

координата с номером

вектора становится координатой с

номером

center вектора

. После этого вектор нормируется, чтобы его

длина стала равной 1.

Зафиксируем одно значение

′

, определяющее размер

колоколообразного базисного изображения, и

- число слагаемых в

сумме, аппроксимирующей заданное изображение базисными. После

аппроксимации обоих изображений согласно одинаково

зафиксированным параметрам, для каждого изображения получаем

набор дескрипторов следующего вида:

),,(

d =

ni ,...1

где

- коэффициент разложения изображения по данному базису,

- координаты центра вектора

)(wSn

в векторах

),,( centerwNVec∈

),,( centerwNVec

∈

соответственно. Далее

каждый набор дескрипторов можно рассматривать как множество

точек на плоскости с координатами

. Дискриминантная

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

как некоторая метрика на множествах точек на плоскости.

В качестве такой метрики была выбрана метрика Хаусдорфа: если

BA,

- два множества точек, соответствующие первому и второму

изображениям, то для каждой точки

∈

находится расстояние от

до

, а затем подсчитывается

),(sup)( Bad

BA =

. После этого

множества меняются местами и подсчитывается аналогичная

величина. Метрикой считается значение

))(),(max(),( ABBABAd

Использование данной методики сравнения является устойчивым

при таких искажениях изображения, как кадрирование и

масштабирование. Но чтобы достичь этого эффекта, требуются

преобразования изображений в процессе подсчета расстояния,

направленные на устранение этих искажений. Суть этих

преобразований состоит в итеративном улучшении вычисляемой

метрики. Изначально предполагается, что оба изображения

принадлежат к одному и тому

же классу, и требуется определить

343

преобразования искажения, максимально приближающие первое

изображение ко второму по расстоянию, определяемому как метрика

Хаусдорфа на совмещенных множествах. К одному из множеств

векторов итеративно применяются преобразования масштабирования и

переноса на малую величину. Если в процессе преобразования метрика

была уменьшена, то считается, что второе изображение было

подвергнуто данному искажению, и запоминается новое

положение

точек на плоскости.

Изложенный выше подход применим в ситуациях, когда

предполагается, что все фотографии сделаны при одной и той же

позиции лица. Для того чтобы компенсировать возможность поворота

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

Рассмотрим преобразование Фурье в полярных координатах:

∑

−

+−=

))

)sin()cos(

(2exp(),(

),(

ϕϕ

πϕ

где

),(

- координаты центра i-го шаблона в аппроксимации

изображения,

),(

- коэффициент, с которым данный шаблон

входит в аппроксимирующую сумму. Если

),(

′

- преобразование

Фурье в полярных координатах для повернутого изображения, а

),(

– для исходного, то имеет место соотношение:

),(),(

−

′

rFrF

Но данное соотношение имеет место только том случае, если все

точки множества были повернуты на одну и ту же величину. В

реальном же случае такого может и не быть (например, если человек

на фотографии наклонил голову и т. д.). Поэтому для определения

таких искажений использовался следующий метод.

Фиксируется дискретный набор

значений

и вычисляются

значения функций

),(

′

в данных точках. Между

полученными матрицами коэффициентов вычисляется построчно

корреляция, и затем находится итоговый вектор корреляций как

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

значение в данном векторе и определяется соответствующий ему угол

поворота. Считается, что второе изображение было повернуто на

найденную величину относительно первого.

344

Алгоритм сравнения пары изображений

1. Предварительный этап: совмещение множеств и компенсация

возможного поворота.

1.1. Наборы точек масштабируются таким образом, чтобы

величины среднеквадратического отклонения положения точек от

центра медиан стали равными.

1.2. Наборы точек совмещаются таким образом, чтобы совпали их

центры медиан.

1.3. Определяется предположительный поворот второго

изображения относительно первого.

2. Итеративное улучшение метрики: компенсация возможного

кадрирования и

масштабирования.

2.1. Второе множество точек растягивается/сжимается на малую

величину. Если метрика улучшается, то запоминается новое значение

метрики и положение точек.

2.2. Координаты второго множества сдвигаются на малую

величину. Если метрика улучшается, то запоминается новое значение

метрики и положение точек.

2.3. Второе множество точек поворачивается на малую величину.

Если метрика улучшается, то

запоминается новое значение метрики и

положение точек.

2.4. Если на шагах 2.1 – 2.3 метрика не была уменьшена или

достигнут максимум по количеству итераций, то текущее значение

метрики считается итоговым и алгоритм сравнения пары изображений

заканчивает свою работу. В противном случае осуществляется возврат

на шаг 2.1.

Таким образом, получаем набор численных характеристик

соответствия исходного изображения

каждому изображению из

заданного множества. Если для какой-либо пары значение

характеристики меньше заданного порогового значения, то считается,

что данная пара представляет собой одно и то же изображение -

исходное и искаженное.

Параллельная реализация алгоритма

Первая очевидная оптимизация состоит в том, что коэффициенты

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

могут быть вычислены заранее и сразу использованы при подаче

фотографии для сравнения со всеми экземплярами из базы данных на

вход алгоритма.

345

Распараллеливание вычислений происходит на двух стадиях

работы алгоритма. Первой стадией является процедура аппроксимации

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

вычислительную сложность. Как было указано выше, процедуру

аппроксимации можно выполнить заранее для всех изображений из

базы. Поэтому все присутствующие в базе фотографии разделяются по

процессам вычислительной системы и обрабатываются параллельно.

Вторым

этапом является сравнение представленной фотографии со

всеми образцами из базы данных. Сравнение ведется попарно, поэтому

процедура разделяется по процессам согласно количеству фотографий

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

Результатом каждой процедуры сравнения является значение метрики.

По завершению работы процедуры во всех процессах полученные

значения собираются и формируется набор фотографий,

представляющих

наибольшую схожесть с представленным образцом.

Результаты расчетов

Рис.1. Пример исходного изображения и искаженного (поворот, кадрирование,

масштабирование)

Рис. 2. Соответствующие представления изображений

(число слагаемых в аппроксимирующей сумме равно 100)

В общем случае пороговая величина, определяющая изображения

как одинаковые, зависит от размера изображения и от числа слагаемых

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

346

больше значения метрики, и чем больше выделено точек, тем заметнее

разница в значениях метрики для пар одинаковых изображений и

различных. Поэтому при тестировании пороговое значение

выбиралось опытным путем таким образом, чтобы минимизировать

величину ошибок при приемлемом времени работы алгоритма. В

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

различных исходных

изображений и множеств предполагаемых

искаженных при нулевой ошибке первого рода ошибка второго рода

не превышает 10%.

Литература

1. Столов Е.Л. Параллельный алгоритм для отыскания водяных

знаков в изображении. // Вестник Казанского

государственного технического университета, 2006, № 3 с.37-

42.

Ming-Hsuan Yang, D. J. Kriegman, N. Ahuja, Detecting Faces in

Images: A Survey // IEEE TRANS PATTERN ANALYSIS AND

MACHINE INTELLIGENCE, VOL. 24, NO. 1, 2002, pp. 34-57.

Айвазян С.А. и др. Классификация и снижение размерности

.М.: Финансы и статистика, 1989. 607 с.

Song H., Chung S. J., Park Y.H. An Online Face Recognition

System Using Multiple Compressed Images over the Internet //

WISE 2005, LNCS 3806, Springer-Verlag, 2005, p. 569 – 576/

Yang J., Zhang D., et al. Two-Dimensional PCA: A New

Approach to Appearance-Based Face Representation and

Recognition // IEEE TRANS PATTERN ANALYSIS AND

MACHINE INTELLIGENCE, VOL. 26, NO. 1, p. 131-137.

Huang Y. S, Tsai Y.H., Shieh J.W. Robust Face Recognition with

Light Compensation // PCM 2001, LNCS 2195, Springer-Verlag,

2001, p. 237–244.

Sing J. K., et al. Face recognition using point symmetry distance-

based RBF network // Applied Soft Computing , V.7, 2005, p. 58–

70.

Phillips P.J. Matching pursuit filters applied to face identification //

IEEE Trans. Image Process. 7 (1998) 1150–1165.

Cand`es E.J., Donoho D.L. New tight frames of curvelets and

optimal representations of objects with piecewise C2 singularities.

Comm. on Pure and Appl. Math. 57 (2004), p. 219–266.

347

10.

Гонсалес Р., Вудс Р. Цифровая обработка изображений. М.:

Техносфера, 2006.

РАСПРЕДЕЛЕНИЕ ЗАДАНИЙ В КОМПЬЮТЕРНОЙ СИСТЕМЕ

НА БАЗЕ НЕЙРОННОЙ СЕТИ

М.Ю. Юрич, Р.К. Кудерметов

Запорожский национальный технический университет

Введение

В последнее время быстродействие стало весомым параметром

определения качества компьютерной системы. Применение

параллельных технологий значительно увеличивает эффективность

работы многопроцессорных вычислительных систем, которые

являются мощным средством для решения задач больших

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

возникает такая проблема, как распределение нагрузки между узлами

сети. Эта проблема найдет эффективное решение при

равномерном

распределении задач между ними. Но при распараллеливании потока

задач между большим количеством машин возникает проблема

насыщения межсетевого взаимодействия [1]. Для минимизации общего

времени выполнения задач в сети необходимо решить две

взаимопротиворечащие проблемы – обеспечение равномерности

распределения задач между большим количеством компьютеров и

минимизацию насыщения межсетевых взаимодействий.

Существуют различные подходы к решению

задач распределения,

и каждое из них имеет свои преимущества и недостатки [2,3]. В

данной работе предпринята попытка решить эту проблему с помощью

нейронной сети. Авторами выбрана нейронная сеть Дж. Хопфилда,

поскольку она обладает необходимым быстродействием в силу

распараллеленности работы, и минимизирует свою энергию, что дает

возможность с наименьшими временными затратами решить

поставленную

задачу.

Постановка задачи

Пусть задана распределенная система, в которой поступают n

потоков заданий, задачи которых необходимо равномерно

распределить между

m компьютерами сети. Предполагается, что

348

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

момент распределения заданий различна.

Наша цель состоит в назначении заданий потока

n одному из m

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

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

минимальным.

Для решения поставленной задачи с помощью нейронных сетей

Хопфилда введем следующие обозначения:



– матрица–столбец, каждое значение в которой есть

количество задач

–го потока, которые необходимо решить на

одном из компьютеров

в момент времени t;



– матрица–строка, каждое значение в которой есть

максимальное количество задач, которое может быть решено

на

–м компьютере при равномерной загрузке компьютеров;



– матрица

, где в качестве элементов есть количество

связей между компьютерами

i и j, при решении задач i–го

потока на

j–м компьютере. Данное значение вычисляется как

cc −

, если

cc ≥

cc −

, если

cc ≤

и чем меньше будет

это значение, тем быстрее будет найдено оптимальное

решение.

Необходимо найти количество задач

, которое необходимо

решить из

i–го потока на j–м компьютере. То есть, необходимо найти

матрицу

, в которой в i–й строке и

–м столбце будет стоять

единица, если

–е задание назначено

–му компьютеру, и нуль – в

обратном случае.

При этом для нахождения решения поставленной задачи

необходимо, чтобы для

, не равного нулю.

∑∑

→⋅

ijij

min

, (1)

т.е. время выполнения перераспределения задач должно быть

минимальным.

Матрицу

назовем планом. При этом количества задач

должны удовлетворять следующим условиям (2):

349



0≥

– количество задач неотрицательно;



∑

iij

ni ,1=

– количество задач потока, которые

необходимо решить, должно совпадать с количеством задач

этого потока;



∑

jij

mj ,1=

– количество задач потока, которые

необходимо решить, должно совпадать с количеством задач,

которое возможно решить на данном компьютере.

План, удовлетворяющий ограничениям (2), называется

допустимым планом. Допустимый план, удовлетворяющий критерию

(1), назовем оптимальным планом. Как и любая задача целочисленного

программирования, данная задача (транспортная задача или задача о

назначениях) имеет необходимые и достаточные условия

своей

разрешимости и имеет решение тогда и только тогда, когда

выполняется условия баланса:

∑∑

. (3)

Распределение заданий в сети

При моделировании сети Хопфилда необходимо иметь

первоначальные данные, такие как количество задач, которое

возможно решить при условии равномерной загрузки узлов в сети,

CJ[j], и количество задач, которые необходимо оптимальным образом

распределить между узлами сети

, CI[i]. Оба этих показателя получаем

путем расчета, используя данные из сформированного

статистического файла.

Для того, чтобы определить, какое распределение заданий

является оптимальным, на выходе нейронов, обеспечивающих

минимальное суммарное количество связей, должна стоять единица.

В результате выполнения программы, решающей поставленную

задачу, а значит отработки нейронной сети до своего устойчивого

состояния, получаем значения

V[i][j][k], значения которых от нуля до

единицы. Именно те значения, которые равны единице и будут

искомыми значениями матрицы

U. Индексы i и j будут указывать

350

расположение в этой матрице.

А в реальности, зная эти значения,

будем знать какому

j–му узлу назначить сколько задач i–го узла.

Далее значения

i и j (в том случае, когда V[i][j][k]=1)

используются в файле machines, который уже непосредственно и

отвечает за распределение задач в сети между узлами.

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

лаборатории является независимая работа каждого пользователя за его

рабочей станцией. При этом каждая рабочая станция, за которой

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

Программа, реализующая нейронную сеть, осуществляет расчет

эволюции нейронной сети с учетом различных коэффициентов,

некоторые из которых были найдены опытным путем, при

моделировании, поскольку на данный момент не существует

определенной методики их определения или вычисления [4].

Испытание условно можно разбить на несколько этапов. На

первом этапе были измерены значения загрузок машин и записаны в

текстовый файл. На втором – эти

значения преобразовывались к

необходимому для поступления на входы нейронной сети виду и

проводилась эволюция нейронной системы. На третьем этапе по

результатам, полученным со входов нейронной сети, выполнялась

процедура распределения задач между узлами в сети.

Выводы и результаты исследований

В результате испытания были задействованы компьютеры с

номерами 1, 2, 3, 4. Процессорное время, выделяемое на решение

одной задачи на компьютере, было соответственно равным 19,2%,

24,8%, 87,3% и 49,8%.

При переводе в необходимые нам единицы – количество задач,

выполняемых в данный момент на компьютере, – это будет означать

следующее. На первом компьютере выполняется пять задач, на втором

– четыре, на третьем

– одна, на четвертом – две. Эти данные

применяются при расчете эволюции нейронной сети, которая должна

работать так, чтобы каждая задача была распределена между всеми

компьютерами равномерно и при этом все задачи, распределенные в

данный момент времени, также равномерно были распределены между

всеми компьютерами, причем все заданные условия ограничения,

описанные в поставленной

задаче должны быть соблюдены.