本发明涉及基于DWT(离散小波变换)的自适应特征点提取和图像匹配的方法、装置和计算机程序产品。在本发明中，采用haar小波对图像进行DWT分解。对分解后的低频部分进行特征提取来获得特征点及其相关的特征向量。最后，利用两个图像各自的特征点及其相关的特征向量对两个图像进行图像匹配。
1.一种用于自适应特征点提取和图像匹配的方法，包括以下步骤：(a)输入二维图像；
(b)利用DWT(离散小波变换)变换对所述二维图像进行N级分解，得到所述二维图像的低频部分；
(c)对所述低频部分进行特征提取，从而得到多个特征点和相关的特征向量；
(d)使用所述多个特征点和相关的特征向量对所述二维图像和参考图像进行图像匹配，其中，步骤(c)进一步包括以下子步骤：
(c.1)基于所述二维图像的所述低频部分，产生多尺度的差分空间：D(x，y，kσ)＝[G(x，y，kσ)-G(x，y，σ)]*I(x，y)其中，k为固定的系数，I(x，y)为所述二维图像的所述低频部分，G为高斯函数，σ为尺度因子；
(c.2)在所述差分空间中进行候选特征点检测，其中，将每一个待检测点和同一尺度的
8个相邻点和上下相邻尺度对应的9*2个共有26个点进行比较，如果该点大于26个点中的最大值或小于26个点中的最小值时，就认为是该待检测点是在该尺度下的一个候选特征点；
(c.3)在所述特征候选点检测中得到的多个特征候选点中进行筛选，得到特征点；以及(c.4)基于所述特征点的邻域梯度信息生成所述特征点的特征向量，其中，子步骤(c.3)进一步包括：
在所述差分空间中所述特征点所在的尺度中的，将所述特征点的16*16邻域划分为16个4*4的块，并在每个4*4的块上计算8个方向的梯度方向和梯度模的大小，从而形成8个特征向量，并在所述特征点的16*16邻域中形成128个特征向量，其中，所述删除低对比度的点进一步包括：
在每一个候选特征点处对D(x，y，kσ)进行二阶泰勒展开，并对泰勒展开式求导得到D′(x，y，kσ)，如果|D′(x，y，kσ)|＜0.03则删除该候选特征点；
针对每一个候选特征点，判断是否满足以下标准，若不满足则作为伪边缘点而被删除：其中，Dxx(x，y)表示D(x，y，kσ)对参数x的二阶偏导，Dxy(x，y)表示D(x，y，kσ)分别对参数x，y进行求偏导运算，Dyy(x，y)表示D(x，y，kσ)对参数y的二阶偏导，η＝10。
2.如权利要求1所述的方法，其中，步骤(d)进一步包括：基于所述二维图像中的特征点的特征向量和所述参考图像中的特征点的特征向量，计算所述二维图像和所述参考图像中每一对特征点的欧几里得距离，当所述欧几里得距离小于阈值时，判断该对特征点为匹配点。
3.如权利要求1或2所述的方法，其中，N＝1或2。
4.一种用于自适应特征点提取和图像匹配的装置，包括：(a)用于输入二维图像的模块；
(b)用于利用DWT(离散小波变换)变换对所述二维图像进行N级分解，得到所述二维图像的低频部分的模块；
(c)用于对所述低频部分进行特征提取，从而得到多个特征点和相关的特征向量的模块；
(d)用于使用所述多个特征点和相关的特征向量对所述二维图像和参考图像进行图像匹配，其中，模块(c)进一步包括：
(c.1)用于基于所述二维图像的所述低频部分，产生多尺度的差分空间的模块：D(x，y，kσ)＝[G(x，y，kσ)-G(x，y，σ)]*I(x，y)其中，k为固定的系数，I(x，y)为所述二维图像的所述低频部分，G为高斯函数，σ为尺度因子；
(C.2)用于在所述差分空间中进行候选特征点检测的模块，其中，将每一个待检测点和同一尺度的8个相邻点和上下相邻尺度对应的9*2个共有26个点进行比较，如果该点大于
26个点中的最大值或小于26个点中的最小值时，就认为是该待检测点是在该尺度下的一个候选特征点；
(C.3)用于在所述特征候选点检测中得到的多个特征候选点中进行筛选，得到特征点的模块；以及(C.4)用于基于所述特征点的邻域梯度信息生成所述特征点的特征向量的模块，其中，模块(C.3)进一步包括：用于删除低对比度的点的模块；以及
用于在所述差分空间中所述特征点所在的尺度中的，将所述特征点的16*16邻域划分为16个4*4的块，并在每个4*4的块上计算8个方向的梯度方向和梯度模的大小，从而形成8个特征向量，并在所述特征点的16*16邻域中形成128个特征向量的模块，其中，所述用于删除低对比度的点的模块进一步包括：用于在每一个候选特征点处对D(x，y，kσ)进行二阶泰勒展开，并对泰勒展开式求导得到D′(x，y，kσ)，如果|D′(x，y，kσ)|＜0.03则删除该候选特征点的模块；
用于针对每一个候选特征点，判断是否满足以下标准，若不满足则作为伪边缘点而被删除的模块：其中，Dxx(x，y)表示D(x，y，kσ)对参数x的二阶偏导，Dxy(x，y)表示D(x，y，kσ)分别对参数x，y进行求偏导运算，Dyy(x，y)表示D(x，y，kσ)对参数y的二阶偏导，η＝10。
5.如权利要求4所述的装置，其中，模块(d)进一步包括：用于基于所述二维图像中的特征点的特征向量和所述参考图像中的特征点的特征向量，计算所述二维图像和所述参考图像中每一对特征点的欧几里得距离，当所述欧几里得距离小于阈值时，判断该对特征点为匹配点的模块。
6.如权利要求4或5所述的装置，其中，N＝1或2。
基于DWT的自适应特征点提取和图像匹配
[0001] 联合研究
[0002] 本申请由北方工业大学与北京交通大学信息所联合研究，并得到以下基金资助：北京市属高等学校人才强教深化计划项目(PHR201008187)；国家自然科学基金(No.60903066，No.60972085)；北京市自然科学基金(No.4102049)，教育部新教师基金(No.20090009120006)。
技术领域
[0003] 本发明涉及基于DWT(离散小波变换)的自适应特征点提取和图像匹配的方法、装置和计算机程序产品。
背景技术
[0004] 基于内容的图像检索CBIR(content based image retrieval)是图像研究领域的热点问题之一。早期的CBIR方法，利用诸如颜色、纹理、形状等图像的底层特征进行图像检索，这些方法都是对图像底层的信息进行描述，虽然能够达到一定的效果，但是都不能详细的描述图像的尺度的缩放、移动、旋转、仿射等特性。因此几年来特征点提取算法及其应用成为了图像处理领域中的一个研究热点。
[0005] 本发明的思想是把图像看作一种信号流，一般信号的稳定部分包含图像的主要特征，它处于信号的低频部分，而高频部分包含了图像的噪声和图像对尺度变换不稳定的边缘信息，因此首先利用DWT变换把图像进行多级分解，提取子图像的低频信息，从而把图像进行压缩，并且滤除了产生边缘效应的不稳定点的边缘点，然后对图像进行特征提取，这样可以得到数量少且更稳定的特征点。试验证明：我们的方法提取的特征点更稳定，对各种几何变换的适应性更强，并且匹配精度更高，匹配速度更快。
附图说明
[0006] 图1示出了根据本发明的一个实施例的图像处理系统；
[0007] 图2示出了根据本发明的一些实施例的基于DWT的自适应特征点提取和图像匹配的流程图；
[0008] 图3示出了根据本发明的一些实施例的基于DWT的自适应特征点提取和图像匹配装置；
[0009] 图4示出了根据一些实施例的一种基于DWT的自适应特征点提取和图像匹配装置的细节；以及
[0010] 图5是根据本发明的一些实施例的DWT变换的图示。
具体实施方式
[0011] 现在参考附图来描述各种方案。在以下描述中，为了进行解释，阐述了多个具体细节以便提供对一个或多个方案的透彻理解。然而，显然，在没有这些具体细节的情况下也能够实现这些方案。
[0012] 如在本申请中所使用的，术语“组件”、“模块”、“系统”等等旨在指代与计算机相关的实体，例如但不限于，硬件、固件、硬件和软件的组合、软件，或者是执行中的软件。例如，组件可以是但不限于：在处理器上运行的进程、处理器、对象、可执行体(executable)、执行线程、程序、和/或计算机。举例而言，运行在计算设备上的应用程序和该计算设备都可以是组件。一个或多个组件可以位于执行进程和/或者执行线程内，并且组件可以位于一台计算机上和/或者分布在两台或更多台计算机上。另外，这些组件可以从具有存储在其上的各种数据结构的各种计算机可读介质执行。组件可以借助于本地和/或远程进程进行通信，例如根据具有一个或多个数据分组的信号，例如，来自于借助于信号与本地系统、分布式系统中的另一组件交互和/或者与在诸如因特网之类的网络上借助于信号与其他系统交互的一个组件的数据。
[0013] 图1示出了根据本发明的一个实施例的图像处理系统100。装置101为图像采集设备，用于依据现有技术中已知的任何图像采集技术来获取待处理的图像，所采集的图像可以经由通信装置直接传送给图像处理装置103，或者可以存储在存储装置105中以待后续处理。在本发明的一个实施例中，图像采集装置101直接在用户所访问的网页上获取与网页相关联的图像。
[0014] 由图像采集设备101所采集到的图像通过通信装置102以有线和/或无线的方式传送至图像处理装置103，该图像处理装置103对接收到的图像进行基于DWT的自适应特征点提取和图像匹配，以检测原图和目标图像的匹配相似程度。但是应该理解，图像处理装置103还可以对输入图像进行其它各种处理，例如图像去噪、图像配准、模式识别等等。
[0015] 图像处理装置103可以用通用处理器、数字信号处理器(DSP)、专用集成电路(ASIC)、现场可编程门阵列(FPGA)或其它可编程逻辑器件、分立门或晶体管逻辑器件、分立硬件组件或者设计为执行本文所述功能的其任意组合，来实现或执行。通用处理器可以是微处理器，但是可替换地，该处理器也可以是任何常规的处理器、控制器、微控制器或者状态机。处理器也可以实现为计算设备的组合，例如，DSP和微处理器的组合、多个微处理器的组合、一个或多个微处理器与DSP内核的组合或者任何其它此种结构。另外，至少一个处理器可以包括可操作以执行上述的一个或多个步骤和/或操作的一个或多个模块。
[0016] 当用ASIC、FPGA等硬件电路来实现图像处理装置103时，其可以包括被配置为执行各种功能的各种电路块。本领域技术人员可以根据施加在整个系统上的各种约束条件来以各种方式设计和实现这些电路，来实现本发明所公开的各种功能。例如，用ASIC、FPGA等硬件电路实现的图像处理装置103可以包括用于基于DWT的自适应特征点提取和图像匹配的电路及/或其它电路模块，其用来依据本文公开的各种基于DWT的自适应特征点提取和图像匹配方案来对输入图像执行图像匹配。本领域技术人员应该可以理解和认识到，本文所述的图像处理装置103可选地可以包括除用于基于DWT的自适应特征点提取和图像匹配的电路之外的其它任何可用电路模块，例如被配置为进行边缘检测、图像配准、模式识别的任何电路模块。以下结合图3的流程图详细描述了滤波器电路所实现的功能。
[0017] 图像存储装置105可以耦合至图像采集设备101及/或图像处理装置103，以存储图像采集设备101所采集的原始数据及/或经过图像处理装置103处理后的输出图像。
[0018] 图2示出了根据本发明的一些实施例的基于DWT的自适应特征点提取和图像匹配的流程图。
[0019] 在步骤201中，输入待处理的二维图像。在实施例中，待输入的二维图像可以来自图像采集装置101或图像存储装置105。
[0020] 在步骤202中，利用DWT变换对所述二维图像进行N级分解，得到所述二维图像的低频部分。
[0021] 同时参考图5。在本发明的一个实施例中，使用Haar小波的离散小波变换(DWT)对二维图像进行小波分解。在图5中的(b)中示出了对二维图像进行一级小波分解的图示，其中LL1为该图像的低频部分。在图5中的(c)中示出了一级小波分解的低频部分进行进一步小波分解从而得到二级小波分解的图示，其中LL2为该二维图像的二级DWT分解的低频部分。
[0022] 如图1所示的，输入的二维图像经过DWT变换生成了图像的低频分量(LL1)，图像垂直分量(LH1)，图像的水平分量(HL1)，图像的对角分量(HH1)。由于LL1中包含了图像大量的能量和主要特征，LH1，HL1和HH1部分包含了图像较多的垂直边缘信息，水平边缘信息等细节信息并且这些细节信息会在特征点提取中产生边缘效应问题。
[0023] 另外，二级分解中的低频部分LL2与LL1相比，包含更少的能量和主要特征。
[0024] 在本发明的实施例中，采用DWT的一级分解得到的LL1部分，或者DWT的一级分解得到的LL2部分来进行接下来的特征点提取处理。
[0025] 在步骤203中，对所述低频部分进行特征提取，从而得到多个特征点。
[0026] 具体而言，该步骤203主要有以下几个子步骤：
[0027] (c.1)基于所述二维图像的所述低频部分(LL1或LL2)，产生多尺度的差分空间：
[0028] D(x，y，kσ)＝[G(x，y，kσ)-G(x，y，σ)]*I(x，y)
[0029] 其中，k为固定的系数，I(x，y)为所述二维图像的所述低频部分，G为高斯函数，σ为尺度因子，并且可以根据实际情况采取多个值以便实现对图像的多尺度分析。
[0030] (c.2)在所述差分空间中进行候选特征点检测，其中，将每一个待检测点和同一尺度的8个相邻点(即3*3邻域中的8个相邻点)和上下相邻尺度对应的9*2个(即相应的9个3*3邻域点)共有26个点进行比较，如果该点是26个点中的最大或最小值时，就认为是该待检测点是在该尺度下的一个候选特征点。
[0031] (c.3)在所述特征候选点检测中得到的多个特征候选点中进行筛选，得到特征点和相关的特征向量。
[0032] 该子步骤(c.3)主要包括以下分析和删除操作：
[0033] ●删除低对比度的点。
[0034] 在每一个候选特征点处对D(x，y，kσ)进行二阶泰勒展开，并对泰勒展开式求导得到D′(x，y，kσ)，如果|D′(x，y，kσ)|＜0.03则删除该候选特征点。
[0035] ●删除伪边缘点；
[0036] 针对每一个候选特征点，判断是否满足以下标准，若不满足则作为伪边缘点而被删除：
[0037]
[0038] 其中，Dxx(x，y)表示D(x，y，kσ)对参数x的二阶偏导，Dxy(x，y)表示D(x，y，kσ)分别对参数x，y进行求偏导运算，Dyy(x，y)表示D(x，y，kσ)对参数y的二阶偏导，η＝10。
[0039] (c.4)基于所述特征点的邻域梯度信息生成所述特征点的特征向量。
[0040] 具体而言，对于每一个特征点而言，在差分空间中该特征点所在的尺度中的，将该特征点的16*16邻域划分为16个4*4的块，并在每个4*4的块上计算8个方向的梯度方向和梯度模的大小，从而形成8个特征向量，并在所述特征点的16*16邻域中形成128个特征向量，其中梯度方向和梯度模的计算是本领域公知的内容，因此在此不再赘述。
[0041] 在该步骤203结束时，能够获得所输入的二维图像的多个特征点及其相关的特征向量。
[0042] 在步骤204中，使用所得到的特征点，对原图像和目标图像进行图像匹配。
[0043] 具体而言，分别将原图像和目标图像作为输入图像输入步骤201中作为所述二维图像，并利用在步骤202-204中找到的原图像的多个特征点和目标图像的多个特征点，对这两个图像计算匹配精度。
[0044] 在一个实例中，通过利用原图像和目标图像的特征向量计算原图像中的每一个特征点和目标图像的每一个特征点的欧几里得距离。在一个实施例中，当一对特征点的距离小于某个阈值时，则判定该对特征点是一对匹配特征点。
[0045] 最后，依据以下等式计算匹配精度。
[0046]
[0047] 图3示出了根据本发明的一些实施例的基于DWT的自适应特征点提取和图像匹配装置。该装置的各个组件301-304的功能与以上方法中的步骤201-204类似，因此在此不再赘述。
[0048] 图4示出了根据一些实施例的一种基于DWT的自适应特征点提取和图像匹配装置的细节。基于DWT的自适应特征点提取和图像匹配装置400可以包括处理电路410和存储器420。其中处理电路410可以是通用处理器、数字信号处理器(DSP)、专用集成电路(ASIC)、现场可编程门阵列(FPGA)或其它可编程逻辑器件、分立门或晶体管逻辑器件、分立硬件组件或者设计为执行本文所述功能的其任意组合。处理电路410可以包含用来实现各种功能的各个电路模块。在一个实施例中，这些电路模块可以以分立组件的形式存在于处理电路410中。在另一个实施例中，这些电路模块可以是仅是电路的电子设计图中的功能模块，而并不在实际电路中存在。例如，在利用商用电子电路设计软件设计电路模块图并最终将其以电子方式写入电路中时，这些电路模块可分别地或者汇集地存在于该电子电路设计软件支持的一个或多个文件中，而在最后的电路写入阶段合并为单个设计。
[0049] 在一个实施例中，处理电路410可以包括：用于获得一输入二维图像的电路模块411；用于利用DWT变换对所述二维图像进行N级分解，得到所述二维图像的低频部分的电路模块413；用于对所述低频部分进行特征提取，从而得到多个特征点和相关的特征向量的电路模块415；用于使用所述多个特征点对所述二维图像和参考图像进行图像匹配，并得到匹配精度的电路模块417。在一个实施例中，存储器420可以用来存储该基于DWT的自适应特征点提取和图像匹配装置400的输入数据、输出数据以及处理电路410的各个电路模块的中间数据。例如，在一个实施例中，处理电路410可以将进行处理后的图像存储在存储器420中以便由电路模块415取回。在另一个实施例中，处理电路410可以将经过处理的图像存储在存储420中以便由电路模块417取回。存储器220可以是各种随机存取存储器(RAM)，其包括但不限于：RAM、DRAM、DDR RAM等等。存储器220通过总线连接至处理电路210。
[0050] 本发明还涵盖实现图2所述方法的计算机程序产品和处理器。
[0051] 尽管前述公开文件论述了示例性方案和/或实施例，但应注意，在不背离由权利要求书定义的描述的方案和/或实施例的范围的情况下，可以在此做出许多变化和修改。而且，尽管以单数形式描述或要求的所述方案和/或实施例的要素，但也可以设想复数的情况，除非明确表示了限于单数。另外，任意方案和/或实施例的全部或部分都可以与任意其它方案和/或实施例的全部或部分结合使用，除非表明了有所不同。
