python - 使用opencv对类似于物理顺序的轮廓进行排序

Question

我想对图像中的一组轮廓进行排序。顺序应该就像我们在物理上堆叠这些轮廓一样。想象一下，我们正在堆叠纸张，然后从顶部或底部开始一张一张地检索。

在下图中，我描述了所需的顺序(如果顺序是自下而上或自上而下并不重要):

我已经使用具有不同模式的 cv2.findCountours 函数检索了这个轮廓，但没有一个达到这个顺序。这是我用来标记轮廓的代码:

img = cv2.imread(img_path, cv2.IMREAD_GRAYSCALE)
ret, contours, hierarchy = cv2.findContours(img, cv2.RETR_CCOMP, cv2.CHAIN_APPROX_SIMPLE)
dst_img =img.copy()
for idx, cnt in enumerate(contours):
    x, y = tuple(cnt[cnt[:, :, 0].argmin()][0])
    cv2.putText(dst_img, str(idx), (x + 10, y), cv2.FONT_HERSHEY_SIMPLEX, 0.6, 150, 2)

我怎样才能得到这个特定的订单？在其他问题中提出的用于排序上下 + 左右的更简单的排序方法在这种情况下是不够的，因为它可以从图像中推断出来。

Answer 1

想到以下算法:

建立一棵依赖树(或者更确切地说“被树直接阻碍”)然后移除叶子直到到达根。如果在 B 占据的某些列中 B 位于 A 之上并且它们之间没有其他轮廓，则轮廓 B 直接阻碍轮廓 A。我们还需要添加一些启发式方法，以便在候选者不止一个时选择先采摘哪片叶子。

---

更详细:

1. 找到轮廓，枚举它们，并填充依赖树。

2. 创建标签图像。没有轮廓的区域包含 -1，有轮廓的区域包含等于轮廓索引的值。

3. 查找依赖关系，一次处理一列标签图像:

   一个。如果轮廓 B 位于轮廓 A 的正上方(即它们之间没有轮廓)，则 A 依赖于 B。

4. 通过从依赖树中移除叶子并将它们附加到结果列表来进行排序。重复直到依赖树为空:

   一个。找到所有当前的叶子。这些是候选人。

   按深度(轮廓占用的最小列索引)对候选进行排序。

   从树中移除第一个候选者(深度最小的那个)，并将其附加到结果列表。

5. 结果列表现已排序。

---

下图说明了堆叠顺序。

---

示例脚本:

import cv2
import numpy as np

# ============================================================================

class ContourInfo(object):
    def __init__(self, n, points):
        self.index = n
        self.color = np.random.rand(3) * 255
        self.points = points
        self.dependencies = set()

    def add_dependency(self, n):
        self.dependencies.add(n)

    def remove_dependency(self, n):
        self.dependencies.discard(n)

    @property
    def is_leaf(self):
        return not bool(self.dependencies)

    @property
    def depth(self):
        return self.points[:,:,1].min()

    def __repr__(self):
        return "{n=%d, dependencies=%s, leaf=%s, depth=%d}" % (self.index
            , self.dependencies
            , self.is_leaf
            , self.depth)

# ============================================================================

img = cv2.imread('papers.png', cv2.IMREAD_GRAYSCALE)
_, contours, _ = cv2.findContours(img, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_NONE)

# ----------------------------------------------------------------------------
# Create a label image and populate dependency tree

NO_CONTOUR = -1

labels = np.full_like(img, NO_CONTOUR, dtype=np.int32)
dependency_tree = {}

for n,contour in enumerate(contours):
    cv2.drawContours(labels, [contour], -1, n, -1)
    dependency_tree[n] = ContourInfo(n, contour)

# ----------------------------------------------------------------------------
# Find dependencies, processing each column from the bottom up

rows, cols = img.shape[:2]
for c in range(cols):
    last_contour = NO_CONTOUR
    for r in range(rows - 1, -1, -1):
        current_contour = labels[r,c]
        if current_contour != NO_CONTOUR:
            if (last_contour != current_contour) and (last_contour != NO_CONTOUR):
                dependency_tree[last_contour].add_dependency(current_contour)
            last_contour = current_contour

# ----------------------------------------------------------------------------
# Sort by removing one leaf at a time

sorted_contours = []

while bool(dependency_tree):
    candidates = []
    for node in dependency_tree.values():
        if node.is_leaf:
            candidates.append(node.index)

    if not bool(candidates):
        raise RuntimeError("Cycle found, cannot sort.")

    candidates = sorted(candidates, key=lambda n: dependency_tree[n].depth)

    sorted_contours.append(dependency_tree.pop(candidates[0]))
    for node in dependency_tree.values():
        node.remove_dependency(candidates[0])

# ============================================================================
# Done, create an output to illustrate the sort order

result_images = []
for n in range(len(sorted_contours)):
    tmp = np.zeros((rows, cols, 3), dtype=np.uint8)
    for c in sorted_contours[:n+1]:
        cv2.drawContours(tmp, [c.points], -1, c.color, -1)
    result_images.append(tmp)

combined_result = np.hstack(result_images)
cv2.imwrite("papers_out.png", combined_result)

---

为方便起见，clean unlabeled input image .