Orthogonal Zig-Zag: An algorithm for vectorizing engineering drawings compared with Hough Transform

Vectorization is the process of extracting bars (straight line segments) from a binary image. It is the first processing step in a system for understanding engineering drawings. This work presents the Orthogonal Zig-Zag (OZZ) algorithm as an efficient vectorization method, shows its suitability to vectorization of engineering drawings and compares it to the Hough Transform (HT). The underlying idea of OZZ is inspired by a light beam conducted by an optic fiber: a one-pixel-wide 'ray' travels through a black pixel area designating a bar, as if it were a conducting pipe. The ray's trajectory is parallel to the drawing axes, and its course zig-tags orthogonally, changing direction by 90 degrees each time a white area is encountered. Accumulated statistics about the two sets of black run-lengths gathered along the way provide data for deciding about the presence of a bar, its endpoints and its width, and enable skipping junctions. Using the object-process analysis methodology, the paper provides an overview of the OZZ algorithm by explicitly showing the algorithm's procedures and the corresponding processes they support. The performance of OZZ is demonstrated on a sample of engineering drawings and compared to HT. The work shows theoretically and empirically that the sparse-pixel approach of OZZ results in about twenty-fold reduction in both space and time complexity compared to HT, while the recognition quality is about 40% higher. (C) 1997 Elsevier Science Limited. All rights reserved.