blob: 1abe19fc303cbc4146f71c9dde9f134aa876b6dc [file] [log] [blame]
Urvang Joshia22aca52020-03-04 12:12:56 -08001/*
2Copyright (C) 2006 Pedro Felzenszwalb
3
4This program is free software; you can redistribute it and/or modify
5it under the terms of the GNU General Public License as published by
6the Free Software Foundation; either version 2 of the License, or
7(at your option) any later version.
8
9This program is distributed in the hope that it will be useful,
10but WITHOUT ANY WARRANTY; without even the implied warranty of
11MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12GNU General Public License for more details.
13
14You should have received a copy of the GNU General Public License
15along with this program; if not, write to the Free Software
16Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17*/
18
19#ifndef SEGMENT_GRAPH
20#define SEGMENT_GRAPH
21
22#include <algorithm>
23#include <cmath>
24#include "third_party/segment/disjoint-set.h"
25
26// threshold function
27#define THRESHOLD(size, c) (c / size)
28
29typedef struct {
30 float w;
31 int a, b;
32} edge;
33
34bool operator<(const edge &a, const edge &b) { return a.w < b.w; }
35
36/*
37 * Segment a graph
38 *
39 * Returns a disjoint-set forest representing the segmentation.
40 *
41 * num_vertices: number of vertices in graph.
42 * num_edges: number of edges in graph
43 * edges: array of edges.
44 * c: constant for treshold function.
45 */
46universe *segment_graph(int num_vertices, int num_edges, edge *edges, float c) {
47 // sort edges by weight
48 std::sort(edges, edges + num_edges);
49
50 // make a disjoint-set forest
51 universe *u = new universe(num_vertices);
52
53 // init thresholds
54 float *threshold = new float[num_vertices];
55 for (int i = 0; i < num_vertices; i++) threshold[i] = THRESHOLD(1, c);
56
57 // for each edge, in non-decreasing weight order...
58 for (int i = 0; i < num_edges; i++) {
59 edge *pedge = &edges[i];
60
61 // components conected by this edge
62 int a = u->find(pedge->a);
63 int b = u->find(pedge->b);
64 if (a != b) {
65 if ((pedge->w <= threshold[a]) && (pedge->w <= threshold[b])) {
66 u->join(a, b);
67 a = u->find(a);
68 threshold[a] = pedge->w + THRESHOLD(u->size(a), c);
69 }
70 }
71 }
72
73 // free up
Urvang Joshid89b3402020-05-18 15:14:32 -070074 delete[] threshold;
Urvang Joshia22aca52020-03-04 12:12:56 -080075 return u;
76}
77
78#endif