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

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

4

/Ж

Атанов Артем Викторович

МЕТОДЫ И АЛГОРИТМЫ В ЗАДАЧЕ ВОССТАНОВЛЕНИЯ ГРАНИЦ ОБЪЕКТОВ ПО ДАЛЬНОМЕТРИЧЕСКИМ ИЗОБРАЖЕНИЯМ

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

1 7 ЯНВ 2013

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

Воронеж-2012

005048444

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Воронежский государственный университет»

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

доцент Кургалин Сергей Дмитриевич

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

доцент Бугаев Юрий Владимирович, ФГБОУ ВПО «Воронежский

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

инженерных технологий»

доктор технических наук, профессор Новикова Нелля Михайловна, ФГБОУ ВПО «Воронежский

государственный университет»

Ведущая организация Федеральное государственное бюджетное

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

«Вологодский государственный

технический университет»

Защита состоится 30 января 2013 года в 15.10 на заседании диссертационного совета Д 212.038.20 при Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Воронежский государственный университет» по адресу: 394006, г. Воронеж, Университетская площадь, д. 1, ауд. 335.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Воронежский государственный университет»

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

Ученый секретарь диссертационного совета, кандидат физико-математических наук, доцент

С.А. Шабров

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

Актуальность темы

Одним из главных направлений исследований при создании систем компьютерного зрения является анализ и решение проблем, связанных с задачей реконструкции (восстановления) границ объектов. Значительный интерес к созданию компьютерных реконструкций реальных объектов объясняется широкой областью их применения: в медицине, геологии, промышленном производстве, археологии, мультимедиа-технологиях и т.д. Важнейшие части этой задачи - математическое описание границ различных фигур и представлении информации о границе в форме, удобной для изменения, хранения и визуализации.

В настоящее время существует два основных подхода к решению задачи восстановления границ. Так в работах М.Гопи, Д.Эберли, Ж.-Д. Буассона предлагаются методы, использующие триангуляцию Делоне. Несмотря на простоту реализации, эти методы не подходят для использования в системах компьютерного зрения реального времени из-за появления значительных ошибок при обработке больших массивов данных и низкой скорости работы основанных на них алгоритмов. Р.Франке, С.Ошер, Дж.Карр применили получивший большую популярность подход, определяющий положение границы объекта с помощью неявно заданных функций. Однако у разработанных на его основе методов имеются недостатки, связанные, в частности, с ограничением на количество точек, по которым восстанавливается граница. Кроме того, реализация этих методов требует больших временных затрат. Таким образом, несмотря на большое число способов реконструкции, пока ещё не существует универсального метода, позволяющего с достаточно высокой скоростью восстанавливать границы произвольных фигур. Кроме того, практически все известные методы ориентированы на работу с дальнометрическими изображениями (содержащими информацию о расстоянии от камеры до точек на поверхности рассматриваемого объекта), полученными с прецезионных ЗБ-сканеров, имеющих большую разрешающую способность. Высокая стоимость таких сканеров не позволяет использовать их для создания систем компьютерного зрения, ориентированных на массового потребителя. Однако дальнометрические изображения можно получить и с устройств с низкой разрешающей способностью, например, веб-камер, камер ноутбуков и мобильных телефонов и т.д., что может существенно снизить стоимость разрабатываемых на их базе систем компьютерного зрения. При этом следует учитывать, что информация о границе фигуры, получаемая с таких устройств, очевидно, содержит гораздо больше ошибок, чем информация с ЗБ-сканеров. Проведённый анализ показал, что в настоящее время отсутствуют методы и алгоритмы, ориентированные на реконструкцию объектов по данным, полученным с устройств с низкой разрешающей способностью.

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

Диссертационная работа выполнена на кафедре цифровых технологий Воронежского государственного университета по НИР «Разработка новых методов обработки, хранения, передачи и защиты информации в информационно-коммуникационных системах» № ГР 01200956642 (20092010 гг.) и «Разработка новых методов обработки, хранения и передачи информации в информационно-коммуникационных системах» № ГР 01201170666 (2011 г.) аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы».

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

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

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

2. Создание двухэтапного метода реконструкции, допускающего параллельную реализацию.

3. Разработка и анализ алгоритмов для предложенных моделей и методов.

4. Построение и исследование компьютерной модели реконструкции границ объектов.

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

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

Новизна работы состоит в:

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

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

3. Создании и исследовании алгоритмов для реализации двухэтапного метода реконструкции в двумерном и трёхмерном случаях.

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

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

Область исследования - содержание диссертации соответствует паспорту специальности 05.13.17 - «Теоретические основы информатики» (физико-математические науки), область исследований соответствует п.2 «Исследование информационных структур, разработка и анализ моделей информационных процессов и структур»; п.5 «Разработка и исследование моделей и алгоритмов анализа данных, обнаружения закономерностей в данных и их извлечениях разработка и исследование методов и алгоритмов анализа текста, устной речи и изображений»; п.7 «Разработка методов распознавания образов, фильтрации, распознавания и синтеза изображений, решающих правил. Моделирование формирования эмпирического знания».

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

Основные результаты, выносимые на защиту:

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

2. Алгоритмы, реализующие метод пересечений и двухэтапный метод в двумерном и трёхмерном случаях и результаты их исследования.

3. Компьютерная модель реконструкции границ двумерных и трёхмерных объектов, результаты анализа модели.

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах: IX-XII Международных научно-методических конференциях «Информатика : проблемы, методология, технологии», г.Воронеж, 2009-2012 гг.; XVII, XIX Всероссийских научно-методических конференциях «Телематика», г.Санкт-Петербург, 2010, 2012 гг.; научно-практической конференции «Связь и телекоммуникации - инновационное развитие регионов», г.Воронеж, 2011 г.; Всероссийской научной конференции "Современные проблемы математического моделирования, супервычислений и информационных технологий", г.Таганрог, 2012 г.

Публикации. По теме диссертации имеется 10 публикаций, в том числе 3 - в ведущих периодических изданиях, рекомендованных ВАК РФ.

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

Структура и объём работы. Диссертация состоит из введения, четырёх глав, заключения и списка литературы из 107 наименований. Объём диссертации составляет 111 страниц текста, содержащего 47 рисунков и 12 таблиц.

СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность темы диссертационной работы, сформулированы цели и задачи исследования, определены научная новизна и практическая значимость.

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

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

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

б

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

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

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

Общая постановка задачи: заданы точки О?/,//), у = 1,..., /V, £ М5, /у ё К, полученные в результате сканирования некоторого объекта. Требуется по данным точкам восстановить границу фигуры, т.е. построить (непрерывную) функцию Р такую, что Р(ху) = /¡, ] = 1,...,N, т.е. фактически решить задачу интерполяции.

Стандартный подход к решению задачи интерполяции состоит в нахождении функции Р в виде линейной комбинации некоторых базисных функций Вк: Р(х) = £к=1скВк(х), х е К5.

Такая формулировка, очевидно, приводит к решению системы линейных уравнений вида Ас = /, где А]к = Вк(Х]), ],к = 1, с) = (с1( .....с^)7;

/у = {/1,....,Сформулированная задача будет корректно поставленной, т.е. её решение будет существовать и будет единственным, тогда и только тогда, когда матрица А невырожденна.

Как известно, в одномерном случае решить задачу интерполяции по N произвольно взятым попарно различным точкам X] можно, используя полиномы степени не выше N — 1. Однако для случая двух и более пространственных измерений справедлива теорема Майрхубера-Кёртиса, следствием которой является тот факт, что корректную постановку задачи интерполяции для размерностей больших 1 нельзя обеспечить, задавая наперёд какое-то множество базисных функций Вк — напротив, базис должен зависеть от того, как расположены точки х1м... .,Хц.

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

п

7=1

где <p(r) - некоторая радиальная базисная функция (г > 0). Коэффициенты Лу определяются из условия интерполяции s(xj) = fj (J = 1,..., ЛО, которое приводит к симметричной системе линейных уравнений

[Л][Л]=[Я, (2)

где элементы матрицы А задаются следующим образом: ajk = (p(\\xj - Наиболее часто использующиеся радиальные базисные

функции: <р(г) = ф) = г, <p(r) = г3, <p{r) = г2 In г и др.

Одной из главных проблем методов интерполяции, использующих радиальные базисные функции, является ограничение на количество точек, по которым производится интерполяция - с ростом числа точек матрица А из уравнения (2) становится плохо обусловленной, что приводит к значительным ошибкам при восстановлении границы. В ряде работ (например, Kappa, Битсона) предпринимались попытки решить эту проблему, но она по-прежнему остаётся актуальной.

В диссертации разработан метод пересечений, который позволяет снять ограничение на количество исходных точек во множестве Q = {£ (s = 2,3). Алгоритм метода пересечений состоит из следующих шагов.

1. Исходное множество точек Q разбивается на некоторое количество подмножеств Qx, Qz,..., Qi, причём точки из множества Q для подмножеств выбираются равномерно по всему облаку точек.

2. Для каждого из множеств Qv Q2, -,Qi строится свой интерполянт (1), в итоге создаются I промежуточных реконструкций границы. Таким образом, каждой точке сетки, на которой происходит построение, будет соответствовать I различных значений функции s(x) из (1). Соответственно, в каждом из этих случаев рассматриваемая точка будет оказываться либо внутри области, ограниченной полученной границей (тогда значение s(x) будет отрицательным), либо вне её (тогда значение будет положительным), либо будет лежать непосредственно на границе (тогда значение s С?) равно нулю).

3. Если данная точка была классифицирована как внутренняя (внешняя) для более чем половины из I построенных поверхностей, то она классифицируется как внутренняя (внешняя) и для итоговой границы. Таким образом, в итоге будет получена граница фигуры, формально построенная по всем исходным точкам из множества Q.

Важно отметить, что представление границы фигуры в виде нулевой поверхности уровня приводит к следующей проблеме: т.к. заданные точки, по которым производится реконструкция, лежат на границе поверхности, то условие интерполяции s(x;) = fj (j = 1,-,N) для них имеет вид s(xj) = О (/ = 1, ...,N). В этом случае система (2), очевидно, будет иметь тривиальное решение.

Для того чтобы этого избежать, необходимо ввести дополнительные точки, в которых fj Ф 0, т.е. точки с соседних поверхностей уровня. Причём в

литературе отмечается, что для корректной реконструкции требуется ввести и точки, в которых > 0, и точки, в которых ^ < 0. Значения /у ^ 0 можно вычислить, найдя функцию расстояния с1(х), однако информацию о знаке получить гораздо сложнее. В диссертации для этого предлагается следующий алгоритм.

Найдём расстояние с((х) от каждой точки сетки, на которой проводится реконструкция, до ближайшей к ней точки из 5. Введём число у > 0. Для каждой точки (£,у, к) сетки введём метки: если к) > у, то

тагк(1,),к) = 1, если (Щ.,),к) < у, то тагк(1,],к) = 2. Будем считать, что начало координат - всегда внешняя по отношению к границе точка, т.е. функция расстояния со знаком ¿¡ДОДО) > 0. Пометим точку как таг/с (0,0,0) = 0 и рассмотрим соседние с ней точки сетки. Если в них выполняется равенство тагк{1,],к) = 1, то меняем метку на 0 и так далее. Таким образом, все точки сетки, внешние по отношению к области, в которой £¿(¿,7, к) < у, поменяют свои метки с 1 на 0. В результате получим ситуацию, представленную на рис.1 (для простоты на рисунке представлен

Рис. 1. Разделение точек сетки на внешние и внутренние. Внешняя по отношению к участку с меткой 2 область будет иметь метку 0, в то время как внутренняя останется с

меткой 1.

Выберем теперь точки с меткой 0 и меткой 1, имеющие хотя бы одну соседнюю точку с меткой 2, т.е. точки на границах этих областей. Если у такой точки (г,у, к) имеется метка 0, то <4(/,/, = +с1(1,],к), если же у точки 0,;', к) метка 1, то = -ё.{1,),к). Таким образом, получены

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

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

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

J

(а) (б)

Рис. 2. Результат реконструкции кривой, заданной функцией (х/3 — 4)2 + ((у/3 —

4)2—6)3—(х/3—4)3(у/3—4)3 = —5. (а) - реконструкция без использования метода пересечений; (б) - реконструкция с помощью метода пересечений (количество точек, по которым проводилась реконструкция - 1035).

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

Рассматривается движущаяся во времени замкнутая поверхность F(t) коразмерности один в Еп. Пусть iî(t) - область ( в общем случае многосвязная), ограниченная поверхностью T(i), a cp(x,t) - поверхность уровня, связанная с fi(t), т.е. (pÇx, t) < 0, если х е iî(t), ср(x,t) = 0, если х 6 F(t), ф(х, t) > 0, еслих £ fi(t) U r(t).

Таким образом, F(t) определяется как нулевая поверхность уровня для функции ср(х, t). Дифференцируя уравнение cp(r(t), t) s 0 по переменной t, получаем уравнение в частных производных вида

dr (t)

Здесь = v(r(t)) - скорость движения точки х на Г = {х ■ ф(х, t) = 0}. Если поле скоростей порождено потенциальным полем Т, то v = — ЧТ. Пусть S - множество точек, по которым строится реконструкция, a d(x) -функция расстояния от точки х до множества S (т.е. до ближайшей точки из

5). Тогда cL(x) в данном обсуждении будет потенциальным полем, а рассматриваемое уравнение перепишется в виде

дер

— = У^со-Уф. (3)

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

Различные разностные схемы, используемые для решения уравнения (3), будут устойчивы при выполнении условия Куранта-Фридрихса-Леви (СРЬ-условия), накладывающего жёсткие ограничения на шаг по времени, поэтому скорость реконструкции с применением метода линий уровня будет крайне низкой, что не позволяет использовать этот метод в реальных задачах. Удачный выбор начальной поверхности может решить эту проблему, но до настоящего времени не было разработано универсальных методов построения такой поверхности. В данной работе предлагается метод решения этой проблемы.

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

Алгоритм двухэтапного метода реконструкции границ фигур

1. На первом этапе по заданному множеству точек 5 с помощью метода пересечений строится приближение к искомой поверхности

2. На втором этапе полученное приближение корректируется и приближается к искомой границе с помощью метода линий уровня.

Для построения предварительной реконструкции с помощью метода пересечений необходимо разбить исходное множество точек 5 на подмножества. Для этого каждой точке из 5 поставим в соответствие случайное число р из интервала (0; 1), подчиняющееся равномерному закону распределения. Введём М - число разбиений исходного множества на подмножества. Построим М реконструкций с помощью радиальных базисных функций, выбирая для каждой из них точки (¿,/, к) так, что — < к) < —, где q - номер рассматриваемого подмножества.

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

принимала отрицательное значение. Будем считать, что если > о.5, то

м

точка (},],к) включается в итоговую реконструкцию как внутренняя точка

п

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

Рассчитанная на первом этапе функция расстояния со знаком используется как начальное значение для метода линий уровня. Для решения уравнения (3) применяется противопоточная (upwind) схема (для простоты приведём пример схемы для двумерного случая):

= <Рц + M(max(dij, О) V+ + mm(d£/, 0) V'),

где

[7+ = Jmax((p~, О)2 + min(q>x, О)2 + тах{<р~, О)2 + min(<Py, О)2

V~ = Jmin((px, О)2 + тах((рх, О)2 + min{(py, О)2 4- тах^сру, О)2. 4>iiUi) = cp-iij) = М-«™,

<Py(.i,j) =

rpUJ+D- vii.j)

<РУ (i.D =

<p{i,D~ <p(j.j-1)

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

( Ввод

i

/ I юстроение \ промежуточной

реконструкции 1

1

I JOUIриение

промежуточной ч реконструкции N

/ Построение ^

реконструкции методом пересечений

( Уточнение Л

положения границы 1 ^ методом линий уровня J

Нет / Ч Да С —--—<3ааершить?>~.........

Построение итоговой реконструкции фигуры j

I

Рис. 3. Схема работы двухэтапного метода реконструкции границы

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

Для проверки работы алгоритма двухэтапного метода была создана его программная реализация в среде MATLAB R2010a. Рассмотрен ряд функций, графики которых образуют различные замкнутые кривые и поверхности. Выбирались множества точек, лежащие на границах этих фигур, и по ним с помощью двухэтапного метода восстанавливалась граница. Мерой оценки точности реконструкции являлось отношение Е = Err/N, где Err - число точек, в которых знак неявной функции, получающейся в результате работы двухэтапного алгоритма, отличался от знака заданной тестовой функции, N -общее число точек сетки. Примеры реконструкции в двумерном и трёхмерном случаях представлены на рис. 4 и рис. 5.

с? CL, д

3 с к щ S

<=< ? -к; с

<«- ir г-*?

. < I ft S

f. Л

Г

Ь.

* " " ь « * V.

(а) (б)

Рис. 4. Восстановление границы фигуры с использованием двухэтапного метода, (а) -график исходной функции; (б) - результат реконструкции с помощью двухэтапного

метода.

(а) (б)

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

Кроме того, был рассмотрен пример реконструкции по данным, полученным с устройства с низкой разрешающей способностью (см. рис. 6).

Рис. 6. Реконструкция границы фигуры с помощью двухэтапного метода: (а) -реконструируемый объект; (б) - исходное множество точек, полученных с видеоустройств с низкой разрешающей способностью; (в) - результат реконструкции двухэтапным методом по 4930 точкам; (г) - результат реконструкции двухэтапным методом по 19237 точкам.

В результате проведённых вычислительных экспериментов был сделан вывод, что двухэтапный метод позволяет, с одной стороны, компенсировать недостатки реконструкции с использованием радиальных базисных функций (ограничение на количество точек, по которым восстанавливается граница), и, с другой стороны, преодолеть главный недостаток метода линий уровня -низкую скорость восстановления. При этом в рассмотренных примерах были получены качественные реконструкции (не более 7% ошибочно классифицированных точек в двумерном случае и не более 12% в трёхмерном). Использование двухэтапного метода даже без параллельной реализации метода пересечений (первого этапа) позволяет существенно (в 34 раза) ускорить процесс реконструкции в трёхмерном случае, что даёт возможность при параллельной реализации использовать разработанный метод в системах компьютерного зрения реального времени.

(а) (б)

(в)

(г)

В заключении сформулированы основные результаты работы:

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

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

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

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

Основные публикации по теме диссертации Статьи в изданиях, рекомендованных ВАК РФ

1. Атанов A.B. Параллельный алгоритм реконструкции двумерных объектов на основе радиальных базисных функций / A.B. Атанов, A.A. Крыловецкий, С.Д. Кургалин // Известия Южного федерального университета. Технические науки. - Таганрог, 2012. - № 6. - С. 195198.

2. Пространственная реконструкция в системах компьютерного зрения на основе web-камер / A.B. Атанов, A.A. Крыловецкий, С.Д. Кургалин, С.И Протасов // Вестник Воронежского государственного университета. Сер. Системный анализ и информационные технологии. - Воронеж, 2011. - № 2. - С. 149-153.

3. Атанов A.B. Параллельный алгоритм реконструкции объектов по неупорядоченному набору точек на основе радиальных базисных функций / A.B. Атанов, A.A. Крыловецкий, С.Д. Кургалин // Вестник Воронежского государственного технического университета. -Воронеж, 2012. - Т. 8, № 10-2. - С. 13-15.

Статьи в сборниках научных трудов и материалах конференций

4. Атанов A.B. Современные алгоритмы трехмерной реконструкции по изображениям / A.B. Атанов, A.A. Крыловецкий // Информатика : проблемы, методология, технологии : материалы 9-ой международ.

науч.-метод, конф., Воронеж, 12-13 февр. 2009 г. - Воронеж, 2009. -Т. 1. - С. 57-61.

5. Атанов A.B. Восстановление контура объекта по точкам с использованием алгоритм LevelSet / A.B. Атанов, A.A. Крыловецкий // Информатика : проблемы, методология, технологии : материалы X междунар. науч.-метод. конф., 11-12 февр. 2010 г., г. Воронеж. -Воронеж, 2010. - Т. 1. - С. 60-63.

6. Атанов А. В. Реконструкция моделей объектов по неупорядоченному набору точек / A.B. Атанов, A.A. Крыловецкий // Телематика'2010 : тр. XVII Всерос. науч.-метод. конф., 21-24 июня 2019 г., Санкт-Петербург. - СПб., 2010. - Т. 2. - С. 310-312.

7. Атанов A.B. Реконструкция трехмерных моделей объектов по неупорядоченному набору точек с использованием алгоритма Level Set / A.B. Атанов, A.A. Крыловецкий // Информатика : проблемы, методология, технологии : материалы XI междунар. науч.-метод. конф., 10-11 февр. 2011 г., г. Воронеж. - Воронеж, 2011. - Т. 1. - С. 61-65.

8. Атанов A.B. Реконструкция трехмерных моделей объектов в системах компьютерного зрения на основе веб-камер методом функций уровня / A.B. Атанов, A.A. Крыловецкий // Информатика : проблемы, методология, технологии : материалы XII Междунар. науч.-метод. конф., 9-10 февр. 2012 г., г. Воронеж. - Воронеж, 2012. -Т. 1. - С. 25-26.

9. Атанов A.B. Параллельный алгоритм реконструкции двумерных объектов на основе радиальных базисных функций / A.B. Атанов, A.A. Крыловецкий // Телематика'2012 : тр. XIX Всерос. науч.-метод. конф., 25-28 июня 2012 г., Санкт-Петербург. - СПб., 2012. - Т. 2. - С. 309-311.

10.Атанов A.B. Трехмерная реконструкция в системах компьютерного зрения с использованием WEB-камер / A.B. Атанов, A.A. Крыловецкий // Телематика'2012 : тр. XIX Всерос. науч.-метод. конф., 25-28 июня 2012 г., Санкт-Петербург. - СПб., 2012. - Т. 2. - С. 313314.

Подписано в печать 20.12.12. Формат 60*84 Усл. печ. л. 0,93. Тираж 100 экз. Заказ 1212.

Отпечатано с готового оригинал-макета в типографии Издательско-полиграфического центра Воронежского государственного университета. 394000, Воронеж, ул. Пушкинская, 3

Введение.

Глава 1. Методы реконструкции границ объектов.

1.1 Этапы реконструкции объекта в системах компьютерного зрения.

1.2 Методы реконструкции границ фигур.

Глава 2. Метод пересечений.

2.1 Радиальные базисные функции.

2.2 Метод пересечений.

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

Глава 3. Двухэтапный метод реконструкции границ объектов.

3.1 Метод линий уровня.".

3.2 Двухэтапный метод реконструкции.

Глава 4. Компьютерная модель и численные эксперименты.

4.1 Программная реализация.:.

4.2 Численные эксперименты.

Актуальность темы

Одним из главных направлений исследований при создании систем компьютерного зрения является анализ и решение проблем, связанных с задачей реконструкции (восстановления) границ объектов. Значительный интерес к созданию компьютерных реконструкций реальных объектов объясняется широкой областью их применения: в медицине, геологии, промышленном производстве, археологии, мультимедиа-технологиях и т.д. Важнейшие части этой задачи - математическое описание границ различных фигур и представлении информации о границе в форме, удобной для изменения, хранения и визуализации.

В настоящее время существует два основных подхода к решению задачи восстановления границ. Так в работах М.Гопи, Д.Эберли, Ж.-Д. Буассона предлагаются методы, использующие триангуляцию Делоне. Несмотря на простоту реализации, эти методы не подходят для использования в системах компьютерного зрения реального времени из-за появления значительных ошибок при обработке больших массивов данных и низкой скорости работы основанных на них алгоритмов. Р.Франке, С.Ошер, Дж.Карр применили получивший большую популярность подход, определяющий положение границы объекта с помощью неявно заданных функций. Однако у разработанных на его основе методов имеются недостатки, связанные, в частности, с ограничением на количество точек, по которым восстанавливается граница. Кроме того, реализация этих методов требует больших временных затрат. Таким образом, несмотря на большое число способов реконструкции, пока ещё не существует универсального метода, позволяющего с достаточно высокой скоростью восстанавливать границы произвольных фигур. Кроме того, практически все известные методы ориентированы на работу с дальнометрическими изображениями (содержащими информацию о расстоянии от камеры до точек на поверхности рассматриваемого объекта), полученными с прецезионных ЗЭ-сканеров, имеющих большую разрешающую способность. Высокая -стоимость таких сканеров не позволяет использовать их для создания систем компьютерного зрения, ориентированных на массового потребителя. Однако дальнометрические изображения можно получить и с устройств с низкой разрешающей способностью, например, веб-камер, камер ноутбуков и . мобильных телефонов и т.д., что может существенно снизить стоимость разрабатываемых на их базе систем компьютерного зрения. При этом следует учитывать, что информация о границе фигуры, получаемая с таких устройств, очевидно, содержит гораздо больше ошибок, чем информация с ЗО-сканеров. Проведённый анализ показал, что в настоящее время отсутствуют методы и алгоритмы, ориентированные на' реконструкцию объектов по данным, полученным с устройств с низкой разрешающей способностью.

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

Диссертационная работа выполнена на кафедре цифровых технологий Воронежского государственного университета по НИР «Разработка новых методов обработки, хранения, передачи и защиты информации в информационно-коммуникационных системах» № ГР 01200956642 (20092010 гг.) и «Разработка новых методов обработки, хранения и передачи инфррмации в информационно-коммуникационных системах» № ГР 01201170666 (2011 г.) аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы».

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

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

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

2. • Создание двухэтапного метода реконструкции, допускающего параллельную реализацию.

3. Разработка и анализ алгоритмов для предложенных моделей и методов.

4. Построение и исследование компьютерной модели реконструкции границ объектов.

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

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

Новизна работы состоит в:

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

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

3. Создании и исследовании алгоритмов для реализации двухэтапного метода реконструкции в двумерном и трёхмерном случаях.

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

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

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах: IX-XII Международных научно-методических конференциях «Информатика : проблемы, методология, технологии»,- г.Воронеж, 2009-2012 гг.; XVII, XIX Всероссийских научно-методических конференциях «Телематика», г.Санкт-Петербург, 2010, 2012 гг.; научно-практической конференции «Связь и телекоммуникации - инновационное развитие регионов», г.Воронеж, 2011 г.; Всероссийской научной конференции "Современные проблемы математического моделирования, супервычислений и информационных технологий", г.Таганрог, 2012 г.

Публикации. По теме диссертации имеется 10 публикаций, в том числе 3 - в ведущих периодических изданиях, рекомендованных ВАК РФ.

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

Структура и объём работы. Диссертация состоит из введения, четырёх глав, заключения и списка литературы из 107 наименований. Объём диссертации составляет 111 страниц текста, содержащего 47 рисунков и 12 таблиц.

Заключение

В заключении сформулируем основные результаты работы.

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

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

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

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

1. Форсайт Д. Компьютерное зрение : современный подход : пер. с англ. / Д. Форсайт, Ж. Понс ; Калифорнийский университет в Беркли; Иллинойский университет в Урбана-Шампейн. — М. : Вильяме, 2004. — 926 с.

2. Шапиро JI. Компьютерное зрение / JI. Шапиро, Дж. Стокман: Пер. с англ. — М.: БИНОМ. Лаборатория знаний, 2006. — 752 с.

3. Agin G. Fitting ellipses and general second-order curves / G. Agin // Technical report. — CMU Robotics Institute, 1981. — 29 p.

4. Shirai Y. Recognition of polyhedrons with a range finder / Y. Shirai // Pattern Recognition. — 1972. — Vol. 4. — P. 243-250.

5. Besl P. A method for registration of 3D shapes / P. Besl, H. McKay // IEEE Transaction on pattern analysis and machine intelligence. — 1992. — Vol. 14. —P. 239-256.

6. Chen Y. Object modeling by registration of multiple range images / Y. Chen, G. Medioni // Int. J. Image and Vision Computing. — 1992. — Vol. 10(3). — P. 145-155.

7. Dorai C. Optimal registration of multiple range views / C. Dorai, J. Weng, A. Jain // Proc. 12th Int. Conf. Pattern Recognition, Jerusalem, Israel. — 1994. —Vol. 1. —P. 569-571.

8. Blais G. Registering multiview range data to create 3D computer objects / G. Blais, D. Levine // IEEE Transaction on Pattern Analysis and Machine Intelligence. — 1995. — Vol. 17. — P. 820-824.

9. Г Dorai C. Optimal registration of object views using range data / C. Dorai, J. Weng, A. Jain // IEEE Transaction on Pattern Analysis and Machine Intelligence. —1997. —Vol. 19. —P. 1131-1138.

10. Levoy M. Zippered polygon meshes from range images / M. Levoy, G. Turk // Computer Graphics (SIGGRAPH'94 Proceedings). — 1994. — P. 311-318.

11. Boissonnat J.-D. Geometric structures for three-dimensional shape representation / J.-D. Boissonnat // ACM Transactions on Graphics. 1984. — Vol. 3(4). —P. 266-286.

12. DeRose T. Surface reconstruction from unorganized points / T. DeRose et al. // Proceedings of" SIGGRAPH. — 1992. — P. 71-78.

13. Edelsbrunner H. Three-dimensional alpha shapes / H. Edelsbrunner, E. . P. Mucke // ACM Transactions on Graphics. — 1994. — Vol. 13(1). — P. 43-72.

14. Amenta N. A new Voronoi-based surface reconstruction algorithm / N. Amenta, M. Bern, M. Kamvysselis // Proceedings of ACM SIGGRAPH. — 1998.1. P. 415-421.

15. Bernardini F. The ball-pivoting algorithm for surface reconstruction / F. Bernardini // IEEE Transactions on Visualization and Computer Graphics. — 1999. — Vol. 5(4). — P. 349-359.

16. Attene M. Automatic surface reconstruction from point sets in space / M. Attene, M. Spagnuolo // Computer Graphics Forum. — 2000. — Vol. 19(3). — P. 457-465.

17. Dey T.K. Tight cocone: A water-tight surface reconstructor / T.K. Dey, S. Goswami // Proc. 8th ACM Sympos. Solid Modeling Applications. — 2003. — P. 127-134.

18. Bajaj C. Automatic reconstruction of surfaces and scalar fields from 3d scans / C. Bajaj, F. Bernardini, G. Xu // International Conference on Computer Graphics and Interactive Techniques. — 1995. — P. 109-118.

19. Beatson R.K. Reconstruction and representation of 3D objects with radial basis functions / R. K. Beatson et al. // Proceedings of ACM SIGGRAPH.2001. —P. 67-76.

20. Curless B. A volumetric method for building complex models from range images / B. Curless, M. Levoy // Proceedings of ACM SIGGRAPH. — 1996. —P. 303-312.

21. Alexa M. Multi-level partition of unity implicits / M. Alexa et al. // ACM Transactions on Graphics. — 2003.' — Vol. 22(3). — P. 463-470.

22. O'Brien J.F. Shape transformation using variational implicit "functions / G. Turk, J. F. O'Brien // Proceedings of ACM SIGGRAPH. — 1999. — P. 335• • 342.

23. Levoy M. Zippered polygon meshes from range images / G. Turk, M. Levoy // Proceedings of ACM SIGGRAPH. — 1994. — P. 311-318.

24. Jeong W.-K. Using growing cell structures for surface reconstruction / K. Jeong, I. Ivrissimtzis // Shape Modeling International. — 2003. — P. 78-86.

25. Jeong W.-K. Neural meshes: Statistical learning based on .normals / W.K. Jeong, I. ivrissimtzis, H.-P. Seidel // Pacific Graphics. — 2003. — P. 404-408.

26. Yu Y. Surface reconstruction from unorganized points using self-organizing neural networks / Y. Yu // Proc. of IEEE Visualization'99. — 1999. — P. 61-64.

27. Cazals F. Delaunay Triangulation Based Surface Reconstruction / F. Cazals, J. Giesen // Effective Computational Geometry for Curves and Surfaces. —• Springer-Verlag, Mathematics and Visualization, 2006. — P. 231-276.

28. Aurenhammer F. Voronoi Diagrams — A Survey of a Fundamental Geometric Data Structure / F. Aurenhammer // ACM Computing Surveys. — 1991. — Vol. 23(3). — P. 345-405.

29. Boots B. Spatial Tessellations — Concepts and Applications of Voronoi Diagrams / B. Boots et al.. — 2nd edition. — John Wiley, 2000. — 671 P

30. Amenta N. Surface reconstruction by Voronoi filtering / N. Amenta, M. Bern // Discr. Comput. Geom. — 1999. — Vol. 22. — P. 481-504.

31. Gopi M. Surface reconstruction based on lower dimensional localized delaunay triangulation / M. Gopi, S. Krishnan, C. T. Silva // Computer Graphics Forum (Eurographics 2000). — 2000. — Vol. 19(3). — P. 467-478.

32. Eberly D. Ridges for Image Analysis / D. Eberly el al. // Jour. Mathematical Imaging and Vision. — 1994. — Vol. 4(4). — P. 353-373.

33. Papaleo L. Surface Reconstruction: Online Mosaicing and Modeling with Uncertainty: Ph.D. Thesis in Computer Science. — Genova, 2004. — 154 p.

34. Capps M. Surface Reconstruction with Anisotropic Density-Scaled A Shape / M. Teichmann, M. Capps // Proceedings in IEEE Visualization'98. — 1998. —P. 18-23.

35. Veltkamp R.C. Closed Object Boundaries from Scattered Points : PhD thesis / R. C. Veltkamp. — Center for Mathematics and Computer Science, Amsterdam. — 1992.

36. De Floriani L. On-line Space Sculpturing for 3D Shape Manipulation / L. De Floriani, P. Magillo, E. Puppo // Proc. Int. Conference on Pattern Recognition, Barcelona, Spain. — 2000. — Vol. 1. — P. 105-108.

37. Heidrich W. Shape Simplification Based on the Medial Axis Transform / R. Tam, W. Heidrich // Proceedings of IEEE Visualization. — 2003. — P. 481488. - "

38. Amenta N. A Simple Algorithm for Homeomorphic Surface Reconstruction / N. Amenta et al. // International Journal of Computational Geometry and Applications. — 2002. — Vol. 12(1-2). — P. 125-141.

39. Angel E. Spiraling Edge: Fast Surface Reconstruction from Partially Organized Sample Points / E. Angel, P. Crossno // Proceedings Visualization IEEE'99. — 1999. — P. 317-324.

40. Gopi M. Surface Reconstruction based on Lower Dimensional Localized Delaunay Triangulation / M. Gopi, S. Krishnan, C. Silva // Proceedings of Eurographics. — 2000. — Vol. 19(3). — P. C467-C478.

41. Cline H.E. Marching Cubes: A high resolution 3D surface construction algorithm / H.E. Cline, W.E. Lorensen // Computer Graphics. — 1987. — Vol. 21(4). —P. 163-169.

42. Bloomenthal J. Introduction to Implicit Surfaces / J. Bloomenthal. — Morgan Kaufmann, 1997. — 332 p.

43. Franke, R. Scattered data interpolation: tests of some methods // Math. Comput. — 1982. — Vol. 38. — P. 181-200.

44. Sethian J.A. Level Set Methods and Fast Marching Methods Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science. / J.A. Sethian. — University of California, Berkeley, 1999. —• 404 p.

45. Sethian J.A. Evolution, Implementation, and Application of Level Set and Fast Marching Methods for Advancing Fronts. / J.A. Sethian. // J. Comp. Phys.—2001. —Vol. 169. —P. 503-555.

46. Sethian J.A. Fast Marching Methods / J.A. Sethian. // SIAM Review.1999. — Vol. 41(2). — P. 199-235.

47. Osher S. Fronts Propagating with Curvature Dependent speed: Algorithms Based on Hamilton-Jacobi Formulation. / S. Osher, J.A. Sethian // J. Comp. Phys. — 1988. — Vol. 79. — P. 12-49.

48. Fedkiw R. Fast surface reconstruction using the level set method / R. Fedkiw, S, Osher, H.-K. Zhao // VLSM'01: Proceedings of the IEEE Workshop on Variational and Level Set Methods (VLSM'01), Washington, DC, USA. — 2001.1. P. 194.

49. Schaback R. Reconstruction of multivariate functions from scattered data// Manuscript. — 1997. — (http://www.num.math.uni-goettingen.de/schaback/).

50. Hardy R.L. Multiquadric equations of topography and other irregular surfaces / R.L. Hardy // J. Geophy. Res. — 1971. — Vol. 76. — P. 1905-1915.

51. Hardy R.L. Theory and applications of the multiquadric-biharmonic method: 20 years of discovery / R.L. Hardy // Comput. Math. Appl. — 1980. — Vol. 19. —P. 163-208.

52. Duchon J. Splines minimizing rotation-invariant semi-norms in sobolev ' spase / J. Duchon // Constructive Theory of Functions of Several Variables,

53. Springer Lecture Notes in Math, 21. — 1977. — P. 85-100.

54. Schagen I.P. Interpolation in two dimensions — a new technique / LP. Schagen // J. Inst. Math. Appl. — 1979. — Vol. 23. — P.53-59.

55. Franke R. Scattered data interpolation: tests of some methods / R. Franke // Math. Comput. — 1982. — Vol. 38. — P. 181-200.

56. Micchelli C.A. Interpolation of scattered data: distance matrices and conditionally positive definite functions / C.A. Micchelli // Constr. Approx. — 1986. —Vol.2 —P. 11-22.

57. Micchelli C.A. Optimal recovery of smooth functions approximations / C.A. Micchelli, T.J. Rivlin, S. Winograd // Numerische Mathematik. — 1976. — Vol. 260. —P. 191-200.

58. Micchelli C.A. Lectures on optimal recovery / C.A. Micchelli, TJ. Rivlin // Lecture Notes in Mathematics 1129. — Springer Verlag, 1984. — P. 1293.

59. Schoenberg I.J. Metric spaces and completely monotone functions / I.J. Schoenberg // Ann. Math. — 1938. — Vol. 39. — P. 811-841.

60. Variational implicit surfaces : Tech Report GIT-GVU-99-15 / Georgia Institute of Technology; Turk G., O'Brien J.F. — 1999. — 9 p.

61. Beatson R.K. Fast fitting of radial basis functions: Methods based on preconditioned GMRES iteration / R.K. Beatson, J.B. Cherrie, C.T. Mouat // Adv. Comput. Math. — 1999. — Vol. 11. — P. 253-270.

62. Dyn N. Numerical procedures for global surface fitting of scattered data by radial functions / N. Dyn, D. Levin, S. Rippa // SIAM J. Sci. Stat. Comput. — 1986. — Vol. 7. — pp.639-659.

63. Faul A.C.- Krylov subspace methods for radial basis function interpolation / A.C. Faul, M.J.D. Powell // Numerical Analysis. — 1999. — P. 115-141.

64. Wendland H. Piecewise polynomial, positive definite and compactly supported radial functions of minimal degree / H. Wendland // Adv. Comput. Math. — 1995. — Vol. 4. — P. 389-396.

65. Wu Z. Multivariate compactly supported positive definite radial functions / Z. Wu // Adv. Comput. Math. — 1995. — Vol. 4. — P. 283-292.

66. Beatson R.K. Fast solution of the radial basis function interpolation equations: Domain decomposition methods / R.K. Beatson, S. Billings, W.A. Light // SIAM X. Sci. Comput. — 2000. — Vol. 22. — P. 1717-1740.

67. Hon Y.C. Circumventing the ill-conditioning problem with multiquadric radial basis functions: Applications to elliptic partial differential equations / Y.C. Hon, E.J. Kansa // Comput. Math. Appl. — 2000. — Vol. 39(1).1. P. 123-137.

68. Girosi F. Some extensions of radial basis functions and their ■ applications in artificial intelligence / F. Girosi // Comput. Math. Appl. — 1992. —1. Vol.24. —P. 61-80.

69. Beatson R.K. Surface interpolation with radial basis functions for medical imaging / R.K. Beatson, J.C. Carr, W.R. Fright // IEEE Trans. Medial Imaging. — 1997. — Vol. 16. — pp.96-107.

70. Flusser J. An adaptive method for image registration / J. Flusser // Pattern Recognition. — 1992. — Vol. 25. — P. 45-54.

71. Park C. A radial basis function approach to pattern recognition and its applications / M. Shin, C. Park // ETRI Journal. — 2000. — Vol. 22. — P. 1-10.

72. Barrodale I. Warping aerial photographs to orthomaps using thin plate splines /1. Barrodale, C.A. Zala // Adv. Comput. Math. — 1999. — Vol. 11. — P. 211-227.

73. Kunii T.L, Function representation of solids reconstructed from scattered surface points and contours / Kunii et al. // Computer Graphics Forum.1995. —Vol. 14(4). —P. 181-188.

74. Beatson R.K. Reconstruction and representation of 3d objects with radial basis functions / R.K. Beatson et al. // Proceedings of SIGGRAPH. — 2001. —P. 67-76.

75. Sibson R. Computation of thin-plate splines / R. Sibson, G. Stone // • SIAMJ. Sci. Stat. Comput. —1991.-Vol. 12(6). —P. 1304-1313.

76. Osher S. Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations / S. Osher, J. A. Sethian // Journal of Computational Physics. — 1988. — Vol. 79. — P. 12-49.

77. Enright D. Animation and rendering of complex water surfaces / D. Enright, R. Fedkiw, S. Marschner // Proceedings of SIGGRAPH 2002, Computer Graphics Proceedings, Annual Conference Series. — ACM Press, 2002. — P. 736-744.

78. Fedkiw R. Practical animation of liquids / N. Foster, R. Fedkiw // Proceedings of ACM SIGGRAPH 2001, Computer Graphics Proceedings, Annual Conference Series. — ACM Press, 2001. — P. 23-30.

79. Barr A. Level set surface editing operators / A. Barr et al. // ACM Trans, on Graphics (Proc. SIGGRAPH). — 2002. — Vol. 21(3). — P. 330-338.

80. Breen D.E. A level-set approach for the metamorphosis of solid models. / D. E. Breen, R. T. Whitaker // IEEE Trans. Vis. Comput. Graph. — 2001. — Vol. 7(2). — P. 173-192.

81. Bridson R. Simulation of clothing with folds and wrinkles / R. Bridson, R. Fedkiw, S. Marino // SCA'03: Proceedings of the 2003 ACM SIGGRAPH/Eurographics Symposium on Computer animation. — 2003. — P. 28-36.

82. Fedkiw R. Fast surface reconstruction using the level set method / H.-R. Fedkiw, S. Osher, H.-K. Zhao // VLSM'01: Proceedings of the IEEE Workshop on Variational and Level Set Methods (VLSM'01), Washington, DC, USA. — 2001. —P. 194.

83. Fedkiw R. Level set method and dynamic implicit surfaces / S. Osher, R. Fedkiw. — Springer, 2003. — 273 p.

84. Sethian, J. A. Evolution, implementation, and application of level set and fast marching methods for advancing fronts / J.A. Sethian // Journal of Computational Physics. — 2001. — Vol. 169. — P. 503-555.

85. Роуч П. Вычислительная гидродинамика / П. Роуч ; пер. с анг. В.А. Гущина, .В.Я. Митницкого; под ред. П.И. Чушкина. — М. : Мир, 1980. — 615,1. с.

86. Курант Р. О разностных уравнениях математической физики / Р. Курант, Г. Леви, К. Фридрихе // УМН. — 1941. — № 8. — С. 125—160.

87. Shu C.-W., Osher S. Efficient implementaton of essentially non-oscillatory schock-capturing schemes // J. Comput. Phys. — 1989. — Vol. 83. — N. 1. —P. 32-78.

88. Chan T. Weighted Essentially Non-Oscillatory Schemes / X.-D. Liu, S. Osher, T. Chan // J. Comput. Phys. — 1996. — Vol. 126. — P. 202-212.

89. Osher S. Efficient implementation of Essentially Non-Oscillatory Shock Capturing Schemes II / S. Osher, C.W. Shu // J. Comput. Phys. — 1989. — Vol. 83. —P.32-78.

90. Osher S. A level set approach for computing solutions to incompressible two-phase flow / S. Osher, P. Smereka, M. Sussman // J. Comput. Phys. —1994. —Vol. 114. —P. 146-159.

91. A PDE-based fast local level set method / D. Peng et al. // J. Comput. Phys. — 1999. — Vol. 155. — P. 410-438.

92. Sethian J.A. Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials^Science / J.A. Sethian. — Cambridge University Press, 1999. — 404 p.

93. Paragios N. Handbook of Mathematical Models in Computer Vision / N. Paragios, Y. Chen, O.D. Faugeras. — Springer, 2006. — 639 p.

94. Сулейманов P. P. Компьютерное моделирование математических задач.: Учебное пособие / Р. Р. Сулейманов. — М.: БИНОМ, 2011. — 384 с.

95. Королев А. Л. Компьютерное моделирование/ Королев А. Л. — М.: Бином, Лаборатория знаний, 2010. — 230 с.

96. Компьютерное моделирование физических процессов в пакете MATLAB : учеб. пособие / C.B. Поршнев и др.. — СПб.: Лань, 2011. — 736 с.

97. Corke P. Robotics, Vision and Control: Fundamental Algorithms in MATLAB (Springer Tracts in Advanced Robotics) / P. Corke. — Springer, 2011. — 596 p.

98. Hlavac Vol. Image Processing, Analysis & and Machine Vision — A MATLAB Companion / T. Svoboda, J. Kybic , Vol. Hlavac/ — CL Engineering, 2007. — 272 p.

99. Карапищ Г. А. Построение виртуальных моделей по дальнометрическим данным / Г.А. Карапиш, A.A. Крыловецкий, И.С. Черников // Телематика'2008 : тр. XV Всерос. науч.-метод. конф., 23-26 июня 2008 г., Санкт-Петербург. — СПб., 2008. — Т.1. — С. 208.