Я пытаюсь использовать "интеллектуальные ножницы" для интерактивной сегментации изображения. Поэтому мне нужно создать ориентированный граф из изображения, где каждая вершина представляет один пиксель. Затем каждая вершина соединяется с каждым из своих соседей двумя ребрами: одним исходящим и одним входящим.Это связано с тем, что стоимость ребра (a, b) может отличаться от стоимости (b, a). Я использую изображения размером 512 * 512 пикселей, поэтому мне нужно создать граф с 262144 вершинами и 2091012 краями. В настоящее время я использую следующий график:
typedef property<vertex_index_t, int,
property<vertex_distance_t, double,
property<x_t, int,
property<y_t, int
>>>> VertexProperty;
typedef property<edge_weight_t, double> EdgeProperty;
// define MyGraph
typedef adjacency_list<
vecS, // container used for the out-edges (list)
vecS, // container used for the vertices (vector)
directedS, // directed edges (not sure if this is the right choice for incidenceGraph)
VertexProperty,
EdgeProperty
> MyGraph;
Я использую дополнительный класс Graph (извините за скучное именование), который обрабатывает график:
class Graph
{
private:
MyGraph *graph;
property_map<MyGraph, vertex_index_t>::type indexmap;
property_map<MyGraph, vertex_distance_t>::type distancemap;
property_map<MyGraph, edge_weight_t>::type weightmap;
property_map<MyGraph, x_t>::type xmap;
property_map<MyGraph, y_t>::type ymap;
std::vector<MyGraph::vertex_descriptor> predecessors;
public:
Graph();
~Graph();
};
Создание нового Граф с 262144 вершинами довольно быстр, но вставка ребер занимает до 10 секунд, что слишком медленно для желаемого приложения. Прямо сейчас я вставляю края следующим образом:
tie(vertexIt, vertexEnd) = vertices(*graph);
for(; vertexIt != vertexEnd; vertexIt++){
vertexID = *vertexIt;
x = vertexID % 512;
y = (vertexID - x) / 512;
xmap[vertexID] = x;
ymap[vertexID] = y;
if(y > 0){
if(x > 0){
tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y-1)+(x-1)], *graph); // upper left neighbour
}
tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y-1)+(x)], *graph); // upper
if(x < 511){
tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y-1)+(x+1)], *graph); // upper right
}
}
if(x < 511){
tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y)+(x+1)], *graph); // right
}
if(y < 511){
if(x > 0){
tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y+1)+(x-1)], *graph); // lower left
}
tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y+1)+(x)], *graph); // lower
if(x < 511){
tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y+1)+(x+1)], *graph); // lower right
}
}
if(x > 0){
tie(edgeID, ok) = add_edge(vertexID, indexmap[IRES2D*(y)+(x-1)], *graph); // left
}
}
Могу ли я что-нибудь сделать, чтобы повысить скорость работы программы? Я использую Microsoft Visual C ++ 2010 Express в режиме выпуска с оптимизацией (в соответствии с рекомендациями Boost). Я подумал, что могу использовать контейнер listS для вершин или ребер, но с вершинами проблем нет, а если я использую listS для ребер, он становится еще медленнее.