## "Fossies" - the Fresh Open Source Software Archive

### Member "scikit-image-0.19.3/skimage/transform/hough_transform.py" (12 Jun 2022, 15240 Bytes) of package /linux/misc/scikit-image-0.19.3.tar.gz:

As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) Python source code syntax highlighting (style: standard) with prefixed line numbers. Alternatively you can here view or download the uninterpreted source code file. For more information about "hough_transform.py" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 0.19.2_vs_0.19.3.

```    1 import numpy as np
2 from scipy.spatial import cKDTree
3
4 from ._hough_transform import _hough_circle, _hough_ellipse, _hough_line
5 from ._hough_transform import _probabilistic_hough_line as _prob_hough_line
6
7
8 def hough_line_peaks(hspace, angles, dists, min_distance=9, min_angle=10,
9                      threshold=None, num_peaks=np.inf):
10     """Return peaks in a straight line Hough transform.
11
12     Identifies most prominent lines separated by a certain angle and distance
13     in a Hough transform. Non-maximum suppression with different sizes is
14     applied separately in the first (distances) and second (angles) dimension
15     of the Hough space to identify peaks.
16
17     Parameters
18     ----------
19     hspace : (N, M) array
20         Hough space returned by the `hough_line` function.
21     angles : (M,) array
22         Angles returned by the `hough_line` function. Assumed to be continuous.
23         (`angles[-1] - angles[0] == PI`).
24     dists : (N, ) array
25         Distances returned by the `hough_line` function.
26     min_distance : int, optional
27         Minimum distance separating lines (maximum filter size for first
28         dimension of hough space).
29     min_angle : int, optional
30         Minimum angle separating lines (maximum filter size for second
31         dimension of hough space).
32     threshold : float, optional
33         Minimum intensity of peaks. Default is `0.5 * max(hspace)`.
34     num_peaks : int, optional
35         Maximum number of peaks. When the number of peaks exceeds `num_peaks`,
36         return `num_peaks` coordinates based on peak intensity.
37
38     Returns
39     -------
40     accum, angles, dists : tuple of array
41         Peak values in Hough space, angles and distances.
42
43     Examples
44     --------
45     >>> from skimage.transform import hough_line, hough_line_peaks
46     >>> from skimage.draw import line
47     >>> img = np.zeros((15, 15), dtype=bool)
48     >>> rr, cc = line(0, 0, 14, 14)
49     >>> img[rr, cc] = 1
50     >>> rr, cc = line(0, 14, 14, 0)
51     >>> img[cc, rr] = 1
52     >>> hspace, angles, dists = hough_line(img)
53     >>> hspace, angles, dists = hough_line_peaks(hspace, angles, dists)
54     >>> len(angles)
55     2
56
57     """
58     from ..feature.peak import _prominent_peaks
59
60     min_angle = min(min_angle, hspace.shape[1])
61     h, a, d = _prominent_peaks(hspace, min_xdistance=min_angle,
62                                min_ydistance=min_distance,
63                                threshold=threshold,
64                                num_peaks=num_peaks)
65     if a.size > 0:
66         return (h, angles[a], dists[d])
67     else:
68         return (h, np.array([]), np.array([]))
69
70
71 def hough_circle(image, radius, normalize=True, full_output=False):
72     """Perform a circular Hough transform.
73
74     Parameters
75     ----------
76     image : (M, N) ndarray
77         Input image with nonzero values representing edges.
78     radius : scalar or sequence of scalars
79         Radii at which to compute the Hough transform.
80         Floats are converted to integers.
81     normalize : boolean, optional (default True)
82         Normalize the accumulator with the number
83         of pixels used to draw the radius.
84     full_output : boolean, optional (default False)
85         Extend the output size by twice the largest
86         radius in order to detect centers outside the
87         input picture.
88
89     Returns
90     -------
91     H : 3D ndarray (radius index, (M + 2R, N + 2R) ndarray)
92         Hough transform accumulator for each radius.
93         R designates the larger radius if full_output is True.
94         Otherwise, R = 0.
95
96     Examples
97     --------
98     >>> from skimage.transform import hough_circle
99     >>> from skimage.draw import circle_perimeter
100     >>> img = np.zeros((100, 100), dtype=bool)
101     >>> rr, cc = circle_perimeter(25, 35, 23)
102     >>> img[rr, cc] = 1
103     >>> try_radii = np.arange(5, 50)
104     >>> res = hough_circle(img, try_radii)
105     >>> ridx, r, c = np.unravel_index(np.argmax(res), res.shape)
107     (25, 35, 23)
108
109     """
112                          normalize=normalize, full_output=full_output)
113
114
115 def hough_ellipse(image, threshold=4, accuracy=1, min_size=4, max_size=None):
116     """Perform an elliptical Hough transform.
117
118     Parameters
119     ----------
120     image : (M, N) ndarray
121         Input image with nonzero values representing edges.
122     threshold : int, optional
123         Accumulator threshold value.
124     accuracy : double, optional
125         Bin size on the minor axis used in the accumulator.
126     min_size : int, optional
127         Minimal major axis length.
128     max_size : int, optional
129         Maximal minor axis length.
130         If None, the value is set to the half of the smaller
131         image dimension.
132
133     Returns
134     -------
135     result : ndarray with fields [(accumulator, yc, xc, a, b, orientation)].
136           Where ``(yc, xc)`` is the center, ``(a, b)`` the major and minor
137           axes, respectively. The `orientation` value follows
138           `skimage.draw.ellipse_perimeter` convention.
139
140     Examples
141     --------
142     >>> from skimage.transform import hough_ellipse
143     >>> from skimage.draw import ellipse_perimeter
144     >>> img = np.zeros((25, 25), dtype=np.uint8)
145     >>> rr, cc = ellipse_perimeter(10, 10, 6, 8)
146     >>> img[cc, rr] = 1
147     >>> result = hough_ellipse(img, threshold=8)
148     >>> result.tolist()
149     [(10, 10.0, 10.0, 8.0, 6.0, 0.0)]
150
151     Notes
152     -----
153     The accuracy must be chosen to produce a peak in the accumulator
154     distribution. In other words, a flat accumulator distribution with low
155     values may be caused by a too low bin size.
156
157     References
158     ----------
159     .. [1] Xie, Yonghong, and Qiang Ji. "A new efficient ellipse detection
160            method." Pattern Recognition, 2002. Proceedings. 16th International
161            Conference on. Vol. 2. IEEE, 2002
162     """
163     return _hough_ellipse(image, threshold=threshold, accuracy=accuracy,
164                           min_size=min_size, max_size=max_size)
165
166
167 def hough_line(image, theta=None):
168     """Perform a straight line Hough transform.
169
170     Parameters
171     ----------
172     image : (M, N) ndarray
173         Input image with nonzero values representing edges.
174     theta : 1D ndarray of double, optional
175         Angles at which to compute the transform, in radians.
176         Defaults to a vector of 180 angles evenly spaced in the
177         range [-pi/2, pi/2).
178
179     Returns
180     -------
181     hspace : 2-D ndarray of uint64
182         Hough transform accumulator.
183     angles : ndarray
184         Angles at which the transform is computed, in radians.
185     distances : ndarray
186         Distance values.
187
188     Notes
189     -----
190     The origin is the top left corner of the original image.
191     X and Y axis are horizontal and vertical edges respectively.
192     The distance is the minimal algebraic distance from the origin
193     to the detected line.
194     The angle accuracy can be improved by decreasing the step size in
195     the `theta` array.
196
197     Examples
198     --------
199     Generate a test image:
200
201     >>> img = np.zeros((100, 150), dtype=bool)
202     >>> img[30, :] = 1
203     >>> img[:, 65] = 1
204     >>> img[35:45, 35:50] = 1
205     >>> for i in range(90):
206     ...     img[i, i] = 1
207     >>> rng = np.random.default_rng()
208     >>> img += rng.random(img.shape) > 0.95
209
210     Apply the Hough transform:
211
212     >>> out, angles, d = hough_line(img)
213
214     .. plot:: hough_tf.py
215
216     """
217     if image.ndim != 2:
218         raise ValueError('The input image `image` must be 2D.')
219
220     if theta is None:
221         # These values are approximations of pi/2
222         theta = np.linspace(-np.pi / 2, np.pi / 2, 180, endpoint=False)
223
224     return _hough_line(image, theta=theta)
225
226
227 def probabilistic_hough_line(image, threshold=10, line_length=50, line_gap=10,
228                              theta=None, seed=None):
229     """Return lines from a progressive probabilistic line Hough transform.
230
231     Parameters
232     ----------
233     image : (M, N) ndarray
234         Input image with nonzero values representing edges.
235     threshold : int, optional
236         Threshold
237     line_length : int, optional
238         Minimum accepted length of detected lines.
239         Increase the parameter to extract longer lines.
240     line_gap : int, optional
241         Maximum gap between pixels to still form a line.
242         Increase the parameter to merge broken lines more aggressively.
243     theta : 1D ndarray, dtype=double, optional
244         Angles at which to compute the transform, in radians.
245         Defaults to a vector of 180 angles evenly spaced in the
246         range [-pi/2, pi/2).
247     seed : int, optional
248         Seed to initialize the random number generator.
249
250     Returns
251     -------
252     lines : list
253       List of lines identified, lines in format ((x0, y0), (x1, y1)),
254       indicating line start and end.
255
256     References
257     ----------
258     .. [1] C. Galamhos, J. Matas and J. Kittler, "Progressive probabilistic
259            Hough transform for line detection", in IEEE Computer Society
260            Conference on Computer Vision and Pattern Recognition, 1999.
261     """
262
263     if image.ndim != 2:
264         raise ValueError('The input image `image` must be 2D.')
265
266     if theta is None:
267         theta = np.linspace(-np.pi / 2, np.pi / 2, 180, endpoint=False)
268
269     return _prob_hough_line(image, threshold=threshold,
270                             line_length=line_length, line_gap=line_gap,
271                             theta=theta, seed=seed)
272
273
274 def hough_circle_peaks(hspaces, radii, min_xdistance=1, min_ydistance=1,
275                        threshold=None, num_peaks=np.inf,
276                        total_num_peaks=np.inf, normalize=False):
277     """Return peaks in a circle Hough transform.
278
279     Identifies most prominent circles separated by certain distances in given
280     Hough spaces. Non-maximum suppression with different sizes is applied
281     separately in the first and second dimension of the Hough space to
282     identify peaks. For circles with different radius but close in distance,
283     only the one with highest peak is kept.
284
285     Parameters
286     ----------
287     hspaces : (N, M) array
288         Hough spaces returned by the `hough_circle` function.
290         Radii corresponding to Hough spaces.
291     min_xdistance : int, optional
292         Minimum distance separating centers in the x dimension.
293     min_ydistance : int, optional
294         Minimum distance separating centers in the y dimension.
295     threshold : float, optional
296         Minimum intensity of peaks in each Hough space.
297         Default is `0.5 * max(hspace)`.
298     num_peaks : int, optional
299         Maximum number of peaks in each Hough space. When the
300         number of peaks exceeds `num_peaks`, only `num_peaks`
301         coordinates based on peak intensity are considered for the
303     total_num_peaks : int, optional
304         Maximum number of peaks. When the number of peaks exceeds `num_peaks`,
305         return `num_peaks` coordinates based on peak intensity.
306     normalize : bool, optional
307         If True, normalize the accumulator by the radius to sort the prominent
308         peaks.
309
310     Returns
311     -------
312     accum, cx, cy, rad : tuple of array
313         Peak values in Hough space, x and y center coordinates and radii.
314
315     Examples
316     --------
317     >>> from skimage import transform, draw
318     >>> img = np.zeros((120, 100), dtype=int)
319     >>> radius, x_0, y_0 = (20, 99, 50)
320     >>> y, x = draw.circle_perimeter(y_0, x_0, radius)
321     >>> img[x, y] = 1
322     >>> hspaces = transform.hough_circle(img, radius)
324
325     Notes
326     -----
327     Circles with bigger radius have higher peaks in Hough space. If larger
328     circles are preferred over smaller ones, `normalize` should be False.
329     Otherwise, circles will be returned in the order of decreasing voting
330     number.
331     """
332     from ..feature.peak import _prominent_peaks
333
334     r = []
335     cx = []
336     cy = []
337     accum = []
338
340         h_p, x_p, y_p = _prominent_peaks(hp,
341                                          min_xdistance=min_xdistance,
342                                          min_ydistance=min_ydistance,
343                                          threshold=threshold,
344                                          num_peaks=num_peaks)
346         cx.extend(x_p)
347         cy.extend(y_p)
348         accum.extend(h_p)
349
350     r = np.array(r)
351     cx = np.array(cx)
352     cy = np.array(cy)
353     accum = np.array(accum)
354     if normalize:
355         s = np.argsort(accum / r)
356     else:
357         s = np.argsort(accum)
358     accum_sorted, cx_sorted, cy_sorted, r_sorted = \
359         accum[s][::-1], cx[s][::-1], cy[s][::-1], r[s][::-1]
360
361     tnp = len(accum_sorted) if total_num_peaks == np.inf else total_num_peaks
362
363     # Skip searching for neighboring circles
364     # if default min_xdistance and min_ydistance are used
365     # or if no peak was detected
366     if (min_xdistance == 1 and min_ydistance == 1) or len(accum_sorted) == 0:
367         return (accum_sorted[:tnp],
368                 cx_sorted[:tnp],
369                 cy_sorted[:tnp],
370                 r_sorted[:tnp])
371
372     # For circles with centers too close, only keep the one with
373     # the highest peak
374     should_keep = label_distant_points(
375         cx_sorted, cy_sorted, min_xdistance, min_ydistance, tnp
376     )
377     return (accum_sorted[should_keep],
378             cx_sorted[should_keep],
379             cy_sorted[should_keep],
380             r_sorted[should_keep])
381
382
383 def label_distant_points(xs, ys, min_xdistance, min_ydistance, max_points):
384     """Keep points that are separated by certain distance in each dimension.
385
386     The first point is always accpeted and all subsequent points are selected
387     so that they are distant from all their preceding ones.
388
389     Parameters
390     ----------
391     xs : array
392         X coordinates of points.
393     ys : array
394         Y coordinates of points.
395     min_xdistance : int
396         Minimum distance separating points in the x dimension.
397     min_ydistance : int
398         Minimum distance separating points in the y dimension.
399     max_points : int
400         Max number of distant points to keep.
401
402     Returns
403     -------
404     should_keep : array of bool
405         A mask array for distant points to keep.
406     """
407     is_neighbor = np.zeros(len(xs), dtype=bool)
408     coordinates = np.stack([xs, ys], axis=1)
409     # Use a KDTree to search for neighboring points effectively
410     kd_tree = cKDTree(coordinates)
411     n_pts = 0
412     for i in range(len(xs)):
413         if n_pts >= max_points:
414             # Ignore the point if points to keep reaches maximum
415             is_neighbor[i] = True
416         elif not is_neighbor[i]:
417             # Find a short list of candidates to remove
418             # by searching within a circle
419             neighbors_i = kd_tree.query_ball_point(
420                 (xs[i], ys[i]),
421                 np.hypot(min_xdistance, min_ydistance)
422             )
423             # Check distance in both dimensions and mark if close
424             for ni in neighbors_i:
425                 x_close = abs(xs[ni] - xs[i]) <= min_xdistance
426                 y_close = abs(ys[ni] - ys[i]) <= min_ydistance
427                 if x_close and y_close and ni > i:
428                     is_neighbor[ni] = True
429             n_pts += 1
430     should_keep = ~is_neighbor
431     return should_keep
```