ТЕХНИЧЕСКОЕ ЗРЕНИЕ
ГЛАВНАЯ
СТАТЬИ
ПРОГРАММЫ
ЛИТЕРАТУРА
МЕРОПРИЯТИЯ
Статьи

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


Surface registration using a dynamic genetic algorithm


[ссылка на оригинал статьи на английском языке]

Авторы:   Чи Кинь Чоу, Хун Тат Цуй, Тон Ли
Лаборатория технического зрения и обработки изображений, Кафедра электронной техники, Китайский Университет Гонконга, Гонконг —
Chi Kin Chow, Hung Tat Tsui, Tong Lee
Computer Vision and Image Processing Laboratory, Department of Electronic Engineering, The Chinese University of Hong Kong, Hong Kong

Публикация в журнале Pattern Recognition № 37 (2004) стр.105-117


перевод и частичная переработка текста: Пасяда Александр Васильевич, 2004 г.

1. Введение
  Обзор классов алгоритмов регистрации поверхностей
2. Регистрация поверхности
  2.1. Регистрация поверхности как проблема оптимизации
  2.2. Многообразие поверхностей при использовании функции ошибок регистрации
3. Предложенный генетический алгоритм
  3.1. Определение гена и хромосомы
  3.2. Функция пригодности
  3.3. Воспроизводство
    3.3.1 Скрещивание
    3.3.2. Мутации
  3.4. Динамические границы
4. Результаты экспериментов
  4.1. Построение модели
  4.2. Чувствительность к шуму
  4.3. Получение моделей реальных изображений
5. Итоги
Благодарности
Литература и ссылки
Переменные в статье

1. Введение

Сегодня достаточно популярен подход в моделировании объектов при помощи захвата ряда перекрывающихся видов объекта, целиком охватывающих его поверхность. Но существуют серьёзные сложности с точностью регистрации произвольных поверхностей, соответствующих различным видам в одной объёмной модели [1-4], даже если объект распознаётся дорогими системами технического зрения (например, Сyber Scan). Они есть даже в том случае, когда объект установлен на вращающейся платформе или датчик расстояния контролируется роботом. Идеальному алгоритму регистрации поверхности следует быть быстрым и точным. А также алгоритму качественной регистрации поверхности следует иметь такие свойства, как:

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

В статье рассматривается решение проблемы регистрации поверхности с применением генетических алгоритмов. Такие алгоритмы подходят по данным критериям.

ОБЗОР КЛАССОВ АЛГОРИТМОВ РЕГИСТРАЦИИ ПОВЕРХНОСТЕЙ

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

1) алгоритм Итеративной ближайшей точки (ИБТ, англ. ICP) [1,5–8] и
2) сравнение соответствий [9–12].

Бэсл и МакКей [6] предложили алгоритм ИБТ, который вычисляет набор параметров жёстких движений, которые регистрируют поверхность с различных видов на объект. Этот метод хорошо работает, когда каждая точка данных имеет соответствующую точку на модели. И естественно его работа сильно зависит от зашумлённости, особенно когда применяется к большому объёму изображений объекта.

Среди других предложений — рассмотренный Масудой и другими авторами в [1, 8] более точный метод регистрации двух плотных рядов изображений, который представляет интеграцию алгоритма ИБТ с произвольным выбором образцов и оценкой наименьшей медианы квадратов. Эта оценка более точна, чем стандартная оценка наименьших квадратов, который минимизирует сумму квадратных остатков, т.к. оценка наименьшей медианы квадратов минимизирует медиану квадратных остатков. Следовательно, оценка наименьшей медианы квадратов способна допускать присутствие выбросов за границы теоретически до 50%.

Ямани и Фараг [9, 13] предложили альтернативу — вначале вычисляются так называемые сигнатуры поверхностей на основе изображений. Сигнатуры поверхностей — это кривизна поверхности, вычисленная в каждой точке растра изображения. Можно воспользоваться сравнением сигнатур двух поверхностей, чтобы восстановить параметр трансформации между этими поверхностями. Авторы предложили использовать шаблонный подбор для сравнения изображений сигнатур.

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

Регистрацию двух произвольных поверхностей можно сформулировать как поиск или оптимизационную задачу. Это приводит к шестимерной задаче оптимизации с множеством локальных экстремумов. Именно генетические алгоритмы (ГА) хороши в качестве функции оптимизации со множеством оптимальных точек и отсутствием ограничений на форму объектных функций. Недавно было опубликовано несколько попыток использования генетических алгоритмов [13-15]. К примеру, Brunnstrom и Stoddart [14] успешно разработали подобный алгоритм с частым схождением решения за 2 минуты на AlphaStation 250. Результаты были получены с помощью нахождения первого соответствия из набора точек данных образца между моделью и исходным изображением. Из этих соответствий затем вычислялась трансформация. С помощью этого подхода генетический алгоритм производит только приближённую трансформацию. Затем, чтобы найти точную трансформацию с приближённым решением в качестве начального предположения, предлагается использовать процесс типа ИБТ. Но не ясно, как такой подход станет работать, когда некоторые точки данных в исходном изображении не будут иметь соответствия на модели.

В этой работе предлагается новый генетический метод решения проблемы регистрации поверхности. По двум изображениям измерений поверхностей мы стараемся найти трансформацию между этими изображениями. Два изображения могут быть соединены отображением одной выборки на другую с такой вычисленной трансформацией, что скрытые части изображения могут быть восстановлены из второго изображения. Для решения этого мы разработали используемый генетический алгоритм. Его эффективность будет критически оценена при использовании синтезированных данных. Разработанный алгоритм регистрации поверхности показал себя быстрым, точным и ясным. Например, интегрирование двух частых выборок растровых изображений, состоящих из 10 000 точек образца, с перекрытием около 70% для обработки заняло 45 секунд на ПК Pentium III с 450 МГц процессором. Перестроенная модель использует предложенный алгоритм интегрирования поверхности и даёт ошибку менее 1%.

2. Регистрация поверхности

2.1. Регистрация поверхности как проблема оптимизации

Рассмотрим регистрацию поверхности как проблему оптимизации. Даны две поверхности, исходное изображение S1 = {Pi} и целевое изображение S2 = {Qi}. Цель регистрации поверхности в том, чтобы определить евклидову трансформацию Т между этими поверхностями. Если S2 представляет изображение S1 после трансформации Т, то евклидово расстояние между точками преобразованной поверхности Т(Pi) и их соответствием на поверхности S2 Qi является нулевым для всех i. Тем не менее, если изображения поверхностей S1 и S2 были захвачены датчиком расстояния, евклидово расстояние между Т(Pi) и Qi не будет нулевым из-за ошибок измерения и квантования. Следовательно, будем рассматривать регистрацию поверхности как оптимизационную проблему минимизации евклидовых расстояний из числа всех пар соответствий Т(Pi) и Qi с учётом трансформации, т.е. для всех i:

[|Т(Pi) – Qi|]             (1)

Трансформация Т содержит 6 параметров: перенос по x-, y- и z-оси, а также 3 поворота вокруг этих осей. Когда поверхности S1 и S2 перекрываются, имеет смысл минимизировать сумму Ei(Т) для всех i, или же вместо этого минимизируется медиана Ei(Т), т.е.

[|Т(Pi) – Qi|]             (2)

На практике соответствия Т(Pi) не известны, пока не определена действительная трансформация. Потому обычно временное соответствие берётся по своему усмотрению для измерений евклидова расстояния. Смысл временного соответствия был удачно определён Беслом и МакКеем в [6] как точка с минимумом евклидова расстояния из всех точек S2. Задав набор точек {Pi} в S1 (размером N1) и {Qj} в S2 (размером N2), точка Qj в S2 определяется как временное соответствие из Pi после трансформации T, так как евклидово расстояние Ei между Qi и Т(Pi) является минимумом среди всех точек S2. К тому же, т.к. медиана функции ошибки нелинейна, то это вообще не дифференцируемо. Потому алгоритмы оптимизации на основе вычисления градиентов не подходят. Чтобы просуммировать функцию ошибки регистрации для трансформации, Т определится как

F(T) = Меdian(Ei)              для 1 ≤ iN1             (3а)
Ei(T) = |Т(Pi) – Qj|              для 1 ≤ jN2             (3б)

2.2. Многообразие поверхностей при использовании функции ошибок регистрации

А теперь рассмотрим многообразие поверхностей при использовании функции ошибок регистрации. Для рассмотрения возьмём гипотетическую проблему регистрации простой поверхности (чтобы лучше очертить проблему регистрации). Дана поверхность S, заданная тремя точками Р1, Р2 и Р3 на рис. 1. Мы пытаемся зарегистрировать S вместе с ней самой с помощью фиксации Tx, Ty, Tz и Rz, которые должны равняться 0 и изменяем значения Rx и Ry. Соответствующая поверхность ошибок F(Т) и её градиент представлены на рис. 2. Функция должна иметь глобальный оптимум при Rx = Ry = 0, который соответствует центру на рис.2б. Это может быть рассмотрено

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

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

Тем не менее, на рис. 3 мы показали следы 20 наиболее крутых градиентных спусков с различными исходными точками. Кружком на каждом пути представлено исходное положение траектории, а звездочкой положение сходимости. Мы можем увидеть, что только 2 из 20-ти траекторий приходят к глобальному оптимуму и, следовательно, показатель достижения успеха был бы менее 10%. Хотя некоторые точки попали в окрестность глобального оптимума, когда случается, что решение глобального оптимума не дифференцируемо. Рис.4 ясно иллюстрирует это явление колебаний. Когда решение подходит к глобальному оптимуму (через 4 – 6 операций), решение колеблется в пределах малой области. А это явление появляется в большинстве случаев, даже при локальных минимумах. С другой стороны предложенные генетические алгоритмы, о которых мы ещё скажем, могут успешно находить глобальный оптимум в этом примере среди всех пятисот траекторий. Рис.5 показывает результирующую пригодность пятиста траекторий и диапазон результирующей годности между 0 и 0,03.


Рис. 1 — Образец поверхности для проверки дифференцируемости F(T).

3. Предложенный генетический алгоритм

3.1. Определение гена и хромосомы

Теперь рассмотрим предлагаемые генетические алгоритмы. Вначале сформулируем понятие гена и хромосомы. Так как геометрические отношения (евклидова трансформация) между двумя поверхностями могут быть представлены 6-ю параметрами, мы определили этот ряд параметров как хромосому. Каждый параметр тогда соответствует одному из генов хромосомы:
Гены переноса
TxПеренос по оси х
TyПеренос по оси y
TzПеренос по оси z

Гены поворота
αПоворот вокруг оси х
βПоворот вокруг оси y
θПоворот вокруг оси z

Гены формируют хромосому [Tx, Ty, Tz, Rx, Ry, Rz], которые представляют отношения (матрицу евклидовой трансформации) между двумя произвольными поверхностями, так как в точке данные на двух поверхностях соотносят при помощи отображения:

T = С1 Rx, Ry, Rz S С2, где
Rx = ,
Ry = ,
Rz = ,
S = ,
C1 = ,
C2 = .


(а)

(б)
Рис. 2а — Фигура от F(T) — медианы Ошибки на Rx и Ry; Рис. 2б — Градиент поверхности из (a), где значения градиента отображаются яркостью.

Рис. 3. — Слева пути (траектории) 20 оценок наиболее крутых градиентных склонов. Справа соответствующие значения интенсивности.

3.2. Функция пригодности

Для определения эффективности каждой искусственно созданной хромосомы ГА использует функцию пригодности. Т.к. предполагается, что эта функция измеряет качество регистрации, логично использовать функцию ошибок регистрации из уравнения (3) как функцию годности. С медианой от Еi как пригодное измерение в (3) соответствующий ГА может, в принципе, регистрировать поверхности с более чем 50% перекрытием.

Тем не менее, скорость схождения всегда важна при подборе ГА подхода для оптимизации [16,17]. Т.к. мы должны найти временное соответствие всех точек данных, чтобы определить Еi на измерении пригодности каждой хромосомы, в нашей формулировке время обработки сильно зависит от эффективности поискового процесса. Чтобы уменьшить это время, мы выбрали две ускоряющие стратегии:

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

F(T) = Median(Ei)              для Рi в SS1             (4a)
Ei(T) = |Т(Рi) – Qj|              для 1 ≤ jN2             (4б)

II) для вычисления функции пригодности становится нужно установить тождество Qi соответствующих точек разбитой поверхности к целевой поверхности на равенстве (4б). Т.к. мы не разбили целевую поверхность, число требуемых поисков растёт с ростом N2. Следовательно мы используем быстрый алгоритм поиска ближайшего соседа "k-мерное дерево" [18] для нахождения соответствующей точки в (4б).

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


Рис. 4 — Колебание при оптимизации недифференцируемой функции, показанной на Рис. 2a.

Рис. 5 — Результирующая пригодность 500 оценок предложенного алгоритма минимизации F(T) функции.

3.3. Воспроизводство

3.3.1 Скрещивание

Рассмотрим воспроизводство в ГА. Одна из операций — Скрещивание. Во время скрещивания двух хромосом CMSj = [Txj  Tyj  Tzj  αj  βj  θj] и СМSk = [Txk  Tyk  Tzk  αk  βk  θk] мы случайно выбираем номер генов для обмена — Nобм., причём 1 ≤ N2 ≤ 6, а затем и гены тоже случайно. Эффективный показатель скрещивания для каждого гена 0,5833 во всех наших экспериментах. Заметим, что сгенерированные при операции скрещивания потомки могут сильно отличаться от родителей, так что перекрёстное изменение — процесс, широкий поиск оптимума. С другой стороны мутации будут создавать несколько отличных от родителей потомков, следовательно это изменение — локальный поиск оптимума.


3.3.2. Мутации

Вторая операция — Мутация. Под воздействием мутации каждый ген имеет некоторую вероятность изменить значение. Пусть будем считать, что все вероятности одинаковы. Следовательно, эффективность мутации 0,1666 ,т.к. каждая хромосома из 6 генов.

Рассмотрим гены с действительными значениями. Для гена генерируется случайное добавочное значение в диапазоне [– MV, +MV]. И хромосома, т.е. трансформация подвергается небольшому изменению. Мы рассмотрим случай переменного максимума накопления MV, зависящего от значения пригодности каждой хромосомы. Если значение пригодности велико, хромосома далека от точки оптимумов, следовательно, необходим большой прыжок к более верным значениям хромосомы, значит, присваиваем MV большее значение. И наоборот. Обозначим пригодность родительской хромосомы СМSi как FIT(СМSi), которая является средним евклидовым расстоянием среди всех временных пар соответствий. Геометрически это эквивалентно случаю, когда действительное соответствие внутри сферы с центром в СМSi и радиусом, равным FIT(СМSi). Величина максимума накопления MV для генов переноса выбиралась FIT(СМSi). Это удовлетворяет требованию, что когда хромосома далека от глобального оптимума, мутацией совершается прыжок большой величины и наоборот.

Оценивая эффект от динамической мутации, мы провели 2 регистрации 100% перекрывающихся поверхностей со стратегией постоянного MV и динамического. Статистика окончательных значений пригодности, числа требуемых генераций и времени для 10 экспериментов показана в Таблице 1:

Таблица 1.
Сравнение производительности ГА с динамической мутацией и без неё
С динамической мутациейБез динамической мутации
Пригодность(мм)Среднее: 0,41
SD: 0,266
Среднее: 10,4
SD: 2,73
Число ГенерацийСреднее: 115,7
SD: 24,3
Среднее: 109,4
SD: 21,2
Время вычисленийСреднее: 130,9
SD: 22,3
Среднее: 91,9
SD: 14,0

Так как динамическая мутация уменьшает диапазон мутаций, то подходы ГА ближе к оптимуму, а шаг поиска будет переменным. Он мог быть больше вначале, но уменьшался с приближением к оптимуму. Как мы обсудим позже, ГА будет сходиться к решению, если его расстояние до оптимума меньше шага. Это имеет два последствия:

I) алгоритм динамической мутации вероятно должен сходиться к решению с меньшей ошибкой регистрации,

II) диапазон алгоритма статической мутации будет склонятся к сходимости раньше.

Схема динамической мутации эффективна для определения размера шага. Из Таблицы 1 ГА с динамической мутацией сходится последовательнее с лучшей пригодностью, хотя число генераций только немного больше. А заметный рост времени вычислений объясняется переменным шагом мутаций. Тем не менее эффективность перевешивает оба эти недостатка.


Рис. 6. (А) — Диапазон оригинального параметра в исходной популяции; (Б) — первый сокращённый диапазон параметра, основанный на распределении сходящейся популяции; (В) — второй сокращённый диапазон.

3.4. Динамические границы

Рассмотрим динамические границы. Для прекращения работы ГА следует достичь стационарной точки без улучшения пригодности в нескольких последовательно проходящих генерациях. Это случается или когда найдено оптимальное решение или шаг мутации слишком велик в сравнении с различием между оптимальным решением и решением схождения. Чтобы удостовериться, что сходящееся решение достаточно близко к глобальному оптимуму, была использована стратегия подобная представленной в ссылке [19], После схождения ГА мы снова применили ГА с уменьшенным пространством решения, что эффективно дало второму процессу меньший шаг мутаций. И решение было ближе к глобальному оптимуму, чем при первом. Этот итеративный процесс был повторён до исчезновения улучшения пригодности популяции.

Чтобы определить подходящее пространство решения для каждого итеративного шага ГА, мы предполагали, что популяция будет попадать в или около окрестности глобального оптимума, как только ГА сходится. Следовательно, гены в сходящейся популяции могут быть использованы для определения уменьшения пространства решений, т.е. нового диапазона параметров. Мы предположили новый диапазон параметров, содержащий все хромосомы сходящейся популяции. Рис.6 показывает такой процесс. Тем не менее, процесс динамических границ имеет значимость для точной подстройки решения, но не для поиска окрестности глобального оптимума. Т.е. он не сможет помочь выбраться из окрестности локального оптимума, чтобы достигнуть глобального. Полный динамический ГА показан на рис.7. После создания популяции с N хромосомами были сгенерированы 2 группы новых потомков: первая сгенерирована как с помощью скрещивания, так и динамической мутацией, в то время как другая сгенерирована только с помощью динамической мутации. Следующее поколение сформировано двумя группами хромосом: половина сгенерирована скрещиванием, а половина только мутацией или из предыдущего поколения. Такая селекция пытается получить как механизм дальнего поиска, так и ближнего, чтобы сбалансировать эффект исследования и эксплуатации. Процесс воспроизводства будет продолжаться, пока пригодность вновь сгенерированной популяции не улучшится для числа итераций. Если это случилось, мы применяем шаг динамических границ для уменьшения пространства поиска и снова применяем генетический поиск. Если рассматривать полный процесс, то весь процесс останавливается, если дальнейшее уменьшение пространства поиска и генетический поиск не дают лучшего решения.

блоксхема предложенного генетического алгоритма
Рис. 7. — Потоковая блоксхема предложенного генетического алгоритма.

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

4.1. Построение модели

Проведём обзор экспериментальных результатов. Чтобы показать построение модели, оценим сначала эффективность системы разработки для мультиракурсной (т.е. для нескольких видов) интеграции и реконструкции объёмной модели. Чтобы измерить точность процесса реконструкции, соответствие глубины изображения к ряду изображений, взятых с различных направлений, было сгенерировано с компьютерной модели, взятой из [20]. Эти исходные изображения показаны в первом ряду рис.8. Виды были интегрированы с использованием разработанного алгоритма регистрации поверхности. Если число видов достаточно велико, может быть реконструирована полная модель. С помощью интегрирования исходных изображений был получен второй ряд на рис. 8.

В Таблице 2 показано время обработки и ошибки регистрации поверхности во время эксперимента. Были проведены три процесса регистрации для отображения исходных изображений к изображениям-результатам. С нахождением трансформаций регистрации получена модель. И она по сравнению с моделью-оригиналом дала ошибку моделирования около 0,5% размера модели. Во время регистрации случайно выбирались 300 точек из исходного изображения. Все процессы выполнялись на платформе ПК c процессором Pentium II 450 МГц. Время обработки более 3 минут.

Таблица 2.
Время регистрации и значение пригодности сходимости во время реконструкции модели из изображений с рис.8.
Исходное изображениеЦелевое изображениеВремя обработки
(с)
Лучшее значение пригодности
к сходимости
21540,875
32511,043
43530,988


Исходное
изображение 1
Исходное
изображение 2
Исходное
изображение 3
Исходное
изображение 4

Созданная модель
с вида 1
Созданная модель
с вида 2
Созданная модель
с вида 3
Созданная модель
с вида 4

Рис. 8. — Результаты эксперимента по построению из незашумлённых изображений компьютерной модели черепа.


4.2. Чувствительность к шуму

Теперь покажем чувствительность алгоритма к шуму. В этом эксперименте была оценена чувствительность к шуму процесса синтеза предложенной модели. Как в прошлом эксперименте, мы генерировали соответствие глубины изображения к ряду изображений, полученных с разных направлений от другой компьютерной модели, взятой из [20]. Эти изображения на рис. 9. Перед экспериментами к изображениям добавляли гауссовский шум с различными уровнями. Если предложенный процесс реконструкции ясен, то должна быть получена модель с ошибкой, сравнимой с шумом. Статистика по времени обработки и ошибки моделирования приведены в Таблице 3:

Таблица 3.
Результаты эксперимента по чувствительности процесса воссоздания модели к шуму
Уровень шума (%)Время моделирования (с)Ошибка моделирования (%)
0,51840,53
1,02010,83
2,02421,25

Реконструированные модели на рис. 10-12. Эксперимент показал, что ошибки моделирования около и даже меньше уровня шума исходных изображений. Следовательно, представленный алгоритм относительно нечувствителен к шуму. Эксперименты с бóльшим добавленным уровнем шума не выполнялись из-за того, что изображения с 2% шумом уже существенно искажены по сравнению с теми, которые ожидаются от системы захвата хорошего класса.

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


4.3. Получение моделей реальных изображений

А теперь рассмотрим получение моделей реальных изображений. Для экспериментов из [21] был скачан полный набор изображений. Исходные изображения на рис. 13, а изображения из ряда соответствия на рис. 14. Время регистрации соответствий и ошибок в Таблице 4. После конструирования модели могут были получены новые изображения с модели. Четыре таких вида воссозданной модели показаны на рис.15. Процесс построения соответствий занял 3 минуты на ПК c процессором Pentium II 450 МГц. Результаты показывают, что процесс, по-видимому, является эффективным и быстрым.

Таблица 4.
Время регистрации и значение пригодности сходимости во время реконструкции модели по изображениям из рис.14.
Исходное изображениеЦелевое изображениеВремя обработки
(с)
Лучшее значение пригодности
к сходимости
21611,54
32581,59
43641,69


Исходное
изображение 1
Исходное
изображение 2
Исходное
изображение 3
Исходное
изображение 4

Рис. 9. — Исходный ряд изображений модели позвоночника.

5. Итоги

В этой работе описана точная система для регистрации поверхности произвольных форм, основанная на генетическом алгоритме [22]. Благодаря характеристикам ГА, разработанная система не зависит от хороших начальных предположений решения. Предшествующая информация по соответствиям или точкам характерных особенностей также не является необходимой, и нет чувствительности к шуму и загораживанию поверхностями данным.

Один из вкладов этой работы состоит в предложении новой функции пригодности. Тем не менее, формулировка функции пригодности ведёт к сильной вычислительной нагрузке. Чтобы ускорить процесс, исходные изображения были жёстко выбраны случайным образом, и был подобран быстрый метод поиска соответствий в целевом изображений. После этого процесс ускорился как минимум в 1000 раз для регистрации поверхностей с десятками тысяч точек данных без потери точности. Другим важным шагом стало предложение использовать «Адаптивную Мутацию» для дальнейшего ускорения процесса. Система была исследована большим числом моделей и все процессы построения моделей могут быть завершены с приемлемыми отклонениями. К примеру, составление модели по четырём видам требует всего 5 минут на ПК c процессором Pentium II 450 МГц.

Полученная модель
с видом 1
Полученная модель
с видом 2
Полученная модель
с видом 3
Полученная модель
с видом 4
Полученная модель
с видом 5
Полученная модель
с видом 6

Рис. 10 — различные виды восстановленной модели с добавленным 0,5% гауссовым шумом к исходному изображению, показанному на Рис. 9.


Полученная модель
с видом 1
Полученная модель
с видом 2
Полученная модель
с видом 3
Полученная модель
с видом 4
Полученная модель
с видом 5
Полученная модель
с видом 6

Рис. 11 — различные виды восстановленной модели с добавленным 1% гауссовым шумом к исходному изображению, показанному на Рис. 9.


Полученная модель
с видом 1
Полученная модель
с видом 2
Полученная модель
с видом 3
Полученная модель
с видом 4
Полученная модель
с видом 5
Полученная модель
с видом 6

Рис. 12 — различные виды восстановленной модели с добавленным 2% гауссовым шумом к исходному изображению, показанному на Рис. 9.



1 исходный кадр2 исходный кадр 3 исходный кадр4 исходный кадр

Рис. 13 — исходные изображения для построения модели.



1 изображение
входного ряда
2 изображение
входного ряда
3 изображение
входного ряда
4 изображение
входного ряда

Рис. 14 — соответствующие изображения ряда, показанные на Рис. 13 для конструирования модели.



Составленная модель с видом 1Составленная модель
с видом 2
Составленная модель
с видом 3
Составленная модель
с видом 4

Рис. 15 — синтезированные виды из построенной модели при использовании ряда изображений, показанных на Рис. 14.


Благодарности

Эта статья была создана при частичной поддержке RGC Central Allocation Grant CUHK1/00C.


ЛИТЕРАТУРА И ССЫЛКИ

[1] C. Dorai, G. Wang, A.K. Jain, C. Mercer, Registration and integration ofmultiple object views for 3D model construction, IEEE Trans. Pattern Anal. Machine Intell. 20 (1) (1998) 83–89.

[2] P. Eisert, E. Steinbach, B. Girod, Automatic reconstruction ofstationary 3-D objects from multiple uncalibrated camera views, IEEE Trans. Circuits Systems Video Technol. 10 (2) (2000) 261–277.

[3] Li-Yueh Hsu, M.H. Loew, Automated registration ofCT and MR brain images using 3-D edge detection, in: Proceedings of the 20th Annual International Conference IEEE Engineering in Medicine and Biology Society, Vol. 2, 1998, pp. 679–682.

[4] V. Charvillat, B. Thiesse, Registration ofstereo-based 3D maps for object modeling: a stochastic yet intelligent solution, in: Proceedings ofthe 13th International Conference on Pattern Recognition, Vol. 1, 1996, pp. 780–785.

[5] T. Masuda, K. Sakaue, N. Yokoya, Registration and integration ofmultiple range images for 3-D model construction, in: Proceedings ofthe 13th International Conference on Pattern Recognition, Vol. 1, 1996, pp. 879–883.

[6] P.J. Besl, N.D. McKay, A method for registration of 3-D shapes, IEEE Trans. Pattern Anal. Machine Intell. 14 (2) (1992) 239–256.

[7] G. Blais, M.D. Levine, Registering multiview range data to create 3D computer objects, IEEE Trans. Pattern Anal. Machine Intell. 17 (8) (1995) 820–824.

[8] T. Masuda, N. Yokoya, A robust method for registration and segmentation ofmultiple range images, in: Proceedings ofthe Second Workshop on CAD-Based Vision, 1994, pp. 106–113.

[9] S.M. Yamany, A.A. Farag, Free-form surface registration using surface signatures, in: Proceedings of the Seventh IEEE International Conference on Computer Vision, Vol. 2, 1999, pp. 1098–1104.

[10] C. Schutz, T. Jost, H. Hugli, Multi-feature matching algorithm for free-form 3D surface registration, in: Proceedings of the 14th International Conference on Pattern Recognition, Vol. 2, 1998, pp. 982–984.

[11] A.E. Johnson, M. Hebert, Surface registration by matching oriented points, in: Proceedings ofthe International Conference on Recent Advances in 3-D Digital Imaging and Modeling, 1997, pp. 121–128.

[12] W.R. Fright, A.D. Linney, Registration of3-D head surfaces using multiple landmarks, IEEE Trans. Med. Imaging 12 (3) (1993) 515–520.

[13] S.M. Yamany, M.N. Ahmed, E.E. Hemayed, A.A. Farag, Novel surface registration using the Grid Closest Point (GCP) Transform, in: Proceedings of the 1998 International Conference on Image Processing (ICIP 98), 1998, pp. 809–813.

[14] K. Brunnstrom, A.J. Stoddart, Genetic algorithms for free-form surface matching, in: Proceedings of the 13th International Conference on Pattern Recognition, Vol. 4, 1996, pp. 689–693.

[15] A.M. Eldeib, S.M. Yamany, A.A. Farag, Multi-modal medical volumes fusion by surface matching, in: Proceedings of the Fifth International Symposium on Signal Processing and Its Applications (ISSPA’99), Vol. 1, 1999, pp. 439–442.

[16] Doo-Hyun Choi, Se-Young Oh, A new mutation rule for evolutionary programming motivated from Backpropagation Learning, IEEE Trans. Evol. Comput. 4 (2) (2000) 188–190.

[17] Xin Yao, Global optimisation by evolutionary algorithms, in: Proceedings ofthe Second International Symposium Parallel Algorithms/Architecture Synthesis, 1997, pp. 282–291.

[18] M. Vanco, G. Brunnett, T. Schreiber, A hashing strategy for eOcient k-nearest neighbors computation, in: Proceedings of the International Conference Computer Graphics, 1999, pp. 120–128.

[19] C.K. Chow, H.T. Tsui, T. Lee, Optimization on unbounded solution space using dynamic genetic algorithms, in: Proceedings ofthe International Joint Conference on Neural Networks, July 2001, Vol. 4, pp. 2349–2354.

[20] http://www.3dcafe.com/asp/meshes.asp.

[21] http://sampl.ing.obio-state.edu/~sampl/data/3DDR/RID/minolta.

[22] D.E. Goldberg, Genetic Algorithms in Search Optimization and Machine Learning, Addison-Wesley, Reading, MA, 1989.


ПЕРЕМЕННЫЕ В СТАТЬЕ

  • α — поворот вокруг оси х — ген поворота по x.
  • β — поворот вокруг оси y — ген поворота по y.
  • θ — поворот вокруг оси z — ген поворота по z.
  • E — целевая функция расстояний между точками от преобразованного исходного изображения и целевого изображения, минимум которой ищем для решения задачи. Иначе говоря функция энергии в оптимизационной задаче.
  • СМSi — хромосома.
  • FIT(СМSi) — пригодность родительской хромосомы СМSi.
  • MV — шаг мутации ±MV.
  • N1 — число точек поверхности на исходном изображении.
  • N2 — число точек поверхности на целевом изображении.
  • P — точка исходного изображения.
  • Q — точка целевого изображения.
  • Rx — матрица поворота вокруг оси х.
  • Ry — матрица поворота вокруг оси y.
  • Rz — матрица поворота вокруг оси z.
  • S1 — исходное изображение.
  • S2 — целевое изображение.
  • SS1 — подобразец поверхности на исходном изображении.
  • T — евклидова трансформация между двумя поверхностями, содержащая три переноса по трём осям пространства и три поворота вокруг них.
  • Tx — смещение вдоль оси х — ген переноса по x.
  • Ty — смещение вдоль оси y — ген переноса по y.
  • Tz — смещение вдоль оси z — ген переноса по z.
  • x — ось x в пространстве объектов.
  • y — ось y в пространстве объектов.
  • z — ось z в пространстве объектов.

посещений Счетчик посещений Counter.CO.KZ - бесплатный счетчик на любой вкус!