## Assignment 2 Part II

### 2(II).Graph Cuts

#### 2(II).1 Description and requirements

Now we will add a component using graph cuts to find the region of an image to insert into another image instead of doing this by hand. You will need to find code to do graph cuts in Matlab---in particular we are looking for min-cut, max-flow algorithms that minimize the sum of weights of edges that are cut to separate a source and a sync. There are many version of this type of code available. You can exchange ideas about good sources for this code on the Sakai site for the class. You will then have to formulate the problem of finding a good region as a graph-cut problem. This will involve defining the graph based on the image(s) involved, passing it to the graph-cut algorithm, and interpreting the result to automatically crop out a region. Then you will use the first part of your assignment to blend this region into an image.

You should also collect a set of at least 50 images with similar content and search through these to find one for use in the assignment.

#### 2(II).2 Max-flow/Min-cut

Use max-flow/min-cut to find the region of the image to insert to another one.

I used the maxflow code from http://www.math.ucla.edu/~wittman/Fields/maxflow.zip

The usage format is "[flow,labels] = maxflow(A,T);".

#### 2(II).3 Construct the graph

We need to construct the graph for the maxflow algorithm, and I constructed the graph following the instructions in the slides of lecture8.

For the initial setting, I set the four outside edges of the figure to be background and use `imfreehand()` to specify the a small area that is definitely in foreground. Also, initial unary is set great enough.

The code is:

``````
m = double(rgb2gray(im));
[height,width] = size(m);

disp('building graph');
N = height*width;

unary = 9e9;

% construct graph
E = edges4connected(height,width);
figdis = gmdistribution.fit(m(:),1);
V = exp(-((m(E(:,1))-m(E(:,2))).^2)/(2*figdis.Sigma*figdis.Sigma));
A = sparse(E(:,1),E(:,2),V,N,N,4*N);

T = sparse(N,2);

for y = 1:height
for x = 1:width
if y==1 || y==height || x==1 || x==height
T((x-1)*height+y,1)=unary;
end

if front(y,x)
T((x-1)*height+y,2)=unary;
end
end
end
``````

#### 2(II).4 Iterations

In this part, we use the `labels` got in last `maxflow()` to re-define background and foreground. Also, use Gaussian Mixture Model to re-compute unary for each node.

Do the iterations until `labels` does not change anymore.

The code is:

``````
while sum(labels(:)) ~= sum(old_labels(:))
count = count + 1;
fi = find(labels(:)==1);
bi = find(labels(:)==0);
fg = m(fi);
bg = m(bi);
fgdis = gmdistribution.fit(fg,1);
bgdis = gmdistribution.fit(bg,1);

tmp = m(:);
unary_v = -log(fgdis.pdf(tmp)./bgdis.pdf(tmp));
unary_b = unary_v;
unary_v = abs(unary_v);
pos = find(unary_b >= 0);
neg = find(unary_b < 0);
unary_b(pos) = 1;
unary_b(neg) = 2;

i(1:N,1)=[1:N];
v(1:N,1)=unary_v;
j(1:N,1)=unary_b;
T = sparse(i,j,v,N,2);
old_labels = labels;
[flow,labels] = maxflow(A,T);
labels = reshape(labels,[height width]);
end
``````

The code for getting the region by using graph cut is mygraphcut.m.

#### 2(II).5 Result

Now, we use `labels` as `bMask` in part I of this assignment, then we can use techniques in part I to blending images.

The sources and the target are as follows:

 souce1 source2 target

The result is as follows:

 source1 simple clone source2 simple clone
 source1 alpha blending source2 alpha blending

#### 2(II).6 COMP 790 additional part

Now we collect a set of 50 images, and use GIST as the criteria to select one as background to best fit our sources.

The core part of the code is:

``````
for index=1:50

target_name=sprintf('targets/target%d.jpg',index);

% Parameters:
clear param

param.orientationsPerScale = [8 8 8 8];
param.numberBlocks = 4;
param.fc_prefilt = 4;

[gist2, param] = LMgist(img2, '', param);

gist_diff(index) = sum((gist1-gist2).^2);
end
``````

Then we use `[mini_v mini_index] = min(gist_diff)` to find the best-fit backgound index.

The code for computing `gist_diff` is selectbg.m.

#### 2(II).7 Best-fit background blending

We use GIST to search for the best background. For the two sources, we got different best back grounds.

The 50 candidate images are provided here.

The following are the final result. Note that we use gradient domain blending.

 source1 the best background for source1
 the result of blending source1
 source2 the best background for source2
 the result of blending source2