Coffee beans separation algorithm

Question

What is proper algorithm for separating (counting) coffee beans on binary image? Beans can touch and partially overlap.

_{(source: beucher at cmm.ensmp.fr)}

I am working actually not with coffee beans, but with coffee beans it is easier to describe. This is sub-problem in my task of counting all present people and counting people crossing some imaginary line from supermarket surveillance video. I've extracted moving objects into binary mask, and now I need to separate these somehow.

Two promising algo that someone mentioned in comments:

• Wathershed+distancetransofrm+labeling. This probably an answer for this question as I put it (beans separation).
• Tracking of moving objects from video sequence (what is the name of this algorithm?). It can track overlapping objects. This is more promising algo and probably exactly what I need to solve the task that I have (moving people separation).

Answer 1

This approach is a spin-off from mmgp's answer that explains in detail how the watershed algorithm works. Therefore, if you need some explanation on what the code does, please check his answer.

The code can be played with in order to improve the rate of detection. Here it is:

import sys
import cv2
import numpy
from scipy.ndimage import label

def segment_on_dt(a, img):
    border = cv2.dilate(img, None, iterations=3)
    border = border - cv2.erode(border, None)
    cv2.imwrite("border.png", border)

    dt = cv2.distanceTransform(img, 2, 5)    
    dt = ((dt - dt.min()) / (dt.max() - dt.min()) * 255).astype(numpy.uint8)
    _, dt = cv2.threshold(dt, 135, 255, cv2.THRESH_BINARY)
    cv2.imwrite("dt_thres.png", dt)    

border (left), dt (right):

    lbl, ncc = label(dt)
    lbl = lbl * (255/ncc)      
    # Completing the markers now. 
    lbl[border == 255] = 255

    lbl = lbl.astype(numpy.int32)
    cv2.imwrite("label.png", lbl)

lbl:

    cv2.watershed(a, lbl)

    lbl[lbl == -1] = 0
    lbl = lbl.astype(numpy.uint8)
    return 255 - lbl

# Application entry point
img = cv2.imread("beans.png")
if img == None:
    print("!!! Failed to open input image")
    sys.exit(0)

# Pre-processing.
img_gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)    
_, img_bin = cv2.threshold(img_gray, 128, 255, cv2.THRESH_OTSU | cv2.THRESH_BINARY_INV)
cv2.imwrite("img_bin.png", img_bin)

img_bin = cv2.morphologyEx(img_bin, cv2.MORPH_OPEN, numpy.ones((3, 3), dtype=int))
cv2.imwrite("img_bin_morphoEx.png", img_bin)

img_bin (left) before and after (right) a morphology operation:

result = segment_on_dt(img, img_bin)
cv2.imwrite("result.png", result)

result[result != 255] = 0
result = cv2.dilate(result, None)
img[result == 255] = (0, 0, 255)
cv2.imwrite("output.png", img)

result (left) of watershed segmentation, followed by output (right):