时间戳

首页 > 解决方案 > 填补分类数据漏洞的有效方法？

python - 填补分类数据漏洞的有效方法？

问题描述

我们有 3D 分割掩码，其中每个类都有自己的标签/ID。对于每个类，我们都想填补分割中的漏洞。

例如，以下矩阵：

[
  [
    [ 1, 1, 1, 2, 2, 2 ],
    [ 1, 1, 1, 2, 2, 2 ],
    [ 1, 1, 1, 2, 2, 2 ],
    [ 0, 3, 0, 0, 4, 0 ],
    [ 3, 3, 3, 4, 0, 4 ],
    [ 0, 3, 0, 0, 4, 0 ],
  ],
  [
    [ 1, 1, 1, 2, 2, 2 ],
    [ 1, 0, 1, 2, 0, 0 ],
    [ 1, 1, 1, 2, 2, 2 ],
    [ 0, 3, 0, 0, 4, 0 ],
    [ 3, 0, 3, 4, 0, 4 ],
    [ 0, 3, 0, 0, 4, 0 ],
  ],
  [
    [ 1, 1, 1, 2, 2, 2 ],
    [ 1, 1, 1, 2, 2, 2 ],
    [ 1, 1, 1, 2, 2, 2 ],
    [ 0, 3, 0, 0, 4, 0 ],
    [ 3, 3, 3, 4, 4, 4 ],
    [ 0, 3, 0, 0, 4, 0 ],
  ],
]

应该导致

[
  [
    [ 1, 1, 1, 2, 2, 2 ],
    [ 1, 1, 1, 2, 2, 2 ],
    [ 1, 1, 1, 2, 2, 2 ],
    [ 0, 3, 0, 0, 4, 0 ],
    [ 3, 3, 3, 4, 0, 4 ],
    [ 0, 3, 0, 0, 4, 0 ],
  ],
  [
    [ 1, 1, 1, 2, 2, 2 ],
    [ 1, 1, 1, 2, 0, 0 ],
    [ 1, 1, 1, 2, 2, 2 ],
    [ 0, 3, 0, 0, 4, 0 ],
    [ 3, 3, 3, 4, 0, 4 ],
    [ 0, 3, 0, 0, 4, 0 ],
  ],
  [
    [ 1, 1, 1, 2, 2, 2 ],
    [ 1, 1, 1, 2, 2, 2 ],
    [ 1, 1, 1, 2, 2, 2 ],
    [ 0, 3, 0, 0, 4, 0 ],
    [ 3, 3, 3, 4, 4, 4 ],
    [ 0, 3, 0, 0, 4, 0 ],
  ],
]

唯一填充的孔是中间切片中的 1 和 3。2 形状向侧面敞开，4 向背面敞开。类之间的 0 应该保持不变。

我使用现有的scipy.ndimage.morphology.binary_fill_holes函数（或其实现）和numpy. 这是迄今为止最好的两个版本：

import numpy as np
from scipy.ndimage.morphology import binary_fill_holes, label, generate_binary_structure, binary_dilation

def fill_holes6(img: np.ndarray, applied_labels: np.ndarray) -> np.ndarray:
    output = np.zeros_like(img)
    for i in applied_labels:
        output[binary_fill_holes(img == i)] = i

    return output

def fill_holes7(img: np.ndarray, applied_labels: np.ndarray) -> np.ndarray:
    output = np.zeros(img.shape, dtype=int)
    for i in applied_labels:
        tmp = np.zeros(img.shape, dtype=bool)
        binary_dilation(tmp, structure=None, iterations=-1, mask=img != i, origin=0, border_value=1, output=tmp)
        output[np.logical_not(tmp)] = i
        
    return output

# EDIT: Added the following method:
def fill_holes8(img: np.ndarray, applied_labels: np.ndarray) -> np.ndarray:
    connectivity = 1
    footprint = generate_binary_structure(img.ndim, connectivity)
    background_mask = img == 0
    components, num_components = label(background_mask, structure=footprint)
    filled_holes = np.zeros_like(img)
    for component_label in range(1, num_components + 1):
        component_mask = components == component_label
        component_neighborhood = np.pad(img, 1, constant_values=-1)[binary_dilation(np.pad(component_mask, 1), structure=footprint)]

        neighbor_labels = np.unique(component_neighborhood)
        if len(neighbor_labels) == 2 and -1 not in neighbor_labels:
            neighbor_label = neighbor_labels[1]
            filled_holes[component_mask] = neighbor_label

    return img + filled_holes

我通过以下方式测量了性能（与我的真实数据分布相匹配）：

import time
import pandas as pd

def measure(funs, t):
    res = []
    for _ in range(t):
        ra = np.random.randint(10, 40)
        sh = np.random.randint(200, 400, 3)
        img = np.random.randint(0, ra, sh)

        applied_labels = np.unique(img)[1:]

        fun_res = []
        for fun in funs:
            start = time.time()
            fun(img, applied_labels)
            end = time.time()
            fun_res.append(end - start)
        res.append(fun_res)
    return np.min(res, axis=0), np.max(res, axis=0), np.mean(res, axis=0), np.std(res, axis=0)

print(measure([fill_holes6, fill_holes7], t=10))

对于我的第一个实现，我得到了以下执行时间（t=100）：

填充孔1 填充孔2 填充孔3
分钟 6.4s 6.9s 6.2s
最大限度 83.7s 96.0s 80.4s
意思是 32.9s 37.3s 31.6s
性病 17.3s 20.1s 16.5

这是非常缓慢的。最后一个实现 fill_holes7 仅比 fill_holes3 快 1.27 倍。

有没有更高效的方法来做到这一点？

先在 scipy 项目上打开了一个功能请求，但被要求先去 stackoverflow：https ://github.com/scipy/scipy/issues/14504

编辑：

我还在 MONAI 项目上打开了一个功能请求。请参阅#2678 为此，我使用迭代侵蚀解决方案 ( fill_holes7) 打开了一个拉取请求。您可以在此处找到文档：monai.transforms.FillHoles

在此期间，我还实现了一个基于连接组件标签 (CCL) 的版本。在此处查看 MONAI 中的实现。我在fill_holes8上面添加，基本上就是那个实现。

MONAI 包对任何提高此方法性能的拉取请求都很满意。随意去那里，打开一个问题和一个拉取请求。

标签： pythonnumpyscipy

解决方案

binary_fill_holes实现效率不高：它似乎没有使用 SIMD 指令并且没有并行化。它还基于一个非常密集的算法（迭代侵蚀）。由于此函数针对每个标签运行，因此您的最终实现计算量非常大。解决性能问题的一种解决方案是重新设计您的算法。

第一步是保持对标签的迭代，并找到一种更有效的方法来填补空洞。一种有效的解决方案是对边界的每个尚未填充的单元格使用填充算法，然后查找未填充的单元格。这些剩余的单元格应该是已经设置了当前标签的孔或单元格。这样的算法应该很快。但是，要在 Python 中有效地实现它并不容易。在 Python 中有一些 Flood-fill 的实现（例如 in skimage.morphology），但是对于大多数边界单元格从 Python 调用函数的成本会太高。

另一种解决方案是使用标签算法来查找数组中相互连接的所有区域。这可以很容易地使用labelof来完成skimage.measure。一旦标记，标记的边界区域可以设置为不是孔。剩下的一个作为洞或区域已经设置了正确的标签。此解决方案更加密集，特别是当标签数量很大时（根据您的示例，这似乎非常罕见，只要每个标签都是单独计算的）。这是一个实现：

from skimage.measure import label

def getBorderLabels(img):
    # Detection
    lab0 = np.unique(img[:,:,0])
    lab1 = np.unique(img[:,:,-1])
    lab2 = np.unique(img[:,0,:])
    lab3 = np.unique(img[:,-1,:])
    lab4 = np.unique(img[0,:,:])
    lab5 = np.unique(img[-1,:,:])

    # Reduction
    lab0 = np.union1d(lab0, lab1)
    lab2 = np.union1d(lab2, lab3)
    lab4 = np.union1d(lab4, lab5)
    return np.union1d(np.union1d(lab0, lab2), lab4)

def getHoleLabels(borderLabels, labelCount):
    return np.setdiff1d(np.arange(1, labelCount+1, dtype=int), borderLabels, assume_unique=True)

def fill_holes8(img: np.ndarray, applied_labels: np.ndarray) -> np.ndarray:
    output = img.copy()
    for i in applied_labels:
        labelized, labelCount = label(img==i, background=True, return_num=True, connectivity=1)
        holeLabels = getHoleLabels(getBorderLabels(labelized), labelCount)
        if len(holeLabels) > 0:
            output[np.isin(labelized, holeLabels)] = i
    return output

这个实现在我的机器上快了大约3 倍。

请注意，可以通过同时处理多个标签来并行化算法（例如，使用多个进程）。但是，应该注意不要使用太多内存并且不要output以正确的顺序写入（类似于顺序算法）。

减速的最大来源来自每个标签的单独计算。一旦可以调整洪水填充算法以编写适合您需要的自定义优化实现，尽管这似乎很难做到。或者，可以调整基于标签的实现来做同样的事情。第二种方法更简单，但也不容易。在复杂情况下会出现许多问题：当具有给定标签 L1 的单元格形成包含孔的边界时，会发生什么情况？如果边界彼此部分重叠怎么办？这种情况可能吗？是否应该对它们进行调查，如果是，接受的输出集是什么？

只要标记的边界没有形成棘手的情况，就有一种非常有效的算法可以用正确的标签来跟踪和填充漏洞。我不确定它是否总是有效，但这是一个想法：

  • 使用标签算法查找所有连接区域
  • 构建一组包含所有标签的标签
  • 从集合中移除与边界区域相关的标签
  • 删除与已标记的单元格相关的标签（即非零单元格）
  • 到目前为止，剩下的标签要么是漏洞，要么是假漏洞（或者假设不存在的棘手情况）。假孔是未标记的单元格，周围是带有多个不同标签的标记单元格（例如示例中间的 0 单元格）。
  • 检查每个标记区域边界上的单元格标签。如果一个标记区域只被具有相同标签 L3 的细胞包围，那么它就是一个必须用 L3 标记细胞填充的洞。否则，这要么是一个假漏洞（或一个棘手的案例）。

生成的算法应该比参考实现和前一个算法快得多。

推荐阅读