scikit-image

1
#cython: cdivision=True
2
#cython: boundscheck=False
3
#cython: nonecheck=False
4
#cython: wraparound=False
5

6
"""Cython code used in `remove_objects_by_distance` function."""
7

8
cimport numpy as cnp
9

10
from .._shared.fused_numerics cimport np_anyint
11

12

13
def _remove_objects_by_distance(
14
    np_anyint[::1] out not None,
15
    Py_ssize_t[::1] border_indices not None,
16
    Py_ssize_t[::1] inner_indices not None,
17
    kdtree,
18
    cnp.float64_t p_norm,
19
    cnp.float64_t min_distance,
20
    tuple shape,
21
):
22
    """Remove objects, in specified order, until remaining are a minimum distance apart.
23

24
    Remove labeled objects from an image until the remaining ones are spaced
25
    more than a given distance from one another. By default, smaller objects
26
    are removed first.
27

28
    Parameters
29
    ----------
30
    out :
31
        An array with labels for each object in `image` matching it in shape.
32
    border_indices, inner_indices :
33
        Indices into `out` for the border of objects (`border_indices`) and
34
        the inner part of objects (`inner_indices`). `border_indices`
35
        determines the iteration order; objects that are indexed first are
36
        preserved. Indices must be sorted such, that indices pointing to the
37
        same object are next to each other.
38
    kdtree : scipy.spatial.cKDTree
39
        A KDTree containing the coordinates of all objects in `image`.
40
    min_distance :
41
        The minimal allowed distance between objects.
42
    p_norm :
43
        The Minkowski p-norm used to calculate the distance between objects.
44
        Defaults to 2 which corresponds to the Euclidean distance.
45
    shape :
46
        The shape of the unraveled `image`.
47
    """
48
    cdef:
49
        Py_ssize_t i_indices, j_indices  # Loop variables to index `indices`
50
        Py_ssize_t i_out  # Loop variable to index `out`
51
        np_anyint object_id, other_id
52
        list neighborhood
53
        set remembered_ids
54

55
    remembered_ids = set()
56
    for i_indices in range(border_indices.shape[0]):
57
        i_out = border_indices[i_indices]
58
        object_id = out[i_out]
59
        # Skip if sample is part of a removed object
60
        if object_id == 0:
61
            continue
62

63
        neighborhood = kdtree.query_ball_point(
64
            kdtree.data[i_indices, ...],
65
            r=min_distance,
66
            p=p_norm,
67
        )
68
        for j_indices in neighborhood:
69
            # Check object IDs in neighborhood
70
            other_id = out[border_indices[j_indices]]
71
            if other_id != 0 and other_id != object_id:
72
                # If neighbor ID wasn't already removed or is the current one
73
                # remove the boundary and remember the ID
74
                _remove_object(out, border_indices, j_indices)
75
                remembered_ids.add(other_id)
76

77
    # Delete inner parts of remembered objects
78
    for j_indices in range(inner_indices.shape[0]):
79
        object_id = out[inner_indices[j_indices]]
80
        if object_id != 0 and object_id in remembered_ids:
81
            _remove_object(out, inner_indices, j_indices)
82

83

84
cdef inline _remove_object(
85
    np_anyint[::1] out,
86
    Py_ssize_t[::1] indices,
87
    Py_ssize_t start
88
):
89
    """Delete an object.
90

91
    Starting from `start`, iterate the `indices` in both directions and assign
92
    0 until the object ID changes
93

94
    Parameters
95
    ----------
96
    out :
97
        An array with labels for each object in `image` matching it in shape.
98
    indices :
99
        Indices into `out` for objects. Indices must be sorted such, that
100
        indices pointing to the same object are next to each other.
101
    start :
102
        Index into `indices` for the object.
103
    """
104
    cdef:
105
        Py_ssize_t k_indices, k_labels
106
        np_anyint remove_id
107

108
    with nogil:
109
        remove_id = out[indices[start]]
110

111
        for k_indices in range(start, -1, -1):
112
            k_labels = indices[k_indices]
113
            if remove_id == out[k_labels]:
114
                out[k_labels] = 0
115
            else:
116
                break
117
        for k_indices in range(start + 1, indices.shape[0]):
118
            k_labels = indices[k_indices]
119
            if remove_id == out[k_labels]:
120
                out[k_labels] = 0
121
            else:
122
                break
123