Image Morphing

Happy new year. I've started this blog today with an article about computer vision.

Introduction

In this article, I will explain about "Image Morphing" which means changing the shape of a object gradually into the shape of another object. I wrote a program code using OpenCV. My algorithm is based on this slide. My code morph myself into "dragon". Why dragon? In Japan, each year is associated with an animal according to a 12-year mathematical cycle, and 2012 is a year-of-dragon. So, this program is a kind of new year greeting to readers :)

Overview

Image Morphing needs two images and mapping between their feature point as input, and is composed of two phase. First, images need to be warped so that their corresponding feature point is at the same position. Second, blend two images into one image using cross-dissolving. So images are warped and cross-dissolving into one image while time parameter is increasing. I will explain the detail about these methods.

Warping

Warping is required to make corresponding pixels in two images be at the same position. To do so,  we have to prepare pairs of lines. In this experiment, I use these two images. the left is a source image, and the right is a destination image.

source image	destination image

Pairs of lines for these images are below.
First, lines of the source image.

[srcFeature.txt]

15
74 130 122 1
74 130 82 132
82 132 106 135
106 135 153 137
106 135 118 177
118 177 153 137
122 1 205 130
74 130 81 209
205 130 208 219
81 209 123 266
208 219 123 266
98 211 119 226
119 226 159 215
98 211 119 206
119 206 159 215

And lines of the destination image are below.

[destFeature.txt]

15
84 83 147 20
84 83 96 82
96 82 119 88
119 88 184 88
119 88 154 127
154 127 184 88
147 20 230 82
84 83 75 135
230 82 221 135
75 135 156 275
221 135 156 275
80 135 156 257
156 257 217 140
80 135 151 154
151 154 217 140

The first line is the number of lines n. Next n lines contains four integers - Px, Py, Qx, Qy which represent the coordinate of the starting point and the ending point. For example, the first line or left image is from (74, 130) to (122, 1) which means from left ear to top of the head, and the first line of right image is the corresponding one.

We need to get warped image from the pairs. If the location of X' on the destination image is given, how to calculate the location of X on the source image which is corresponding to X'?

First, we calculate u and v. The value u goes from 0 to 1 as the pixel moves from P' to Q'. The value v is the perpendicular distance from the line to X'. Once we get u and v, we can apply them to the source image, and so X coordinate will be acquired.

In this case, we have multiple pairs of lines, so we need to average the sum of X coordinate weighted by a kind of factor. The factor is set to be inversely proportional to the distance from line and directly proportional to the length of the line. (the details are described in the slide mentioned in "Instruction".)

By calculating source pixels for each pixels in the destination image, we can get warped image whose shape is closer to the destination image.

Cross-dissolving

Cross-dissolving is simpler than warping. We already have similar-shape images. For each pixel in the destination image, we mix the values of corresponding source pixel and destination pixel. The ratio of mixture depends on the time parameter. Time parameter goes from 0 to 1, so at the beginning point(t=0) the ratio of the source image is 1 and the other is 0, and at the end point (t=1) vice versa.

Warping+cross-dissolving=Morphing

As I mentioned above, the time parameter goes from 0 to 1. To complete morphing the source image into the destination image, at first we compute the intermediate image at each time. This means that both the source image and the destination image are warped into the intermediate image. So, for each pixels in intermediate image, we can also compute the corresponding pixels in the source image and the destination image. After that, apply cross-dissolving to these pixels.

Result

Source code

Notice: This source code requires OpenCV 2.0 or later, and this only outputs image files corresponding to each frame. I used ffmpeg to combine those image files into a movie file.

	#include <opencv2/opencv.hpp>
	#include <iostream>
	#include <fstream>
	#include <vector>
	#include <cmath>
	#include <assert.h>
	#define mp make_pair
	#define pb push_back
	#define A 0.1
	#define P 1
	#define B 1
	#define FRAMENUM 80
	#define GAIN 10.0
	using namespace std;
	using namespace cv;
	inline double sigmoid(double x) {
	return 1.0 / (1.0 + exp(-GAIN * (x - 0.5)));
	}
	inline double lengthSquare (double x, double y) {
	return pow(x,2)+pow(y,2);
	}
	inline double length (double x, double y) {
	return pow(lengthSquare(x,y),0.5);
	}
	CvPoint getMappingPoint (CvPoint p, CvPoint q, double u, double v) {
	double vx = q.y - p.y;
	double vy = -q.x + p.x;
	double hx = q.x - p.x;
	double hy = q.y - p.y;
	double vu = length(vx, vy);
	double sx = p.x + u*hx + (vx/vu)*v;
	double sy = p.y + u*hy + (vy/vu)*v;
	//printf("u=%f hx=%f vx/vu=%f v=%f \n", u, hx, vx/vu, rv);
	return cvPoint(sx, sy);
	}
	int main(int argc, char** argv) {
	if (argc != 5) {
	cerr << "specify 4 arguments" << endl;
	exit(-1);
	}
	const char* srcImageFile = argv[1];
	const char* srcFeatureFile = argv[2];
	const char* destImageFile = argv[3];
	const char* destFeatureFile = argv[4];
	IplImage* srcImage = cvLoadImage(srcImageFile, CV_LOAD_IMAGE_ANYCOLOR|CV_LOAD_IMAGE_ANYDEPTH);
	IplImage* destImage = cvLoadImage(destImageFile, CV_LOAD_IMAGE_ANYCOLOR|CV_LOAD_IMAGE_ANYDEPTH);
	IplImage* morphImage = cvCreateImage(cvGetSize(destImage), IPL_DEPTH_8U, 3);
	if (!srcImage || !destImage) {
	cerr << "cannot find image file" << endl;
	exit(-1);
	}
	// load feature line mapping from text files
	int srcFeatureNum;
	int destFeatureNum;
	vector< pair <CvPoint, CvPoint> > srcFeatures;
	vector< pair <CvPoint, CvPoint> > destFeatures;
	{
	ifstream srcFeatureStream(srcFeatureFile);
	ifstream destFeatureStream(destFeatureFile);
	srcFeatureStream >> srcFeatureNum;
	for (int i=0; i<srcFeatureNum; i++) {
	int x1,y1,x2,y2;
	srcFeatureStream >> x1 >> y1 >> x2 >> y2;
	CvPoint p1=cvPoint(x1,y1);
	CvPoint p2=cvPoint(x2,y2);
	srcFeatures.pb(mp(p1,p2));
	}
	destFeatureStream >> destFeatureNum;
	for (int i=0; i<destFeatureNum; i++) {
	int x1,y1,x2,y2;
	destFeatureStream >> x1 >> y1 >> x2 >> y2;
	CvPoint p1=cvPoint(x1,y1);
	CvPoint p2=cvPoint(x2,y2);
	destFeatures.pb(mp(p1,p2));
	}
	srcFeatureStream.close();
	destFeatureStream.close();
	}
	int w = destImage->width;
	int h = destImage->height;
	vector< pair <CvPoint, CvPoint> > targetFeatures(destFeatureNum);
	int fileIndex = 0;
	cvNamedWindow("mywindow");
	// increase time parameter
	for (double t=0; t<=1.0F; t+=1.0F/FRAMENUM) {
	// calculate intermediate feature line
	for (int i=0; i<destFeatureNum; i++) {
	pair <CvPoint, CvPoint> sp = srcFeatures[i];
	pair <CvPoint, CvPoint> dp = destFeatures[i];
	CvPoint t1 = cvPoint( (1.0F-t)*sp.first.x + t*dp.first.x, (1.0F-t)*sp.first.y + t*dp.first.y );
	CvPoint t2 = cvPoint( (1.0F-t)*sp.second.x + t*dp.second.x, (1.0F-t)*sp.second.y + t*dp.second.y );
	targetFeatures[i] = mp(t1, t2);
	}
	// calculate warped images from src image and dest image, and cross-dissolve two warped images into target image
	for (int y=0; y<h; y++) {
	for (int x=0; x<w; x++) {
	double sumsdx=0, sumsdy=0, sumddx=0, sumddy=0, sumweight=0;
	for (int i=0; i<destFeatureNum; i++) {
	// calculate weight for point(x,y) with line(i)
	double u,v,rawv,weight;
	{
	pair<CvPoint,CvPoint> tp = targetFeatures[i];
	// vertical vector is ps.second.y-ps.first.y, -ps.second.x+ps.first.x
	double vx = tp.second.y - tp.first.y;
	double vy = -tp.second.x + tp.first.x;
	double hx = tp.second.x - tp.first.x;
	double hy = tp.second.y - tp.first.y;
	double tx = x - tp.first.x;
	double ty = y - tp.first.y;
	// calc u
	u = (tx*hx + ty*hy) / lengthSquare(hx,hy);
	double vu = length(vx, vy);
	rawv = (vx*tx + vy*ty) / vu;
	if (u <= 0) {
	// v = PX
	v = length(tx, ty);
	} else if (u >= 1) {
	// v = QX
	v = length(x - tp.second.x, y - tp.second.y);
	} else {
	// vertical vector length
	v = abs(rawv);
	}
	double lineLength = length(hx, hy);
	weight = pow ((pow(lineLength, P)/(A+v)), B);
	assert(weight >= 0);
	}
	{
	pair<CvPoint, CvPoint> sf = srcFeatures[i];
	CvPoint sp = getMappingPoint(sf.first, sf.second, u, rawv);
	double sdx = x - sp.x;
	double sdy = y - sp.y;
	//printf("sdx=%f sdy=%f weight=%f\n", sdx, sdy, weight);
	sumsdx += sdx*weight;
	sumsdy += sdy*weight;
	}
	{
	pair<CvPoint, CvPoint> df = destFeatures[i];
	CvPoint dp = getMappingPoint(df.first, df.second, u, rawv);
	double ddx = x - dp.x;
	double ddy = y - dp.y;
	sumddx += ddx*weight;
	sumddy += ddy*weight;
	}
	sumweight += weight;
	}
	double avesdx = sumsdx/sumweight;
	double avesdy = sumsdy/sumweight;
	double aveddx = sumddx/sumweight;
	double aveddy = sumddy/sumweight;
	int sx = (int)(x - avesdx);
	int sy = (int)(y - avesdy);
	int dx = (int)(x - aveddx);
	int dy = (int)(y - aveddy);
	if (sx < 0 || sx > srcImage->width || sy < 0 || sy > srcImage->height) {
	continue;
	}
	if (dx < 0 || dx > destImage->width || dy < 0 || dy > destImage->height) {
	continue;
	}
	int destIndex = destImage->widthStep * dy + dx * destImage->nChannels;
	int srcIndex = srcImage->widthStep * sy + sx * srcImage->nChannels;
	int targetIndex = morphImage->widthStep * y + x * morphImage->nChannels;
	for (int i=0; i<morphImage->nChannels; i++) {
	uchar dp = (destImage->imageData[destIndex+i]);
	uchar sp = (srcImage->imageData[srcIndex+i]);
	int diff = (int)dp - (int)sp;
	int newvalue = diff * sigmoid(t) + sp;
	//int newvalue = diff * t + sp;
	//printf("diff=%d old=%d new=%d\n", diff, sp, newvalue);
	assert(newvalue <= 255 && newvalue >= 0);
	morphImage->imageData[targetIndex+i] = (uchar)newvalue;
	}
	//printf("source=(%d,%d) dest=(%d,%d)\n", sx, sy, x, y);
	}
	}
	char outfile[256];
	sprintf(outfile, "/Users/takahiro/Desktop/morph/morph%03d.jpg", fileIndex++);
	//int res = cvSaveImage(outfile, morphImage);
	cvShowImage("mywindow", morphImage);
	cvWaitKey(2);
	//printf("save to %s\n", outfile);
	}
	cvWaitKey(0);
	// 後始末
	cvReleaseImage(&srcImage);
	cvReleaseImage(&destImage);
	cvReleaseImage(&morphImage);
	return 0;
	}

view raw morphing.cpp hosted with ❤ by GitHub