Non-paramtetric Shapes Detection using Generalized Hough Transform

Non-parametric shapes detection using a generalized Hough transform

Hough transform was originally proposed to detect circles in an image. It was later improvised to detect all parameteric shapes. The procedure is to find imperfect instances of objects within a certain class of shapes by a voting procedure. The voting is carried out in parameter space from which the object candidates are obtained as local maxima in accumulator space. This project further extends the algorithm to detect any arbitrary, non-parameteric shapes with different scaling. It uses gradient information around the centroid of the non-parameteric shape to accumulate bin array. Thresholding the bin array gives the centroid of detected shape.

Block diagram

Algorithm for generalized Hough transform to detect any non-parametric shape with scaling

Input:

\( P \): Grayscale pattern image of size \( N \times N \)
\( I \): Grayscale target image of size \( N \times N \)
\( R \): Angular resolution (e.g., 360 bins)
\( S \): Number of scales to evaluate
\( \{s_1, s_2, \ldots, s_S\} \): Array of scale factors

Output:

\( D \): Output image of size \( N \times N \) with detected centers marked

Procedure:

Initialize Reference Table:
Create a lookup table \( G[\theta][k] = (dx, dy) \), where:
- \( \theta \in \{0, 1, \ldots, R - 1\} \)
- \( k \) indexes coordinates per angle
For each edge pixel \( (x, y) \) in \( P \), compute gradients:
\[ G_x = \sum_{i,j} K_x[i,j] \cdot P(x+i, y+j), \quad G_y = \sum_{i,j} K_y[i,j] \cdot P(x+i, y+j) \] \[ \theta = \left\lfloor \frac{\text{atan2}(G_y, G_x) \cdot 180}{\pi} \right\rfloor + 179 \]
Store displacement vector \( (x - x_0, y - y_0) \) in \( G[\theta] \), where \( (x_0, y_0) \) is the center of \( P \).
Initialize Voting Accumulator:
Create a 3D accumulator array:
\[ C[x][y][s] = 0 \quad \forall x,y \in [0,N), \quad s \in [1, S] \]
Vote for Potential Centers in Image:
For each edge pixel \( (x, y) \) in \( I \):
- Compute gradients \( G_x, G_y \) as in Step 1
- Calculate orientation \( \theta \) and retrieve displacements from \( G[\theta] \)
- For each displacement \( (dx, dy) \in G[\theta] \), and each scale \( s_i \):
\[ x_c = x - s_i \cdot dx,\quad y_c = y - s_i \cdot dy \]
If \( (x_c, y_c) \) within bounds, increment:
\[ C[x_c][y_c][i] = C[x_c][y_c][i] + 1 \]
Thresholding and Peak Detection:
For each scale index \( i \in [1, S] \):
- Compute maximum vote: \( V_{\max} = \max_{x,y} C[x][y][i] \)
- Set threshold \( T = V_{\max} - \delta \) (e.g., \( \delta = 50 \))
- For each location \( (x, y) \), if:
  \[ C[x][y][i] \geq T \text{ and } C[x][y][i] \text{ is local maximum} \]
  then mark \( (x, y) \) as detected center on \( D \)
Output:
Return image \( D \) with centers marked.

Demonstration of generalized Hough transform for detecting non-arametric shape with scaling

Non-parameteric shape to be detected

Input image with salt and pepper noise

Output image with centroid of detected non-parametric shapes

Detected image — Output image with detected centroid of non-parametric shapes

C++ source code for generalized Hough transform

main.cpp and functions.h.

Reference

Generalizing the Hough transform to detect arbitrary shape, DH Ballard (1981)

Author

Anurag Gupta is an M.S. graduate in Electrical and Computer Engineering from Cornell University. He also holds an M.Tech degree in Systems and Control Engineering and a B.Tech degree in Electrical Engineering from the Indian Institute of Technology, Bombay.

Comment

Past Comments

No comments yet. Be the first!