0
$\begingroup$

Suppose there is an image with long, connected lines which form connected, closed cycles in an image.

Is there a standard morphological approach to isolate only the lines, and drop all other pixels?

I can imagine a couple of slow approaches:

  1. convolutional approach where a window -- say, 50x50 -- is passed along the image, and any non-zero pixels which are not connected to a pixel on the perimeter of the window are set to 0.

  2. Skeletonize - threshold the components - close - skeletonize ...: the skeleton is calculated, small components are dropped, disconnected skeletons are closed, and the skeleton is recalculated and re-thresholded. Repeat.

But it seems like this would be a common problem, and there should be an easy solution...?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

OpenCV offers a set of routines embracing all the operations necessary for graph network extraction from pixel images. Yet, to my knowledge, there is no a "graph network extraction" toolbox in OpenCV on the manner of MATLAB toolboxes that supply integrated solutions for DSP, image processing, etc. tasks.

The search for a solution of the kind brought me a Nature article NEFI: Network Extraction From Images by M. Dirnberger, T. Kehl & A. Neumann.

The NEFI tool is freely available, both in the form of release binaries and the source code. I have no practical experience with this tool and cannot recommend it to you, but I like the Nature article and follow their guidelines to summarize the review of graph network extraction techniques. In fact, I've compiled my answer from the article text, attaching comments and references for your convenience.

A typical pipeline of a solution for graph network extraction combines algorithms from up to four different classes: preprocessing, segmentation, graph detection and graph filtering.

PREPROCESSING

Uses operations on pixel images, like filtering (blurring, denoising) and maybe color adjustment, to ease the operation and, to a degree, to improve the results of a segmentation step.

SEGMENTATION

Separates the image foreground, i.e. the structures of interest representing a graph network, from the remaining image.

It seems that the first (historically) segmentation method is Otsu's method (adaptive thresholding): a threshold that gives the best separation of "background" and "graph object" pixel classes in gray levels would be the best threshold.

Watershed algorithms are based on the "flooding" process performed on the gradient image (priority-flood). The algorithms define and use a set of markers, pixels where the flooding shall start. Implementation and application: see the article On Graph Extraction from Image data.

Otsu's and watershed segmentation approaches work on grayscale images.

The GrabCut algorithm based on graph cuts works on color images and, similar to watershed algos, also receive an additional input from markers. The algorithm is implemented in an openCV function

cv.grabCut (image, mask, rect, bgdModel, fgdModel, iterCount, mode = cv.GC_EVAL)

, see an OpenCV tutorial Foreground Extraction using GrabCut.

See also an CNN implementation: https://grlearning.github.io/papers/23.pdf

GRAPH DETECTION followed by GRAPH FILTERING

Morphological operations (thinning) performed on segmentation results give a skeleton of the segmented image. The skeleton is used to find the graph node positions and consequently the graph edges.

If you've read up to this point, you may agree that a one-piece morphological operation of your description,

a standard morphological approach to isolate only the lines, and drop all other pixels

, has yet to be developed.

To the moment, in order "to isolate only the lines, and drop all other pixels", the software developers can only offer a pipeline of at least two stages: segmentation (e.g., with a $cv.grabCut(..)$ function) and graph detection (thinning procedure).

The output of graph detection algorithms is further improved in the graph filtering stage using heuristic or user assisted methods. The NEFI creators developed an approach exploiting the structure of the extracted graph.

The graph filter operation can also be considered partially overlapping with your item 2 description.

I hope this answer would help you develop your own solution, or you will decide to contribute to the NEFI project or the other graph extraction projects on GitHub.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is a pretty amazing answer. Suppose one has obtained a skeleton that is "decent" for these purposes. Is there any skeleton specific erosion functionality that will only erode leaf pixels, and leave all other pixels untouched? $\endgroup$
    – Chris
    Mar 27, 2021 at 11:22
  • $\begingroup$ In principle, you can find a leaf (external vertex) with the hit-n-miss transform, defining an appropriate structuring element (stencil), and then progressively eat into the leaf's edge up to a full destruction of this edge. Notice that this operation is not equivalent to erosion or thinning. But, in my opinion, the graph filtering stage is a better option to get rid of external vertices. At this stage, you have a complete graph and you can adjust it to any structural requirements. $\endgroup$
    – V.V.T
    Mar 28, 2021 at 10:35
  • $\begingroup$ To be able to mirror the graph to an original image, make sure you maintain a mapping between pixels of the original image and the graph's elements (nodes, edges) throughout a computation pipeline. $\endgroup$
    – V.V.T
    Mar 28, 2021 at 10:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.