Biblioteca de gráficos Boost: inserción de bordes lenta para gráficos grandes

Question

Estoy tratando de implementar una "tijera inteligente" para una segmentación de imágenes interactiva. Por lo tanto, tengo que crear un gráfico dirigido desde una imagen donde cada vértice representa un solo píxel. Cada vértice se conecta a cada uno de sus vecinos por dos bordes: uno de salida y otro de entrada. Esto se debe al hecho de que el costo de un borde (a, b) puede diferir del costo de (b, a). Estoy usando imágenes con un tamaño de 512 * 512 píxeles, así que necesito crear un gráfico con 262144 vértices y 2091012 bordes. Actualmente, estoy usando el siguiente gráfico:

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; 

estoy usando una clase adicional Gráfico (lo siento por el nombramiento sin inspiración), que se encarga de la gráfica:

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(); 

};

Crear un nuevo gráfico con 262144 vértices es bastante rápido, pero la inserción de los bordes lleva hasta 10 segundos, lo que es demasiado lento para la aplicación deseada. En este momento, estoy insertando los bordes de la siguiente manera:

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 
    } 
} 

¿Hay algo que pueda hacer mejoran la velocidad de la Programm? Estoy usando Microsoft Visual C++ 2010 Express en modo de lanzamiento con optimización (recomendado por Boost). Pensé que podría usar un listS contenedor para los vértices o los bordes, pero los vértices no son un problema y si uso listS para los bordes, se vuelve aún más lento.

Answer 1

adjacency_list es muy general; desafortunadamente nunca va a ser tan eficiente como una solución que explote la regularidad de tu caso particular de uso. BGL no es magia.

Su mejor apuesta es, probablemente, para llegar a la representación gráfica eficiente que tendría que utilizar en ausencia de BGL (pista: para un gráfico de píxeles vecinos de una imagen, esto es no va a asignar de forma explícita todos los nodos y bordes de objetos) y luego ajustar BGL a él (example), o equivalentemente solo implementar directamente una contraparte de las plantillas existentes adjacency_list/adjacency_matrix (concept guidelines) sintonizadas a las regularidades de su sistema.

Por una representación optimizada, por supuesto me refiero a una en la que no se almacenan todos los nodos y bordes explícitamente, sino que solo se puede iterar sobre enumeraciones de los nodos y bordes implícitos que surgen del hecho de que la imagen es un tamaño particular. Lo único que realmente debe almacenar es una matriz de contrapesos.