Find Hough Peaks

mediumPROHough TransformsHoughCV: Feature Detection and Matching

Implement a function to find the top-k peaks in a Hough accumulator, which represents the parameter space of lines in an image. The goal is to identify the most prominent lines, characterized by their Hough transform parameters $θ$ and $ρ$ , where $θ$ is the angle and $ρ$ is the distance from the origin.

The Hough transform is a feature extraction technique used to detect lines in images by transforming the image into a parameter space, where each cell represents a line in the original image. Peaks in the accumulator correspond to lines that received the most votes from edge points, indicating their presence in the image.

To find these peaks, follow these steps:

Collect all cells with their values and coordinates
Sort by vote count (descending)
Return the top k $(θ, ρ)$ pairs

P(θ, ρ) = \sum_{(x, y)} H(x, y) \cdot δ(ρ - x \cos(θ) - y \sin(θ))

This technique is widely used in computer vision applications for line detection and image analysis.

Example

Input

accumulator = [[1, 2, 1],
               [3, 1, 3],
               [1, 5, 1]]
k = 2

Output

[(2, 1), (1, 0)]

Reasoning

Flattening with coordinates: (0,0)=1, (0,1)=2, (0,2)=1 (1,0)=3, (1,1)=1, (1,2)=3 (2,0)=1, (2,1)=5, (2,2)=1

Sorting by value (descending):

(2,1)=5
(1,0)=3
(1,2)=3
(0,1)=2 ...

Top 2: [(2, 1), (1, 0)] Note: (1,0) and (1,2) tie at 3, but (1,0) comes first due to smaller rho_idx.

Constraints

accumulator is a 2D array (theta_bins × rho_bins)
k is the number of peaks to find
Return list of (theta_idx, rho_idx) tuples
Sorted by votes (highest first)
If tied, prefer smaller theta_idx, then smaller rho_idx

Learn this in

Feature Detection and MatchingCV Study Plan

More from CV: Feature Detection and Matching

Circle Hough Transformhard Canny Edge Detection Pipelinehard Hamming Distance Matcherhard Simple BRIEF Descriptormedium Point to Hough Spaceeasy

Concept primerPREVIEW

Background Knowledge

The Hough Transform is a feature extraction technique in computer vision that detects parametric shapes (like lines, circles) by transforming edge points from image space to a parameter space called the accumulator array. For line detection, each edge point votes for all possible lines passing through it, parameterized typically as $(\rho,$ \theta $)$ where $\rho = x\cos$ \theta $+ y\sin\theta$ ; collinear points produce a peak in the accumulator representing the most-voted line.

Peaks in the accumulator correspond to the strongest geometric features—high-vote cells indicate lines supported by many edge points, robust to noise and partial occlusions. In the "Find Hough Peaks" problem, the accumulator is a 2D array (rows for $\rho$ , columns for $\theta$ ), and identifying top-k peaks reveals dominant lines for applications like edge grouping or object recognition in feature detection pipelines.

This fits into CV: Feature Detection and Matching as a post-processing step after edge detection (e.g., Canny) and Hough voting, enabling robust line extraction amid clutter.

Algorithm/Approach

The standard pattern for peak detection in Hough accumulators involves non-maximum suppression (local maxima finding) followed by sorting or thresholding to select top-k peaks by vote count.

Key idea: Scan the 2D accumulator for local maxima (cells higher than 8-connected neighbors), apply a minimum vote threshold to filter noise, then rank by accumulator value to extract top-k positions with their $(\rho,$ \theta $)$ parameters and strengths. Efficient variants use connected component labeling on high-value regions or sliding windows for peak localization, avoiding exhaustive searches.

This scales to larger accumulators via hierarchical or multi-scale analysis, common in probabilistic Hough variants.

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results