// 伪代码
LineFit(Pixel ⁄pixelChain, int noPixels){
double lineFitError = INFINITY; // current line fit error
LineEquation lineEquation; // y = ax + b OR x = ay + b
while (noPixels > MIN_LINE_LENGTH){
LeastSquaresLineFit(pixelChain, MIN_LINE_LENGTH, &lineEquation,
&lineFitError);
if (lineFitError <= 1.0) break; // OK. An initial line segment detected
pixelChain ++; // Skip the first pixel & try with the remaining pixels
noPixels–; // One less pixel
} // end-while
if (lineFitError > 1.0) return; // no initial line segment. Done.
// An initial line segment detected. Try to extend this line segment
int lineLen = MIN_LINE_LENGTH;
while (lineLen < noPixels){
double d = ComputePointDistance2Line(lineEquation,
pixelChain[lineLen]);
if (d > 1.0) break;
lineLen++;
} //end-while
// End of the current line segment. Compute the final line equation & output it.
LeastSquaresLineFit(pixelChain, lineLen, &lineEquation);
Output ‘‘lineEquation’’
// Extract line segments from the remaining pixels
LineFit(pixelChain + lineLen, noPixels-lineLen);
} //end-LineFit
//下一次讨论代码
此部分思想源于Desolneux提出的方法,主要思路是引入一个*NFA(Number of False Alarms,误检数量)*的概念
首先提出梯度值和梯度角的概念
3.1、计算像素的梯度
每个点的梯度值*m(x,y)*和梯度角
θ
(
x
,
y
)
\theta(x,y)
θ(x,y)
一般的梯度和梯度角度公式:
m
(
x
,
y
)
=
[
L
(
x
+
1
,
y
)
−
L
(
x
−
1
,
y
)
]
2
+
L
(
x
,
y
+
1
)
−
L
(
x
,
y
−
1
)
]
2
m(x,y) = \sqrt{[L(x+1,y)-L(x-1,y)]^2+L(x,y+1)-L(x,y-1)]^2}
m(x,y)=[L(x+1,y)−L(x−1,y)]2+L(x,y+1)−L(x,y−1)]2
θ
(
x
,
y
)
=
a
r
c
t
a
n
L
(
x
,
y
+
1
)
−
L
(
x
,
y
−
1
)
L
(
x
+
1
,
y
)
−
L
(
x
−
1
,
y
)
\theta(x,y) = arctan{\frac{L(x,y+1)-L(x,y-1)}{L(x+1,y)-L(x-1,y)}}
θ(x,y)=arctanL(x+1,y)−L(x−1,y)L(x,y+1)−L(x,y−1)
论文的梯度和梯度角度公式:
g
x
(
x
,
y
)
=
L
(
x
+
1
,
y
)
−
L
(
x
,
y
)
+
L
(
x
+
1
,
y
+
1
)
−
L
(
x
,
y
+
1
)
2
g_x(x,y) = \frac{L(x+1,y)-L(x,y)+L(x+1,y+1)-L(x,y+1)}{2}
gx(x,y)=2L(x+1,y)−L(x,y)+L(x+1,y+1)−L(x,y+1)
g
y
(
x
,
y
)
=
L
(
x
,
y
+
1
)
−
L
(
x
,
y
)
+
L
(
x
+
1
,
y
+
1
)
−
L
(
x
+
1
,
y
)
2
g_y(x,y) = \frac{L(x,y+1)-L(x,y)+L(x+1,y+1)-L(x+1,y)}{2}
gy(x,y)=2L(x,y+1)−L(x,y)+L(x+1,y+1)−L(x+1,y)
g
(
x
,
y
)
=
[
g
x
(
x
,
y
)
]
2
+
[
g
y
(
x
,
y
)
]
2
g(x,y) = \sqrt{[g_x(x,y)]^2+[g_y(x,y)]^2}
g(x,y)=[gx(x,y)]2+[gy(x,y)]2
θ
(
x
,
y
)
=
a
r
c
t
a
n
g
x
(
x
,
y
)
−
g
y
(
x
,
y
)
\theta(x,y) = arctan{\frac{g_x(x,y)}{-g_y(x,y)}}
θ(x,y)=arctan−gy(x,y)gx(x,y) 每个特征点可以得到三个信息*(x,y,m,
θ
\theta
θ),*即位置,尺度和方向。
梯度值为非负数,而角度范围为360°
箭头的大小和方向为梯度大小*m(x,y)*和梯度角
θ
(
x
,
y
)
\theta(x,y)
θ(x,y)
3.2 、NFA(误检线段数量)
定义一张尺寸为NxN个像素的图像,A为一段线段,其中n 为 A 的线段长度,像素值;k为 A 上与A方向一致的点的数目
N
F
A
(
n
,
k
)
=
N
4
⋅
∑
i
=
k
n
(
n
i
)
p
i
(
1
−
p
)
n
−
i
NFA(n,k) = N^4 ·\sum_{i=k}^n \binom{n}{i} p^i (1-p)^ {n-i}
NFA(n,k)=N4⋅i=k∑n(in)pi(1−p)n−i
其中
N
4
\N^4
N4 为NxN图像潜在线段的数量,因为图像有NxN个像素点,而两个点确定一个线段,共
N
2
N^2
N2个点,因此共有
N
4
N^4
N4条可能的线段
重新把NFA公式列一下
N
F
A
(
n
,
k
)
=
N
4
⋅
∑
i
=
k
n
(
n
i
)
p
i
(
1
−
p
)
n
−
i
NFA(n,k) = N^4 ·\sum_{i=k}^n \binom{n}{i} p^i (1-p)^ {n-i}
NFA(n,k)=N4⋅i=k∑n(in)pi(1−p)n−i 且有NFA(n,k)<=
ε
\varepsilon
ε,实际上一般
ε
\varepsilon
ε取1
线段拟合中的Minimum line length的选取
对于过短的线段(即首末像素的距离长度小于一定值),可以直接过滤掉
之前提到NFA(n,k)<= 1来保证像素和线段的方向一致。要使得最小线长有效,必有k = n,得到
N
F
A
(
n
,
n
)
=
N
4
⋅
P
4
≤
1
NFA(n,n) = N^4·P^4 \leq 1
NFA(n,n)=N4⋅P4≤1
移项可得
n
≤
−
4
l
o
g
(
N
)
l
o
g
(
p
)
n \leq \frac{-4log(N)}{log(p)}
n≤log(p)−4log(N),其中p = 0.125。对于一个512x512的图像,最小线段长应为12像素