TGGLinesPlus: A robust topological graph-guided computer vision algorithm for line detection from images

Wenbin Zhang, Liping Yang, Joshua Driscol, Ming Gong, Shujie Wang, Catherine G. Potts

Abstract

TGGLinesPlus is a parameter-free algorithm that reimagines line detection by treating images as topological graphs rather than simple pixel collections. By leveraging image skeletons and graph theory, it extracts clean, continuous line segments from challenging sources like satellite imagery, medical scans, and scanned documents, outperforming traditional gradient-based methods.

Introduction

Line detection is a cornerstone of computer vision, essential for applications ranging from autonomous vehicle lane detection to medical mapping of blood vessels. However, classic tools like the Hough Transform or the Line Segment Detector (LSD) were primarily designed for natural images with clear gradients. When faced with "technical" images—such as low-resolution scans, noisy satellite data, or handwritten characters—these traditional methods often produce fragmented results or require extensive manual parameter tuning. TGGLinesPlus addresses these challenges by mimicking human perception of connectivity and shape, regardless of the image domain.

Methodology

The core innovation of TGGLinesPlus is its transition from pixel space to topological space. The workflow follows a sophisticated four-stage pipeline:

  1. Skeletonization: The algorithm first binarizes the image and applies the Zhang-Suen thinning algorithm to create a "skeleton" where every line is exactly one pixel wide.
Skeletonization of a handwritten digit, reducing the structure to a single-pixel width.
  1. Graph Construction: Every pixel in the skeleton is converted into a node in a graph, with edges connecting neighboring pixels. This transforms the visual data into a structured mathematical format.
The resulting topological graph where pixels are mapped to numbered nodes (0-50) and edges represent connectivity.
  1. Topological Cleaning: The algorithm employs clique detection to identify primary junction nodes. It removes redundant edges that would otherwise cause over-segmentation or artificial turns in the detected lines.
  2. Path Segmentation: Finally, terminal and junction nodes are used to segment the graph into distinct, continuous paths.

Unlike its predecessors, TGGLinesPlus is entirely parameter-free, relying on the inherent geometry of the skeleton rather than user-defined thresholds.

Key Insights

  • Topology Over Gradients: By prioritizing connectivity (topology) over local brightness changes (gradients), the method is resilient to shadows and shading that typically confuse standard detectors.
  • Structured Data Output: Instead of a filtered image, the algorithm returns a Python dictionary containing nodes, edges, and paths, making it immediately compatible with downstream machine learning or Geographic Information Systems (GIS).
  • Scale Invariance: Because the method operates on skeletons, the resulting graph remains a stable representation of the underlying shape whether the original line was 5 or 50 pixels wide.

Results and Performance

In benchmarks against major methods including PPHT, LSD, and EDLines, TGGLinesPlus demonstrated significant advantages in connectivity and robustness. In complex document analysis, where traditional methods like LSD found only a fraction of the structure (87 components vs. a ground truth of 283), TGGLinesPlus successfully identified 229 components. It also effectively handled "self-looped" lines (such as the letter 'o'), a common failure point for earlier graph-based algorithms.

Conclusion and Future Work

While TGGLinesPlus offers a robust solution for line detection, its performance is currently tied to the quality of initial binarization and skeletonization. Future research aims to parallelize subgraph processing to handle high-resolution datasets in real-time and extend the topological graph approach from 2D imagery to 3D volumetric data.

Summary updated

BibTeX
@article{zhang2025tgglinesplus,
  author = {Wenbin Zhang and Liping Yang and Joshua Driscol and Ming Gong and Shujie Wang and Catherine G. Potts},
  title = {{TGGLinesPlus: A robust topological graph-guided computer vision algorithm for line detection from images}},
  journal = {Transactions},
  year = {2025},
  doi = {10.1111/tgis.70015},
}
Figure