Sort contours resembling physical order with opencv

Question

I want to sort a collection of contours in an image. The order should be like we are stacking physically those contours. Imaging we are stacking paper sheets, and then retrieving one by one starting from the top or bottom one.

In the following image I describe the desired order (if order is bottom-up or up-bottom is not important):

I have retrieved this contours using cv2.findCountours functions with different modes but non of them achieve this order. This is the code I'm using to label the contours:

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)

How could I get this specific order? Simpler sorting methods proposed in other questions for ordering top-bottom + left-right are not enough in this case as it can be inferred from the image.

Answer 1

The following algorithm comes to mind:

Build a dependency tree (or rather "is directly obstructed by" tree) and then remove the leaves until you get to the root. Contour B directly obstructs contour A if in some column occupied by both B is above A and there is no other contour in between them. We will also need to add some heuristic to chose which leaf to pick first when there's more then one candidate.

---

In more detail:

1. Find the contours, enumerate them, and populate a dependency tree.

2. Create a label image. Areas with no contour contain -1, areas with contour contain a value equal to contour index.

3. Find dependencies, processing one column of the label image at a time:

   a. If there is a contour B positioned directly above contour A (i.e. there is no contour in between them), then A depends on B.

4. Sort by removing leaves from the dependency tree and appending them to a result list. Repeat until the dependency tree is empty:

   a. Find all current leaves. These are the candidates.

   b. Sort candidates by depth (the minimum column index occupied by the contour).

   c. Remove the first candidate (the one with minimum depth) from the tree, and append it to the result list.

5. The result list is now sorted.

---

The following picture illustrates the stacking order.

---

Sample script:

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)

---

For convenience, a clean unlabeled input image.