This paper addresses the problem of detecting digital line components in a given binary image consisting of n black dots arranged over N N integer grids. The most popular method in computer vision for this purpose is the one called Hough Transform which transforms each black point to a sinusoidal curve to detect digital line components by voting on the dual plane. We start with a definition of a line component to be detected and present several different algorithms based on the definition. The one extreme is the conventional algorithm based on voting on the subdivided dual plane while the other is the one based on topological walk on an arrangement of sinusoidal curves defined by the Hough transform. Some intermediate algorithm based on half-planar range counting is also presented. Finally, we discuss how to incorporate several practical conditions associated with minimum density and restricted maximality.

The purpose of this paper is to discuss length estimation based on digitized curves. Information on a curve in the Euclidean plane is lost after digitization. Higher resolution supports a convergence of a digital image towards the original curve with respect to Hausdorff metric. No matter how high resolution is assumed, it is impossible to know the length of an original curve exactly. In image analysis we estimate the length of a curve in the Euclidean plane based on an approximation. An approximate polygon converges to the original curve with an increase of resolution. Several approximation methods have been proposed so far. This paper proposes a new approximation method which generates polygonal curves closer (in the sense of Hausdorff metric) in general to its original curves than any of the previously known methods and discusses its relevance for length estimation by proving a Convergence Theorem.

A graph G is called an n-channel graph at vertex r if there are n independent spanning trees rooted at r. A graph G is called an n-channel graph if G is an n-channel graph at every vertex. Independent spanning trees of a graph play an important role in fault-tolerant broadcasting in the graph. In this paper we show that if G1 is an n1-channel graph and G2 is an n2-channel graph, then G1G2 is an (n1 + n2)-channel graph. We prove this fact by a construction of n1+n2 independent spanning trees of G1G2 from n1 independent spanning trees of G1 and n2 independent spanning trees of G2. As an application we describe a fault-tolerant broadcasting scheme along independent spanning trees.