Graphics & Media Lab. >> Курсы >> Курс Ю.М.Баяковского 2000


О курсе	Лекции	Практикум	FAQs	Оценки	Глоссарий	Литература

Метаморфические преобразования растровых изображений (morphing)

Файл для печати - morphing.doc

Автор: Мазеев Максим

Mazeyev@pmail.net

Простейшие преобразования растровых изображений

1. Последовательное замещение одного изображения другим. (Fading)

2. Геометрические преобразования. Аффинное преобразование. (Affine transformation)

3. Простейшая реализация морфинга. Fading + Affine transformation.

Морфинг. Преобразования на основе характеристических линий

1. Преобразование на основе одной пары линий

2. Преобразование на основе множества характеристических линий

Примечания

Интерполяция цвета «промежуточных» пикселов изображения

Преобразование на основе характеристических кривых

Обязательные требования к выполнению заданий

Литература

Метаморфическое преобразование изображений I⁽⁰⁾(v) и I^(T)(v) - преобразование:

F(t): I⁽⁰⁾(v),I^(T)(v) -> I^(t)(u), tЄ[0, T] , v=(v_x, v_y), u=(u_x, u_y),

выполняющее “плавное превращение” изображения I⁽⁰⁾ в– I^(T) (и наоборот I^(T) в– I⁽⁰⁾). Функция F(t) обладает следующими свойствами:

F(t=0, I⁽⁰⁾, I^(T)) = I⁽⁰⁾

F(t=T, I⁽⁰⁾, I^(T)) = I^(T)

F(t, I⁽⁰⁾, I^(T)) = I^(t), 0<t<T, последовательность изображений { I^(t)(u) } представляет промежуточные состояния между I⁽⁰⁾и I^(T), причем I⁽⁰⁾ ->{ I^(t) }-> I^(T) при 0->t->T, т.е. отражает эффект «непрерывной» трансформации объектов из I⁽⁰⁾ в объекты из I^(T) и наоборот.

Простейшие преобразования растровых изображений

Последовательное замещение одного изображения другим. (Fading)

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

I^(t)(v) = (1-t)I⁽⁰⁾(v) + t I⁽¹⁾(v), tЄ[0, 1]

(для цветных изображений(RGB) вычисления выполняются независимо для всех цветовых составляющих)

Пример 1

Пример 2

Геометрические преобразования.

Аффинное преобразование. (Affine transformation)

Аффинное преобразование задается в виде:

u=Av + b,

,

обратное v=A^-1(u – b),

или в обобщенных координатах

,, ,

обратное ,

Пример 1

Пример 2

Аффинное преобразование M изображения I⁽⁰⁾(v) в I^(T)(u), можно записать так

M: I⁽⁰⁾(v) -> I^(T)(u)

I⁽⁰⁾(v)= I^(T)(u) = I^(T)(Mv)

или в более удобном для реализации виде: I^(T)(u) = I⁽⁰⁾(v)= I⁽⁰⁾(M^-1u)

(Для точек вне изображения можно взять «средний» цвет изображения или цвет фона. Либо взять «большое» изображение, а показывать и выполнять геометрические преобразования только над его частью)

С помощью такого преобразования можно задать поворот, перенос, масштабирование и «скашивание»

Рассмотрим последовательность аффинных преобразований M(t), такую что

M(t) = M_A(t),b(t) = M_(1-t)E+tA,_tb tЄ[0, 1], E – единичная матрица

в матричном виде

Получим последовательность изображений {I^(t)(u)}

M(t): I⁽⁰⁾(v) -> I^(t)(u), I^(t)(u) = I⁽⁰⁾( M(t)^-1 u )

причем

M(0)= M_E,0: I⁽⁰⁾(v) -> I⁽⁰⁾(v),

M(1) = M_A,b: I⁽⁰⁾(v) -> I⁽¹⁾(u)

M(t) = M_(1-t)E+tA,_tb: I⁽⁰⁾(v) -> I^(t)(u)

т.е. {I^(t)(u)} – некоторая последовательность изображений, представляющая собой «плавный» переход от I(0) к I(1)

Таким образом, задав I⁽⁰⁾(v), M_{A,
b} и применив описанный алгоритм, можно построить последовательность, отражающую «постепенное» выполнение аффинного преобразования M_A,b над I⁽⁰⁾(v)

Заметим, что M(t) можно задать и другими способами, необязательно линейными, как в этом примере. Если M матрица поворота на 180⁰, то из предложенного алгоритма M(0.5) – нулевая матрица, и многие дальнейшие рассуждения не верны. В этом случае необходимо представить другой способ задания M(t), например, выделить матрицу поворота и «разложить» М на последовательность поворотов и смещений с растяжениями.

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

Простейшая реализация морфинга.
Fading + Affine transformation.

Fading: I^(t)(u) = (1-t)I⁽⁰⁾(u) + tI⁽¹⁾(u), tЄ[0, 1]

Affine transformation M: I^(t)(u) = I⁽⁰⁾( M(t)^-1u )

Пусть заданы I⁽⁰⁾, I⁽¹⁾, и M

Рассмотрим преобразование

I^(t)(u) = (1-t) I⁽⁰⁾( M(t)^-1u ) + t I⁽¹⁾( [M^-1(1-t)]^-1 u )

Пример 1

Пример 2

Такое преобразование обладает следующими свойствами

I^(t)(u) = { t = 0 }= I⁽⁰⁾(u) = 1 I⁽⁰⁾( M(0)^-1u ) + 0 I⁽¹⁾(…) = I⁽⁰⁾(M⁽⁰⁾u ) = I⁽⁰⁾(u) – начальное изображение

I^(t)(u) = { t = 1 }= I⁽¹⁾(u) = 0 I⁽⁰⁾( …) + 1 I⁽¹⁾ ( [M^-1(1-t)]^-1 u) = I⁽¹⁾( [M^-1(0)]^-1u ) = I⁽¹⁾(u) -конечное изображение

I^(t)(u) = { t = 0.5 }= I^(0.5)(u) = 0.5 I⁽⁰⁾( M(0.5)^-1u ) + 0.5 I⁽¹⁾ ( [M^-1(0.5)]^-1 u) – промежуточное изображение - «середина» между соответствующими пикселами начального и конечного изображений, над каждым из которых применена «половина» аффинного преобразования M_A,b

Если I⁽⁰⁾, I⁽¹⁾, и M подобраны так, что из I⁽⁰⁾ с помощью преобразования М получается изображение I’⁽¹⁾ похожее на I⁽¹⁾, например, совпадением контуров объектов, то построенная последовательность { I^(t)} ,будет представлять собой «непрерывное» метаморфическое трансформирование I⁽⁰⁾ в I⁽¹⁾

Для построения «удачной» последовательности { I^(t)(u) } необходимо подобрать подходящие изображения I⁽⁰⁾, I⁽¹⁾, и построить геометрическое преобразование M (mapping) изображений. Преобразование M необязательно должно быть аффинным, оно может быть, например, некоторой композицией аффинных преобразований.

Один из способов задания такой композиции рассматривается в следующей части.

Это преобразование представляет собой частный случай аффинного.

Выберем на начальном – I⁽⁰⁾ и конечном – I⁽¹⁾ изображениях по одному вектору PQ и P’Q’ соответственно. Вычислим коэффициенты аффинного преобразования, такого, что P->P’, Q->Q’ и для любой точки v из I⁽⁰⁾ и u из I⁽¹⁾ выполнены условия:

a=|OP| / |QP| равно a’=|O’P’| / |Q’P’| (см. рис) и расстояние от точек v и u до соответствующих векторов PQ и P’Q’ равны b =b ’=const.

Получим

a) ,

- отношение OP к QP, см. рис.

- расстояние от v до QP

- перпендикуляр

- скалярное произведение

Или в матричном виде

б)

M=M_A,b

,

где

- скалярное произведение

Такое преобразование M_A,b не выполняет «скашивания» изображения

2. Преобразование на основе множества характеристических линий

Выберем на начальном – I⁽⁰⁾ и конечном – I⁽¹⁾ изображениях по набору векторов {P_iQ_i} и {P_i’Q_i’}

Построим композицию преобразований M_i переводящих P_iQ_i->P_i’Q_i’, (Преобразование PQ->P’Q’ описано в предыдущей части)

Для этого вычислим v как взвешенную сумму между соответствующими v_i, полученных с помощью Mi.

,

,

- «нормированное расстояние» от v до i-го вектора

с₁, с₂– константы

можно взять, например, такие, с₁>0, c₂Є[0.5, 2]

Примеры морфинга

Пример 1

выполняемое геометрическое преобразование:

Пример 2

выполняемое геометрическое преобразование:

Пример 3

выполняемое геометрическое преобразование:

Примечания

Интерполяция цвета «промежуточных» пикселов изображения

Для вычисления цвета изображения “между пикселами” можно воспользоваться следующими подходами:

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

например, (x, y) находится внутри области xЄ[i, i+1], yЄ[j, j+1], тогда
I(x, y)=[I(i, j)+ I(i+1, j)+ I(i, j+1)+ I(i+1, j+1)] / 4

Интерполировать значение цвета

I(x, y)=I(i, j) (1-a )(1-b )+ I(i+1, j) a (1-b )+ I(i, j+1) (1-a )b + I(i+1, j+1) a b ,

a =x-i, b =y-j (дробные части)

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

Преобразование на основе характеристических кривых

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

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

Задания

Реализовать

количество баллов

Простейшие преобразования растровых изображений

Замещение изображений (Fading)

построить N промежуточных состояний между двумя изображениями (t=0..1 step 1/(N+1))

Аффинное преобразование изображения (Affine transformation)

построить N промежуточных состояний между двумя изображениями, одного из которых получено применением аффинного преобразования к другому (t=0..1 step 1/(N+1))

Простейшая реализация морфинга. (Fading + Affine transformation)

построить N промежуточных состояний между двумя изображениями, с применением «последовательного» аффинного преобразования (t=0..1 step 1/(N+1))

Морфинг. Преобразования на основе характеристических линий

Одна пара характеристических линий

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

Множество характеристических линий

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

Преобразования на основе характеристических линий и кривых

Удобство интерфейса, удобная работа с программой

+1 - +4

Обязательные требования к выполнению заданий

Программы к заданиям 1)-6) должны иметь РЕЖИМ РАБОТЫ С КОМАНДНОЙ СТРОКОЙ, т.е. как минимум принимать входные параметры из командной строки. Обязательные параметры для всех заданий - имена начального и конечного изображений в формате BMP (24-bit-color format), начальная часть имени файла для серии BMP файлов, в которые выводятся результаты промежуточных шагов (промежуточных изображений) и N – количество шагов.
Описание формата командной строки

Задание 1

<your_program1.exe> <first_image> <last_image> <output_file> N
Например:

На входе

morphing.exe first.bmp last.bmp middle 10
где

morphing.exe – ваша программа
first.bmp – начальное изображение

last.bmp – конечное изображение

middle – начальная часть имен файлов для вывода построенных промежуточных изображений

10 – количество промежуточных изображений, которые необходимо построить

На выходе
middle0.bmp = first.bmp
middle1.bmp

middle2.bmp

…

middle9.bmp

middle10.bmp = last.bmp

Эталонный пример: Source1.zip, Source2.zip

Задание 2, 3
<your_program2.exe> <first_image><output_file> N <transformation_file> <your_program3.exe> <first_image> <last_image> <output_file> N <transformation_file>
transformation_file – файл с коэффициентами аффинного преобразования, его формат

{ a11, a12, a21, a22 } { b1, b2 }
все числа могут быть вещественные, с десятичной точкой “.”,
пример

{0.707, 0.707, -0.707, 0.707} {5, –5}

ЗАМЕЧАНИЕ. Все координаты относительно нижнего левого угла изображения. (Координатная система как в BMP файле)
Эталонный пример для задания 2: Source1.zip, Source2.zip
Эталонный пример для задания 3: Source1.zip, Source2.zip

Задание 4
<your_program4.exe> <first_image> <last_image> <output_file> N <transformation_file> transformation_file:
{

{Px, Py, Qx, Qy }
}
{

{P’x, P’y, Q’x, Q’y}
}
ЗАМЕЧАНИЕ. Все координаты относительно нижнего левого угла изображения. (Координатная система как в BMP файле)

Пример

{

{1, 2, 51, 52 }
}
{

{41, 3, 61, 62}
}
что значит PQ-> P’Q’ = {(1,2), (51,52)}->{(41,3),(61,62)}

Эталонный пример: Source1.zip, Source2.zip

Задание 5
<your_program5.exe> <first_image> <last_image> <output_file> N <transformation_file> transformation_file

{

{P1x , P1y , P2x , P2y , …, Pmx , Pmy } 1-ая ломанная
…

{P1x , P1y , P2x , P2y , … , Pmx , Pmy } n-ая ломанная

}
{

{P1x , P1y , P2x , P2y , …, Pmx , Pmy } 1-ая ломанная
…

{P1x , P1y , P2x , P2y , …, Pmx , Pmy } n-ая ломанная

}
Пример

{

{1, 2, 51, 52 }
{57, 58, 60, 62 }

}
{

{41, 3, 61, 62} {37, 38, 40, 42 }
}
Эталонный пример: Source1.zip, Source2.zip, Source3.zip
Задание 6
Необходимо реализовать режим работы с характеристическими линиями, см Задание 5. Кривые могут быть заданы произвольным образом. Для выполнения задания желательно реализовать графический интерфейс (GUI), с возможностью сохранения и восстановления «разметки» в файле.
Дополнительные средства для удобной работы с программой ПРИВЕТСТВУЮТСЯ, например GUI, и будут оценены.

Оформление заданий

См. предыдущие задания и FAQ

Исходные коды

Полезные исходные коды для работы с растровыми изображениями в формате BMP. Реализовано под Visual C++ 6.0 (можно использовать для выполнения заданий)

Example.zip

Литература

[1] Thaddeus Beier, Shawn Neely, Feature-Based Image Metamorphosis, SIGGRAPH’92 (Chicago, July 26-31, 1992)


На главную	Наверх

Graphics & Media Lab. >> Библиотека | Курсы | Графикон



Hosted by Graphics & Media Lab http://graphics.cs.msu.su		Поддержка и дизайн: Алексей Игнатенко