Segmentation of overlapping noisy parallelograms in a binary image

Question

Edited.

Previously this question was named "Segmentation of overlapping pulses in a binary spectrogram" and it was stated in slightly different way. I'm apologise to those users, who were affected by reformulation of the question.

Problem.

There are a set of binary images, that contain arbitrary set of noisy parallelograms. The height and width of objects can vary in a wide range. Some parallelograms can overlap. Set of typical images is listed bellow.

I need an algorithm to segment objects on those images in order to prepare them to extraction of connected components. There is one restriction on the segmentation algorithm - shape of the objects should be preserved during segmentation.

Attempted solutions.

Morphological erosion.
Morphological erosion don't work well in this case. In order to separate three overlapping rectangles in the last image from typical set, I needed structuring element so big, that it erases some small objects from other images.

Boundary extraction and Hit-or-miss transform with corner-like structuring elements.
I have tried detect corners of parallelograms, in order to find regions of intersection. But pattern matching of boundary with corner-like structuring elements turned out to be a bad idea (boundary doesn't have the shape of a corner in regions of intersection).

Some other morphological transformations.
I have tried playing with combinations of original and shifted images. $A - [A - [(A)_{(-x, 0)}\cap(A)_{(+x, 0)}]]$, where $A$ is an original image and $x$ is a shift along $x$-axis. This transformation can be applied for separation of objects on the last image. But it messes up second image.

Question.

Is there good general approach to such problem?
Any ideas, hints, links, articles will be much appreciated.
Thank you.

Answer 1

After couple days of research, I have found another interesting solution. The Similar algorithm for segmentation of overlapping objects is described in this article (the algorithm below is an adaptation for objects of parallelogram shape). It uses properties of the boundary to perform separation. Perhaps someone may find it interesting.

Overlapping rectangles.

To get the intuition behind the algorithm, consider easy case of two overlapping rectangles.

We can extract the boundary ( by applying morphological transformation $A - A\ominus B$) and choose an arbitrary point on it.

Now we can traverse boundary starting with chosen point and plot the dependence $\lvert \frac{dy}{dl}(l)\rvert$ along the boundary. (Here $y$ is $y$-coordinate of a pixel and $l$ is a length of the path along boundary). Each peak on the plot is a vertical edge of the rectangle. We can select begin and end points of edges by finding intersection of the graph with threshold $t = 0.5 \underset{l}{\max}\lvert\frac{dy}{dl}(l)\rvert$.

After all, we can connect each pair of points with the amount of points on the path between them greater than 3, and distance between them $d < d_{0}$.

More complex parallelograms.

This algorithm is also suited for handling more complex overlapping parallelograms. In this case dependence $\lvert\frac{dy}{dl}(l)\rvert$ will have the same form as for case with rectangels, but reversed around $x$-axis and shifted. So, the same technique can be applied to extract corner points.

Noisy rectangles.

For noisy objects (as in my case) the dependence $\lvert\frac{dy}{dl}(l)\rvert$ doesn't have such straight shape, as in previous cases. So, additional effort can be required. In order to increase performance of an algorithm, I have applied closing to the original image and moving average filter to the sequence $y[l]$, before calculating derivative.

Answer 2

You can use a line structure with 90 degree and a pre-defined thickness to erode the image. Then scan along the x-axis. In each y-axis line, it can be viewed as connection parts if there are more than 4 pixels.