Posts /

智能剪刀

Twitter Facebook
22 Apr 2017

智能剪刀 实验报告

[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* link_cost;  // double link_cost[8]
    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)
    {...}

};

linkCost contains the costs of each link, as described above.

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)
    {

        if (link_idx == 0)
        {
            offsetX = 1;
            offsetY = 0;
        }
        else if (link_idx == 1)
        {
            offsetX = 1;
            offsetY = -1;
        }
        else if (link_idx == 2)
        {
            offsetX = 0;
            offsetY = -1;
        }
        else if (link_idx == 3)
        {
            offsetX = -1;
            offsetY = -1;
        }
        else if (link_idx == 4)
        {
            offsetX = -1;
            offsetY = 0;
        }
        else if (link_idx == 5)
        {
            offsetX = -1;
            offsetY = 1;
        }
        else if (link_idx == 6)
        {
            offsetX = 0;
            offsetY = 1;
        }
        else if (link_idx == 7)
        {
            offsetX = 1;
            offsetY = 1;
        }
    }

Cost Function

Visualisation:

double* ImgLabel::compute_cost_link(QImage &img, int i, int j)
{
     double *costlink = new double[8];

     double RDlink[8];
     double GDlink[8];
     double BDlink[8];

     uint RawColor[8];

     if((i+1) < img_width)
        RawColor[0] = img.pixel(i+1, j);
     if((i+1) < img_width && (j-1) >= 0)
        RawColor[1] = img.pixel(i+1, j-1);
     if((j-1) >= 0)
        RawColor[2] = img.pixel(i, j-1);
     if((i-1) >= 0 && (j-1) >= 0)
        RawColor[3] = img.pixel(i-1, j-1);
     if((i-1) >= 0)
        RawColor[4] = img.pixel(i-1, j);
     if((i-1) >= 0 && (j+1) < img_height)
        RawColor[5] = img.pixel(i-1, j+1);
     if((j+1) < img_height)
        RawColor[6] = img.pixel(i, j+1);
     if((i+1) < img_width && (j+1) < img_height)
        RawColor[7] = img.pixel(i+1, j+1);

     for(int k=0; k < 8; k++) {
         if(k==0 && (i+1)<img_width) {
             RDlink[k]=abs((qRed(RawColor[2])+qRed(RawColor[1]))/2-(qRed(RawColor[6])+qRed(RawColor[7]))/2)/2;
             GDlink[k]=abs((qGreen(RawColor[2])+qGreen(RawColor[1]))/2-(qGreen(RawColor[6])+qGreen(RawColor[7]))/2)/2;
             BDlink[k]=abs((qBlue(RawColor[2])+qBlue(RawColor[1]))/2-(qBlue(RawColor[6])+qBlue(RawColor[7]))/2)/2;
         } else if(k==1&&(i+1)<img_width&&(j-1)>=0) {
             RDlink[k]=abs((qRed(RawColor[2])-qRed(RawColor[0])))/sqrt(2.0);
             GDlink[k]=abs((qGreen(RawColor[2])-qGreen(RawColor[0])))/sqrt(2.0);
             BDlink[k]=abs((qBlue(RawColor[2])-qBlue(RawColor[0])))/sqrt(2.0);

         } else if(k==2&&(j-1)>=0) {
             RDlink[k]=abs((qRed(RawColor[3])+qRed(RawColor[4]))/2-(qRed(RawColor[1])+qRed(RawColor[0]))/2)/2;
             GDlink[k]=abs((qGreen(RawColor[3])+qGreen(RawColor[4]))/2-(qGreen(RawColor[1])+qGreen(RawColor[0]))/2)/2;
             BDlink[k]=abs((qBlue(RawColor[3])+qBlue(RawColor[4]))/2-(qBlue(RawColor[1])+qBlue(RawColor[0]))/2)/2;

         } else if(k==3&&(j-1)>=0&&(i-1)>=0) {
             RDlink[k]=abs((qRed(RawColor[2])-qRed(RawColor[4])))/sqrt(2.0);
             GDlink[k]=abs((qGreen(RawColor[2])-qGreen(RawColor[4])))/sqrt(2.0);
             BDlink[k]=abs((qBlue(RawColor[2])-qBlue(RawColor[4])))/sqrt(2.0);
         } else if(k==4&&(i-1)>=0) {
             RDlink[k]=abs((qRed(RawColor[3])+qRed(RawColor[2]))/2-(qRed(RawColor[5])+qRed(RawColor[6]))/2)/2;
             GDlink[k]=abs((qGreen(RawColor[3])+qGreen(RawColor[2]))/2-(qGreen(RawColor[5])+qGreen(RawColor[6]))/2)/2;
             BDlink[k]=abs((qBlue(RawColor[3])+qBlue(RawColor[2]))/2-(qBlue(RawColor[5])+qBlue(RawColor[6]))/2)/2;

         } else if(k==5&&(i-1)>=0&&(j+1)<img_height) {
             RDlink[k]=abs((qRed(RawColor[6])-qRed(RawColor[4])))/sqrt(2.0);
             GDlink[k]=abs((qGreen(RawColor[6])-qGreen(RawColor[4])))/sqrt(2.0);
             BDlink[k]=abs((qBlue(RawColor[6])-qBlue(RawColor[4])))/sqrt(2.0);
         } else if(k==6&&(j+1)<img_height) {
             RDlink[k]=abs((qRed(RawColor[4])+qRed(RawColor[5]))/2-(qRed(RawColor[0])+qRed(RawColor[7]))/2)/2;
             GDlink[k]=abs((qGreen(RawColor[4])+qGreen(RawColor[5]))/2-(qGreen(RawColor[0])+qGreen(RawColor[7]))/2)/2;
             BDlink[k]=abs((qBlue(RawColor[4])+qBlue(RawColor[5]))/2-(qBlue(RawColor[0])+qBlue(RawColor[7]))/2)/2;

         } else if(k==7&&(i+1)<img_width&&(j+1)<img_height) {
             RDlink[k]=abs((qRed(RawColor[6])-qRed(RawColor[0])))/sqrt(2.0);
             GDlink[k]=abs((qGreen(RawColor[6])-qGreen(RawColor[0])))/sqrt(2.0);
             BDlink[k]=abs((qBlue(RawColor[6])-qBlue(RawColor[0])))/sqrt(2.0);
         } else {
             RDlink[k]=max_weight ;
             GDlink[k]=max_weight ;
             BDlink[k]=max_weight ;
         }
     }

     for(int k = 0; k < 8; k++) {
         costlink[k]=sqrt((255-RDlink[k])*(255-RDlink[k])+(255-GDlink[k])*(255-GDlink[k])+(255-BDlink[k])*(255-BDlink[k]))/3;
         int a=1;
         costlink[k]=255*(1/(1+exp(-a*costlink[k]+127.5*a)));
     }

     return costlink;
}

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**

对应的 c++ 代码为:

// 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]->total_cost = node_graph[index]->total_cost + node_graph[index]->link_cost[i];
                              node_graph[new_index]->state = 1;//active

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

Run Demo

File -> Open -> select a image.

Click 开始:

When finished the “circle”:

File -> Save Contour

File -> Save Mask


Twitter Facebook