gc_readme.txt

Graph Cut algorithm implementation. Includes MATLAB compiled codes.

	
Note that only one of the above setData() functions can be used.    

------------------------dataSetup-----------------------
In case smoothSetup = SET_INDIVIDUALLY, to set the smooth cost you must use the member function 
setSmoothCost(label1,label2,cost).  This function sets V(label1,label2) = cost. Notice that
no spatially varying coefficient w_pq is allowed in this case.
If smoothSetup = SET_ALL_AT_ONCE,  to set the smoothness costs you must use any of the setSmoothness() 
functions, either by passing an array of smoothness costs, or a pointer to a function which returns 
smoothness cost. More details on different setSmoothness() functions:

(a) void setSmoothness(EnergyTermType* V);
         V is an array of smoothness costs, such that V_pq(label1,label2)  is stored at V[label1+num_labels*label2]        
	 If graph is a grid, then using this  function only if the smooth costs are not spacially varying    
	 that is the smoothness penalty V depends only on labels, but not on pixels.  If the graph is 
         not a grid, then you can specify spacially varying coefficients w_pq when you set up the
         neighborhood system using setNeighbor(p,q,w_pq) function. In this case, 
         V_pq(label1,label2) =  V[label1+num_labels*label2]*w_pq                            
	 
(b) void setSmoothness(EnergyTermType* V,EnergyTermType* hCue, EnergyTermType* vCue);
	 This function should be used only if the graph is a grid. Array V is the same as above, under (a).
         Arrays hCue and vCue have the same size as the image (that is width*height), and are used to set
         the spatially varying coefficients w_pq. If p = (x,y) and q = (x+1,y), then 
         w_pq =  hCue[x+y*width], and so the smoothness penalty for pixels (x,y) and (x+1,y) to have labels       
	 label1 and label2, that is V_pq(label1,label2) = V[label1+num_labels*label2]*hCue[x+y*width]
         If p = (x,y) and q = (x,y+q), then 
         w_pq =  vCue[x+y*width], and so the smoothness penalty for pixels (x,y) and (x,y+1) to have labels       
	  label1 and label2, that is V_pq(label1,label2) = V[label1+num_labels*label2]*vCue[x+y*width]

(c) void setSmoothness(smoothFnCoord cost);

          cost is pointer to a function f(pix1,pix2,label1,label2) such that smoothness penalty for neigboring pixels     
	  pix1 and pix2 to  have labels, respectively, label1 and label2 is f(pix1,pix2,label1,label2)         

(d)  void setSmoothness(smoothFnCoord horz_cost, smoothFnCoord vert_cost);
	 
	This function  can be used only if the graph is a grid.                                              
        horz_cost is a poineter to a function f(x,y,label1,label2) such that smoothness penalty for neigboring pixels      
	(x,y) and (x+1,y) to have labels, respectively, label1 and label2 is f(x,y,label1,label2)            
        vert_cost is a pointer to a function f(x,y,label1,label2) such that smoothness penalty for neigboring pixels      
	 /* (x,y) and (x,y+1) to have labels, respectively, label1 and label2 is f(x,y,label1,label2)            
	

Note that only one of the above setSmoothness() functions can be used.    


##################################################################

6. Optimizing the energy

You can optimize the energy and get the resulting labeling using the following functions.  Notice that they can 
be called as many times as one wishes after the constructor has been called and the data/smoothness terms
(and the neighborhood system, if general graph) has beeen set.  The initial labeling is set to consists of
all 0's. Use function setLabel(PixelType pixelP, LabelType labelL), described under heading (x) in this section
to initialize the labeling to anything else (but in the valid range, of course, labels must be between
0 and num_labels-1)


i) expansion(int max_num_iterations)
Will run the expansion algorithm up to the specified number of iterations.
Returns the energy of the resulting labeling.

ii)expansion();
Will run the expansion algorithm to convergence (convergence is guaranteed)
Returns the energy of the resulting labeling
	
iii) oneExpansionIteration();
 Performs one iteration (one pass over all labels)  of expansion algorithm, see the paper for more details.
 Returns the energy of the resulting labeling


iv)  alpha_expansion(LabelType alpha_label);
Performs  expansion on the label specified by alpha_label.  Returns the energy of the resulting labeling
	
v)	swap(int max_num_iterations);
Will run the swap algorithm up to the specified number of iterations.
Returns the energy of the resulting labeling.


vi)  swap();
Will run the swap algorithm up to convergence (convergence is guaranteed)
Returns the energy of the resulting labeling
	

vii) oneSwapIteration();
Performs one iteration (one pass over all pairs of labels)  of the swap algorithm, see the paper for more details.
Returns the energy of the resulting labeling.

	
viii) alpha_beta_swap(LabelType alpha_label, LabelType beta_label);
Performs  swap on a pair of labels, specified by the input parameters alpha_label, beta_label.
Returns the energy of the resulting labeling.


ix)	whatLabel(PixelType pixelP)
Returns the current label assigned to pixelP.  Can be called at any time after the constructor call.

x) setLabel(PixelType pixelP, LabelType labelL)
Sets the label of pixelP to the the input parameter labelL. Can be called at any time after the constructor call.
This function is useful, in particular, to  initialize the labeling to something specific before optimization starts.

xi) setLabelOrder(bool RANDOM_LABEL_ORDER)
By default, the labels for the swap and expansion algorithms are visited in random order, thus the results
are going to be slightly different each time the optimization is invoked. To set the label order to
be not random, call setLabelOrder(0).  To set it to be random again, call setLabelOrder(1). Notice,
that by using functions under heading (iv) and (viii) you can completely  and exactly specify the desired
order on labels.

xii) EnergyType giveDataEnergy();
Returns the data part of the energy of the current labling

	
xiii)	EnergyType giveSmoothEnergy();
Returns the smoothness part of the energy of the current labling

##################################################################

7. Example usage.

Example 1, uses constructor A.

__________________________________________________________________

#include <stdio.h>
#include <time.h>
#include "GCoptimization.h"

void main(int argc, char **argv)
{

	GCoptimization *optimize = (GCoptimization *) new GCoptimization(3,2, SET_INDIVIDUALLY, SET_INDIVIDUALLY);
	GCoptimization::EnergyType engS,engD,engT;

	// First set the data costs terms for each pixel and each label
	optimize ->setDataCost(0,0,5);
	optimize ->setDataCost(0,1,1);
	optimize ->setDataCost(1,0,3);
	optimize ->setDataCost(1,1,0);
	optimize ->setDataCost(2,0,-3);
	optimize ->setDataCost(2,1,3);


	//Next set the neighboring pixels
	optimize->setNeighbors(0,1,7);

	optimize->setNeighbors(1,2,5);

	//Finally, specify the remaining part of Vpq.  This is the part that
	// depends just on labels, not on  pixels, and in this case 
	// it is penalty(label1,label2) = |label1-label2|

	optimize->setSmoothCost(0,0,0);
	optimize->setSmoothCost(0,1,1);
	optimize->setSmoothCost(1,0,1);
	optimize->setSmoothCost(1,1,0);

	////////////////////////////////////////////////////////////////////////
	/* Now the energy is completely specified. Can call any optimization  */
	/* methods */

	engD = optimize->giveDataEnergy();
	engS = optimize->giveSmoothEnergy();

	printf("\nBefore optimization, the smooth energy is %d, data energy %d, total %d",engS,engD,engS+engD);

	engT = optimize->expansion(); //to run expansion algorithm to convergence
	//eng = optimize->swap();      //to run swap algorithm to convergence

	engD = optimize->giveDataEnergy();
	engS = optimize->giveSmoothEnergy();

	printf("\nAfter optimization, the smooth energy is %d, data energy %d, total %d",engS,engD,engS+engD);
	for( int i = 0; i < 3; i++ )
		printf("\nPixel %d has label %d",i,optimize->whatLabel(i));
	

}

__________________________________________________________________

Example 2, uses constructor A


#include <stdio.h>
#include <time.h>
#include "GCoptimization.h"


// Suppose we have a grid of width 3 and height 2. That is there are 6 pixels
// Suppose there are 7 labels.
// The neighborhood structure is the usual grid, so we will use constructor C
// Let the data costs be: 
// D(pixel,label) = 0  if pixel < 3 and label = 1
//                = 10 if pixel < 3 and label is not equal to 1
//                = 0  if pixel >= 3 and label = 6
//                = 10 if pixel >= 3 and label is not equal to 6

// Let the smoothness terms be the so called "Potts model",
// that is Vpq(l_p,l_q) = w_pq  if |l_p-l_q| > 1
//                      = 0     if l_p = l_q
// and let w_pq be as pictured:
//
//
//           o   __2__    o  __10__  o
//         
//           |            |          | 
//           3            1          5
//           |            |          | 
//           o   __8__    o  __4__   o
  

/****************************************************************************/

void main(int argc, char **argv)
{
	
	int num_pixels = 6, num_labels = 7, width = 3, height = 2;
	GCoptimization::EnergyTermType *datacost,*smoothcost,*vertWeights,*horizWeights;
	GCoptimization::EnergyType engS,engD,engT;

        /* First call the constructor for a grid graph */
	GCoptimization *optimize = (GCoptimization *) new GCoptimization(width,height,num_labels,SET_ALL_AT_ONCE,SET_ALL_AT_ONCE);
	
	datacost     = (GCoptimization::EnergyTermType *) new GCoptimization::EnergyTermType[num_pixels*num_labels];
	smoothcost   = (GCoptimization::EnergyTermType *) new GCoptimization::EnergyTermType[num_labels*num_labels];
	vertWeights  = (GCoptimization::EnergyTermType *) new GCoptimization::EnergyTermType[num_pixels];
	horizWeights = (GCoptimization::EnergyTermType *) new GCoptimization::EnergyTermType[num_pixels];
	
	// Fill in the datacost matrix with the correct values
	for ( int pix = 0; pix < num_pixels; pix++ )
		for ( int l = 0; l < num_labels; l++ )
		{
			if ( pix < 3 && l == 1)
				datacost[pix*num_labels+l] = 0;
			else if ( pix < 3 && l != 1)
				datacost[pix*num_labels+l] = 10;
			else if ( pix >= 3 && l == 6 )
				datacost[pix*num_labels+l] = 0;
			else datacost[pix*num_labels+l] = 10;
	

		}


	// Fill in the smoothcost matrix with the correct values
	for ( int i = 0; i < num_labels; i++ )
		for ( int j = 0; j < num_labels; j++ )
			if ( i != j )
				smoothcost[i+j*num_labels] = 1;
			else smoothcost[i+j*num_labels] = 0;
		

	// Fill in the horizontal and vertical matrices with the correct values

	vertWeights[0] =  3;
	vertWeights[1] =  1;
	vertWeights[2] =  5;

	horizWeights[0] = 2;
	horizWeights[1] = 10;
	horizWeights[3] = 8;
	horizWeights[4] = 4;

        optimize->setData(datacost);
	optimize->setSmoothness(smoothcost,horizWeights,vertWeights);

	///////////////////////////////////////////////////////////////////////
	/* Now the energy is completely specified. Can call any optimization  */
	/* methods */

	srand(time(NULL));
	//	Just for fun, start with random labeling
	for ( i = 0; i < num_pixels; i++ ) 
		optimize->setLabel(i,rand()%num_labels);



	engD = optimize->giveDataEnergy();
	engS = optimize->giveSmoothEnergy();

	printf("\nBefore optimization, the smooth energy is %d, data energy %d, total %d",engS,engD,engS+engD);

	engT = optimize->alpha_beta_swap(1,0);      //run swap algorithm on labels 1 and 0
	engD = optimize->giveDataEnergy();
	engS = optimize->giveSmoothEnergy();


	printf("\nAfter swapping labels 0 and 1, the smooth energy is %d, data energy %d, total %d",engS,engD,engS+engD);

	engT = optimize->expansion(); //run expansion algorithm to convergence

	engD = optimize->giveDataEnergy();
	engS = optimize->giveSmoothEnergy();

	printf("\nAfter optimization, the smooth energy is %d, data energy %d, total %d",engS,engD,engS+engD);
	for(  i = 0; i < num_pixels; i++ )
		printf("\nPixel %d has label %d",i,optimize->whatLabel(i));

}

__________________________________________________________________