# Detect Longest Vertical Lines (Edges) in an Image

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.

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:

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:

• 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)? Jun 20, 2023 at 23:08
• @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? Jun 21, 2023 at 1:05
• @JunYang, We need the actual images. Not the plots.
– Royi
Jun 24, 2023 at 6:15
• 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. Jun 24, 2023 at 16:48
• @CrisLuengo Thank you for your reply. This is also a promising and novel solution. Jun 25, 2023 at 13:24

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:

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:

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:

The binary image for the edges of 255:

The path of the edges of 255:

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).

• 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. Jun 23, 2023 at 13:55
• @JunYang, I see the images as plots. Can you give the RAW data, not the plot()?
– Royi
Jun 23, 2023 at 15:37
• 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? Jun 24, 2023 at 9:38
• @JunYang, I implemented the method I wrote. It works well.
– Royi
Jun 24, 2023 at 17:07
• 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. Jun 25, 2023 at 13:21