This paper describes a new method of extracting straight Lines based on unsupervised line clustering. It is assumed that each line support region (LSR) in an image is composed of pixels that share similar gradient orientation values. Therefore, by an appropriate partitioning of gradient space, the sets of parallel lines can be more easily extracted. Previous works on partitioning gradient space, however, relied on ad hoc methods, and cannot be used as reliable tools for the extraction of the number of clusters in gradient space. In order to handle such a clustering issue, the Bhattacharyya distance is introduced to define a measure for cluster separability and thereafter to estimate the number of inherent clusters. Subsequent to the clustering stage, each extracted line support region undergoes a consistency test to evaluate its validity In terms of uncertainty descriptors. For the consistency test, an entropy-based line selection scheme is formulated and a theory from robust statistics is adopted. The feasibility of the proposed line extraction method is assessed by considering the issue of vanishing point detection. (C) 1999 Pattern Recognition Society. Published by Elsevier Science Ltd. All rights reserved.