插值三角形形成方法及装置

摘要

本发明公开了一种插值三角形形成方法及装置，为解决现有插值三角形形成过程中计算量大，效率低，实时性差等问题而设计。所述方法包括：根据待补偿质心的坐标，在靶标像点质心阵列上获取距离所述待补偿质心的最近靶标像点质心的行列坐标；获取最近靶标像点质心所在四邻域中的四个边缘靶标像点质心的行列坐标；依据所述待补偿质心、所述四个边缘靶标像点质心的行列坐标，通过距离计算以及向量计算，获得形成所述插值三角形的三个靶标像点质心的行列坐标。本实施例所述的方法及装置，具有计算量小、搜索效率高等优点。

权利要求

1.一种插值三角形形成方法，其特征在于，所述方法包括：

根据待补偿质心的坐标，在靶标像点质心阵列上获取距离所述待补偿质心的最近靶标像点质心的行列坐标；

获取最近靶标像点质心所在四邻域中的四个边缘靶标像点质心的行列坐标；

依据所述待补偿质心、所述四个边缘靶标像点质心的行列坐标，通过距离计算以及向量计算，获得形成所述插值三角形的三个靶标像点质心的行列坐标；

其中，所述通过距离计算以及向量计算，获得形成所述插值三角形的三个靶标像点质心的行列坐标包括：计算四个所述边缘靶标像点质心与所述待补偿质心的距离，最小距离所对应的边缘靶标像点质心为最近边缘靶标像点质心；

根据第一向量及第二向量的向量积，确定所述待补偿质心所在靶标方格；所述第一向量为所述最近靶标像点质心与所述待补偿质心连线构成的向量；所述第二向量为所述近靶标像点质心与所述最近边缘靶标像点质心连线构成的向量；

计算所述待补偿质心与所述待补偿质心所在靶标方格的四个靶标像点质心之间的距离；

所述待补偿质心距离最近的三个靶标像点质心为形成所述插值三角形的三个靶标像点质心的行列坐标。

2.根据权利要求1所述的方法，其特征在于，所述根据质心的坐标，在靶标像点质心阵列上获取距离所述待补偿质心的最近靶标像点质心的行列坐标包括：将所述待补偿质心的坐标代入靶标系数式，计算获得初步行值以及初步列值；

分别对所述初步行值以及初步列值进行四舍五入取整处理，获得第一行号以及第一列号；所述第一行号为最近靶标像点质心在所述靶标像点质心阵列中的行号，所述第一列号为最近靶标像点质心在所述靶标像点质心阵列中的列号。

3.根据权利要求2所述的方法，其特征在于，所述靶标系数式为：ri＝A1xi+B1yi+D1

ci＝A2xi+B2yi+D2

其中，所述xi为待代入的所述待补偿质心横坐标值；所述yi待代入的所述待补偿质心的纵坐标值；所述ri为所述初步行值；所述ci为初步列值；所述A1为已知的第一系数；所述A2为已知的第二系数；所述B1为已知的第三系数；所述B2为已知的第四系数；所述D1为已知的第一修正系数；所述D2为已知的第二修正系数。

4.一种插值三角形形成装置，其特征在于，所述装置包括：

第一获取单元，根据待补偿质心的坐标，在靶标像点质心阵列上获取距离所述待补偿质心的最近靶标像点质心的行列坐标；

第二获取单元，用以获取最近靶标像点质心所在四邻域中的四个边缘靶标像点质心的行列坐标；

形成单元，用以依据所述待补偿质心、所述四个边缘靶标像点质心的行列坐标，通过距离计算以及向量计算，获得形成所述插值三角形的三个靶标像点质心的行列坐标；

其中，所述形成单元包括：

第一计算模块，用以计算四个所述边缘靶标像点质心与所述待补偿质心的距离，最小距离所对应的边缘靶标像点质心为最近边缘靶标像点质心；

确定模块，用以根据第一向量及第二向量的向量积，确定所述待补偿质心所在靶标方格；所述第一向量为所述最近靶标像点质心与所述待补偿质心连线构成的向量；所述第二向量为所述近靶标像点质心与所述最近边缘靶标像点质心连线构成的向量；

第二计算模块，用以计算所述待补偿质心与所述待补偿质心所在靶标方格的四个靶标像点质心之间的距离；

确定模块，用以所述待补偿质心距离最近的三个靶标像点质心为形成所述插值三角形的三个靶标像点质心的行列坐标。

5.根据权利要求4所述的装置，其特征在于，所述第一获取单元具体用以将所述待补偿质心的坐标代入靶标系数式，计算获得初步行值以及初步列值；及分别对所述初步行值以及初步列值进行四舍五入取整处理，获得第一行号以及第一列号；所述第一行号为最近靶标像点质心在所述靶标像点质心阵列中的行号，所述第一列号为最近靶标像点质心在所述靶标像点质心阵列中的列号。

6.根据权利要求5所述的装置，其特征在于，所述靶标系数式为：ri＝A1xi+B1yi+D1

ci＝A2xi+B2yi+D2

其中，所述xi为待代入的所述待补偿质心横坐标值；所述yi待代入的所述待补偿质心的纵坐标值；所述ri为所述初步行值；所述ci为初步列值；所述A1为已知的第一系数；所述A2为已知的第二系数；所述B1为已知的第三系数；所述B2为已知的第四系数；所述D1为已知的第一修正系数；所述D2为已知的第二修正系数。

说明书

插值三角形形成方法及装置

[0001] 技术邻域

[0002] 本发明涉及计算机邻域的像增强器误差补偿技术，尤其涉及一种插值三角形形成方法及装置。

背景技术

[0003] 现有技术中提出了一种像增强器误差分离并进行补偿的方法包括：首先采集图像中各靶标像点质心的质心数据，建立像增强器误差模型并利用优化算法进行求解，得到质心位置与像增强误差的映射关系；最后通过三角形插值的方法对像增强器误差进行补偿。

[0004] 像增强器误差补偿的一个关键步骤是搜索插值三角形，对于每一个输入的待补偿质心坐标，需要从大量的靶标像点质心中搜索到能连线包围待补偿质心，且距离质心最近的三个靶标像点质心构成插值三角形，根据插值三角形三点的像素坐标和误差对输入坐标进行补偿。现有的搜索插值三角形方法是计算输入的待补偿质心与所有靶标像点质心的距离，对所有距离进行搜索，找到距离最小的三个靶标像点质心构成插值三角形。这种方法无疑计算量大，效率低，故提出一种计算量小，效率高，实时性高的方法是现有技术亟待解决的一个问题。

[0005] 理想靶标是由棋盘状均匀分布的一组点阵构成的，如图1（a）所示；由于光纤形变造成靶标像点质心之间相对位置、距离发生扭曲变形，如图1（b）所示。因此现有的搜索插值三角形方法可能会造成错误。第一种错误是搜索到的三个靶标像点质心连线不包围待补偿质心，如图2（a）所示，由于E点在c2列靶标像点质心中左偏，且待补偿质心距离BE连线较近，造成原有方法搜索到距离待补偿质心最近的三点为B、E、F，但B、E、F三点构成的三角形并不包围待补偿质心；第二种错误是搜索到的三点均属于同行或同列靶标像点质心，如图2（b）所示，由于E点在r2行中上偏，且待补偿质心距离E点较近，造成搜索到距离待补偿质心最近的三点为D、E、F，但D、E、F三点均属于r2行靶标像点质心，在分布正常的点阵靶标中应该构成一条直线。

发明内容

[0006] 有鉴于此，本发明提供了一种插值三角形形成方法以及装置，在形成插值三角性的过程中计算量小，效率高。

[0007] 为达到上述目的，本发明的技术方案是这样实现的：

[0008] 本发明第一方法提供一种插值三角形形成方法，所述方法包括：

[0009] 根据待补偿质心的坐标，在靶标像点质心阵列上获取距离所述待补偿质心的最近靶标像点质心的行列坐标；

[0010] 获取最近靶标像点质心所在四邻域中的四个边缘靶标像点质心的行列坐标；

[0011] 依据所述待补偿质心、所述四个边缘靶标像点质心的行列坐标，通过距离计算以及向量计算，获得形成所述插值三角形的三个靶标像点质心的行列坐标。

[0012] 优选地，所述通过距离计算以及向量计算，获得形成所述插值三角形的三个靶标像点质心的行列坐标包括：

[0013] 计算四个所述边缘靶标像点质心与所述待补偿质心的距离，最小距离所对应的边缘靶标像点质心为最近边缘靶标像点质心；

[0014] 根据第一向量及第二向量的向量积，确定所述待补偿质心所在靶标方格；所述第一向量为所述最近靶标像点质心与所述待补偿质心连线构成的向量；所述第二向量为所述近靶标像点质心与所述最近边缘靶标像点质心连线构成的向量；

[0015] 计算所述待补偿质心与所述待补偿质心所在靶标方格的四个靶标像点质心之间的距离；

[0016] 所述待补偿质心距离最近的三个靶标像点质心为形成所述插值三角形的三个靶标像点质心的行列坐标。

[0017] 优选地，所述根据质心的坐标，在靶标像点质心阵列上获取距离所述待补偿质心的最近靶标像点质心的行列坐标包括：

[0018] 将所述待补偿质心的坐标代入靶标系数式，计算获得初步行值以及初步列值；

[0019] 分别对所述初步行值以及初步列值进行四舍五入取整处理，获得第一行号以及第一列号；所述第一行号为最近靶标像点质心在所述靶标像点质心阵列中的行号，所述第一列号为最近靶标像点质心在所述靶标像点质心阵列中的列号。

[0020] 优选地，所述靶标系数式为：

[0021] ri=A1xi+B1yi+D1

[0022] ci=A2xi+B2yi+D2

[0023] 其中，所述xi为待代入的所述待补偿质心横坐标值；所述yi待代入的所述待补偿质心的纵坐标值；所述ri为所述初步行值；所述ci为初步列值；所述A1为已知的第一系数；所述A2为已知的第二系数；所述B1为已知的第三系数；所述B2为已知的第四系数；所述D1为已知的第一修正系数；所述D2为已知的第二修正系数。

[0024] 本发明第二方面提供一种插值三角形形成装置，所述装置包括：

[0025] 第一获取单元，根据待补偿质心的坐标，在靶标像点质心阵列上获取距离所述待补偿质心的最近靶标像点质心的行列坐标；

[0026] 第二获取单元，用以获取最近靶标像点质心所在四邻域中的四个边缘靶标像点质心的行列坐标；

[0027] 形成单元，用以依据所述待补偿质心、所述四个边缘靶标像点质心的行列坐标，通过距离计算以及向量计算，获得形成所述插值三角形的三个靶标像点质心的行列坐标。

[0028] 进一步地，所述形成单元包括：

[0029] 第一计算模块，用以计算四个所述边缘靶标像点质心与所述待补偿质心的距离，最小距离所对应的边缘靶标像点质心为最近边缘靶标像点质心；

[0030] 确定模块，用以根据第一向量及第二向量的向量积，确定所述待补偿质心所在靶标方格；所述第一向量为所述最近靶标像点质心与所述待补偿质心连线构成的向量；所述第二向量为所述近靶标像点质心与所述最近边缘靶标像点质心连线构成的向量；

[0031] 第二计算模块，用以计算所述待补偿质心与所述待补偿质心所在靶标方格的四个靶标像点质心之间的距离；

[0032] 确定模块，用以所述待补偿质心距离最近的三个靶标像点质心为形成所述插值三角形的三个靶标像点质心的行列坐标。

[0033] 进一步地，所述第一获取单元具体用以将所述待补偿质心的坐标代入靶标系数式，计算获得初步行值以及初步列值；及分别对所述初步行值以及初步列值进行四舍五入取整处理，获得第一行号以及第一列号；所述第一行号为最近靶标像点质心在所述靶标像点质心阵列中的行号，所述第一列号为最近靶标像点质心在所述靶标像点质心阵列中的列号。

[0034] 进一步地，所述靶标系数式为：

[0035] ri=A1xi+B1yi+D1

[0036] ci=A2xi+B2yi+D2

[0037] 其中，所述xi为待代入的所述待补偿质心横坐标值；所述yi待代入的所述待补偿质心的纵坐标值；所述ri为所述初步行值；所述ci为初步列值；所述A1为已知的第一系数；所述A2为已知的第二系数；所述B1为已知的第三系数；所述B2为已知的第四系数；所述D1为已知的第一修正系数；所述D2为已知的第二修正系数。

[0038] 本发明实施例中所述的插值三角形的形成方法及装置，首先根据待补偿质心坐标确定出最近的靶标像点质心，即将搜索范围由整个靶标像点质心靶标像点质心阵缩小到最近靶标像点质心所在的八邻域，再通过距离计算以及向量计算，获得形成所述插值三角形的三个靶标像点质心，故而相对于计算待补偿质心与每一靶标像点质心之间的距离，计算量大大的减少了，从而插值三角形的形成效率大大的提高了。

附图说明

[0039] 图1（a）为靶标点和变形前的靶标像点质心局部示意图；

[0040] 图1（b）为靶标点和变形后的靶标像点质心局部示意图；

[0041] 图2（a）为现有方法形成插值三角性的错误情况示意图之一；

[0042] 图2（b）为现有方法形成插值三角性的错误情况示意图之一；

[0043] 图3为本发明第一实施例所述的插值三角形形成方法的流程示意图之一；

[0044] 图4为本发明第一实施例中所述靶标像点质心阵的局部示意图；

[0045] 图5为本发明第一实施例中所述的步骤S130的流程示意图；

[0046] 图6为本发明第一实施例中所述的靶标像点质心阵局部与质心的位置关系示意图；

[0047] 图7为本发明第一实施例中所述的靶标方格与质心的位置关系示意图；

[0048] 图8为本发明第一实施例中所述的插值三角形形成方法的流程示意之二；

[0049] 图9为本发明第二实施例中所述的插值三角形形成装置的结构示意图之一；

[0050] 图10为本发明第二实施例中所述的插值三角形形成装置的结构示意图之二。

具体实施方式

[0051] 以下结合说明书附图以及具体实施例对本发明的技术方案做进一步的详细阐述。

[0052] 第一实施例：

[0053] 如图3所示，本实施例提供了一种插值三角形形成方法；

[0054] 所述方法包括：

[0055] 步骤S110：根据待补偿质心的坐标，在靶标像点质心阵列上获取距离所述待补偿质心的最近靶标像点质心的行列坐标；

[0056] 步骤S120：获取最近靶标像点质心所在四邻域中的四个边缘靶标像点质心的行列坐标；

[0057] 步骤S130：依据所述待补偿质心、所述四个边缘靶标像点质心的行列坐标，通过距离计算以及向量计算，获得形成所述插值三角形的三个靶标像点质心的行列坐标。

[0058] 在所述步骤S110中的根据待补偿质心的坐标，在靶标像点质心阵列上获取距离所述待补偿质心的最近靶标像点质心的行列坐标的方法步骤如下：

[0059] 步骤1：将所述待补偿质心的坐标代入靶标系数式，计算获得初步行值以及初步列值；

[0060] 步骤2：分别对所述初步行值以及初步列值进行四舍五入取整处理，获得第一行号以及第一列号；所述第一行号为最近靶标像点质心在所述靶标像点质心阵列中的行号，所述第一列号为最近靶标像点质心在所述靶标像点质心阵列中的列号。

[0061] 在所述靶标像点质心阵中，每一靶标像点质心的坐标（x，y）与靶标像点质心在靶标像点质心阵的坐标（r,c）存在映射关系，所述映射关系可以表达为：

[0062] x=f(r,c)

[0063] y=g(r,c)

[0064] 若靶标像点质心阵不扭曲或扭曲程度不大，则上述映射关系通常为线性映射关系，可以表达为：

[0065] x=a1r+b1c+d1

[0066] y=a2r+b2c+d2

[0067] 进而可以进一步的改写乘以（x，y）为自变量，（r,c）为因变量的表示式：

[0068] r=A1x+B1y+D1

[0069] c=A2x+B2y+D2

[0070] 进而根据上述规律，提出了如下通过质心求取最近靶标像点质心的公式组。

[0071] ri=A1xi+B1yi+D1

[0072] ci=A2xi+B2yi+D2

[0073] 从而当质心的坐标确定了之后，可以将质心的坐标（xi，yi）代入上述，就可以得到一个（ri,ci），当所述待补偿质心没有落在靶标像点质心上时，得到的ri以及ci都不会是整数，故当进行四舍五入后，即得到了离待补偿质心最近的最近靶标像点质心的坐标。

[0074] 其中，所述A1为已知的第一系数；所述A2为已知的第二系数；所述B1为已知的第三系数；所述B2为已知的第四系数；所述D1为已知的第一修正系数；所述D2为已知的第二修正系数。不同的靶标像点质心阵，对应的A1、A2、B1、B2、D1以及D2不同，在进行插值三角形形成之前，可以根据前述步骤进行求解，并存储好所述A1、A2、B1、B2、D1以及D2。所述A1、A2、B1、B2、D1以及D2可以形成系数矩阵 进行存储。

[0075] 采用上述方法可以快速的确定离质心最近的最近靶标像点质心坐标，具有计算量小，计算复杂低的优点。在具体的实现过程中，所述系数矩阵的形成，在使用靶标像点质心阵之前、定期或不定期的根据当前所述靶标像点质心阵的情况进行更新，以使所述系数矩阵可以反映当前靶标像点质心阵更加真实的情况，从而充分考虑到靶标像点质心阵的变形等因素，以降低所构成的三角形没有包围所述待补偿质心现象出现的概率。靶标像点质心靶标像点质心靶标像点质心靶标像点质心如图4所示，靶标像点质心D、B、H以及F连线所构成的区域为靶标像点质心E的四邻域，靶标像点质心A、C、I以及G连线所构成的区域为靶标像点质心E的八邻域。其中，D、B、H以及F为靶标像点质心四邻域的边缘靶标像点质心。

[0076] 所述步骤S120中获取最近靶标像点质心所在四邻域中的四个边缘靶标像点质心的行列坐标可为：从存储器中读取预先存储的所述最近靶标像点质心的上、下、左、右四个方位最近靶标像点质心的坐标即可。如当前最近的靶标像点质心E的行列数为(r0,c0)，则B的行列数为(r0+1,c0)、H的行列数为(r0,c0-1)、D的行列数为(r0-1,c0)、F的行列数为(r0,c0+1)。在具体的实现过程中所述行列坐标还可以转换成像素坐标。

[0077] 为了能快速根据行列坐标读取对所有靶标像点质心的行列坐标与像素坐标、误差建立映射关系。

[0078] 在进行插值三角形搜索之前，需要将所有靶标像点质心的靶标数据存入存储空间中。一个靶标像点质心对应四种数据类型，分别是X轴方向坐标、Y轴方向坐标、X轴方向误差、Y轴方向误差。为了在误差补偿的过程中实现快速读取任意一个特定的靶标数据，需要根据每个靶标数据对应的行数、列数、数据类型将每个靶标数据存入特定的存储空间。因此每一个靶标数据的存储地址中要包含该靶标数据对应的行数、列数、数据类型信息。

[0079] 根据行列数与坐标的映射关系，可以从存储器或数据库中直接获取D、B、H以及F的坐标。

[0080] 如图5所示，所述步骤S130包括：

[0081] 子步骤S131：计算四个所述边缘靶标像点质心与所述待补偿质心的距离，最小距离所对应的边缘靶标像点质心为最近边缘靶标像点质心；

[0082] 子步骤S132：根据第一向量及第二向量的向量积，确定所述待补偿质心所在靶标方格；所述第一向量为所述最近靶标像点质心与所述待补偿质心连线构成的向量；所述第二向量为所述近靶标像点质心与所述最近边缘靶标像点质心连线构成的向量；

[0083] 子步骤S133：计算所述待补偿质心与所述做质心所在靶标方格的四个靶标像点质心之间的距离；

[0084] 子步骤S134：所述待补偿质心距离最近的三个靶标像点质心所形成的三角形，为所述插值三角形。

[0085] 在子步骤S131中，获取了质心与四个边缘靶标像点质心的距离分别为D1、D2、D3以及D4，两两比较即可得到最小距离；最小距离所述对应的边缘靶标像点质心即为所述最近边缘靶标像点质心，存储下所述最近边缘靶标像点质心的行列号以及坐标等信息。

[0086] 所述步骤S132具体又包括：

[0087] 如图6所示，将最近靶标像点质心的左上、左下、右下、左上四个靶标方格分别标记为靶标方格1、2、3、4；

[0088] 求最近靶标像点质心到最近边缘靶标像点质心向量，与最近靶标像点质心到待补偿质心点向量的向量积。

[0089] 设向量积标志位为V；若向量积为正，则V=0，此时待补偿质心在最近靶标像点质心与最近边缘靶标像点质心的逆时针方向；否则V=1，此时待补偿质心在最近靶标像点质心与最近边缘靶标像点质心的顺时针方向。其中，所述第一向量的起点为最近靶标像点质心，方向为由最近靶标像点质心指向所述待补偿质心。第二向量的起点为最近靶标像点质心，方向为由最近靶标像点质心指向所述最近边缘靶标像点质心。

[0090] 求取质心所在标靶方格S值；若Pmin+V-1=0，则最近方格序号S=4；否则，最近方格序号S=Pmin+V-1其中，所述Pmin靶标像点质心按照以最近靶标像点质心为中心，上、左、下以及右的计数方法，最近靶标像点质心的序号。在图4中所述Pmin=3。

[0091] 其中，所述子步骤S133具体包括：

[0092] 如图7所示，质心（在图5中用五角星表示）所在靶标方格序号为S；将最近靶标像点质心记为方格点1，从点1开始按逆时针方向将靶标方格S其余三靶标像点质心标记为方格点2、3、4。

[0093] 根据最近靶标像点质心坐标(x0,y0)、四邻域靶标像点质心坐标(x1,y1)、(x2,y2)、(x3,y3)、(x4,y4)和最靶标方格S可得到1、2、3、4号靶标像点质心的行列数及1、2、4号方靶标像点质心的坐标。1-4号靶标像点质心行列数分别设为(rS1,cS1)、(rS2,cS2)、(rS3,cS3)、(rS4,cS4)，坐标分别设为(xS1,yS1)、(xS2,yS2)、(xS3,yS3)、(xS4,yS4)。下面详细阐述方格四点行列数及坐标求取过程。

[0094] 1号靶标像点质心为最近靶标像点质心，行列数(rS1,cS1)是(r0,c0)，坐标(xS1,yS1)是(x0,y0)。

[0095] 2号靶标像点质心是序号为S的四邻域的边缘靶标像点质心，行列数(rS2,cS2)是序号为S的四邻域的边缘靶标像点质心行列数，坐标(xS2,yS2)是序号为S的四邻域的边缘靶标像点质心坐标。

[0096] 3号靶标像点质心是八邻域靶标像点质心，由靶标方格S值求3号靶标像点质心行列数(rS3,cS3)，求出(rS3,cS3)后，下面详细阐述(rS3,cS3)求取过程：

[0097] 若S=2或S=3，则rS3=r0+1；否则，rS3=r0+1。

[0098] 若S<3，则cS3=c0-1；否则，cS3=c0+1。

[0099] 若S=4，则4号靶标像点质心是1号四邻域边缘靶标像点质心，行列数(rS4,cS4)为1号靶标像点质心的行列数(r0+1,c0)，坐标(xS4,yS4)是1号靶标像点质心的坐标(x1,y1)；
否则，4号靶标像点质心是序号为S+1的四邻域的边缘靶标像点质心，行列数(rS4,cS4)是序号为S+1的四邻域靶标像点质心行列数，坐标(xS4,yS4)是序号为S+1的四邻域靶标像点质心坐标。

[0100] 由靶标方格S得到1、2、4靶标像点质心与质心的距离DS1、DS2、DS4，由3号靶标像点质心坐标(xS3,yS3)和质心坐标(X,Y)计算质心与3号靶标像点质心的距离DS3。从而得到质心与1-4号靶标像点质心的距离DS1-DS4。

[0101] 将DS1-DS4两两比较，得到其中最大的距离Dmax，对应的最远靶标像点质心序号设为Pmax。则除Pmax号靶标像点质心之外的另外三个方格点构成所求的插值三角形。

[0102] 由最远靶标像点质心的序号Pmax、最近靶标方格的序号S、最近靶标像点质心行列数可得到插值三角形三点的行列数。将插值三角形的直角点表标为插值三角形A1点，行列数为(rA1,cA1)；行数与直角点相同的靶标像点质心设为插值三角形B1点，行列数为(rB1,cB1)；列数与直角点相同的靶标像点质心设为插值三角形C1点，行列数为(rC1,cC1)。下面详细阐述插值三角形三点行列数求取过程，

[0103] a)将序号大于Pmax的靶标像点质心设点序号均减1，使1-3号方格点为插值三角形的三点。

[0104] b)插值三角形的将直角点标为1号，步骤如下：

[0105] i.将1号方格点的行列数缓存为插值三角形直角点行列数(rr,cr)。

[0106] ii.若2、3号靶标像点质心设点行数相同或列数相同，转入步骤iii.；否则1号靶标像点质心设点为插值三角形的直角点。

[0107] iii.将2、3号靶标像点质心设点序号均减1，将3号方格点的行列数设为(rr,cr)。

[0108] c)若1、2号靶标像点质心设点的行数不相等，则将2、3号靶标像点质心设点行列数互换。

[0109] d)插值三角形A1、B1、C1点行列数(rA1,cA1)、(rB1,cB1)、(rC1,cC1)分别为当前1-3号靶标像点质心设点行列数。

[0110] 采用上述方法形成插值三角形，相对于现有的方法，计算量小，且通过实验证明构成的插值三角形因靶标像点质心阵变形，导致没有包围所述待补偿质心的概率降到了万分之一数量级。

[0111] 靶标像点质心具体的如图8所示，本实施例所述插值三角形形成方法：

[0112] 首先，可通过上述的系数式获取最近靶标像点质心，从而将搜索形成插值三角形顶点的搜索范围，由整个靶标像点质心阵缩小到由四个靶标方格构成的八邻域；通过向量；

[0113] 其次，通过计算四邻域中距离质心最近的最近边缘靶标像点质心，将所述范围锁定在八邻域的上半部分，搜索范围缩小到两个靶标方格；

[0114] 再次，通过根据第一向量和第二向量的积，将搜索范围所辖到一个靶标方格；

[0115] 最后，通过距离计算，形成如图8中所示的插值三角形。

[0116] 综合上述，本实施例提供了一种插值三角形形成方法，相对于现有方法大大的减少了计算量且降低了出错率。

[0117] 第二实施例

[0118] 如图9所示，本实施例提供一种插值三角形形成装置，所述装置包括：

[0119] 第一获取单元110，用以根据待补偿质心的坐标，在靶标像点质心阵列上获取距离所述待补偿质心的最近靶标像点质心的行列坐标；

[0120] 第二获取单元120，用以获取最近靶标像点质心所在四邻域中的四个边缘靶标像点质心的行列坐标；

[0121] 形成单元130，用以依据所述待补偿质心、所述四个边缘靶标像点质心的行列坐标，通过距离计算以及向量计算，获得形成所述插值三角形的三个靶标像点质心的行列坐标。

[0122] 所述第一获取单元110可以包括存储有靶标像点质心阵列上靶标像点质心的行列坐标的数据库以及处理器，用以根据所述待补偿质心的坐标查询所述数据库，获取靶标像点质心的行列坐标。

[0123] 所述第二获取单元120可以包括存储有靶标像点质心阵列上靶标像点质心的行列坐标的数据库以及处理器，用以根据所述最近靶标像点质心的坐标查询所述数据库，获最近靶标像点质心的四邻域的边缘靶标像点质心的坐标。

[0124] 第一获取单元110及第二获取单元120中的处理器及数据库之间均可通过有线或无线的通信接口相连，如数据总线和地址总线。

[0125] 所述形成单元130包括：

[0126] 第一计算模块，用以计算四个所述边缘靶标像点质心与所述待补偿质心的距离，最小距离所对应的边缘靶标像点质心为最近边缘靶标像点质心；

[0127] 确定模块，用以根据第一向量及第二向量的向量积，确定所述待补偿质心所在靶标方格；所述第一向量为所述最近靶标像点质心与所述待补偿质心连线构成的向量；所述第二向量为所述近靶标像点质心与所述最近边缘靶标像点质心连线构成的向量；

[0128] 第二计算模块，用以计算所述待补偿质心与所述待补偿质心所在靶标方格的四个靶标像点质心之间的距离；

[0129] 确定模块，用以所述待补偿质心距离最近的三个靶标像点质心为形成所述插值三角形的三个靶标像点质心的行列坐标。

[0130] 所述获取单元110具体用以将所述待补偿质心的坐标代入靶标系数式，计算获得初步行值以及初步列值；分别对所述初步行值以及初步列值进行四舍五入取整处理，获得第一行号以及第一列号；所述第一行号为最近靶标像点质心在所述靶标像点质心阵列中的行号，所述第一列号为最近靶标像点质心在所述靶标像点质心阵列中的列号；其中所述靶标系数式为：

[0131] ri=A1xi+B1yi+D1

[0132] ci=A2xi+B2yi+D2

[0133] 其中，所述xi为待代入的所述待补偿质心横坐标值；所述yi待代入的所述待补偿质心的纵坐标值；所述ri为所述初步行值；所述ci为初步列值；所述A1为已知的第一系数；所述A2为已知的第二系数；所述B1为已知的第三系数；所述B2为已知的第四系数；所述D1为已知的第一修正系数；所述D2为已知的第二修正系数。

[0134] 以下还提供一个实例，所述插值三角形形成装置包括处理器、存储介质、至少一个通信接口以及总线。所述总线连接所述处理器、存储介质以及通信接口，实现装置内部的数据交互。所述总线可是串联和/或并联总线。所述通信接口至少为一个，可以是无线通信接口或有线通信，用以装置与外设交互数据。所述处理器为一个或多个；所述存储介质为ROM、RAM以及flash等存储介质，优选为如ROM这种非瞬间存储介质。所述存储介质上存储有软件或固件；所述处理器运行存储在所述软件或固件，可以实现第一实施例中所述三角形插值形成方法，具体的至少可以实现以下功能：

[0135] 根据待补偿质心的坐标，在靶标像点质心阵列上获取距离所述待补偿质心的最近靶标像点质心的行列坐标；

[0136] 获取最近靶标像点质心所在四邻域中的四个边缘靶标像点质心的行列坐标；

[0137] 通过距离计算以及向量计算，获得形成所述插值三角形的三个靶标像点质心的行列坐标。

[0138] 本实施例所述的插值三角形形成装置，为第一实施例所述的插值三角形形成方法提供了实现的物理设备，采用本实施例中所述的的插值三角形形成装置，在进行插值三角的形成，具体计算量小，形成效率高以及出错率第等优点。

[0139] 此外，本实施例还提供了另一个基于电子元器件以及逻辑电路的实例，如图10所示，本实施例所述的装置包括靶标数据存储器、第一获取单元、第二获取单元以及形成单元。

[0140] 所述靶标数据存储器1，存储有所述A1、A2、B1、B2、D1以及D2的靶标数据存储器；

[0141] 第一获取单元，根据待补偿质心的坐标，在靶标像点质心阵列上获取距离所述待补偿质心的最近靶标像点质心的行列坐标；

[0142] 第二获取单元，用以获取最近靶标像点质心所在四邻域中的四个边缘靶标像点质心的行列坐标；

[0143] 形成单元，用以通过距离计算以及向量计算，获得形成所述插值三角形的三个靶标像点质心的行列坐标。

[0144] 所述获取单元包括：

[0145] 乘法器2、乘法器3、乘法器4、乘法器5、加法器6、加法器7以及最近靶标像点质心坐标存储器9；

[0146] 所述乘法器2以及乘法器3的输入端均与所述靶标数据存储器1相连，输出端均与所述第一加法器6相连；

[0147] 所述乘法器2接收所述A1以及xi，计算并输出A1xi的结果；

[0148] 所述乘法器3接收所述B1以及yi，计算并输出B1yi的结果；

[0149] 所述加法器6接收所述D1、A1xi以及B1yi，计算得出ri；

[0150] 所述乘法器4以及第四乘法器5的输入端均与所述靶标数据存储器相连，输出端均与所述加法器7相连；

[0151] 所述乘法器4接收所述A2以及xi，计算并输出A2xi的结果；

[0152] 所述乘法器5接收所述B2以及yi，计算并输出B2yi的结果；

[0153] 所述加法器7接收所述D2、A2xi以及B2yi，计算得出ri；

[0154] 所述坐标存储器用以存储最近靶标像点质心的行号r0以及列号c0。

[0155] 所述第二获取单元，具体包括四邻域点坐标寄存器8；所述四邻域点坐标寄存器8，用以缓存根据最近靶标像点质心的行号r0以及列号c0从所述靶标数据存储器1中所获取的四邻域的边缘靶标像点质心的坐标(x1,y1)、(x2,y2)、(x3,y3)、(x4,y4)；所述最近靶标像点质心坐标寄存器8，用以缓存最近靶标像点质心的坐标(x0,y0)。

[0156] 所述形成单元包括距离计算单元10、距离计算单元11、距离计算单元12、距离计算单元13、距离比较器16、减法器17、减法器18、减法器19、减法器20、乘法器21、乘法器22、减法器23、比较器24、距离计算单元14、距离计算单元28、距离寄存器15、比较器27、减法器26，加法器25、距离比较器29以及行列比较器30。

[0157] 将待补偿质心的坐标以及四邻域的边缘靶标像点质心坐标(x1,y1)输入到距离计算单元10；将待补偿质心的坐标以及四邻域的边缘靶标像点质心坐标(x2,y2)输入到距离计算单元11；将待补偿质心的坐标以及四邻域的边缘靶标像点质心坐标(x3,y3)输入到距离计算单元12；将待补偿质心的坐标以及四邻域的边缘靶标像点质心坐标(x4,y4)输入到距离计算单元13，依次得到距离D1、D2、D3以及D4，并将所述D1、D2、D3以及D4输入到距离寄存器15。

[0158] 将待补偿质心的坐标以及最近靶标像点质心坐标(x0,y0)输入到距离计算单元14，得到待补偿质心与最近靶标像点质心的距离D0，并将所述D0存储到距离寄存器15。

[0159] 将所述D1、D2、D3以及D4输入到距离比较器16，得到最小距离Pmin，根据Pmin的值所对应的四邻域边缘靶标像点质心的坐标，从四邻域点坐标寄存器8中读取最近边缘靶标像点质心坐标(xmin,ymin)。

[0160] 减法器17、减法器18、减法器19、减法器20、乘法器21、乘法器22、减法器23构成了形成单元中的所述确定模块，读取质心坐标、最近靶标像点质心的坐标以及最近边缘点坐标，计算出第一向量与第二向量的向量积，并将向量积送入比较器24。同时所述比较24的另一输入端输入0或所述比较器24内部已将另一输入置为0；比较器24比较所接收的向量积与0，得到并输出向量积的标志位V。

[0161] 所述加法器25接收V和Pmin，求取V+Pmin后，将和输入到减法器26中。

[0162] 所述减法器26输入端与所述加法器25的输出端相连，用以接收所述V+Pmin，并将V+Pmin与1做减法，将结果输入到比较器27中。

[0163] 所述比较器27接收所述减法器26的结果，在将比较结果与0进行比较，从而得到质心所在的靶标方格的序号S。根据S值从靶标数据存储器1中读入待补偿质心所在靶标方格的四个靶标像点质心，并将八邻域所对应的靶标像点质心(xs,ys)的坐标以及待补偿质心的坐标输入到距离计算单元28。

[0164] 所述距离计算单元28接收到所述点(xs,ys)的坐标以及待补偿质心的坐标，计算出距离Ds，并将所述Ds输入到距离寄存器15，在根据之前计算并存储在距离寄存器15的待补偿质心所在靶标方格，待补偿质心与靶标像点质心之间的距离分别读出可记为Ds1、Ds2、Ds3以及Ds4。

[0165] 所述距离比较器29，接收所述Ds1、Ds2、Ds3以及Ds4，两两进行比较，并最终得到最远距离Pmax，其中Pmax所对应的靶标像点质心。

[0166] 所述行列比较器30，根据最近靶标像点质心的行号和列号，待补偿质心所在靶标方格S以及Pmax得到构成插值三角形的三个靶标像点质心的行列数，从而形成插值三角形。

[0167] 本实施例所述的插值三角形形成装置，具有快速搜索出形成插值三角形三个顶点的优点，且计算量小，实现简便，实时性强。

[0168] 以上所述，仅为本发明的较佳实施例而已，并非用于限定本发明的保护范围。