segment-graph.h
Go to the documentation of this file.
00001 /*
00002 Copyright (C) 2006 Pedro Felzenszwalb
00003 
00004 This program is free software; you can redistribute it and/or modify
00005 it under the terms of the GNU General Public License as published by
00006 the Free Software Foundation; either version 2 of the License, or
00007 (at your option) any later version.
00008 
00009 This program is distributed in the hope that it will be useful,
00010 but WITHOUT ANY WARRANTY; without even the implied warranty of
00011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00012 GNU General Public License for more details.
00013 
00014 You should have received a copy of the GNU General Public License
00015 along with this program; if not, write to the Free Software
00016 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
00017 */
00018 
00019 #ifndef SEGMENT_GRAPH
00020 #define SEGMENT_GRAPH
00021 
00022 #include <algorithm>
00023 #include <cmath>
00024 #include "disjoint-set.h"
00025 
00026 // threshold function
00027 #define THRESHOLD(size, c) (c/size)
00028 
00029 typedef struct {
00030   float w;
00031   int a, b;
00032 } edge;
00033 
00034 bool operator<(const edge &a, const edge &b) {
00035   return a.w < b.w;
00036 }
00037 
00038 /*
00039  * Segment a graph
00040  *
00041  * Returns a disjoint-set forest representing the segmentation.
00042  *
00043  * num_vertices: number of vertices in graph.
00044  * num_edges: number of edges in graph
00045  * edges: array of edges.
00046  * c: constant for treshold function.
00047  */
00048 universe *segment_graph(int num_vertices, int num_edges, edge *edges, 
00049                         float c) { 
00050   // sort edges by weight
00051   std::sort(edges, edges + num_edges);
00052 
00053   // make a disjoint-set forest
00054   universe *u = new universe(num_vertices);
00055 
00056   // init thresholds
00057   float *threshold = new float[num_vertices];
00058   for (int i = 0; i < num_vertices; i++)
00059     threshold[i] = THRESHOLD(1,c);
00060 
00061   // for each edge, in non-decreasing weight order...
00062   for (int i = 0; i < num_edges; i++) {
00063     edge *pedge = &edges[i];
00064     
00065     // components conected by this edge
00066     int a = u->find(pedge->a);
00067     int b = u->find(pedge->b);
00068     if (a != b) {
00069       if ((pedge->w <= threshold[a]) &&
00070           (pedge->w <= threshold[b])) {
00071         u->join(a, b);
00072         a = u->find(a);
00073         threshold[a] = pedge->w + THRESHOLD(u->size(a), c);
00074       }
00075     }
00076   }
00077 
00078   // free up
00079   delete threshold;
00080   return u;
00081 }
00082 
00083 #endif


iri_leaf_segmentation
Author(s): Sergi Foix
autogenerated on Fri Dec 6 2013 20:27:24