Parallel BFS graph traversal on images using structured grid

Graph algorithms are widely used in image processing techniques. With technology advancements, image sizes are increasing, and the contents inside images are becoming more complex, resulting in increased runtimes for graph algorithms on these images. Breadth First Search (BFS) is a fundamental graph traversal approach. A key to parallelizing graph algorithms used in image processing is to parallelize the BFS graph traversal operation. In this paper, we propose using highly parallelizable structured grid computations to realize the BFS graph traversal operations. This mapping enables efficient implementation of the BFS graph traversal operations on highly parallel manycore platforms. By using such a mapping, we were able to achieve performance gains of 2× to 33× depending on image complexity.