Adaptive multiresolution structures for image processing on parallel computers

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)475-483
Number of pages9
JournalJournal of Parallel and Distributed Computing
Volume23
Issue number3
DOIs
StatePublished - Dec 1994

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Adaptive multiresolution structures for image processing on parallel computers'. Together they form a unique fingerprint.

Cite this