[101 ԋε]Ֆᒏ Manchester encoding?ՖᓬલᗺǶ Ƞเ();pdf

Синтез панорамных изображений с использованием метода SIFT и
кластеризующего слоя Кохонена
Загидуллин Б.А., Бочкарев В.В.
Казанский федеральный университет
[email protected]
Аннотация
В
данной
статье
описывается
автоматизированный
алгоритм
синтеза
панорамных изображений. Проблема синтеза
включает распознавание того, как нужно
соединить изображения, чтобы получить
панораму. В работе поэтапно описываются все
процедуры синтеза панорамного изображения.
Алгоритм базируется на использовании метода
SIFT для поиска соответствующих точек между
изображениями.
Данный
метод
является
инвариантным к изменениям масштаба, яркости
изображений
и
поворотам. Для оценки
параметров
модели
геометрического
преобразования между изображениями в работе
предложен новый способ робастной оценки с
совместным применением метода RANSAC и
кластеризующей нейронной сети со слоем
Кохонена.
1. Введение
Тема синтеза панорамных изображений
широко охвачена в литературе. Одна из основных
задач при синтезе панорамы – это поиск
соответствий
и
оценка
геометрического
преобразования между изображениями. Основное
внимание в исследовательской литературе по
методам автоматического поиска соответствий
между изображениями
уделяется методам
основанным на поиске особых ключевых точек
(ОКТ) [1-5]. По этим ОКТ ведется поиск
соответствии между изображениями. В данной
работе для поиска особых ключевых точек
использовался метод SIFT (Scale Invariant Feature
Transform). Использование метода SIFT также
обусловлено тем, что точки найденные этим
методом инварианты к смещениям, поворотам,
масштабированию, а также частично к изменению
яркости.
Оценка
матрицы
геометрических
преобразований (ГП) ведется по минимизации
квадрата ошибки [8, 11]. Однако, из-за
присутствия шумов могут возникать ложные
соответствия особых точек, определенных по
методу SIFT и, следовательно, не все данные
будут удовлетворять модели ГП. В таких случаях
применяется
методы
робастной
оценки
параметров модели на основе случайных выборок
[9, 10]. Такой метод получил название RANSAC
(Random Sample Consensus), и имеют широкое
применение в обработке изображений. В данной
работе представляются результаты подхода для
устойчивой оценки с совместным использованием
метода RANSAC и кластеризующего слоя
Кохонена (КСК).
Алгоритм автоматического синтеза панорам,
описанный в статье,
использовался для
склеивания изображений высокого разрешения
гистологических срезов живой ткани, полученных
с оптического микроскопа Nikon eclipse e200.
Далее в качестве примеров будут использованы
изображения с данного микроскопа.
2.
Общий
панорамы
алгоритм
построения
Процесс автоматического синтеза панорамных
изображений, описанный в работе можно
разделить на несколько главных этапов: 1) Поиск
особых ключевых точек на каждом изображении
по методу SIFT, 2) определение соответствующих
ОКТ между изображениями, 3) оценка матрицы
ГП между связанными изображениями по методу
RANSAC и КСК, 4) Попарное склеивание
изображения по оцененному ГП до получения
конечного панорамного снимка.
407
Рисунок 1. Общая схема синтеза панорамы из
набора перекрывающихся изображений.
3. Поиск особых точек по методу SIFT
Давид Лоуве (David G.Lowe) [5] предложил
алгоритм для выделение особых точек, инвариантных к
изменению масштаба, поворотам, изменению яркости и
положению камеры. Такой алгоритм получил название
SIFT (Scale Invariant Feature Transform). Основным
моментом в детектировании ОКТ по методу SIFT
является построение пирамиды гауссианов и разностей
гауссианов. Гауссианом называется изображение
размытое гауссовым фильтром. Операцию размытия
можно представить в виде свертки изображения
гауссовым ядром:
L ( x, y , σ ) = G ( x, y , σ ) * I ( x, y )
Рисунок 2. Построение пирамиды разности
гауссианов.
Доказано,
что
гауссово
масштабируемое
пространство является линейным, инвариантным
относительно сдвигов, вращений, масштаба, не
смещающим локальные экстремумы. Масштабируемым
пространством
изображения
является
набор
всевозможных, сглаженных некоторым фильтром
версий исходного изображения [14].
(1)
где: x, y - координаты пикселей.
σ - радиус размытия
L( x, y, σ ) - гауссиан, размытое изображение
G ( x, y, σ ) - гауссово ядро.
G ( x, y, σ ) = 1 /( 2πσ 2 ) exp − ( x
2
+ y2 ) /σ 2
Рисунок 3. Пример гауссианов и разности
гауссианов при различных значениях сигма.
(2)
Разностью гауссианов называют изображение,
полученное путем попиксельного вычитания одного
гауссиана с радиусом σ из соседнего гауссиана с
радиусом размытия kσ (Рисунок 2).
D ( x, y,σ ) = L( x, y, kσ ) − L( x, y, σ )
После построения пирамид начинается поиск ОКТ.
Точка считается особой, если она является локальным
экстремумом разности гауссианов [5].
(3)
Рисунок 4. Поиск локального экстремума в
пирамиде разности гауссианов.
408
В каждом изображении из пирамиды разности
гауссианов ищутся точки локального экстремума.
Каждая точка текущего изображения из пирамиды
сравнивается с ее восьмью и девятью соседями,
находящимися на уровень выше и ниже. Если точка
больше (меньше) всех соседей, то она принимается за
точку локального экстремума. Локальный минимум
еще не является особой точкой, требуются провести
еще несколько проверок пригодности точки на роль
ОКТ. Проверка точки на большой изгиб (одна из
компонент второй производной) [5].
Следующим шагом будет вычисление ориентации
ОКТ. Направление вычисляется исходя их направлений
градиентов точек, соседних с особой. Все вычисления
градиентов производятся на изображении в пирамиде
гауссианов, с масштабом наиболее близким к масштабу
ключевой точки.
m( x, y ) = ( L( x + 1, y ) − L( x − 1, y )) 2 + ( L( x, y + 1) − L( x, y − 1)) 2
Рисунок 5. Дескриптор особой точки. Градиенты и
их направление пикселей (слева), сформированный
дескриптор особой точки (справа).
(4)
θ ( x, y ) = arctg (( L ( x, y + 1) − L( x, y − 1)) /( L ( x + 1, y ) − L( x − 1, y ))) (5)
−1
m( x, y ) - величина градиента в точке
θ ( x, y ) - направление градиента
Окрестность ОКТ, в которой будут рассмотрены
градиенты, определяется по правилу «трех сигм».
Радиус окрестности определяется как 3σ , так как
значение гауссова ядра близко к нулю на этом
расстоянии.
Направление ОКТ находится из гистограммы
направлений. Гистограмма состоит из 36 компонент
[5], которые равномерно покрывают промежуток в 360
градусов.
Каждый
градиент
вносит
вклад
m( x, y ) * G ( x, y, σ ) в ту компоненту гистограммы,
которая
покрывает
промежуток,
содержащий
направление θ ( x, y) .
4. Дескрипторы особых точек
После определения локальных особых точек,
необходимо
определить
какая
точка
одного
изображения соответствует особой точке другого
изображения. Дескриптор – идентификатор особой
точки, выделяющий ее из остальной массы особых
точек. Для того чтобы дескриптор обеспечил
инвариантность нахождения соответствия между
точками, выбирается небольшая окрестность около
ОКТ, так как на маленькие области меньшее влияние
оказывают эффекты искажений. Дескриптором в
методе SIFT [5] является вектор. Как и направление
особой точки дескриптор вычисляется на гауссиане,
ближайшем по масштабу. Перед вычислением
дескриптора окно поворачивается на угол направления
ключевой точки, чем и достигается инвариантность
относительно поворота.
409
Рисунок 6. Несколько соответствующих ОКТ на
двух изображениях.
Вычисление дескрипторов ведется в той же
окрестности, что и ориентация ОКТ (рисунок 5,
круговая область). Окрестность делится на 4x4
регионов и для каждого региона вычисляется
распределение гистограммы в 8 направлениях. В итоге
каждый дескриптор ОКТ содержит 4x4x8 элементов.
В конце полученный дескриптор нормализуется, что
дает устойчивость к изменениям яркости.
Поиск
соответствующих
точек
(ОКТ)
на
изображениях осуществлялся через вычисление
евклидова расстояния между дескрипторами всех ОКТ.
Пример найденных соответствующих точек можно
увидеть на рисунок 6.
5. Оценка матрицы
преобразования
геометрического
Для вычисления нового положения пикселей
изображения B относительно изображения А,
необходимо сделать оценку матрицы
аффинного
преобразования, так как изображения полученные с
микроскопа
подвержены
только
аффинным
преобразованиям.
Имеется множество точек соответствия x и
 xi 
 x'i 
 
 
x i =  yi  , x'i =  y 'i  .
1
1
 
 
x'
(6)
xi , yi - координаты точек соответствия.
Аффинная трансформация в матричном запишется как:
(7)
x' = A ⋅ x
Окончательно, на выходе сигнал с номером
j max = arg max{K j } равен единице, остальные - нулю. Из
A - матрица аффинного преобразования 3x3.
 a b c


A = d f e
 0 0 1


j
(8)
Оценка параметров матрицы A осуществляется по
минимизации квадрата ошибки [8, 11]:
min A ⋅ x − x'
Так как аффинные
линейными, то:
2
преобразования
(9)
являются
A = x ⋅ x'−1
(10)
6. Нейронная сеть со слоем Кохонена
Самоорганизующийся слой Кохонена [12, 13] –
класс нейронных сетей, основным элементом которых
является слой Кохонена. КСК – это соревновательная
сеть с алгоритмом обучения «без учителя». Выходные
сигналы слоя Кохонена обрабатываются по правилу
«победитель забирает все»: наибольший сигнал
превращается в единичный, остальные обращаются в
нуль. Слой Кохонена состоит из некоторого количества
параллельно действующих линейно – адаптивных
сумматоров (в работе использовано количество
нейронов равно 7).
Рисунок 7. Пример организации сети Кохонена.
Нейрон Ki, взвешенная сумма которого наибольшая,
объявляется победителем для данного входного
вектора X.
Нейроны самоорганизующейся сети могут быть
обучены выявлению групп (кластеров) векторов входа
обладающих общими свойствами. Общий принцип
работы слоя Кохонена выглядит следующим образом,
после подачи на вход вектора x = ( x1 ,.....x m ) на
выходе линейного элемента получается сигнал
m
K j = w j 0 + ∑ wij xi
(11)
i =m
w ji -весовой коэффициент i - го входа j - го нейрона
w j 0 - пороговый весовой коэффициент.
410
описанного выше можно сделать вывод, что нейрон с
номером j max определяет ту группу (кластер), к которой
наиболее близок входной вектор.
Правило обучения слоя Кохонена [12], заключается
в том, чтобы настроить нужным образом элементы
матрицы весов. Пусть нейрон j победил при подаче
входа p(q ) на шаге самообучения q , тогда веса
нейрона
j корректируется в
рекуррентным правилом Кохонена:
соответствии
W j(q ) =W j(q − 1) + α ( p (q ) −W j(q − 1))
с
(12)
В конечном счете, если в слое имеется достаточное
количество нейронов, то каждая группа близких
векторов окажется связанной с одним из нейронов.
7. Определение ГП с помощью метода
RANSAC и кластеризующих нейронных
сетей
В работах по синтезу панорамных изображении
[1-3] для оценки параметров геометрического
преобразования по набору особых точек применялся
метод RANSAC [9, 10]. Это робастный метод оценки
параметров модели на основе случайных выборок.
Однако, соответствие ОКТ на изображениях не всегда
определяется точно. Причиной этого может быть
зашумленность исходных данных, несовершенство
дескрипторов ОКТ, разница масштабов изображений.
Эти и другие факторы сказываются на точности оценки
модели ГП. Из сказанного выше весь набор найденных
ключевых точек можно разделить на два типа: хорошие
точки, удовлетворяющие оцененной модели и ложные
точки.
В данной работе предлагается новый метод с
совместным использованием метода RANSAC и
кластеризующего
слоя
Кохонена.
Оцененные
параметры модели ГП на каждом шаге итерации
передаются в КСК с 7 нейронами и 6 входами. В ходе
обучения по правилу Кохонена происходит настройка
весовых коэффициентов нейронной сети таким
образом, что веса нейрона определяют характерные
параметры ГП для определенного кластера. Нейрон,
весовые коэффициенты которого дают наименьшую
абсолютную ошибку ГП для двух изображений,
объявляется наилучшим модельным преобразованием.
Для сравнения двух подходов устойчивой оценки
построены распределения плотности вероятности
ошибки рис.8а и суммарная вероятность ошибки рис.8б
в пределах ошибки до 2 пикселей. Как видно по обоим
графикам величина ошибки уменьшается для метода с
совместным использовании RANSAC и КСК,
следовательно, можем сделать вывод, что данный
подход дает оценку более точной модели.
Рисунок 8а. Плотность распределения вероятности
ошибки.
Рисунок 8б. Интегральная функция распределения
ошибки.
8. Примеры синтезированных панорам
Рисунок 9а: Пример панорамы гистологического
среза из 14 изображений.
Заключение
Рисунок 9а: Пример панорамы гистологического
среза из 4 изображений.
411
В работе описано применение нового метода
основанного на совместном использовании метода
оценки
параметров
модели
RANSAC
и
кластеризующего слоя Кохонена. Использование
метода дало уменьшение ошибки
при оценке
параметров
геометрического
преобразования
и
позволило
получить
более
точную
склейку
панорамного изображения. Также были представлены
все этапы синтеза панорамных изображении. В
качестве примера рассмотрено применение алгоритма
на снимках гистологических срезов, полученных с
оптического микроскопа Nikon eclipse e200.
Список литературы
[1] M. Brown and D. G. Lowe. Recognising Panoramas. Ninth
IEEE International Conference on Computer Vision (ICCV’03) –
Volume 2, 2003.
[2] M. Brown, R. Szeliski, S. Winder. Multi-Image Matching
using Multi-Scale Oriented Patches. Microsoft Research
[3] R. Szeliski. Image Aligment and Stitching: A Tutorial.
Microsoft Research, 2004.
[4] R. Szeliski and H.-Y. Shum. Creating full view panoramic
image mosaics and environment maps. Computer Graphics,
31(Annual Conference Series):251-258, 1997.
[5] D. G. Lowe. Distinctive Image Features from Scale-Invariant
Keypoints. Computers Science Department University of British
Columbia Vancouver, 2004.
[6] P. J. Burt and E. H. Adelson. A multiresolution spline with
application to image mosaics. ACM Transactions on Graphics,
2(4):217-236, 1983.
[7] D. Capel and A. Zisserman. Automated mosaicing with superresolution zoom. In Proceedings of the International Conference
on Computer Vision and Pattern Recognition, pages 885-891,
June 1988.
[8] B. Leibe. Object Recognition with Local Features. Computer
Vision – Lecture 12.
http://www.vision.ee.ethz.ch/~bleibe/multimedia/teaching/cvws08
[9] M. A. Fischler and R. C. Bolles. Random sample consensus: A
paradigm for model fitting with applications to image analysis
and automated cartography. Comm. Assoc. Comp. Mach.,
24(6):381–395, 1981.
[10] А. Конушин. Устойчивые алгоритмы оценки
параметров модели на основе случайных выборок.
http://cgm.computergraphics.ru/content/view/47
[11] M. Magnor. Computer Graphics II – Camera Geometry.
2005.
[12] Kohonen T. Self-Organization Maps, Second Edition, Berlin:
Springer-Verlag. 1997.
[13] В.В. Круглов., В.В. Борисов Искусственные нейронные
сети, Москва. 2001.
[14] J. Bauhad, A.P. Witkin, M. Baudin, R.O. Duda Uniqness of
the Gaussian kernel for scale-space filtering, IEEE Transactions
on Pattern Analysis and Machine Inteligence, 1986.
412