基于量子模拟分叉算法实现形状匹配的方法

摘要

本发明涉及到一种基于量子模拟分叉算法实现形状匹配的方法。包括利用不同形状的数据集构建不同形状数据点之间的测地矩阵，初始化成对的数据的节点排列，从所述节点排列选取子节点集并构建对应的能量子矩阵，依据子节点集生成循环列表，由量子模拟分叉算法求解基于循环列表和能量子矩阵的一个耦合矩阵的循环变量的二进制参量。

说明书

技术领域

本发明主要涉及到计算机视觉领域，更确切的说，涉及到一种基于量子模拟分叉算法实现形状匹配的方法。

背景技术

计算机视觉又称之为机器视觉，通过利用计算机或者是其他的一些类似设备来帮助转化视线事物到图片的过程，从而进行三维世界的感知活动。计算机的快速发展，离不开神经心理学和心理学和认知科学方面的研究和发展，计算机视觉检测技术的发展方向基本就是对周围的三维空间进行感知和分析。一旦拥有这种能力，计算机不仅能感知到周围的总体环境而且还能具有对物体进行描述、识别理解和储存的能力。

要实现人工智能对视觉的计算机处理，很重要的方面是计算机视觉应用领域中须让计算机明白图像的信息，这就必须经过一系列的数据处理过程如数字图像处理。数字图像的处理包括五大步骤：图像预处理(去除噪声)、分割处理分割后区域、测量、图像判读和图像技术。根据抽象程度和处理方法的不同图像技术可分为三个层次：图像处理、图像分析和图像理解。这三个层次的有机结合也称为图像工程。

计算机视觉(Computer vision)则是用计算机实现人的视觉功能对客观世界三维场景的感知、识别和理解。视觉检测按其所处理的数据类型又大致可分为二值图像、灰度图像及彩色图像和深度图像的视觉检测。另外还有X射线、超声波和红外线检测。

形状是一种高级别的视觉信息，在计算机视觉的研究领域中，形状是一种描述物体的重要属性。形状表示与匹配作为计算机视觉领域中的关键且基础性问题，已在目标检测和医疗分析、古文字研究等诸多领域发挥了重要作用。各类形状匹配方法中，结合轮廓和区域信息的方法由于包含更加丰富的形状信息。为解决在形状匹配中由于强制约束线性等式而极大地限制了成功匹配的概率等问题，适用于寻找形状匹配的二次分配问题。

发明内容

本申请一种基于量子模拟分叉算法实现形状匹配的方法，包括：

利用不同形状的数据集构建不同形状数据点之间的测地矩阵，初始化成对的数据的节点排列，从所述节点排列选取子节点集并构建对应的能量子矩阵；

依据所述子节点集生成循环列表，由量子模拟分叉算法求解基于循环列表和能量子矩阵的一个耦合矩阵的循环变量的二进制参量。

上述的方法，其中：

所述子节点集是所述节点排列中被选取的匹配度不符和要求的成对的子节点集。

上述的方法，其中：

依据所述子节点集随机生成一个带有不相交的循环数的循环排列，改变生成的循环排列中每个不相交的循环数的位置，以生成一个包含循环排列的所述循环列表。

上述的方法，其中：

依据所述循环列表和所述能量子矩阵，构建以循环数为二进制参量的二元二次无限制优化问题的耦合矩阵。

上述的方法，其中：

用量子模拟分叉算法求解耦合矩阵的循环变量的二进制参量时，依据所述二进制参量改变数据的节点的排列位置。

上述的方法，其中：

所述测地矩阵d为方阵，其维度大小等于数据点的数量，对角线上的元素均为0以及矩阵元d

上述的方法，其中：

形状的节点数量为n时，能量矩阵大小为n

W

其中i,j和k,l分别是两个形状A和B的节点，该矩阵元用描述了两个匹配(i,k),(j,l)之间测地线距离的情况，d

上述的方法，其中：

所述循环数即2-循环c由2个位置构成，c＝(a,b)表示为：

其中x为循环c可视化的矩阵，作用是将排列P的位置a和位置b交换；

x

x

x

本申请涉及一种基于量子模拟分叉算法实现形状匹配的方法，包括：

S1、基于两个形状的数据集，构建不同形状数据点之间的测地矩阵，初始化成对的数据节点的排列；

S2、从成对的节点排列中选取匹配度不符和要求的成对的子节点集；

S3、依据所述子节点集构建对应的能量子矩阵；

S4、依据所述子节点集随机生成一个带有不相交的循环数的循环排列，改变生成的循环排列中每个不相交的循环数的位置，生成一个包含循环排列的循环列表；

S5、依据所述循环列表和所述能量子矩阵，构建以循环数为二进制参量的二元二次无限制优化问题的耦合矩阵；

S6、利用量子模拟分叉算法求解步耦合矩阵的循环变量的二进制参量，并依据所述的二进制参量改变数据节点的排列位置。

上述的方法，其中，还包括：

S7、重复S5-S6的操作，对S4生成的循环列表中的每个循环排列遍历一次；

S8、依据S7生成的更新点集的新排列，重复S2-S7的操作，直到结果收敛。

本申请涉及量子计算计算机视觉应用领域，本申请主旨是“为解决惩罚项在形状匹配中由于强制约束线性等式，极大地限制了成功匹配的概率以及求解变元数量庞大导致求解困难这些问题”。在可选的实施例中具体涉及一种量子迭代的子空间求解的方法并适用于寻找形状匹配的二次分配问题。因此本申请中基于量子模拟分叉算法实现形状匹配的方法含有量子迭代的子空间求解的方法之意。

形状匹配是许多计算机视觉和图形应用程序的核心，因为了解点之间的关系可以将信息传递到新的形状。其一直以来都是一个具有挑战性的问题，缘由是它们通常被表述为带有排列矩阵约束的组合二次分配问题(QAPS)，具有N-P难题的性质。量子计算如何有助于解决计算机视觉方面的问题仍然是一个相对未被探索的问题。

随着量子计算从理论考虑到实际实现，它在处理计算机视觉中的N-P难问题上变得越来越有吸引力。不幸的是，像这样的约束问题不能直接用量子计算解决，必须转换为二次无约束二进制优化问题，但这极大的限制了此类方法的成功概率。同时，形状匹配传统的组合优化求解方法对求解变元的数量要求过高，从而极大限制了匹配求解大规模节点形状问题的可能性。本申请的优势是解决这些问题。

附图说明

为使上述目的和特征及优点能够更加明显易懂，下面结合附图对具体实施方式做详细的阐释，阅读以下详细说明并参照以下附图之后，本申请的特征和优势将显而易见。

图1是构建测地矩阵并初始化成对的数据节点的排列。

图2是从成对的节点排列中选取匹配度不符和要求的成对的子节点集。

图3是基于量子模拟分叉算法实现形状匹配的方法的主要流程图。

图4是对生成的循环列表中的每个循环排列遍历一次。

图5是依据生成的更新点集的新排列而重复整个流程直到结果收敛。

具体实施方式

下面将结合各实施例，对本发明的方案进行清楚完整的阐述，所描述的实施例仅是本发明用作叙述说明所用的实施例而非全部的实施例，基于该等实施例，本领域的技术人员在没有做出创造性劳动的前提下所获得的方案属于本发明的保护范围。

参见图1，本申请提出使用模拟分叉优化算法求解形状匹配问题。

受利用非线性振荡网络进行量子绝热优化计算技术的启发，业界提出在经典计算机上利用模拟分叉(Simulated Bifurcation，简称SB)求解伊辛问题的方法。该方法对经典哈密顿系统在绝热演化过程中的分岔现象进行了数值模拟。相对于在经典计算机上模拟量子绝热演化现象，经典计算机更有效率地模拟哈密顿系统。与模拟退火每步更新一个变量以保证收敛相比，模拟分岔可同时更新多个甚至全部变量，加速问题的收敛并且使得模拟分岔算法可以很好地利用多核并行计算。

参见图1，基于量子模拟分叉算法实现形状匹配的方法，包括：利用不同形状的数据集构建不同形状数据点之间的测地矩阵，初始化成对的数据的节点排列，从所述节点排列选取子节点集并构建对应的能量子矩阵。例如利用不同形状(以一组形状A和B为例但允许形状的数目根据实际进行调整)的数据集，藉此来构建出不同形状如A和B数据点之间的测地矩阵如矩阵d。

参见图2，已知从节点排列选取子节点集(例如匹配度最差的成对子节点集被选取作为子节点集)并构建对应的能量子矩阵，在可选的实施例中，从节点排列LT选取一些子节点集LT1并构建对应的能量子矩阵W。较佳的是从成对的节点排列中选取匹配度最差的成对子节点集，依据匹配最差的节点集构建该点集对应的能量子矩阵。在可选的实施例中子节点集是节点排列中被选取的匹配度不符和要求的成对的子节点集，匹配度不符和要求在下文中是以匹配度最差的成对子节点集为例进行阐述。

参见图2，依据子节点集LT1生成循环列表，由量子模拟分叉算法求解基于循环列表和能量子矩阵的一个耦合矩阵的循环变量的二进制参量。在可选的范例中，依据生成的子节点集随机生成一个由不相交的循环数或循环信息(典型的例如是多个2-循环这样的循环数或循环信息)构成的循环排列，改变生成的循环排列中每个不相交的循环数或循环信息的位置例如可改变2-循环的位置，生成一个由循环排列构成的列表。

参见图2，依据生成的循环列表和之前中生成的能量子矩阵W，构建以循环为二进制参量的二元二次无限制优化问题的耦合矩阵。用量子模拟分叉算法求解耦合矩阵的循环变量的二进制参量时，依据二进制参量改变数据的节点的排列位置。关于循环列表和能量子矩阵以及改变数据的节点的排列位置等范例，下文会接续详细介绍。

参见图1，在可选的实施例中，假设测地矩阵d为方阵，矩阵维度的大小等于数据点的数量，对角线上的元素均为0以及矩阵元d

参见图1，在可选的实施例中，形状的节点数量为n，能量矩阵大小为n

W

其中i,j和k,l分别是两个形状A和B的节点，矩阵元描述两个匹配(i,k),(j,l)之间测地线距离的情况。例如d

参见图1，在可选的实施例中，循环数如2-循环c由2个位置构成，c＝(a,b)表示为：

其中x为循环c可视化的矩阵，作用是将排列P的位置a和位置b交换。

注意x

以及x

再者x

参见图3，在可选的实施例中，基于量子模拟分叉算法实现形状匹配的方法，其主要的流程包括如下的步骤S1-S6。

参见图3，S1、基于两个形状的数据集，构建不同形状数据点之间的测地矩阵，初始化成对的数据节点的排列。

参见图3，S2、从成对的节点排列中选取匹配度不符和要求的成对的子节点集。

参见图3，S3、依据所述子节点集构建对应的能量子矩阵。

参见图3，S4、依据子节点集随机生成一个带有不相交的循环数的循环排列，改变生成的循环排列中每个不相交的循环数的位置，生成包含循环排列的循环列表。

参见图3，S5、依据循环列表和所述能量子矩阵，构建以循环数为二进制参量的二元二次无限制优化问题的耦合矩阵。

参见图3，S6、量子模拟分叉算法求解步耦合矩阵的循环变量的二进制参量，并依据所述的二进制参量改变数据节点的排列位置。

量子计算是对电子芯片计算方式的补充，然而经典的立体匹配算法在量子芯片上的运行无法按照其在电子芯片上的方式进行处理。

由于本文与量子相关，关于量子器件和量子数据的相关内容如下文。

本文所谓“量子器件”包含已知的量子计算设备和量子芯片等，也可以用量子硬件替代量子器件这类术语。典型的“量子器件”包括但不限制于：量子计算机、量子信息处理系统或量子密码系统、量子模拟器、处理量子数据的所有种类的装置、设备和机器。

本文所谓“量子数据”包含由量子系统携带、保存或存储的信息或数据，最小的非平凡系统是量子比特，即定义量子信息单位的系统。应当理解，术语“量子比特”包括在相应上下文中可以适当地近似为二能级系统的所有的量子系统。这种量子系统举例来说通常包括了典型的原子、电子、光子、离子或超导量子比特等等。

虽然立体匹配问题基于经典求解器取得了可接受的性能，但是经典算法中的求解模块运算具有高度并行性并消耗大量计算资源。本发明基于模拟分岔算法替换经典立体匹配算法中的某一模块，并用纯量子线路与量子经典混合算法来处理立体匹配问题。从而使得量子芯片和电子芯片能够协同工作用于处理立体匹配问题。

参见图4，在可选的实施例中，基于量子模拟分叉算法实现形状匹配的方法，其主要的流程包括如下的步骤S7。步骤S7主要是重复S5-S6的操作，对S4生成的循环列表中的每个循环排列遍历一次。

参见图5，在可选的实施例中，基于量子模拟分叉算法实现形状匹配的方法，其主要的流程包括如下的步骤S8。主要是依据S7生成的更新点集(更新点集例如是S7所生成的一个最差点集)的新排列，重复S2-S7的操作，直到结果收敛。

参见图3，在可选的实施例中，本申请提供了一种实现形状匹配的方法，是基于量子启发的模拟分叉算法求解的新型量子迭代方法。相比于现有的形状匹配方法，该方法通过循环集合来表示排列，再通过二进制变量参数化循环使用，不需要强制任何类型的约束而且可以在解空间中更有效的搜索，提升匹配解的质量。

参见图3，在可选的实施例中，本申请提供了一种基于量子模拟分叉算法实现形状匹配的方法，具体方案包括八个步骤。

步骤一：基于两个形状的数据集，构建不同形状数据点之间的测地矩阵，初始化成对的数据节点的排列P

步骤二：从成对的节点排列中选取匹配度最差的成对子节点集。

步骤三：依据步骤二中得到的匹配最差的节点集构建该点集对应的能量子矩阵。

步骤四：依据步骤二中生成的子节点集随机生成一个由不相交的多个2-循环构成的循环排列，改变生成的循环排列中每个不相交的2-循环的位置，生成一个由循环排列构成的列表。

步骤五：依据步骤四中生成的循环列表和步骤三中生成的能量子矩阵，构建以循环为二进制参量的二元二次无限制优化问题的耦合矩阵。

步骤六：利用量子模拟分叉算法(允许使用现有技术的分叉算法)求解步骤五中生成的耦合矩阵的循环变量的二进制参量，并依据二进制变量改变节点的排列位置。

步骤七：重复步骤五到步骤六的操作，最主要的是，需要对步骤四生成的列表中的每个循环排列遍历一次。

步骤八：依据步骤七生成的一个最差点集(例如称作一个更新点集)的新排列重复步骤二到步骤七的操作，直到结果收敛。

参见图3，在可选的实施例中，步骤一中，分别依据两个形状节点的特性与流形面构建两形状对应的测地矩阵d。所述测地线矩阵d为方阵，维度大小等于点的数量，对角线上的元素均为0，矩阵元d

参见图3，在可选的实施例中，步骤一中，使用两特性矩阵的点积构建两位置坐标间的关联矩阵，所述点积中，对第二个形状的特性矩阵转置。通过求解所述关联矩阵的线性分配解得到两形状节点之间较为粗糙的初始匹配排列。

参见图3，在可选的实施例中，步骤二中，依据匹配两点在两形状中与其它各点测地距离和的差异体现匹配程度的优劣。

参见图3，依据的匹配原理为：若两形状A、B完全相同且A、B上的每个点都完美匹配，则形状A中某点到其他点的测地距离一定等于形状B中某匹配点到其他匹配点的测地距离，即A、B上的匹配点到其他各点的测地距离之和相同，差异为0；两匹配点与其他各点测地距离和的绝对值之差越大，则两点的匹配程度就越差。

参见图3，基于该原理，将两形状所有匹配点与其他各点测地距离和的绝对值之差的总和视为匹配能量，匹配能量为0时，则两形状完美匹配。

参见图3，在可选的实施例中，步骤二中，依据匹配原理，对各匹配点与其它点测地距离和的绝对值之差进行排序，挑选出特定数量的绝对值之差最大的成对点作为坏点而且例如坏点在成对排列中匹配度最差。

参见图3，在可选的实施例中，步骤三中，基于形状匹配的能量矩阵W构建的前述步骤二中得到的坏点的能量子矩阵W

参见图3，在可选的实施例中，形状的节点数量为n时，所述能量矩阵大小为n

W

其中，i,j和k,l分别是形状A和B的节点，该矩阵元描述了两个匹配(i,k),(j,l)之间测地线距离的情况。即反映了这两个匹配对的匹配程度，既而所述能量矩阵描述所有成对特性的匹配程度。

参见图3，在可选的实施例中，步骤三中，若仅取能量矩阵的子集作为子能量矩阵譬如即令(W

其中，V\S表示成对节点集V去掉选取子点集S的部分。将所述步骤二中得到坏点作为选取子集S，得到坏点的子能量矩阵。

参见图3，在可选的实施例中，步骤四中，依据所述步骤二得到的坏点，生成多个不相交的2-循环。所述2-循环c由2个位置构成，c＝(a,b)表示为

其中x为循环c可视化的矩阵，维度与坏点数量相同，其作用是对于排列P，将P的位置a和b交换。所述不相交即为多个循环的位置均不重叠，即而各个不相交的循环排列的可视化总矩阵X可描述为各个循环矩阵x的乘积形式X＝Π

参见图3，在可选的实施例中，步骤四中，生成的单个循环排列表达能力有限。基于前一个循环排列变换生成新的循环排列的方法可以生成所有可能的排列，方法为：对于循环排列为

当n

参见图3，在可选的实施例中，步骤五中，将循环排列的每个循环c

乘积关系与矩阵表示仅当所有循环独立的条件下成立。

参见图3，步骤五中，基于形状匹配的能量表示E(P

其中v(P

其中，Q为子矩阵W

基于所述矩阵元的表示，可构建二元二次无约束优化问题。

参见图3，在可选的实施例中，步骤六中，基于步骤五中得到的耦合矩阵，使用量子模拟分叉算法求解所述执行参量α。量子模拟分叉算法基于相干伊辛机启发，利用量子物理的自然演化，有效的将2的指数次方量级的运算减少为平方量级。

参见图3，在可选的实施例中，步骤六中，基于量子模拟分叉算法的求解结果，对当前排列执行特定位置的交换。对于每一个循环对应的二进制参量α

参见图5，在可选的实施例中，步骤七中，将步骤六中所述位置交换后的排列作为当前排列。对于每一个循环，均生成一个耦合矩阵Q，从而此时可应用量子模拟分叉算法求解执行参量，更新当前排列。

参见图5，在可选的实施例中，步骤八中，一个步骤为所述步骤五中循环列表的每个循环均对排列进行更新，基于更新后的排列对坏点的成对点集重新匹配直到收敛。所述收敛为步骤二中所述匹配能量迭代结果不变为止。

本申请的优势包括以下各项：首先是基于量子比特的数据表达能力更优。其次基于模拟分岔算法的匹配法可在量子计算设备和量子芯片上高度并行处理数据特征。再者基于模拟分岔算法的匹配算法相比经典算法均具有更广泛的应用场景。以及基于参数化量子线路的模型训练过程中能更快收敛至稳定状态。

以上通过说明和附图的内容，给出了具体实施方式的特定结构的典型实施例，上述申请内容提出了现有的较佳实施例，但这些内容并不作为局限。对于本领域的技术人员而言在阅读上述说明后，各种变化和修正无疑将显而易见。因此，所附的权利要求书应当看作是涵盖本发明的真实意图和范围的全部变化和修正。在权利要求书范围之内的任何和所有等价的范围与内容，都应认为仍属本发明的意图和范围内。