# Detect grid corner

I have a picture (B&W) of a curve which is plotted on a gridded paper.

What I would like to do is to find the points which are corners of the grid. I apply Harris corner detection algorithm to detect the corner points which actually works fine (red dots in the picture). However, there are of course other points that return as outputs of the Harris algorithm. How can I get only the corner points of the grid?

Any idea will be appreciated.

• An idea: the corners form a lattice (see Wikipedia). Assuming most points are corners, you can identify the lattice and reject point that are not in it.
– MBaz
Nov 27 '16 at 1:01
• @MBaz, thanks, that would be an idea but this is only part of the image. There are almost same amount of non-grid-corner points as grid-corner points in the full size picture. And other issue is the corner points are not perfectly aligned (see detected corner points at the thick line in the picture). I wonder if there is a way to detect only the points which are orthogonal to each other.
– Lati
Nov 27 '16 at 10:09
• A lattice can be rotated; the point is that the relationship between (x,y) coordinates of the lattice points remains constant. I think that if you set a threshold to allow for small variations, you can detect all or most grid corners, especially if you don't need 100% accuracy.
– MBaz
Nov 27 '16 at 16:02
• @MBaz, I need to detect all corners actually, but I can do post processing if I can at least detect average grid size at X and Y direction. I have googled using "lattice reduction" keyword and found a Matlab library (LPAC), it works well indeed however it is commercial. I need a .net library, do you know any?
– Lati
Nov 28 '16 at 8:07
• I don't know any libraries (I don't work in image processing). But I still feel that a naive algorithm may get you going. For instance: for every point, find the point's four nearest neighbors and their distance. I think you'll be able to tell apart the corners by the distance to their neighbors.
– MBaz
Nov 28 '16 at 14:37

1. Threshold the image to convert into binary image.
2. Check whether it is a corner or not by dilating with these kernels separately on corners detected by corner detection. $$E_1 = \begin{bmatrix}0 & 0 &0 & 1& 0\\0 & 0 & 0 & 1& 0\\0 & 0 & 0 & 1& 0\\1 & 1 & 1 & 1& 0\\0 & 0 & 0 & 0& 0\end{bmatrix}$$ $$E_2 = \begin{bmatrix}0 & 1 &0 & 0& 0\\0 & 1 & 0 & 0& 0\\0 & 1 & 0 & 0& 0\\0 & 1 & 1 & 1& 1\\0 & 0 & 0 & 0& 0\end{bmatrix}$$ $$E_3 = \begin{bmatrix}0 & 0 &0 & 0& 0\\0 & 1 & 1 & 1& 1\\0 & 1 & 0 & 0& 0\\0 & 1 & 0 & 0& 0\\0 & 1 & 0 & 0& 0\end{bmatrix}$$ $$E_4 = \begin{bmatrix}0 & 0 &0 & 0& 0\\1 & 1 & 1 & 1& 0\\0 & 0 & 0 & 1& 0\\0 & 0 & 0 & 1& 0\\0 & 0 & 0 & 1& 0\end{bmatrix}$$
3. If it's not a corner all these kernels will result 1. If it's a corner one of these kernels will result in 0. Based on distance between lattices you can modify the height and width of the kernel.
• Thanks for your response. Currently writing a program to test it but have few questions. As you see in the picture, not all corner points are really aligned with the grid corner (and with each other). Do you think that might be an issue? And I have around 9000 corner points detected in a picture; I wonder if there will be a performance issue with dilating all points 4 different kernels.
– Lati
Nov 27 '16 at 10:00
• The corners will be missed if it's not perfectly aligned with the use of these kernels.. Nov 27 '16 at 10:05
• yes, that is my point. Image can also be rotated in reality. I wonder if there is a method to detect the grid points which are orthogonal to each other.
– Lati
Nov 27 '16 at 10:12
• How about using hough transform to extract lines and perform corner detection on those lines.. Nov 27 '16 at 10:15
• I have tried that but this assumes detecting all lines in the picture which Hough transform doesn't promise.
– Lati
Nov 27 '16 at 10:24

I'd try something like this (assuming pictures contain more or less strictly horizontal and vertical lines):

1. for each horizontal line, check how many black pixels are included (black pixels should be pixels below a certain threshold which you can work out by trial and error, also you might have to check each color channel seperately when working with RGB images)

2. if a line includes a certain amount of black pixels, it is a grid line. (thresholding here as well, i'd start at > 50%)

3. repeat process for vertical lines

4. get intersection points

you might wanna double check at some point using average line distances.