Информационный сервер для программистов: Исходники со всего света. Паскальные исходники со всего света
  Powered by Поисковый сервер Яndex: Найдется ВСЁ!
На Главную Pascal Форум Информер Страны мира
   Demo Making    >>    morphing
   
 
 Morphing   Roman Lout 23.11.1997

Статья о двумерном морфинге изображений (плавная трансформация одной картинки в другую). Описание алгоритма и выдержки из исходника.
2D Morphing algorithm with pascal examples (Russian)



6k 
 

- 4INT -------------------------------------------- It's interesting - Msg : 152 of 200 Addr Date From : Lout Roman 2:463/586.20 23.11.97 Subj : Морфинг ---------------------------------------------------------------------- ---> Hi Dmitry! <--- [Втp Hоя 18 1997, 22:26], Dmitry Sorvachev нашкрябал All: DS> Кто может помочь с алгоpитмом 2D моpфинга (плавный пеpеход одной DS> каpтинки в дpугую)? У кого-нибудь есть инфоpмация по этому вопpосу DS> на _pусском_ языке? Статья писалась для жуpнала, так что извиняюсь за некотоpое "pазжевывание" понятных вопpосов. Sincerely Yours, ++AX --- * Origin: ћДа мне за это шнобелевскую премию должны были дать ! {> Cut here. FileName= MORPHING.TXT } MORPHING В наши дни по телевидению в рекламе, фильмах, просто заставках можно увидеть эффект "переливания" одного изображения в другое - "морфирование изображений". Будь то превращение человекаобо- ротня в волка, галлерея лиц в клипе Майкла Джексона, трансфор- мация Терминатора 2 - действие происходит так плавно, что даже трудно уловить, на каком мгновении предмет потерял все признаки предыдущей формы и приобрёл новые. Как же это делается ? Морфинг - это плавное "превращение" одного изображения в другое, во время которого конкретный элемент первого изобра- жения "перетекает" в элемент второго изображения. Hапример, при морфировании одного автомобиля в другой, колесо первого превра- щается в колесо второго. Компьютер не может выполнить морфинг двух изображений самостоятельно - сначала художнику требуется задать соответствие элементов первого изображения элементам второго а также другие параметры, пользуясь специальным редак- тором. Способ задания соответствия зависит от редактора - это могут быть точки, линии, полигоны. Сам морфинг можно разбить на три части: warping, tweening и dissolving. Warping (коробить, искривлять) - преобразование изобра- жения, при котором оно в отдельных областях сжимается и растя- гивается - как буд-то изображение нанесено на резину. Расчёт каждой точки этого изображения осуществляется по математическим формулам в зависимости от соответствия элементов изображения, которое задал художник. Во время warping'а элеметны изображения пытаются принять положение и форму элементов второго изображе- ния. Tweening (построение промежуточных кадров) - интерполя- ция двух изображений для получения плавной анимации. апример, если соответствие элементов изображений задано точками, то ин- терполяцией положений точек можно получить промежуточные соот- ветствия. Dissolving (растворять, в кино cross-dissolving - за- темнение одной сцены и осветление другой) - слияние двух изоб- ражений, при котором в качестве цвета каждой точки нового изоб- ражения берётся смесь цветов соответствующих точек двух исход- ных изображений в заданной пропорци. Рассмотрим как пример морфирование авто мобилей: [skiped] Рис. 1. При warping'е один автомобиль пытается принять форму другого (в результате, конечно, ничего хорошего не получается): [skiped] Рис. 2. Tweening применяет warping для интерполированных точек, то есть позволяет получить промежуточные фазы (вверху показаны конечные кадры). Dissolving обьединяет два полученных изображения в од- но. В целом при морфинге первый атомобиль плавно пытается при- нять форму второго, а второй, приняв форму первого, пытается вернуться к нормальной форме. Dissolving смешивает изображения, при этом изображение первого автомобиля постепенно затухает, а второго - появляется. АЛГОРИТМЫ Алгоритм зависит от требуемого качества, скорости и способа задания соответствия элементов изображений. Удобно за- давать соответствие пользуюясь сеткой (mesh), например: [skiped] [Фотогpафия, накотоpую наложена сетка из четыpёхугольников] Рис. 3. Плотность сетки влияет на скорость вычислений, требования к па- мяти, качество получаемого изображения. Редактор, предоставляю- щий другие способы задания соответствий, дожен привести их к сетке. Художник, работая с редактором, может вообще не подозре- вать о том, что в конечном счёте всё задаётся таким образом (вообще говоря, чем лучше редактор этот факт скрывает, тем он удобнее). Сетка задаётся узлами, и именно эти узлы (точки) при tweenig'е плавно движутся от своего первого положения во вто- рое, то есть tweening морфирует сетку. Warping осуществляется в соответствии с начальной сеткой и сеткой, полученной для данно- го кадра. Для узловых точек это легко: мы знаем, что в исходной сетке узел находился в точке (x,y) с цветом с. Значит в требуе- мой картинке точка, в которой теперь находится узел, имеет цвет c. Для остальных точек несколько сложнее: тут применяется били- нейная или бикубическая интерполяция. В алгоритме, предоженном Douglas Smithe для создания спецэффектов к фильму "Willow" (1988), применятся двух проход- ное преобразование изображения: в начале изображение деформиру- ется по x, а затем по y. Объясню на примере : [описание алгоpитма skiped. Без pисунков все pавно не понять, да и не нужен он тебе - используй описанный ниже] Hа деформацию сетки действуют ограничения: её ячейки не должны накладываться друг на друга, и боковые узлы не должны двигаться, иначе нельзя будет построить однозначную сплайн-функцию. В более сложных алгоритмах в узлах сетки можно задавать дополнительные параметры - например, скорость dissolving'а, таким образом регулируя нежелательное быстрое по- явление светлых частей второго изображения и т.п. Реализацию этого алгоритма можно найти в интернете - файл morfsrc.zip. К сожалению использовать исходные тексты на PC не удаётся из-за различия расположения старших/младших байт на PC и sun SPARC workstation, для которой они написаны. В РЕАЛЬHОМ ВРЕМЕHИ ? "Я смотрел демку Heart-Quake/Iguana (ftp.cdrom.com pub/demos/demos/1994/heartq.zip) - они делают морфинг в реаль- ном времени. Вышеописанный алгоритм слишком медленный для это- го. Как у них это получается, причём быстро даже на 486DX33 ?". Как точно сделано с демке, я не могу сказать. Однако идея, ко- торую я покажу в исходных текстах, будет визуально именно тем, что нам показала Iguana. Прежде всего - только линейная интерполяция. Это значи- тельно снижает объём вычислений, в тоже время не сильно влияя на качество изображения при удачно заданном соответствии точек. Далее - работа в 256 оттенках серого. В связи с такими ограниче- ниями можно применить некоторую хитрость: работать не с точками изображения, а с целыми ячейками сетки. Действительно: доста- точно четырёхугольник изображения, являющийся ячейкой первой сетки, преобразовать в четырёхугольник, которым он стал в теку- шей сетке - и мы автоматически получаем нужное деформированное изображение. С процедурой, выполняющей такое преобразование, знаком каждый, кто занимается программированием трёхмерной гра- фики. Это так называемый линейный маппинг изображения. Hа вход процедуре даются вершины исходного четырёхугольника на текстуре (картинке, ниже - s_polybmp), указатель на саму картинку, коор- динаты вершин требуемого четырёхугольника на экране (s_poly2d). Сама процедура здесь не описывается - это тема отдельной статьи. С dissolving'ом всё просто: цвет точки определяется по формуле c=c1+(c2-c1)*t, 0<t<1, где с1 и c2 - цвета точки первой и второй картинки, t - фаза морфинга. Ксати, для цветного изоб- ражения выполняется тоже самое для составляющих RGB. Что каса- ется Heart-Quake, там нахождение цвета точки (индекса в палит- ре) выполняется, судя по всему, по заранее просчитанной таблице c=ColTable[c1,c2,t] размер которой для t=0..20 составляет 256*256*20=1310720 байт (!). Однако размеры таблицы можно зна- чительно уменьшить, если заставить оба изображения использовать не все цвета палитры, а, например, - 64. Это требует таблицу всего 81Кб (при этом остальные цвета палитры используются для представления промежуточных цветов). Вы заметили, какой сильный dithering на фотографиях в Heart-Quake ? Исходные тексты для Borland Pascal 7.0 for DPMI. Расс- читаны на работу с картинками 256x256 и сеткой 9x9. Из-за боль- ших размеров текст некоторорых процедур не приводится - в этом месте ставится соответствующий комментарий. Все процедуры моду- ля myvesa и описание редактора сеток не приводится. Ссылки. 1. morphscr.zip "MESHWARPING ALGORITHM FOR MORPHING IMPLEMENTED IN C by George Wolberg". 2. DEMO.DESIGN.* Frequently Asked Questions, Release 9 (С) Peter Sobolev, 2:5030/84@fidonet. 3. Demo Heart-Quake/Iguana (ftp.cdrom.com pub/demos/demos/1994/heartq.zip) 4. Demo Stars/Noon (ftp.cdrom.com pub/demos/demos/1995/n/nooon_st.zip)