Very Simple Edge Detection

I have a simple, high-contrast, black & white video image on which I need to find the X value of a vertical edge and the Y value of a horizontal edge. I also need to know the direction of the edges (white->black or black->white).

There will be:

Zero or one horizontal edge
Zero or one vertical edge.
The edges are perfectly straight.
The edges will be defined by a sharp(ish) transition from black to white or white to black.

I've been reading about edge detection algorithms and understanding very little of it, but what I do understand is that they are all far more complex than my requirements. They are all designed to produce an image of simple edges from a complex image. My requirements (my images) are much simpler, I only need the X and a Y value of zero to two edges.

If I plot say one row of pixels on a graph (X=pixel index, Y=pixel intensity), I will get something like a line, a rising slope, and another line. The center point of the slope would be what I need. But the lines are not perfect. They are noisy and there can be small bumps or dips, or it can be (mostly) flat if no edge is visible.

So is there a simple algorithm to smooth that plot and produce both the direction and the center point of "the slope"?

Solution

I would approach this using ImageMagick straight from the command line - it is installed on most Linux distros and is available for OSX and Windows too.

So, firstly, I would go to greyscale and normalise the contrast so that you are less susceptible to variations in exposure or lighting. Then I would threshold at 50% so that all the pixels are forced to either black or white.

convert line.png -colorspace gray -normalize -threshold 50% result.png

Then I would run a tall, thin median filter (say 100 pixels tall and 1 pixel wide) to smooth the image in the vertical direction (so I can find the horizontal edges).

convert line.png -colorspace gray -normalize -threshold 50% -virtual-pixel mirror -statistic median 1x100 result.png

I would then resize the image to 1 pixel wide and 100 pixels tall to reduce the volume of output and because I would say that to find the edge within 1% of the image height is as much as you can hope for with such a noisy image.

convert line.png -colorspace gray -normalize -threshold 50% -virtual-pixel mirror -statistic median 1x100 -resize 1x100! txt:

# ImageMagick pixel enumeration: 1,100,255,srgb
0,0: (32496,32496,32496)  #7E7E7E  srgb(126,126,126)
0,1: (32969,32969,32969)  #808080  srgb(128,128,128)
0,2: (33498,33498,33498)  #828282  srgb(130,130,130)
0,3: (32632,32632,32632)  #7F7F7F  srgb(127,127,127)
0,4: (32708,32708,32708)  #7F7F7F  srgb(127,127,127)
0,5: (32787,32787,32787)  #808080  srgb(128,128,128)
0,6: (32615,32615,32615)  #7F7F7F  srgb(127,127,127)
0,7: (33186,33186,33186)  #818181  srgb(129,129,129)
0,8: (33786,33786,33786)  #838383  srgb(131,131,131)
0,9: (33610,33610,33610)  #838383  srgb(131,131,131)
0,10: (32577,32577,32577)  #7F7F7F  srgb(127,127,127)
0,11: (33159,33159,33159)  #818181  srgb(129,129,129)
0,12: (33578,33578,33578)  #838383  srgb(131,131,131)
0,13: (33276,33276,33276)  #818181  srgb(129,129,129)
0,14: (33259,33259,33259)  #818181  srgb(129,129,129)
0,15: (32620,32620,32620)  #7F7F7F  srgb(127,127,127)
0,16: (32624,32624,32624)  #7F7F7F  srgb(127,127,127)
0,17: (33131,33131,33131)  #818181  srgb(129,129,129)
0,18: (33278,33278,33278)  #818181  srgb(129,129,129)
0,19: (32680,32680,32680)  #7F7F7F  srgb(127,127,127)
0,20: (33136,33136,33136)  #818181  srgb(129,129,129)
0,21: (32707,32707,32707)  #7F7F7F  srgb(127,127,127)
0,22: (33051,33051,33051)  #818181  srgb(129,129,129)
0,23: (33794,33794,33794)  #838383  srgb(131,131,131)
0,24: (33704,33704,33704)  #838383  srgb(131,131,131)
0,25: (33028,33028,33028)  #818181  srgb(129,129,129)
0,26: (33605,33605,33605)  #838383  srgb(131,131,131)
0,27: (33785,33785,33785)  #838383  srgb(131,131,131)
0,28: (33290,33290,33290)  #828282  srgb(130,130,130)
0,29: (33079,33079,33079)  #818181  srgb(129,129,129)
0,30: (33430,33430,33430)  #828282  srgb(130,130,130)
0,31: (33246,33246,33246)  #818181  srgb(129,129,129)
0,32: (33102,33102,33102)  #818181  srgb(129,129,129)
0,33: (33248,33248,33248)  #818181  srgb(129,129,129)
0,34: (33823,33823,33823)  #848484  srgb(132,132,132)
0,35: (33678,33678,33678)  #838383  srgb(131,131,131)
0,36: (33497,33497,33497)  #828282  srgb(130,130,130)
0,37: (33960,33960,33960)  #848484  srgb(132,132,132)
0,38: (33520,33520,33520)  #828282  srgb(130,130,130)
0,39: (33235,33235,33235)  #818181  srgb(129,129,129)
0,40: (32655,32655,32655)  #7F7F7F  srgb(127,127,127)
0,41: (32825,32825,32825)  #808080  srgb(128,128,128)
0,42: (32847,32847,32847)  #808080  srgb(128,128,128)
0,43: (33214,33214,33214)  #818181  srgb(129,129,129)
0,44: (32966,32966,32966)  #808080  srgb(128,128,128)
0,45: (33262,33262,33262)  #818181  srgb(129,129,129)
0,46: (33178,33178,33178)  #818181  srgb(129,129,129)
0,47: (32501,32501,32501)  #7E7E7E  srgb(126,126,126)
0,48: (32499,32499,32499)  #7E7E7E  srgb(126,126,126)
0,49: (31982,31982,31982)  #7C7C7C  srgb(124,124,124)
0,50: (32564,32564,32564)  #7F7F7F  srgb(127,127,127)
0,51: (32336,32336,32336)  #7E7E7E  srgb(126,126,126)
0,52: (30311,30311,30311)  #767676  srgb(118,118,118)
0,53: (27119,27119,27119)  #6A6A6A  srgb(106,106,106)
0,54: (13002,13002,13002)  #333333  srgb(51,51,51)
0,55: (1855,1855,1855)  #070707  srgb(7,7,7)
0,56: (187,187,187)  #010101  srgb(1,1,1)           <--- This is your edge at 56% of the image height down from the top
0,57: (72,72,72)  #000000  srgb(0,0,0)
0,58: (0,0,0)  #000000  black
0,59: (0,0,0)  #000000  black
0,60: (0,0,0)  #000000  black
0,61: (0,0,0)  #000000  black
0,62: (0,0,0)  #000000  black
0,63: (0,0,0)  #000000  black
0,64: (0,0,0)  #000000  black
0,65: (0,0,0)  #000000  black
0,66: (0,0,0)  #000000  black
0,67: (0,0,0)  #000000  black
0,68: (0,0,0)  #000000  black
0,69: (0,0,0)  #000000  black
0,70: (0,0,0)  #000000  black
0,71: (0,0,0)  #000000  black
0,72: (0,0,0)  #000000  black
0,73: (0,0,0)  #000000  black
0,74: (0,0,0)  #000000  black
0,75: (0,0,0)  #000000  black
0,76: (0,0,0)  #000000  black
0,77: (0,0,0)  #000000  black
0,78: (0,0,0)  #000000  black
0,79: (0,0,0)  #000000  black
0,80: (0,0,0)  #000000  black
0,81: (0,0,0)  #000000  black
0,82: (0,0,0)  #000000  black
0,83: (0,0,0)  #000000  black
0,84: (0,0,0)  #000000  black
0,85: (0,0,0)  #000000  black
0,86: (0,0,0)  #000000  black
0,87: (0,0,0)  #000000  black
0,88: (0,0,0)  #000000  black
0,89: (0,0,0)  #000000  black
0,90: (0,0,0)  #000000  black
0,91: (0,0,0)  #000000  black
0,92: (0,0,0)  #000000  black
0,93: (0,0,0)  #000000  black
0,94: (0,0,0)  #000000  black
0,95: (0,0,0)  #000000  black
0,96: (0,0,0)  #000000  black
0,97: (0,0,0)  #000000  black
0,98: (0,0,0)  #000000  black
0,99: (0,0,0)  #000000  black

Likewise for your vertical edge...

convert line.png -colorspace gray -normalize -threshold 50% -virtual-pixel mirror -statistic median 100x1 -resize 100x1! txt:

# ImageMagick pixel enumeration: 100,1,255,srgb
0,0: (0,0,0)  #000000  black
1,0: (0,0,0)  #000000  black
2,0: (0,0,0)  #000000  black
3,0: (0,0,0)  #000000  black
4,0: (0,0,0)  #000000  black
5,0: (0,0,0)  #000000  black
6,0: (0,0,0)  #000000  black
7,0: (0,0,0)  #000000  black
8,0: (0,0,0)  #000000  black
9,0: (0,0,0)  #000000  black
10,0: (0,0,0)  #000000  black
11,0: (0,0,0)  #000000  black
12,0: (0,0,0)  #000000  black
13,0: (0,0,0)  #000000  black
14,0: (0,0,0)  #000000  black
15,0: (0,0,0)  #000000  black
16,0: (0,0,0)  #000000  black
17,0: (0,0,0)  #000000  black
18,0: (0,0,0)  #000000  black
19,0: (0,0,0)  #000000  black
20,0: (0,0,0)  #000000  black
21,0: (0,0,0)  #000000  black
22,0: (0,0,0)  #000000  black
23,0: (0,0,0)  #000000  black
24,0: (0,0,0)  #000000  black
25,0: (0,0,0)  #000000  black
26,0: (0,0,0)  #000000  black
27,0: (0,0,0)  #000000  black
28,0: (0,0,0)  #000000  black
29,0: (0,0,0)  #000000  black
30,0: (0,0,0)  #000000  black
31,0: (0,0,0)  #000000  black
32,0: (0,0,0)  #000000  black
33,0: (0,0,0)  #000000  black
34,0: (0,0,0)  #000000  black
35,0: (0,0,0)  #000000  black
36,0: (0,0,0)  #000000  black
37,0: (0,0,0)  #000000  black
38,0: (0,0,0)  #000000  black
39,0: (0,0,0)  #000000  black
40,0: (0,0,0)  #000000  black
41,0: (0,0,0)  #000000  black
42,0: (0,0,0)  #000000  black
43,0: (0,0,0)  #000000  black
44,0: (0,0,0)  #000000  black
45,0: (7,7,7)  #000000  srgb(0,0,0)
46,0: (87,87,87)  #000000  srgb(0,0,0)
47,0: (342,342,342)  #010101  srgb(1,1,1)
48,0: (3623,3623,3623)  #0E0E0E  srgb(14,14,14)
49,0: (16943,16943,16943)  #424242  srgb(66,66,66)      <-- This is your vertical edge, 49% of the image width across from the left side
50,0: (29779,29779,29779)  #747474  srgb(116,116,116)
51,0: (33852,33852,33852)  #848484  srgb(132,132,132)
52,0: (34745,34745,34745)  #878787  srgb(135,135,135)
53,0: (35643,35643,35643)  #8B8B8B  srgb(139,139,139)
54,0: (35893,35893,35893)  #8C8C8C  srgb(140,140,140)
55,0: (35932,35932,35932)  #8C8C8C  srgb(140,140,140)
56,0: (35934,35934,35934)  #8C8C8C  srgb(140,140,140)
57,0: (36041,36041,36041)  #8C8C8C  srgb(140,140,140)
58,0: (36095,36095,36095)  #8C8C8C  srgb(140,140,140)
59,0: (35975,35975,35975)  #8C8C8C  srgb(140,140,140)
60,0: (35937,35937,35937)  #8C8C8C  srgb(140,140,140)
61,0: (35937,35937,35937)  #8C8C8C  srgb(140,140,140)
62,0: (36042,36042,36042)  #8C8C8C  srgb(140,140,140)
63,0: (36094,36094,36094)  #8C8C8C  srgb(140,140,140)
64,0: (36148,36148,36148)  #8D8D8D  srgb(141,141,141)
65,0: (36409,36409,36409)  #8E8E8E  srgb(142,142,142)
66,0: (36409,36409,36409)  #8E8E8E  srgb(142,142,142)
67,0: (36375,36375,36375)  #8E8E8E  srgb(142,142,142)
68,0: (36252,36252,36252)  #8D8D8D  srgb(141,141,141)
69,0: (36214,36214,36214)  #8D8D8D  srgb(141,141,141)
70,0: (36176,36176,36176)  #8D8D8D  srgb(141,141,141)
71,0: (36274,36274,36274)  #8D8D8D  srgb(141,141,141)
72,0: (36406,36406,36406)  #8E8E8E  srgb(142,142,142)
73,0: (36366,36366,36366)  #8E8E8E  srgb(142,142,142)
74,0: (36128,36128,36128)  #8D8D8D  srgb(141,141,141)
75,0: (36004,36004,36004)  #8C8C8C  srgb(140,140,140)
76,0: (35900,35900,35900)  #8C8C8C  srgb(140,140,140)
77,0: (35872,35872,35872)  #8C8C8C  srgb(140,140,140)
78,0: (35855,35855,35855)  #8C8C8C  srgb(140,140,140)
79,0: (35779,35779,35779)  #8B8B8B  srgb(139,139,139)
80,0: (35777,35777,35777)  #8B8B8B  srgb(139,139,139)
81,0: (35664,35664,35664)  #8B8B8B  srgb(139,139,139)
82,0: (35774,35774,35774)  #8B8B8B  srgb(139,139,139)
83,0: (35785,35785,35785)  #8B8B8B  srgb(139,139,139)
84,0: (35753,35753,35753)  #8B8B8B  srgb(139,139,139)
85,0: (35671,35671,35671)  #8B8B8B  srgb(139,139,139)
86,0: (35675,35675,35675)  #8B8B8B  srgb(139,139,139)
87,0: (35694,35694,35694)  #8B8B8B  srgb(139,139,139)
88,0: (35621,35621,35621)  #8B8B8B  srgb(139,139,139)
89,0: (35819,35819,35819)  #8B8B8B  srgb(139,139,139)
90,0: (36080,36080,36080)  #8C8C8C  srgb(140,140,140)
91,0: (36300,36300,36300)  #8D8D8D  srgb(141,141,141)
92,0: (36550,36550,36550)  #8E8E8E  srgb(142,142,142)
93,0: (36561,36561,36561)  #8E8E8E  srgb(142,142,142)
94,0: (36425,36425,36425)  #8E8E8E  srgb(142,142,142)
95,0: (36268,36268,36268)  #8D8D8D  srgb(141,141,141)
96,0: (36317,36317,36317)  #8D8D8D  srgb(141,141,141)
97,0: (36409,36409,36409)  #8E8E8E  srgb(142,142,142)
98,0: (36521,36521,36521)  #8E8E8E  srgb(142,142,142)
99,0: (36568,36568,36568)  #8E8E8E  srgb(142,142,142)

This is your median filtered image for the vertical edge:

And, I can draw the detected edges on in red like this:

convert line.png -stroke red -draw "line 0,268 640,268" -draw "line 313,0 313,480" result.png

So, in summary, the two commands you would run in Terminal, without writing or compiling and linking any code, are as follows:

# Find horizontal edges
convert line.png -colorspace gray -normalize -threshold 50% -virtual-pixel mirror -statistic median 1x100 -resize 1x100! txt:

# Find vertical edges
convert line.png -colorspace gray -normalize -threshold 50% -virtual-pixel mirror -statistic median 100x1 -resize 100x1! txt: