автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Построение и исследование аналитических функций расстояния и их применение для анализа и синтеза изображений

На правах рукописи

СЕМЕРИЙ Олег Сергеевич

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

Специальность 05.13.17 - «Теоретические основы информатики»

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата физико-математических наук

Таганрог-2004

Работа выполнена

в Таганрогском государственном радиотехническом университете

Научный руководитель: доктор физико-математических наук,

профессор Каркшценко Александр Николаевич Официальные оппоненты: доктор физико-математических наук,

профессор Рыжов Владимир Петрович (ТРТУ, г. Таганрог)

кандидат физико-математических наук, доцент Мисюра Валентина Владимировна (РГСУ, г. Ростов-на-Дону) Ведущая Ьрганизация: НИИ прикладной математики и автоматизации

Кабардино-Балкарского научного центра РАН (г. Нальчик)

Защита состоится «11» ноября 2004 года в 14 часов на заседании диссертационного совета ДР212.259.09 в Таганрогском государственном радиотехническом университете по адресу: г. Таганрог, пер. Некрасовский, 44, ауд. Д-406.

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

Автореферат разослан « ^ » октября 2004 года.

Просим Вас прислать отзыв на автореферат, заверенный печатью учреждения, по адресу: 347928, г. Таганрог, пер. Некрасовский, 44, диссертационный совет ДР212.259.09.

Учёный секретарь

диссертационного совета ДР212.259.09 доктор технических наук, профессор

)Л.К. Бабенко

2005-4 ,

13544 | з

Общая характеристика работы

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

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

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

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

В соответствии с этим задачами диссертационного исследования являются:

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

2. Определение условий, при которых фуяутч» ряг-г-ртоид мпг^т Аы-п представлены в виде алгебраических выражений с использ*в?Ш<5л14гаИт^вивныхрпераций Ричи,

дни радстАдшя "" п

! »1

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

4. Разработка и исследование методов распознавания и анализа сцен с помощью функций расстояния.

Методы исследований основываются на аналитической, дифференциальной и вычислительной геометрии, топологии, теории R-функций, твердотельном моделировании, конструктивной твердотельной геометрии, краевом представлении, методе трассировки лучей, методах оценки параметров моделей, методе М-оценок, преобразовании Хафа, методе аналитического конструирования агрегированных регуляторов.

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

1. Методы построения знаковых и беззнаковых функций расстояния, а также функций верхнего расстояния для комбинированных множеств в n-мерном пространстве.

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

3. Методика записи функций кратчайшего и верхнего расстояния для двумерных и трёхмерных множеств, ограниченных квадратичными линиями и поверхностями.

4. Обобщение преобразования Хафа для анализа сцен сложных объектов с использованием функций расстояния.

Практическая ценность и внедрение. Разработанный математический аппарат представления геометрической информации может применяться для построения систем конструирования и распознавания изображений, навигации мобильных роботов, обнаружения столкновений. На основании теоретических результатов диссертационной работы было создано программное обеспечение на языке Borland Delphi для конструирования моделей сложных объектов в виде унифицированных файлов моделей, а также конструирования и исследования систем распознавания изображений, планирования траектории движения роботов, обнаружения столкновений.

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

Апробация работы. Основные положения и результаты работы представлялись и обсуждались на Всероссийской научно-технической конференции «Компьютерные технологии в инженерной и управленческой деятельности», (Таганрог, 1998), Международной конференции «Интеллектуальные многопроцессорные системы» (Таганрог, 1999), Всероссийской конференции «Измерения, автоматизация и моделирование в промышленности и научных исследованиях» (Бийск, 2000), Международной конференции «Искусственный интеллект» (Крым, Украина, 2000), Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управлени^'(Т4^аЦмщ#09О), Всероссийском симпозиуме по прикладной и про-

^ j

f m tf'

мьппленной математике (Сочи, 2000), Национальной конференции по искусственному интеллекту с международным участием (Переславль-Залесский, 2000), Международной конференции «Цифровая обработка сигналов и её применение» (Москва, 2000), Международной конференции по управлению, автоматизации, робототехнике и машинному зрению (Сингапур, 2000), Научной сессии МИФИ-2001 (Москва, 2001), Международной конференции «Распознавание образов и анализ изображений» (В.Новгород, 2002), а также на ежегодных конференциях профессорско-преподавательского состава Таганрогского радиотехнического университета (2001, 2002,2003, 2004).

Публикации. Опубликовано 32 работы, из них 28 по теме диссертации.

Структура и объём диссертации. Диссертационная работа состоит из введения, четырёх тематических глав, заключения, списка литературы и приложения. Объём диссертации - 140 страниц. Текст диссертации содержит 62 рисунка и 19 таблиц. Список литературы изложен на 8 страницах и включает 95 наименований.

Содержание работы

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

Первая глава посвящена разработке методов записи функций расстояния для множеств в Ж". Предварительно определяется функция расстояния, а также сопутствующие ей понятия. Пусть £1 с К", ЕсП и | * - j>| = д/Х'-Х*' ~ У ¡У »где * и У заДаны своими координатами ...,*„) и (у1,у2,---,уп) в некоторой декартовой системе координат. Беззнаковой функцией расстояния для Q называется функция /„(*) = inf|jc — ,у(. Знаковой функцией расстояния или просто функцией расстояния для

О. называется функция fa(x) = inf такая что У^(дг)> 0 при хеО, и fa(x)ü 0

при х еП, полагая, что 9Q и Q - граница и замыкание множества £1.

Также вводятся следующие математические объекты. Точка у eil называется точкой противостояния для JteR", если |je-jr| =

V . ... ; .• .■■.->

'" '. У = infljc-zl. Множество точек противостояния, соот-

teil1 1

ветствующих точке д;, обозначается как £„(*). Множество Ф = е К" | 4а(х) п ^ * Щ называются множеством Вороного для £ в контексте Q и обозначается как F(L | fi) (рис. 1).

Формулируется и доказывается в виде сле-

Ршс. 1. Множество Вороного дующей теоремы важное свойство множества Воро-Ф = Г(£|П).

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

Теорема 1. Пусть и граница дО. в некото-

рой окрестности точки у е дС1 представляет собой к -мерную С1-регулярную поверхность У, к < п-\, (рис.2). Пусть Д - плоскость, касательная к X в точке у, а У -(п - к) -мерная плоскость, такая что Ч* ± А. Тогда существует такая окрестность е(у) точки у, что

Ряс. 2. Множество Вороного ,, , ч —г-

для точки у на С -регулярной У) I = £(У> п *'

границе дП - луч аЬ, Затем,' анализируется возможность использования

с началом в я и проходящий конструктивных операций Ричи XV у = пип (*,>>) и через точку Ь. 4

лгл^ = тах(д:,>') для записи функций расстояния объединения и пересечения множеств. С этой целью исследуются свойства неявно заданных функций, которые формируются из функций расстояния с помощью конструктивных операций. Определяются области, в которых полученные таким образом функции являются функциями расстояния объединения и пересечения исходных множеств. Также определяются условия, при которых эти функции являются функциями расстояния для всех точек пространства. Делается вывод о невозможности непосредственного использования конструктивных операция для записи функций расстояния объединения и пересечения множеств.

Далее вводятся следующие понятия. Точечное множество называется комбинированным, если оно определяется как объединение множеств, являющихся подмножествами некоторых заданных точечных множеств. Если К" \Р(2|П)= Ч'1иЧ,2, где У, и Ч>2 - не-/^Р связные непустые множества, то множество Е0 назы-Ш вается разделяющим в контексте £1 (рис. 3).

[О, хйО, [оо, х>0.

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

я

Теорема 2. Пусть П = и множества Т( и г = 1... и, такие, что

1=1

Ч*, =£, где 0 - разделяющее множество, причём либо Ч'1=2(.

Тогда/;(*) = «пт{Л<(*)+^[«т1(*)]1-

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

Пусть функция 8 (х) =

щью конструктивных операций объединения и пересечения.

Следствие. Пусть в теореме 2 определены функции А,(лг), i = \...п, такие, что,

если хеУ,, то ht(x) ^ и, если х£ Y,, mo А,(х) £ (дс), у = 1... л, у'*/. Гогйд

Если ввести функцию принадлежности для П как функцию g(1(x), такую что gn(ж)<0 при дс6intCi, ga(x) = 0 при xedCl, gft(*)>0 при х«П, то знаковая функция расстояния может быть определена как /п(х) - sgn> где sgn(0) = 0.

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

Лемма 1. Пусть П £ R", I с дП и ¥ = int^R" \ int(R" \ П)}. Тогда:

1. Если EcW, и дЧ* в окрестности любой точки х е £ представляет собой (я-1)-мерную С2 -регулярную поверхность, то F(£|3Q)n£2*0 и V(Z |Ш)п(К"\П)*0.

2. Если 2 с ffV, и &¥ в окрестности любой точки xel, представляет собой некоторую совокупность участков -мерных Сг-регулярных поверхностей, а х является точкой негладкой стыковки этих поверхностей, то или V(Z | öfi) £ Q, или

r(I|a£l)cR"\n.

3. Если 2 с и Ъ S intQ, то V(Z | ЭП) с П.

4 Если Z<z5Т и 2cint(R"\n), то K(£|dfi)£R"\П.

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

м

Теорема 3. Пусть ßcR", öi2=U2,, а множества ЭЧЛ и Т(, i=\...m, опреде-

(»1

лены в соответствии с теоремой 2. Пусть каждому подмножеству S,, / = 1... т, относящемуся к одному из четырёх классов в соответствии с леммой 1, сопоставлен коэффициент г(е{-1;1}, такой что, если х е V(ll | Ш), ie{l...m}, то

sgn[/nW] = Vsgn[A,(*)]- Тогда ■£.(*) = {>£,(*)+ ¿[/г.М]} ■ "„(*) =

Затем проводится анализ дифференциальных свойств функций расстояния, опре-

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

т

Теорема 4. Пусть flcR", aCl = Uа множества ST,, Y, и множество коэффициентов г,б{-1;1}, i=\...m, определены в соответствии с теоремой 3. Если функции i=\...m, дифференцируемы на то vn(jc) =

-«e«fa{>s;#w+*[*T.w]}«Mi-*}-

Также в первой главе вводится понятие функции верхнего расстояния для Q как функции /n(jc) = sup|*-^|. По аналогии с ранее введёнными понятиями определяются

jrefl

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

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

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

клин acb - это множество точек, ограниченное лучами са и cb, и образованное вращением са вокруг точки с против часовой стрелки, доказывается следующая лемма.

Лемма 2. Пусть пиния ПсМ2 непрерывна в точках a,bed. (рис.4). Тогда множество {«,6} является разделяющим в том и только в том случае, если:

1. Существует такой круг В2(с,г), что {a,b} с сдВ2{с,г) и ClnintB\c,r) = 0. ► 2. Клин adb, образованный касательными к

Рис. 4. Линия П удовлетворяет дВг(с,г) в точках а и Ь, причём се adb, огра-

лемме 2. а

ничивает Q, т.е. Clcadb

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

Теорема 5. Пусть линия ПсИ!, удовлетворяющая условиям леммы 2, может

быть заданна некоторой кривой, С2 -регулярной в точках а,Ь е П, и аЬ - отрезок ли>

нии О, ограниченный точками а и Ь Пусть клин асЬ, ограниченный лучами са и сЬ, такай что аЬ с асЬ. Тогда у{аЬ \ С1) = У^аЬ \ {а,Ь) | п) = асЬ.

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

Пусть известны множества У, и Т,, / = 1...л, в соответствии с теоремой 2. Под схемой комбинирования понимается изображение множества О, на котором каждое покрывающее множество I,, / = 1 ...я, помечено символом из второго столбца /-ой строки таблицы комбинирования. В таблице комбинирования каждому покрывающему множеству 1(, / = 1... л, отводится соответствующая строка, в первом столбце отмечается номер множества 2,, во втором - краткое обозначение множества 2, на схеме комбинирования, в третьем собственно определяется множество к¥п г = 1...и, в четвёртом - функция (х). в пятом - £т(дс). Знаковая функция расстояния задаётся аналогичным образом, только в таблице комбинирования в четвёртом столбце определяются функции /т (*), а в шестом столбце - знаки г,.

Пример. Необходимо записать функцию расстояния для сектора (рис. 5).

Рис. 5. Сектор и линии уровня его функции расстояния.

Рис. 6. Схема комбинирования сеетора.

Пусть г = 1, e( 1,0), 6(0,0) и с(0,1). Учитывая схему комбинирования (рис. 6) и таблицу комбинирования (ниже), в соответствии с теоремой 3 получаем vn(x) = arg min {|/(*)| + *[*.(*)]} и Л>(*) = '/(*)•

Таблица 1. Таблица комбинирования сектора.

/ Ф) Ф) г,

1 В\Ь,г) +1

2 я, Н\а,Ь) |х,-0,5|-0,5 +1

3 Нг Н\Ь,с) +1

4 Ъ Р\а) >/(*>-I)2 + *? -1 +1

5 Рг Р\Ь) V*,2+*2 -1 -1

6 Р\с) -1 +1

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

В частности, для отрезка прямой, соединяющего точки а(-1,0) и ¿(1,0) при Л(дг) = |х1| + |л:2|-1 верно /*(*) = /Ш'(х IЬ)л Кх) ^ /А* I а'Ь) ■

„ _ _ , Если же рассмотреть семейство окружностей

Рас. 7. Линии уровня функции г

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

в (-1,0) и 6(1,0), а угол между касательной к дуге окружности аЬ в точке а и отрезком аЬ равен в, то

и если Л(дг|^)=тах(1,(1-со8^)|5т^|"1|((1-|д;1))со8^+л:28т^ + |(1-|д:1|)5т^+х2со8^|, то функция расстояния для дуги аЬ окружности ЗВ2(#) представима в виде (рис. 7):

Шв)=л /А* \«'ь)-

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

/(х)=^г[дс) + Л, же®2, где г(х) - целая рациональная функция произвольного порядка, функции расстояния исчерпываются теми, что соответствуют точке, кругу, прямой, полосе и полуплоскости.

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

Теорема 6. Для параболы дЛг(а), заданной уравнением у2 = ау\, верно

у,{х) = ^/ь + к+1/ь^И,тде b = 4"'a"2, A = 36"'«"3^(9ax:1)2+6(l-2ax2)' .

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

Теорема 7. Пусть выпуклая оболочка множества Г2 с R2, может быть заданна некоторой кривой, С2 -регулярной в точках a,beQ, причём перпендикуляры к ней в

этих точках пересекаются в с (рис. 8). Пусть г = \а - с|, и ab — отрезок линии П, ограниченный точками а и Ь. Тогда, если существует такой круг Вг{с,г), что с 8B\c,r),

Рас. 8. Линия Я V)- [к!\Лг(с/)]пП = 0 и еедВ2(с,г)пас, d едВг{с,г)пЬс,

то v(ab \ flj = v{ab \{а,А} | fij = dee, где клин dee ограничен cd и се, причём ab <t dee.

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

Пусть ficl! лежит в некоторой плоскости ПсМ!. Множество, образованное прямыми, проходящими через каждую точку £2 перпендикулярно П, называется цилиндрическим телом. Множество называется телом вращения, если оно образовано окружностями, проходящими через каждую точку О; причём окружности лежат в плоскостях, перпендикулярных некоторой прямой Л с П, и имеют центры в точках Л. В обоих случаях О. называется направляющей. Прямая Л называется осью вращения.

Теорема 8. Пусть в К2 и R3 введены декартовы системы координат и у = = ^(дс): x(a,,a2)—»j>(ij[,i7j,0). Если между i^cR2 и £22cR3 существует взаимнооднозначное соответствие: П2=#>(П1) и Clt=ip''(Cl2), то /Пг(х,,х2,хг)=^/(2(х,,х2) +х2 Также, если Е, сЦ и I2 =<р{I,), то F(S2 |П2) - цилиндрическое тело с направляющей 1Г2,)], и, если множество -разделяющее, той Хг -разделяющее

Теорема 9. Пусть к условиям теоремы 8 добавлено следующее: Q3cR5 - цилиндрическое тело с направляющей П2. Тогда /^(х^д^,*, )= /П](лпх2). Также, если S.cfl,, «13 - цилиндрическое тело с направляющей 12, то j П,) - ци-

линдрическое тело с направляющей Щ)], и, если множество 2, - разделяю-

щее, то и I, - разделяющее. К тому же, если плоскость П с К3: П || ох1х1, то £23пП -разделяющее множество.

Цилиндрическое тело с направляющей - клином называется трёхмерным клином. Вершине клина соответствует прямая, называемая осью трёхмерного клина.

Теорема 10. Пусть к условиям теоремы 8 добавлены следующие • О, с К3 - тело вращения с направляющей С2г и осью вращения ох,, а также, если х е ЗП,, то хг £ 0.

Тогда + х]При этом, если £2=<з(1,) к I, - тело

вращения с направляющей 12, то К(23|03) - тело вращения с направляющей ¡О,)]. К тому же, если 2, -разделяющее, той 23 -разделяющее; если К с К3 - трёхмерный клин с осью ох,, то 03Г>5К -разделяющее множество.

Эти теоремы обобщаются с помощью следующего утверждения.

Утверждение 1. Пусть множества П1 с К" и П2 с К" связаны преобразованием подобия р(х) с коэффициентом к как £12 = р(П,). Тогда /П1{х) = к'1

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

Теорема 11. Пусть через у,г € К3 проходит прямая Нг~ъ(у,£), и

а) если уг\\ох^, то хг =хг-уг, х}=х,-у,,

б) если уг$охх,топри р = г-у, М = ^р\ + р] . Ь = у]р* + р\ + р],

хг = М-*Ь->{М1Х1 -р,ргх, -ра>,хз -\мгу, -АЛЛ-АЛЛ]). х, = -М'1 (рЛ - р2х, - [р,уг - р.у,]).

Тогда /„»(* | у, г) = уЩТ^ ■

Полагая, что [х, - векторное произведения, можно записать /Н1-,(х\у,г) = = |г-^|"1-|[дс->', но соответствующее выражение из теоремы 11 более опти-

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

Функция расстояния для окружности определяется в следующей теореме.

Теорема 12. Пусть окружность В2'1{у,г,д,е) с центром в точке ее Ж3 проходит через точки у,г,ц е К3, (рис.9). Тогда при г^\у-е\, А = # = .у,

ki

/

Рис. 9. Окружность в пространстве.

ftiAx I у^лА=

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

Приводятся примеры записи функций расстояния и Рис. 10. Поверхности уровня ФУ1™"™ верхнего расстояния для множеств в пространстве в

функции расстояния виде таблиц и схем комбинирования. Таким образом, напри-тетраэдра. , _

мер, записывается функция расстояния тетраэдра, изображённого на рис. 10.

Четвёртая глава посвящена применению функций расстояния в задачах анализа и синтеза изображений. В начале демонстрируется пригодность функций расстояния для моделирования геометрических объектов, содержащих компоненты различной топологической размерности. Показывается, что для их визуализации достаточно в известных алгоритмах прорисовки неявно заданных поверхностей заменить условие принадлежности точки объекту с gn(x) < 0 на /п(х) £ 1/2. Проводятся сравнения вычислительных сложностей функций расстояния для комбинированных множеств и соответствующих функций принадлежности, полученных методом конструктивной твердотельной геометрии. Также сравниваются алгоритмы визуализации, использующие и не использующие тот факт, что, если /¡¡(х) = г, то int В"(лг,r)nfl = 0 и дВ"(х,г) г>Q * 0.

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

Затем рассматривается задача анализа сцен методом преобразования Хафа. Показывается, что выделение из точек сцены х^, < — 1... л, тех, что принадлежат объектам &(/>), сводится к поиску и анализу локальных максимумов функции Хафа

1/ ~ -г '"-"-'-Цр.

1 \ / "V Если в качестве функции Хафа использовать

= а в качестве £п(*|р) функцию

Ршс. П. Сцена букв. /п(дс| р), то при корректном выборе шагов дискретизации

пространства параметров модели любому изображению объекта соответствует локальный максимум функции Хафа. В диссертации приводится алгоритм преобразования Хафа, позволяющий распознавать сцены объектов, подобные приведённой на рис. 11.

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

Основные результаты

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

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

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

3. Предложена методика записи функций кратчайшего и верхнего расстояния для двумерных и трёхмерных тел, ограниченных квадратичными линиями и поверхностями.

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

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

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

Список публикаций по теме работы

1. Семерий О.С. Метод максимальных площадей для выделения движущихся объектов по серии изображений // Сб. трудов ВНТК «Компьютерные технологии в инженерной и управленческой деятельности-98». - Таганрог: ТРТУ, 1999. - С. 23-31.

2. Семерий О.С., Бутенков С. А. Оптимизация процесса распознавания изображений в параллельных системах // Сб. тезисов докладов Междун конф. «Интеллектуальные многопроцессорные системы-99». - Таганрог: ТРТУ, 1999. - С. 92-93.

3. Бутенков С.А., Семерий О.С. Оптимизационный метод распознавания изображений с помощью аналитических моделей в параллельных системах // Сб. трудов Междун. конф. «Интеллект, многопроц. системы-99». - Таганрог: ТРТУ, 1999. - С. 190-196.

4. Семерий О.С. Математическое моделирование в техническом зрении // Сб. докладов Всероссийской конференции «Измерения, автоматизация и моделирование в промышленности и научных исследованиях-2000». - Бийск: АлтГТУ, 2000. - С. 26-28.

5. Бутенков С.А., Бачило С.А., Семерий О.С. Динамические модели краёв в задачах обработки изображений // В сб. трудов Межд. научной конференции «Математические методы в технике и технологиях». - С.-Петербург: СПбГТИ, 2000.-Т.4.-С. 26-28.

6. Бутенков С.А., Семерий О.С. Аналитические модели в задачах компьютерной графики // Сб. тезисов докладов Международной научной конференции «Искусственный интеллект-2000». - Таганрог: ТРТУ, 2000. - С. 168-170.

7. Бутенков С.А., Семерий О.С. Аналитический подход к решению задач компьютерной графики // Искусственный интеллект. - Донецк: ИЛИИ, 2000. - №3. - С. 428-437.

.8. Бутенков С.А., Семерий О.С. Аналитические методы решения основных задач компьютерной графики // Обозрение прикладной и промышленной математики. - М.: ТВП, 2000. - Т.7, Вып.2. - С. 325-326.

9. Семерий О.С. Аналитические методы в задачах геометрического моделирования // Сб. тезисов докладов ВНТК студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления». - Таганрог: ТРТУ, 2000. - С. 104-105.

10. Семерий О.С. Методы динамической фильтрации изображений // Сб. тезисов докладов ВНТК студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления». - Таганрог: ТРТУ, 2000. - С. 120-121.

11. Семерий О.С. Самоорганизующийся метод идентификации состояния экологических систем // Сб. тезисов докладов ВНТК студентов и аспирантов «Технич. кибернетика, радиоэлектроника и системы управления». - Таганрог: ТРТУ, 2000. - С. 385-386.

12. Бутенков С.А., Семерий О.С. Аналитические модели и их нечеткие обобщения в задачах распознавания изображений // Сб. трудов 7-ой Национальной конференции по искусственному интеллекту с международным участием. - Переславль-Залесский: Физматлит, 2000. - Т.2. - С. 508-516.

13.ИтенбергИ.И., Бутенков С.А., Семерий О.С., Бачило С.А. Аналитический метод представления геометрической информации // Сб. докладов 3-ой Междун. научн. конф. «Цифровая обработка сигналов и её применение». - М., 2000. - Т.2. - С. 57-60.

14. Itenberg, I., Butenkov, S., Semery, О. and Bachilo, S. Analytical Method of the Geometrical Information Representation // Proc. of 3rd Int. Conf. on Digital Signal Processing and Its Applications (DSPA-2000). - Moscow, 2000. - Vol.2. - pp. 60-62.

15.Karkishchenko, A., Butenkov, S. and Semery, O. Analytical Parameterized Models in Computer Vision // Proc. of 6th Int. Conf. on Control, Robotics and Vision (ICARCV-

2000). - Singapore, 2000.

16. Butenkov, S., Semery, O., Karkishchenko, A. Analytical Approach for Recognition of Arbitrary Primitives // Proc. of the 4th IAPR Int. Workshop on Graphics Recognition (GREC

2001). - Kingston, Canada, 2001.

{ #'85 111544

17.Бутенков С.А., Семерий О.С. Интелл. подход в задаче распознавания симе. _ _ Т: ста // Сб. докладов Научн. сессии МИФИ-2001- М.: МИФИ, 2001.- Т.З.- С. 160-161.

18. Семерий О.С., БугенковС.А. Метод моделирования и распознавания симметрии в интеллектуальных системах // Сб. докладов Научной сессии МИФИ-2001. - М.: МИФИ, 2001.-Т.З.-С. 162-163.

19. Колесников A.A., Бутенков С.А., Семерий О.С. Синерг. методы в классификации состояния экологич. систем // Известия ТРТУ. - Таганрог: ТРТУ, 2001.- №2.- С. 52-56.

20. Семерий О.С., Бутенков С.А. Геометрич. моделирование с учётом симметрии // Обозрение прикл. и промьпнл. математики. - М.: ТВП, 2001. - Т.8, Вып.1. - С. 319-320.

21. Бутенков С.А., Семерий О.С. Применение нечётких операторов в задачах агрегирования геометрической информации // Сб. трудов конгресса «Искусственный интел' лектв XXI веке» (ICAI'2001). -М., Физматлит, 2001. -Т.1. - С. 167-175.

22. Семерий О.С. Разработка математического метода геометрического моделирования // Сб. тезисов докладов 10-й Всероссийской конференции молодых учёных «Математическое моделирование в естественных науках». - Пермь: ПГТУ, 2001. - С. 76.

23. Семерий О.С., Бутенков С.А. Использование R-Моделей для решения задач обработки геометрич. информации в многопроц. системах // Сб. тезисов докладов Меж-дун. конф. «Интелл. многопроц. системы-2001».- Таганрог: ТРТУ, 2001- С. 109-192.

24. Семерий О.С. Представление геометрической информации в задачах обнаружения столкновений II Сб. трудов Научной молодёжной школы «Интеллектуальные робо-тотехнические системы-2001». - Таганрог: ТРТУ, 2001. - С. 94-96.

25. Каркищенко А.Н., Семерий О.С. Анализ сцен с использованием R-Моделей // Обозрение прикл. и промышл. математики. - М.:ТВП, 2001. - Т.8, Вып.2. - С. 680-681.

26. Семерий О.С. Распознавание геометрических объектов с помощью функций расстояния // Сб. трудов Международной конференции «Распознавание образов и анализ изображений». - В.Новгород, 2002. - С. 486-490.

27. Семерий О.С., Бутенков С.А. Оптимальный синергетический регулятор для управления манёврами ИСЗ на круговых орбитах // Известия ТРТУ. - Таганрог: ТРТУ, 2004. - №4, книга 2. - С. 154-160.

28.Броневич А.Г., Семерий О.С. Яркостная сегментация изображений на основе меры информативности // Pattern Recognition and Image Analysis - M.: Наука- №4, Вып. 14.

В работах, опубликованных в соавторстве, лично автору принадлежат следующие результаты: в [2, 3] теоретическое и практическое исследование эффективности применения функций расстояния в задачах оценки параметров моделей, в [5] практическая реализация метода динамической фильтрации и анализ его эффективности, в [6, 7, 8] теоретическое и практическое исследование метода решения задач компьютерной графики путём конструирования и визуализации соответствующих функций расстояния, в [12, 21] анализ применимости функций расстояния для построения функций принадлежности нечётких множеств, в [13, 14, 15, 23] разработка и исследование методов конструирования функций расстояния, в [16, 17] разработка принципов распознавания изображений с помощью функций расстояния, в [18, 20] создание эффективных методик записи функций расстояния для симметричных объектов, в [19] разработка и реализация методов распознавания изображений на основе синергетических принципов, в [25] разработка метода анализа изображений с помощью функций расстояния и исследование его эффективности, в [27] расчёт соответствующего регулятора и моделирование его поведения, в [28] разработка принципов и методов сегментации изображений с использованием функций расстояния.

Типография ТРТУ, ГСП 17А, Таганрог, ул. Энгельса, 1. Заказ № 427, Тираж 100 экз.

Глава 1. Исследование функций расстояния в n-мерном пространстве

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

1.2. Основные понятия и определения.

1.3. Множества Вороного.

1.4. Исследование конструктивных операций.

1.5. Беззнаковые функции расстояния для комбинированных множеств

1.6. Знаковые функции расстояния для комбинированных множеств.

1.7. Дифференциальные свойства функций расстояния.

1.8. Функции верхнего расстояния.

1.9. Примеры функций расстояния в n-мерном пространстве.

1.10. Выводы.

Глава 2. Построение функций расстояния для множеств на плоскосгии

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

2.2. Функции расстояния для комбинированных множеств на плоскости.

2.3. Алгебраические функции расстояния.

2.4. Функции расстояния для кривых второго порядка.

2.5. Численно-аналитические функции расстояния.

2.6. Функции верхнего расстояния на плоскости.

2.7. Выводы.

Глава 3. Построение функций расстояния для множеств в пространстве

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

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

3.3. Функции расстояния для плоских линий в пространстве.

3.4. Функции расстояния для поверхностей.

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

3.6. Функции расстояния для комбинированных множеств в пространстве

3.7. Функции верхнего расстояния в пространстве.

3.8. Выводы.

Глава 4. Применение функций расстояния в задачах анализа и синтеза изображений

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

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

4.3. Распознавание изображений с помощью функций расстояния.

4.4. Обобщение преобразования Хафа.

4.5. Применение функций расстояния в задачах робототехники.

4.6. Выводы.

Обработка графической информации1 является одной из основных областей деятельности практически любой компьютерной системы . Это обусловлено тем, что, во-первых, представление информации в графическом виде позволяет организовать эффективное человеко-машинное взаимодействие3 [1], так как такого рода информация значительно проще воспринимается людьми [2], во-вторых, при решении достаточно сложных задач автономная компьютерная система выступает в качестве замены человека и поэтому обычно получает и обрабатывает визуальную информацию. К таким интеллектуальным [3] задачам относятся анализ аэрофотоснимков [4], визуальный контроль трафика движения автотранспорта [5, 6], навигация мобильных роботов [4] и многие другие [7, 8].

Устройства ввода графической информации в компьютерную систему [9], такие как сканеры, фото и видеокамеры, а также устройства вывода, такие как дисплеи и принтеры, обуславливают форму представления графической информации в вид изображений [10]. С математической точки зрения, изображение является матрицей, элементы которой в двумерном случае называются пикселями, а в трёхмерном4 — вокселями. В простейшем случае пиксель принимает значение «1», если он соответствует точке изображённого объекта, и значение «0», если не соответствует. Эти изображения называются бинарными [10]. Существуют и другие виды изображений [11], например, полутоновые, в которых пиксель принимает значения, определяющие яркость соответствующей точки изображённого объекта. Отсюда, имеет смысл

1 Здесь под графической понимается информация, представленная в виде фотографий, рисунков и диаграмм.

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

3 Обратим внимание на то, что практически все современные операционные системы имеют графический интерфейс [12].

4 Примерами устройств ввода трёхмерных изображений являются томографические, магнитно-резонансные и ультразвуковые медицинские сканеры [4]. говорить о геометрической информации, представленной бинарным изображением, так как оно определяет только форму и положение соответствующего объекта5, который в этом случае называется геометрическим объектом6 [13].

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

Существуют исследования [14, 15], посвящённые теории представления геометрической информации, в соответствии с которыми, метод представления информации сопоставляет каждому допустимому геометрическому объекту его модель. Модель - это выражение, составленное из символов некоторого алфавита в соответствии с определёнными синтаксическими правилами. Метод представления информации должен обладать свойствами: а) полноты, т.е. моделировать все интересуемые виды геометрических объектов; б) адекватности - любая модель должна соответствовать некоторому реальному геометрическому объекту; в) однозначности - любой модели должен соответствовать единственный объект; г) уникальности — любому допустимому объекту должна соответствовать единственная модель;

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

4 С математической точки зрения геометрический объект может быть определён как множество точек в евклидовом пространстве, поэтому в диссертационной работе не делается различий между понятиями «геометрический объект» и «множество точек». д) краткости - модель должна представлять собой достаточно простое выражение; е) эффективности - должны существовать эффективные алгоритмы создания, обработки и визуализации моделей.

Наиболее известными методами представления геометрической информации являются [15, 16]: а) полигональное представление — представление в виде аппроксимации поверхности геометрического объекта многогранниками; б) конструктивная геометрия, создающая геометрические объекты из примитивов (кубов, сфер, конусов и т.п.) с помощью теоретико-множественных операций, таких как пересечение, объединение и вычитание; в) краевое представление, определяющее топологию объекта путём задания его клеточного разбиения [17].

Полигональное представление отличается наличием крайне эффектив ных с вычислительной точки зрения алгоритмов визуализации , но обладает и большим количеством недостатков: а) применяется для описания только трёхмерных объектов; б) форма объектов определяется приближённо9 [18]; в) практически не приспособлено для описания объектов, изменяющих свою форму; г) сложно решается задача обнаружения столкновений [19] при моделировании динамических сцен; д) конструирование моделей непосредственно в полигональном виде крайне неудобно.

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

8Немаловажным является и тот факт, что большинство современных видеоадаптеров на аппаратном уровне решает часть проблем, связанных с визуализацией полигональных моделей [20].

9 Приближённость описания объектов эффективно маскируется различными методами наложения текстур и теней [21].

Конструктивная геометрия и краевое представление отличаются достаточным удобством при моделировании, но имеют не очень эффективные методы визуализации [15].

В виду того, что каждый из методов имеет определённые недостатки, существует большое количество алгоритмов преобразования конструктивных моделей в краевые [22, 23, 24, 25] и наоборот [22], а также тех и других в краевое представление [26].

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

27] и объектов нерегулярной формы10, таких как горы, шерсть, камни, ракушки и т.п. В числе этих методов — суперквадрики [18], мягкие объекты

28], капельные объекты [29], обобщённые цилиндры [30] и свёрточные поверхности [31]. Основные требования, предъявляемые к таким методам представления информации, - это максимальная полнота и эффективность визуализации [32].

Обратим внимание на то, что все эти методы определяют геометрические объекты с помощью неявно заданных функций [33], а именно функций, принимающих отрицательные значения внутри описываемого геометрического объекта и положительные - снаружи. В результате существует большое количество работ [32], посвящённых разработке эффективных методов визуализации неявно заданных функций, как с учётом особенностей конкретных моделей, так и без их учёта. Метод преобразования неявных функций в полигональное представление [26] в данном случае практически не применим из-за нерегулярной формы описываемых объектов, и фактически единственным методом визуализации таких неявно заданных функций является метод трассировка лучей [32], заключающийся в определении координат

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

Метод трассировки лучей позволяет визуализировать с заданной точностью сцены, содержащие полупрозрачные объекты, в условиях множественного отражения света. Обратной стороной таких возможностей является то, что алгоритмы трассировки лучей являются одними из самых неэффективных с вычислительной точки зрения, если не используются параллельные вычисления. Практически все усовершенствования метода трассировки лучей применительно к произвольным неявным функциям заключаются в оценке производных визуализируемой функции. На этом принципе основаны такие известные методы как Липшицев [34] и интервальный [35].

Наиболее эффективным методом можно признать такое обобщение липшицева метода как трассировка сфер Джона Харта [36]. Он использует понятие так называемой знаковой функции расстояния, т.е. функции, определяющей евклидово расстояние от данной точки пространства до ближайшей точки на описываемом ею объекте. Но, так как построение таких функций для сложных объектов - нетривиальная задача, то Джон Харт использовал понятие ограничивающей знаковой функции расстояния, возвращающей значения меньшие либо равные реальному расстоянию до объекта. Так как в алгоритме трассировки сфер функции расстояния рассчитываются преимущественно в точках вне объектов, то операции Ричи [37], используемые при формировании конструктивных моделей, позволяют описывать объекты с помощью ограничивающих функций расстояния. Как доказано в работе [36], сходимость метода трассировки сфер линейная, а в лучшем случае — квадратичная. Скорость визуализации достаточно сильно зависит от точности оценки функции расстояния. Более того, им было показано, что с помощью этого метода можно избавиться такого от такого неприятного эффекта трассировки лучей, как появление зубчатости на гранях изображённых геометрических объектов.

Кроме того, что моделирование с помощью функций расстояния позволяет разрабатывать эффективные алгоритмы визуализации, такие модели обладают ещё одной замечательной особенностью. В отличие от подавляющего большинства методов представления геометрической информации11, функции расстояния способны корректно моделировать геометрические объекты, содержащие компоненты различной размерности [38], при этом существуют алгоритмы визуализации таких объектов [39], основанные на методе трассировки лучей.

Следует отметить, что функции расстояния не являются принципиально новым математическим объектом. В частности, понятие функций расстояния используется при построении свёрточных поверхностей [31] и обобщённых цилиндров [30].

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

1 7

1. Выделение остова [40], часто применяемое при распознавании абстрактных двумерных объектов, таких как буквы, цифры и т.п.

2. Построение дистантных изображений13 [41], использующихся, например, при сравнении изображений.

Дистантные изображения формируются либо с помощью эвристических алгоритмов фильтрации изображений [41], либо путём решения так называемого уравнения эйконала [42, 43], которое является дифференциальным уравнением в частных производных. Решением уравнения эйконала и является функция расстояния. Данные методы весьма эффективны, но не решают проблему построения исходного бинарного изображения, задающего начальные условия для уравнения эйконала или алгоритма фильтрации. Эта про

11 Все рассмотренные ранее методы представления геометрической информации позволяют корректно моделировать только так называемые твёрдые тела [ 14], одной из особенностей которых является то, что это п-мерные [44] тела в n-мерном пространстве, и они не содержат элементов размерности меньше п.

12 Выделение остова заключается в утончении изображённых объектов.

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

Дистантные изображения являются мощным инструментом для сравнения различных изображений [41], построения непрерывных трансформаций одного изображения в другое [45], выделения остова [40] и построения эквидистантных поверхностей [46]. Дистантные изображения преимущественно используются при распознавании изображений.

Если же рассмотреть собственно задачу распознавания изображений, то обнаруживается следующий факт. Существует стандартный подход к определению положения и размеров изображённого объекта по его параметризованной модели - метод оценки параметров модели со среднеквадратичным критерием [47]. Как было показано в исследовании [47], если параметризованная модель задаётся функцией, фактически являющейся функцией расстояния, то параметры модели будут определены наиболее быстро и точно.

В присутствии сильного шума на изображениях применяются робаст-ные методы оценки параметров, например, метод М-оценок [47]. Анализ используемого в нём критерия близости [47] также показывает, что для него желательно описание объекта в виде функции расстояния. Существуют и конкретные работы, посвящённые распознаванию геометрических объектов по их функциям расстояния [48].

Таким образом, задача определения функций расстояния для различных геометрических объектов является крайне актуальной. Рассмотрим публикации, посвящённые выводу функций расстояния для конкретных геометрических объектов. Во-первых, это работа Дж. Харта о методе трассировки сфер [36], где были получены приближённые функции расстояния для различных тел и их объединений. Во-вторых, это работа В.Л. Рвачёва [49], по-свящённая теории R-функций. В ней автором было введено понятие беззнаковой функции расстояния и исследованы её свойства. Также была получена схема записи функций расстояния для фигур, представляющих собой конечное число отрезков прямых и дуг окружностей на плоскости. Им же было введено и исследовано понятие функции верхнего расстояния, определяющей евклидово расстояние от точки пространства до наиболее удалённой точки объекта. Существуют также работы, связанные с построением эвристических методов вычисления расстояний до многогранников [50]. И, наконец, определение расстояния до ближайшей точки на множестве является одной из основных задач вычислительной геометрии [51]. К сожалению, традиционно в качестве множеств, до которых определяется расстояние, выступают совокупности изолированных точек. При этом задача сводится к построению диаграмм Вороного, разделяющих пространство на многогранники Вороного [52], в приделах которых расстояние минимально до конкретной точки из рассматриваемого множества точек. Однако существуют работы, посвящён-ные построению диаграмм Вороного для множеств, содержащие отрезки кривых [53].

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

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

В соответствии с поставленной целью задачами диссертационного исследования являются:

1. Разработка методов построения функций расстояния для достаточно сложных двумерных и трёхмерных объектов.

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

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

4. Разработка и исследование методов распознавания с использованием функций расстояния.

5. Разработка обобщения преобразования Хафа для анализа сцен сложных объектов с использованием функций расстояния.

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

Первая глава посвящена разработке метода записи функций расстояния для множеств в R". В начале главы вводится и исследуется понятие множества Вороного, обобщающего понятие области Дирихле. Затем анализируются свойства неявных функций, формируемых с помощью операций min(jc,j>) и max(jc,j>). Определяются условия, при которых эти функции являются функциями расстояния. Вводятся понятия комбинированного и разделяющего множеств. В результате разрабатываются оригинальные схемы записи знаковых и беззнаковых функций расстояния для объединения и пересечения множеств. Также формулируются условия для записи функций расстояния в виде алгебраических выражений, использующих конструктивные операции Ричи. Далее проводится анализ дифференциальных свойств функций расстояния. Выводятся выражения для вычисления частных производных различных порядков от функций расстояния, соответствующих комбинированным множествам. Исследуются свойства функций верхнего расстояния, разрабатываются методики их вычисления. В заключение выводятся формулы для вычисления знаковых и беззнаковых функций расстояния, соответствующих множествам изолированных точек, шарам, сферам, плоскостям и полупространствам в пространстве R".

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

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

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

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

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

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

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

3. Методика записи функций кратчайшего и верхнего расстояния для класса двумерных и трёхмерных множеств, ограниченных квадратичными линиями и поверхностями.

4. Обобщение преобразования Хафа для анализа сцен сложных объектов с использованием функций расстояния.

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

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

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

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

Апробация работы. Основные положения и результаты работы представлялись и обсуждались на Всероссийской научно-технической конференции с международным участием «Компьютерные технологии в инженерной и управленческой деятельности», Таганрог, 6-8 октября 1998 г.; Международной научно-технической конференции «Интеллектуальные многопроцессорные системы» (ИМС-99), Таганрог, Россия, 1-5 сентября 1999 г.; 1-ой Всероссийской научно-технической конференции «Измерения, автоматизация и моделирование в промышленности и научных исследованиях» (ИАМП-2000), Бийск, 8-9 июня 2000 г.; Международной научной конференции «Искусственный интеллект - 2000» (ИИ-2000), п. Кацивели, Крым, Украина, 11-16 сентября 2000 г.; 5-ой Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (КРЭС-2000), Таганрог, 12-13 октября 2000 г.; 1-ом Всероссийском симпозиуме по прикладной и промышленной математике (осенняя сессия), Сочи, 1-6 октября 2000 г.; 7-ой Национальной конференции по искусственному интеллекту с международным участием (КИИ-2000), Переславль-Залесский, 24-27 октября 2000 г.; 3-ей Международной конференции «Цифровая обработка сигналов и её применение» Москва, Россия, 29 ноября-1 декабря 2000 г.; 6-ой Международной конференции по управлению, автоматизации, робототехнике и машинному зрению, Сингапур, 5-8 декабря 2000 г.; Научной сессии МИФИ-2001, Москва, 22-26 января 2001 г; 6-ой Международной конференции «Распознавание образов и анализ изображений», В.Новгород, 21-26 октября 2002, а также на ежегодных конференциях профессорско-преподавательского состава Таганрогского радиотехнического университета (2001,2002,2003,2004 г).

Публикации. Опубликовано 32 работы, из них 28 по теме диссертации.

Структура и объём диссертации. Диссертационная работа состоит из введения, четырёх тематических глав, заключения, списка литературы и приложения. Объём диссертации - 140 страниц. Текст диссертации содержит 62 рисунка и 19 таблиц. Список литературы изложен на 8 страницах и включает 95 наименований.

4.6. Выводы

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

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

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

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

Заключение

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

1. Разработаны методы построения знаковых и беззнаковых функций расстояния, а также функций верхнего расстояния для комбинированных множеств в n-мерном пространстве, для чего были введены и исследованы понятия множества Вороного и разделяющего множества.

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

3. Предложена методика записи функций кратчайшего и верхнего расстояния для класса двумерных и трёхмерных множеств, ограниченных квадратичными линиями и поверхностями.

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

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

6. Определены области Вороного для эллипсов, лежащих на поверхности цилиндров, полуконусов и полупространств.

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

1. Грачёв Н.Н. Психология инженерного труда. - М.: Высш. шк., 1998.

2. ХорнБ., Минский М., Сираи И. и др. Психология машинного зрения. -М.: Мир, 1978.

3. ЧернухинЮ.В. Искусственный интеллект и нейрокомпьютеры. — Таганрог: ТРТУ, 1997.

4. Куафе Ф. Взаимодействие робота с внешней средой. — М.: Мир, 1985.

5. BeymerD., McLauchlan Ph., et al. A real-time computer vision system for measuring traffic parameters // Proc. of CVPR'1997. 1997. - pp.495-501.

6. Koller D., Daniilidis K., et al. Model-based object tracking in traffic scenes // Proc. ofECCV'1992.- 1992. -pp.437-452.

7. Верхаген К., Дёйн P., Грун Ф. и др. Распознавание образов: состояние и перспективы. М.: Радио и связь, 1985.

8. Горелик A.JL, Гуревич И.Б., Скрипкин В.А. Современное состояние проблемы распознавания: Некоторые аспекты. М.: Радио и связь, 1986.

9. Михайленко В.Е., Кислоокий В.Н., ЛященкоА.А. и др. Геометрическое моделирование и машинная графика в САПР. К.: Выща шк., 1991.

10. Ю.Павлидис Т. Алгоритмы машинной графики и обработки изображений. -М.: Радио и связь, 1986.11 .Gonzalez R.C. and Woods R.E. Digital image processing. MA.: Addison-Wesley, 1992.12,Олифер В.Г., Олифер Н.А. Сетевые операционные системы. СПб.: Питер, 2002.

11. Васюков А.Н., Комаров Ю.А., Янович И.А. Логико-алгебраические методы решения геометрических задач и разработка программного обеспечения САПР. К.: Наук, думка, 1991.

12. Requicha A.A.G. Representation for rigid solids: Theory, Methods, and Systems // ACM Computing Surveys. 1980. - Vol.12, N.4. - pp. 437-464.

13. Hoffmann C.M. Geometric and solid modeling. San Mateo, California: Morgan Kaufmann, 1989.

14. MantylaM. An introduction to solid modeling. Rockville, Maryland: Computer Science Press, 1988.

15. Борисович Ю.Г. и др. Введение в топологию. М.: Наука, Физматлит, 1995.

16. Вяткин С.И., Долговесов Б.С., Есин А.В. и др. Геометрическое моделирование и визуализация функционально заданных объектов // Автометрия. -1999.-№6.-С. 84-92.

17. LinM. and Gottschalk S. Collision detection between geometric models: A survey // Proc. of IMA Conference on Mathematics of Surfaces, 1998.

18. Sung K. Area sampling buffer: Tracing rays with z-buffer hardware // Comput. Graph. Forum 11(3):299-310, 1992.

19. Ikedo Т., Ma J. An advanced graphics chip with bump-mapped Phong shading // Proc. of CGI'1997,1997.

20. Requicha A.A.G. and Voelcker H.B. Boolean operations in solid modeling: boundary evaluation and merging algorithms // Proc. of the IEEE, 73(1), 1985.

21. Miller J. and Goldman R. Combining algebraic rigor with geometric robustness for the detection and calculation of conic section in the intersection of two quadric surfaces // Proc. of ACM Solid Modeling, pp.221-233,1991.

22. Keyser J., Krishnan S., and Manosha D. Efficient and accurate b-rep generation of low degree sculptured solids using exact arithmetic: I representation // Computer Aided Geometric Design, 16(9):841-859, 1999.

23. Keyser J., Krishnan S., and Manosha D. Efficient and accurate b-rep generation of low degree sculptured solids using exact arithmetic: II computation // Computer Aided Geometric Design, 16(9):861-882,1999.

24. Bloomenthal J. Polygonization of implicit surfaces // CAD, 5(4):341-355, 1988.

25. Woodwark J.R. Blends in geometric modeling // In R.R. Martin, ed., The Mathematics of Surface II. Clarendon Press, 1997. - pp.255-297.

26. Wyvill G., McPheeters C., and Wyvill B. Data structure for soft objects // Visual Computer 2(4):227-234, 1986.

27. Wyvill В., Guy A., and Galin E. The BlobTree: Warping, blending and Boolean operations in an implicit surface model system // Computer Graphic Forum, 18(2):149-158,1999.

28. Agin CG.J. and Binford Т.О. Computer description of curved objects // IEEE Trans, on Computers, 24(4):439-449,1976.31 .Bloomenthal J. and Shoemake K. Convolution surfaces // Computer Graphics, 25(4):251-256,1991.

29. Hart J.C. Ray tracing implicit surfaces // WSU technical report EECS-93-014, 1993.

30. Bloomenthal J. Introduction to implicit surfaces. Morgan Kaufmann, 1997.

31. Karla D. and Barr A.H. Guaranteed ray intersections with implicit surfaces // Computer Graphics, 23(3):297-306,1989.

32. Snyder J.M. Interval analysis for computer graphics 7/ Computer Graphics, 26(2):121-130,1992.

33. Hart J.C. Sphere tracing: a geometric method for the antialiased ray tracing of implicit surfaces // The Visual Computer, 12(10):527-545, 1996.

34. Ricci D. A constructive geometry for computer graphics // Computer Journal, 1973.

35. Gomes J. and Faugeras O. Representing and evolution smooth manifolds of arbitrary dimension embedded in Rn as the intersection of n hypersurfaces: The vector distance functions // Technical Report 4012, INRIA, 2000.

36. Бутенков C.A., Семерий O.C. Аналитический подход к решению задач компьютерной графики // Искусственный интеллект. Донецк: ИЛИИ, 2000.-№3.-С. 428-437.

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

38. Sethian J.A. Level set methods and fast matching methods evolving interface in computational geometry, fluid mechanics, computer vision, and material science. Cambridge University Press, 1999.

39. Болтянский В.Г., Ефремович B.A. Наглядная топология. M.: Наука, 1983.

40. Breen D. and Whitaker R. A level-set approach for the metamorphosis of solid models // IEEE Trans, on Visualization and Computer Graphics, 7(2): 173-192, 2001.

41. Barnhill R.E., Frost T.M., and Kersey S.N. Self-intersection and offset surfaces // In R.E. Barnhill, ed., Geometry Processing for Design and Manufacture, SLAM. —1992. pp.35-44.

42. Zhang Z. Parameter estimation techniques: a tutorial with application to conic fitting // Int. Journal of Image and Vision Computing, 15(l):59-76, 1997.

43. Сироджа И.Б. Алгоритм распознавания геометрических образов. // Известия АН СССР, Техническая кибернетика. 1967. - №5. - С. 136-144.

44. Рвачёв B.JI. Теория R-функций и некоторые её приложения. Киев: Наук, думка, 1982.

45. Huang J., LiY., et al. A complete distance field representation // Proc. 12th IEEE Visualisation. 2001. - pp.247-254.51 .Препарата Ф., Шеймос M. Вычислительная геометрия: Введение. — М.: Мир, 1989.

46. Aurenhammer F. and Klein R. Voronoi diagrams // In J. Sack and G. Urrutia, editors, Handbook of Computational Geometry. Elsevier Science Publishing, 2000. -pp 201-290.

47. Yap C.K. An 0(n log n) algorithm for the Voronoi diagram of set of simple curve segments // Discrete Comput. Geom., 2:365-393, 1987.

48. Breen D., Mauch S., and Whitaker R. 3D scan conversion of CSG models into distance, closest-point and color volumes // In M. Chen, A.E. Kaufman,

49. R. Yagel (eds.), Volume Graphics. London: Springer, 2000. - Chapter 8. -pp.135-158.

50. SiggC., PeikertR., and Gross M. Signed distance transform using graphics hardware // IEEE Visualization 2003. 2003. - pp.83-90.

51. Sethian J.A. A fast marching level set method for monotonically advancing fronts // Proc. Nat. Acad. Sci. 1996. - Vol. 94. - pp.1591-1595.

52. Mauch S. A fast algorithm for computing the closest point and distance transform // Technical report, Applied and computational mathematics, California Institute of technology. 2000.

53. Hoff K., Culver T., et al. Fast computation of generalized Voronoi diagrams using graphic hardware // SIGGRAPH 99. 1999. - pp.277-285.

54. Семерий O.C. Распознавание геометрических объектов с помощью функций расстояния // Сб. трудов Международной конференции «Распознавание образов и анализ изображений» (РОАИ-6-2002). — В.Новгород, 2002. -С. 486-490.

55. Семерий О.С. Математическое моделирование в техническом зрении // Сб. докладов Всероссийской конференции «Измерения, автоматизация и моделирование в промышленности и научных исследованиях-2000». -Бийск: АлтГТУ, 2000. С. 26-28.

56. Семерий О.С. Разработка математического метода геометрического моделирования // Сб. тезисов докладов 10-й Всероссийской конференции молодых учёных «Математическое моделирование в естественных науках». Пермь: ПГТУ, 2001. - С. 76.

57. Итенберг И.И., Бутенков С.А., Семерий О.С., Бачило С.А. Аналитический метод представления геометрической информации // Сб. докладов 3-ой

58. Семерий O.C., Бутенков C.A. Метод моделирования и распознавания симметрии в интеллектуальных системах // Сб. докладов Научной сессии МИФИ-2001. М.: МИФИ, 2001. - Т.З. - С. 162-163.

59. Семерий О.С., Бутенков С.А. Геометрическое моделирование с учётом симметрии // Обозрение прикладной и промышленной математики. М.: ТВП, 2001. - Т.8, Вып.1. - С. 319-320.

60. Бутенков С.А., Семерий О.С. Применение нечётких операторов в задачах агрегирования геометрической информации // Сб. трудов конгресса «Искусственный интеллект в XXI веке» (1САГ2001). — М., Физматлит, 2001. -Т.1.-С. 167-175.

61. Семерий О.С. Представление геометрической информации в задачах обнаружения столкновений // Сб. трудов Научной молодёжной школы «Интеллектуальные робототехнические системы-2001». Таганрог: ТРТУ, 2001.-С. 94-96.

62. Бутенков С.А., Семерий О.С. Аналитические модели в задачах компьютерной графики // Сб. тезисов докладов Международной научной конференции «Искусственный интеллект-2000». Таганрог: ТРТУ, 2000. -С. 168-170.

63. Бутенков С.А., Семерий О.С. Аналитические методы решения основных задач компьютерной графики // Обозрение прикладной и промышленной математики. М.: ТВП, 2000. - Т.7, Вып.2. - С. 325-326.

64. Семерий О.С. Метод максимальных площадей для выделения движущихся объектов по серии изображений // Сб. трудов ВНТК «Компьютерные технологии в инженерной и управленческой деятельности-98». Таганрог: ТРТУ, 1999.-С. 23-31.

65. Семерий О.С., Бутенков С.А. Оптимизация процесса распознавания изображений в параллельных системах // Сб. тезисов докладов Междун. конф. «Интеллектуальные многопроцессорные системы-99». — Таганрог: ТРТУ, 1999.-С. 92-93.

66. Бутенков С.А., Семерий О.С. Оптимизационный метод распознавания изображений с помощью аналитических моделей в параллельных системах // Сб. трудов Междун. конф. «Интеллектуальные многопроцессорные системы-99». Таганрог: ТРТУ, 1999.-С. 190-196.

67. Разработка методов распознавания изображений ограниченного класса сцен для задачи «Автопоиск»: Отчет о НИР (заключит.) / НКБ ВС; Руководитель А.Н. Каркищенко; А.Г. Броневич, С.А. Бутенков, О.С. Семерий и др. Таганрог, 1999. - 200 с.

68. Бутенков С.А., Бачило С.А., Семерий О.С. Динамические модели краёв в задачах обработки изображений // В сб. трудов Межд. научной конференции «Математические методы в технике и технологиях». С.-Петербург: СПбГТИ, 2000. - Т.4. - С. 26-28.

69. Семерий О.С. Методы динамической фильтрации изображений // Сб. тезисов докладов V Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (КРЭС-2000). Таганрог: ТРТУ, 2000. - С. 120-121.

70. Karkishchenko, A., Butenkov, S. and Semery, О. Analytical Parameterized Models in Computer Vision // Proc. of 6th Int. Conf. on Control, Robotics and Vision (ICARCV-2000). Singapore, 2000.

71. Разработка методов распознавания изображений ограниченного класса сцен для задачи «Автопоиск»: Отчет о НИР (итоговый) / НКБ ВС; Руководитель А.Н. Каркищенко; А.Г. Броневич, С.А. Бутенков, О.С. Семерий и др. Таганрог, 2000. - 122 с.

72. Butenkov, S., Semery, О., Karkishchenko, A. Analytical Approach for Recognition of Arbitrary Primitives // Proc. of the Fourth LAPR Int. Workshop on Graphics Recognition (GREC 2001). Kingston, Canada, 2001.

73. Бутенков C.A., Семерий О.С. Интеллектуальный подход в задаче распознавания символов текста // Сб. докладов Научной сессии МИФИ-2001. — М.г МИФИ, 2001.-Т.З.-С. 160-161.

74. Колесников А.А., Бутенков С.А., Семерий О.С. Синергетические методы в классификации состояния экологических систем // Известия ТРТУ. Таганрог: ТРТУ, 2001. - №2. - С. 52-56.

75. Каркищенко А.Н., Семерий О.С. Анализ сцен с использованием R-Моделей // Обозрение прикладной и промышленной математики. М.: ТВП, 2001. - Т.8, Вып.2. - С. 680-681.

76. Семерий О.С., Бутенков С.А. Оптимальный синергетический регулятор для управления манёврами ИСЗ на круговых орбитах // Известия ТРТУ. — Таганрог: ТРТУ, 2004. №4, книга 2. - С. 154-160.

77. Броневич А.Г., Семерий О.С. Яркостная сегментация изображений на основе меры информативности // Pattern Recognition and Image Analysis. — M.: Наука. №4, Вып. 14.

78. Ефимов H.B., Розендорн Э.Р. Линейная алгебра и многомерная геометрия. -М.: Наука, 1970.

79. Моденов П.С. Аналитическая геометрия. М.: Изд. МГУ, 1969.

80. Abramowitz М. and Stegun I.A. (Eds.). Handbook of mathematical functions with formulas, graphs, and mathematical tables. New York: Dover, 1972.

81. Hough P.V.C. Method and means for recognizing complex patterns // U.S. Patent 3,069,654, 1962.

82. Колесников А.А. Синергетическая теория управления. M.: Энергоатом-издат, 1994.

83. Мирошник И.В., Говядинкин Д.С., Дроздов В.Н. Система управления транспортной тележкой. // Сб. Управление в оптических и электромеханических системах. Ленинград, 1989.