二值图像中直线拟合误差与直线方向的关系

第 19 卷 第 5 期 2 0 0 6 年 1 0 月 模式识别与人工智能P R & A l V o l . 1 9 O e t N o . 5 2 0 0 6 二值图像中直线拟合误差与直线方向的关系 ‘ 刘 阳成 ‘,“ 朱 枫 , (中国科学院沈阳 自动化研究所 沈 阳 1 10 0 1 6) , (中国科学院研究生院 北京 1 0 0 0 8 0 ) 摘 要 主要从空间量化误差的角度分析直线方向与拟合误差的关系 . 首先介绍直线的拟合方法 , 然后定义敏感 距离这一度量图像中的直线对移动敏感性的概念 . 由此 出发讨论不同斜率的直线对直线平移的敏感程 度 , 给出敏 感移动距离的表 达式及证明 . 对各种直线拟合结果进行实验统计 , 结果表明拟合误差与敏感距离有着密切 的联系 . 基于直线拟合时方向误差远小于截距误差这一结果 , 在 已知直线斜率以及直线像素点的前提下 , 提出一种新 的估 计截距的方 法 , 实验结果表 明本文方法更优越 . 关键词 直线拟合 , 边缘定位 , 量化误差 , 误差分析 , 检测精度 中图法分类号 T P 202 R e l a t i o n b e t w e e n L i n e F i t t i n g E r r o r a n d D i r e c t i o n o f t h e L i n e i n B i n a r y Im a g e L IU Y a n g 一 C h e n g l ’ 2 , Z H U F e n g ‘ ( S h e n 夕a n g I n s t i r u t e o f A u t o m a t i o n , C h i n e s e A e a d e m 夕 o f S c i e n c e 、 , S h e n g 夕a n g 1 1 0 0 1 6 ) (G r a d u a t e S c h o o l , C h i n e s e A c a d e m 夕 o f S c i e , , c e s , B e i少i n g 1 0 0 0 8 0 ) A B ST R A C T T h e q u a n t i z a t i o n e r r o r p l a y s a n im p o r t a n t r o l e i n t h e f i e l d o f im a g e p r o e e s s i n g a n d e o m p u t e r v i s i o n . T h e r e l a t io n b e t w e e n t h e e r r o r o f l i n e f i t t i n g a n d t h e l i n e e h a r a e t e r s , e s p e e ia l l y t h e s l o p e o f t h e s t r a i g h t l i n e s , 15 m a i n l y a n a l y z e d . A f t e r a s im p le in t r o d u e t i o n o f t h e l in e fi t t i雌 , t h e d e f i n i t i o n o f t h e s e n s i t i v e s p a e e o f s t r a i g h t l i n e s 15 g iv e n , a n d it s e x p r e s s i o n u n d e r d if f e r e n t e o n d i t i o n s 15 p r e s e n t e d a n d p r o v e d . T h e e m u l a t i o n a l e x p e r im e n t s s u g g e s t t h e r e 15 a e l o s e r e l a t i o n b e t w e e n t h e s e n s i t i v e s p a e e a n d t h e e r r o r o f fi t t i n g r e s u lt s 二 T h e e r r o r o f in t e r e e p t 15 e a r e f u l ly r e s e a r e h e d a s t h e e r r o r o f s l o p e 15 m u e h l e s s t h a n t h a t o f i n t e r e e p t . A m e t h o d t o e v a l u a t e in t e r e e p t 15 P r e s e n t e d . T h e e x p e r im e n t a l r e s u l t s h o w s t h e p r o p o s e d m e t h o d o u t p e r f o r m s t h e t r a d i t i o n a l o n e . K e y W o r d s L in e F i t t i n g , E d g e l刀e a t io n , Q u a n t i z a t i o n E r r o r , E r r o r A n a ly s i s , De t e e t io n A e e u r a e y , 国家 8 6 3 计划资助项 目 ( N o . 2 0 0 2A A 4 0 1 0 0 1 一4 A ) 收稿 日期 : 2 0 0 5 一0 1 一0 4 ; 修回日期 : 2 0 0 5 一0 5 一1 9 作者简介 刘阳成 , 男 , 1 9 8。年生 , 硕士研究生 , 主要研究方向为 图像处理 、视觉计算 . E 一 m ail : l iu yc h @ s ia . cn . 朱枫 , 男 , 1 9 6 2年生 , 研究员 , 博士生导师 , 主要研究方向为机器人视觉 、 图像处理 . 5 期 刘 阳成 等 :二值图像中直线拟合误差与直线方向的关系 1 引 言 计算机视觉 、三维重建 、精密检测等领域的前期 工作都要涉及到图像处理 , 图像中的基元可以是点 , 直线 , 二次 曲线等〔’口. 直线作为特征元要 比其它特征 元更容易 、更准确地检测和匹配 [2] . (空间 )量化误差 在数字图像处理 中是不可避免的 , 因此量化误差在 计算机视觉等领域 中占有 十分重要 的地位胳 5习. B. K a m g盯一P a r s i 提出一种分析算法误差的方法川 , C. C . Y a n g 〔5一 6〕等人分析图像中线段长度度量的误差 . 直线拟合的研究大 多集 中在 噪声 图像 中的直线 拟 合 , 去除奇 异点 , 并 且 取得 不少 成果 . N . Ki ry at i , A . M . B r u e k s t e i n 与 H . 衡 id a a , 12 . R a d o u a n e 分 别 提出 自己的鲁棒直线拟合方法仁7一g J . 边缘检测得到的结果可 以是离散的边缘点 (如 边缘检 测算 子 ) , 也 可 以直 接得 到边界 曲线 (例 如 H ou g h 变换等 ) . 在标定 、 三维测量 、 精密检测等实 际应用中获取图像 中直线 的精确方程非常重要 . 但 即使用同一种拟合 方法 , 不同直线 的拟合精 度也不 相同 . 前人对量化误差 以及直线拟合均有不少研究 , 但就我们所知把二者结合起来研究的较少 , 而研究 拟合精度高低与直线类型 的关系的则基本没有 . 本 文讨论的内容是关 于拟合误差 的分析 , 文中分析直 线的拟合误差与直线 方向的关系 , 这有利于研究直 线方向对边缘检测精度的影响 , 进而指导图像处理 、 摄像机标定 、三维测量 、精密检测等实际应用 . 论推导以及仿真实验时可以仅考虑斜率 k (0 镇 k 镇 1) 的情况 . 直线的检测结果与图像的分辨率 有关 , 仿真图像的分辨率为 5 12 只 5 1 2 . 3 直线对移动的敏感程度 3 . 1 敏感距离的概念 当图像分辨率固定时 , 直线沿垂直于直线 的方 向做平移运动 , 运动距离很小时在数字 图像 中无法 体现 , 只有足够的运动距离才能够引起 图像 中表征 直线的像素发生变化 . 定义 1 图像中直线沿垂直于直线的方 向做平 移运动 , 能够引起图像像素变化 的最小距离 d 的上 界定义为具有该斜率直线的敏感距离 . 3 . 2 敏感距离的表达式及证明 由敏感距离 的定义很容易知道 , 水平直线和斜 率为 1 的直线敏感距离分别为 1 和 了之/ 2 . 定理 1 斜率为 m / n( m < n , 饥与 n 互质 ) 的直 线 , 它的敏感距离为 m i· ( ,一 / · ,一“一 不片丽 , 其 中 , 0 为斜率是 m /n 的直线与 二 轴的夹角 , h 、w 均 为整数 , h 一 ~ /n > O , h 毛 ,n, w < n. 2 直线的拟合 口口口口口口口 曰曰曰 曰曰日日日日 } } } ...吕吕口口门门门门曰曰曰曰曰曰曰 门门口口口口曰曰曰曰 }}}口口口口口口门门曰曰曰曰曰曰日日日日日 }}}}}}}门门门门门 口口曰曰 丈川川口口牙牙牙牙 曰曰刁刁刁刁 口口州州州厂川川门门厂节节l——厂一、、占补补「一 ‘‘乙口口「一节节广,, 广一 )))「节门门二二二二二二〔二二二〕〕〕!一一{{{厂一一厂下下仗 尸尸贬三三巨二二〔二二二巨二二厂门门匡口口二二二巨二二二二二二口口「二二二洲洲洲洲 习扩、、{{{ 口口口口口 曰曰口口口口口口口 口口口口口口口口口口口习习习 口口口口口口习习习 口口口口 直线在图像 中的像素点是抽样后经 四舍五入量 化而形成的 , 为论迷方便把直线所在坐标系 的单位 取作一个像素的大小 . 由于量化误差 , 像素中心点常 常不是准确分布在一条直线上 , 而是分布在直线的 附近 . 这就需要 由像素坐标拟合出直线的方程 , 应用 函数最佳平方逼近 , 由离散点集 {尸 } 可以拟合直线 方程 . 常用的方法有两种 :按直线斜率 的绝对值与 1 的大小比较 , 分别取 y 、 x 方向的残差平方和使其最 小 ;取离散点到拟合直线 的距离 (平方 )之和使其最 小 . 这两种方法实际上是分别对不同的 目标 函数进 行优化 , 从而求 出对应的拟合直线方程 , 本质上都是 最小二乘法 . 经过实 验发现本文提 出的结论不依赖 于某一种方法 . 斜率 为负的情况与斜率为正的情况 类似 , 由于第一种拟合方法的对称性 , 因此在进行理 图 1 斜率为 m /n 的直线量化结果 F i g . 1 Q u a n t iz a t io n r e s u l t o f l in e w i t h s l o p o f m / n 证明 如图 1 所示 , 直线上采样点的横坐标依 次记为 二。 , 二 ; , 二 : , … (均 为整数 ) , 纵 坐标依 次记 为 y 。 , y , , y : , … (未经量化 ) . 斜率为 m /n , 故 y , 的小数 部分呈现 出周期性 , 周 期为 , , . 直线 向上移动过程 中 , 每当经过纵坐标小数部分为 0 . 5 的采样点 (横坐 标为整数 ) 时量化结果就发生一次变化 . 根据敏感 距离定义 , 仅需考虑两次变化直线 移动的距离 . 设 y 。 小数部分为 。. 5 , y l , y Z , … , y 二 , 中小数部分小于 。. 5 且最接近 0 . 5 的点纵坐标设 为 丸. , 其整数部分 与 y 。整数部分相差 h , 则 h 、二为使得 h 一~ /n 取得最小 正 数 的 整 数 , 故 敏 感 距 离 d 一 m in( h 一 ~ /n ) co so . 下面证明 m in( h 一 ~ / n) 一 1 /n , 该问 模式识别与人工智能 1 9 卷 题等价于下述命题 : n , m 为互质正整数 , m < n , 结论 是存在整数 h 、w 使得 n h 一 ~ 一 1 . 证明如下 : 注意到 n , Z n , 3 n , … , (m 一 1) n 这 m 一 1个数都 不能整除 m , 那么它们除以 m 的余数必然各不相同 , 分别为 1 , 2 , 3 , … , m 一 1 . 因为如果有两个数除以 m 余数相同 , 它们 的差就能被 m 整除 . 但这个差仍然 是这 m 一 1 个数之一 , 矛盾 . 所 以这 m 一 1 个数有一 个除以 m 余 1 ,命题成立 . 由于 m < n , 因此敏感距离主要取决于 n . 定理 1 说明 n 越大 , 直线对于平移越敏感 . 注意这是假设 图 像分辨率足够大的情况下 ,或者说图像宽度大于 n . 定理 2 斜率为无理数的直线若不考虑图像大 小限制 , 其敏感距离为任意小的正数 . 简证 设直线斜率为无理数 k . 由实变函数论 知无理数和有理数在数轴上是稠密分布 的 , 故对 于 任意 。 > o , 存在一个有理数 u ,满足 。 < u 一 k < 。. 设 u 一 h / 二 , h 、w 均为整数 , 也即必然存在整数 h 、 w , 使 h / w 一 k 为任意小 的正数 , 即 h 一 w k 为任意小 的正数 , 于是得证 . 3 . 3 实验结果 按照定理 1 计算斜率为有理数 (精度为 0 . 0 0 1) 的直线的敏感距 离 , 运行 结果如图 2 所示 . 斜率 为 m /n 的直线 , 当 n 较小时敏感距离较大 . 同一斜率的 直线束中截距不 同的直线其引起像素发生变化的最 小距离 d , 是不同的 , 敏感距离是 d : 的上界 . 定义直 线沿垂直直线方向移动一个像素宽度 的过程 中 峨 的平均值为平均敏感距离 . 图 3 为用各种斜率的平 行直线束仿 真平均 敏感距离与直线斜率 关系 的结 果 . 图 3 中毛刺的幅度要小于图 2 , 但分布规律与 图 2 一致 . O . 0 ‘ 4 拟合误差与直线的关系 直线的敏感距离越大 , 说明直线 (离散化 ) 对移 动越不敏感 , 拟合结果可能出现相对较大的误差 , 因 此直线的拟合误差与敏感距离有着密切 的联系 . 本 节仿真各种斜率直线与拟合误差的关系 . 原始直线 记为二 十妙 + c 一 O , 方 向系数经过归一化处理 , 即 矿 + 护 一 1 . 拟合三个 系数 的误差与直线斜率 的关 系分别表示于图 4 、 图 5 、 图 6 中 , 横轴 表示直线斜 率 , 由于每一斜率取值对应一组直线 , 因此纵轴表示 最坏情况下拟合系数 的误差 (以下如无特殊说明 , 误 差均指最坏情况 ) . 这些结果可以转换为误差与倾角 的关系 , 图 7 为拟合系数 。 的误差与直线倾角 的关 系 . 090八内z广0工r4, ,,”1 000000被口以旗场 0片岁摆劣豁咒絮湍罚挑岁 .0斜率 0 . 0 0 12 0 乃0 10 0 . 0 0 0 8 架。刀0 0 6 0 . 0 0 0 4 0 . 0 0 0 2图 2 敏感距离与直线斜率的关系 F ig . 2 R e la t io n b e t w e e n s e n s i t iv e d is t a n e e a nd s lo p e o f li n e 0炭瑞署甜甜能岌念六罚群. 0斜率 0 . 7 0 . 6 图 4 拟合系数 a 误差与直线斜率的关系 0 . 5 0 . 4 F ig . 4 R e la t io n b e t w e e n t h e s lo p e o f l in e a n d t h e f it t in g e r r o r o f e o e f f ie ie n t a 0 . 3 0 . 2 从实验结果 中可以得 出以下三点有用的结论 : ( 1 ) a 、 b 系数的误差量级要小于系数 ‘ 的误差量级 . ( 2) 拟合误差 与直线斜率的关系并不是连续 的 , 个 别斜率的直线检测会引起较大 的误差 , 图像处理时 应尽量避免这些情况 . ( 3) 误差 的峰值分布 与敏感 距离的峰值分布基本一致 , 这说 明直线 的拟合误差 与敏感距离有着密切的联系 . 成像直线 的斜率应尽 可能在毛刺较少的区域 , 或者说避开这些峰值 . 我们 褪留御彭坷除 0 · , { . , , { 1 . ! 2 1 { . { 卜 { 0’ 一自 l’ 山 ‘一 ll’ .山·L 卜 比‘ 一 ll. 川 ‘ 11 一 日 L 』 . 1 0 0 . 1 0 . 2 0 ‘ 1 0 4 n 气 n ‘ n , n o n n , n 斜率 图 3 平均敏感距离与直线斜率的关系 F ig . 3 R e la t io n b e t w e e n m e a n s e n s i t iv e d is t a n e e a n d s lo P e o f li n e 5 期 刘阳成 等 :二值图像中直线拟合误差与直线方向的关系 可 以根据实际应用中对精度的要求 , 合理选择观测 方向 , 使成像直线的斜率处于一个合适的区 间中 . 我 们的工作为进一步分析空间量化误差及拟合误差 的 度量和原因做 了初步的工作 , 并对精确检测时图像 中直线 的方向布置有一定的指导意义 . 5 已知直线斜率时拟合截距的误 差 绷 鹦 0 . 0 004 0 0 . 0 0 0 3 5 0 . 0 0 0 3 0 0 . 0 0 0 2 5 0 . 0 0 0 2 0 0 0 0 0 1 5 0 . 0 0 0 10 0 . D0 0 0 5 由于直线拟合的方向误差要远小于截距误差 , 因此截距误差成为考虑的主要对象 . 假设拟合直线 的方向完全准确 , 则误差可 由拟合直线和实际直线 的距离衡量 . 拟合截距 的方法有两种 . 传统方法是对每一个点分别求 出截距 b , 然后 对这些 b 求平均值作为拟合截距 . 设拟合截距 为 b’ , 则 o品岸材贵糕澎瑞羚羚湍箭{。斜率 b , 一 艺 ( y , 一 肠 , ) F j g . 5 F i g . 6 图 5 拟合系数 b 误差与直线斜率的关系 R e la t io n b e t w e e n t h e s lo p e o f lin e a n d t h e 王i t t in g e r r o r o f e o e f f ie ie n t b 绷 咚 0 . 3 5 0 . 3 0 0 . 2 5 0 . 2 0 0 . 15 0 . 1 0 0 . 0 5 0 0 0 . 1 0 2 0 3 0 . 4 0 5 0石 0 7 0名 0 .9 1 . 0 斜率 图 6 拟合系数 。误差与直线斜率的关系 R e la t i o n b e t w e e n t h e s lo p e o f lin e a n d t h e f i t t in g e r r o r o f e o e f f ie ie n t e 这种方法等价于优 化像 素点到拟合直线 的距 离之 和 . 我们提出的方法是通过限制 b 的取值范围然后 取均值 . 对于所有的 x ‘ , y : (量化后的结果 ) 均有 一 0 . 5 < y , 一赶 、一 b 镇 0 . 5 , 故 m a x { v , 一 kx 、一 0 . 5 } < 占 , ( 1 ) b 镇 m i n {夕‘一 赶 , + 0 . 5 圣, 由式 ( 1) 可以把 b 的取值限制在一个范围内 , 只要 b 取该范围内的值 , 那么拟合直线上 的点经过量化 以 后与已知像素点完全一样 . 因此这个范围的 b 的取 值都是合理的 , 取该区间的中点作为截距的估计值 . 这种方法针对量化特点考虑误差 , 利用全体像素坐 标信息对 b 的取值范 围做了最严格的限制 . 按照这 种方法仿真实验结果如图 8 所示 . 气„4,、†气乙0.住住住 绷咚如只藉嘱 绷 联 0 . 3 5 0 . 3 0 0 . 2 5 0 . 2 0 0 . 15 0 . 1 0 0 . 0 5 10 15 2 0 2 5 3 0 3 5 4 0 4 5 直线倾角 o匕 1 0 1 5 2 0 2 5 3 0 3 5 4 0 4 5 直线倾角 图 7 拟合系数 。 误差与直线倾角的关系 F i g . 7 R e la t io n b e t w e e n t h e o b l iq u i t y o f l in e a n d t h e f i t t in g e r r o r o f e o e f f ie ie n t ‘ 图 8 最大拟合误差 与直线倾角的关系 F ig . 8 R e la t io n b e t w e e n t h e o b liq u it y o f li n e a n d t h e m a x in u m f it t in g e r r o r 由实验结果可以看 出 , 在 已知直线斜率的情况 下 , 拟合直线与原直线的误差 (即拟合直线与原直线 的距离 )具有以下特点 : 直线的倾角小于 26 “时截距 的误差最大值都 小于 0 . 06 ;倾 角小于 26 “时截距误 6 8 4 模式识别与人工智能 1 9 卷 差均值都小于 0 . 02 ; 误差的方差普遍很小 . 当我们 已知直线的方向或拟合得到的直线方 向较准确 (或 在误差要求内 ) 时 , 若截距精度还需要进一步提高则 应设法控制 图像 中的直线倾角小于 2 60 , 这对 于截 距 的估计较有利 . 该种方法与传统方法 的比较见图 9 , 纵轴表示传统方法与本方法分别得到的误差最大 值相减的结果 , 可以看出相减结果均大于 0 . 这表明 传统方法的误差大于本文提出的方法 , 本文的方法 优于传统方法 . 并提出一种更好的拟合截距的方法 . 这些理论分 析 和实验结果 , 为进一步寻求提高直线检测精度 的途 径打下基础 ,提供新的思路 , 对精确检测直线时直线 方向的布置 、选择也具有一定的指导意义 . 参 考 文 献 ”、”n2勺山 : O 0 一、一011, .1 : 0 0 0 . 0 5 刊期翎瑙状崛如辙 0 0 5 10 1 5 2 0 2 5 3 0 3 5 4 0 4 5 直线倾角 F i g . 9 图 9 C o m 传统方法与本文方法拟合误差的比较 p a r i s o n o f f i t t in g e r r o f b e t w e e n t h e t r a d i t i o n a l m e t h o d a n d t h e p r o p o s e d m e t h o d 6 结 束 语 本文主要从空间量化误差的角度分析直线方向 与检测误差的关系 , 定义敏感移动距离这一度量图 像 中的直线对移动敏感性 的概念 , 分情况讨论不同 斜率的直线对直线平移的敏感程度 , 给出敏感移动 距离的表达式 , 并进行证明和仿真实验 . 基于直线拟 合时方向误差远小于截距误差这一结果 , 通过实验 分析已知直线斜率以及直线像素点的情况下 , 截距 拟合误差 的最大值 、均值 、方差与直线倾角的关系 , [ l ] M a S o n g d e , Z h a n g Zh e n g y o u . C o rn p u t e r V i s i o n . B e i j i n g , C h i - n a : S e i e n e e P r e s s , 19 9 8 : 7 2一 78 ( i n C h i n e s e ) ( 马颂德 , 张正友 . 计算机视觉 . 北京 : 科学出版社 , 1 9 9 8 : 7 2一 78) 仁2〕M a S D , W e i G Q , H u a n g J F . S e g m e n t B a s e d C a rn e r a C a lib r a - t i o n . Jo u r n a l o f C o m p u t e r s c i e n e e & T e e h n o lo g y , 1 9 , 3 . 8 ( l ) : 1 1 一 16 仁3」S t e v e n D B , T h o m a s 5 H . E r r o r A n a ly s i s i n S t e r e o D e t e r m i n a - t io n o f 3 D P o i n t . I E E E T r a n s o n P a t t e r n A n a l y s i s a n d M a e h i n e I n t e l ig e n e e , 19 8 7 , 9 ( 6 ) : 7 5 2 一 7 6 5 仁4 j K a m g a r 一 P a r s i B . E v a l u a t i o n o f Q u a n t i z a t io n E r r o r i n C o m p u t e r V i s i o n . I E E E T r a n s o n P a t t e r n A n a ly s i s a n d M a e h i n e I n t e l i- g e n e e , 19 8 9 , 1 1 ( 9 ) : 9 2 9 一 94 0 [ 5习Y a n g C C , M a r e f a t M M , C i a r a l l o F W . E r r o r A n a l y s i s a n d P l a n n i n g A e e u r a e y fo r D im e n s i o n a l M e a s u r e rn e n t i n A e t i v e V i - 5 io n In s p e e t io n . IE E E T r a n s o n R o b o t i e s a n d A u t o m a t i o n , 19 9 8 , 1 4 ( 3 ) : 4 7 6 一 48 7 仁6〕Y a n g C C , M a r e f a t M M , C i a r a llo F w . A n a ly s i s o f E r r o r S I n D im e n s i o n a l I n s Pe e t i o n B a s e d o n A e t i v e V i s i o n . P r o e o f t h e S P I E , 1 9 9 6 , 2 3 5 4 : 9 6一 10 4 [ 7〕K i r y a t i N , B r u e k s t e i n A M . Wh a t ’ 5 i n a S e t o f P o i n t s ? IE E E T r a n s o n P a t t e r n A n a l y s i s a n d M a e h i n e I n t e l ig e n e e , 1 9 9 2 , 14 ( 4 ) : 4 9 6一 5 0 0 [ 8〕q id a a H , R a d o u a n e L . R o b u s t L i n e F i t t i n g i n a N o i s y Im a g e b y t h e M e t h o d o f Mo m e n t s . I E E E T r a n s o n P a t t e r n A n a l y s i s a n d M a e h i n e In t e l lig e n e e , 19 9 9 , 2 1 ( 1 1 ) : 12 16 一1 2 2 3 仁9」K i r y a t i N , B r u e k s t e i n A M . C o m m e n t s o n “ R o b u s t I i n e F i t t i n g i n a N o i s y I m a g e b y t h e Me t h o d o f M o m e n t s , , . IE E E T r a n s o n P a t r e r n A n a ly s i s a n d M a e h i n e I n t e l ig e n e e , 2 0 0 0 , 2 2 ( 1 2 ) : 1 3 4 0 - 1 3 4 1