Hi,
I am trying to use incremental connected components to find the
connected components of an image as I randomly add pixels to the
image. I calculate the number of components after each pixel is added.
This crashes part way through. Any help would be greatly appreciated.
Chris
#include
#include
#include
#include
#include <algorithm>
#include <numeric>
#include
int main()
{
// Image size
size_t width = 100;
size_t height = 100;
// Create vector of randomized indices
std::vector indices(width*height,1);
indices[0] = 0;
std::partial_sum(indices.begin(),indices.end(),indices.begin());
std::random_shuffle(indices.begin(),indices.end());
// Create image which holds which pixels were stored by their linear index
boost::multi_array added_pixels(boost::extents[height][width]);
for(size_t i=0;i Graph;
typedef graph_traits<Graph>::vertex_descriptor Vertex;
typedef graph_traits<Graph>::vertices_size_type size_type;
Graph G(indices.size());
std::vector rank(num_vertices(G));
std::vector<Vertex> parent(num_vertices(G));
typedef size_type* Rank;
typedef Vertex* Parent;
disjoint_sets ds(&rank[0],&parent[0]);
initialize_incremental_components(G,ds);
incremental_components(G,ds);
// Loop over indices and add pixels to image, and edges to graph
std::vector::iterator b_iter = indices.begin();
for(;b_iter!=indices.end();++b_iter)
{
size_t r = (*b_iter)/width;
size_t c = (*b_iter)%width;
size_t j = *b_iter;
added_pixels[r][c] = j;
if(r>0 && added_pixels[r-1][c])
{
add_edge(j,added_pixels[r-1][c],G);
ds.union_set(j,added_pixels[r-1][c]);
}
if(r<(height-1) && added_pixels[r+1][c])
{
add_edge(j,added_pixels[r+1][c],G);
ds.union_set(j,added_pixels[r+1][c]);
}
if(c>0 && added_pixels[r][c-1])
{
add_edge(j,added_pixels[r][c-1],G);
ds.union_set(j,added_pixels[r][c-1]);
}
if(c<(width-1) && added_pixels[r][c+1])
{
add_edge(j,added_pixels[r][c+1],G);
ds.union_set(j,added_pixels[r][c+1]);
}
// After each pixel is added and connected, compute the number of cc's
typedef component_index<unsigned int> Components;
Components comp(parent.begin(),parent.end());
std::cout << comp.size() << std::endl;
}
return 0;
}
Chris Weed