Hierarchical Image Clustering using Boost Graph Library

Question

I am trying to do image segmentation by bottom-up hierarchical clustering, in order to obtain R regions. Starting with assumption that each pixel is a region, at each iteration two the most similar spatially adjacent regions must be merged together. The image can be of order 500 x 500, leading to a large number of initial regions.

I try to programmate RAG using GBL. First, I create a graph with number of vertices, equal to number of initial regions (number of pixels) and number of edges between regions. In other words, I will represent each link between 2 regions also as a vertex:

For 4-neighborhood:

 unsigned int nPixels = nSamples * nLines;
 int nVertices = nPixels + nLines*(nSamples-1) + (nLines-1)*nSamples;
 typedef adjacency_list<listS, vecS, directedS> Graph;
 Graph RAG(nVertices);

Then I fill in this graph, so that first nPixels vertices correspond to pixels, and others to links.

There is array that keeps in a[i] dissimilarity value between regions a and b, if a link [i] is a link of connection between a and b.

And then at each iteration I find the smallest dissimilarity value (between regions a and b), and I merge 2 corresponding regions. For that, a link becomes a new region, that I add edges between a new vertex and links previously connecting a and b to all other regions:

   //FIRST REGION - ANALYSE NEIGBORING LINKS
   //LIST OF NEIGHBORING LINKS
   tie(ei, e_end) = adjacent\_vertices(v_first, RAG);

   for (; ei!=e_end; ++ei)
   {

      e_index =index[*ei]; 
      if (LinkOrVertex[e_index]==1)
     {

         tie(vi, v_end) = adjacent\_vertices(e_index, RAG);

         if (index[*vi]==v_first)
         {
            ++vi; v_index = index[*vi]; --vi; }
            else v\_index = index[*vi];

            add\_edge(index_minDM, e_index, RAG);

            add\_edge(e_index, index_minDM, RAG);
            //...
         }

     }

and finally, I delete edges between a and b and each of previous links between them:

  clear\_vertex(v_first, RAG);

This last operation (clear_vertex) takes the longest time. This lead to the time of each iteration equal to 10-12 second, which is a lot.

Could you help me with writing this code for hierarchical clustering? Are there any more efficient ways of implementation in order to reduce the time?

Thank you very much in advance!