📐 Hough Transform for Line Detection

Parameter Space, Voting, Accumulator, Mathematics & Beginner Python

📌 1. What is the Hough Transform?

```

The Hough Transform is a feature extraction technique used in digital image processing and computer vision to detect geometric shapes, especially straight lines.

Instead of directly searching for complete lines in an image, the Hough Transform converts image points into a parameter space. Points that belong to the same geometric line produce votes that accumulate around the corresponding line parameters.

Simple idea: Edge pixels vote for possible lines. A strong concentration of votes indicates a possible detected line.

```

🎯 2. Why Do We Use Hough Transform?

```

📏 Line Detection

Detects straight lines even when the line is broken into separate edge segments.

🛣️ Road Analysis

Useful for detecting approximately straight road or lane markings.

📄 Document Analysis

Can identify borders and straight structures in documents.

🤖 Computer Vision

Provides geometric information for higher-level vision tasks.

```

📐 3. Equation of a Straight Line

```

A common Cartesian representation of a straight line is:

y = mx + c

where:

• m = slope
• c = y-intercept

However, this representation has a problem for vertical lines because their slope approaches infinity.

Therefore, the Hough Transform commonly uses the polar form.

```

📊 4. Polar Representation

```

The Hough line equation is commonly represented as:

ρ = x cos θ + y sin θ

where:

ρ (Rho)

Perpendicular distance from the origin to the line.

θ (Theta)

Angle of the perpendicular from the origin to the line.

x, y

Coordinates of an image point.

```

🔄 5. Basic Idea of Voting

```

Suppose an edge pixel has coordinates (x,y).

For many possible values of θ, we calculate:

ρ = x cos θ + y sin θ

Every calculated pair (ρ,θ) receives a vote in an accumulator array.

If several image points belong to the same line, their votes accumulate around the same parameter pair.

Key concept: A peak in Hough parameter space represents a strong candidate line.

```

📈 6. Accumulator Array

```

The accumulator is a two-dimensional data structure indexed by ρ and θ.

A(ρ,θ)

Whenever an edge point votes for a particular parameter pair, the corresponding accumulator cell is increased.

A(ρ,θ) ← A(ρ,θ) + 1

Large accumulator values indicate that many image points support that particular line.

```

🔬 7. Hough Transform Step-by-Step

```

1. Read the input image.
2. Convert it into grayscale.
3. Detect edges, commonly using Canny.
4. Find the coordinates of edge pixels.
5. Choose possible values of θ.
6. Calculate ρ for every edge point and θ.
7. Increment the corresponding accumulator cell.
8. Search for high accumulator values.
9. Convert the detected parameters back into image lines.

```

🧮 8. Numerical Example

```

Consider an edge point:

(x,y) = (10,20)

Suppose:

θ = 0°

Then:

ρ = x cos(0°) + y sin(0°)

ρ = 10(1) + 20(0)

ρ = 10

Therefore this image point votes for the parameter pair:

(ρ,θ) = (10,0°)

```

📐 9. Why Polar Form is Better

```

Representation	Problem / Advantage
y = mx + c	Vertical lines cause difficulty because slope becomes undefined.
ρ = x cosθ + y sinθ	Can represent vertical as well as non-vertical lines.

The polar representation makes the Hough Transform suitable for detecting lines with many different orientations.

```

🧠 10. Point Space vs Parameter Space

```

🖼️ Image Space

Contains pixel coordinates such as (x,y).

📊 Parameter Space

Contains line parameters such as (ρ,θ).

🗳️ Voting

Edge pixels vote for possible parameter combinations.

⛰️ Peak

A high accumulator value indicates strong geometric evidence.

```

🔗 11. Connection with Edge Detection

```

In many practical systems, Hough line detection is performed after edge detection.

Original Image → Grayscale → Edge Detection → Hough Transform → Detected Lines

A common workflow is:

Step 1

Convert image to grayscale.

Step 2

Apply Canny edge detection.

Step 3

Apply Hough Line Transform.

Step 4

Draw the detected lines.

```

🐍 12. Beginner Python — Hough Line Transform

```

The following program uses OpenCV's standard Hough Line Transform.

import cv2 ``` import numpy as np # Read the image image = cv2.imread("image.jpg") # Convert to grayscale gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY) # Detect edges edges = cv2.Canny( gray, 50, 150 ) # Apply Hough Line Transform lines = cv2.HoughLines( edges, 1, np.pi / 180, 100 ) # Draw detected lines if lines is not None: ``` for line in lines: rho, theta = line[0] a = np.cos(theta) b = np.sin(theta) x0 = a * rho y0 = b * rho x1 = int(x0 + 1000 * (-b)) y1 = int(y0 + 1000 * (a)) x2 = int(x0 - 1000 * (-b)) y2 = int(y0 - 1000 * (a)) cv2.line( image, (x1, y1), (x2, y2), (0, 0, 255), 2 ) ``` # Display results cv2.imshow("Edges", edges) cv2.imshow("Detected Lines", image) cv2.waitKey(0) cv2.destroyAllWindows()

```

Beginner explanation:

cv2.Canny() detects image edges.
cv2.HoughLines() searches for lines in the edge image.
rho stores the distance parameter.
theta stores the angular parameter.
cv2.line() draws the detected line.

```

📦 13. OpenCV Installation

```

pip install opencv-python ``` pip install numpy

```

Import the libraries:

import cv2 ``` import numpy as np

🐍 14. Beginner Python — Probabilistic Hough Transform

```

OpenCV also provides HoughLinesP(), which returns line segments instead of the infinite-line representation used by the standard Hough Transform.

import cv2 ``` # Read image image = cv2.imread("image.jpg") # Convert to grayscale gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY) # Detect edges edges = cv2.Canny( gray, 50, 150 ) # Probabilistic Hough Transform lines = cv2.HoughLinesP( edges, 1, 3.14159 / 180, 50, minLineLength=50, maxLineGap=10 ) # Draw line segments if lines is not None: ``` for line in lines: x1, y1, x2, y2 = line[0] cv2.line( image, (x1, y1), (x2, y2), (0, 0, 255), 2 ) ``` cv2.imshow("Detected Line Segments", image) cv2.waitKey(0) cv2.destroyAllWindows()

⚖️ 15. Standard Hough vs Probabilistic Hough

```

Feature	HoughLines()	HoughLinesP()
Output	ρ and θ	Line segment endpoints
Representation	Infinite line	Finite segment
Typical use	Geometric line parameters	Actual visible line segments
Parameters	Distance and angle resolution, threshold	Threshold, minimum line length, maximum gap

```

🎛️ 16. Interactive Hough Transform Demonstration

```

📍 Enter an Image Point

Enter an image coordinate and an angle. The demonstration calculates the corresponding ρ value.

X coordinate: Y coordinate: Theta (degrees):

Enter values and click Calculate ρ.

Parameter Calculation

ρ = x cosθ + y sinθ

```

📊 17. Interactive Voting Demonstration

```

For a single image point, changing θ produces different values of ρ. Each pair represents a possible line passing through that image point.

θ	cos θ	sin θ	ρ

When multiple edge points generate the same or nearby (ρ,θ) combinations, the corresponding accumulator cells receive multiple votes. These peaks are used to identify candidate lines.

```

🔍 18. Hough Transform Algorithm

```

Input Image ↓ ``` Convert to Grayscale ↓ Edge Detection ↓ Find Edge Pixels ↓ Create Accumulator ↓ For each Edge Pixel ↓ For each θ ↓ Calculate ρ ↓ Increment Accumulator ↓ Find Accumulator Peaks ↓ Convert (ρ, θ) to Lines ↓ Output Detected Lines

📚 19. Applications of Hough Transform

```

🛣️ Lane Detection

Straight lane markings can be detected from road images.

📄 Document Analysis

Straight borders and table structures can be identified.

🏭 Industrial Vision

Straight structural components and linear defects can be analyzed.

🤖 Robotics

Geometric structures can provide information for navigation and scene understanding.

🏗️ Structural Analysis

Straight edges and geometric components can be extracted from images.

🖼️ Computer Vision

Provides geometric features for subsequent processing.

```

⚠️ 20. Limitations

```

• Large parameter spaces can require substantial memory.
• Computation increases with image size and parameter resolution.
• Noise can generate unwanted votes.
• Threshold selection affects the number of detected lines.
• Very close lines may produce multiple accumulator peaks.
• Curved objects require different representations or extensions.

```

🎓 21. B.Sc. Computer Science Honours — Important Exam Points

```

• Define the Hough Transform.
• Explain why Hough Transform is used for line detection.
• Write the polar equation of a straight line.
• Explain ρ and θ.
• Explain image space and parameter space.
• Explain the accumulator array.
• Explain the voting mechanism.
• Solve a numerical problem using ρ = x cosθ + y sinθ.
• Explain the complete Hough line detection algorithm.
• Explain the relationship between Canny and Hough Transform.
• Differentiate HoughLines() and HoughLinesP().
• Write Python code for Hough line detection.
• Discuss applications and limitations.

```

💡 22. Quick Revision

```

Term	Meaning
Hough Transform	Technique for detecting geometric shapes using parameter space
ρ	Perpendicular distance from origin
θ	Angle of the perpendicular
Accumulator	Array that stores votes for parameter combinations
Peak	High vote count indicating a strong candidate
HoughLines()	Standard Hough line transform in OpenCV
HoughLinesP()	Probabilistic Hough transform returning line segments

```

CREATED BY BIJAN KRISHNA PAUL