Распознавание изображений по параметрам преобразований

єдину розподілену базу даних, яка б охоплювала всі рівні управління та забезпечувала інформацією функціональні задачі, що вирішуються на цих рівнях.

На сьогодні в рамках запропонованого підходу розроблено комплекс задач локального рівня, які реалізують функції контролю працездатності У КЗ, ідентифікації та оптимізації режимів електро-хімзахисту трубопроводів, розрахунку показників ефективності функціонування засобів ЕХЗ і захищеності споруд від корозії, створення та ведення локальних баз даних. Розроблені задачі впроваджені у виробництво і проходять дослідну експлуатацію на ряді ЛЕС України і за її межами.

Література: 1. Палашов В.В. Расчет полной катодной защиты. Л.: Недра, 1988. 136 с. 2. МесаровичМ., МакоД, Такахара И. Теория иерархических многоуровневых

систем. М.: Мир, 1973. 344 с. 3. Чернышев М.К., Гаджиев М.Ю. Математическое моделирование иерархических систем с приложением к биологии и экономике. М.: Наука, 1983. 192 с. 4. Месарович М, Такахара Я. Общая теория систем: математические основы. М.: Мир, 1978. 311 с. 5. Бородавкин П.П., Березин В.Л. Сооружение магистральных трубопроводов. М.: Недра, 1977. 407с. 6. Зиневич А. М., Глазков В. И., Котик В. Г. Защита трубопроводов и резервуаров от коррозии. М.: Недра, 1975. 288 с.

Надійшла до редколегії 10.11.1998 Рецензент: д-р техн. наук, проф. Левикін В. М.

Скляров Станіслав Олександрович, аспірант кафедри ПО ЕОМ ХТУРЕ. Наукові інтереси: математичне моделювання, теорія прийняття рішень. Адреса: Україна, 310726, Харків, вул. Конєва, 16, кімната 702, тел. 20-57-89, 37-49-48.

УДК 681.327

РАСПОЗНАВАНИЕ ИЗОБРАЖЕНИЙ ПО ПАРАМЕТРАМ ПРЕОБРАЗОВАНИЙ

ГОРОХОВАТСКИЙ В.А.

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

Теория нормализации изображений [1] обосновывает процессы распознавания для объектов, подвергающихся геометрическим преобразованиям в поле зрения. В настоящее время создаются программные приложения этой теории с учетом возможностей современных компьютеров по обработке реальных полутоновых и цветных изображений [2]. Рассмотрим метод и соответствующий алгоритм распознавания, в основе которых лежит теория построения нормализаторов. В этом подходе, как и в классическом [1], вначале определяются параметры геометрических преобразований. Затем по полученным параметрам осуществляется распознавание класса эквивалентности изображения. Предлагаемый подход к распознаванию обладает большим быстродействием, так как в нем отсутствует сравнение двумерных полей, характерное для распознавания путем предварительной нормализации.

Из основной теоремы теории нормализации [1] следует, что для одного и того же класса эквивалентности изображений Wk существует большое разнообразие конкретных представлений нормализаторов. Общий вид оператора нормализации

F

(здесь В — изображение; В є W — множество изображений; G — группа преобразований) показывает, что это разнообразие обеспечивается различием

отображений Ф.

Утверждение 1. Пусть G — группа преобразований с элементами g є G ; Wk — фиксированный

класс эквивалентности Wk є W; Ф1, Ф2,..., Ф8 —

произвольные отображения Ф^W ^ G, і = 1,s, удовлетворяющие условию нормализации

giФi

g1,g2,...,gs — параметры преобразования изображе-

ния В, определяемые отображениями Ф1, Ф2,..., Ф s. Если В є Wk , то имеет место равенство

g1 = g2 =...= gs.

Доказательство. Если В є Wk , то

В = Bog, g є G . Тогда из (2) для і -го элемента в равенстве (3) имеем

gi =Ф і(В0)[Ф і (В)]-1 =Ф і(В0)[ф і^)]-1 =

= Ф і

-1

Применяем правило получения обратного элемента в группе, после чего

gi = Фі(В0)[Фі(В0)] 1g = g .

Доказанное не зависит от і, значит, условие (3) выполняется.

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

эквивалентности Wk мы получаем один и тот же параметр преобразования g.

Утверждение 2. Пусть W1, W2 — классы эквивалентности

W1 = ^0g,g є G}, W2= ^0g,g є g},

В — изображение, принадлежащее одному из классов W1, W2; Ф1, Ф2 — отображения, удовлетворяющие условию нормализации (2) относительно обоих классов W1,W2, а g1,g2 — параметры преобразования изображения В, определяемые отображениями

Фъ Ф2 .

Для того чтобы равенство g1 = g2 выполнялось

только для одного из классов ( W1 или W2 ), необходимо условие

РИ, 1998, № 4

43

Ф1

-1

* Ф2

-1

Доказательство. Предположим вначале, что Б є W1, т.е. Б = B0g. Из утверждения 1 следует, что g1 = g2 . Покажем теперь, что относительно класса W2 условие g1 = g2 не выполняется. Вычислим

g1 =Ф1(Б2)[Ф1(Б)]-1 = Ф1(Б0)[ф1(Б0^]-1 =

= Ф1(б2)[Ф1(б0)] V

Аналогично для g2 получаем

g2 = Ф2(Б0) Ф2(Б0) g.

Из соотношений для g1 и g2 при условии (4) имеем, что g1 * g2 . Аналогично доказывается и

предположение, что Б Є W2 .

Утверждение 2 допускает обобщение на случай, когда число эталонов равно q , а число отображений равно s . Условие (4) имеет вид совокупности

Ф1

-1

Ф1

1 * Ф2

Фs-l

которая включает С? • C2 условий, так как пары эталонов и отображений выбираются независимо друг от друга, cq,C2 — число комбинаций. Кажется, что

проверка условий (5) для больших значений q,s может вызвать трудности из-за больших значений

величины С? • С:?. Однако процедура проверки вы-

полняется однократно во времени настройки на определенный набор эталонов, поэтому на длительности времени распознавания не сказывается. Для того чтобы условие (3) выполнялось только для класса эквивалентности распознаваемого изображения, тре-

буется, чтобы для каждой пары эталонов Bj,Bj

выполнялось хотя бы одно из условий совокупности (5). С увеличением количества выполняемых условий для конкретной пары эталонов увеличивается расстояние между классами эквивалентности Wj, Wj, а следовательно, растет надежность различения этих классов при воздействии помех. Это же можно отметить и относительно роста величины s , при котором увеличивается число используемых признаков (отображений), а следовательно, повышается достоверность распознавания классов [ 1].

Таким образом, выбор Фj и количества членов в условии (3) определяется разнообразием различаемых классов и уровнем помех.

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

1. Для множества из q эталонов выбираем s отображений, удовлетворяющих условию (5).

2. Вычисляем эталонные значения отображений

Ф1(Б0), ФДБ?),...^^),...^^),..., Фs(Bq).

3. Полагаем j = 1 и выбираем эталон Bj из множества эталонов.

4. Для распознаваемого изображения Б проверяем выполнение равенства (3) в виде

Ф1(Б0)[Ф1(Б)]-1 = Ф 2(Б0)[ф aw]1 =

=...= Ф s

5. Если (6) выполняется, принимаем решение о соответствии Б i -му классу. Если (6) не выполняется, то i = i + 1 и при i < q переход к п. 4. Если

i > q — конец алгоритма.

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

Конкретизируем алгоритм для преобразований

смещения, когда B(x,y) = B0(x + lx,y + ly), где lx, ly — параметры смещений. В качестве отображений Ф i выберем функциональные центры тяжести

[1], обозначив их ФДБ), Фу (Б). Величины смещений находим по формулам

lx = Фx(B)- Фx(Bo), ly = Фу (Б) - Фy(Bo).

Условие (5) состоит в том, чтобы для каждой пары эталонов B0, Bjj выполнялось хотя бы одно из соотношений

Фkx(B0) - Фkx(B0) = Фlx(B0) - Фlx^jX k * l, т.е. чтобы для двух различных эталонов не были равны их функциональные центры тяжести. Приме -ром меры для проверки условия (6) может быть

R(B,B0) = 2 {|Qix - Qjxl + |Qiy - Qjy} i,j ’

^Qix = Фix(B)- Фix(Bo),Qiy = Фiy(B)- Фiy(B0).

Величина R удовлетворяет определению метрики в пространстве векторов, а при наличии естественных погрешностей в определении Ф i учитывает степень отклонения от условия (6).

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

44

РИ, 1998, № 4

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

m2

Y =---------------і------,

sm2(ty +2tc)+^s2qtc

или после упрощений с учетом ty = 3tc

г =

6 + 12q

5s + — s2 2

q

m

2

Из (7) следует почти линейный характер зависимости у от числа эталонов q , так как вторым слагаем в знаменателе для практических значений m и q можно пренебречь (m значительно больше q). Делаем вывод, что с увеличением числа эталонов выигрыш во времени распознавания для предлагаемого алгоритма возрастает. Так, для случая

s = 10, q = 10, m = 16 имеем у = 2,5 , а при

s = 10, q = 20, m = 16 у = 4,5 . Кроме того, значение Y уменьшается с ростом числа отображений (признаков) s .

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

16х16 элементов с числом градаций, равным 8, количеством эталонов q = 10, отображений s = 8 для преобразований смещения при действии аддитивного шума. Эксперимент показал, что разработанный алгоритм распознавания для выбранного класса эталонов и соответствующего набора отображений обладает помехозащищенностью не худшей, чем традиционный алгоритм, и позволяет осуществлять уверенное распознавание с вероятностью, большей 0,99 при уровне сигнал-шум, равном 5. Алгоритм распознавания с нормализацией обеспечивает эту вероятность при уровне сигнал-шум, равном 6. Достаточно высокая помехозащищенность объясняется многократным характером измерений и отсутствием нормализующих воздействий.

Выигрыш в быстродействии в эксперименте составил y = 2, что подтверждает эффективность подхода и целесообразность его применения при решении задач инвариантного распознавания изображений.

Литература: 1. Путятин Е.П., Аверин С.И. Обработка изображений в робототехнике. М.: Машиностроение, 1990. 320 с. 2. Гороховатский В.А., ТрипутеньВ.В. Алгоритм параллельной нормализации аффинных преобразований для цветных изображений // Радиоэлектроника и информатика. 1997. Вып. 1. С. 97-98.

Поступила в редколлегию 22.11.1998 Рецензент: д-р техн. наук Путятин Е.П.

Гороховатский Владимир Алексеевич, канд. техн. наук, доцент кафедры применения ЭВМ ХТУРЭ. Научные интересы: обработка изображений в компьютерных системах. Адрес: Украина, 310141, Харьков, пр. Ленина, 14, тел. 40-94-19.

УДК 681.142.1.01

ПРОГНОЗИРОВАНИЕ ВОЗМОЖНЫХ СОБЫТИЙ В СИСТЕМАХ ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ

ХОДАКОВ В.Е., ШЕРСТЮК В.Г.,

СТЕПАНСКИЙ К.Г., ДИДЫКА.А., КОЗУБ НА, ГРИГОРОВА А.А., РАДВАНСКАЯ Л.Н.__

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

1. Введение

В настоящее время использование технологий информационных хранилищ (Data Warehousing), переработки данных (Data Mining) и извлечения знаний (Knowledge Discovery) становится все более популярным при решении задач обработки больших массивов информации. Практически все вновь разрабатываемые системы сбора и анализа информации используют, частично или полностью, эти технологии.

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

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

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

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

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

РИ, 1998, № 4

45