Robotics Research Technical Report: Design of Fast Connected Components Hardware (Classic Reprint) - Tapa blanda

Excerpt from Robotics Research Technical Report: Design of Fast Connected Components Hardware

The algorithm consists of two passes. Pass 1 sweeps through the rows from bot tom to top, during which the groups in Gp are calculated inductively from the knowledge of Rp+1 by a simple updating rule. Pass 2 sweeps from top to bottom to assign component numbers to each pixel and outputs this symbolic image.

In each row, runs belonging to the same group are associated by a simple mechanism, called bracket marking, as follows.

About the Publisher

Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com

This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.

Excerpt from Robotics Research Technical Report: Design of Fast Connected Components Hardware

The intensive use of the connected components algorithm in image analysis and robot vision calls for a very fast implementation of such algorithm suitable for real-time applications. This paper presents a hardware design implementing the algorithm due to Schwartz, Sharir, and Siegel). A prototype board, without using special VLSI chips, had been constructed in Robotics Research Lab of Courant Institute. It can compute the connected components of a 512 x 512 binary image in few video frame times (about 300 ms). A real-time version (video speed) in VLSI is proposed.

The labeling of connected components of a binary image is a fundamental problem in image analysis. An early method was developed by Rosenfeld and Pfaltz in 1966; it uses a pair of arrays, one containing the current region label and the other containing its smallest equivalent label. This algorithm processes the image from top to bottom to compute label equivalences, storing the result in the arrays. A second pass reassigns each label to its smallest equivalent label. Lumia, Shapiro, and Zuniga improved the previous method by using a very short equivalence table, which needs to cover only one line. Schwartz, Sharir, and Siegel present a method which uses bracket marking to associate equivalent groups. This method enables one to compute the component numbers for each pixel on the fly, by using an relative small auxiliary 'bracket table.' More interestingly, this algorithm uses only simple form of pushdown-stacks, making high-speed hardware realization possible. In addition to the above mentioned sequential algorithms, Shiloach and Vishkin present a logarithmic-time connected components algorithm known for massively parallel computing systems (e.g.1 processor per pixel) connected in shuffle exchange or other similar pattern.

In this paper, we present a hardware implementation of the algorithm due to Schwartz, Sharir, and Siegel. In the following sections, data structures and algorithm are described in detail. Then the hardware design realizing the algorithm is presented. A prototype Connected Components Board, which does not use any specially designed VLSI chips, has been constructed at Robotics Research Lab. of Courant Institute, NYU. It can label the connected components of a 512 x 512 binary image in just a few video-frame times (about 300 ms). Real-time computation (i.e. video speed) can be achieved without significant redesigning by pipelining the two major computing components of the board.

About the Publisher

Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com

This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.