IEPF Line Extraction Algorithm

Iterative End Point Fit — Line extraction for SLAM and robotics

---

📋 Overview

IEPF (Iterative End Point Fit) is a recursive line extraction algorithm commonly used in SLAM (Simultaneous Localization and Mapping) for mobile robotics. It takes a point cloud — typically from a LiDAR, depth camera, or sonar — and segments it into straight line segments.

The algorithm works by:

1. Drawing a line between the first and last point of a cluster
2. Finding the point with the greatest perpendicular distance to that line
3. If that distance exceeds a threshold, split the cluster at that point
4. Repeat recursively on each sub-cluster

Each extracted line is represented as:

---

✨ Features

• Pure Python — no ROS dependency, runs anywhere
• Recursive splitting — automatically finds optimal segmentation
• Threshold-controlled — tune line sensitivity with a single parameter
• Visualization included — plots results with matplotlib
• Minimal dependencies — just numpy, pandas, matplotlib

---

🚀 Quick Start

# Clone
git clone https://github.com/ekorudiawan/IEPF-Line-Extraction.git
cd IEPF-Line-Extraction

# Install deps
pip install -r requirements.txt

# Run
python Source-Code/iepf_core.py

Install as a package

pip install -e .

---

🧠 How It Works

IEPF is a top-down recursive algorithm:

1. Start with the full point set and its two endpoints
2. Fit a line through the endpoints
3. Measure perpendicular distance from every point to that line
4. If the max distance > threshold, split at that point
5. Recurse on each segment
6. Output: ordered list of line segments with endpoints

The animated demo above shows this process step by step in 3 iterations.

---

📁 Project Structure

IEPF-Line-Extraction/
├── Source-Code/
│   ├── iepf_core.py          # Main IEPF algorithm
│   ├── dataset.csv           # Sample LiDAR point cloud
│   └── generate_demo.py      # Demo GIF generator
├── Images/
│   ├── iepf_demo.gif         # Animated algorithm walkthrough
│   ├── Demo1.png             # Static result 1
│   ├── Demo2.png             # Static result 2
│   └── Equation1.png         # Line equation
├── pyproject.toml            # Package config
├── requirements.txt          # Dependencies
├── LICENSE                   # MIT license
└── README.md

---

⚙️ Parameters

Parameter	Default	Description
d_threshold	50	Max perpendicular distance (pixels). Lower = more segments.

Higher threshold → fewer, longer line segments (more aggressive merging).
Lower threshold → more detailed segmentation (finer detail preserved).

---

📚 References

• Nguyen, Viet, et al. "A comparison of line extraction algorithms using 2D laser rangefinder for indoor mobile robotics." IROS 2005. IEEE
• Einsele, Tobias. "Real-time self-localization in unknown indoor environment using a panorama laser range finder." IROS 1997. IEEE
• Lv, Jixin, et al. "Straight line segments extraction and EKF-SLAM in indoor environment." Journal of Automation and Control Engineering 2.3 (2014). ResearchGate

---

📄 License

MIT © Eko Rudiawan Jamzuri