Adaptive multiresolution structures for image processing on parallel computers

This paper presents a solution to the problem of creating region adjacency graph (RAG) pyramids on parallel computers comprising the hypercube topology. RAG pyramids represent hierarchies of irregular tesselations, with each tesselation generated in parallel by independent stochastic processes, and can be used for multiresolution image analysis. The outcome of the stochastic processes depends on the input data allowing the adaptation of RAG pyramids to the image content. For the extraction of connected components from labeled images, different connected components are reduced to different roots which are interconnected in a final region adjacency graph. An algorithm for implementing RAG pyramids on hypercube computers is discussed in detail and timing results are presented for the Connection Machine CM-2 supercomputer. The time complexity of the algorithm is found for the hypercube and the CRCW PRAM. The results show that the iterative process that creates a new level of the hierarchy from its preceding one does not heavily depend on the size of the graph, as its expected time is O(log N) for a random graph, where N is the total number of vertices in the input graph. The total number of levels is O(log(image_-size)), as for the regular pyramid.