opencv - Approximating a group of line segments with only one -

assuming have group of lines segments red lines (or green lines) in picture

i want know how can replace them 1 line segment approximates them best. or maybe can advise search since might common problem in statistics.

problem background: comes using opencv's probabilistic hough transform. want detect corners of piece of paper. when apply image on edges group of lines want convert single line continuous segment.

one way thinking of, take line couple of points , use line regression equation of line. once have should cut segment.

this great question. right way @ integrate error along each line segment. instead of simple term (y[i] - y_hat)^2 (where y_hat predicted value regression line) should have integral((y[i](t) - y_hat)^2, t, 0, 1) y[i](t) parametrization of line segment, y[i](t) = t * y[i, 1] + (1 - t)*y[i, 0] (denoting endpoints of i-th segment y[i, 0] , y[i, 1]). think you'll find can compute integral , therefore you'll terms sum of squared errors involve endpoints. i've left out details think that's enough work out rest. edit: error terms should squared; i've adjusted formulas accordingly.

2nd edit: worked out formulas (using maxima). regression line represented y = alpha*x + beta, least squares estimates alpha , beta:

alpha = (4*('sum(ll[k],k,1,n))*'sum(xx[k][2]*yy[k][2]*ll[k],k,1,n)     +2*('sum(ll[k],k,1,n))*'sum(xx[k][1]*yy[k][2]*ll[k],k,1,n)     +('sum(xx[k][2]*ll[k],k,1,n))*(-3*'sum(yy[k][2]*ll[k],k,1,n)                                   -3*'sum(yy[k][1]*ll[k],k,1,n))     +('sum(xx[k][1]*ll[k],k,1,n))*(-3*'sum(yy[k][2]*ll[k],k,1,n)                                   -3*'sum(yy[k][1]*ll[k],k,1,n))     +2*('sum(ll[k],k,1,n))*'sum(yy[k][1]*xx[k][2]*ll[k],k,1,n)     +4*('sum(ll[k],k,1,n))*'sum(xx[k][1]*yy[k][1]*ll[k],k,1,n))     /(4*('sum(ll[k],k,1,n))*'sum(xx[k][2]^2*ll[k],k,1,n)      +4*('sum(ll[k],k,1,n))*'sum(xx[k][1]*xx[k][2]*ll[k],k,1,n)      -3*('sum(xx[k][2]*ll[k],k,1,n))^2      -6*('sum(xx[k][1]*ll[k],k,1,n))*'sum(xx[k][2]*ll[k],k,1,n)      +4*('sum(ll[k],k,1,n))*'sum(xx[k][1]^2*ll[k],k,1,n)      -3*('sum(xx[k][1]*ll[k],k,1,n))^2)    beta = -((2*'sum(xx[k][2]*ll[k],k,1,n)+2*'sum(xx[k][1]*ll[k],k,1,n))    *'sum(xx[k][2]*yy[k][2]*ll[k],k,1,n)    +('sum(xx[k][2]*ll[k],k,1,n)+'sum(xx[k][1]*ll[k],k,1,n))     *'sum(xx[k][1]*yy[k][2]*ll[k],k,1,n)    +('sum(xx[k][2]^2*ll[k],k,1,n))*(-2*'sum(yy[k][2]*ll[k],k,1,n)                                    -2*'sum(yy[k][1]*ll[k],k,1,n))    +('sum(xx[k][1]*xx[k][2]*ll[k],k,1,n))     *(-2*'sum(yy[k][2]*ll[k],k,1,n)-2*'sum(yy[k][1]*ll[k],k,1,n))    +('sum(xx[k][1]^2*ll[k],k,1,n))*(-2*'sum(yy[k][2]*ll[k],k,1,n)                                    -2*'sum(yy[k][1]*ll[k],k,1,n))    +('sum(xx[k][2]*ll[k],k,1,n)+'sum(xx[k][1]*ll[k],k,1,n))     *'sum(yy[k][1]*xx[k][2]*ll[k],k,1,n)    +2*('sum(xx[k][1]*yy[k][1]*ll[k],k,1,n))*'sum(xx[k][2]*ll[k],k,1,n)    +2*('sum(xx[k][1]*ll[k],k,1,n))*'sum(xx[k][1]*yy[k][1]*ll[k],k,1,n))    /(4*('sum(ll[k],k,1,n))*'sum(xx[k][2]^2*ll[k],k,1,n)     +4*('sum(ll[k],k,1,n))*'sum(xx[k][1]*xx[k][2]*ll[k],k,1,n)     -3*('sum(xx[k][2]*ll[k],k,1,n))^2     -6*('sum(xx[k][1]*ll[k],k,1,n))*'sum(xx[k][2]*ll[k],k,1,n)     +4*('sum(ll[k],k,1,n))*'sum(xx[k][1]^2*ll[k],k,1,n)     -3*('sum(xx[k][1]*ll[k],k,1,n))^2) 

where xx , yy lists of pairs of values, 1 pair each line segment. is, xx[k] x-coordinates endpoints of k-th segment, yy[k] y-coordinates endpoints of k-th segment, , ll[k] length sqrt((xx[k][2] - xx[k][1])^2 + (yy[k][2] - yy[k][1])^2) of k-th segment.

here program derive formulas. there other reasonable ways set problem yield similar different formulas.

y_hat[k](l) := alpha * x[k](l) + beta; x[k](l) := (1 - l/ll[k]) * xx[k][1] + l/ll[k] * xx[k][2]; y[k](l) := (1 - l/ll[k]) * yy[k][1] + l/ll[k] * yy[k][2]; e[k]:= y[k](l) - y_hat[k](l); foo : sum (integrate (e[k]^2, l, 0, ll[k]), k, 1, n); declare (nounify (sum), linear); [da, db] : [diff (foo, alpha), diff (foo, beta)]; map (expand, %); bar : solve (%, [alpha, beta]); 

here example data , result get. postponed defining dx, dy, , ll because, since constant terms, didn't want them expanded in solutions alpha , beta.

dx[k] := xx[k][2] - xx[k][1]; dy[k] := yy[k][2] - yy[k][1]; ll[k] := sqrt (dx[k]^2 + dy[k]^2);  xx : [[1,2],[1.5,3.5],[5.5,10.5]]$ yy : [[1,2.2],[1.5,3.3],[5,12]]$  ''bar, nouns, n=length(xx);   => [[alpha = 1.133149837130799, beta = - 0.4809409869515073]]