javascript - How to find horizon line efficiently in a high-altitude photo?

Question

I am trying to detect the horizon in images taken from high altitude, so as to determine the orientation of the camera. I am also trying to have this run fast - ideally, I'd like to be able to process frames in real time (that is, a few frames per second) on a Raspberry Pi. The approach I've been taking so far is based on the fact that at high altitudes the sky is very dark, like so:

What I've tried is taking samples from all over the image and separating them into light and dark samples, and drawing a line between them. However, this places the horizon above its actual location, due to the fuzzyness of the amosphere:

And here's my code (in Javascript for ease of web demo):

function mag(arr) {
    return Math.sqrt(arr[0]*arr[0]+arr[1]*arr[1]+arr[2]*arr[2])
}
// return (a, b) that minimize
// sum_i r_i * (a*x_i+b - y_i)^2
function linear_regression( xy ) {
    var i,
        x, y,
        sumx=0, sumy=0, sumx2=0, sumy2=0, sumxy=0, sumr=0,
        a, b;
    for(i=0;i<xy.length;i++) {
        x = xy[i][0]; y = xy[i][2];
        r = 1
        sumr += r;
        sumx += r*x;
        sumx2 += r*(x*x);
        sumy += r*y;
        sumy2 += r*(y*y);
        sumxy += r*(x*y);
    }
    b = (sumy*sumx2 - sumx*sumxy)/(sumr*sumx2-sumx*sumx);
    a = (sumr*sumxy - sumx*sumy)/(sumr*sumx2-sumx*sumx);
    return [a, b];
}


var vals = []
for (var i=0; i<resolution; i++) {
            vals.push([])
            for (var j=0; j<resolution; j++) {
                    x = (canvas.width/(resolution+1))*(i+0.5)
                    y = (canvas.height/(resolution+1))*(j+0.5)
                    var pixelData = cr.getImageData(x, y, 1, 1).data;
                    vals[vals.length-1].push([x,y,pixelData])
                    cr.fillStyle="rgb("+pixelData[0]+","+pixelData[1]+","+pixelData[2]+")"
                    cr.strokeStyle="rgb(255,255,255)"
                    cr.beginPath()
                    cr.arc(x,y,10,0,2*Math.PI)
                   cr.fill()
                    cr.stroke()
            }
    }
    var line1 = []
    var line2 = []
    for (var i in vals) {
            i = parseInt(i)
            for (var j in vals[i]) {
                    j = parseInt(j)
                    if (mag(vals[i][j][3])<minmag) {
                            if ((i<(vals.length-2) ? mag(vals[i+1][j][4])>minmag : false)
                             || (i>0 ? mag(vals[i-1][j][5])>minmag : false)
                             || (j<(vals[i].length-2) ? mag(vals[i][j+1][6])>minmag : false)
                             || (j>0 ? mag(vals[i][j-1][7])>minmag : false)) {
                                    cr.strokeStyle="rgb(255,0,0)"
                                    cr.beginPath()
                                    cr.arc(vals[i][j][0],vals[i][j][8],10,0,2*Math.PI)
                                    cr.stroke()
                                    line1.push(vals[i][j])
                            }
                    }
                    else if (mag(vals[i][j][9])>minmag) {
                            if ((i<(vals.length-2) ? mag(vals[i+1][j][10])<minmag : false)
                             || (i>0 ? mag(vals[i-1][j][11])<minmag : false)
                             || (j<(vals[i].length-2) ? mag(vals[i][j+1][12])<minmag : false)
                             || (j>0 ? mag(vals[i][j-1][13])<minmag : false)) {
                                    cr.strokeStyle="rgb(0,0,255)"
                                    cr.beginPath()
                                    cr.arc(vals[i][j][0],vals[i][j][14],10,0,2*Math.PI)
                                    cr.stroke()
                                    line2.push(vals[i][j])
                            }
                    }
            }
        }
        eq1 = linear_regression(line1)
        cr.strokeStyle = "rgb(255,0,0)"
        cr.beginPath()
        cr.moveTo(0,eq1[1])
        cr.lineTo(canvas.width,canvas.width*eq1[0]+eq1[1])
        cr.stroke()
        eq2 = linear_regression(line2)
        cr.strokeStyle = "rgb(0,0,255)"
        cr.beginPath()
        cr.moveTo(0,eq2[1])
        cr.lineTo(canvas.width,canvas.width*eq2[0]+eq2[1])
        cr.stroke()
        eq3 = [(eq1[0]+eq2[0])/2,(eq1[1]+eq2[1])/2]
        cr.strokeStyle = "rgb(0,255,0)"
        cr.beginPath()
        cr.moveTo(0,eq3[1])
        cr.lineTo(canvas.width,canvas.width*eq3[0]+eq3[1])
        cr.stroke()

And the result (green line is the detected horizon, red and blue are estimated outside bounds):

How can I improve this? And is there a more efficient way to do it? The final program will probably be written in Python, or C if that's too slow.

Answer 1

Consider some basic channel mixing and thresholding, followed by vertical samples as @Spektre suggests. [Edited to change to 2*R-B instead of R+G-B following @Spektre's comment]

Here are some options on the channel mixing:

1. Original
2. Flat mono mix R+G+B
3. Red channel
4. 2*R - B
5. R + G - B

It looks like #4 is the clearest horizon (thanks @Spektre for making me check this more carefully), mixing the colours in a ratio [Red 2: Green 0: Blue -1], you get this monochrome image:

Setting blue negative means that the blue haze over the horizon is used to kill off the fuzziness there. This turns out to be more effective than just using red and/or green (try it with the Channel Mixer in the GIMP).

Then we can clarify further, if you like, by thresholding (although you could do this after sampling), here at 25% grey:

Using Spektre's approach of vertically sampling the image, just scan down until you see the value go over 25%. With 3 lines, you should gain 3 x,y pairs and thus reconstruct the curve knowing that it is a parabola.

For more robustness, take more than 3 samples and discard outliers.