4
$\begingroup$

I have a task in image processing, which need to detect vertical lines from matrix. For example, there is a pair of white and black vertical lines segmenting the picture below. I need to find it. So I want to find the lines labeled in red.

enter image description here enter image description here

Actually, this matrix consists only -1(black), 0(gray) and 1(white), which is from edge detection and non-maximum suppression algorithm. But how to get the longest white and black line pairs? I want to find an algorithm which can give solutions in more complicated situations, like picture below:

enter image description here enter image description here enter image description here

There may have more than one pairs in the matrix. I think it need to group pixels according to points continuity and consider gaps. The short lines along y axis can be regarded as noise.

Is there an appropriate algorithm or feasible route to complete it? Hope to get your advice.

matrix image:

enter image description here

enter image description here

enter image description here

enter image description here

Improve this question
$\endgroup$
5
  • $\begingroup$ Is that really your data, exactly? Is there a minimum length of line where you stop being interested? Is a line with a gap of interest (depending on how you define "a gap" your top picture may or may not have one, in the upper left quadrant)? $\endgroup$
    – TimWescott
    Commented Jun 20, 2023 at 23:08
  • $\begingroup$ @TimWescott Hi! Yes, I can set a minimum length of line in y axis, say, half of the number of rows. I have added the target line in red of top picture. The points in target line are not completely continuous. There may have points gaps. So how can we detect the target line like human eyes? $\endgroup$
    – Jun Yang
    Commented Jun 21, 2023 at 1:05
  • $\begingroup$ @JunYang, We need the actual images. Not the plots. $\endgroup$
    – Royi
    Commented Jun 24, 2023 at 6:15
  • $\begingroup$ The last image you posted is before thresholding. I think that is the better image to work on. You can set up a simple optimization scheme where you find the path from top to bottom with the highest sum intensity. A grey-weighted distance transform would get you there. See this post, towards the bottom. Not exactly the same problem, but similar enough. $\endgroup$
    – Cris Luengo
    Commented Jun 24, 2023 at 16:48
  • $\begingroup$ @CrisLuengo Thank you for your reply. This is also a promising and novel solution. $\endgroup$
    – Jun Yang
    Commented Jun 25, 2023 at 13:24

1 Answer 1

Reset to default
3
$\begingroup$

You may use the Dynamic Programming approach as utilized in Seam Carving for Content Aware Image Resizing.

Just replace their weights with yours.

Julia Implementation

I implemented the idea of looking for the longest chain using dynamic programming.

This is the input image:

enter image description here

We have 3 values: Blue -> Edges of 0, Green -> Background and Yellow -> Edges of 255.

We need to work on each on itself. For instance, this is the image of the 0 edges:

enter image description here

Now, using the dynamic programming based algorithm we can build the path.
The idea is very simple, per pixel we look at row above it in its 8 connected neighborhood. We find the maximum and keep the value and the direction. We add the value to the values accumulated until this step.

mS[ii - 1, jj - 1]  mS[ii - 1, jj] mS[ii - 1, jj + 1]
                  ↖         ↑      ↗
                       mS[ii, jj]

For the case above the result is:

↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑
↑↖↖↖↖↗↑↖↖↖↖↗↑↖↖↖↖↖↖↖↖↖↗↑↖↖↖↖↖↖
↑↖↖↖↗↑↖↖↖↖↗↗↑↖↖↖↖↖↖↖↖↗↑↗↑↖↖↖↖↖
↑↖↖↗↑↖↖↖↖↖↗↑↖↖↖↖↖↖↖↖↗↑↗↑↗↑↖↖↖↖
↑↖↖↖↖↖↖↖↖↗↗↑↖↖↖↖↖↖↖↗↑↖↑↗↑↗↑↖↖↖
↑↖↖↖↖↖↖↖↗↗↗↑↖↖↖↖↖↖↗↑↗↑↖↑↗↗↑↖↖↖
↑↖↖↖↖↖↖↗↗↗↗↑↖↖↖↖↖↖↑↗↗↑↖↗↗↗↑↖↖↖
↑↖↖↖↖↖↗↗↗↗↗↑↖↖↖↖↖↖↗↗↗↑↖↗↗↑↖↖↖↖
↑↖↖↖↖↖↗↗↗↗↑↗↑↖↖↖↖↑↖↗↗↑↖↗↗↑↖↖↖↖
↑↖↖↖↖↖↗↑↗↑↗↗↑↖↖↖↖↖↗↗↗↑↖↗↗↑↖↖↖↖
↑↖↖↖↖↖↑↗↑↖↗↗↑↖↖↖↖↖↗↗↑↖↗↗↗↑↖↖↖↖
↑↖↖↖↖↖↗↑↖↗↗↑↖↖↖↖↖↖↗↑↖↗↗↗↑↖↖↖↖↖
↑↖↖↖↖↗↑↖↗↗↑↖↖↖↖↖↖↖↖↖↗↗↗↑↖↖↖↖↖↖
↑↖↖↖↗↑↖↗↗↗↑↖↖↖↖↖↖↖↖↗↗↗↑↖↖↖↖↖↖↖
↑↖↖↗↑↖↗↗↗↑↗↑↖↖↖↖↖↖↖↗↗↑↖↖↖↖↖↖↖↖
↑↖↗↑↖↗↗↗↑↗↗↑↖↖↖↖↖↑↖↖↑↖↖↖↖↖↖↗↑↖
↑↗↑↖↗↗↗↑↗↗↗↑↖↖↖↖↗↑↖↖↖↖↖↖↖↖↗↗↑↖
↗↑↖↗↗↗↑↗↗↗↑↖↖↖↖↖↖↗↑↖↖↖↖↖↖↗↗↗↑↖
↑↖↗↗↗↑↗↗↗↑↖↖↖↖↖↖↖↗↑↖↖↖↖↖↗↗↗↗↑↖
↑↗↗↗↑↗↗↗↗↑↖↖↖↗↑↖↖↖↖↖↖↖↖↗↗↗↗↗↑↖
↗↗↗↑↗↗↗↗↑↗↑↖↖↑↗↑↖↖↖↗↑↖↖↗↗↗↗↑↖↖
↗↗↑↗↗↗↗↑↗↑↖↖↖↗↗↑↖↖↖↗↑↖↖↖↗↗↑↖↖↖
↗↑↗↗↗↗↑↗↑↗↑↖↖↖↗↑↖↖↖↗↑↖↖↖↗↑↖↖↖↖
↑↗↗↗↗↑↗↑↗↗↑↖↖↗↑↗↑↖↖↖↑↖↖↖↖↖↖↖↖↖
↗↗↗↗↑↗↑↗↗↗↑↖↖↖↗↗↑↖↖↖↗↑↖↖↖↖↖↖↖↖
↗↗↗↑↗↑↗↗↗↑↖↖↖↖↗↑↖↖↖↖↗↑↖↖↖↖↖↖↖↖
↗↗↑↗↑↗↗↗↑↖↖↖↗↑↖↖↗↑↖↖↖↑↖↖↖↖↖↖↖↖
↗↑↗↑↗↗↗↑↖↖↖↗↗↑↖↖↗↑↖↖↖↑↖↖↖↖↖↖↖↖
↑↗↑↗↗↗↑↖↗↑↖↗↗↑↖↖↗↑↖↖↖↑↖↖↖↖↖↖↖↖
↗↑↗↗↗↑↖↗↗↑↖↗↗↑↖↖↗↑↖↖↖↑↖↖↖↖↖↖↖↖
↑↗↗↗↑↖↗↗↑↗↑↗↑↖↖↖↗↑↖↖↖↑↖↖↖↖↖↖↖↖
↗↗↗↑↖↗↗↑↗↗↑↖↖↖↖↖↖↗↑↖↖↖↖↖↖↖↖↖↖↖
↗↗↑↖↗↗↑↗↗↗↑↖↖↗↑↖↗↗↑↖↖↖↖↖↖↖↖↖↖↖
↗↑↖↗↗↑↗↗↗↑↖↖↖↖↖↖↗↑↖↖↖↖↖↖↖↖↖↖↖↖

With the chosen path being:

enter image description here

The binary image for the edges of 255:

enter image description here

The path of the edges of 255:

enter image description here

It looks like the method is working for your case.

The code is available at my StackExchange Codes Signal Processing GitHub Repository (Look at the SignalProcessing\Q88303 folder).

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks. I think this is a promising solution for my problem. But I am not sure how to apply it to the line detection here. I have updated three pictures in png in my question. Hope to receive your help. $\endgroup$
    – Jun Yang
    Commented Jun 23, 2023 at 13:55
  • $\begingroup$ @JunYang, I see the images as plots. Can you give the RAW data, not the plot()? $\endgroup$
    – Royi
    Commented Jun 23, 2023 at 15:37
  • $\begingroup$ Thank you for your response. I apologize for the misunderstanding. I have updated 3 png files for the matrix in the end. After I reading the paper of seam carving, I think the key of my question is making multiple seams from the matrix with no overlapping. Actually, the matrix above are results of non-maximum suppression. Raw data is exactly a gradient computation result, which can be regarded as energy matrix (last one in my question). So I want to use DP to make the pair of seam lines (-1 and +1). One matrix may have more than one pair. Is there some advice to implement it? $\endgroup$
    – Jun Yang
    Commented Jun 24, 2023 at 9:38
  • $\begingroup$ @JunYang, I implemented the method I wrote. It works well. $\endgroup$
    – Royi
    Commented Jun 24, 2023 at 17:07
  • $\begingroup$ Thanks a lot for implementing the method. This is a very good solution for me. I'm going to try implementing it on my end using the instructions you provided. Really appreciate your assistance. $\endgroup$
    – Jun Yang
    Commented Jun 25, 2023 at 13:21

Your Answer

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

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