Homepage: Renjie Chen (中科大陈仁杰教授).pdf

中国图象图形学报 第１５卷第３期 Ｖ０１．１５，Ｎｏ．３ Ｊｏｕｒｎａｌ ｏｆ Ｉｍａｇｅ ａｎｄ Ｇｒａｐｈｉｃｓ ２０１０年３月 Ｍａｒ．２０１０ 图像主特征直线的检测算法 刘利刚 陈仁杰 董光昌 （浙江大学数学系计算机图像图形研究所，杭州３１００２７） 摘 要直线特征的检测是计算机视觉与图像处理的基本任务之一。主特征直线是图像中最显著而且被人们最 为关心的一些直线。本文提出了从图像中自动检测主特征直线的算法。首先利用图像分割算法分析得到图像的 特征边缘，然后用短线段逼近这些边缘像素，接着用动态聚类算法对这些线段进行聚类，并用直线拟合聚类中的线 段得到所有可能存在的直线，最后根据直线有效性度量找到其中有效性最高的直线就是主特征直线。最后本文给 出了主特征直线在图像自动修复和自动美学构图中的应用实例。 关键词 主特征直线直线检测线段聚类拟合有效性 中图法分类号：ＴＰ３９１．４１ 文献标志码：Ａ 文章编号：１００６－８９６１（２０１０）０３．４０３．０６ Ｄｅｔｅｃｔｉｏｎ ｏｆ Ｐｒｉｎｃｉｐａｌ Ｌｉｎｅｓ ｉｎ Ｉｍａｇｅｓ ＣＨＥＮ Ｒｅｎｊｉｅ，ＬＩＵ Ｌｉｇａｎｇ，ＤＯＮＧ Ｇｕａｎｇｃｈａｎｇ （Ｉｎｓｔｉｔｕｔｅ ｏｆＣｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ ａｎｄ Ｉｍａｇｅ Ｐｒｏｃｅ＂ｉｎｇ，Ｚｈｅｊｉａｎｇ Ｕｎｉ钾ｒｓｉｔｙ，Ｈａｎｇｚｈｏｕ ３１００２７） Ａｂｓｔｒａｃｔ Ｔｈｅ ｄｅｔｅｃｔｉｏｎ ｏｆ ｌｉｎｅａｒ ｆｅａｔｕｒｅ ｉｓ ｏｎｅ ｏｆ ｔｈｅ ｍｏｓｔ ｆｕｎｄａｍｅｎｔａｌ ｔａｓｋｓ ｉｎ ｃｏｍｐｕｔｅｒ ｖｉｓｉｏｎ ａｎｄ ｉｍａｇｅ ｐｒｏｃｅｓｓｉｎｇ． Ｐｒｉｎｃｉｐａｌ ｌｉｎｅｓ ａｒｅ ｔｈｅ ｍｏｓｔ ｖｉｓｕａｌｌｙ ｐｒｏｍｉｎｅｎｔ ｌｉｎｅｓ ｉｎ ｔｈｅ ｉｍａｇｅｓ ｔｈａｔ ｐｅｏｐｌｅ ｍｏｓｔｌｙ ｃａｒｅ ｆｏｒ．Ｔｈｉｓ ｐａｐｅｒ ｐｒｅｓｅｎｔｓ ａｌｇｏｒｉｔｈｍ ｆｏｒ ａｕｔｏｍａｔｉｃ ｄｅｔｅｃｔｉｏｎ ｏｆ ｔｈｅ ｐｒｉｎｃｉｐａｌ ｌｉｎｅｓ ｉｎ ｄｉｇｉｔａｌ ｉｍａｇｅｓ．Ｔｈｅ ｆｅａｔｕｒｅ ｅｄｇｅ ｐｉｘｅｌｓ ｉｍａｇｅ ｗｉｔｈ ａｌｌ ｉｍａｇｅ ｓｅｇｍｅｎｔａｔｉｏｎ ｔｅｃｈｎｉｑｕｅ．Ｔｈｅｎ ｔｈｅｙ ｃｌｕｓｔｅｒｅｄ ｕｓｉｎｇ ８０ｍｅ ｓｉｍｉｌａｒｉｔｙ ｍｅｔｒｉｃ．Ｅａｃｈ ｃｌｕｓｔｅｒ ｏｆ ｐｒｉｎｃｉｐａｌ ｌｉｎｅｓ ａｒｅ ｄｅｔｅｒｍｉｎｅｄ ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｖａｌｉｄｉｔｙ ａｒｅ ａｐｐｒｏｘｉｍａｔｅｄ ｗｉｔｈ ｓｈｏｒｔ ｌｉｎｅ ａｒｅ ａｎ ｎｏｖｅｌ ｆｎ＇ｓｔ ｄｅｔｅｃｔｅｄ ｆｒｏｍ ｔｈｅ ｓｅｇｍｅｎｔｓ，ｗｈｉｃｈ ｓｅｇｍｅｎｔｓ ｉｓ ｆｉｔｔｅｄ ｗｉ山ａ ｓｔｒａＪＩｓｈｔ ｌｉｎｅ ｉｎ ａ ａｒｅ ｆｕｒｔｈｅｒ ｉｔｅｒａｔｉｖｅ ｍａｎｎｅｒ．Ｔｈｅ ｍｅａｓｕｒｅｍｅｎｔ．Ｗｅ ｄｅｍｏｎｓｔｒａｔｅ ｔｗｏ ｐｒａｃｔｉｃａｌ ａｐｐｌｉｃａｔｉｏｎｓ ｉｎｃｌｕｄｉｎｇ ａｕｔｏｍａｔｉｃ ｉｍａｇｅ ｒｅｃｏｖｅｒｉｎｇ ａｎｄ ａｕｔｏｍａｔｉｃ ｐｈｏｔｏ ｃｏｍｐｏｓｉｔｉｏｎ ｔｏ ｓｈｏｗ ｔｈｅ ａｐｐｌｉｃａｂｉｌｉｔｙ ｏｆ ｔｈｅ ｐｒｉｎｃｉｐａｌ ｌｉｎｅｓ ｉｎ ｉｍａｇｅ ｐｒｏｃｅｓｓｉｎｇ． Ｋｅｙｗｏｒｄｓ ｐｒｉｎｃｉｐａｌ ｌｉｎｅ，ｌｉｎｅ ｄｅｔｅｃｔｉｏｎ，ｓｅｇｍｅｎｔ，ｃｌｕｓｔｅｒｉｎｇ，ｆｉｔｔｉｎｇ，ｖａｌｉｄｉｔｙ 线之前的对偶性，把图像空间中直线检测问题转换 ０ 引 言 为参数空间中点的检测问题，通过在参数空间进行 简单的累加统计完成检测任务。该算法的优点是抗 直线检测是计算机视觉和模式识别中最重要的 噪能力强，能在低信噪比下检测出直线，其缺点是由 任务之一。直线是图像的重要特征，直线特征提取 于是全搜索，计算量和存储量都很大。多年来研究 方法的研究对图像的理解、模式识别有重要的意义。 者致力于发展各种有效方法解决这些问题。其中自 例如可以用于自动识别图像中直线特征明显的人造 适应Ｈｏｕｇｈ变换雎】、快速Ｈｏｕｇｈ变换旧１、多分辨率 目标（如河流、道路、桥梁等）。 Ｈｏｕｇｈ变换Ｈ巧１等利用多分辨率方法把图像分成一 直线检测的方法有很多，Ｈｏｕｇｈ变换是其中最 系列独立的子图像分别进行Ｈｏｕｇｈ变换从而实现 经典的算法。Ｈｏｕｇｈ变换…的基本原理是利用点和 有效加速。而概率Ｈｏｕｇｈ变换峥。、随机Ｈｏｕｇｈ变 基金项目：国家自然科学基金委员会与微软亚洲研究院联合项目（６０７７６７９９） 收稿日期：２００８—１０－０６；改回日期：２００９．０１．１２ 第一作者简介：陈仁杰（１９８３一），男。浙江大学数学系计算机图像图形研究所博士研究生。主要研究领域为计算机图形学、数字几 何处理。Ｅ—ｍａｉｌ：ｒｅｎｊｉｅ＠ｚｊｕ．ｅｄｕ．ｃｎ 通讯作者：刘利刚。Ｅ－ｍａｉｌ：ｆｉｇａｎｇｆｉｕ＠ｚｊＩＬ ｅｄｕ．ｃｎ 万方数据 中国图象图形学报 第１５卷 换¨。８１等则在尽可能保证和标准Ｈｏｕｇｈ变换得到相 由于图像中可能存在的直线条数是不确定的， 同结果的前提下对原始边缘图像进行随机抽样从而 因此采用动态聚类方法，并且不固定聚类个数，而由 减少计算量实现加速。文献［９］则通过改进Ｈｏｕｇｈ 聚类过程来最终确定。基本检测算法如下： 变换的投票算法，对近似共线的点进行加权投票，实 １）随机选择一条线段，作为第一个聚类 现实时而精确的直线检测。另外一类直线检测的方 ２）对每条线段，计算其到所有聚类中心的距 法是模糊聚类算法。基于聚类的直线检测方法近年 离，判断这些距离的最小值是否小于事先给定的阈 来发展很快。模糊聚类传统上用于检测紧的或具有 值，若是则将其归类至相应的聚类，否则新建一个只 球对称的形状，通过改变聚类元素并选择合适的相似 包含它的聚类。 ３）对每个聚类，重新计算聚类中心。若某个聚 性度量，这类方法可用于检测其他形状。在文献 ［１０］，［１１］中，对所有边界像素直接应用聚类过程得 类不包含任何线段则删除此聚类。 ４）判断结果是否收敛，若聚类个数或某个聚类 到狭长的聚类，然后合并共线的相邻聚类并用直线拟 合整个聚类就得到了目标直线。文献［１２］“１４］则 内部成员有变化，则返回步骤１），否则退出。 在点聚类算法中，聚类中心一般取为聚类内所 先从图像中分析得到边缘线段，然后重复寻找共线的 两条线段合并成一条长线段，从而得到目标直线。 有元素的平均值，因此数据元素和聚类中心均为低 现有的直线检测算法试图检测图像中所有直 维或高维空间中的点，故元素和聚类中心的距离可 线，而不管直线的重要程度，然而许多实际应用中可 直接定义为空间中两点之间距离。然而在线段聚类 能只需要主特征直线，即图像中最重要的一条或几条 中，数据元素为线段，而聚类中心为目标直线。故需 直线。为此，提出了图像中主特征直线的检测算法， 要对线段到聚类中心的距离进行合理的定义，并给 并将此算法用于图像的自动修复和自动美学构图。 出相应计算聚类中心的方法。 最简单的，可以定义线段和直线的距离为线段 １ 基于线段聚类的直线检测算法 中点到直线的距离，或者为两者之间夹角。明显这 两种定义都有缺陷，并且两者数量上无法统一，难以 和传统的直线检测算法一样，先从图像中检测 对两者进行适当组合得到较合理的定义。 边缘像素，然后从这些边缘像素中分析可能存在的 定义线段和直线的距离为线段上所有点到直线 直线。传统的边缘检测算法，例如Ｃａｎｎｙ算子¨引， 距离之和。即给定线段ＡＢ：Ｐ（ｔ）＝（茄（ｔ），Ｙ（ｔ））， 不能很好地找到所需要的边界点。虽然可以调整不 ０≤ｔ≤Ｉ和直线Ｌ：ｘｓｉｎ ０＋ｙｃｏｓ ０＋ｃ＝０，则 同参数得到不同的检测结果，但是如图ｌ所示，不同 ｒＩ ｄ（ＡＢ，Ｌ）＝Ｉ ｄ（ｐ（ｔ），￡）ｄｔ 或者导致一些构成目标直线的重要边缘丢失。 （１） Ｊｕ 参数或者导致检测出过多与目标直线无关的边缘， 式中，ｄ（ｐ（ｔ），Ｌ）表示点Ｐ（ｔ）到直线工的距离。例 注意到图像分割算法提供了很好的图像边缘， 如，在图３中，红色线段和蓝色直线之间距离为灰色 如图２所示。因此以图像分割后不同块之间的边界 区域面积。设线段两端点Ａ，Ｂ坐标分别为（菇。，，，。）、 像素为初始条件来进行直线检测，采用基于图的分 （茗２，Ｙ２），则 割算法¨引。当然图像分割结果也和参数选取有关 菇（ｔ）＝菇ｌ＋（菇２一茗１）ｔ 系，采用比较保守的参数，使得尽可能找到所有和目 Ｙ（ｔ）＝，，ｉ＋（，，２一ＹＩ）ｔ 标直线相关的边缘像素。得到这些边缘像素后，可 以直接对这些边缘点进行聚类，然而由于边缘像素 故有 ａ（ｐ（ｔ），￡）＝Ｉ菇（ｔ）ｓｉｎ ０＋），（１）ＣＯＳ ０＋Ｃ Ｉ＝ 很可能比较多，所以点聚类过程会很慢，不易收敛。 Ｊ（茗２一算１）ｔｓｉｎ ０＋（Ｙ２－ｙ１）ｔｃｏｓ ０＋ 注意到这些边界像素都是连续的，并且有很多相邻 名ｌｓｉｎ ０＋，，ＩＣＯＳ ０＋ｃ Ｉ 像素位于同一直线，因此在直线检测前，先用短线段 经过简单计算可得 Ｉ仰Ｊ（１ ｄ。Ｉ＋Ｉ ｄ：Ｉ） 近似这些边缘像素，近似结果如图２（ｂ）所示，从图 中可以看出图像分割算法确实提供了更好更相关的 边缘。得到短线段后，采用线段聚类的方法从所有 这些短线段中分析可能存在的直线。 万方数据 （２） ＿ ２ ａ（ＡＳ，Ｌ）＝ Ｉ（ｄ２＋透） 玎啊丁了而 ＡＢ ｄｌ·ｄ２≥０ ｄｌ·ｄ２＜０ 第３期 陈仁杰等：图像主特征直线的检测算法 图１对同一图像用不同参数进行Ｃａｎｎｙ边缘检测‘“１的结果 Ｆｉｇ．１ Ａｐｐｌｙ ｔｈｅ ｃａｎｎｙ ｅｄｇｅ ｄｅｔｅｃｔｏｒ ｔｏ ｔｈｅ ８ａｎｌｅ ｉｍａｇｅ ｗｉｔｈ ｄｉｆｆｅｒｅｎｔ ｐａｒａｍｅｔｅｒｓ 图２从图像中检测直线 Ｆｉｇ．２ Ｄｅｔｅｃｔｉｎｇ ｌｉｎｅｓ ｆｒｏｍ ｉｍａｇｅ 其中，Ａ。曰；：ｐ；（ｔ）＝（菇；（ｔ），Ｙ；（ｔ））为聚类内第ｉ条线 段，而三为目标拟合直线。然而根据式（１）和式 （２），上述能量函数不能关于０和ｔ直接求导，因而 难于优化。因此修改目标函数为 ．１ ｅｒｒ（Ｌ）＝∑ｆ。ｄ２（ｐ。（ｔ），Ｌ）ｄｔ Ｆｉｇ．３ Ｔｈｅ ｄｉｓｔａｎｃｅ ｂｅｔｗｅｅｎ ａ ｓｅｇｍｅｎｔ ａｎｄ ａ ｌｉｎｅ ｄｌ＝菇ｌｓｉｎ ０＋Ｙ１ＣＯＳ ０＋ｃ ｄ２＝Ｘ２ｓｉｎ ０＋，，２Ｃ０８ ０＋ｃ 可以看出只有当线段ＡＢ和直线Ｌ完全重合时，两 者之前距离ｄ（ＡＢ，Ｌ）才为０，因此上述定义是合理的。 在步骤２）中，需要比较当前线段到所有聚类中 心距离的最小值和给定阈值的大小，然后再进行归 类，这是因为采用变化的聚类个数，二开始聚类数为 １，若不进行比较直接聚类将导致所有线段被聚为一 类。这个阈值还会影响最终聚类个数，阈值越大则 聚类数越小。一般取此阈值为１０，这是因为图像中 相邻直线之前平均距离不小于此数值。 在步骤３）中，计算聚类中心也就是用直线拟合 聚类内所有线段的过程。拟合直线应满足该聚类内 （３） 根据ｅｒ４Ｌ）最小化条件，对式（３）关于０和ｔ求导可得： ０＝Ｋ１ ｓｉｎ２０＋Ｋ２ＣＯＳ２０＋Ｋ３ｓｉｎ ０ ＣＯＳ ０＋ ｃ（Ｋ４ｓｉｎ ０＋ＫｓＣＯＳ日） ０＝Ｌｌ ｓｉｎ ０一Ｌ２ＣＯＳ ０＋２ｃＬ３ （４） （５） 式中，Ｋ，…，毛和￡，，￡：，己，为关于聚类内线段端点坐 标的表达式，与０和ｔ均无关，故从上述两式容易计算 出０和ｔ，这样就完成了拟合过程。由于采用变化的聚 类个数，所以在迭代过程中有些聚类可能会不包含任 何线段，因此在步骤３）最后，将所有的空聚类删除。 聚类过程迭代结束，就得到了图像中的所有直 线，也就是所有聚类中心。例如在图２中，图２（ｃ） 中紫色直线就是对图２（ｂ）中线段进行聚类最后得 到的聚类中心，可以看出这些紫色直线绝大多数都 是图像上真实存在的直线。 所有线段到它的距离之和最小。因此，和从点集拟 合直线类似，通过最小化以下目标函数实现对线段 ２直线有效性度量 集合的拟合： ｅｒｒ（Ｌ）＝∑ｄ（Ａ…Ｂ工）＝∑ｆ。ｄ（ｐ；（ｆ），Ｌ）ｄｔ 万方数据 在很多实际应用中，事实上并不需要检测出图 像中所有直线。这些应用最关注的是主特征直线， 中国图象图形学报 第１５卷 即图像中最重要的一条或几条直线，然而现有的直 效性之前，将ｇｒａｄ（Ｌ），ｌｅｎ（￡），ｅｒｒ（￡）和ｌｅｎ２（￡）均 线检测算法未曾考虑此问题。为此，提出了直线的 归一化至［０，１］区间。根据所有直线的有效性 有效性度量，然后根据有效性确定主特征直线。从 ｖａｌ（￡），可以从中确定出主特征直线，即ｖａｌ（￡）最大 以下几个因素考虑检测到的直线的有效性。 的几条。但是由于一般图像中主特征直线的条数并 直线附近区域梯度变化。设直线附近区域梯度 不确定，所以给出一个经验阈值ｖａｌ。（本文实验图像 的平均值为ｇｒａｄ（Ｌ），则ｇｒａｄ（Ｌ）越大有效度越高。 均取２．５），根据ｖａｌ（Ｌ）是否大于ｖａｌ。判断其是否为 例如图４（ａ）为图１（ａ）的梯度图，可以看出图中橘 主特征直线。表１列出了图２（ｃ）中总体有效性最 色区域像素灰度值的平均值很大，因此红色直线极 高的四条直线的各有效因素得分。 有可能是主特征直线。 表１图２（ｃ）中直线有效性分数 直线的有效拟合长度。有效拟合长度是指用于 Ｔａｂ．１ Ｖａｌｉｄｉｔｙ 拟合当前直线的线段集合在直线上投影区间的长 ｍｅａｓｕｒｅｍｅｎｔ ｏｆ ｌｉｎｅｓ ｉｎ Ｆｉｇ．２（ｅ） 表示线段Ａ；召；在当前直线￡上的投影。显然ｌｅｎ（工） 越大，则直线有效性越高。如图４（ｂ）所示，紫色线 ｌｅｎ２ ｖａｌ Ｏ ９ Ｏ Ｏ ０ ２ ７ ●３ Ｏ ７ Ｏ １ ｌ ２ ６ Ｏ ２ Ｏ ７ Ｏ ６ ｌ ０ ５ ∞＂龆竹 Ｏ 孔拍巧¨ ２ １ Ｏ ２ Ｏ ３ Ｏ ２ 舛町坦两 直直直直 线线线线 ４ ｍ ｌｅｎ ｇｒａｄ 度，即ｌｅｎ（Ｌ）＝０ Ｕｐｒｏｊ（Ａ；Ｂ；，工）０，其中ｐｒｏｊ（Ａ；Ｂｉ，己） ｌ 螂咖咖咖 ２ ３ ｌ ９ ∞钳铂ｗ 段为蓝色线段在绿色拟合直线上的投影，显然直线 ①比②和③有效拟合长度更长，因此其有效性更高。 直线的拟合误差ｅｒｒ（Ｌ）。本文的线段聚类算法 ３ 实验结果 并不直接要求聚类内线段共线，因此有可能很多细 碎杂乱的短线段会聚成一类，但是实际上这些短线 为了验证新算法的性能，对大量图像进行了测 段并不属于同一条直线，例如图４（ｂ）中的直线②。 试。结果如图５（ｃ），图６和图７所示，其中彩色直 由于这些短线段和拟合直线之间夹角较大，由式 线为本文算法检测到的主特征直线，并按不同的有 （３）可知拟合误差一定比较大。因此ｅｒｒ（￡）越小， 效性进行着色，其中红、绿、蓝３条直线分别对应有 则有效性越高。 效性最高的３条，另外图６（ｂ）中白色像素为用短线 直线被图像画面所截长度ｌｅｎ２（Ｌ）。当直线特 段逼近图像分割边界的结果。从结果可以看出给出 别接近图像边框时，例如图４（ｂ）中的直线③在图像 的有效性度量标准基本符合人眼视觉观察，检测结 画砸内的长度特别短，因此其有效性很低。 果是可以接受的。 在图５中，还与传统Ｈｏｕｇｈ变换进行了对比，图 ５（ａ）和图５（ｂ）中直线分别为用Ｈｏｕｇｈ变换…和概 率Ｈｏｕｇｈ【６１变换检测得到的直线，同样分别用红、 绿、蓝３种颜色给Ｈｏｕｇｈ变换返回的前３条直线着 色。注意到图５（ａ）中最重要的３条直线都位于第２ 条主特征直线附近，而图５（ｂ）中第２条直线完全 不对应任何主特征直线。而本文算法正确检测出 Ｆｉｇ ４ 图４直线有效性度量 了两条主特征直线，并且有效度量了每条直线的 Ｔｈｅ ｖａｌｉｄｉｔｙ ｍｅａｓｕｒｅｍｅｎｔ ｏｆ ｌｉｎｅｓ 正确性。 在确定任意直线的有效性时，必须综合考虑以 从所有结果可以看出，本文算法对直线斜率和 上因素。在本文实验中，采用下式作为直线有效性 连续性没有特别要求，可以检测出任意角度的主特 度量标准 征直线。主特征直线的确定及其重要性和人的主观 ｖａｌ（Ｌ）＝ｆｉｌ×ｇｒａｄ（Ｌ）＋口２×ｌｅｎ（￡）一ｆｉ３× 感觉及具体应用有关。例如图７（ａ）中位于桥塔上 ｅｒｒ（Ｌ）＋口４×ｌｅｎ２（Ｌ） 的蓝色和紫色两条直线的有效性和本文使用的阈值 其中，口。，…，ｆｉ。均为正数。对于不同类型图像， ｖａｌ。非常接近，事实上也可以看成非主特征直线。 ｆｉｌ＇．一，口。可能稍有不同。根据对大量图像的实验结 而图７（ｂ）中旗杆所在直线由于有效拟合长度过短， 果，分别取口。＝２，口：＝２，口３＝２，口４＝１。在计算总有 所以被判断为非主特征直线，当然可以通过调整阈 万方数据 第３期 陈仁杰等：图像主特征直线的检测算法 值移口ｚ。使结果更符合实际需要。图７（ａ）和７（ｂ）中 感的应用可以在直线有效性度量中增加直线斜率因 地平线都不是最重要的主特征直线，对于地平线敏 素从而使结果更符合实际应用的需要。 图５图１（ａ）直线检测结果及比较 Ｆｉｇ．５ Ｔｈｅ ｃｏｍｐａｒｉｓｏｎ ｂｅｔｗｅｅｎ ｄｉｆｆｅｒｅｎｔ ｌｉｎｅ ｄｅｔｅｃｔｉｎｇ ａｐｐｒｏａｃｈｅｓ 图６第２个例子 Ｆｉｇ．６ Ａｎｏｔｈｅｒ ｒｅｓｕｌｔ ｏｆ ｐｒｉｎｃｉｐａｌ ｌｉｎｅ ｄｅｔｅｃｔｉｏｎ Ｆｉｇ．７ Ｍｏｒｅ ｒｅｓｕｌｔｓ ｏｆ ｐｒｉｎｃｉｐａｌ ｌｉｎｅ ｄｅｔｅｃｔｉｏｎ 图７更多检测结果 图像修复技术被广泛地用于重建旧照片和移 ４主特征直线的一些应用 除一些图片背景中不想要的物体。为了得到较好 的修复结果，需要指定关于待修复区域的结构特 主特征直线还可用于实现数码照片的自动构 征。例如在文献［１８］中，就是由用户手工指定一 图。直线是美学构图中最基本元素之一【１７ Ｊ，图像 些直线或曲线特征。利用本文算法，可以自动检 中的主特征直线往往位于画面的三分线或黄金分 测出主特征直线，从而使整个修复过程无须人工 割线附近。利用本文算法检测到主特征直线后， 交互自动完成。例如在图９中，图９（ｂ）为从原始 可以对原图进行裁剪来改变其在图像中的相对位 图片图９（ａ）中直接擦除南瓜得到的不完整图像， 置，从而使其更符合美学构图规则。例如在图８ 先对图９（ｂ）进行主特征直线检测，得到重要的直 （ｂ）中，紫色直线为本文算法检测到的主特征直 线结构，如图９（ｃ）中紫色直线所示，然后根据这些 线。为了便于比较，将裁剪结果放大至和原图相 直线结构应用文献［１８］给出的修复算法，得到最 同尺寸。 终修复结果图９（ｄ）。 万方数据 中国图象图形学报 ４０８ ［２】 第１５卷 Ｊ，Ｋｉｔｔｌｅｒ Ｊ．Ｔｈｅ ａｄａｐｔｉｖｅ Ｈｏｕｇｈ １ｌｌｉｎｇｗｏｒｔｈ Ｔｒａｎｓａｃｔｉｏｎｓ ｔｒａｎｓｆｏｒｍ［Ｊ］．ＩＥＥＥ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ，１９８７， ｏｎ ９（５）：６９０·６９８． ［３】 Ｆａｓｔ ＨｏｕｇｌＩ ｔｒａｎｓｆｏｒｍ：Ａ ｈｉｅｒ－ Ｗ，Ｌａｖｉｎ Ｍ Ａ，ＭａｓｔｅｒＲ Ｊ ｈ Ｌｉ Ｈ ａｒｃｈｉｃａｌ ａｐｐｒｏａｃｈ［Ｊ］．Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ。Ｇｒａｐｈｉｃｓ，ａｎｄ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ。１９８６。３６（２－３）：１３９－１６１． ［４］ Ａｔｉｑｕｚｚａｍａｎ Ｍ．Ｍｕｈｉｒｅｓｏｌｕｔｉｏｎ Ｈｏｕｇｈ ｏｆ 图８ 自动构图应用 Ａｐｐｌｉ。８ｔｉ。ｎ ｏｆ ８ｕ佃ｍ砒ｉ。ｉｍａｇｅ ｃ。ｍｐｏｓｉｔｉｏＩＩ Ｆｉｇ·８ ｄｅｔｅｃｔｉｎｇ ｐａｔｔｅｒｎｓ ｔｒａｎｓｆｏｒｍ－ｍｌ ｅｆｆｉｃｉｅｎｔ ｍｅｔｈｏｄ ｉｍａｇｅｓ［ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｉｎ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ，１９９２，１４（１１）：１０９０－１０９５． 【５］ Ｙｕｅ Ｄｏｎｇｘｕｅ，Ｈｕａｎｇ Ｘｉｎｓｈｅｎｇ．Ｍｅｔｈｏｄ ｏｆ ｌｉｎｅ ｄｅｔｅｃｔｉｏｎ ｉｍｐｒｏｖｅｄ ｍｕｌｔｉｒｅｓｏｈｉｔｉｏｎ Ｈｏｕｓｈ ｂｕｓｅｄ ０ｎ ｔｒａｎｓｆｏｒｍ［Ｊ］．Ｃｏｍｐｕｔｅｒ Ｓｉｍｕｈ— ｔｉｏｎ．２００６，２３（９）：７６—７９．［岳冬雪，黄新生．基于改进的多 分辨率Ｈｏｕｇｌｌ变换的赢线检测方法［Ｊ］．计算机仿真，２００６， ２３（９）：７６－７９．］ ［６］ Ｎ，Ｅｌｄａｒ Ｙ，Ｂｒｕｃｋｓｔｅｉｎ Ａ Ｍ．Ａ ｐｒｏｂａｂｉｌｉｓｔｉｃ Ｈｏｕｇｈ ｔｒａｎｓ· Ｋｉｒｙａｔｉ ｆｏｒｍ［Ｊ］．Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ，１９９１，２４（４）：３０３—３１６． ［７Ｊ Ｋｕｌｔｕｎｅｎ Ｐ，Ｘｕ Ｌ，Ｏｊａ Ｅ．Ａ ｎｅｗ ｃｕｒｖｅ ｄｅｔｅｃｔｉｏｎ ｍｅｔｈｏｄ：Ｒａｎ— ｄｏｍｉｚｅｄ Ｈｏｕｇｈ ｔｒａｎｓｆｏｒｍ［Ｊ］．ＰａＲｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ Ｌｅｔｔｅｒｓ，１９９０， １１（５）：３３１－３３８． ［８］ Ｌｉ Ｑｕａｎｌｉｎ，Ｚｈｏｕ Ｙｕａｎ．Ｐｒｏｂａｂｉｌｉｔｙ ｍｏｄｅｌ ｏｆ ｒａｎｄｏｍｉｚｅｄ Ｈｏｕｇｈ ｔｒａｎｓｆｏｒｍ：ｌｉｍｉｔｅｄ ｄａｔａ［Ｊ］．Ｃｈｉｎｅｓｅ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒｓ，２００２， ２５（３）：２３８—２４６－［李泉林，周渊．随机Ｈｏｕ【ｇＩＩ变换的概率模 型；有限数据点［Ｊ］．计算机学报，２００２，２５（３）：２３８·２４６．］ 【９】 Ｌｅａｎｄｒｏ Ａ，Ｆｅｍａｎｄｅｓ Ｆ，Ｏｆｉｖｅｉｒａ Ｍ Ｍ．Ｒｅａｌ·ｔｉｍｅ ｌｉｎｅ ｄｅｔｅｃｔｉｏｎ ｔｈｒｏｕｇｈ ａｎ ｉｍｐｒｏｖｅｄ Ｈｏｕｇｈ ｔｒａｎｓｆｏｒｍ ｖｏｔｉｎｇ ｓｃｈｅｍｅ［Ｊ］．Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ，２００８，４１（１）：２９９－３１４． ［１０】 图９图像修复应用 Ｆｉｇ．９ 结 Ｐ．Ｆｉｔｔｉｎｇ ａｎ ｕｎｋｎｏｗｎ ｎｕｍｂｅｒ ｏｆ ｆｉｎｅｓ ａｎｄ ｐｌａｎｅｓ ｔｏ ｉｍａｇｅ ｄａｔａ ｔｈｒｏｕｓｈ ｃｏｍｐａｔｉｂｌｅ ｃｌｕｓｔｅｒ ｍｅｒｇｉｎｇ［Ｊ］． Ａｐｐｌｉｃａｔｉｏｎ ｏｆ ｉｍａｇｅ ｒｅｃｏｖｅｒｉｎｇ Ｐａｔｔｅｒｎ Ｒｅｅｏｇｎｔｉｏｎ。１９９２，２５（４）：３８５—４００． ［１１］ ５ Ｋｒｉｓｈｎａｐｕｒａｍ Ｒ，Ｆｒｅｇ Ｃ Ｄａｖｅ Ｒ Ｎ．Ｕｓｅ ｏｆ ｔｈｅ ａｄａｐｔｉｖｅ ｆｕｚｚｙ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｔｏ ｆｉｎｅｓ ｉｎ ｄｉｇｉｔａｌ 论 ｄｅｔｅｃｔ ｉｍａｇｅｓ［Ｊ］．Ｉｎｔｅｌｌｉｇｅｎｔ Ｒｏｂｏｔｓ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ＶｌｌＩ，１９８９，１１９２（２）：６００－６１１． ［１２】 直线检测一直是模式识别与计算机视觉的基本 ｔｉｏｎ ［１３】 ｄｅｔｅｅ— ｔｈｒｏｕｇＩｌ ｐｏｓｓｉｂｉｆｉｓｔｉｃ ｃｌｕｓｔｅｒｉｎｇ［Ｃ］／／Ｐｒｏ— Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｃｈｅｒ Ｃｏｎｆｅｒｅｎｃｅ Ｉｍａｇｅ ｏｎ Ａ．Ｃｌｕｓｔｅｒｉｎｇ ｏｆ Ａ，Ｓｈｎｅｉｅｒ Ｍ，Ｒｏｓｅｎｆｅｌｄ Ｔｓｕｄａ Ｋ，Ｍｉｎｏｈ ｓｅｑｕｅｎｔｉａｌ ｆｕｚｚｙ Ｐｒｏｃｅｓｓｉｎｇ， ｃｏｌｉｎｅａｒ ｌｉｎｅ Ｍ，Ｉｋｅｄａ ｋ Ｅｘｔｒａｃｔｉｎｇ ｓｔｒａｉｇｈｔ ｆｉｎｅｓ ｂｙ ｃｌｕｓｔｅｒｉｎｇ［Ｊ］．Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｏｎ Ｌｅｔｔｅｒｓ，１９９６， １７（６）：６４３—６４９． ［１５］ 需要非常精确，故可以考虑对分割算法进行加速，或 Ｃａｎｎｙ Ｊ Ｆ．Ａ ｃｏｍｐｕｔａｔｉｏｎａｌ ａｐｐｒｏａｃｈ ｔｏ ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ 者采用其他更快的算法。另外关于直线有效性的检 验，本文标准尚不适用于所有图像，必须根据具体的 Ｕｎｓｕｐｅｒｖｉｓｅｄ ｓｅｇｍｅｎｔｓ［Ｊ］．Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ，１９８２，１５（２）：８５—９１． ［１４］ 加速，实现实时检测。目前由于采用基于图的分割 算法，所以预处理分析比较慢。事实上分割结果不 ｏｆ ａＬ Ｌａｕｓａｎｎｅ，Ｓｗｉｔｚｅｒｌａｎｄ：ＩＥＥＥ，１９９６：９６３—９６６． 特征直线。实验结果表明新算法检测结果准确度 高、速度快、实用性强。今后工作主要是算法进一步 Ｍ，Ｃａｐｐｅｌｌｉｎｉ Ｖ，Ｍｅｃｏｃｅｉ Ａ，ｅｔ ｏｆ ｓｔｒａｉｇｈｔ ｌｉｎｅｓ ｃｅｅｄｉｎｇｓ 问题之一。给出了一种基于线段聚类的快速直线检 测算法，并提出了直线有效性度量用于从中找出主 Ｂａｒｎｉ ｏｎ ｅｄｇｅ ｄｅｔｅｃｔｉｏｎ［Ｊ］． Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ， １９８６，８（６）：６７９—６９８． ［１６］ Ｆｅｌｚｅｎｓｚｗａｌｂ Ｐ ｉｍａｇｅ 实际应用考虑更多因素。 Ｆ．Ｈｕｔｔａｎｌｏｃｈｅｒ Ｄ Ｐ．Ｅ珏ｉｃｉｅｎｔ ｓｅｇｍｅｎｔａｔｉｏｎ［Ｊ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ ｇｒａｐｈ—ｂａｓｅｄ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ，２００４，５９（２）：１６７—１８１． ［１７】 参考文献（Ｒｅｆｅｒｅｎｃｅｓ） Ｂａｎｅｒｊｃｅ Ｓ，Ｂｒｉａｎ Ｌ Ｅ．Ｕｎｓｕｐｅｒｖｉｓｅｄ ａｕｔｏｍａｔｉｏｎ ｏｆ ｐｈｏｔｏｇｒａｈｉｅ ｃｏｍｐｏｓｉｔｉｏｎ ｒｕｌｅｓ ｉｎ ｄｉｇｉｔａｌ ｓｔｉｌｌ ｃａｎｌｅｒａｓ［Ｊ］．Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆＳＰＩＥ ２００４，５３０１：３６４·３７３． ［１】Ｄｕｄａ Ｒ Ｏ。Ｈａｒｔ Ｐ Ｅ．Ｕｓｅ ｏｆ ｔｈｅ Ｈｏｕｇｈ ｔｒａｎｓｆｏｒｍａｔｉｏｎ ｔｏ ｄｅｔｅｃｔ ｌｉｎｅｓ ａｎｄ ｃｕｒｖｅｌｌ ｉｎ ｐｉｃｔｕｒｅｓ［Ｊ】．Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆ ｔｈｅ ＡＣＭ， １９７２，１５（１）：１１·１５． 万方数据 ［１８］ Ｓｕｎ Ｊ，Ｙｕａｎ Ｌ，Ｊｉａ Ｊ Ｙ，ｅｔ ａＬ Ｉｍａｇｅ ｃｏｍｐｌｅｔｉｏｎ ｐｒｏｐａｇａｔｉｏｎ［Ｊ］．ＡＣＭ Ｔｒａｎａｎｃｔｉｏｎｓ ８６１．８６８． ｏｎ ｗｉｔｈ ｓｔｒｕｃｔｕｒｅ Ｇｒａｐｈｉｃｓ，２００５。２４（３）： 图像主特征直线的检测算法 作者： 陈仁杰， 刘利刚， 董光昌 作者单位： 刊名： 浙江大学数学系计算机图像图形研究所,杭州,310027 英文刊名： JOURNAL OF IMAGE AND GRAPHICS 年，卷(期)： 引用次数： 2010，15(3) 0次 中国图象图形学报A 参考文献(18条) 1.Duda R O,Han P E.Use of the Hough transformation to detect lines and curves in pictures[J].Communications of the ACM,1972,15(1):11-15. 2.Illingworth J,Kittler J.The adaptive Hough transform[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1987,9(5):690-698. 3.Li H W,Lavin M A,Master R J L.Fast Hough transfurm:A hierarchical approach[J].Computer Vision,Graphics,and Image Processing,1986,36(2-3):139-161. 4.Atiquzzaman M.Multiresohition Hough transform-an efficient method of detecting patterns in images[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1992,14 (11):1090-1095. 5.Yue Dongxue,Huang Xinsheng.Method of line detection based on improved multiresolution Hough transform[J].Computer Simulation,2006,23(9):76-79.[岳冬雪,黄新生.基于改进的多分辨率Hough变换的直线检 测方法[J].计算机仿真,2006,23(9):76-79.] 6.Kiryati N,Eldar Y,Bruckstein A M.A prababilistic Hough transform[J].Pattern Recognition,1991,24 (4):303-316. 7.Kultanen P,Xu L,Oja E.A new curve detection method:Randomized Hough transform[J].Pattern Recognition Letters,1990,11(5):331-338. 8.Li Quanlin,Zhou Yuan.Probability model of randomized Hough transform:limited data[J].Chinese Journal of Computers,2002,25(3):238-246.[李泉林,周渊.随机Hough变换的概率模型;有限数据点[J].计算机学 报,2002,25(3):238-246.] 9.Leandro A,Fernandes F,Oliveirn M M.Real-time line detection through an improved Hough transform voting scheme[J].Pattern Recognition,2008,41 (1):299-314. 10.Krishnapuram R,Freg C P.Fitting an unknown number of lines and planes to image data through compatible cluster merging[J].Pattern Recogntion,1992,25 (4):385-400. 11.Dave R N.Use of the adaptive fuzzy clustering algorithm to detect lines in digital images[J].Intelligent Robots Computer Vision Ⅷ,1989,1192(2):600-611. 12.Barni M,Cappellini V,Mecocci A,et al.Unsupervised detection of straight lines through possibilistic clustering[C]//Proceedings of International Conference on Image Processing,Lausanne,Switzerland:IEEE,1996:963-966. 13.Scher A,Shneier M,Rosenfeld A.Clustering of colinear line segments[J].Pattern Recognition,1982,15 (2):85-91. 14.TsudaK,Minoh M,Ikeda K.Extracting straight lines by sequential fuzzy clustering[J].Pattern Recognion Letters,1996,17(6):643-649. 15.Canny J F.A computational approach to edge detection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1986,8(6):679-698. 16.Felzenszwalb P F,Huttenlocher D P.Efficient graph-based image segmentation[J].International Journal of Computer Vision,2004,59(2):167-181. 17.Banerjee S,Brian L E.Unsupervised automation of photograhic composition rules in digital still cameras[J].Proceedings of SPIE 2004,5301:364-373. 18.Sun J,Yuan L,Jia J Y,et al.Image completion with structure propagation[J].ACM Transactions on Graphics,2005,24 (3):861-868. 相似文献(0条) 本文链接：http://d.g.wanfangdata.com.cn/Periodical_zgtxtxxb-a201003008.aspx 下载时间：2010年6月3日