Segmentation for open-contour line drawings

Question

Here is an example of the type of drawing I'm talking about:

it has clearly distinct areas, but they are not fully enclosed.

I'm trying to segment the image, but since it's in 1-bit color I don't have any useful information like hue or value gradients to make a more educated guess. It would seem at first glance that the only information a segmentation algorithm could use to make a decision is the width of the gaps falling below or above a certain threshold.

My question here is if there is a particular method or algorithm, either in scikit-image or opencv say, that works with this kind of input or at least something similar.

Answer 1

You can use negative affinities and correlation clustering to segment your image into something like this:

You can define "affinity" for pairs of nearby pixels: if there is an "edge" pixel between them - then they should have negative affinity (they should not be clustered together).
If there isn't any edge pixel between them - then they should have positive affinity (they should be clustered together).

Once you have the affinity matrix, you can apply correlation clustering to it.

Here's a sketch of the solution in Matlab:

img = imread('PaG3p.png');
bw = img(:,:,1) > 128;
n = numel(bw);

% construct the affinity matrix using improfile
[x, y] = meshgrid(1:size(bw,2), 1:size(bw,1));
x = x(:);
y = y(:);

r = 5;
[dx, dy] = meshgrid(-r:r, -r:r);
dx = dx(:);
dy = dy(:);
sel = max(abs(dx),abs(dy)) == r & dx >= dy;
dx = dx(sel);
dy = dy(sel);
m = numel(dx);

ii = nan(n*m, 1);
jj = nan(n*m, 1);
wij = zeros(n*m, 1);
counter = 1;
for k=1:n    
    % from
    fi = y(k);
    fj = x(k);
    if bw(fi, fj)
        % to
        for l=1:m
            ti = fi + dy(l);
            tj = fj + dx(l);
            if ti > 1 && tj > 1 && ti <= size(bw,1) && tj <= size(bw,2) && bw(ti, tj)
                p = improfile(bw, [fj, tj], [fi, ti]);
                num_cross = sum((p(2:end)-p(1:end-1)) == -1);
                
                ii(counter) = k;
                jj(counter) = sub2ind(size(bw), ti, tj);

                if  num_cross == 1
                    % only one cross of edge
                    wij(counter) = -1;
                elseif num_cross == 0
                    % no crosses
                    wij(counter) = 1;
                end
                counter = counter + 1;
            end
        end
    end
    % add 4 connect
    if fi < size(bw,1) && bw(fi+1, fj)
        ii(counter) = k;
        jj(counter) = sub2ind(size(bw), fi + 1, fj);
        wij(counter) = (bw(fi, fj) == bw(fi+1, fj))*2 - 1;
        counter = counter + 1;
    end
    if fj < size(bw,2) && bw(fi, fj+1)
        ii(counter) = k;
        jj(counter) = sub2ind(size(bw), fi, fj + 1);
        wij(counter) = (bw(fi, fj) == bw(fi, fj+1))*2 - 1;
        counter = counter + 1;
    end    
end

sel = ~isnan(ii);
ii=ii(sel);
jj=jj(sel);
wij=wij(sel);
W = sparse(ii, jj, wij, n, n);
W = W + W.';  % make symetric

% apply correlation clustering
l = a_expand(W, bw(:));
out = reshape(l, size(bw));