基于常量时间复杂度的图像矩形邻域极大(极小)值计算方法

摘要

本发明提供了一种基于常量时间复杂度的图像矩形邻域极大(极小)值计算方法。该方法可以简要的概括为以下四个步骤：用户给定一幅灰度图像作为输入图像；根据输入图像构造一个三维的多层直方图；分别计算多层直方图中每一层的直方图的图像矩形邻域求和，获得一个矩形邻域求和的多层直方图；根据矩形邻域求和的多层直方图计算出输入图像中每一个像素所对应的矩形邻域求和值大于0的最大(最小)层的层号，即为所求的输入图像的图像矩形邻域极大(极小)值。本方法利用三维的多层直方图及其局部相关性来求解图像矩形邻域极大(极小)值，使图像矩形邻域极大(极小)值的计算具有常量时间复杂度。

说明书

技术领域

本发明涉及一种图像矩形邻域极大(极小)值计算方法，尤其是基于常量时间复杂度的 图像矩形邻域极大(极小)值计算方法。

背景技术

图像矩形邻域极大(极小)值的计算，是指通过一些特定的算法求图像中每个像素的矩 形邻域内的极大(极小)值。图像矩形邻域极大(极小)值计算有着非常广泛的应用。例如， 调节图像对比度时就需要求图像矩形邻域的极大值和极小值。在模式识别领域，往往需要求 图像中每个像素的矩形邻域内的特征极值来指导目标检测或者分类。因此图像矩形邻域极大 (极小)值计算有着重要的实际意义。

然而，传统的求解图像矩形邻域极大(极小)值的方法，直接对矩形邻域内的所有像素 值进行极大(极小)比较，处理每个像素极值的时间复杂度并达不到常量时间复杂度，而是 随着矩形邻域的增大而增大。当矩形邻域比较大的时，传统方法会消耗比较多的处理时间， 这就限制了其在某些算法中的应用。因此，本发明提出了一种基于常量时间复杂度的图像矩 形邻域极大(极小)值计算方法。

发明内容

本发明的目的：本发明提出了一种基于常量时间复杂度的图像矩形邻域极大(极小)值 计算方法。该方法利用三维的多层直方图来求图像矩形邻域极大(极小)值，改善了算法的 时间复杂度。

本发明设计了一种基于常量时间复杂度的图像矩形邻域极大(极小)值计算方法。该方 法包括以下四个步骤：

(1)给定一幅二维的灰度图像作为输入图像I，其宽度和高度分别记作w和h个像素，I 中像素记作(x，y)，则x∈{0，1，2，...，w-1}，y∈{0，1，2，...，h-1}。(x，y)的像素值记作I(x，y)，对 于8位二进制数所表示的灰度图像，最多有2⁸＝256个灰度值，因此I(x，y)∈{0，1，2，...，255}。 给定一个大小为(2r+1)×(2r+1)的二维矩形作为像素(x，y)的矩形邻域Ω(x，y)(其中r为自然 数)。

(2)根据步骤(1)中输入图像I构造一个三维的多层直方图V。V层数等于I的取值范 围，即256层，每层的直方图宽度和高度与I相同，即分别为w和h。用z表示V中层号，则 z∈{0，1，2，...，255}，第z层直方图记作V_z。遍历输入图像的所有像素，首先对V中所有的值根 据公式V_z(x，y)＝0进行初始化，然后根据公式V_I(x，y)(x，y)＝1对V进行设置。也就是说，对于 像素(x，y)，如果像素值I(x，y)和第z层直方图V_z的层号不相等，则V_z(x，y)＝0，反之，则设 置为V_z(x，y)＝1。该构造方法只需要常量时间复杂度即可构造完成。

(3)根据步骤(1)中的矩形邻域Ω(x，y)和步骤(2)中构造的三维的多层直方图V，采用 基于常量时间复杂度的积分图算法分别计算V中每一层的直方图的图像矩形邻域求和，获得 一个矩形邻域求和的多层直方图V′。

对于第z层直方图V_z，首先对V_z求每一列的前序和，记作S_z。设置初始值S_z(x，-1)＝0，从 小到大遍历V_z中每一行，根据如下公式迭代计算对V_z每一列的前序和：

S_z(x，y)＝S_z(x，y-1)+V_z(x，y)

然后，利用S_z作为中间结果构造直方图V_z的积分图A_z。类似地，设置初始值A_z(-1，y)＝0， 从小到大遍历S_z中每一列，根据如下公式迭代计算对S_z每一行的前序和：

A_z(x，y)＝A_z(x-1，y)+S_z(x，y)

接下来，对于第z层直方图V_z，可以根据如下公式高效计算出对应的矩形邻域求和的直 方图V′_z：

V′_z＝A_z(x-r，y-r)+A_z(x+r，y+r)-A_z(x-r，y+r)-A_z(x+r，y-r)

积分图方法最早是由PaulViola等人提出的一种常量时间复杂度的快速求图像矩形邻域 和的方法。该方法的时间复杂度只跟图像大小w，h及图像灰度范围有关，而与矩形邻域Ω(x，y) 的大小无关，即与r的大小无关。具体参见文献P.ViolaandM.Jones，″Rapidobjectdetection usingaboostedcascadeofsimplefeatures，″inProceedingsofthe2001IEEEComputerSociety ConferenceonComputerVisionandPatternRecognition(CVPR2001)，vol.1，pp.I-511-I-518， 2001。

(4)根据步骤(3)中的矩形邻域求和的多层直方图V′，基于常量时间复杂度计算出输入 图像中每一个像素所对应的矩形邻域求和值大于0的最大(最小)层的层号，即为所求的输 入图像的图像矩形邻域极大(极小)值。对于每个像素(x，y)，从大到小遍历矩形邻域求和的 多层直方图V′的每一层(即令z从255开始遍历到0)，第一个满足V′_z(x，y)＞0的层号z即为 所求的输入图像的图像矩形邻域极大值。类似地，对于每个像素(x，y)，从小到大遍历矩形邻 域求和的多层直方图V′的每一层(即令z从0开始遍历到255)，第一个满足V′_z(x，y)＞0的层 号z即为所求的输入图像的图像矩形邻域极小值。该步骤计算方法最多只需要256次就可找 到某个像素所对应的矩形邻域极大(极小)值，因此只需要常量时间复杂度即可计算完成， 而与矩形邻域Ω(x，y)的大小无关，即与r的大小无关。

至此我们就计算出了输入图像矩形邻域的极大(极小)值。

传统的求图像矩形邻域极大(极小)值的方法，处理每个像素极值的时间复杂度并达不 到常量时间复杂度，而是随着矩形邻域大小的增大而增大。相比于传统方法，本发明涉及的 基于常量时间复杂度的图像矩形邻域极大(极小)值计算方法的有益效果在于：三维的多层 直方图及其空间相关性的有效运用使得求解图像矩形邻域极大(极小)值的运算时间不会随 着图像矩形邻域Ω(x，y)的大小(2r+1)×(2r+1)中r值的增大而增大。对于一幅给定的灰度图 像，无论图像矩形邻域多大，求解该幅灰度图像的图像矩形邻域极大(极小)值的时间复杂 度始终保持不变，进而有效地改善了处理速度。

附图说明

图1是实施例的流程示意图。

具体实施方法

下面通过实施例结合流程示意图对本发明做进一步的阐述。

下面结合附图对本发明：基于常量时间复杂度的图像矩形邻域极大(极小)值计算方法 进行详细说明；本实施例是以本发明技术方案为前提，进行实施的，并结合了详细的实施方 式和过程，但本发明的保护范围不限于下述的实施例。

如图1所示，本实施例所描述的基于常量时间复杂度的图像矩形邻域极大(极小)值计 算方法可以分为以下四个步骤：

(1)给定一幅二维的灰度图像作为输入图像I，其宽度和高度分别记作w和h个像素，I 中像素记作(x，y)，则x∈{0，1，2，...，w-1}，y∈{0，1，2，...，h-1}。(x，y)的像素值记作I(x，y)，对 于8位二进制数所表示的灰度图像，最多有2⁸＝256个灰度值，因此I(x，y)∈{0，1，2，...，255}。 给定一个大小为(2r+1)×(2r+1)的二维矩形作为像素(x，y)的矩形邻域Ω(x，y)(其中r为自然 数)。

(2)根据步骤(1)中输入图像I构造一个三维的多层直方图V。V层数等于I的取值范 围，即256层，每层的直方图宽度和高度与I相同，即分别为w和h。用z表示V中层号，则 z∈{0，1，2，...，255}，第z层直方图记作V_z。遍历输入图像的所有像素，首先对V中所有的值根 据公式V_z(x，y)＝0进行初始化，然后根据公式V_I(x，y)(x，y)＝1对V进行设置。也就是说，对于 像素(x，y)，如果像素值I(x，y)和第z层直方图V_z的层号不相等，则V_z(x，y)＝0，反之，则设 置为V_z(x，y)＝1。

(3)根据步骤(1)中的矩形邻域Ω(x，y)和步骤(2)中构造的三维的多层直方图V，采用 基于常量时间复杂度的积分图算法分别计算V中每一层的直方图的图像矩形邻域求和，获得 一个矩形邻域求和的多层直方图V′。

对于第z层直方图V_z，首先对V_z求每一列的前序和，记作S_z。设置初始值S_z(x，-1)＝0，从 小到大遍历V_z中每一行，根据如下公式迭代计算对V_z每一列的前序和：

S_z(x，y)＝S_z(x，y-1)+V_z(x，y)

然后，利用S_z作为中间结果构造直方图V_z的积分图A_z。类似地，设置初始值A_z(-1，y)＝0， 从小到大遍历S_z中每一列，根据如下公式迭代计算对S_z每一行的前序和：

A_z(x，y)＝A_z(x-1，y)+S_z(x，y)

接下来，对于第z层直方图V_z，可以根据如下公式高效计算出对应的矩形邻域求和的直 方图V′_z：

V′_z＝A_z(x-r，y-r)+A_z(x+r，y+r)-A_z(x-r，y+r)-A_z(x+r，y-r)

(4)根据步骤(3)中的矩形邻域求和的多层直方图V′，基于常量时间复杂度计算出输入 图像中每一个像素所对应的矩形邻域求和值大于0的最大(最小)层的层号，即为所求的输 入图像的图像矩形邻域极大(极小)值。对于每个像素(x，y)，从大到小遍历矩形邻域求和的 多层直方图V′的每一层(即令z从255开始遍历到0)，第一个满足V′_z(x，y)＞0的层号z即为 所求的输入图像的图像矩形邻域极大值。类似地，对于每个像素(x，y)，从小到大遍历矩形邻 域求和的多层直方图V′的每一层(即令z从0开始遍历到255)，第一个满足V′_z(x，y)＞0的层 号z即为所求的输入图像的图像矩形邻域极小值。

至此我们就计算出了输入图像矩形邻域的极大(极小)值。