Процессы управления и устойчивость

2). При правильном ответе точка S будет двигаться по диагонали,

а при неправильном – по горизонтали. Процесс перемещения точки

S, изображающей прохождение теста, из начального состояния S

0

в конечное S

k

, отобразится на плоскости QOM некоторой ступенча-

той линией. Эта линия – траектория движения точки S на плоскости

QOM – будет характеризовать управление процессом набора баллов

и ответов. Очевидно, что существует множество возможных управ-

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

S из S

0

в S

k

. Из всех этих траекторий нужно выбрать ту, на которой

выбранный критерий Т – затраты времени – будет минимальным.

2.3. Сбор статистических данных. Точка S

1

движется по

своей траектории. На каждом шаге получаем время ответов на во-

просы первого участника. При ответе второго точка S

2

движется

по другой траектории. Для неё получаем время на каждом шаге. В

результате, получим данные на все возможные пути. Если же тра-

ектория S

2

совпадает с траекторией S

1

на каких-то участках, то их

время суммируется и делится между ними и т.д. Если же S

i

дошла

до линии уровня Level Line, но получены ответы еще не на все вопро-

сы, тогда считаем, что S

i

движется вдоль Level Line до достижения

S

k

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

линии уровня.

2.4. Решение. Общее количество всех возможных траекто-

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

и поэтому применим принцип оптимальности Беллмана. Посколь-

ку конечное состояние системы S

k

известно, то процесс построения

оптимальной траектории начинаем с конца.

Рис. 4. Структура базы MS

Access

Из принципа оптимальности Беллма-

на следует, что если система находит-

ся в некоторой промежуточной точке

S

i

и известна конечная точка S

k

, то

оптимальной стратегией будет та, кото-

рая переводит из точки S

i

в конечную

S

k

по оптимальной траектории, кото-

рой отвечают наименьшие затраты. По-

скольку это справедливо для любой про-

межуточной точки, то приходим к вы-

воду, что оптимальная траектория име-

ет следующее свойство: каждый ее уча-

сток (фрагмент) составляет оптималь-

309

ную траекторию.

Гораздо скорее можно решить задачу динамического программи-

рования по шагам. Пусть число шагов m соответствует количеству

вопросов. Последний шаг непременно должен привести в конечную

точку. Двигаясь последовательно от точки к точке справа налево и

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

екторию, ведущую к S

k

, и соответствующее ей минимальное значе-

ние расхода. Этот процесс заканчивается, приведя к начальной точке

S

0

.

Рис. 5. Структура

системы

Двигаясь теперь от нее в противоположном

направлении, которое показано стрелками

на рис. 3, последовательно проходим иско-

мую траекторию от S

0

к S

k

. Например, если

уже имеем статистические данные, то рас-

смотрим ситуацию на рис. 3, где на диа-

гоналях и горизонталях стоит среднестати-

стическое время. На этом рисунке показа-

на получившаяся по методу динамического

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

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

3. Выводы. В результате получаем среднестатистическую опти-

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

При этом можно вычислить те шаги (вопросы или темы), которые

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

эти вопросы могут быть изъяты из процесса подготовки обучаемых,

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

другими вопросами или темами.

4. Модель практической реализации.

4.1. Компоненты системы. Чтобы реализовать предложен-

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

нентов (рис. 5).

• База данных. Содержит файлы, в которых хранятся тесты,

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

ных MS Access. Структура базы MS Access представлена на

рис. 4.

• Клиентская часть. Представляет собой интерфейс для поль-

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

310

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

пользователя.

• Конструктор тестов. Позволяет создавать новые и редакти-

ровать уже существующие тесты, выставлять для них необхо-

димый уровень знаний.

• Серверная часть. Обеспечивает взаимодействие всех осталь-

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

в реальном времени, позволяет добавлять пользователей, до-

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

4.2. Взаимодействие частей системы. При авторизации

пользователя создаются переменные, в которых хранятся:

• время начала теста;

• текущий вопрос;

• полученные ответы на вопросы (строка, ’0’ – неверный ответ,

’1’ – верный);

• имя пользователя;

• массив, содержащий время, затраченное на ответ к каждому

вопросу (в секундах).

Рис. 6. Алгоритм

статистической обработки

После ответа на последний вопрос

информация записывается в таблицу

tstLog согласно формату, представлен-

ному на рис. 5.

4.3. Статистическая обработ-

ка. Обрабатывается только накоплен-

ная в tstLog статистика. Сначала гене-

рируются матрицы X, Y и Z:

• X – (n × m)-матрица неверных от-

ветов (X

0,1

– переход на нулевом уровне

достигнутых знаний к первому вопро-

су);

• Y – ((m − 1) × m)-матрица верных

ответов (Y

1,2

– означает, что человек, до-

стигнувший первого уровня знаний пе-

решел на второй);

• Z – (m × n)-матрица, где m – коли-

чество правильных ответов, необходи-

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

знаний, n – общее количество вопросов.

311

Далее по построенной матрице Z находим оптимальный путь.

5. Заключение. Таким образом, предлагаемая система и реа-

лизованные в ней алгоритмы позволяет получить экспертную оцен-

ку оптимальной траектории учебного процесса. Кроме того, сама

система интерактивного взаимодействия с обучаемым существенно

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

связанные с контролем знаний.

Рис. 7. Взаимодействие частей системы

312

Гришкин В.М.

Санкт-Петербургский государственный университет

Методы автоматизированной идентификации

гранитных образцов археологических объектов

1. Формулировка задачи. В археологии при реставрации па-

мятников материальной культуры встает задача реконструкции объ-

екта по его составным частям. Эту задачу часто называют проблемой

"склейки вазы из черепков". Типичный случай, когда в ходе археоло-

гических работ получают большое количество фрагментов, принад-

лежащих разным объектам, а определить точную принадлежность

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

что все они принадлежат некоторой известной группе объектов. При

этом решение задачи существенно усложняется, так как сначала

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

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

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

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

фрагментов разных объектов на подмножества фрагментов, относя-

щихся к одним объектам. В качестве исходного множества выступа-

ет набор изображений фрагментов большого количества гранитных

статуй, найденных на территории одного их храмов в Египте. Из-

вестно, что все эти фрагменты принадлежат статуям, находившемся

до разрушения именно в этом месте, а также общее количество этих

статуй. Каждая отдельная статуя была вырублена целиком из од-

ного монолитного куска гранита. Сами гранитные монолиты добы-

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

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

от друга типом гранитов, из которых были изготовлены. Геологи-

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

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

их химический состав один и тот же даже для разных месторожде-

ний. Единственным успешным методом сортировки фрагментов по

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

и видимой текстуре материала фрагмента. Он основан на проведе-

нии экспертизы фрагментов профессиональным художником, обла-

дающим хорошим цветоощущением и достаточным опытом работы в

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

313

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

дения экспертизы и практически не формализуем. Дополнительным

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

фрагменты не находятся в одном месте, а рассредоточены по разным

музеям и коллекциям по всему миру.

Для решения задачи сортировки предлагается создать автомати-

зированную систему обработки изображений фрагментов археологи-

ческих объектов, на которую возложить функции предварительной

группировки изображений по цвету и текстуре. Эта система долж-

на работать с базой изображений фрагментов и изображений, полу-

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

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

крайней мере, унифицировать изображения, отстроиться от неоди-

наковых условий съемки и сделать их менее чувствительными к осо-

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

Результаты работы системы, как и сами унифицированные изобра-

жения, могут быть доступны любому количеству экспертов.

2. Исходные изображения и их предварительная обработ-

ка. Исходными данными для работы системы являются изображе-

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

мощью электронных фотокамер и сохраненных в виде стандартных

файлов изображений в формате JPEG. Все изображения получают

с одинаковым разрешением и полной цветовой палитрой True Color.

Съемка производится при примерно одинаковых условиях освеще-

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

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

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

нанесены линейная и цветовая шкалы. Изображения, обрабатывае-

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

рамленные белым фоном, на котором располагаются размерные и

цветовые шкалы. Первый этап обработки изображений заключает-

ся в цветовой коррекции. В силу различных условий освещенности

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

ных изображений отличается от цветового состава объектов. Осо-

бенно хорошо этот эффект проявляется на цвете фона изображений

– он отличается от чисто белого фона трафарета. Поэтому исходное

изображение корректируется относительно полученного цвета фона

следующим образом.

314

На изображении выбираются небольшие квадратные области от-

носящиеся к фону, расположенные близко к границам изображения.

Для этих областей рассчитываются средние значения красной, зе-

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

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

чения цветовых составляющих фона R

f

, G

f

, B

f

. Затем проводится

коррекция цветовых составляющих каждого пикселя исходного изоб-

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

равны и имеют максимальное значение. Для формата True Color это

значение равно числу 255. Тогда корректированные значения цвето-

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

R

c

i

= 255

R

i

R

f

,

G

c

i

= 255

G

i

G

f

,

R

c

i

= 255

B

i

B

f

.

Это скорректированное изображение и участвует в дальнейшей об-

работке.

3. Распознающая система. Задачу группировки фрагментов

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

строить систему обработки изображений именно в этом ключе. При

этом можно по всей совокупности изображений определить некото-

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

пать цвет и текстура образцов, и сгруппировать эти значения в близ-

кие в статистическом значении группы. Сама группировка и даст

искомое разделение фрагментов по принадлежности. В этом случае

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

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

экспертной оценке можно получить наборы изображений эталонных

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

использовать в качестве эталонных. Саму группировку для осталь-

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

вычисляя расстояние в пространстве признаков до эталонных обла-

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

это расстояние будет минимальным. Естественно, кроме требования

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

удовлетворяло некоторым дополнительным условиям. В этом случае

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

с учителем". При любом подходе к построению системы распозна-

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

315

объектами распознавания [1]. В нашем случае, одним из этих при-

знаков является цвет образца.

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

личное представление цвета. Наиболее распространенным представ-

лением является разложение цвета по основным цветам – так на-

зываемая цветовая система RGB. В этом формате и представлены

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

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

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

цветности в виде отношений основных цветов или их комбинаций.

Кроме того, оно не соответствует цветовому восприятию человека,

который различает отдельные цветовые тона, их насыщенность и яр-

кость. Наиболее соответствующим человеческому восприятию при-

знана цветовая модель HSB (hue, saturation, brightness), составля-

ющие которой прямо соответствуют перечисленным величинам [2].

Между этими цветовыми моделями существует однозначная связь,

описываемая следующими соотношениями:

V = max(R, G, B);

v = min(R, G, B);

S =







0,

если V = 0;

V − v

V

;

Cr =

V − v

V

;

Cg =

V − G

V

;

Cb =

V − B

V

;

H =

π

3

·











Cb − Cg,

если R = V ;

2 + Cr − Cb,

если G = V ;

4 + Cg − Cr,

если B = V ;

где H – цветовой тон, S – насыщенность, V – яркость пикселя.

В системе в качестве вектора признаков используются парамет-

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

оценки математического ожидания соответствующих параметров по

всему предъявляемому изображению. В режиме обучения форми-

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

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

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

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

316

ра, которые используются на этапе распознавания. На этапе распо-

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

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

всех эталонов. Эталон, для которого это расстояние минимально,

используется для дальнейшей проверки. Вокруг точки в простран-

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

параллелепипеда. Размеры граней этого параллелепипеда пропорци-

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

для данного эталона. Если координаты вектора признаков предъяв-

ленного изображения лежат внутри этой области, то считается, что

распознавание произошло успешно и фрагмент входит в группу, опи-

сываемую данным эталоном. В противном случае происходит отказ

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

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

4. Реализация. В настоящее время система идентификации ар-

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

"MATLAB" и основана на использовании цветовых признаков. Си-

стема испытывалась на "сырых" изображениях фрагментов архео-

логических объектов, которые были заранее сгруппированы экспер-

тами. Эталоны строились на половине сгруппированных изображе-

ний, а распознавание осуществлялось для остальных изображений.

Система распознает правильно около 80%, отвергает примерно 10% и

неправильно идентифицирует около 10% предъявляемых изображе-

ний. Относительно низкая вероятность распознавания связана с ма-

лой размерностью вектора признаков и недостаточно представитель-

ной выборкой, на основе которой рассчитывались эталонные при-

знаки. Повышение вероятности правильной идентификации можно

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

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

изображений эталонных выборок.

Литература

1. Дуда Р., Харт П. Распознавание образов и анализ сцен. M.: Мир,

1976. 502 c.

2. Ярословский Л.П. Введение в цифровую обработку изображений.

М: Наука, 1979. 279 с.

317

Демидов С.В.

Санкт-Петербургский государственный университет

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

графического ускорителя и OpenGL API

Рекомендовано к публикации доцентом Гришкиным В.М.

1. Формулировка задачи. Обработка изображений широко ис-

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

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

также эта техника успешно применяется художниками, дизайнерами

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

редактировании видеоряда.

Проблема быстродействия при реализации алгоритмов фильтра-

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

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

ления ресурсов вычислительной машины (как времени, так и опера-

тивной памяти).

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

ления фильтрации изображения с использованием ресурсов совре-

менных графических адаптеров с целью снижения нагрузки на цен-

тральный процессор. Потенциально данная технология может спо-

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

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

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

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

2. Средства реализации.

2.1. Производительность современных графических

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

ведущих производителей (ATI и NVIDIA) значительно превосходят

высокопроизводительные CPU в ряде вычислительных задач. Одной

из основных причин этому является максимальная оптимизация вы-

числительного конвейера GPU (GPU — Graphics Processing Unit) для

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

в процессе просчета графических преобразований. Не менее важным

является также тот факт, что архитектура современных GPU рас-

сматривает форматы fp16 и fp32 чисел с плавающей точкой как ос-

новные типы данных при расчетах [9].

318

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

жүктеу/скачать 30,48 Mb.

Достарыңызбен бөлісу: