"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)
  106     >>> r, c, try_radii[ridx]
  107     (25, 35, 23)
  108 
  109     """
  110     radius = np.atleast_1d(np.asarray(radius))
  111     return _hough_circle(image, radius.astype(np.intp),
  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.
  289     radii : (M,) array
  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
  302         corresponding radius.
  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)
  323     >>> accum, cx, cy, rad = hough_circle_peaks(hspaces, [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 
  339     for rad, hp in zip(radii, hspaces):
  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)
  345         r.extend((rad,)*len(h_p))
  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