close

Вход

Забыли?

вход по аккаунту

?

Стыковка фрагментов изображения по многооткликовой модели контурной линии.

код для вставкиСкачать
2015
ВЕСТНИК НОВГОРОДСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА
№8(91)
УДК 004.93:519.6
СТЫКОВКА ФРАГМЕНТОВ ИЗОБРАЖЕНИЯ
ПО МНОГООТКЛИКОВОЙ МОДЕЛИ КОНТУРНОЙ ЛИНИИ
А.C.Наумов
IMAGE FRAGMENT MATCHING USING MULTIRESPONSE CONTOUR LINE MODEL
A.S.Naumov
Политехнический институт НовГУ, alex.naumov53@mail.ru
Представлен метод поиска стыков между фрагментами изображения произвольной формы, использующий для
описания и сравнения геометрических и цветовых характеристик контурной линии многооткликовую кусочно-линейную модель
сегмента. Особенностью метода является совместное использование геометрической и цветовой информации. Показан
статистический критерий сравнения сегментов. При общей универсальности метода на уровне математической и
концептуальной модели обеспечивается гибкость и вариативность его применения за счет выбора оптимального количества
откликов модели и способа идентификации сегментов. Метод применим в широком спектре задач в области анализа и
реконструкции изображений из фрагментов.
Ключевые слова: геометрический контур, цветовой контур, многооткликовая модель, линейная функция, кусочнолинейная аппроксимация, совмещение контуров, расстояние Махаланобиса
This article proposes a method for arbitrary shaped image fragments matching, which uses multiresponse piecewise linear
segment model for contour description and comparing. Key feature of the method includes joint use of geometrical and color features of
the contour line. Statistical criterion for image comparison is presented. The method provides universality on the conceptual and
mathematical level wherein flexibility and variability in practical cases because the number of response variable and segment
identification method can be changed. The method is suitable for various applications in the field of image analysis and fragment
matching.
Keywords: geometric contour, color contour, multiresponse model, linear function, piecewise-linear approximation, contour
matching, Mahalanobis distance
тура, обеспечивает широкие возможности по адаптации его к различным типам исходных материалов.
1. Введение
Задача автоматизированной стыковки плоских
фрагментов как часть процесса реконструкции фрагментированных изображений востребована в криминалистике, археологии, реставрации и других прикладных областях. Для ее решения, в частности, требуется
создание методов описания и сравнения характеристик
контурной линии, позволяющих локализовывать области стыка изображений фрагментов. Под геометрическим контуром будем понимать линию, обозначающую границу фрагмента и являющуюся характеристикой формы, а под цветовым — размещение цветовой
информации вдоль границы фрагмента.
В работах [1,2] автором проанализированы
особенности известных подходов к описанию и сравнению контуров, в результате чего сделан вывод об
их недостаточной эффективности применительно к
рассматриваемой задаче. Известные методы в большинстве своем являются эмпирическими, слабо обоснованными математически и ориентированными на
узкие задачи, базирующиеся на конкретных примерах. Внимание уделяется в основном геометрическим
характеристикам, не предложено удобных и эффективных способов работы с цветовым контуром.
Для преодоления указанных недостатков автором разработан новый метод описания и сравнения
контуров, использующий линейную многооткликовую статистическую модель. Метод использует геометрическую и цветовую информацию в единой модели, позволяет получать достоверное описание кон-
2. Многооткликовая модель контура
В работе [3] автором был представлен метод
описания геометрического и цветового контура фрагмента трехоткликовой линейной моделью. Для использования в задаче стыковки фрагментов изображения
метод обобщается на произвольное число зависимых
переменных и дополняется механизмом, обеспечивающим инвариантность полученного описания к преобразованиям сдвига и поворота фрагментов.
На рис.1. показан пример контура объекта. Исходная информация о каждой его точке представлена
вектором, включающим в себя одну независимую и k
зависимых переменных (откликов). Число откликов
определяется спецификой задачи и в типичном случае
равно 5:2 геометрические координаты (x и y) и 3 координаты в цветовом пространстве (например, RGB). В
качестве независимой переменной используется расстояние вдоль контура с, рассчитываемое относительно начальной точки описания следующим образом:
i
ci 

( xi  xi1) 2  ( yi  yi1)2 или, иначе,
j1
ci  ci1  (xi  xi1)2  ( yi  yi 1)2 ,
(1)
где i 1, n, n — общее число точек контура, xi и yi —
геометрические координаты i-й точки, xi1 и yi1 —
соответственно i–1-й точки, c0  0. Параметризация
11
2015
ВЕСТНИК НОВГОРОДСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА
№8(91)
контура от расстояния позволяет избежать проблем с
аппроксимацией вертикальных линий и в дальнейшем
обеспечить инвариантность описания. Таким образом,
для модели с 5 откликами в цветовом пространстве
RGB вектор описания i-й точки имеет вид:
ci , xi , yi , ri , gi , biT , где ci — независимая переменная,
xi , yi — геометрические переменные, ri , gi , bi — цветовые.
Рис.2. Пример аппроксимации сегмента контура для случая
одной переменной. Значение независимой переменной ci+1
соответствует точке излома (границе линейных участков Yi и
Yi+1)
Алгоритм описания контура и поиска точек излома представлен в работе [3]. Поиск точек излома
сводится к последовательному обходу контура и проверке статистического критерия о принадлежности
текущей группы точек модели предыдущего участка.
При отклонении гипотезы текущая точка принимается за точку излома, и начинается расчет нового линейного участка. Процесс заканчивается при обходе
всего контура. Отсчет независимой переменной (1)
начинается заново от каждой точки излома. Поиск
точек излома выполняется либо по геометрическому,
либо по цветовому контуру. Если характер фрагментов в конкретной задаче не предполагает ярко выраженных углов и цветовых переходов, то используется
равномерная аппроксимация [2], где точки излома
располагаются на некотором заданном расстоянии.
Несколько последовательных участков аппроксимации и относящихся к ним точек излома образуют
сегмент (рис.2).
Рис.1. Геометрические координаты как функция расстояния
вдоль контура. Точка с0 = 0 — начальная точка отсчета; x(с0),
y(с0) — соответствующие значения координат
Контур аппроксимируется кусочно-линейной
функцией, участки которой начинаются и заканчиваются в точках излома. Многооткликовая, линейная по коэффициентам модель линейного участка контура изображения представляется в виде векторной функции
Yij  PiTcij Bi  Ei ,
(2)
где i — номер участка, j 1, ni — номер точки на i-м
участке, ni — количество точек на i-м участке,
u
N
n
i
— полное количество точек контура фраг-
i1
3. Преобразование модели в инвариантный вид
T
мента изображения, Pi cij    f1cij , f 2 cij ,..., f k cij  —
функция, описывающая зависимость значений откликов
от
независимой
переменной
cij ,
Многооткликовая модель для цветовых переменных является инвариантной относительно сдвига и
поворота фрагментов, а за счет того, что значение независимой переменной c отсчитывается заново от каждой точки излома, она является инвариантной к выбору начальной точки описания. Таким образом, сравнение цветовых характеристик сегментов можно выполнять на уровне коэффициентов линейной модели.
Для геометрических переменных требуется
выполнить преобразование модели в инвариантный
вид. Для этого на основе оценок коэффициентов и
координат точек изломов рассчитываются:
1) длины линейных участков геометрического
контура;
2) углы между соседними линейными участками геометрического контура в точках излома.
При использовании в модели (2) двух откликов
(только геометрических переменных) вектор оценок
Yij  y1ij , y2ij ,..., y kij T — вектор значений откликов,
B i  b1i , b2i ,, b(2k )i T — вектор коэффициентов моде-
ли для i-го участка, Ei  e1i , e2i ,, ekiT — вектор остатков на i-м участке с ковариационной матрицей VEi .
Матрица P X для обобщенной модели i-го
участка принимает вид
 1 cij 0 0 ... 0 0 
 0 0 1 c ... 0 0 
ij


(3)
PiT cij   
,
...
...
...
...
...
...
...


 0 0 0 0 ... 1 cij 
где число строк равно числу откликов модели.
Оценки коэффициентов для i-го участка рассчитываются по методу наименьших квадратов [4] в виде:
Bˆ i  Gi1
коэффициентов имеет вид Bi  b1i , b2i , b3i , b4iT. Длина
участка между точками излома рассчитывается по
ni
 Pc Y ,
ij
ij
(4)
формуле Li  ( xi0  xim )2  ( yi  yi1)2 или после преобразования:
j 1
где матрица G i рассчитывается как
Li  (ci0  cim )2 (b2i 2  b4i2 ) ,
ni
Gi 
T
 Pc P c .
ij
ij
(6)
где Li — длина i-го участка, ci0 и cim — значения
независимой переменной в начальной и конечной
(5)
j 1
12
2015
ВЕСТНИК НОВГОРОДСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА
точке i-го участка, b2i и b4i — соответствующие
элементы вектора коэффициентов.
Угол между двумя прямыми на плоскости
k k
представляется выражением вида ai  arctg i1 i ,
1
  ki 1ki 
где ki и ki1 — соответствующие угловые коэффициенты прямых. С учетом используемой независимой
b
переменной ki  4i — угловой коэффициент i-го
b2i
b
линейного участка, ki1  4i1 — i+1-го участка. Пуb2i1
тем преобразования получаем выражение для угла
между двумя линейными участками
b b b b
ai  arctg 4i 1 2i 2i1 4i ,
(7)
 b2i 1b2i  b4i 1b4i 
где b2i и b4i — элементы вектора коэффициентов для iго участка, b4i1 и b2i1 — для i+1-го. Коэффициенты
двух последовательных участков контура не коррелированы, поэтому с учетом (12) выражение (9) примет вид:
2
2
 b2ib4i 
 cov(b2i , b4i ) 
 2
 2
22
 b2i  b4i  
i
2
i 1
i
2
xi


i
j
 x  x r  
2
i j
ij xi
xj ,

i
i

где B i — вектор коэффициентов только цветовых
переменных, получаемый из общего вектора коэффициентов путем вычеркивания первых четырех элементов, соответствующих геометрическим переменным.
Общая ковариационная матрица вектора A получается путем объединения матриц и имеет следующий вид:
[VA ] 0 
VA  
,
(16)
 0 [VB ]
где VB — ковариационная матрица коэффициентов
только для цветовых переменных, получаемая из
матрицы VB вычеркиванием первых четырех строк и
столбцов. При этом полагается отсутствие корреляционной связи между формой контура и цветом.
i

(13)
 b2i1b4i 1 
 cov(b2i1, b4i 1).
 2

2
22
 b2i 1  b4i1  
Таким образом, получим ковариационную
матрицу вектора A (8):
2 0 
VA   li 2 .
(14)
 0 ai 
Общий вектор описания участка в инвариантном виде с учетом цветовых переменных имеет вид:
T
A  (A )T , (B )T ,
(15)
Для
функции
нескольких
переменных
y  ( x1, x2 ,..., xn ) дисперсия рассчитывается [5] как
n
2
b4i1
b2i1

 2

 2

 b2i1  
 b4i 1 
2
2
2
2
 b2i 1  b4i1 
 b2i1  b4i1 
Расчет ковариационной матрицы вектора Ai
выполняется путем линеаризации выражений (6) и (7)
относительно коэффициентов в окрестности точки Bˆ .
  x  
2
b
 b



2a   2 4i 2  2b2i    2 2i 2  2b4i 
 b2i  b4i 
 b2i  b4i 
где i 1, n — номер линейного участка контура, b2i и
b4i — соответствующие элементы вектора коэффициентов для i-го участка, b4i1 и b2i1 — для i+1-го.
Для геометрического контура вектор описания
i-го участка имеет вид
Ai  Li , aiT.
(8)
2y 
№8(91)
(9)
где  2xi — дисперсия соответствующей переменной,
rij  xi  x j — ковариация двух переменных xi и x j.
Найдем частные производные выражения (6)
по коэффициентам:
L
b2 (cim  ci0 )2

;
b2
2
2
(cim  ci0 )2 (b2  b4 )
(10)
L
b4 (cim  ci0 )2

.
b4
2
2
(cim  ci0 )2 (b2  b4 )
Выполнив подстановку в (9) и преобразования
получим выражение для расчета дисперсии (6):
4. Сравнение сегментов
Для оценки близости двух сегментов используется величина, основанная на расстоянии Махаланобиса и выражаемая квадратичной формой
1 t
lij 
Aiq  A jq T VA1Aiq  A jq ,
(17)
t

(cim  ci0 )2 (b22b22  2 cov(b2, b4 )  b24b42 )
, (11)
b22  b42
где ci0 и cim — значения независимой переменной соответственно в начальной и конечной участка;
cov(b2 ,b4 ) — ковариация коэффициентов b2, b4. Оценки
коэффициентов и их ковариационная матрица известны.
Аналогичным образом рассчитывается дисперсия угла. Частные производные выражения (7) по
коэффициентам:
a
b4i
a
b

;
  2 2i 2 ;
(12)
b2i b2i 2  b4i2 b4i
b2i  b4i
a
b4i1
a
b2i1

;

,
2
2
2
2
b2i1

b
4i 1 b2i 1  b4i 1
b2i1  b4i1
2L 
q 1
где lij — мера близости i-го и j-го сегментов, t — количество линейных участков в сегменте, A iq — вектор описания для q-го линейного участка i-го сегмента, VA — средневзвешенная ковариационная матрица вектора A.
Для сравнения сегментов выполняется попарное
сравнение всех сегментов имеющихся фрагментов.
Сравнение можно выполнять как отдельно для геометрического и цветового контура, так и совместно.
Критическая величина l устанавливается из
тестовой выборки заведомо стыкующихся фрагментов. Для этого следует выбрать совокупность пар
13
2015
ВЕСТНИК НОВГОРОДСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА
фрагментов, вручную задать на них границы сегментов и точки излома, выполнить расчет моделей, после
чего для имеющихся стыков рассчитать значения
близости по формуле (17).
Оценка дисперсии величины lij для тестовой
выборки равна
2
1 t
l2 

lij  lij  ,
(18)
t 1
№8(91)
наращивания области стыка, представленным в работе [6].
6. Заключение
Разработан универсальный метод описания и
сравнения контуров изображений на основе многооткликовой линейной модели, который может быть использован в задаче стыковки фрагментов изображения произвольной формы. Метод позволяет использовать геометрические и цветовые характеристики
контурной линии в единой модели, что повышает
достоверность описания и сравнения контуров, а следовательно, эффективность процесса реконструкции
фрагментированных изображений. Единая модель
упрощает практическую реализацию программных
средств для реконструкции изображений и лишена
недостатков традиционных эмпирических подходов.
Разработанные методы имеют самостоятельную практическую ценность и могут быть использованы в широком спектре задач анализа изображений.
В настоящее время ведется внедрение разработки в
программную систему, предназначенную для реконструкции бумажных документов и керамических изделий.

j 1
где lij — среднее значение величины lij.
Объем тестовой выборки в практических задачах, как правило, ограничен и может не всегда достоверно отражать генеральную совокупность, поэтому
для построения доверительного интервала целесообразно использовать правило трех сигм.
Доверительный интервал для величины lij (17)
можно представить в виде:
lij  3l  lij  lij  3l.
(19)
Попадание величины lij в доверительный интервал позволяет полагать наличие стыка между
фрагментами.
5. Особенности реализации
В зависимости от специфики предлагаются
следующие варианты использования метода:
1. Только геометрический контур: 2 отклика —
координаты точек.
2. Только цветовой контур: 1-3 отклика — значения компонент либо только яркость.
3. Совместный контур: 3-5 откликов.
Возможны другие варианты.
1.
2.
3.
4.
5.
6.
Наумов А.С. Анализ методов описания контуров фрагментов при решении задачи синтеза изображения / НовГУ им. Ярослава Мудрого. 2010. Деп. в ВИНИТИ РАН
24.01.11, № 15-В2010.
Наумов А.С., Луций С.А. Формирование дескриптора
контурной линии в задаче синтеза изображения из фрагментов произвольной формы // Вестник НовГУ. Сер.: Естеств. и техн. науки. 2012. №68. С.68-74.
Наумов А.С., Попов С.А. Многооткликовая модель описания контура фрагмента изображения // Вестник НовГУ.
Сер.: Техн. науки. 2013. №75. Т.1. С.81-84.
Rencher Alvin C. Methods of Multivariate Analysis. A John
Wiley & Sons, Inc. Publication. Brigham Young University,
2002. 708 p.
Вентцель Е.С. Теория вероятностей. М.: Наука, 1969. 576 с.
Наумов А.С. Стыковка фрагментов изображения по геометрическому и цветовому контурам // Вестник компьютерных и информационных технологий. 2013. №9. C.16-21.
References
а)
1.
б)
Рис.3. Варианты определения сегментов контура: а) по угловым точкам; б) по характерному элементу (паттерну)
2.
Для каждой пары фрагментов сравниваются
все возможные комбинации сегментов, найденные
стыки запоминаются. Определение границ сегментов
выполняется вручную или с использованием какихлибо эвристических методов. Рассмотрим варианты
выделения сегментов:
1) имеются ярко выраженные сегменты, ограниченные угловыми точками и соответствующие всей
области разлома (рис.3а);
2) отсутствуют ярко выраженные углы либо
границы стыка не совпадают с ними, но имеются характерные паттерны формы или цвета (рис.3б), которые рассматриваются в качестве сегментов;
3) в прочих случаях сравнение может осуществляется методом скользящего окна [2] либо методом
3.
4.
5.
6.
14
Naumov A.S. Analiz metodov opisaniia konturov fragmentov
pri reshenii zadachi sinteza izobrazheniia [Contour description method analysis for the fragmented image reconstruction
problem]. NovSU, 2010. Dep. in VINITI RAS, January 24,
2011, no. 15-B2010.
Naumov A.S., Lutsii S.A. Formirovanie deskriptora konturnoi
linii v zadache sinteza izobrazheniia iz fragmentov proizvol'noi
formy [Forming of the contour descriptor for the problem of
image synthesis from fragments of a random shape]. Vestnik
NovGU. Ser. Tekhnicheskie nauki – Vestnik NovSU. Issue:
Engineering Sciences, 2012, no. 68, pp. 68-74.
Naumov A.S. Popov S.A. Mnogootklikovaia model' opisaniia
kontura fragmenta izobrazheniia [Multiresponse model of an
image contour description] Vestnik NovGU. Ser. Tekhnicheskie nauki – Vestnik NovSU. Issue: Engineering Sciences, 2013, no. 75, vol. 1, pp. 81-84.
Rencher A.C. Methods of Multivariate Analysis. John Wiley
& Sons Inc., Brigham Young University, 2002. 708 p.
Venttsel' E.S. Teoriia veroiatnostei [Probability theory].
Moscow, “Nauka” Publ., 1969. 576 p.
Naumov A.S. Stykovka fragmentov izobrazheniia po geometricheskomu i tsvetovomu konturam [Image fragment matching
using geometrical and color contours]. Vestnik komp'iuternykh
i informatsionnykh tekhnologii – Herald of computer and information technologies, 2013, no. 9, pp. 16-21.
Документ
Категория
Без категории
Просмотров
8
Размер файла
734 Кб
Теги
многооткликовых, линия, фрагменты, изображение, стыковки, модель, контурной
1/--страниц
Пожаловаться на содержимое документа