一种用于标识数字图像中给定模糊数字直线段的方法

摘要

本发明涉及一种用于标识数字图像中给定模糊数字直线段的方法，当模糊数字直线段BDSS识别算法完成对数字图像中模糊数字直线段BDSS的识别，模糊数字直线段BDSS以集合的形式保存为识别结果；根据识别结果给定的一个模糊数字直线段BDSS，计算其几何直线特性，使用斜率符合该几何直线特性的矩形边框标识给定像素集合。本发明特别适用于可视化标识数字直线段，模糊数字直线段等数字图像中具有直线几何特征的像素集合，除在数字图像中添加矩形边框外，不修改数字图像中其他原始信息，背景更容易观察；实施简单，耗时与分辨率基本呈线性稳定增加，性能高效。

说明书

技术领域

本发明涉及一种用于标识数字图像中给定模糊数字直线段的方法，即由分 散或连续像素组成的集合，进行可视化标识的一种计算方法。

背景技术

数字图像处理中，识别图像中具有特定属性的对象具有很高的学术和应用 价值，例如人脸识别，光学字符识别等。数字直线段及衍生的，具有直线几何 特征的图形识别属于图像识别领域中的重要分支，其应用包括卫星图片中的道 路识别(S.Aliana,V.A.Tolpekina,W.Bijkera,L.Kumarb,“Identifying  curvature of overpass mountain roads in Iran from high spatial resolution  remote sensing data”,Int.J.of Appl.Earth Observation and  Geoinformation,vol.26,pp.21–25,2014.)，焊接中的焊缝识别(L.Jia, N.Sun,“A line segment detection algorithm based on statistical  analyses of quantified directions in digital image”,Comput.Modelling& New Technologies,vol.18,no.6,pp.79-88,2014.)等。对于数字直线 段及衍生对象的自动识别计算方法在国内外学术界不断推陈出新，虽然识别精 度和效率逐步上升，但一直采用较粗糙的方法标识结果，如附图说明中图1所 示。图1展示了三种常见标识方法，从左至右依次为端点标识法(P.Bhowmick  and B.B.Bhattacharya,“Fast polygonal approximation of digital curves  using relaxed straightness properties”,IEEE Trans.Pattern Anal. Mach.Intell.,vol.29,no.9,pp.1590-1602,Sept.2007.)，彩色线段标 识法(L.Jia,N.Sun,“A line segment detection algorithm based on  statistical analyses of quantified directions in digital image”, Comput.Modelling&New Technologies,vol.18,no.6,pp.79-88,2014.) 和斜率覆盖标识法(L.Buzer,“A simple algorithm for digital line  recognition in the general case”,Pattern Recognition,vol.40,no.6, pp:1675-1684,Jun.2007.)。这三种标识法的共同缺点是使用单色完全覆盖 标识对象，过多修改了图像原始数据，导致背景信息丢失，无法清楚标识叠加 区域，对人眼观察被识别对象造成了障碍，特别是当识别对象只包含覆盖区域 的部分像素时，这种对象包含部分像素的情况是现实图像中的常见情况。学术 界常以类似图1中(a)和(c)的相应原始图像开展测试，在这种理想状态下， 单色覆盖引起的问题不显著，但涉及到实际应用时，往往需要根据实际图像测 试结果反复开展实验，类似图1所示的三种标识法在实际实验中会导致标识区 域背景信息的完全丢失且难以区分叠加区域，使得测试结果难以用人眼进行评 估。因此，针对图形识别，特别是数字直线段及衍生对象的识别，缺乏一种既 实施简单，又能相对完好保存图像背景的标识计算方法。

发明内容

本发明要解决的技术问题是：为了克服现有数字直线段及衍生对象的自动 识别后的标识法使用单色完全覆盖标识对象，过多修改了图像原始数据，导致 背景信息丢失，无法清楚标识叠加区域，对人眼观察被识别对象造成了障碍的 不足，本发明提供一种用于标识数字图像中给定模糊数字直线段的方法，特别 适用于可视化标识数字直线段，模糊数字直线段等数字图像中具有直线几何特 征的像素集合，除在数字图像中添加矩形边框外，不修改数字图像中其他原始 信息。

为使陈述清楚明了，现集中定义本发明所涉及的部分符号和概念。

Z⁺表示正整数集合。

Z表示包括零的整数集合。

R⁺表示包括零的正实数集合。

R表示包括零的实数集合。

max{元素|元素满足的条件}表示满足条件的“最大”元素。

min{元素|元素满足的条件}表示满足条件的“最小”元素。

对于r∈R⁺，

表示数字图像的宽。

表示数字图像的高。

存在r₁,r₂∈R⁺，满足条件

索引值：

图像数据：以索引值标识并保存的数字化信息。

图像空间(记作)：保存数字图像的图像数据。每一个记录单元唯一对应 一个像素。图像数据中，对应图像信息左上角的像素索引值为按照对应图 像信息的，先从左向右，后从上至下的顺序排列像素，顺序中的第k∈Z⁺个像素 的索引值为

p_i表示图像空间中索引值为i的像素。

p_(x，y)表示图像空间中，对应坐标空间中的点(x，y)的像素，其中x,y∈Z。

dist(o₁,o₂)：当o₁，o₂为二维空间中的点时，dist(o₁,o₂)表示o₁与o₂间的欧 几里得距离；当o₁，o₂分别为二维空间中的点和直线时，dist(o₁,o₂)表示从o₁做 与o₂垂直的直线，垂线与o₂的交点到o₁的欧几里得距离；当o₁,o₂∈R， dist(o₁,o₂)＝|o₁-o₂|。

对于r，round(r)＝min{z∈Z⁺|dist(z,r)≥0}。

偏移量：对于偏移量为

序列化：将中的像素按索引值递增的顺序，向右逐个成行排列，当一行像 素数为则在此行第一个像素正下方另起一行，并按上一行的排列方法继续 排列像素，如此反复，直至中所有像素按索引值递增的顺序排列完毕，此时每 行像素数为可视作具有长宽且单位欧几里得距离为的二维空间。

坐标空间(记作)：序列化并任选其中一个像素为原点的直角坐标系。对 于该坐标系中具有单位欧几里得距离的两点(x₁,y₁)和(x₂，y₂)，由式 给出的单位欧几里得距离值为该坐 标系是具有无限长(y轴)宽(x轴)的二维空间。

平均中心：对于其中i＝1,2…n，n为BDSS所含像素总数； 平均中心的坐标为$\bar{x}={\Sigma }_{i=1}^n{x}_i/n,\bar{y}={\Sigma }_{i=1}^n{y}_i/n.$

图像中心：即像素

坐标中心化：序列化设的原点为图像中心且x正半轴指向图像中心所 在行的右侧，对于偏移量已知为d_i的像素与中坐标为的点一一对应，(x_i,y_i)称为p_i的中心 坐标。当像素的中心坐标已知为(x_i,y_i)时，其偏移量为索引值为

数字直线段(digital straight segment，DSS)：坐标中心化若像素和的坐标值分别为和i_p,i_q,j_p,j_q∈Z且i_p＜i_q， 过p和q的直线记作且其斜率属于区间(0,1)，对于中直线x＝i∈R其中 i_p≤i≤i_q，若直线和直线x＝i的交点坐标为(x,y),则存在坐标值为 (round(x),round(y))的唯一像素，其与交点的欧几里得距离不大于 在区间[i_p,i_q]内变化i值，可获得此类像素的集合，由p和q确 定的数字直线段DSS(p,q)为：

模糊数字直线段(blurred digital straight segment，BDSS)：坐标中心 化若i,j,a,b,μ,ω∈Z,b≠0且gcd(a,b)＝1，则满足条件μ≤di-bj≤μ+ω 的的合集称为模糊数字直线段BDSS(a,b,μ,ω)，即：

在以上定义的基础上，本发明解决其技术问题所采用的技术方案是：

当模糊数字直线段BDSS识别算法完成对宽高的数字图像中模糊数字直线 段BDSS的识别，模糊数字直线段BDSS以集合的形式保存为识别结果；

根据识别结果给定的一个模糊数字直线段BDSS，计算其几何直线特性，使用 斜率符合该几何直线特性的矩形边框标识给定像素集合。

具体包括以下步骤：

步骤1：计算坐标中心化图像空间中，对应坐标空间的中心坐标；

步骤2：根据模糊数字直线段BDSS中像素的中心坐标，计算平均中心，并使 用线性回归计算模糊数字直线段BDSS的方向θ；

步骤3：计算模糊数字直线段BDSS中像素的转换坐标：将坐标中心化对应的 坐标空间的原点平移到平均中心，并将x轴正半轴旋转至与θ重合；

步骤4：根据模糊数字直线段BDSS中像素的转换坐标计算模糊数字直线段 BDSS在转换坐标系中的四个边界点；

步骤5：生成平行于方向θ的边界线l₁和l₂，并计算其转换坐标，边界线l₁和l₂分别通过步骤4中的其中两个边界点；

步骤6：生成垂直于方向θ的边界线l₃和l₄，并计算其转换坐标，边界线l₃和 l₄分别通过步骤4中的另外两个边界点，直线l₁，l₂，l₃和l₄相交形成矩形边框；

步骤7：根据步骤5和6所生成的转换坐标，计算其中心坐标；

步骤8：根据步骤7所生成的中心坐标，计算其偏移量并将偏移量保存为结 果输出。

根据偏移量所确定像素的集合即为矩形边框，最后，可以使用像素修改方 法，在识别BDSS的数字图像中更改矩形边框所含像素的值以标识模糊数字直线 段BDSS。

步骤1和2中，将识别模糊数字直线段BDSS的数字图像映射为坐标中 心化对于任意像素p∈BDSS，若p的偏移量为d，则其中心坐标根据式(1) 计算：

通过BDSS像素的中心坐标，计算BDSS的平均中心

根据线性回归理论，BDSS的方向θ∈[0，π)，由式(2)计算：

其中i＝1,2…n，n为BDSS所含像素总数。

步骤3中，对于其转换坐标根据式(3)计 算：

$\left(\begin{array}{c}{x}^{\prime }=(x-\bar{x})\cos \theta +(y-\bar{y})\sin \theta \\ y^{\prime }=-(x-\bar{x})\sin \theta +(y-\bar{y})\cos \theta \end{array}\right)---\left(3\right).$

步骤4中，转换坐标系中的四个边界点通过比较转换坐标的所有横坐标x 和纵坐标y得到。

坐标空间的原点的转换坐标为步骤7中，对于其中心坐标根据式 (7)计算：

步骤8中，对于像素的偏移量d由式(8)计算：

在中，由于原点位于BDSS的平均中心，BDSS像素转换坐标存在四个极值， 即横坐标最大值x′_lmax，横坐标最小值x′_lmin，纵坐标最大值y′_wmax和纵坐标最小 值y′_wmin；中存在着对应转换坐标(x′_lmax,0)，(x′_lmin,0)，(0,y′_wmax)和(0,y′_wmin) 的像素，这些像素为步骤4所述的边界点；

其中，表示矩形边框，矩形边框的定义由式(4)给出：

其中m＝1，2，3，4，表示从 p′_(x′,y′)做与l_m垂直的直线，垂线与l_m的交点到p′_(x′,y′)的欧几里得距离。

矩形边框实际上由四条线段组成，式(4)可被替换为式(5)和式(6)， 式(5)和式(6)分别为l₁和l₂上，l₃和l₅上像素的转换坐标：

本发明的有益效果是，本发明的一种用于标识数字图像中给定模糊数字直 线段的方法，对给定数字直线段，模糊数字直线段等，由分散或连续像素组成 的像素集合，计算其几何直线特性，使用斜率符合所计算特性的矩形边框标识 给定像素集合的计算方法，具有如下优点：

(1)本发明方法在未大幅修改背景像素的前提下，清晰地标明了给定的模 糊数字直线段。随着被标识数字图像分辨率的上升，本发明方法所修改像素的 数量与图像全部像素之比快速下降，其视觉效果呈现为高分别率图像中，本发 明标识的BDSS背景更容易观察；即使是小分辨率图像，本发明方法对图像背景 的占用也较有限。

(2)本发明方法实施简单，耗时与分辨率基本呈线性稳定增加，性能高效。

附图说明

下面结合附图和实施例对本发明进一步说明。

图1是目前常用的标识方法。(a)端点标识法，(b)彩色线段标识法，(c) 斜率覆盖标识法。

图2是本发明的一种用于标识数字图像中给定模糊数字直线段的方法的原 理图。(a)将原坐标系旋转到转换坐标系，(b)将转换坐标系旋转回原坐标系。

图3是本发明的一种用于标识数字图像中给定模糊数字直线段的方法中 Point类的数据结构。

图4是本发明的一种用于标识数字图像中给定模糊数字直线段的方法的原 理框图。

图5是本发明的一种用于标识数字图像中给定模糊数字直线段的方法中步 骤2的原理框图。

图6是本发明的一种用于标识数字图像中给定模糊数字直线段的方法中步 骤5的原理框图。

图7是本发明的一种用于标识数字图像中给定模糊数字直线段的方法中步 骤6的原理框图。

图8是本发明标识128*128分辨率的图像中给定模糊数字直线段的结果图。 (a)图像cameraman，(b)图像house，(c)图像lena，(d)图像puzzle。

图9是本发明标识256*256分辨率的图像中给定模糊数字直线段的结果图。 (a)图像cameraman，(b)图像house，(c)图像lena，(d)图像puzzle。

图10是本发明标识512*512分辨率的图像中给定模糊数字直线段的结果图。 (a)图像cameraman，(b)图像house，(c)图像lena，(d)图像puzzle。

图11是本发明的一种用于标识数字图像中给定模糊数字直线段的方法不同 步骤在完成绘制一幅图中所有BDSS边框的平均耗时情况分析图。

图12是本发明的一种用于标识数字图像中给定模糊数字直线段的方法不同 步骤在完成绘制一幅图中最长的BDSS边框的耗时情况分析图。

图13是本发明的一种用于标识数字图像中给定模糊数字直线段的方法不同 步骤在完成绘制一幅图中最短的BDSS边框的耗时情况分析图。

图14是本发明的一种用于标识数字图像中给定模糊数字直线段的方法总耗 时随图像分辨率增加而变化的情况分析图。

具体实施方式

现在结合附图对本发明作进一步详细的说明。

当BDSS识别算法完成对宽高的数字图像中模糊数字直线段(BDSS)的 识别，BDSS以集合的形式保存为识别结果。

对于任一BDSS，根据BDSS定义，其形态类似附图说明的图2(a)和图2(b) 所示。图2(a)和图2(b)用方块代表的像素群分别展示了一个BDSS，图2(a) 表示将原坐标系旋转到转换坐标系，图2(b)表示将转换坐标系旋转回原坐标 系。本发明的目标是根据给定的一个BDSS，通过基于数学原理的计算，得到如 图2(a)所示，由直线l₁，l₂，l₃和l₄相交形成的矩形边框在识别该BDSS的数 字图像中，所对应像素的偏移量。每条直线通过一个边界点，且l₁，l₂与BDSS方 向θ平行，l₃，l₄与θ垂直。

根据偏移量所确定像素的集合称为矩形边框，可以使用本发明以外的各种 像素修改方法，在识别BDSS的数字图像中更改矩形边框所含像素的值以标识 BDSS。

对于给定的一个BDSS，将识别BDSS的数字图像映射为坐标中心化中 像素中心坐标对应的坐标系在图2中由相互垂直的箭头直线表示，标有x的箭 头表示x轴正半轴。对于任意像素p∈BDSS，若p的偏移量为d，则其中心坐标根 据式(1)计算：

通过BDSS像素的中心坐标，可计算BDSS的平均中心图2中以实 心小点和汉字标识了根据线性回归理论，BDSS的方向θ∈[0，π)由式(2) 计算：

n为BDSS所含像素总数。

图2(a)中l₁和l₂平行，l₁和l₂与中x轴正半轴的较小夹角为θ。根据θ和 BDSS像素的中心坐标虽可直接计算l₁，l₂，l₃和l₄参数及交点，但计算过程较 复杂，且实施难度较大。

本发明规避了直接计算l₁，l₂，l₃和l₄交点的传统方法，通过平移和旋转坐 标系并计算在转换后坐标系中BDSS的最大和最小坐标值，完成矩形边框的计算。 平移是将的原点移动到BDSS的平均中心，旋转是逆时针旋转的x轴正半轴， 并保证旋转后的x轴正半轴与原x轴正半轴的夹角为θ，通过这种平移和旋转获得 的坐标系称为转换坐标系，记作图2(a)中，由相互垂直的箭头直线表 示,标有x′的箭头表示x轴正半轴，标有y′的箭头表示y轴正半轴，弧形箭头虚线 从原点指向原点表示将的原点平移至与的x轴正半轴的夹角为θ， 旋转方向由弧形箭头实线表示。BDSS像素在中的坐标称为转换坐标。对于 其转换坐标根据式(3)计算：

$\left(\begin{array}{c}{x}^{\prime }=(x-\bar{x})\cos \theta +(y-\bar{y})\sin \theta \\ y^{\prime }=-(x-\bar{x})\sin \theta +(y-\bar{y})\cos \theta \end{array}\right)---\left(3\right).$

在中，由于原点位于BDSS的平均中心，BDSS像素转换坐标存在四个极值， 即横坐标最大值x′_lmax，横坐标最小值x′_lmin，纵坐标最大值y′_wmax和纵坐标最小 值y′_wmin。中存在着对应转换坐标(x′_lmax,0)，(x′_lmin,0)，(0,y′_wmax)和(0,y′_wmin) 的像素，这些像素称为边界点，图2(a)中用实心小点和转换坐标标识了边界 点。

通过边界点，θ，l₁与l₂平行，l₃与l₄平行且l₁与l₃垂直的条件，对于图2 (a)中所示的情况，矩形边框的定义由式(4)给出：

其中d_m＝dist(p′_(x′,y′),l_m)，m＝1，2，3，4，dist(p′_(x′,y′),l_m)表示从 p′_(x′,y′)做与l_m垂直的直线，垂线与l_m的交点到p′_(x′,y′)的欧几里得距离。

对于图2(a)中所示的情况，实际上由四条线段组成，式(4)可被式 (5)和式(6)替代：

式(5)和式(6)分别给出了l₁和l₂上，l₃和l₄上像素的转换坐标。通过 像素的转换坐标，可以计算其像素偏移量，通过偏移量可更改识别BDSS的数 字图像中对应像素的值。计算偏移量的过程依次包括根据转换坐标计算中心坐 标和根据中心坐标计算偏移量。

根据转换坐标计算中心坐标，相当于通过将的原点平移回的原定，并顺 时针旋转中x轴正半轴至的x轴正半轴，将还原为附图说明的图2(b) 中，由相互垂直的箭头直线表示，标有x′的箭头表示x轴正半轴，标有y′的箭 头表示y轴正半轴，由相互垂直的箭头直线表示,标有x的箭头表示x轴正半轴， 从原点指向原点的弧形箭头虚线表示原点平移，从的x轴正半轴指向的x 轴正半轴的弧形箭头实线表示逆时针旋转。还原过程需要原点的转换坐标，其 转换坐标为对于其中心坐标根据式(7)计算：

根据像素的中心坐标，对于像素的偏移量d由式(8)计算：

通过像素的偏移量，即可在识别BDSS所用的数字图像中更改像素的值， 从而完成标识模糊数字直线段BDSS的目的。

具体地，本发明计算方法的实施方式由编写计算机程序完成。

程序输入包括：一个BDSS，识别BDSS所使用的数字图像以及其宽和高其中BDSS的像素以附图说中图3所示数据结构表示。图3展示了Point类，其属 性包括用于存储偏移量的Deviation，分别用于存储中心坐标横坐标x的属性 XtoImageCenter和纵坐标y的属性YtoImageCenter，分别用于存储转换坐标横坐 标x的属性XtoCollectionCenter和纵坐标y的属性YtoCollectionCenter。属性 Deviation的数据类型为整数，用integer表示，其他Point类属性的数据类型为双 精度浮点数，用double表示。

程序输出为根据输入BDSS计算的，由式(4)定义的像素集合。

程序包括八个步骤，见附图说明的图4。现依次介绍八个步骤。

步骤1：计算坐标中心化图像空间中，对应坐标空间的Point对象的中心坐 标。

映射数字图像至图像空间根据中像素的索引值，输入的和可计 算得到每个Point对象的偏移量并坐标中心化对于偏移量为d的Point对象，其 中心坐标根据式(1)计算，中心坐标的横坐标x与纵坐标y分别以属性 XtoImageCenter和YtoImageCenter保存。

步骤2：根据BDSS中Point对象坐标，计算平均中心，并使用线性回归计算 其方向θ。

根据步骤1计算的BDSS中各Point对象中心坐标，计算BDSS的平均中心 基于线性回归理论，根据式(2)计算BDSS的方向θ。具体流程见附 图说明的图6。

步骤3：将坐标中心化对应的坐标空间的原点平移到平均中心，并将x轴正 半轴旋转至与θ重合，计算BDSS中Point对象的转换坐标。

Point对象的转换坐标根据式(3)计算，转换坐标的横坐标x与纵坐标y分别 以属性XtoCollectionCenter和YtoCollectionCenter保存。

步骤4：根据BDSS中Point对象的转换坐标计算边界点。

中BDSS坐标极值是通过比较BDSS中所有Point对象转换坐标的 XtoCollectionCenter属性值和YtoCollectionCenter属性值得到。根据比较得到的 极值，生成类似附图说明的图2中边界点(x′_lmax,0)，(x′_lmax,0)，(0,y′_wmax)和 (0,y′_wmax)的Point对象。这些边界点是完成步骤5和步骤6计算的基础。

步骤5：生成平行于方向θ的边界线的Point对象，并计算其转换坐标。

根据式(5)生成对应图2中l₁和l₂的Point对象，具体流程见附图说明的图 6。边界点的坐标分别用变量X_start，X_end，Y_start和Y_end保存。以附图说明的图2 中的边界点(x′_lmax,0)，(x′_lmin,0)，(0,y′_wmax)和(0,y′_wmin)为例，X_start，X_end，Y_start和Y_end的值分别为x′_lmin，x′_lmax，y′_wmin和y′_wmax，即横坐标x的最小值和最大值， 纵坐标y的最小值和最大值。在保持Y_start和Y_end不变且X_star不大于X_end的前提 下，以X_start为转换坐标横坐标x的初值并每次循环X_start自增1的方式，循环生 成转换坐标分别为(X_start,Y_start)和(X_end,Y_start)的两个Point对象。将循环产生的 所有Point对象保存在矩形边框中。

步骤6：生成垂直于方向θ的边界线的Point对象，并计算其转换坐标。

根据式(6)生成对应图2中l₃和l₄的Point对象，具体流程见附图说明的图 7。使用边界点横坐标x的最小值重新初始化变量X_start，在保持X_start和X_end不 变且Y_start不大于Y_end的前提下，以Y_start为转换坐标横坐标y的初值并每次循环 Y_start自增1的方式，循环生成转换坐标分别为(X_start,Y_start)和(X_start,Y_end)的两 个Point对象。将循环产生的所有Point对象保存在矩形边框中。

步骤7：根据所生成Point对象的转换坐标，计算其中心坐标。

对于矩形边框中所有Point对象，其中心坐标的计算根据式(7)完成。

步骤8：根据所生成Point对象的中心坐标，计算其偏移量并将偏移量保存 为结果输出。

对于矩形边框中所有Point对象，其偏移量的计算根据式(8)完成。

根据输出结果，可以使用像素修改方法，在识别BDSS的数字图像中更改矩 形边框所含像素的值以标识模糊数字直线段BDSS。

以下分为两部介绍本发明的有益效果，第一部分为本发明方法的直观视觉 效果；第二部分为计算效率分析：

1、视觉效果：

图8至图10展示了应用本发明方法标识给定BDSS的结果图(图中矩形边框 均以1像素宽的黑线，白线，黑线的顺序叠加而成的线段表示)。图8至图10 中，数字图像的分辨率依次为128×128，256×256和512×512。注意图像分 辨率改动后，输入的BDSS也会变化，本发明方法的输出会随之变化，并不是放 大相同的结果。图8至图10用于说明随分辨率提高，算法污染的背景像素相应 减少，视觉上的感受是边框遮挡的背景变少，且更容易分辨相互叠加的BDSS。

比较图8至图10所示结果与图1所示结果，很容易得出本发明方法在未大 幅修改背景像素的前提下，清晰地标明了给定的BDSS，可以试想若采用图1(c) 展示的算法标识分辨率较低的图像，例如图8，则被本发明方法标识的BDSS会 以单色填充的矩形表示，从而导致人眼无法辨识BDSS背景区域。随着被标识数 字图像分辨率的上升，本发明方法所修改像素的数量与图像全部像素之比快速 下降，其视觉效果呈现为高分别率图像中，本发明标识的BDSS背景更容易观察， 例如图10，即使是小分辨率图像，本发明方法对图像背景的占用也较有限，例 如图8。

2、计算效率：

附图说明的图11至图13的柱状图展示了具体实施方式所述的八个步骤 消耗的时间，注意图11至图13纵轴单位为CPU时钟周期数的对数。图11至图 13横轴首先按图像cameraman，lena，house和puzzle的顺序从左到右排列， 对于每一幅图，再按分别率128×128，256×256和512×512的顺序从左到右 排列。以图11为例，横轴说明文字“图像cameraman”上方从左到右的立柱分 别对应分别率为128×128，256×256和512×512的耗时。每个立柱里不同颜 色的区域表示不同步骤的耗时，区域越大，则该步骤耗时越多，立柱越高，则 总耗时越多。图11至图13中的同一立柱由下至上的各个方块依次表示具体实 施方式所述的步骤1至步骤8的每个步骤所消耗的时间。图11展示了平均耗时， 即对一幅数字图像中的所有给定BDSS的标识各步骤及总耗时平均值。图12展示 了最大耗时，即对一幅数字图像中给定的具有最多Point对象的BDSS标识中各步 骤及总耗时。图13展示了最小耗时，即对一幅数字图像中给定的具有最少Point 对象的BDSS标识中各步骤及总耗时。图11-13是显示不同步骤在不同情况下的 耗时分布，用于说明算法核心步骤5，6，7耗时较少。

通过观察图11至图13，步骤8在多个立柱中所占区域最多，即该步骤最耗 时。这是由于步骤8计算复杂度较高，且要将矩形边框转换成符合后续处理格 式而引起的。对于每个Point对象，根据式(7)步骤7要完成4次乘法和6次加 法运算，而步骤8需完成1次乘法，2次除法，3次加法及2次取整运算虽 然步骤8运算次数稍小，但其涉及的多是除法和取整此类较复杂的运算。用于 计算矩形边框的步骤5和步骤6在图11至图13普遍耗时少于步骤3和步骤4， 特别是当BDSS包含较少Point对象时，即图13所示。这从效率反应了本发明方 法实施简单的特点，因为步骤5与步骤6是产生矩形边框的主要步骤，由于其 实施过程未涉及复杂运算或数据结构，与其他步骤，特别是步骤7与步骤8相 比，步骤5与步骤6耗时较少。

图14是总耗时随图像分辨率增加而变化的情况分析图，总耗时就是处理 一幅图像中所有BDSS耗时的总和。图14展示了从分别率128×128到512×512， 每间隔32×32的本发明计算方法总耗时情况，注意图14的横轴只显示了图像的 一维大小。按上述分别率顺序，即128，160，192……，图像cameraman，lena， house和puzzle不同分辨率版本的耗时以实心圆点标注在图14中，对于相同内 容但不同分别率图像的圆点用具有相同线段形状的直线段连接，具体的线段形 状说明详见图14。图14中的四条连线基本呈线性，即耗时与分辨率基本成正比， 其中典型的是图像cameraman的耗时分布，图像lena和图像puzzle的耗时分 布虽然起伏很大，但从线性回归的角度分析，其分布与理想直线的差异较小。

图14中，图像house的耗时分布随分辨率增长，出现下降的趋势，但由于其它 图像均未出现这种趋势，house的情况仅是个别现象。综上，通过图14的耗时 分布，未发现本发明方法随分辨率增加，明显呈现耗时非线性快速增加的情况， 即，本发明方法耗时与分辨率基本呈线性稳定增加。这说明本发明计算方法的 性能较为高效。