1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
#include <CGAL/boost/graph/alpha_expansion_graphcut.h>
#include <boost/graph/adjacency_list.hpp>
struct Vertex_property
{
int label;
std::vector<double> cost;
};
struct Edge_property
{
double weight;
};
using Graph = boost::adjacency_list <boost::setS,
boost::vecS,
boost::undirectedS,
Vertex_property,
Edge_property>;
using GT = boost::graph_traits<Graph>;
using vertex_descriptor = GT::vertex_descriptor;
using edge_descriptor = GT::edge_descriptor;
int main()
{
std::array<char, 3> labels = { 'X', ' ', 'O' };
std::array<std::array<int, 6>, 5> input
= { { { 0, 2, 0, 1, 1, 1 },
{ 0, 0, 1, 0, 1, 2 },
{ 2, 0, 1, 1, 2, 2 },
{ 0, 1, 1, 2, 2, 0 },
{ 1, 1, 2, 0, 2, 2 } } };
std::array<std::array<vertex_descriptor, 6>, 5> vertices;
// Init vertices from values
Graph g;
for (std::size_t i = 0; i < input.size(); ++ i)
for (std::size_t j = 0; j < input[i].size(); ++ j)
{
vertices[i][j] = boost::add_vertex(g);
g[vertices[i][j]].label = input[i][j];
// Cost of assigning this vertex to any label is positive except
// for current label which is 0 (favor init solution)
g[vertices[i][j]].cost.resize(3, 1);
g[vertices[i][j]].cost[std::size_t(input[i][j])] = 0;
}
// Display input values
std::cerr << "Input:" << std::endl;
for (std::size_t i = 0; i < vertices.size(); ++ i)
{
for (std::size_t j = 0; j < vertices[i].size(); ++ j)
std::cerr << labels[std::size_t(g[vertices[i][j]].label)];
std::cerr << std::endl;
}
// Init adjacency
double weight = 0.5;
for (std::size_t i = 0; i < vertices.size(); ++ i)
for (std::size_t j = 0; j < vertices[i].size(); ++ j)
{
// Neighbor vertices are connected
if (i < vertices.size() - 1)
{
edge_descriptor ed = boost::add_edge (vertices[i][j], vertices[i+1][j], g).first;
g[ed].weight = weight;
}
if (j < vertices[i].size() - 1)
{
edge_descriptor ed = boost::add_edge (vertices[i][j], vertices[i][j+1], g).first;
g[ed].weight = weight;
}
}
std::cerr << std::endl << "Alpha expansion..." << std::endl << std::endl;
CGAL::alpha_expansion_graphcut (g,
get (&Edge_property::weight, g),
get (&Vertex_property::cost, g),
get (&Vertex_property::label, g),
CGAL::parameters::vertex_index_map (get (boost::vertex_index, g)));
// Display output graph
std::cerr << "Output:" << std::endl;
for (std::size_t i = 0; i < vertices.size(); ++ i)
{
for (std::size_t j = 0; j < vertices[i].size(); ++ j)
std::cerr << labels[std::size_t(g[vertices[i][j]].label)];
std::cerr << std::endl;
}
return 0;
}
|
