## 智能剪刀 实验报告

[TOC]

The tool helps a user trace the object by providing a “live wire” that automatically snaps to and wraps around the object of interest.

This program is based on the paper Intelligent Scissors for Image Composition, by Eric Mortensen and William Barrett, published in the proceedings of SIGGRAPH 1995. The way it works is that the user first clicks on a “seed point” which can be any pixel in the image. The program then computes a path from the seed point to the mouse cursor that hugs the contours of the image as closely as possible. This path, called the “live wire”, is computed by converting the image into a graph where the pixels correspond to nodes. Each node is connected by links to its 8 immediate neighbors. Note that we use the term “link” instead of “edge” of a graph to avoid confusion with edges in the image. Each link has a cost relating to the derivative of the image across that link. The path is computed by finding the minimum cost path in the graph, from the seed point to the mouse position. The path will tend to follow edges in the image instead of crossing them, since the latter is more expensive. The path is represented as a sequence of links in the graph.

### Data structures

Image is represented as a graph. Each pixel (i,j) is represented as a node in the graph, and is connected to its 8 neighbors in the image by graph links (labeled from 0 to 7), as shown in the following figure. The data structure that you will use in this project is the Pixel Node:

struct Node{
double total_cost;

Node *prev_node;

int state;//0-->init 1-->activite(in the queue) 2-->visited

int column;
int row;

Node() {
prev_node = NULL;
total_cost = max_weight;
state = 0;
}

void neighbour(int &offsetX, int &offsetY, int link_idx)
{...}

};


state is used to tag the node as being INITIAL, ACTIVE, or VISITED during the min-cost tree computation. totalCost is the minimum total cost from this node to the seed node.

prevNode points to its predecessor along the minimum cost path from the seed to that node.

column and row remember the position of the node in original image so that its neighboring nodes can be located.

void neighbour(int &offsetX, int &offsetY, int link_idx)
{

{
offsetX = 1;
offsetY = 0;
}
{
offsetX = 1;
offsetY = -1;
}
{
offsetX = 0;
offsetY = -1;
}
{
offsetX = -1;
offsetY = -1;
}
{
offsetX = -1;
offsetY = 0;
}
{
offsetX = -1;
offsetY = 1;
}
{
offsetX = 0;
offsetY = 1;
}
{
offsetX = 1;
offsetY = 1;
}
}


### Cost Function

• Computing cost for grayscale images

D(link1)=|img(i+1,j)-img(i,j-1)|/sqrt(2)

The magnitude of the intensity derivative across the horizontal links, e.g. link 0, is approximated as:

D(link 0)=|(img(i,j-1) + img(i+1,j-1))/2 - (img(i,j+1) + img(i+1,j+1))/2|/2

Similarly, the magnitude of the intensity derivative across the horizontal links, e.g. ln2, is approximated as:

D(link2)=|(img(i-1,j)+img(i-1,j-1))/2-(img(i+1,j)+img(i+1,j-1))/2|/2.

We compute the cost for each link, cost(link), by the following equation:

cost(link)=(maxD-D(link))*length(link)

• Cost for an RGB image

As in the grayscale case, each pixel has eight links. We first compute the magnitude of the intensity derivative across a link, in each color channel independently, denoted as

( DR(link),DG(link),DB(link) ).

Then the magnitude of the color derivative across link is defined as

D(link) = sqrt( (DR(link)*DR(link)+DG(link)*DG(link)+DB(link)*DB(link))/3 ).

Then we compute the cost for link link in the same way as we do for a gray scale image:

cost(link)=(maxD-D(link))*length(link).

Notice that cost(link 0) for pixel (i,j) is the same as cost(link 4) for pixel (i+1,j). Similar symmetry property also applies to vertical and diagonal links.

#### Visualisation: double* ImgLabel::compute_cost_link(QImage &img, int i, int j)
{

uint RawColor;

if((i+1) < img_width)
RawColor = img.pixel(i+1, j);
if((i+1) < img_width && (j-1) >= 0)
RawColor = img.pixel(i+1, j-1);
if((j-1) >= 0)
RawColor = img.pixel(i, j-1);
if((i-1) >= 0 && (j-1) >= 0)
RawColor = img.pixel(i-1, j-1);
if((i-1) >= 0)
RawColor = img.pixel(i-1, j);
if((i-1) >= 0 && (j+1) < img_height)
RawColor = img.pixel(i-1, j+1);
if((j+1) < img_height)
RawColor = img.pixel(i, j+1);
if((i+1) < img_width && (j+1) < img_height)
RawColor = img.pixel(i+1, j+1);

for(int k=0; k < 8; k++) {
if(k==0 && (i+1)<img_width) {
} else if(k==1&&(i+1)<img_width&&(j-1)>=0) {

} else if(k==2&&(j-1)>=0) {

} else if(k==3&&(j-1)>=0&&(i-1)>=0) {
} else if(k==4&&(i-1)>=0) {

} else if(k==5&&(i-1)>=0&&(j+1)<img_height) {
} else if(k==6&&(j+1)<img_height) {

} else if(k==7&&(i+1)<img_width&&(j+1)<img_height) {
} else {
}
}

for(int k = 0; k < 8; k++) {
int a=1;
}

}


### LiveWireDP

The pseudo code for the shortest path algorithm in the paper is a variant of Dijkstra’s shortest path algorithm:

procedure LiveWireDP

**input**: seed, graph
**output**: a minimum path tree in the input graph with each node pointing to its predecessor along the minimum cost path to that node from the seed. Each node will also be assigned a total cost, corresponding to the cost of the the minimum cost path from that node to the seed.

_comment_: each node will experience three states: INITIAL(0), ACTIVE(1), VISITED(2) sequentially. the algorithm terminates when all nodes are EXPANDED. All nodes in graph are initialized as INITIAL. When the algorithm runs, all ACTIVE nodes are kept in a priority queue, pq, ordered by the current total cost from the node to the seed.

**Begin**:
initialize the priority queue prior_queue to be empty;
initialize each node to the INITIAL state;
set the total cost of seed to be zero and make seed the root of the minimum path tree ( pointing to NULL ) ;

insert seed into pq;

while pq is not empty
extract the node q with the minimum total cost in pq;
mark q as VISITED;
for each neighbor node r of q
if r has not been VISITED
if r is still INITIAL
make q be the predecessor of r ( for the the minimum path tree );
set the total cost of r to be the sum of the total cost of q and link cost from q to r as its total cost;
insert r in pq and mark it as ACTIVE;
else if r is ACTIVE, e.g., in already in the pq
if the sum of the total cost of q and link cost between q and r is less than the total cost of r
update q to be the predecessor of r ( for the minimum path tree );
update the total cost of r in pq;
**End**


// LiveWireDP.cpp
void LiveWireDP::compute_paths(vertex_t source, node_list &node_graph, int width, int height) {

node_graph[source]->total_cost = 0;

priority_queue<Node*, vector<Node*>, compare> prior_queue;
prior_queue.push(node_graph[source]);

while(!prior_queue.empty()) {

Node *temp = prior_queue.top();
prior_queue.pop();

temp->state = 2;//mark the state to be visited

int p = temp->column;//x_axis
int q = temp->row;//y_axis

int index = q*width + p;

for(int i = 0; i < 8; i++) {
int offsetx, offsety, new_index;

temp->neighbour(offsetx, offsety, i);//get the offset of each nodes
int n_p = p + offsetx;//this nodes axis
int n_q = q + offsety;//this nodes axis

if(n_p >= 0 && n_q >= 0 && n_p < width && n_q < height) {
new_index = n_q*width + n_p;
} //inside the range

int new_state = node_graph[new_index]->state;

if(new_state != 2) { //not visited now
if(new_state == 0) {  //still initial (not visit)
node_graph[new_index]->prev_node = node_graph[index];
node_graph[new_index]->state = 1;//active

prior_queue.push(node_graph[new_index]);
} else if(new_state == 1) {
node_graph[new_index]->prev_node = node_graph[index];
}
}
}
}


### Run Demo

File -> Open -> select a image. Click 开始： When finished the “circle”: File -> Save Contour  