close

Вход

Забыли?

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

?

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

код для вставкиСкачать
Однако оно не покрывает все множество проективных преобразований. Поэтому целесообразно рассматривать 3 вида преобразований, а именно преобразования, отвечающие условиям b32z0, b33z0,
b31z0. Матрицы этих преобразований представимы
соответственно в виде:
УДК 519.713
МАТЕМАТИЧЕСКИЕ МОДЕЛИ
РАЗЛОЖЕНИЯ ПРОЕКТИВНЫХ
ПРЕОБРАЗОВАНИЙ В ЗАДАЧАХ
НОРМАЛИЗАЦИИ
?1
ЛЮБЧЕНКО В.А., ПУТЯТИН Е.П.
§ b11
Ё
Ё b 21
Ёb
© 31
Впервые рассматриваются модели разложения проективных преобразований на более простые: аффинные,
перспективы, центральное проектирование. Предлагается алгоритм нормализации для одного из разложений.
Распознавание образов ? одна из важнейших функций интеллекта. Задачи распознавания представляются особенно актуальными и трудными, если
входное изображение подвергнуто геометрическим
преобразованиям. При решении этих задач подбирается математическая модель, которая наиболее
точно отвечает требованиям решаемой задачи. В
большинстве случаев достаточно рассматривать
преобразования, отвечающие аффинной группе, а
иногда и ее подгруппам.
Однако преобразования изображений в ряде технических задач выходят за рамки аффинной группы
(аэрофотосъемка, видеосъемка поверхности Земли
и т.д.). Для этих задач используют математические
модели, которые основываются на проективных
преобразованиях. Такие преобразования наиболее
точно описывают реальные геометрические изменения объектов. Координатная зависимость при
этом описывается формулами
b11x b12 y b13
b 21 x b 22 y b 23
, yc
b 31 x b 32 y b 33
b 31x b 32 y b 33 , (1)
xc
b11
b12
b13
где b 21 b 22
b 23
b 31
b 33
0 . Матрицу преобразования
b12
b 22
1
?3
b13 ·
ё
b 23 ё
,
b 33 ё№
§ b11
Ё
Ё b 21
Ё 1
©
?2
b12
b 22
b 32
§ b11
Ё
Ё b 21
Ёb
© 31
b12
b 22
b 32
b13 ·
ё
b 23 ё
,
1 ё№
b13 ·
ё
b 23 ё
.
b 33 ё№
Утверждение 1. Пусть П1 являются преобразованиями П при условии b32z0. Тогда П1 допускают
разложения
П1 = AHC,
где A
§ a 11 a12
Ё
Ё a 21 a 22
Ё 0
0
©
a13 ·
ё
a 23 ё , C
1 ё№
(3)
§ 1 0 0 ·
Ё
ё
Ё a 31 1 a 33 ё ? афЁ 0 0 1 ё
©
№
§1 0 0·
Ё
ё
финные преобразования; H Ё 0 0 1 ё .
Ё0 1 0ё
©
№
Доказате льство. Если имеет место равенство (3),
то композиция преобразований AHC должна однозначно представляться параметрами преобразований П1. Действительно, из системы уравнений
­b11 a 11 a 13 a 31 , b 21 a 21 a 23 a 31 , b 31 a 31 ,
°°
b 22 a 23 ,
b 33 a 33 ,
®b12 a 13 ,
°
°Їb13 a 13 a 33 a 12, b 23 a 23 a 33 a 22 ,
следует система уравнений:
a11
b11 b12 b 31 , a 21
b 21 b 22 b 31 ,
a 31
b 31 ,
обозначим П.
a12
b13 b12 b 33 , a 22
b 23 b 22 b 33 ,
a 32
b 32 ,
Множество проективных преобразований образует
группу [1].
a13
b12 ,
b 22 ,
b 32
Нормализация изображений [2], подвергнутых влиянию проективного преобразования, достаточно
сложная задача, поэтому представляет интерес получить ее разложения на более простые составные.
В литературе приводится доказательство того, что
всякое проективное отображение может быть осуществлено путем надлежащего перемещения плоскости в пространстве и последующего перспективного отображения (из надлежащим образом выбранного центра перспективы) [3]. Как будет показано
ниже, такое представление проективного преобразования возможно в том случае, когда центр перспективы выбран таким образом, чтобы коэффициент b33z0. В этом случае преобразование представимо в виде
b11x b12 y b13
b x b 22 y b 23
, yc 21
b 31x b 32 y 1
b 31x b 32 y 1 .
РИ, 2002, № 2
xc
(2)
a 23
что доказывает однозначность представления.
Рассмотрим геометрическую интерпретацию преобразования, задаваемого матрицей H, т.е. преобразования координаты которого имеют зависимость
x
1
xc
, yc
.
(4)
y
y
Формулами (4) определено преобразование для
любой фигуры, не пересекающей прямую y=0, т.е.
не пересекающей ось абсциссы.
Пусть точке (a, b) преобразование (4) ставит в
a 1
соответствие образ ( , ). Через эти точки провеb b
дем прямую линию. Ее уравнение имеет вид:
x a
a
a
b
yb
x a
yb
1
,
, x(1 b) ya a
a
(
a
ab
)
b
1 b2
b
0 . (5)
57
Пусть точке (c, d) преобразование (4) ставит в
? 1
соответствие образ ( , ). Уравнение прямой,
d d
проходящей через эти точки, имеет вид:
x (1 d ) yc c
0.
(6)
Найдем точку пересечения этих двух прямых:
­x (1 b) ya a
®
Їx (1 d ) yc c
­
°y
0, °
®
0 , °y
Ї°
1 b
1,
a
1 d
1,
x
c
§1 b 1 d ·
1 b
1 d
ё 0 , x=0 џ y= -1.
x
1 x
1, xЁ
c №
a
c
© a
Итак, (0, -1) является точкой пересечения прямых
(5) и (6).
Проверим, проходит ли прямая, проведенная через точxo 1
ки (x0, y0) и ( y , y ), через
0
точку (0, -1). Уравнение прямой, проведенной через точxo 1
ки (x0, y0) и ( y , y ), имеет
0
вид:
x (1 y 0 ) yx 0 x 0 0 . (7)
Подставим точку (0,-1) в
уравнение (7): 1�x0 - x0 = 0, 0 Џ 0.
Вывод: преобразование (4) есть центральное проектирование с центром в (0, -1) [4].
Замечание 1. Точки, лежащие на прямой y=1,
переводятся преобразованием (4) сами в себя.
Замечание 2. Если фигура F лежит выше оси
абсциссы, т.е. y>0, то ее образ Fc также будет выше
оси x0, и наоборот (рисунок).
Утверждение 2. Пусть П2 являются преобразованиями П при условии b33z0. Тогда П2 допускают
разложения
0·
ё
0ё ,
1 ё№
0
0·
ё
0ё
.
h sin(D) 1 ё№
1
Доказательство. Покажем, что композиция преобразований A Px (n )Py (m) однозначно представляется параметрами преобразования П2.
58
a 11 a 13 m,
b 21
a 12 a 13 n ,
a 13 ,
b 22
a 21 a 23 m, b 31
a 22 a 23 n , b 32
b 23
m,
a11=b11-b13m,
a21=b21-b23m,
m=b31,
a12=b12-b13n,
a22=b22-b23n,
n=b32.
a13=b13,
a23=b23,
m,
n,
Аналогично однозначность представления (9) следует из систем уравнений:
­b11
°
®b12
°b
Ї 13
­a
° 11
°
°
°
°a 12
®
°
°
°a
° 13
°Ї
a 11 a 13 m, b 21
a 12 a 13 n , b 22
a 21 a 23 m, b 31
a 22 a 23 n , b 32
a 13 ,
a 23 ,
b 23
b11 - b13 m,
a 21
h cos(D ),
h sin( D).
b 21 - b 23 m, h
2
2
,
r a 31
a 32
­
§ a 32 ·
ё,
°arctgЁЁ
°
a 31 ё№
©
®
°??? a 31 z 0,
°Ї 90 , a 31 0,.
b12 - b13 n,
a 22
b 22 - b 23 n, D
b13 ,
a 23
b 23 ,
Доказательство закончено.
Утверждение 3. Пусть П3 являются преобразованиями П при условии b31z0. Тогда П3 допускают
разложения
П3= A Px ( n )Py (m ) I,
(10)
(11)
П3= A PD (h ) I,
где A ? аффинные преобразования; Px(n) ? преобразования перспективы вдоль оси абсцисс с параметром n; Py(m) ? перспективы вдоль оси ординат
с параметром m, PD(h) ? преобразования перспективы вдоль прямой с углом наклона, равным D; I
? преобразование симметрии, т.е.
(8)
(9)
П2= A PD (h ) ,
где A ? аффинные преобразования; Px(n) ? преобразования перспективы вдоль оси абсцисс с параметром n; Py(m) ? перспективы вдоль оси ординат
с параметром m; PD(h) ? преобразования перспективы вдоль прямой с углом наклона, равным D,
§1 0
§ a11 a12 a13 ·
Ё
Ё
ё
т.е. A Ё a 21 a 22 a 23 ё , Px (n ) Ё 0 1
Ёn 0
Ё 0
0
1 ё№
©
©
1
§1 0 0·
§
Ё
ё
Ё
Py (m) Ё 0 1 0 ё PD (h ) Ё
0
,
Ё0 m 1ё
Ё h cos(D)
©
№
©
­b11
°
®b12
°b
Ї 13
следует система уравнений
x
П2= A Px (n )Py (m) ,
Из системы уравнений
A
§ a 11 a12
Ё
Ё a 21 a 22
Ё 0
0
©
a 13 ·
ё
a 23 ё Px (n )
,
1 ё№
§ 1 0 0·
Ё
ё
Ё 0 1 0ё ,
Ё n 0 1ё
©
№
§1 0 0·
§0 0 1·
Ё
ё
Ё
ё
Py (m) Ё 0 1 0 ё I Ё 0 1 0 ё
,
,
Ё0 m 1ё
Ё1 0 0ё
©
№
©
№
1
0
0·
§
Ё
ё
PD (h ) Ё
0
1
0ё
.
Ё h cos(D ) h sin( D ) 1 ё
©
№
Доказательство аналогично доказательству утверждения 2.
Утверждение 4. Полная проективная группа (1)
может быть представлена хотя бы одним из разложений (3), (8)-(11).
РИ, 2002, № 2
До каз ате л ь ст во . Поскольку детерминант матрицы П не равен нулю, следовательно, параметры
b31, b32, b33 одновременно не равны нулю. А значит
матрица П может быть представлена хотя бы в
одном из видов П1, П2, П3, разложения которых
представлены в утверждениях 1-3.
Следствие. Множество преобразований П1, П2, П3
покрывает всю проективную группу П вида (1).
Рассмотрим случаи нормализации изображений,
для которых нормализация возможна.
Представим изображение как финитные функции
двух переменных B(x, y) в прямоугольной области
D [2]. Пусть эталонное B0(x,y) и входное B(x,y)
изображения имеют зависимость
§ b x b12 y b13 b 21x b 22 y b 23 ·
ё
B 0 ЁЁ 11
,
b 31x b 32 y 1 ё№ ,
© b 31x b 32 y 1
т.е. изображения связаны преобразованием П2.
Следовательно, для них возможна нормализация с
помощью разложения (8). Отметим, что преобразования перспекти вы коммутативны, т.е.
Px (n )Py (m) = Py (m)Px (n ) . Поэтому компенсация
перспективы Px (n ) не влияет на параметр перспективы Py (m) , и наоборот.
B( x , y)
Если на изображении известна характеристическая
точка (xхр.,xхр.) (точка, которую можно найти при
любом преобразовании), находящаяся в некоторой
окрестности центра тяжести изображения, то этап
компенсации перспективы осуществим переходом
от эталонного изображения B0(x,y) к изображению
Bc0(x,y) и от входного B(x,y) к изображению Bc(x,y)
таким образом, чтобы характерная точка совпадала
с центрами тяжестей изображений Bc0(x,y), Bc(x,y).
Полученные изображения будут связаны только
аффинным преобразованием.
Для этого воздействуем на изображение B0(x,y)
преобразованием перспективы Px(m+'m ) с некоторым шагом 'm и преобразованием перспективы
Py(n+'n) с некоторым шагом 'n, проверяя выполнения условий
іі Bc0 ( x, y) xdxdy
іі Bc0 ( x, y)dxdy
,
D
іі Bc0 ( x, y) ydxdy
yхр.=yц.т.. = D
іі Bc0 ( x, y)dxdy
.
D
Выполнив аналогичную процедуру для входного
изображения B(x,y), получим изображение B(x,y),
для которого также будут выполнены условия
xхр.=xц.т., yхр.=yц.т.
Полученные изображения обладают тем свойством,
что центры тяжести у них совпадают, что характерно для аффинного преобразования. Таким образом,
осуществляется переход к изображениям Bc0(x,y) и
Bc(x,y), которые связаны только аффинным преобразованием. Нормализацию аффинного искажения
можно осуществить любым известным методом [2].
РИ, 2002, № 2
§ b x b12 y
b x b 22 y ·
ё.
B0 ЁЁ 11
, 21
ё
© b 31x b 32 y 1 b 31x b 32 y 1 №
Поскольку перспектива всегда влияет на значение
центра тяжести изображения, следовательно, признак несмещенности центра тяжести можно рассматривать как признак отсутствия перспективного искажения на изображении.
B( x , y)
Доказательство закончено.
xхр.=xц.т. = D
Рассмотрим случай, когда b13=b23=0, т.е. когда
изображения несмещенные. При этом из условия
существования преобразования следует, что b33z0.
Таким образом, входное и эталонное изображения
связаны соотношением:
Выделим из проективного преобразования центроаффинное, используя процедуру нормализации
следящего типа [2].
Для нормализации воздействуем на входное изображение преобразованием Py(n+'n) с некоторым
шагом 'n и добиваемся выполнения условия
іі B( x, y) ydxdy іі B0 ( x, y) ydxdy
D
D
іі B( x, y)dxdy ѕ іі B0 ( x , y)dxdy
D
0,
D
тем самым компенсируя перспективу вдоль оси
ординат. Теперь, воздействуя на входное изображение преобразованием Px(m+'m) с некоторым шагом 'm, добиваемся выполнения условия
іі B( x, y) xdxdy іі B0 ( x, y) xdxdy
D
D
іі B( x , y)dxdy ѕ іі B0 ( x, y)dxdy
D
0,
D
тем самым компенсируя перспективу вдоль оси
абсциссы. Остается только нормализовать искажение, внесенное аффинным преобразованием.
Таким образом, для несмещенных изображений
процедура нормализации оказывается более простой, без перехода к промежуточным изображениям.
Полученные результаты показывают возможность
разложения группы проективных преобразований на
более простые составные. При этом для изображений,
подверженных влиянию преобразований вида П2,
процедура нормализации оказывается возможной.
Литература: 1. Моденов П.С. Аналитическая геометрия.
М.: МГУ, 1969. 598с. 2.Путятин Е.П., Аверин С.И.
Обработка изображений в робототехнике. М.: Машиностроение, 1990. 319с. 3 Моденов П.С., Пархоменко А.С.
Геометрические преобразования. М.: МГУ, 1961. 231с.
4.Бакельман И.Я. Высшая геометрия. М.: Просвещение, 1967. 367с.
Поступила в редколлегию 19.06.2002
Рецензент: д-р техн. наук, проф. Петров Э.Г.
Любченко Валентин Анатольевич, студент ХНУРЭ.
Научные интересы: компьютерная графика, распознавание образов. Адрес: Украина, 61166, Харьков, пр.
Ленина,14, тел. 40-94-19.
Путятин Евгений Петрович, д-р техн. наук, профессор,
зав. каф. информатики ХНУРЭ, засл. деят. науки и
техники Украины. Адрес: Украина, 61166, Харьков, пр.
Ленина, 14, тел. 40-94-19.
59
Документ
Категория
Без категории
Просмотров
7
Размер файла
197 Кб
Теги
проективные, математические, разложение, преобразование, модель, задача, нормализация
1/--страниц
Пожаловаться на содержимое документа