图像数据压缩方法、图像处理中的图案模型定位方法,图像处理设备,图像处理程序和计算机可读记录介质

技术领域

本发明涉及在搜索待搜索图像和对与预登记图像对应的图案模型进行定位时用于待搜索图像的数据压缩方法、图像处理中的图案模式定位方法、图像处理设备、图像处理程序和计算机可读记录介质。

背景技术

一种图像处理设备，用于处理由图像拾取元件拾取的图像，该图像处理设备通常包括：图像拾取设备，用于拾取图像处理对象(下文也指“工件”)；图像数据存储装置，用于存储与由图像拾取设备拾取的图像相关的数据；和图像数据处理装置，用于处理由图像数据存储装置存储的图像数据。例如，在其图像拾取设备由CCD相机制成的图像处理设备中，基于组成图像拾取表面的大量电荷耦合元件的每个的电荷量来获得如256个灰度级或1024个灰度级的亮度数据(所谓的多值数据)，其中可以找到作为待搜索对象的工件的位置、旋转角等。通常，作为用于在图像处理中对搜索待搜索对象的图像数据执行处理的技术，已知通过使用图像之间像素差值的绝对值的总值执行的差异搜索、通过使用图像之间归一化相关值来执行归一化相关搜索等。在这些搜索中，预先将希望搜索的待搜索对象登记为模板图像，并且基于该图像来执行对待搜索图像中待搜索对象的搜索。在这些搜索处理中，通过使用图像数据的基于区域的搜索通常为主流。但是，这种基于图像厚度等的传统基于区域的搜索具有易受图像拾取器上的亮度等的改变影响的问题。

同时，也提供了一种用于执行登记图像和待搜索图像的边缘提取处理的方法，以基于边缘信息执行搜索。在这种方法中，不使用组成图像数据的像素的密度值，而使用基于密度值中大量改变的边缘数据，因此可以获得不受图像拾取器上亮度波动影响的优点。特别地，近几年，由于其高度的鲁棒性，使用被看作特征量的边缘的基于边缘的图案搜索备受关注，并且实际应用于工业应用中。

作为用于改进图案搜索的处理速度的技术，已知一种“粗到细”的方法。即，首先通过使用低分辨率图像(粗图像)粗略地执行搜索，并在指定大致位置之后，通过使用高分辨率的图像(细图像)来执行详细定位，从而增强了位置和姿态的准确度。作为通过这种粗至细类型模板匹配的方式用于高准确度地找到位置和姿态的关于细定位的技术，已知的是日本专利No.3759983的图像处理设备。

在通过粗至细类型模板匹配的方式执行基于边缘的搜索的情况下，使用其中通过使用由压缩(也指“减薄”等)原始数据获得的粗数据来执行搜索的金字塔式搜索，从而指定一个大致位置，且此后使用详细数据执行搜索。图87示出了金字塔式搜索的思想。如该图所示，使用具有高缩减比例的低分辨率图像来执行大致搜索(指“粗搜索”等)，以找到一个大致位置。此后，以增加的分辨率和中级缩减比例在其临近处执行搜索，并且最后在原始大小的图像或者具有与原始大小接近的缩减比例的图像上执行细搜索。因此如上所述，在典型的金字塔式搜索中准备多个具有改变了分辨率的图像，并且首先通过使用具有最低分辨率的图像来检测一个示意位置。在随后的处理中，随着分辨率逐渐增加，将搜索范围缩小到先前已检测位置的附近。因此，检测所得的位置的准确度随着每个随后的处理级别而增强，最终导致高准确位置的检测，其中分辨率为原始图像的分辨率或者接近原始图像的分辨率。

但是，在执行这种金字塔式的搜索时，随着更高速的处理目标而增加压缩比例时，由于图像数据的压缩，作为待搜索对象的图案图像中的如边缘强度和边缘角的特征量减少，因此造成使搜索困难的问题，这是因为匹配是基于减少的特征量进行的。特别地，在基于边缘的搜索中，作为搜索中使用的信息，关于边缘的角度的信息非常重要，且必须有效地保持关于边缘角的信息。同时，为了处理速度的改进，金字塔式搜索中图像的缩小是不可避免的，而此时，可能丢失边缘角信息。因此，在执行第一粗搜索时，设置缩小的图像的缩减比例非常重要。即，如果第一搜索基于严重缩小的图像执行，则搜索在丢失了用于搜索的必要特征量的状态下执行，且因此其搜索本身可能就是失败的。相反，当第一搜索基于具有低压缩比例的图像执行，则需要很长时间来执行该搜索。因此，在第一搜索时，应根据用户的使用和目标来设定适当的缩减比例。但是，设定最佳的缩减比例并不容易。当用户为了防止搜索失败而太在意保留足够的特征量时，可能发生不得不基于以图案图像二分之一低的缩减比例提取特征量的数据来执行搜索的情况，从而导致不能满足处理速度的情况。因此如上所述，搜索准确度和处理速度为折中选择的关系，且因此使二者兼容非常困难。

发明内容

本发明正是鉴于这种情况，且本发明的主要目的是提供一种图像数据压缩方法、一种在图像处理中的图案模型定位方法、一种图像处理设备、一种图像处理程序和一种计算机可读记录介质，以使缩减比例增大以力求加速处理，同时保留足够的特征量。

为了实现以上目的，一种用于通过使用与已登记图像相应的图案模型，搜索待搜索图像并定位类似于预登记图像的待搜索对象的图像处理中的图案模型定位中待搜索图像上的数据进行压缩的第一图像数据压缩方法，该方法可包括步骤：计算针对组成图像的每个像素的包括边缘角信息的边缘角图像；将每个像素的边缘角转换为由边缘角位表示的边缘角位图，边缘角位表示具有预定义的固定宽度的角；以及对在OR运算域中包括的每个像素的边缘角位来执行OR运算，以创建从边缘角位图缩减的边缘角位缩减图像，从而创建由表示每个OR运算域的缩减的边缘角位数据组成的边缘角位缩减图像，其中OR运算域是根据用于缩减边缘角位图的缩减比例确定的。因此，由于即使在图像的缩减之后仍然保留边缘角信息，所以可以在保持搜索准确度的同时加速了以减小的数据量进行的搜索。

一种图像处理中的第二图案模型定位方法，在通过使用与已登记图像相应的图案模型来搜索待搜索图像和定位类似于预登记图像的待搜索对象时，包括以下步骤：第一粗搜索步骤，通过使用以第二缩减比例从已登记图像创建的第一图案模型，在通过以第二缩减比例来缩减待搜索图像获得的第二缩减比例的待搜索图像的整个面积上执行搜索；第二粗搜索步骤，基于在第一粗搜索步骤中通过使用以第二缩减比例或者以小于第二缩减比例的第一缩减比例从已登记图像创建的第二图案模型获得的结果，进一步在从待搜索图像创建的第一缩减比例的待搜索图像或第二缩减比例的待搜索图像上执行局部搜索；以及基于在第二粗搜索步骤中通过使用从已登记图像创建的具有第四缩减比例的第三图案模型获得的结果，进一步在第四缩减比例的待搜索图像上执行准确度高于第一或第二粗搜索的细定位，第四缩减比例的待搜索图像从待搜索图像和不高于第一缩减比例的第四缩减比例创建，其中，在第一粗搜索步骤之前，该方法包括步骤：将预登记图像缩减为第一缩减比例；创建具有第二缩减比例的第一图案模型，第二缩减比例基于使用第二缩减比例缩减的已登记图像中关于轮廓的几何信息创建并在第一粗搜索步骤中使用，创建具有第一或第二缩减比例的第二图案模型，第一或第二缩减比例基于使用第一或第二缩减比例的已登记图像中关于轮廓的几何信息创建并在第二粗搜索步骤中使用，并创建具有第四缩减比例的第三图案模型，第四缩减比例由第四缩减比例的待搜索图像创建并在细定位中使用；获取待搜索图像并同时将待搜索图像缩减为第一缩减比例；通过使用第一缩减比例的待搜索图像，计算具有第一缩减比例并包括组成图像的每个像素中的边缘角信息的边缘角图像；通过使用具有第一缩减比例的边缘角图像，创建由边缘角位表示的具有第一缩减比例的边缘角位图，边缘角位表示针对每个像素具有预定固定宽度的角；并对OR运算域中包括的每个像素的边缘角位来执行OR运算，以创建具有大于具有第一缩减比例的边缘角位的第一缩减比例的第二缩减比例的边缘角位缩减图像，从而创建由表示每个OR运算域的缩减的边缘角位数据组成的具有第二缩减比例的边缘角位缩减图像，其中OR运算域是根据第二缩减比例确定的，且因此，该方法使如下步骤执行：第一粗搜索步骤，在具有第二缩减比例的边缘角位缩减图像的整个面积上定位具有第二缩减比例的第一图案模型；第二粗搜索步骤，根据第一粗搜索中的定位结果，通过使用与缩减比例相应的第二图案模型，在具有第一缩减比例的边缘角位图或具有第二缩减比例的边缘角位缩减图像上执行局部粗搜索；以及，根据第二粗搜索的结果，通过使用用于细定位的具有第四缩减比例的第三图案模型和与第三图案模型相应的已登记图像的第四缩减比例的待搜索图像执行细定位的步骤，其中第三图案模型介于具有第一缩减比例的已登记图像和作为原始图像的已登记图像之间。因此，由于即使进一步缩减图像数据仍然保留边缘角信息，因此可以在不降低搜索准确度的情况下使用减少的数据大小来执行高速搜索。

根据图像处理中第三图案模型定位方法，除具有第一缩减比例的边缘角位图或具有第二缩减比例的边缘角位缩减图像之外，第二粗搜索步骤可以从具有大于第一缩减比例并小于第二缩减比例的第三缩减比例的边缘角位缩减图像中选出至少一个待搜索图像。

根据图像处理中的第四图案模型定位方法，具有第三缩减比例的边缘角位缩减图像可由表示每个OR运算域的缩减的边缘角位数据组成，该数据通过对OR运算域中包括的每个像素的边缘角位来执行OR运算获得，OR运算域是根据第三缩减比例确定的。

根据图像处理中的第五图案模型定位方法，待搜索图像的选择可根据介于第一缩减比例和第二缩减比例的比例确定。

在第二粗搜索步骤之前，图像处理中的第六图案模型定位方法还可具有根据介于第一缩减比例和第二缩减比例之间的比例确定是否需要根据介于第三缩减比例和第二缩减比例之间的第三缩减比例的边缘角位缩减图像。

根据图像处理中的第七图案模型定位方法，在确定需要具有第三缩减比例的边缘角位图的情况下，可在第二粗搜索步骤中通过使用具有第三缩减比例的至少边缘角位缩减图像来执行搜索。

根据图像处理中的第八图案模型定位方法，在通过使用具有第三缩减比例的边缘角位缩减图像来执行搜索的情况下，可在第二粗搜索步骤之前从已登记的图像创建与第三缩减比例相应的第四图案模型。

根据图像处理中的第九图案模型定位方法，可基于已登记图像的锐度，将在细定位步骤中使用的与第三图案模型相应的已登记图像的第四缩减比例确定为介于第一缩减比例和未放大图像之间的缩减比例。

根据图像处理中的第十图案模型定位方法，图像的锐度可以是表示轮廓的边缘图像的边缘的锐度。

根据图像处理的第十一图案模型定位方法，细定位步骤可以是安排用于细定位的第三图案模型的步骤，以使其叠加到与第三图案模型相应的第四缩减比例的待搜索图像，在与组成用于细定位的第三图案模型的轮廓相应的待搜索图像上求出相应的边缘点，把每个轮廓与相应边缘点之间的关系看作评估值，并执行细定位以使评估值的累加值最小或最大。

根据图像处理中的第十二图案模型定位方法，第四缩减比例可以包括未放大率。因此，可以使用在缩减原始图像的情况下获得的未放大的图像作为第四缩减比例的待搜索图像。

在第一粗搜索步骤之前，图像处理中的第十三图案模型定位方法还可包括步骤：从具有第二缩减比例的已登记图像提取多个边缘点；在已提取的多个边缘点中连接相邻的边缘点，以创建连续的链条；并且针对一个或多个链条创建每个以圆弧或线的方式接近的段，并通过将段的集合作为轮廓来从已登记图像提取该轮廓，从而组成已登记图像的图案模型，其中，细定位步骤在与组成图案模型的每个段相应的第四缩减比例的待搜索图像上求出单独的相应边缘点，且将每个段与相应的边缘点之间的关系看作是评估值并且执行细定位以使评估值的累加值最小或最大。

在将待搜索图像缩减为第一缩减比例之前，图像处理中的第十四图案模型定位方法还可包括从已登记图像提取轮廓并在提取的轮廓上设置多个参考点的步骤，以及还组成已登记图像的图案模型，其中为每个参考点分配具有预定长度的通过参考点并基本垂直于该轮廓的相应点搜索线，其中细定位步骤基于至少沿着第四缩减比例的待搜索图像上的相应点搜索线的位置中的至少边缘角，针对每个相应点搜索线在与参考点相应的待搜索图像上求出相应的边缘点，并且将每个参考点的相应边缘点与包括参考点的轮廓之间的关系看作评估值并进一步执行细定位以使评估值的累加值最小或最大。

根据图像处理中的第十五图案模型定位方法，当在寻找相应边缘点的步骤中，相应点搜索线上存在可以作为相应边缘点的候选的多个边缘点时，可以选择这些相应边缘点候选中的最接近参考点的一个作为相应边缘点。因此，在存在多个相应边缘点候选的情况下可统一确定一种用于确定边缘点的方法，且之后，在细定位时，可以使用相应边缘点与参考点之间的距离作为评估值。

根据图像处理中的第十六图案模型定位方法，细定位步骤可包括步骤：计算与在最小平方法的计算中使用以解决由最小平方法从这些值中获得联立方程的每个参考点的相应边缘点有关的误差值或权值，以及比较待搜索图像中包括的各边缘点的边缘角与图案模型以计算一致性，从而比以第三缩减比例执行的粗搜索更高准确度地求出图案模型的位置和姿态。

根据图像处理中的第十七图案模型定位方法，计算边缘强度图像的步骤除包括边缘角信息的边缘角图像之外，可计算包括组成图像的每个像素中关于边缘强度的信息的边缘强度图像。由此，可通过使用具有第一缩减比例的边缘角图像和具有第一缩减比例的边缘强度图像针对每个像素创建具有第一缩减比例的边缘角位图。因此，可基于边缘强度信息和边缘角信息通过使用边缘图像数据来实现高准确度的图案模型定位。

根据图像处理中的第十八图案模型定位方法，创建边缘角位图的步骤可以基于每个像素的边缘强度图像和边缘角图像来创建边缘角位图，以使即使在将边缘角图像缩减为预定缩减比例之后仍然能保留针对每个边缘角图像的边缘角信息。

根据图像处理中的第十九图案模型定位方法，保留其边缘强度高于预设边缘强度门限的像素的边缘角，不保留其边缘强度低于预设边缘强度门限的像素的边缘角。

根据图像处理中的第二十图案模型定位方法，提取边缘点的步骤通过使用已登记图像的边缘角和边缘强度执行边缘强度非最大点抑制处理来提取边缘点。

根据图像处理中的第二十一图案模型定位方法，创建边缘角位图的步骤可合成关于边缘角位图中包括的多个邻近边缘点的数据，并保留数据以使每个合成的边缘点拥有与合成有关的多个边缘点的每个的边缘角信息，作为未放大图像或第一缩减比例的待搜索图像的边缘点具有该边缘角信息。

根据图像处理中的第二十二图案模型定位方法，在边缘角其边界介于用于将设置在中心的边缘角分段的边缘角部分之间而包括在预定边缘角位处理宽度中的情况下，创建边缘角位图的步骤可建立两个边缘角部分的边缘角位，边缘角位在边缘角部分之间划界。因此，可消除边缘角位由于噪声的影响不稳定地波动的状态，从而获得稳定均匀的计算结果。

根据图像处理中的第二十三图案模型定位方法，在边缘角其边界介于用于将设置在中心的边缘角分段的边缘角部分之间而包括在预定边缘角位处理宽度中的情况下，创建边缘角位图的步骤可建立边缘角部分中任一的边缘角位，边缘角位在边缘角部分之间划界。因此，也可以针对与相应的边缘角部分相邻的边缘角部分给出边缘角位，以获得稳定的搜索结果。

根据图像处理中的第二十四图案模型定位方法，第一缩减比例可包括未放大率。因此，可创建针对待搜索图像的未放大图像的图案模型和边缘角位图，以获得更高准确度的定位。

根据图像处理中的第二十五图案模型定位方法，可求出与参考点相应的边缘点的子像素位置。

根据图像处理中的第二十六图案模型定位方法，在创建边缘角位图的步骤中的边缘角的分辨率可以是8位、16位、32位和64位中的任意一个。

根据图像处理中的第二十七图案模型定位方法，可通过将作为边缘角的分辨率的边缘角位均匀分配给边缘方向来执行粗搜索。因此，可获得比属于边缘极性的分辨率更重要的属于边缘方向的分辨率的搜索结果。此外，相同的技术可用于忽略边缘极性的情况。

根据图像处理中的第二十八图案模型定位方法，可基于至少已登记图像的大小或有关图案模型的特征数据来确定在创建边缘角位图的步骤中用于执行边缘检测的缩减比例。因此，可适当地确定边缘检测缩减比例。此外，也可进行用户设置。

根据图像处理中的第二十九图案模型定位方法，可根据其姿态改变在创建边缘角位图的步骤中图案模型的边缘角。

根据图像处理中的第三十图案模型定位方法，创建边缘角位图的步骤可并行放置图案模型的边缘数据。因此，可以并行的形式执行搜索处理，以寻求进一步加速处理。

根据图像处理中的第三十一图案模型定位方法，创建边缘角位图的步骤可将多个位分配到边缘角方向。因此，也可加权边缘角，以获得更准确的搜索结果。

根据图像处理中的第三十二图案模型定位方法，在相应点搜索线上存在两个或多个相应边缘点候选的情况下，可根据参考点到每个相应边缘点的距离计算权值作为相应边缘点的加权，且根据权值执行最终的细定位。因此，在存在多个相应边缘点候选的情况下，可准确地确定段基于与多个相应点有关的信息在哪个方向上移动。

根据图像处理中的第三十三图案模型定位方法，在细定位步骤中针对每个边缘点计算权值时，在确定相应边缘点的相应点搜索线上存在一个相应边缘点候选的情况下可将权值设置为1，并且当将参考点与相应边缘点候选中的第一相应边缘点候选之间的距离表示为d1且将参考点与相应边缘点候选中的第二相应边缘点候选之间的距离表示为d2(d1≤d2)时，在相应点搜索线上存在多个相应边缘点候选的情况下将权值设置为“1-α(d1/d2)”(其中0＜α＜1)。因此，由于细定位可影响相应边缘点候选的数量和相应边缘点候选与参考点之间的距离，因此可在细定位时获得在准确方向上的移动。

根据图像处理中的第三十四图案模型定位方法，可进行设置，从而在组成图案模型的步骤中创建段的集合时，从由图像获得的段候选组中优选地选出基本相互垂直的段。因此，由于可替换地优选地选择横向的段，因此可在配置段的图案模型的定位时准确地地执行横向调整。

根据图像处理中的第三十五图案模型定位方法，在组成图案模型的步骤中创建段的集合时，可按照长度顺序将从图像获得的段候选组分类，以提取最长的段，设置基本垂直于提取段的预定角范围并提取段候选中的具有处于角范围的角的最长段，重复与以上方式相同的从包括在预定角范围中的基本垂直于提取段的段候选中进一步提取最长段的操作，直到提取了预定数量的段。因此，由于优选地提取横向段，所以可准确地定位。特别当仅提取长的但以相同方向排列的段时，可在与段垂直的方向上准确定位，而很难在平行于段方向上准确定位。使用上述方法，通过优选地选择横向的段可获得在X和Y的任意方向上准确定位。

根据图像处理中的第三十六图案模型定位方法，可设置使段包括线盒圆弧，且选择在提取段中忽略其角的圆弧，并且进行进一步的设置，使得当选择圆弧段并且存在一个最后选择的线段时，选择长的段作为下一个要从基本垂直于最后选择线段的段候选中选出的段，且当不存在最后选择的线段时，选择长的段作为下一个要从任意段候选中选出的段。因此，对于圆弧，仅根据长度执行优选提取，导致使其可在X和Y的任意方向上获得准确的定位。

一种第三十七图像处理设备，在通过使用与已登记图像相应的图案模型搜索待搜索图像并定位与预登记图像类似的待搜索对象时，用于对比最初给出的定位准确度更高的定位的图像处理中图案模型定位中的图像数据进行压缩，该设备包括：边缘角图像创建装置，用于获取针对组成图像的每个像素的包括边缘角信息的边缘角图像；边缘角位图创建装置，用于将由边缘角图像创建装置创建的针对每个像素的边缘角图像转换为由边缘角位表示的边缘角位图，边缘角位用预定义的固定宽度表示角；以及边缘角位图缩减装置，用于对包括在OR运算域中的每个像素的边缘角位来执行OR运算，以创建从边缘角位图缩减的边缘角位缩减图像，从而创建由表示每个OR运算域的缩减的边缘角位数据组成的边缘角位缩减图像，其中OR运算域是根据用于缩减边缘角位图的缩减比例确定的。因此，由于即使在图像缩减之后仍然能保留边缘角信息，因此可在保持搜索准备性的同时通过数据量的缩减来实现搜索的加速。

一种第三十八图像处理设备，用于在通过使用与已登记图像相应的图案模型搜索待搜索图像并定位与预登记图像类似的待搜索对象时，以高于最初给出的位置的准确度定位，该设备可包括：图像输入装置，用于获取已登记图像和待搜索图像；图像缩减装置，用于以预定缩减比例缩减待搜索图像；边缘角图像创建装置，用于在由图像缩减装置缩减的待搜索的缩减比例图像上计算针对组成图像的每个像素的包括边缘角信息的边缘角图像；边缘角位图创建装置，用于将由边缘角图像创建装置创建的边缘角图像的每个像素转换为由边缘角位表示的边缘角位图，边缘角位表示具有预定义的固定宽度的角；边缘角位图缩减装置，为了创建从边缘角位图缩减的边缘角位缩减图像，对OR运算域中包括的每个像素的边缘角位执行OR运算，以创建由表示每个OR运算域的缩减的边缘角位数据组成的边缘角位缩减图像，其中OR运算域是根据用于缩减边缘角位图的缩减比例确定的；粗搜索装置，针对由图像缩减装置以第一缩减比例缩减的第一缩减比例的待搜索图像，通过将以第一缩减比例创建的用于第一粗搜索的图案模型用作模板，对由边缘角位图缩减装置创建的第一边缘角位缩减图像执行图案搜索，从而以第一准确度从第一边缘角位缩减图像的整个面积求出与用于第一粗搜索的图案模型相应的第一位置和姿态，并针对由图像缩减装置缩减为第二缩减比例的第二缩减比例的待搜索图像，通过将以不大于第一缩减比例且不小于未放大率的第二缩减比例创建的用于第二粗搜索的图案模型用作模板，对由边缘角位图缩减装置创建的第二边缘角位缩减图像执行图案搜索，从而以高于第一准确度的第二准确度从以第一位置和姿态为参考的第二边缘位缩减图像的预定区域求出与用于第二粗搜索的图案模型相应的第二位置和姿态；以及细定位装置，通过使用第三缩减比例的待搜索图像的第二位置和姿态，安排图案模型以使其叠加到通过将待搜索的图像适当缩减为小于未放大率且不大于第二缩减比例的第三缩减比例获得的第三缩减比例的待搜索图像，从而在与组成图案模型的轮廓相应的第三缩减比例的待搜索图像上求出相应的边缘点，将每个轮廓与其相应的边缘点之间的关系作为评估值，并且以高于第二准确度的第三准确度执行细定位，以使评估值的累加值最小或最大。因此，可通过使用图像的边缘角以及其边缘强度来执行抵抗噪声分量的非常准确的定位。此外，改变相应点搜索线的长度可产生便于改变相应的边缘点搜索区域的优点。

根据第三十九图像处理设备，针对组成边缘角图像的每个作为具有不小于预设边缘强度门限的边缘强度的像素创建由边缘角图像创建装置获得的边缘角图像。

一种第四十图像处理程序，在通过使用于已登记图像相应的图案模型来搜索待搜索图像并定位类似于预登记图像的待搜索对象时，用于压缩以高于最初给出的位置的准确度定位的图像处理中图案模型定位中的图像数据，该程序可使计算机实现：边缘角图像创建功能，用于获取针对组成图像的每个像素的包括边缘角信息的边缘角图像；边缘角位图创建功能，用于将针对由边缘角图像创建装置创建的每个像素的边缘角图像转换为由边缘角位表示的边缘角位图，边缘角位表示具有预定义的固定宽度的角；和边缘角位图缩减功能，用于对在OR运算域中包括的每个像素的边缘角位来执行OR运算，以创建从边缘角位图缩减的边缘角位缩减图像，从而创建由表示每个OR运算域的缩减的边缘角位数据组成的边缘角位缩减图像，其中OR运算域是根据用于缩减边缘角位图的缩减比例确定的。因此，由于即使在图像缩减之后仍然能保留边缘角信息，因此可在保持搜索准确度的同时通过数据量的压缩来加速搜索。

一种第四十一图像处理程序，在通过使用与已登记图像相应的图案模型搜索待搜索图像并定位于预登记图像类似的待搜索对象时，以高于最初给出的位置的准确度定位，该程序可使计算机实现：图像输入功能，用于获取已登记图像和待搜索图像；图像缩减功能，用于以预定缩减比例缩减待搜索图像；边缘角图像创建功能，用于在由图像缩减功能缩减的待搜索的缩减比例图像上计算针对组成图像的每个像素的包括边缘角信息的边缘角图像；边缘角位图创建功能，用于将由边缘角图像创建功能创建的边缘角图像的每个像素转换为由边缘角位表示的边缘角位图，边缘角位表示具有预定义的固定宽度的角；边缘角位图缩减功能，为了创建从边缘角位图缩减的边缘角位缩减图像，对OR运算域中包括的每个像素的边缘角位执行OR运算，从而创建由表示每个OR运算域的缩减的边缘角位数据组成的边缘角位缩减图像，其中OR运算域是根据用于缩减边缘角位图的缩减比例确定的；粗搜索功能，针对由图像缩减功能以第一缩减比例缩减的第一缩减比例的待搜索图像，通过将以第一缩减比例创建的用于第一粗搜索的图案模型用作模板，对由边缘角位图缩减功能创建的第一边缘角位缩减图像执行图案搜索，从而以第一准确度从第一边缘角位缩减图像的整个面积求出与用于第一粗搜索的图案模型相应的第一位置和姿态，并且针对由图像缩减功能缩减为第二缩减比例的第二缩减比例的待搜索图像，通过将以不大于第一缩减比例且不小于未放大率创建的用于第二粗搜索的图案模型用作模板，对由边缘角位图缩减功能创建的第二边缘角位缩减图像上执行图案搜索，从而以高于第一准确度的第二准确度从将第一位置和姿态设为参考的第二边缘角位缩减图像的预定区域求出与用于第二粗搜索的图案模型相应的第二位置和姿态；和细定位功能，用于通过使用第三缩减比例的待搜索图像的第二位置和姿态，安排图案模型以使其叠加到通过将待搜索图像适当缩减为不小于未放大率且不大于第二缩减比例的第三缩减比例获得的第三缩减比例的待搜索图像，从而在与组成图案模型的轮廓相应的第三缩减比例的待搜索图像上求出相应的边缘点，将每个轮廓与其相应的每个点之间的关系作为评估值，并且以高于第二准确度的第三准确度执行细定位，以使评估值的累加值最小或最大。

此外，第四十二计算机可读记录介质存储上述程序。该记录介质包括磁盘、光盘、磁-光盘、半导体存储器和一些其他可存储程序的介质，如CD-ROM、CD-R、CD-RW、软盘、磁带、MO、DVD-ROM、DVD-RAM、DVD-R、DVD+R、DVD+RW、蓝光盘、HD以及DVD(AOD)。此外，所述程序包括以通过网线(如因特网)下载而分发的形式的程序，而不是在上述记录介质中存储的发布的程序。另外，所述记录介质包括可记录程序的设备，如安装为上述程序以软件或固件的形式在其中可执行的状态的通用设备或者专用设备。另外，可通过由计算机执行的程序软件来执行程序中包括的每个处理和功能，或者可通过硬件(如预定的门阵列(FPGA、ASIC))或以程序软件和实现硬件的元件部分的部分硬件模块的混合形式来实现每个部分中的处理。

附图说明

图1是表示图像处理设备的示例的方框图；

图2A至图2H是每个表示对图案模型的登记时以及在移动期间通过使用该图案模型执行搜索的的操作方案的示意图；

图3表示对图案模型的登记时的操作方案的流程图；

图4是表示在移动期间实际执行搜索的操作方案的流程图；

图5是表示在手动缩减比例确定模式中用于设置缩减比例的用户界面显示屏的图示；

图6A至图6C是每个表示边缘角位方案的示意图；

图7是表示创建并压缩边缘角位图的状态的示意图；

图8A至图8C是每个表示每个图案模型的示例的示意图，其中

图8A示出了用于局部搜索的图案模型，图8B示出了用于大面积搜索的图案模型，以及图8C示出了用于细定位的图案模型；

图9是在移动期间用于搜索的程序方案的流程图；

图10是表示在移动期间搜索构思的示意图；

图11A至图11D是每个表示旋转图案模型导致边缘角位改变的状态的示意图；

图12是表示用于在登记时创建图案模型的程序的流程图；

图13A至图13C是每个表示用于根据其优先级自动设置搜索准确度和搜索时间的用户界面显示屏的图示；

图14是表示用于细定位的登记图案模型程序的流程图；

图15是表示用于在移动期间对待搜索图像执行预处理的程序的流程图；

图16是表示具有其中设置了相应点搜索线的图案模型的图示；

图17是表示图16的图案模型已被减薄的状态的示意图；

图18是表示用于在移动期间执行图案搜索的程序的流程图；

图19A是表示待搜索图像的示例的图示，并且图19B是表示已被缩减为与图6A的已登记图像的放大率相同的放大率的待搜索的缩减图像的图示；

图20是表示在移动期间用于图案搜索的程序的流程图；

图21A和图21B是每个表示寻找相应的边缘点的相应边缘点搜索处理的示意图；

图22是用于描述边缘位置的波纹现象的示意图；

图23是表示其中很难选择相应点搜索线的某一已登记图像示例的示意图；

图24是表示在图23的图案上自动设置相应点搜索线的状态的示意图；

图25是表示相应点搜索线的过滤结果的示意图；

图26是表示用于相应点搜索线的过滤处理的程序的流程图；

图27是表示设置具有与参考点相同长度的相应点搜索线的状态的图示；

图28是表示设置具有与参考点不同长度的相应点搜索线的状态的图示；

图29是用于描述用于求出相应边缘点的坐标的程序的示意图；

图30是表示由四个像素“a”至“d”组成的边缘角图像的示意图；

图31是表示定义边缘角位的边缘角部分的示意图；

图32是表示通过转换图30的边缘角图像获得的边缘角位图的示意图；

图33是表示通过缩减图32的边缘角位图获得的边缘角位缩减图像的示意图；

图34是用于描述以2×2的单元缩减原始边缘角位图的状态的示意图；

图35是用于描述在图34的缩减处理之后放大图像的状态的示意图；

图36是用于描述将原始边缘角位图缩减为二分之一的状态的示意图；

图37是用于描述将原始边缘角位图缩减为三分之一的状态的示意图；

图38是表示并行处理之前图案模型的概念示图；

图39是表示并行处理之后的图案模型的概念示图；

图40A和图40B是每个表示关于图案模型的登记的数据的概念示图；

图41是表示作为由圆弧段和线段表示的部分有缺口的圆的图案示例的图示；

图42是表示通过使用图41的图案模型对输入图像执行粗搜索以执行某一级别的定位的状态的图示；

图43是表示通过将点与圆弧之间的距离看作误差函数应用最小平方法从图42的状态执行细定位的状态的图示；

图44是表示在图41的图案模型上执行相应点搜索线的创建处理的示例的图示；

图45是表示通过使用图44的图案模型在待搜索图像上执行粗搜索以在搜索确定的位置和姿态叠加图案模型的状态的图示；

图46是表示具有边缘强度EM和边缘角θE的边缘向量(Ex，Ey)的示意图；

图47是表示在圆的工件(work)上执行粗搜索以实现某一级别的定位的状态的概念示图；

图48是表示从图47执行细定位试图在待搜索图像上叠加图案模型的状态的概念示图；

图49A至图49D是每个用于描述在存在多个相应边缘点候选的情况下的加权处理的示意图；

图50是表示用于选择在定位方向上考虑的段的程序的流程图；

图51A和图51B是每个用于描述更新图50中的角范围的设置的状态的示意图；

图52A和图52B是每个表示通过使用饱和相加(saturatedaddition)的缩减处理示例的示意图，其中图52A是表示其中每个像素具有边缘角的边缘角图像的示意图，并且图52B是表示边缘角部分的示意图，边缘角部分以8位表示各自像素的边缘角位数据；

图53是表示二进制图像的示例的图示；

图54是表示图53的像素值的曲线图；

图55是表示具有高锐度的图像的边缘强度改变的曲线图；

图56是表示模糊图像的像素值的曲线图；

图57是表示具有低锐度的图像的边缘强度改变的曲线图；

图58是表示用于根据日本未审查的专利公开No.H07-128017计算子像素坐标的方法的示意图；

图59是表示边缘强度误差和子像素位置之间的关系的曲线图；

图60是表示用于基于边缘点的锐度确定图像数据缩减比例的程序的流程图；

图61是表示边缘模型功能的曲线图；

图62是表示通过使用图像数据缩减比例在登记时操作的流程图；

图63是表示通过使用图像数据缩减比例在运动期间操作的流程图；

图64是表示三个相邻点B、C和F的边缘强度的示意图；

图65是表示用于通过使用相邻边缘点求出相应边缘点的坐标的程序的示意图；

图66是表示用于求出图65的相应边缘点的坐标的程序的流程图；

图67是表示在字符显示在框架中的已登记图像中设置图案模型的状态的图示；

图68是表示用于设置在图像处理程序中以长度的次序执行分类的图案特征选择功能的用户界面显示屏的图示；

图69是表示将不同字符和数字显示在网格框架中的已登记图像中选择作为图案模型的段的图示；

图70是表示在图68的用户界面显示屏中将轮廓登记顺序设置为“长度的递减顺序”的状态的图示；

图71是表示在图70的用户界面显示屏中将轮廓登记顺序设置为“长度的递增顺序”的状态的图示；

图72是表示在图71的设置条件下在图69的已登记图像中选择段的状态的图示；

图73是表示用于以段的长度的顺序执行分类的程序的流程图；

图74是表示用于以链条长的顺序分类的程序的流程图；

图75是表示用于在图像处理程序中设置图案特征选择功能来过滤长轮廓的用户界面显示屏的图示；

图76是表示在图75的用户界面显示屏中已将轮廓长度的上限设置为高的状态的图示；

图77是表示在图76的设置条件下在图69的已登记图像中已选择段的状态的图示；

图78是表示在图75的用户界面显示屏中已将轮廓长度的上限设置为低的状态的图示；

图79是表示在图78的设置条件下在图69的已登记图像中已选择段的状态的图示；

图80是表示用于过滤长段的程序的流程图；

图81是表示用于过滤长链条的程序的流程图；

图82是表示用于选择以段长度分类之后的段的程序的流程图；

图83是表示用于在过滤之后选择段的程序的流程图；

图84是表示对考虑其正交方向的段的程序的流程图

图85是表示在具有高度对称的曲线图上执行细定位的示例的示意图；

图86A和图86B是每个表示通过逆海赛函数(reverse Hessian)方法逼近误差函数的状态的示意图；和

图87是表示金字塔式搜索构思的示意图。

具体实施方式

在下文中，基于附图描述本发明的实施例。但是，如下所示实施例举例证明图像数据压缩方法、图像处理中的图案模型定位方法、图像处理设备、图像处理程序和计算机可读记录介质，用于使本发明的技术构思具体化，并且本发明不将其图像数据压缩方法、图像处理中的图案模型定位方法、图像处理设备、图像处理程序和计算机可读的记录介质限定为下述形式。此外，本发明的说明书并没有将权利要求中示出的构件限定为实施例中的构件。特别地，只要不特别给出具体的说明，实施例中描述的组分元件的大小、材料、形状、相关安排等不限制本发明的范围，而仅仅是说明示例。应该注意的是为了阐明描述，存在可强调每个图示出的构件的大小、位置关系等的情况。此外，在下文的描述中，相同的名字或符号表示相同的构件或同类的构件，且根据需要不重复提供详细的描述。此外，对于组成本发明的每个元件，多个元件可由相同构件组成且因此可采取共用一个构件的方法，或者相反，可通过由多个构件共用来实现一个构件的功能。

用于本发明的示例的图像处理设备与连接到图像处理设备并用于操作、控制、显示和其他处理的计算机、打印机、外部存储设备和其他外围设备以电、磁或光的方式进行连接，以通过串行连接(如IEEE1394、RS-232x、RS-422或USB)、并行连接或通过网络(如10BASE-T、100BASE-TX或1000BASE-T)连接进行通信。该连接不限制为使用电缆的物理连接，而可以是通过使用电波(例如无线LAN，如IEEE802.1x或蓝牙(注册商标)、红外线、光通信等)或一些其他连接的无线连接。此外，可使用存储卡、磁盘、光盘、磁-光盘、半导体存储器等作为用于数据交换、设置存储等的记录介质。应该注意，在本说明书中，对图像处理设备的使用不仅是指用于执行边缘提取、图案匹配等的设备主体，也包括将这个设备主体与外围设备(如计算机和外部存储设备)组合形成的轮廓提取系统。

此外，在本说明书中，图像数据压缩方法、图像处理中的图案模型定位方法、图像处理设备、图像处理程序和计算机可读记录介质均不限制于执行边缘提取、测量区域设置和边缘点连接以及在输入/输出、显示、计算、通信和其他涉及各种图像的拾取与获取的其他处理的以硬件方式处理的操作及执行的设备和方法的系统本身。本发明的范围中还包括用于以软件方式实现处理的设备和方法。例如，一种设备和系统，将软件、程序、插件程序(plug-in)、对象、库、小应用程序、编译器、模块、在特定程序上操作的宏等集成到通用电路或计算机中，以允许边缘提取和边缘点连接及其相关处理的执行，这种设备和系统也对应于根据本发明的图像数据压缩方法、图像处理中的图案模型定位方法、图像处理设备、图像处理程序以及计算机可读记录介质中的任何一个。另外，本发明的说明书中，计算机不仅包括通用或专用的电子计算器，还包括工作站、终端、移动类电子设备、PDC、CDMA、W-CDMA、FOMA(注册商标)、GSM、IMT2000、移动电话(如第四代移动电话)、PHS、PDA、寻呼机、智能电话以及其他电子设备。此外，在本说明书中，不限于单独使用所述程序，而且也可以在作为专用计算机程序、软件、服务等的部分的模式中使用，也可以用于作为必要调用的模式中、在操作系统(OS)环境等中被提供服务的模式中、作为在环境中驻留而操作的模式中、背景中起操作作用的模式中或者作为另一支持程序的位置中。

(图像处理的简单流程)

图1示出了图像处理设备100的方框图。如图2A至图2H中所示，该图像处理设备100预先登记希望待搜索的图像并从该已登记图像创建图案模型，并且在实际操作时，该设备从输入的待搜索图像中求出与图案模型相应的位置。图3的流程图中示出了在创建图案模型时的操作方案。在本发明的实施例中，如图2A所示，用户设置一个区域，即图案窗口PW，其中针对希望被搜索的已登记图像RI创建一个图案模型(图3所示的步骤S301)。如图2B所示，将包括设置了该图案窗口PW的区域的图像适当缩减(图3所示的步骤S302)。此外，如图2C所示，从缩减的图案窗口RPM创建作为与已登记图像RI相应的搜索图案的图案模型PM(图3所示的步骤S303)。因此，如上所述，在实际搜索操作之前，图像处理设备预先从待搜索图像中创建与希望待搜索的已登记图像RI相应的图案模型PM。

另外，如图2D所示，将图案模型PM缩减至用于第一边缘角位图的缩减比例和用于第二边缘角位图(下文描述)的缩减比例，并在移动期间使用(图3所示的步骤S304)。可在登记时预先执行这种缩减的图案模型RPM的创建或者也可在每个操作时执行。

同时，图4的流程图中示出了移动期间的操作方案。移动期间，在步骤S401中输入待搜索的图像OI(图2E)之后，在步骤S402中将待搜索的图像OI适当缩减为缩减的待搜索图像ROI(图2F)。接着，在步骤S403中，从待搜索的缩减图像ROI创建边缘角位图EB(图2G：下文描述)。此外，在步骤S404中，创建从边缘角位图EB缩减的边缘角位缩减图像REB(图2H)。在步骤S405中，通过使用在登记时获得的图案模型，在如上文描述获得的边缘角位缩减图像REB上执行图案搜索。

(图像处理设备100)

接着，描述图像处理设备100的结构。如图1的方块图所示，图像处理设备100包括用于输入图像的图像输入装置1，用于显示图像和各种数据的显示装置3，用于用户执行各种操作的操作装置2；和组成输出界面的用于将图像处理设备主体100A中的图像处理结果输出到外面的输出装置5。图像输入装置1由图像拾取装置(如CCD)组成。通过A/D转换装置将从图像输入装置1输入的输入图像捕获到图像处理设备主体100A中。此外，显示装置3显示输入图像的原始图像或者通过对原始图像执行图像处理(如通过边缘图像处理)获得的边缘图像。

(图像处理设备主体100A)

图像处理设备主体100A包括用于存储各种数据的存储装置4和用于执行各种计算相关图像处理的计算装置6。除通过A/D转换器从图像输入装置1输入的已登记图像之外，存储装置4还包括用作为模板图像的该登记图像创建的图案模型、待搜索图像、用于在从已登记图像中创建图案模型时或者在搜索时创建的数据的保留和暂存的工作区域。

(计算装置6)

计算装置6包括用于在图像上执行边缘检测以提取轮廓的轮廓提取装置62、用于从轮廓信息创建链条的链条创建装置63、用于从链条创建段的段创建装置68以及其他各种装置。其他装置的例子包括边缘角位图创建装置69、边缘角位图缩减装置78、用于将图像缩减为预定放大率的图像缩减装置77、组成图案模型的图案模型组成装置70、执行粗搜索的粗搜索装置71以及用于通过基于边缘信息(下文描述)的已登记图像的图案模型来在待搜索图像内执行高准确度定位的细定位装置76。该计算装置6寄存图案模型并通过使用如上所述的已登记图案模型在待搜索图像中执行搜索。为了执行这种操作，在图案模型的登记时使用链条创建装置63、段创建装置68和图案模型组成装置70。另外，在实际操作时使用粗搜索装置71和细定位装置76。此外，将图像缩减装置77、轮廓提取装置62、链条创建装置63等用于在登记时的操作和移动期间的操作，并且在移动期间使用边缘角位图创建装置69和边缘角位图缩减装置78。应该注意，在本实施例中，尽管仅在登记时使用链条创建装置63，但是也可在移动期间对待搜索图像执行链锁。

(轮廓提取装置62)

轮廓提取装置62包括用于创建用作边缘图像的边缘角图像和边缘强度图像的边缘角/边缘强度图像创建装置60和减薄装置61。具体地说，针对由图像输入装置1输入的多值图像(原始大小的原始图像或者由稍后所述的图像缩减装置77缩减的缩减图像)，边缘角/边缘强度图像创建装置60通过使用用于提取边缘点的滤波器(如在X和Y的每个方向上通过使用索贝尔(Sobel)滤波器)分别在X和Y方向上(X方向上的边缘强度图像分量和Y方向上的边缘强度图像分量)创建边缘强度图像，并且该装置还从X和Y方向上的这些边缘角图像创建一个二维的边缘角图像。此外，针对这个由边缘角/边缘强度图像创建装置60创建的边缘图像，减薄装置61减薄其边缘点，例如通过边缘强度非-最大点抑制处理。

应该注意，本说明书中的边缘强度是表示关于一个像素是否为边缘的一部分的程度(暗度到亮度)的数值。通常从目标像素及其周围的九个像素的像素值来计算边缘强度。此外，边缘角示出一个像素中的边缘方向，且通常从通过使用上述索贝尔(Sobel)滤波器等在的X和Y的每个方向上发现的边缘强度来计算。

(链条创建装置63)

同时，在创建具有被看作模板图像的已登记图像的部分的图案时使用链条创建装置63和段创建装置68。本示例中的链条创建装置63包括边缘链锁装置64和链条滤波装置66。具体地说，边缘链锁装置64通过连接通过轮廓提取装置62创建的边缘图像中包括的多个边缘点中的多个相邻边缘点来创建链条。此外，链条滤波装置66通过各种链条的特征量来对通过边缘链锁装置64创建的多个链条组执行滤波。

(段创建装置68)

此外，段创建装置68包括边缘链条分段装置65和段选择装置67。边缘链条分段装置65接近每个由边缘链锁装置64创建并由链条滤波装置66过滤的链条，以创建段。这种情况中的段是通过最小平方法近似得到的线和/或圆弧。此外，段选择装置67对段执行过滤。

此外，段选择装置67还可包括图案特征选择功能。即，根据从待搜索对象获得的图案的特征来改变组成图案模型的段的选择标准可实现更稳定的定位。这将在下文中详细描述。

(图案模型组成装置70)

图案模型组成装置70是一种用于创建存储到上述存储装置中的图案模型。具体地说，图案模型组成装置70处理通过上述图像提取装置62、链条创建装置63和段创建装置68对已登记图像执行处理创建的每个段。将在下文中详细描述该图案模型。

(图像缩减装置77)

同时，图像缩减装置77是一种用于缩减已登记图像和待搜索图像的装置。其缩减比例是由自动缩减比例确定模式自动设置的。具体地说，如上所述，在本实施例中，在已登记图像上设置用户希望成为图案模型的区域。这种情况下缩减比例根据用户设置的区域自动设置。即，根据用于指定图案模型的图案窗口PW的大小自动确定缩减比例。例如，在图案窗口PW为矩形的情况下，根据其较短边的长度来确定缩减比例。

应该注意，在本说明书中，“增加缩减比例”、“缩减比例大”或“缩减比例高”的意思是增加缩减程度或者增加压缩比例，例如表示从具有八分之一缩减比例的缩减图像缩减到具有六分之一缩减比例的缩减图像。相反，“减小缩减比例”、“缩减比例小”或者“缩减比例低”的意思是抑制缩减程度，例如使缩减图像恢复为未放大图像，并且例如表示具有六分之一的缩减比例的缩减图像变成具有八分之一的缩减比例的缩减图像。另外，“缩减比例不小于未放大率”不表示放大未放大图像，而是指具有缩减比例大于未放大图像(即缩减比例为1)的图像，或者缩减比例为1的未放大图像。

此外，除如自动缩减比例确定模式之外，也可使用用户选择希望的缩减比例并将其确定为缩减比例的手动缩减比例确定模式。如图5所示的用户界面的示例中，用户从多个缩减比例中选择作为用于大区域搜索的缩减比例的缩减比例，此处可选二分之一、四分之一和八分之一。可使用任意数值来指定缩减比例。另外，同时显示表示原始图像如何通过具有这种情况下选择的缩减比例的图像缩减而转换的图像。这种方式中，也可以将用于局部搜索的缩减比例(中间缩减比例)和细定位缩减比例设置为不同于用于大面积搜索的缩减比例(用于大面积的缩减比例)。

另外，也可以自动添加用于局部搜索的缩减比例。具体地说，当处于用于大面积搜索的缩减比例和用于局部搜索的缩减比例之间的比例大于预定值时，自动添加以处于用于大面积搜索的缩减比例和用于局部搜索的缩减比例之间的额外缩减比例(用于局部搜索的缩减比例)设置的局部搜索(额外的局部搜索)(如图10)。另外，可多次重复额外的局部搜索。在这种方式中，可使在用于大面积搜索的缩减比例和用于局部搜索的缩减比例之间的比例保持在预定值之内，以力求搜索速度的降低。

图像缩减装置77用于创建图案模型的已登记图像和以与已登记图像中设置的缩减比例相同的缩减比例缩减的待搜索图像。即，也以已登记图像中设置的缩减比例来缩减待搜索的图像。

(边缘角位图创建装置69)

针对待搜索图像和通过上述图像缩减装置77缩减待搜索图像获得的缩减图像，边缘角位图创建装置69通过使用由上述计算装置6的边缘角/边缘强度图像创建装置60创建的边缘角图像来创建边缘角位图。即，边缘角位图创建装置69是用于在移动期间创建待搜索图像的边缘角位图。换句话说，在图案模型的登记时不使用边缘角位图创建装置。

更具体地说，如图6A至图6C所示，以45度为单位将作为边缘角的0至360度的值分段为八位数据(图6B)。确定获得的与边缘角图像的各自像素相应的边缘角是否分别处于分配给八个分段区域的比特位置(图6A)，将1的标记设置在确定的比特位置，以将边缘角图像转换为边缘角位图(图6C)。在本实施例中，边缘角位图创建装置69通过使用由计算装置6的边缘角/边缘强度图像创建装置60创建的边缘角图像来创建边缘角位图(下文基于图30等详细描述)。但是，该方法不是限制性的，如边缘角位图创建装置69可通过使用由计算装置6的减薄装置61减薄的边缘角图像来创建边缘角位图。

(边缘角位图缩减装置78)

边缘角位图缩减装置78是一种用于缩减由上述边缘角位图创建装置69创建的边缘角位图的装置。因此，获得边缘角位缩减图像。

根据图案窗口PW的大小来确定本实施例中的边缘角位缩减图像的缩减比例，其中用户通过使用图案窗口PW在已登记图像上设置希望成为图案模型的区域。因此，在边缘角位图像缩减装置78中自动确定缩减比例的情况下，反映出设置在已登记图像上的图案窗口PW的大小。但是，这种方法不是限制性的，不用说，可通过检查图案模型的缩减比例直接设置边缘角位图像缩减装置78中的缩减比例。

通过与传统方法的比较来描述该状态。在通过传统方法缩减边缘角位图的情况下，如在缩减比例为待搜索图像原始图像大小的八分之一的情况下，8×8像素的区域，即，将表示64像素的一个像素的边缘角或者通过缩减64像素的均值获得的一个像素的边缘角看作区域的中心值。与此相反，在根据本实施例的通过边缘角位图缩减装置78的边缘位图的缩减中，例如在缩减比例为待搜索图像的原始的八分之一的情况下，通过OR运算以存储比特位置的形式，保持将1的标记设置在8×8区域中64像素的每个像素的比特位置中的状态，即，设置在与图7所示的64像素所具有的每个角相应的比特位置中。因此，可存储关于边缘角位图的信息以防止图像缩减后的损坏，并且因此使用图案模型获得搜索的准确度。

根据用于缩减边缘角位图的缩减比例来确定其中执行OR运算的OR运算域。例如，在通过将边缘角位图缩减为八分之一创建边缘角位缩减图像的情况下，8×8的区域为OR运算域。即，将边缘角位图分段为8×8的OR运算域，并且在每个OR运算域中，对所有包括在OR运算域中的像素的边缘角位来执行OR运算的结果是表示每个OR运算域的缩减的边缘角位数据。以上方式中获得的每个OR运算域中的缩减的边缘角位数据的集合是边缘角位缩减图像。

另外，OR运算的意思是和运算，特别指比特的和运算。此外，在执行像素的OR运算时，除简单的位相加之外，还可在具有边缘角位的像素数上设置一个更低的限制值。例如，在每个具有要增加的边缘角位的像素数不满足预定的像素数门限的情况下，忽略该边缘角位。即，由于位像素的要增加的边缘角位在数量上远小于其他的边缘角位，则如一个到几个像素可能为噪声或误差，如可忽略具有低可靠性的像素。因此，可仅基于被认为是高度可靠的角位来创建高度可靠的边缘角位缩减图像。

(其它OR运算：饱和相加)

另外，也可以使用不同于上述的和运算的OR运算。作为示例描述一种饱和相加。例如，在通过OR运算执行缩减处理或者放大处理的情况下，在n×n的边缘角位图上对像素数据执行OR运算。该运算的扩展是“对与每个角相应的位执行饱和相加并从饱和相加的结果确定下一个中心值”。饱和相加的意思是对相加的结果预先设定一个上限并正常相加的结果超出该上线的情况下在上限值处执行限幅的相加处理。例如，当上限为100时，以如下方式将上限限制为100：

10+89＝99

11+89＝100

12+89＝100

10+100＝100

接着，基于图52A和图52B来描述通过使用饱和相加的缩减处理的特定示例。图52A是表示每个像素具有边缘角的边缘角图像的示意图，并且图52B是表示用于以8位边缘角位数据表示组成该边缘角图像的各像素的边缘角部分的示意图。应该注意，下文通过图31的方式描述通过将用于以边缘角位表示边缘角方向的角分段获得的边缘角部分。在图52B的示例中，通过从水平或垂直方向位移22.5度来分段边缘角。边缘角部分分别由E、SE、S、SW、W、NW、N和NE以45度宽的顺时针从右标记，且分别为其提供边缘角位0、1、2、3、4、5、6和7。根据图52B的边缘角部分通过以边缘角位表示组成图52A的边缘角图像的九个像素“a”至“i”获得的边缘角位图具有如下边缘角位数据：

76543210

a：00001000

b：10000000

c：10000000

d：00001000

e：10000000

f：10000000

g：00001000

h：00000100

i：10000101

接着，在新的缩减图像的边缘角位图中，对与各角对应的位“a”至“i”均进行饱和相加。将饱和相加中的上限设为3。例如，可通过如下来计算“e”的位置的缩减边缘角位数据“e”：

e’＝a+b+c+d+e+f+g+h+i

计算结果如下：

7766554433221100

e’：1100000011100001；二进制显示

e’：30003201；十进制显示

在如上计算结果中，出现饱和相加处理的特征。即，将不小于3的值均限幅到3。这种相加是指饱和相加，当和结果不小于由上述的限幅门限时，以该值执行限幅。可将该缩减的边缘角位数据“e”用于搜索处理。例如，其中仅使不小于2的值为1、且使其他值为0的缩减的边缘角位数据e”被表示如下以使其用于搜索：

76543210

e”：10001100；二进制显示

(用于粗搜索装置的图案模型X)

图案模型组成装置70创建两种图案模型，一种用于下文提到的粗搜索装置71中的粗搜索的图案模型X，以及一种用于细定位中的细定位的图案模型Y(图8A至图8C)。形成用于粗搜索的图案模型X从而基于预设条件在每个段上确定一个参考点，且在每个参考点的与段垂直的方向上以及在设置边缘的方位上设置角。

(用于细定位的图案模型Y)

同时，对于用于细定位的图案模型Y，创建每个参考点，其中除上述用于粗搜索的图案模型X的信息之外，还设置由表示每个相应段的段所划分的参数(如可定义由线或圆弧组成的段的参数)和一种垂直于在边缘方向上延伸的段并且还具有预定长度的线(下文指“相应点搜索线”)。在与设置在中心的参考点垂直的方向上前后延伸相应点搜索线。应该注意，每个段上优选设置一个或多个参考点。换句话说，图案模型中不必包括没有在其中设置参考点的段。

(粗搜索装置71)

通过使用在登记时创建的专用图案模型由粗搜索装置71和细定位装置76执行移动期间的搜索。粗搜索装置71是一种用于在移动期间执行粗搜索的装置。可以不同缩减比例执行多次粗搜索，也可仅执行一次。在执行多次粗搜索的情况下，优选地可以以抑制第二粗搜索的缩减比例使其低于第一粗搜索的缩减比例(即，增加分辨率)的方式或以其他方式基于接近原始大小的更详细的数据来执行。另外，优选地执行第二粗搜索的同时基于第一粗搜索的结果使扫描区域变窄。图9的流程图和图10的示意图中示出了移动期间的搜索方案。在本实施例中，如图9的步骤S901所示，在待搜索图像的整个面积上执行第一粗搜索(大面积搜索)，该第一粗搜索是通过使用以大面积缩减比例缩减获得的第二图案模型执行的。此后，在通过第一粗搜索获得的“检测候选”的区域以及在具有低于第一粗搜索中缩减比例的中等缩减比例的待搜索图像中的外围区域上执行第二粗搜索(局部搜索)。此外，在步骤S903中，通过使用图案模型Y由细定位装置76来执行细定位。

应该注意，在登记时创建图案模型的顺序与移动期间执行搜索的顺序不必相互匹配。例如，在登记时从具有较低缩减比例(接近于原始大小)的图案模型连续创建图案模型(第一图案模型→第二图案模型等)。这可以极大地减小随着图像的缩减丢失微小信息的情况。与此相反，在移动期间，从具有较高缩减比例(较低的分辨率，较高的压缩比例等)的图案模型开始(第一粗搜索→第二粗搜索)以相反的顺序对图案模型执行搜索。因此，通过粗到细的方式可有效地执行搜索。这导致移动期间通过使用第二图案模型执行第一粗搜索，并且接着通过使用第一图案模型执行第二粗搜索。

(第一粗搜索)

接着，描述由粗搜索装置71执行的粗搜索方案。首先，在第一粗搜索中，通过使用已登记图案模型在待搜索图像的整个面积上执行粗搜索，以提取粗定位，即，检测候选。在由边缘角位图缩减装置78创建的待搜索图像的边缘角位缩减图像上，通过使用从具有相同缩减比例的已登记图像创建的图案模型来执行扫描。具体地说，例如，为了扫描通过将原始大小缩减为八分之一获得的边缘角位图的整个区域，从边缘角位缩减图像的左上方到右下方的方向扫描以具有特定旋转角的姿态设置的图案模型。从而在边缘角位缩减图像的整个区域中指定类似于图案模型的检测候选的区域。通过使用单独设置在图案模型上的多个不同方位姿态以相同的方式执行相同的扫描。即，重复具有改变了的旋转角的扫描多次。因此，提取出类似于图案模型的检测候选的整个区域作为关于图案模型的匹配候选。图11A至图11D每个示出了由于图案模型旋转引起边缘角位改变的状态。在该示例中，以60度顺时针方向旋转用于大面积搜索的图案模型(a)时边缘角位从(b)至(d)的改变。另外，计算每个检测候选的表示类似的评估值(分值)，并提取具有高于某一门限的分值的候选。此外，每个检测候选具有关于其位置和姿态的信息，即图案模型的XY坐标、角θ和分值。应该注意，下文将详细描述该分值。

(第二粗搜索)

接着，粗搜索装置71基于第一粗搜索的结果执行第二粗搜索。在第二粗搜索中，使用小于上述第一粗搜索中的使用的待搜索图像的缩减比例的缩减比例(即，具有较大信息量的缩减比例)。通过使用例如具有四分之一的缩减比例的边缘角位缩减图像以及在检测候选的整个外围区域中的仅具有八分之一的缩减比例的图案模型来使检测候选变窄，其中所述图案模型类似于在具有与第一粗搜索中使用的相同的缩减比例的边缘角位缩减图像中提取的图案模型。由于该第二粗搜索是使用边缘角位缩减图像的部分来执行的搜索，因此可有效地执行检测候选的变窄。如上所述，可通过执行多级粗搜索进行有效率的搜索。即，在第一粗搜索中扫描整个面积确定一个粗定位之后，在具有较低缩减比例的图像中的特定区域(检测候选，或“可能为目标的区域”)或者其附近执行第二粗搜索。此外，可根据缩减比例执行多次局部搜索。

(细定位装置76)

如上所述，在通过由粗搜索装置71对检测候选及其附近执行粗搜索找到“更类似目标的检测候选”之后，通过细定位装置76执行细定位。在细定位中，在原始大小的非缩减图像或具有低于在粗搜索中使用并接近原始大小的缩减比例的缩减比例的图像中执行搜索。应该注意，在这种情况下，还将原始大小的图像看作是具有缩减比例为1的图像。此外，在粗搜索中待搜索图像是边缘角位图，而在细定位中待搜索图像是原始图像或从其缩减的图像。

细定位装置76安排图案模型Y的相应点搜索线用于细定位，以使其叠加到检测候选区域中待搜索图像上，其中检测候选在待搜索图像上获得并且类似于图案模型。具体地说，细定位装置76是一种用于通过使用检测候选区域中具有与待搜索图像相同的放大率的图案模型来执行搜索的搜索装置，其中检测候选通过边缘角位缩减图像和具有上述粗搜索装置71使用的两个不同缩减比例的图案模型的方式通过搜索变窄，并且类似于图案模型。

上面的粗搜索装置71和细定位装置76所使用的每个图案模型不是如图像处理中使用的数据(下文指“图像数据”)的图像本身，而是通过一维列举至少X坐标位置、Y坐标位置和与从图像数据获得的每个边缘点相应的边缘角值形成的数据。“图案模型”是由这些数据组成的，并且可通过使用不是图像数据而是列举数据的图案模型寻求加速处理。同时，图像数据即所谓的图像数据，例如当其具有640×480位的数据大小时，需要保留整个面积中每个像素的每个坐标位置的值。与此相反，在使用图案模型的情况下，可将其配置为仅有与边缘图像的边缘部分相应的位置和角。因此，数据量相对较小，以允许所需的处理量的缩减。因此，代替图像数据的图案模型的使用可使处理具有更高的速度。

应该注意，在本说明书中，“已登记图像”是希望待搜索的原始图像。同时，图案模型是适用于从待搜索图像中搜索与已登记图像相同的图像的上述列举数据。在本实施例中，图案模型具有组成图案模型的每个点的关于XY坐标和角θ的信息。如下文所描述的，组成细定位中的图案模型的数据在每个点的有关XY坐标和角θ的信息之上具有下文所述的相应点搜索线的信息。

也可通过集成多个构件或将一个功能划分到多个单独的构件中来执行图1所示的每个构件。例如，可将用于缩减图像的图像缩减装置77集成到轮廓提取装置62中。此外，在可通过一个CPU、LSI等来处理计算装置6的每个功能的同时，例如可将该功能分散到用于执行预处理的专用FPGA、用于执行图像处理的专用DSP等中。在该图像处理设备100中，在由DSP等组成的图像处理部分执行图像处理，并通过CPU来处理图像和搜索结果的显示。如上所述，分散处理每个功能可寻求处理加速。可任意制造执行每个功能的构件。

图像输入装置1需要由外部设备拾取并创建并且进行图像处理的输入图像。可通过通信或I/O从外部设备获取输入图像数据，并且除此之外，也可通过记录介质以数据文件的形式输入数据。此外，可使图像处理设备本身具有拾取输入图像的功能。这种情况下，图像输入装置1用作图像拾取装置和图像创建装置。当使用通过使用固态图像拾取元件(如CCD或CMOS)作为图像拾取装置的相机并且拾取用于图像处理的工件(如电子元件)时，工件上的光照与背景上的光照之间的反射光的光量存在差异，且因此差异发生在与工件相应的部分和与背景相应的部分之间的固态图像拾取元件的电荷量中。即，由于图像的亮度差异发生在工件与背景之间，因此可检测该亮度差异作为工件的轮廓或边缘。应该注意，也可将已登记图像上的轮廓数据输入为工件上的CAD数据等。以这种方式，对从图像输入装置1输入的数据根据需要进行A/D转换，并将其传送到图像处理设备主体部分。

存储装置4存储了存储用于各种转换和模板匹配计算等所需的各种数据以及关于已登记图像的图案模型的数据、用于待搜索图像的边缘图像等的参数文件。如上所述，除了存储设置内容之外，存储装置4还可用作存储输入图像数据的区域。因此，使用的这种存储装置4可以是如DRAM或闪速存储器的半导体元件或者如硬盘的固态存储装置。

操作装置2是一种用于操作图像处理设备100的输入装置。例如，在用户操作鼠标81和键盘82以手动指定处理区域的情况下，输入装置用作处理区域指定装置5。另一方面，可基于图像处理设备100侧的图像处理通过计算装置6来执行计算，以自动地指定处理区域。

输入装置通过电缆连接或无线连接与图像处理设备100连接或固定。典型的输入装置示例包括各种指示装置，如鼠标、键盘、滑块、轨迹点、图形输入板、操纵杆、控制台、拨盘、数字转换变换器、光笔、数字键、触摸板以及指示杆。另外，在连接装有轮廓提取程序的计算机与图像处理设备100的模式下，或者在将装有轮廓提取程序的计算机看作图像处理设备或轮廓提取装置的模式下，除了轮廓提取程序操作之外，还可以在图像处理设备本身及其外部设备的操作中使用上述装置。此外，用户可直接触摸显示屏的表面来通过显示界面显示屏本身的触摸屏或触摸板来实现输入和操作，或者用户可以使用声音输入装置或其他现有的输入装置，或者也可同时使用这些装置。在图1的示例中，输入装置由定位装置(如鼠标和键盘)组成。

可以使用如外部液晶显示器或CRT显示器作为显示装置3。此外，可通过使用装有输入功能(如触摸板)类型的显示装置来同时使用显示装置和操作装置。也可在图像处理设备中建立显示装置3，而不以与外部连接的形式使用。

上述结构是示例性的，且例如，图像处理设备本身可包括显示装置、操作装置等，并且也可在一个构件中同时使用每个构件或者可将每个构件集成到计算装置6中。下文中，描述将轮廓提取程序安装到通用计算机以执行边缘连接处理和轮廓提取处理的示例。

(用于图像处理的详细过程)

该图像处理设备对已登记图像(也指标准图像、参考图像等)和由图像输入装置1获取的待搜索图像执行预处理(放大、缩减、平滑、索贝尔(Sobel)滤波等)，并且接着，提取边缘作为特征提取。该设备接着通过使用从已登记图像获得的图案模型在移动期间执行的基于边缘的图案搜索。在本实施例中，如上所述，预先登记图案模型(图3)，并且在实际操作时，对待搜索图像执行处理(图4)。如上所述，在登记时的分散处理和移动期间的处理可加速处理。

更具体地描述在登记时的操作。通过上述轮廓提取装置62处理已登记图像，提取已登记图像的轮廓部分作为边缘，并且创建由具有大约一个像素宽的点的集合表示的已登记图像的边缘图像。将已登记图像的边缘图像暂存到用于存储装置4的已登记图像的边缘图像存储器中。此外，通过段创建装置68和图案模型组成装置70从已登记图像的边缘图像创建图案模型。将用于搜索的图案模型保留在存储装置4的图案模型存储器中，并根据需要被调用。

(登记时图案模型的创建)

图12示出了在登记时创建图案模型的过程的流程图。对于图案模型的创建，如上所述，将希望从待搜索图像提取出的图像的主图像指定为已登记图像，并暂存到存储装置4中。因此，在已登记图像上设置图案窗口(步骤S 1201)。针对该已登记图像设置缩减比例(步骤S1202)，并接着通过图像缩减装置77缩减图像(步骤S1203)。此外，从缩减图像中提取轮廓。具体地说，执行边缘提取处理和链锁处理(步骤S1204)。此外，连接链条以创建段(步骤S1205)。在如上述的这种方式中，针对缩减图像，将边缘数据通过轮廓提取装置62、链条创建装置63和段创建装置68分段。接着通过图案模型组成装置70创建图案模型(步骤S1206)。

如上所述，在本实施例中，将两种模型创建为用于粗搜索的图案模型X和用于细定位的图案模型Y的图案模型。此外，用于粗搜索的图案模型的数据结构由关于任意设置的原点的每个边缘点的X和Y方向上的坐标位置和边缘角组成。用于细定位的图案模型的数据结构式由关于任意设置的原点的每个边缘点的X和Y方向上的坐标位置、边缘角以及下文所述的相应点搜索线组成。

(边缘角)

边缘角是表示边缘点处边缘的密集梯度(concentration gradient)方向的角度。为了表示边缘角，由256级表示0至360度。

(边缘强度)

应该注意，在本实施例中，对于每个边缘点的边缘强度，仅将数据配置为具有本实施例中大于预设强度值的强度值的边缘点，且因此不将强度值保存为数据。但是，本发明不受该方法的限制，并且例如在搜索算法中基于边缘强度值的相似度通过下述分值计算执行评估、加权等的情况下，可将关于边缘强度的数据保存为图案模型的数据结构的值。

(图像缩减比例的确定)

此外，在使用登记时的缩减图像时，由于缩减比例在移动期间也发挥作用，因此其缩减比例的选择非常重要。设置适当的缩减比例使在保留用于搜索所需的图像特征点的同时消除噪声并减小搜索时间。例如，在搜索准确度和搜索时间之间的平衡中以搜索时间为代价将关于搜索准确度的高值置于某种程度的情况下，将缩减比例设置为相对较低的特定缩减比例。可选择地，可使用用户通过试错法确定的最佳缩减比例。在本实施例中，用于自动确定缩减比例的自动模式与用户指定缩减比例的手动模式是可切换的。在自动模式中，基于图案窗口PW的矩形区域边界的较短边的长度来确定缩减比例。此外，在手动模式中，当用户根据缩减比例使用他的或者她的眼睛检查图案模型实际上如何转换的同时选择最佳值，可将设置操作用作感觉操作。在图13A至图13C的用户界面的示例中，以当选择手动模式时通过下拉列表选择缩减比例的图像的方式示出，并示出图像如何根据选择的缩减比例转换。缩减比例越高，随着其角部分变得更不尖锐图像改变其形状越重要。参考这种图像的改变，用户可根据他的或者她的应用或目的选择适当的缩减比例。

除此以外，作为另一个示例，可采用用于自动确定搜索准确度与搜索时间之间平衡的技术。例如，作为用户在其上设置了高值的项，搜索准确度、搜索时间以及其二者可选择地存在，并且用户选择之后，自动地根据选择执行适当的设置。

(用于粗搜索的图案模型X)

粗搜索是一种在下文所述的细定位之前用于在短时间内有效地使其中与已登记图像相同的图像很可能作为待搜索图像中的检测候选存在的区域变窄的搜索。因此，粗搜索通过使用从待搜索的原始图像或者原始登记图像缩减的图像来实现上述目的。更具体地，如图87所示的金字塔式搜索，通过使用通过缩减原始大小的图像获得的缩减图像来执行粗搜索。在该粗搜索中，使用具有高缩减比例和低分辨率的图像。接着，在粗搜索中获得的大致位置(检测候选)上执行细定位。在该细定位中，使用具有比粗搜索中较低的缩减比例和较高的分辨率的图像。

描述创建用于粗搜索的图案模型X的过程。在步骤S1201中，将希望从待搜索图像检测出来的图像的主图像作为登记图像，暂存到存储装置4的登记图像存储器中。更具体地，用户在显示屏上针对从图像拾取装置获取并在如图2A至图2H所示的矩形中通过使用图案窗口PW显示在显示装置的图像来设置作为已登记图像所需部分的位置和大小。

接着，在该登记图像中确定由图像缩减装置77缩减图像时的缩减比例(步骤S1202)。在本实施例中，根据该图案窗口PW的大小(即包括在矩形中的像素数目)来确定用于下文描述的图案模型的大面积的缩减比例。

即，在作为登记图像的像素数目相对较大的情况下，由于即使缩减比例设置较高图像内部特征点的丢失也很少，因此缩减比例设置的相当高。另一方面，在作为已登记图像的像素数目相对较小的情况下，由于图像内部的特征点更容易丢失，因此缩减比例设置的相当低。优选地，将缩减比例设置为最佳缩减比例的程度，以使缩减导致图像内部噪声的消除，但是不会导致图像中的特征点丢失。

作为另一种确定缩减比例的技术，例如，相对于相同登记图像，在X和Y方向上以预定量移动已登记图像。当自相关适当地改变时，只要实现了某种程度的匹配则可将图像确定为具有相关值不易改变的特性，且因此将缩减比例设置为高。另一方面，当自相关急剧改变时，可确定图像为具有相关值容易改变的特性，且因此将缩减比例保持为低。在这种方式中，也可根据自相关来确定缩减比例。

基于以上述方式确定的缩减比例，通过图像缩减装置77缩减原始大小的已登记图像(步骤S1203)。具体地说，在图像缩减装置77中，不使用基于图案窗口PW的大小确定的最终缩减比例来执行图像缩减，而是以位于图像的原始大小与用于大面积缩减比例之间的中等缩减比例。边缘进一步由轮廓提取装置62、链条创建装置63和分段创建装置68针对具有由图像缩减装置77确定的中等缩减比例的图像分段(步骤S1204、步骤S1205)。应该注意，中等缩减比例对应于第二粗搜索中的缩减比例。

原始大小的图像的缩减之后为图像的边缘数据形成和分段，因为与获得图像的缩减紧接着原始大小的图像的边缘数据形成和分段的相反的顺序相比，以这种顺序执行处理可在存储原始图像中保留的特征点的同时减小噪声。此外，这种方式也与粗搜索以提取类似于图案模型的检测候选区域的目的一致。因此，在查看段的同时可在用户手动确定缩减比例的手动设置中设置中等缩减比例，以使在保留原始大小的图像中的特征点的同时将噪声减小为某种程度。可选择地，可在根据图案窗口PW的大小自动设置比例的自动设置中设置中等缩减比例。

(第一图案模型的创建)

接着，在步骤S1206中，图案模型组成装置70通过使用由段创建装置68分段的数据以上述中等缩减比例创建的第一图案模型。该第一图案模型在粗搜索中用于局部搜索(图9的步骤S902)。图8A至图8C每个示出了每个图案的示例。在第一图案模型中，如图8A所示，基于预定条件在存在于边缘图像数据中的每个段上确定参考点，并且在针对每个参考点在垂直于段的方向上和边缘的方位上设置边缘角处定义边缘模型点。

(第二图案模型的创建)

此外，图案模型组成装置70通过使用由段创建装置68分段的数据以上述用于大面积的缩减比例创建第二图案模型(图8B)。在该用于粗搜索的第二图案模型中，以与第一图案模型相同的方式，基于预定条件在存在于边缘图像数据中的每个边缘段上确定参考点，并且针对每个参考点在与段垂直的方向上和边缘方位上设置边缘角。这些图案模型可能不是根据缩减比例单独创建的，而可能是仅仅创建一个图案模型并接着用于移动期间根据待搜索图像的缩减比例的放大或缩减比例。

第一图案模型与第二图案模型之间的差异是在每个段上设置的参考点存在多个的情况下，如图8A和图8B所示，参考点之间的距离在第二图案模型中比在第一图案模型中长。这归功于两个图案模型之间缩减比例的差异。参考点之间距离的差异程度由中等缩减比例和用于大面积的缩减比例之间的差所控制。

如图9所示，特定的粗搜索由通过使用具有用于大面积的缩减比例的第二图案模型在待搜索图像的整个范围上执行的“大面积搜索”(步骤S901)和仅对通过使用具有中等缩减比例的第一图案模型由该“大面积搜索”提取的检测候选的候选区域执行的“局部搜索”(步骤S902)组成。

在本实施例的描述中，在粗搜索中，执行通过使用具有用于大面积的缩减比例的一个图案模型的一个“大面积搜索”和通过使用具有中等缩减比例的一个图案模型的一个“局部搜索”。具体地说，在针对图像的原始大小的中等缩减比例之后的情况下，将用于大面积的缩减比例设置如下：

(1)在不高于倍的情况下，将用于大面积的缩减比例设置为中等缩减比例的二分之一；

(2)在至1/4倍的情况下，将用于大面积的缩减比例设置为中等缩减比例的三分之一；和

(3)在不低于四分之一的情况下，将用于大面积的缩减比例设置为中等缩减比例的四分之一。

如上所述，根据中等缩减比例来确定用于大面积的缩减比例。从而显著地平衡搜索效率与来自原始图像的特征点的存储。

可执行多次局部搜索。在中等缩减比例相对于原始大小明显较高的情况下，例如在将中等缩减比例设置为上述(3)的图像的原始大小的四分之一的情况下，中等缩减比例变为图像的原始大小的十六分之一。在这种情况下，由于用于大面积的缩减比例与中等缩减比例之间的比例是四倍那么大，因此对通过使用具有用于大面积的缩减比例的第二图案模型提取的检测候选的候选区域及其周围执行“局部搜索”可能花费很长的时间。

因此，在本实施例中，当中等缩减比例与用于大面积的缩减比例之间的比例大于两倍时，设置额外的中等缩减比例以增加一次或多次搜索，以使邻近的缩减比例之间的比例变得不大于两倍。即，通过执行两次或多次局部搜索，寻求一个局部搜索所需的时间缩减。例如可通过在图5所示的用户界面显示屏中设置用于对“自动添加局部搜索的缩减比例”选择的复选框的方式来设置这种中等缩减比例(用于局部搜索的缩减比例)的自动添加。

如上所述，图案模型具有由针对任意设置的原点的每个边缘点在X和Y方向上的坐标位置和边缘角所组成的数据结构。因此，当设置额外中等缩减比例时，如上述第一图案模型和第二图案模型的情况下，从段创建与额外中等缩减比例相应的图案模型。具有额外中等缩减比例的图案模型不同于第一图案模型和第二图案模型，因为当存在多个每个段上设置的参考点时，参考点之间的距离与第一图案模型相比较长，且与第二图案模型相比较短。因此图案模型本身由关于坐标位置等的数据组成，即使当图案模型缩减时，与由于图像数据缩减产生的信息缺陷相比，可使由于缩减产生的信息缺陷非常小。

(大面积搜索)

为了描述的方便也描述移动期间搜索中的操作。如图9中的步骤S901所示，通过使用具有用于大面积的缩减比例的图案模型的“大面积搜索”的执行，提取检测候选的候选区域。接着，通过使用具有仅次于用于大面积的缩减比例的第二最高比例的第二图案模型对检测候选的提取的候选区域执行“局部搜索”。从而基于搜索的结果，使具有高准确度的检测候选的候选区域变窄。接着，通过使用具有以缩减比例递减的顺序所的设置的中等缩减比例的图案模型对变窄的检测候选的候选区域执行“局部搜索”，以重复检测候选的候选区域变窄的过程。

(细定位缩减比例)

(手动缩减比例确定模式)

另外，如上所述，在通过使用图5的用户界面用户可选择缩减比例的手动缩减比例确定模式的情况下，用户可选择一个中等缩减比例、一个用于大面积的缩减比例和一个在使用细定位装置76时的细定位缩减比例。但是，这种设置也可在当选择的中等缩减比例与用于大面积的缩减比例之间的比例大于两倍时的情况中使用，基于上述条件自动创建这些缩减比例之间的另一个中等缩减比例。此外，对于在使用细定位装置76时的细定位缩减比例，当用户选择缩减比例的候选时，将待选择值限制为粗搜索设置的缩减比例中的最低值或比该值(包括图像的原始大小)更低的缩减比例的值。从而可避免使用具有比前置级更高缩减比例的粗数据错误地执行细定位的情况。

(用于细定位的图案模型)

如图9中的步骤S903所示，细定位搜索是通过使用具有最后用于“局部搜索”的最终中等缩减比例或者低于此(包括图像的原始大小)的缩减比例的图案模型对一个或者多个检测候选的候选区域执行细定位。优选地，在细定位中使用的图案模型的缩减比例为未放大图像，即原始大小的原始图像。

(边缘的锐度)

如上所述，在细定位中，不是必须使用原始大小的待搜索图像，而也可使用以范围不超出最后用于前置局部搜索的最终中等缩减比例的缩减比例(细定位缩减比例)缩减的图像。因此，具体地说，即使当待搜索图像模糊时，也可获得优选的搜索结果。

例如，可以认为原始大小的边缘图像的亮度数据的波形越陡，锐度越高，相反，波形越平缓，图像越模糊。因此，当边缘部分的锐度低于预设值时，即当边缘在其不小于预定宽度的宽度方向上分散并且图像因此模糊时，将缩减比例设置为一个合适的细定位缩减比例且将图像缩减到该缩减比例，以使能缩减该图像的锐度来增加边缘的锐度，且因此可获得稳定的定位准确度。

例如，在如图53所示像素急剧改变的二元图像的情况下，该图像的轮廓(即边缘)是所谓的其像素密集度(即像素值)如图54所示阶梯式改变的阶梯型边缘。因此，如图55所示，边缘强度改变的边界趋向于陡峭，并且可获得准确的定位。另一方面，当二元图像不清楚时，边界部分如图56所示平缓地改变，导致边缘强度的改变变成如图57所示较小波动的曲线。因此存在即使周围环境的轻微波动(如亮度或光量的改变)也影响边缘检测准确度的问题，从而妨碍稳定的边缘检测并降低图像处理(如图像识别)的可靠性。因此，在本实施例中，将图像缩减为适当的缩减比例以改进边缘锐度。

(边缘子像素坐标的确定)

具体地说，在通过使用边缘信息的细定位中，基于图案模型执行高准确度的定位，图案模型基于从已登记图像提取的边缘有关的位置信息和从待搜索图像提取的边缘有关的定位信息创建。因此，边缘上的位置信息非常重要。

通常，作为确定边缘的子像素的位置的技术，已知日本未审查的专利公开No.H07-128017、美国专利No.6408109B1等技术。在这些方法中，使用三个数据的总数：目标像素的边缘强度及位于其周围的两个像素的边缘强度，通过二次插入的方式找到子像素坐标。图58示出了用于根据日本未审查的专利公开No.H07-128017计算子像素坐标的方法方案。在该附图中，EMc(边缘强度中心)是作为用于减薄边缘的非最大点抑制处理(非最大抑制)之后留下的边缘点的目标边缘点的边缘强度值。此外，EMf(前向边缘强度)是由目标边缘点的边缘角的方位的箭头表示的评估边缘强度值。此外，EMb(后向边缘强度)是由目标边缘点的边缘角方位的圆表示的评估边缘强度值。另外，EMf1、EMb1的下标1是在横向上给出边缘点的特征量，EMf2、EMb2中的下标2是在对角线方向上给出边缘点的特征量。下文示例中考虑的是由水平方向的边缘角形成的角EAc(＜45度)。通过考虑对称性可求出其他角。确定如下表达式。

EMf＝EMf1*(1-tanEAc)+EMf2*tanEAc

EMb＝EMb1*(1-tanEAc)+EMb2*tanEAc

使用上述表达式中三个边缘强度数据EMc、EMf和EMb，可通过如下表达式计算子像素位置的偏移量：

x＝(EMf-EMb)/(2(2EMc-EMf-EMb))

y＝x*tanθ

如上所述，可计算子像素位置。接着，图55和图57示出了清晰的边缘强度的状态和模糊图像中边缘强度的状态。如图55所示，清晰到某种程度的边缘强度的峰值是陡峭的并且可以清楚地确定边缘位置。另一方面，在如图57所示的不清楚和模糊的图像的情况下，最大值的附近形成非常平的状态，并且边缘强度的误差对子像素坐标影响非常大。为了评估该影响，考虑EMf＝EMb中具有一级误差的EMf的情况。如下表达式示出了边缘角误差与子像素位置之间的关系：

[表达式1]

$>x^{\prime }=\frac{f_d\left(1\right)-f_d(-1)}{2(2f_d\left(0\right)-f_d\left(1\right)-f_d(-1))}$>

[表达式2]

$>y=\frac{x-a}{2(2c-x-a)}$>

在以上函数中，通过如下表达式的方法检查“x＝a+1”周围的状态：

[表达式3]

$>\mathrm{\delta y}=\frac{a-a}{2(2c-a-a)}-\frac{a+1-a}{2(2c-a-1-a)}$>

[表达式4]

$>\mathrm{\delta y}=\frac{0}{2(2c-2a)}-\frac{1}{2(2c-2a-1)}$>

在上述表达式中，当“X＝c-a”时，

[表达式5]

$>\mathrm{\delta y}=-\frac{1}{2(2X-1)}$>

当用曲线表示时，获得如图59所示。如该图中所示，随着边缘强度在X→0中变平，即c→a，由边缘强度的误差对边缘位置误差施加的影响变得更大。在EMf≠EMb中能看到相同的趋势。因此，在本实施例中，计算边缘点的锐度，并使用该值，计算用于执行边缘的子像素位置的计算的边缘数据缩减比例。此外，使用缩减到图像数据缩减比例的图像数据，执行边缘提取。如上所述，缩减图像数据可将如图57所示的平缓波形转换为如图55所示的急剧的波形，以稳定边缘位置，从而可以改进定位准确度。

基于图60的流程图描述用于基于边缘点的锐度确定图像数据缩减比例的过程。首先，在步骤S6001中，从未放大图像创建边缘图像。接着，在步骤S6002中减薄边缘图像的边缘，同时在步骤S6003中计算边缘图像中每个边缘点的锐度。边缘减薄处理是在边缘连接处理之前针对非最大点抑制处理执行的。此外，在步骤S6004中，计算减薄的目标边缘点的锐度的平均值。接着，在步骤S6005中，基于该锐度的平均值确定图像数据缩减比例。确定图像数据缩减比例从而保持边缘点的位置准确度不低于预定的准确度。

(边缘模型函数)

接着，考虑边缘模型函数。将许多提取的边缘看作阶梯式边缘，并假设其为可由如下所示的边缘模型函数表示。该边缘模型函数的“σ_s”是边缘点的锐度。在这种情况下边缘的理想形式表达如下：

[表达式6]

$>\mathrm{edge}\left(x\right)=\Phi \left(\frac{x-d}{{\sigma }_s}\right)$>

[表达式7]

$>\Phi \left(x\right)=\frac{1}{\sqrt{2\pi }}{\int }_{-\infty }^{x}e-\frac{z^2}{2}\mathrm{dz}$>

图61示出了以上函数的曲线图。该图中示出的边缘的理想形状(外形)是由以下表达式(在沿X轴I＝2，I0和δs＝0.6的情况下)标绘的：

[表达式8]

$>S(x;\theta )=\mathrm{I\Phi }\left(\frac{x-l}{{\sigma }_s}\right)$>

(使用图像数据缩减比例的图案搜索的过程)

接着，基于图62和图63的流程图描述通过使用图像数据缩减比例在图像处理中的图案搜索的特定过程。在这些附图中，图62示出了登记时的操作，并且图63示出了移动期间的操作。

(在使用图像数据缩减比例登记时的操作)

首先，基于图62描述登记时的操作。在步骤S6201中，创建用于粗搜索的图案模型。接着，在步骤S6202中，通过使用未放大的图像执行边缘提取，以求出针对每个提取的边缘点的标准偏差σ_s。在求标准变差σ_s期间，假设从图像数据实际提取的边缘形状接近图61的模型。为了在具有边缘强度不小于预定边缘强度门限的边缘点处的每个边缘的子像素位置的计算，通过使用图64中所示的三个相邻点B、C、F的边缘强度EMb、EMc、EMf将下一表达式用作对数边缘强度的二次导数的近似表达式：

[表达式9]

t＝(ln(EMf)+ln(EMb)-2ln(EMc))*(cos(EAc)²)

通过使用上述表达式中的“t”，可从如下表达式计算标准偏差σ_s：

[表达式10]

σ_s＝1.8263*t^(-0.35661)-1.07197

重要的是标准偏差σ_s可由单值函数表示，并且上述没有特别含义。

同时，在步骤S6203中，通过链条创建装置63和段创建装置68链锁并分段从图像数据提取的边缘，以创建试验性的图案模型。此外，在步骤S6204中，仅使用创建该暂时图案模型时使用的每个边缘的σ_s来计算平均值σ_s。接着，在步骤S6205中，使用该有利值σ_s，通过如下表达式求出图像数据缩减比例“r”。这是细定位缩减比例。

[表达式11]

$>r=\frac{{\sigma }_a}{0.6}$>

在该示例中，获得边缘强度的对数的差值，并从该差值计算缩减比例。但是，该示例不是限制性的，也可使用各种关于边缘强度的对数的差值的近似值来计算图像数据缩减比例。此外，对此涉及的合适值包括边缘强度的差值的近似值。

如上所述，当获得图像数据缩减比例“r”时，在步骤S6206中根据细定位缩减比例重新缩减已登记图像。此外，在步骤S6207中从缩减的已登记图像创建用于细定位的图案模型。

(移动期间应用图像数据缩减比例的操作)

接着，基于图63描述通过使用图像数据缩减比例对登记操作响应而在移动期间执行的操作。首先，在步骤S6301中，通过使用以上获得的细定位缩减比例，将待搜索图像缩减为用于细定位的缩减的待搜索图像。同时，在步骤S6302中，从待搜索图像创建用于粗搜索的缩减图像，并且在步骤S6303中，通过使用用于粗搜索的图案模型和用于粗搜索的缩减图像来计算检测候选的位置和姿态。最后，在步骤S6304，通过使用用于细定位的图案模型、用于细定位的缩减的待搜索图像以及检测候选的位置和姿态来执行细定位。

(图像缩减的预处理/后处理)

即使在图像数据缩减之后，也缩减图像数据以尽可能地保留边缘位置的信息。具体地说，在应用与图像数据缩减比例相应的低通滤波器之后，执行子采样。在子采样之后对图像数据执行边缘提取以使能获得关于边缘位置的准确信息。

在如上所述的这种方式中，能抑制由于原始图像的不清楚(如模糊)发生的准确度的恶化。此外，缩减图像数据来减小数据量可产生允许后续处理轻负荷高速地执行的附加好处。

在本实施例中，自动地将细定位缩减比例设置为上限是“局部搜索”中最后使用的最终中等缩减比例(第一缩减比例)的缩减比例。此外，从缩减的已登记图像创建细定位中使用的图案模型以具有与细定位缩减比例相同的缩减比例。如上所述，在从图像的原始大小到最后在局部搜索中使用的最终中等缩减比例的范围内基于原始大小的边缘图像的边缘锐度确定细定位缩减比例。

如上所述，调整细定位缩减比例以使锐度保持在不低于固定级别的级别，并且因此可在锐度高的状态中使用缩减比例，以使能确保定位准确度的稳定。

(在图案模型登记时的操作)

再次转向图案模型的登记操作的描述，基于图14的流程图描述用于细定位的登记图案模型的过程。通过使用与上述用于粗定位的图案模型中描述的登记图像相同的图像来创建用于细定位的图案模型。首先，在步骤S1401中，在由图像缩减装置77处理之前，通过轮廓提取装置62创建关于登记图像的原始大小的边缘图像，并评估边缘的锐度。基于此，在步骤S1402中确定最佳缩减比例，如上所述，在步骤S1403中，基于关于登记图像确定的最佳细定位缩减比例通过图像缩减装置77来缩减图像。此外，针对以确定的缩减比例包括一个缩放比例由图像缩减装置77缩减的图像，通过轮廓提取装置62、链条创建装置63和段创建装置68对边缘分段(步骤S1404，步骤S1405)。具体地说，在缩减图像上，执行从边缘点提取边缘的边缘提取处理和创建链条的链锁处理，并且还执行连接链条的分段。接着，图案模型组成装置70通过使用由段创建装置68分段的数据以确定的细定位缩减比例创建用于细定位的图案模型(步骤S1406)。

此外，如上述用于粗搜索的图案模型，用于细定位的图案模型基于预设条件在边缘图像数据中存在的每个段上确定参考点(步骤S1407)。此外，关于每个参考点设置角(步骤S1408)。在垂直于段和边缘的方位的方向上设置角。此外，设置是提供了参考点的段的类型(如线或圆弧的类型的段)，是表示段、垂直于段的方向和接近边缘角的方向的角以及具有在垂直于段方向上预设长度的线段信息(即相应点搜索线)的参数(步骤S1409)。

(相应点搜索线的线长)

对于关于每个参考点给出的相应点搜索线的线长，设置对每个参考点相同的长度。通过在局部搜索中使用的最终中等缩减比例与在细定位中使用的细定位缩减比例之间的比例的方式确定该长度。换句话说，当最终中等缩减比例与细定位缩减比例之间的比例较大时设置线长为大，并且当所述比例较小时设置线长为小。

例如，当在局部搜索中最后使用的最终中等缩减比例是图像的原始大小的四分之一并且细定位缩减比例是未放大率时，最终中等缩减比例和细定位缩减比例之间的比例为四倍，并且因此局部搜索中的一个像素对应于细定位中的四个像素。因此，将用于细定位的图案模型中的线长设置为从参考点在边缘的正向和反向上覆盖四个像素的每个。但是，由于该线长对定位准确度和搜索时间有影响，因此不是必须通过缩减比例的比例覆盖相应像素的总数。例如，根据所需处理时间将相应点搜索线的线长设置为短。否则，相反，可将线长设置为不小于相应像素数。例如，可根据缩减比例的比例将边沿设置为线长，以寻求处理的稳定性。

(相应点搜索线的线长改变)

此外，可将相应点搜索线的长度设置为相对于参考点前后不一致，并且可改变以使一个线长更长或更短。通过图案模型组成装置70等执行该处理。基于图27和图28描述相应点搜索线的长度改变的示例。在这些附图中，图27示出了距参考点等长的情况，并且图28示出了距参考点不是等长的。应该注意，在这些附图中，已对在这些附图中内部矩形区域产生的相应点搜索线进行过滤。如图27所示，当使在前/后和左/右方向上相应点搜索线从参考点延伸的长度为常数时，线与可造成错误判定的内部矩形形状部分重叠。因此，当相应点搜索线在向内的方向上不延伸而仅在向外的方向上设置时(如图28)，可获得具有更小错误判定的更准确的搜索结果。

(设置相应点搜索线的间隔)

在除其末端部分的段上设置相应点搜索线。这是因为这种末端部分受位移的影响非常大。因此，通过设置相应点搜索线而排除受位移影响大的部分可获得稳定的处理。

根据需要的处理速度和图案搜索的准确度来确定设置其相应点搜索线的间隔和数量。可通过设置使在组成段的每条线或圆弧上安排至少一个相应点搜索线来保持图案搜索的准确度。最简单地，在段的中心安排一个参考点，并从该点在段上等间隔地设置参考点。此外，在段内具有模糊边缘角的部分使参考点的设置变少，并且在可靠的检测部分密集地设置参考点，并且从而可改善准确度。

此外，优选地，为段的中心分配至少一条相应点搜索线。这确保关于图案模型的段组成部分至少一条相应点搜索线的设置，即使相应点搜索线很短。

(移动期间对待搜索图像的预处理)

在上述中，描述了图案模型登记时的操作，即，用于粗搜索和细定位的图案模型的创建(图3、图12)。在移动期间，通过使用这些图案来执行搜索(图4)。在搜索中，在从图像拾取装置输入的待搜索图像上执行预定的预处理。基于图15的流程图描述移动期间在搜索中对待搜索图像执行的预处理的过程。

首先，在步骤S1501中，基于输入的待搜索图像，图像缩减装置77通过使用用于登记时在登记图像中使用的粗搜索的第一图案模型的中等缩减比例(第一缩减比例)来创建缩减的图像。

同时，在步骤S1502中，轮廓提取装置62的边缘角/边缘强度图像创建装置60创建边缘角图像和边缘强度图像。此外，减薄装置61基于这些边缘角图像和边缘强度图像创建减薄的边缘角图像。

接着，在步骤S1503中，由轮廓提取装置62创建边缘角位图创建装置69，并且基于减薄的边缘强度图像，创建与用于粗搜索的第一图案模型的中等缩减比例相应的边缘角位图。不必说，在搜索操作中通过使用用于粗搜索的第一图案模型，将由此创建的边缘角位图应用“局部搜索”。

此外，在步骤S1504中，边缘角位图缩减装置78创建基于由边缘角位图创建装置69创建的边缘角位图创建与用于“大面积搜索”的第二图案模型的大面积的缩减比例相应的边缘角位缩减图像。

应该注意，如在粗搜索的中等缩减比例的设置的描述中所述，在基于首先设定的中等缩减比例与用于大面积的缩减比例之间的额外中等缩减比例创建额外图案模型的情况下，也在该预处理中，如任意的步骤S1505，基于由边缘角位图创建装置69创建的边缘角位图由边缘角位图缩减装置78创建与额外图案模型的中等缩减比例相应的边缘角位缩减图像。

另外，在上述移动期间的预处理中，在待搜索图像上以与作为粗搜索的大面积搜索和局部搜索以及移动期间执行的细定位(图8A至图8C)的顺序相反的顺序执行处理，但是创建图案模型的顺序不特别受限制，并且不用说，可在创建用于细定位的图案模型之后创建用于粗搜索的图案模型。同时，在移动期间，通过使用具有高缩减比例的图像执行粗搜索，并且在大小接近原始大小的图像上逐渐减小缩减比例以执行细搜索。

如上所述，在完成移动期间的预处理之后，使用创建的边缘角位缩减图像、边缘角位图等来执行作为粗搜索的大面积搜索和局部搜索，并且在求出检测候选的坐标之后，执行细定位(图9)。

(登记时的每个操作的细节)

在上文中，描述了登记时和移动期间的操作方案。接着，详细描述登记时的图像处理操作。在登记时，边缘角/边缘强度图像创建装置60对已登记图像使用索贝尔(Sobel)滤波器，并在每个组成已登记图像的点求出边缘强度和边缘角，以计算包括边缘强度、边缘角和边缘位置的边缘信息。基于该边缘信息执行减薄处理，以求出边缘点。作为减薄处理的特定示例，可使用边缘强度非最大点抑制处理。将边缘减薄为具有一个像素宽的线形。

应该注意，也可通过子像素位置的准确度的方式求出边缘点。例如，可通过二次插入的使用来计算子像素位置(如，见日本未审查专利申请No.H07-128017)。

此外，连接获得的边缘点以创建连续的链条。边缘链锁装置64以几乎相同的方向执行连接相邻边缘点和边缘角的边缘连接处理，以创建连续的线元素(链条)。因此获得的链条也具有xy子像素坐标。每个链条是边缘点的集合，并且为了每个链条的区分为每个单独链条提供作为标识的链条索引。

此外，通过边缘链条分段装置65对链条近似以创建段。通过使用最小平方法对由线和圆弧近似的链条匹配(fitting)找出段。在匹配中，首先由线执行近似，并且当由线近似的误差超出预定门限时，将匹配切换到由圆弧的近似。当即使由圆弧近似时误差仍然不减小时，使用由线匹配的结果。在这种方式中，重复在线和圆弧的组合中连续地执行匹配的操作，并且在当匹配结果的误差超出门限时的时间点，如果获得的数据多到足够长，则将段看作连续的线。由于在子像素位置找到边缘点，也可以子像素顺序在高准确度的位置获得段。

通过用线和圆弧近似链条来创建段。可由表示直线(如ax+by+c＝0)、端点坐标等的表达式来表示线段。同时，可由中心坐标、半径、起点角度、终止角等表示圆弧段。例如，圆弧的中心坐标(x0，y0)在“(x-x0)²+(y-y0)²＝r0²”中的半径r0表示圆弧段。在这种方式中创建的每个段处，以预定间隔设置参考点。

应该注意，尽管描述了由线或圆弧作为段的方式近似的示例，但这不是限制性的，并且也可根据需要使用圆锥形曲线、齿条曲线、贝塞尔(Bezier)曲线等。因此，以固定几何形状(如圆形、椭圆形、三角形或矩形)作为参考，可通过单独或组合使用这些形状来创建图案模型，从而使图案搜索的创建和每个后续处理方便。

(图案模型的缩减)

此外，在移动期间的搜索中缩减图案模型。该缩减比例为在下文描述的移动期间用于缩减粗搜索的待搜索图像的缩减比例。由于将要执行这种缩减处理，在作为图案模型的模型边缘点的参考点中设置间隔以防止参考点指定与缩减处理的结果相同的坐标。因此，图16的图案模型变为如图17的图案模型。

(用于粗搜索的图案模型与用于细定位的图案模型之间的差异)

分别从原始大小(或其缩减图像)的已登记图像创建用于粗搜索的图案模型和用于细定位的图案模型。换句话说，不从用于细定位的图案模型的段创建用于粗搜索的图案模型的段，并且两个模型的段不必匹配。此外，由于图案模型的大小在用于粗搜索的图案模型与用于细定位的图案模型之间不同，因此其间每个参考点的距离也不同。通过由未放大率转换每个参考点间的距离获得的距离差异取决于缩减比例。

此外，在用于粗搜索的图案模型中，给出参考点处的参考点坐标和边缘方位(角信息)。换句话说，在垂直于不具有关于相应点搜索线的长度信息的段的方向上将角设为接近边缘的方位。在通过使用用于粗搜索的该图案模型的粗搜索中，在待搜索图像上放置图案模型，并检查其在参考点的位置是否存在边缘以及边缘的方位是否匹配图案模型的方位。

另一方面，除了用于粗搜索的图案模型中参考点的坐标和参考点处边缘的方位之外，用于细定位的图案模型具有通过参考点并在大致垂直于段的方向上延伸的具有预定长度(即一个定义垂直于段的长度)的相应点搜索线和段种类(例如，如线或圆弧的特性)。该差异与每个搜索的处理内容相对应。即，在细定位中，搜索在相应点搜索线的范围中的相应的边缘。在这种方式中，用于细定位的图案模型用作相应边缘点选择装置，用来选择与参考点对应的相应边缘点。

应该注意，在轮廓的提取中，段的创建不是必须的。可以不从段而直接从链条来设置相应点搜索线。例如，在针对某一轮廓设置三个参考点的情况下，以等间隔设置组成了与轮廓相应的链条的三个边缘点，以在各自垂直方向设置相应点搜索线。通过这种方法，由于没有创建段则可获得高速处理，而由于不是由直线或圆弧来近似链条因此准确度轻微恶化。具体地说，通过仅仅连接边缘点来形成链条，并且因此其具有较差的线性度，而由直线或圆弧占用段，以使获得的计算结果更准确并且定位准确度也是稳定的。

(移动期间的粗搜索的详细描述)

接着描述的是移动期间以上述方式通过使用登记的图案模型用于从待搜索图像中实际搜索匹配部分的操作。首先，基于图18的流程图描述在粗搜索中用于获得粗定位和姿态的过程细节。在本实施例中，将粗搜索分为大面积搜索和局部搜索，并执行以找出检测候选。

(步骤S1801-待搜索图像中的缩减)

首先，在步骤S1801中，与登记图像的缩减比例一致地缩减作为待搜索对象的待搜索图像。例如，将图19A中所示的待搜索图像缩减为与登记图像相同的放大率，以获得图19B所示的缩减的待搜索图像。首先，将图像缩减到作为粗搜索比例的中等缩减比例。换句话说，不是首先将缩减比例缩减至用于大面积的作为大缩减比例的缩减比例，而是首先缩减至作为小缩减比例的中等缩减比例。

(步骤S1802-边缘角图像和边缘强度图像的获得)

接着，在步骤S1802中，通过边缘计算装置分别从缩减的待搜索图像获得边缘强度图像和边缘角图像。作为边缘计算方法，可使用索贝尔(Sobel)滤波等。

描述索贝尔(Sobel)方法。在索贝尔(Sobel)方法中，使用3×3的矩阵作为运算符(内核)。该方法提取通过由关于设置在中心的目标点周围点的系数与像素值相乘并将乘积值相加获得的值作为中心点的像素值。该方法是一个水平和垂直的滤波器，并且由于包括平滑操作因此具有抗噪声的特性。下文示出索贝尔(Sobel)滤波器中使用的内核。

[表达式12]

$>\left(\begin{array}{ccc}-1& 0& 1\\ -2& 0& 2\\ -1& 0& 1\end{array}\right)$>

$>\left(\begin{array}{ccc}-1& -2& -1\\ 0& 0& 0\\ 1& 2& 1\end{array}\right)$>

因此，单独获得待搜索图像的边缘强度图像和边缘角图像。

(步骤S1803-待搜索图像的边缘角位图的创建)

此外，在步骤S1803中，由边缘角位图创建装置69从边缘角图像和边缘强度图像创建边缘角位图。边缘角位图是将组成边缘角图像的每个点的边缘角表示为角位的图像数据。因此，获得边缘角位图。下文描述从边缘角图像到边缘角位图的转换。

(步骤S1804-边缘角位图的缩减)

此外，在步骤S1804中，通过边缘角位图缩减装置78缩减获得的边缘角位图。在创建用于大面积搜索的第二图案模的情况下将缩减比例设置为用于大面积的缩减比例，并且在创建用于局部搜索的第一图案模型的情况下将缩减比例设置为中等缩减比例。因此，获得边缘角位图的缩减比例。

(步骤S1805-大面积搜索的执行)

接着，通过使用预缩减的图案模型对在步骤S1804中缩减的边缘角位缩减图像执行大面积搜索。具体地说，在整个范围中执行搜索，同时改变图案模型的角，以从左上到右下扫描图像。从而提取检测候选的区域。例如，分别由XY坐标和角θ等来表示检测候选的位置和姿态。通过分值计算找出检测候选。以搜索位置和姿态的自由程度通过粗搜索装置71移动缩减的图案模型，并且在每个位置和姿态计算一个分值。

(分值计算)

通过比较包括在图案模型中的各自边缘点的边缘角图像和边缘角位图执行大面积搜索中的分值计算，以计算一致性，其中边缘角位图通过将待搜索图像缩减至用于大面积的搜索比例获得。在执行搜索时，与其中计算分值的位置和姿态相应地改变关于参考点的位置和角的数据。接着，如在边缘角位图中一样转换角，并且在缩减之后对边缘角位图数据的像素值执行AND处理。将通过用剩余位数的总值获得的值除以获得总值的最大值看作由粗搜索装置71计算的一致度。此外，可在角方向上分配多个位以增加加权的概念。

(步骤S1806-局部搜索的执行)

此外，对在大面积搜索中找到的检测候选区域执行局部搜索。在局部搜索中，使用具有低于用于大面积搜索的图案模型的缩减比例的用于局部搜索的图案模型。此外，也与边缘角位图作为待搜索图像一样，使用由低于用于大面积的缩减比例的用于局部搜索的缩减比例缩减的缩减图像。

此外，在执行局部搜索时，不仅对在大面积搜索中找出的检测候选的区域执行局部搜索，也可在其附近(例如，对如3×3像素和5×5像素的周围像素)执行局部搜索。从而可获得稳定的搜素结果。

(扩展处理)

即，为了稳定分值计算结果，也可在执行粗搜索时执行放大处理。通常出现一种趋势，当待搜索图像的缩减比例减小以增加准确度时，即使轻微的位置位移也会造成分值的大幅度减小。为了避免分值的快速改变可微小地改变旋转角，但是这种情况下，发生增加处理量的缺点。因此，在考虑处理量的缩减和准确度的改进之间的平衡中，仅通过预定量放大作为被搜检图像的边缘角位图。例如，通过预定像素数(例如通过加倍一个像素获得的2×2像素)在其XY方向上放大图像。因此可抑制由于角的轻微位移造成分值的快速波动，以获得稳定的分值。

在这种方式中，基于计算的分值在缩减的图案模型的缩减的待搜索图像中确定大致位置。此外，根据需要可重复上述步骤，以增强大致位置的准确度。即，不仅简单地将粗搜索分为一分为二(大面积搜索和局部搜索)，而且可将局部搜索分为多次，并且可通过逐渐降低待搜索图像的缩减比例使用更大程度缩减的待搜索图像，以执行高准确度的定位。

应该注意，由于其宽量程和大处理量，通常仅执行一次大面积搜索。但是，可根据需要的准确度和间隔时间执行多次大面积搜索。此外，对于搜索技术，可使用已知搜索技术，如边缘搜索、标准相关搜索、广义的霍夫变换或者几何哈希。

(在移动期间的细定位的细节)

以如上方式执行粗搜索并且找到关于存在图案模型的检测候选的位置和姿态的数据后，通过细定位装置76执行细定位。接着，基于图20的流程图详细描述用于细定位的特定过程。

首先，在步骤S2001中，基于在粗搜索中找到的检测候选的位置和姿态，在待搜索图像上叠加用于细定位的图案模型。优选地，将原始大小的待搜索图像和用于细定位的同时在粗搜索中最终找到位置和姿态的图案模型用作起始位置和起始姿态。但是，也可以高于原始大小(缩减比例为1)并低于最终在粗搜索中使用的缩减比例的缩减比例来执行细定位。

此外，在步骤S2002中，沿着用于细定位的图案模型的相应点搜索线求出作为相应边缘点的点。如上所述，相应点搜索线是在垂直于段的方向上延伸的具有预定长度的线，并且将作为线段的两个端点之一的起始点看作是搜索起始点，并且将终点看作搜索终点。首先，沿着相应点搜索线执行边缘计算，以获得边缘向量。作为用于边缘计算的技术，如上所述，可根据需要使用索贝尔(Sobel)滤波器。在相应点搜索线上求出通过该边缘计算获得的边缘向量、每个点的边缘角、边缘强度、边缘位置等点。应该注意，边缘向量是通过向量表示边缘强度和方位的向量，并且可以将其表示为如(Ex，Ey)。例如，如图46所示，当边缘强度是EM且边缘角是θE时，将这些表示为：边缘角θE＝Atan(Ey/Ex)；和边缘强度EM＝sqrt(Ex²+Ey²)。

(相应边缘点搜索处理)

此外，基于关于边缘向量、边缘角、边缘位置等的信息，找到与包括相应点搜索线的参考点的段相应的相应边缘点。作为用于确定相应边缘点的方法的示例，可通过使用前述边缘向量高速地确定相应边缘点。作为另一种方法，可通过使用下述边缘强度和边缘角来执行计算，但是这种情况下，需要计算下述反正切函数(Atan)，计算变得复杂。下文描述的是通过使用边缘强度和边缘角来获得相应边缘点的过程。

首先，将具有边缘强度大于预定边缘强度门限并且此处边缘角与参考点的角之间差的绝对值小于预定边缘角门限的最大点作为相应边缘点的候选。此外，最终将相应边缘点候选中最接近参考点的点看作相应边缘点。

此外，求出相应边缘点的边缘的子像素位置(步骤S2003)。使用段的位置和几何数据，获得误差值，并且执行最小平方法的计算(步骤S2004)，以获得精细位置(步骤S2005)。在线段情况下的误差值示例包括相应边缘点和直线之间的距离，并且在圆弧段情况下的误差值示例包括半径和相应点与中心位置之间的距离之间的差异的绝对值。

如上所述，通过细定位装置76计算最小平方法的计算中使用的误差值或权值，并且从计算值获取由最小平方法获得的联立方程。采用最小平方法以使段具有理想形状并且使与段相应的多个相应点的误差最小。此外，解联立方程，以求出高准确度的位置和姿态。在这种方式中，获得位置X的修正量Δx、位置Y的修正量Δy、角θ的修正量Δθ、标度(scale)“s”的修正量Δs。

在细定位中，通过使用在粗搜索中获得的关于位置和姿态的数据将参考点叠加到待搜索图像上。接着，沿着相应点搜索线执行如索贝尔(Sobel)滤波的边缘计算，以获得边缘向量。应该注意，边缘向量由索贝尔滤波器应用的结果表示，并且可由(Sx，Sy)等表示。此外，可由“$>\mathrm{EM}=\sqrt{{\mathrm{Sx}}^2+{\mathrm{Sy}}^2}$>”表示边缘强度EM并且可将边缘角θE表示为“θE＝Atan(Sy/Sx)”等。此外，从边缘向量在相应边缘点获得像素的边缘角、边缘强度和位置。从这些边缘向量、边缘角、边缘强度和位置，通过细定位装置76求出与包括相应边缘点的参考点的段相应的相应边缘点。

基于图21A描述该状态。首先，通过细定位装置76将由粗实线表示的图案模型PM叠加并安排到在粗搜索中获得的待搜索图像(由虚线表示的边缘角位缩减图像EABR)的检测候选的位置中。接着，沿着通过设置在图案模型上的参考点KT并几乎垂直于图案模型的段的相应点搜索线TL，求出与参考点KT相应的相应边缘点TT。在图21A中，由细实线表示相应点搜索线TL。应该注意，相应点搜索线TL是虚构设置线，并且不是实际画出的。相应边缘点TT变为相应点搜索线TL与缩减图像EABR的交点。通过使用相应边缘点TT，可获得子像素坐标位置。通过使用段的位置和几何数据，由细定位装置76执行细定位。

具体地说，通过使用段的几何数据(该情况中是线)与被看作评估值的相应边缘点之间的关系，执行分值计算以使评估值的累计值最小化或者最大化。作为评估值，通常可使用距离，并且通过将该距离看作误差值，执行最小平方法的计算以使误差值最小化，从而可获得精细位置。使用的距离可以是段与相应边缘点之间的欧几里德距离。即，在段为线的情况下，使用相应边缘点与直线之间的距离，并且在段为圆弧的情况下，使用半径与介于相应边缘点与中心位置之间距离之间的差的绝对值。求解通过使用最小平方法获得的联立方程可求出高准确度的位置和姿态。此外，评估值不限于距离，并且可以为由参考点和参考点的相应边缘点形成的角。

此外，图21B示出了其中细定位装置76求出相应边缘点的相应边缘点搜索处理的状态。在该图中，如图21A，虚线表示待搜索图像的缩减图像EABR，粗实线表示图案模型PM，并且细实线表示设置在参考点KT上的相应点搜索线TL。这种情况下求出的是在缩减图像EABR的3×3像素的区域SR中应用索贝尔滤波器中的坐标位置x、y。通过使用创建直线数据的布雷森汉姆(Bresenham)算法来求出该计算中的中心坐标。在图21B的示例中，提取像素B作为关于模型边缘点A的相应边缘点。

图21B所示的方法不同于上述日本专利No.3759983，原因在于在自动提取相应边缘点的段上适当选择的的点被看作参考点。特别地，在日本专利No.3759983中，没有定义用于查找线(seek-line)的安排方法。此外，在确定相应边缘点时，除了边缘强度之外，还使用关于边缘角、边缘位置等的数据，从而改进相应边缘点的可靠性。此外，使获得边缘角和边缘强度的处理中使用的内核更小，以降低计算处理的负荷。此外，可使用子像素准确度获得相应边缘点的位置。此外，最小平方法的使用可产生能以各种形状对应于模型的优点。

在上述这种方式中，可在图案搜索中执行高准确度的高速定位。尤其在这种方法中，通过改变相应点搜索线的线长，通过相应点搜索线的方式可容易地改变搜索相应边缘点的范围，以获得可调整所需稳定性的优点。即，在最小平方法的重复使用时通过逐渐减小相应点搜索线的长度，可容易地实现更高速更高准确度的定位。

此外，由于图案模型由段表示，可消除如图22所示的边缘位置的波纹现象。即在执行各个点之间的细定位的情况下，在较高波形的相应点与较低波形相应点之间可能发生大的位置位移，但是可以减小这种影响。

此外，代替或者除此之外，在每次最小平方法重复中可以改变边缘角门限。即，根据最小平方法重复的次数逐渐减小边缘角门限也允许更稳定定位的实现。

应该注意，基于粗搜索中获得的初始位置或者在另一粗搜索中获得的细定位起始位置在待搜索图像上叠加图案模型时，使用未处理数据(所谓的原始图像数据)作为待搜索图像，并且使用与原始图像数据相应的图案模型作为图案模型。

该方法可消除将待搜索图像的原始图像数据中的所有像素转换为边缘图像数据的需要，以寻求处理的加速。特别地，在需要间隔时间的内处理(inline processing)中，优选这种高速低负荷的处理。不用说，当边缘数据的总的预提取更高效时，可将待搜索图像的所有点转换为边缘图像数据以执行图案搜索。

此外，在待搜索图像上叠加并安排整个图案模型不是必须的，而叠加并安排至少相应点搜索线就足够。特别地，由于相应点搜索线是直线，可通过计算容易地获得。因此，在本说明书中，术语“叠加”不是必须意味着实际叠加图像，而是用作根据相应点搜索线确定相应边缘点的处理的意思。此外，这种情况下的短语“叠加并安排”意在描述使每个图像的相应位置容易通过其如上所述的叠加而得到，其中该叠加在计算中仅仅是虚构的，并且不必说，实际叠加数据的操作不是必须的。

根据该方法，与通常方法比较可实现高准确度的基于边缘的搜索。在上述日本专利No.3759983的技术中，不考虑边缘的方向和角分量，而仅仅考虑预定义边缘方向，并且因此不能获得复杂形状中的稳定性。与此相反，在根据本实施例的技术中，重要性依赖于边缘方向，从而允许增强相应边缘点的可靠性。此外，在本实施例中，由于通过使用内核的小滤波器(如索贝尔滤波器)计算差异，所以即使当工件长并且窄时，也能检测到边缘。如上所述，与日本专利No.3759983的技术相比，可实现稳定的适用于复杂形状中的待搜索对象的基于边缘的搜索。

此外，在图案模型的待搜索图像中获得检测候选的位置(即局部搜索中的初始位置)时，通过缩减待搜索图像并执行搜索具有执行高速低负荷图案搜索的优点。但是，由于缩减造成准确度的恶化可能丢失部分信息，因此需要执行缩减以保留信息量(下文描述)。此外，除了在粗搜索中图案模型的初始位置的获得之外，用户还可以专门手动指定位置。

上述示例中提到的点的意思是组成待搜索图像或者已登记图像的点，即一个像素，但是不必说，可集合多个像素(如四个像素)作为一个点。因此，在本说明书中，点的意思是一个像素或者预定数量的像素。

此外，不仅在对参考点上执行边缘检测的意思中使用短语“基于参考点”，而且在包括在参考点的附近执行边缘检测的意思中使用。例如，在指定范围内(如参考点周围从1至10个像素的范围)执行边缘检测。

此外，段是指由线和/或圆弧或者其组合构成的具有有限长度的连续线。此外，除了线和圆弧之外，还可以组合圆锥形曲线、齿条曲线、贝塞尔(Bezier)曲线等。此外，相应点搜索线的数据包括参考点的坐标以及相应点搜索线的角和长度。

(最小平方法)

在最小平方法中，直线误差函数适用于线段。直线误差函数是以点与线之间的距离作为误差函数的最小平方法。此外，圆弧误差函数适用于圆弧段。圆弧误差函数是以点与圆弧之间的距离作为误差函数的最小平方法。这将在下文描述。

最小平方法的问题示例包括，当即使存在一个非常不同的值时，由于该点的影响准确度极大地恶化。因此，在本技术中，使用使其具有权值以降低这种点上的权值的加权最小平方法来抑制该影响。

此外，作为在最小平方法中被使用的自由度，可使用X方向上的移动、Y方向上的移动、旋转、放大/缩减、歪斜、方位等。除了XY方向上的平行移动之外，选择这些还可对应于已登记图像的旋转、放大/缩减、扭曲等。

(最小平方法的误差函数的一般化)

归纳并产生最小平方法的误差函数。首先，考虑通过仿射参数p0，p1，…pn(如p0＝x，p1＝y等)确定误差函数E(p0，p1，…pn)。假设通过最佳仿射参数p0o，p1o，…pno(o：最佳的)最小化误差函数E(p0，p1，…pn)。此时，由如下表达式表示误差函数E(p0，p1，…pn)：

[表达式13]

$>E(p_0,p_1,...p_n)=\underset{i}{\Sigma }{\omega }_i{e}_i{(p_0,p_1,...p_n)}^2$>

上述表达式中参数的含义如下：

i：相应边缘点的下标

ω_i：根据相应边缘点与模型之间的位置关系确定的权重。例如，当相应边缘点与线之间的点到线的距离较长时，定义该参数近似为0。

e(p0，p1…pn)：由相应边缘点与模型之间的几何距离确定的单独的误差函数。该参数由相应边缘点与线段之间的点到线的距离等确定。

p0至pn：平行的x-移动量、平行的y-移动量、旋转角度、标度值等的仿射参数。

为了求出使误差函数E(p0，p1，…pn)最小的仿射参数p0o，p1o，…pno，如下从获得其充分接近待求出仿射参数并在粗搜索中或在最后细定位中获得的仿射参数p0t、p1t，…pnt求出位移量：

[表达式14]

Δp₀，Δp₁，...，Δp_n

(p_i0≈p_it+Δp_i)

(t：近似解(trial))

通过求解下述联立方程获得Δp₀，Δp₁，...，Δp_n：

[表达式15]

$>\left(\begin{array}{cccc}{\Sigma }_i{\omega }_i\frac{\partial e_i}{\partial p_0}\frac{\partial e_i}{\partial p_0}& {\Sigma }_i{\omega }_i\frac{\partial e_i}{\partial p_0}\frac{\partial e_i}{\partial p_1}& ···& {\Sigma }_i{\omega }_i\frac{\partial e_i}{\partial p_0}\frac{\partial e_i}{\partial p_n}\\ {\Sigma }_i{\omega }_i\frac{\partial e_i}{\partial p_1}\frac{\partial e_i}{\partial p_0}& {\Sigma }_i{\omega }_i\frac{\partial e_i}{\partial p_1}\frac{\partial e_i}{\partial p_1}& ···& {\Sigma }_i{\omega }_i\frac{\partial e_i}{\partial p_1}\frac{\partial e_i}{\partial p_n}\\ ···& & ···& \\ {\Sigma }_i{\omega }_i\frac{\partial e_i}{\partial p_n}\frac{\partial e_i}{\partial p_0}& {\Sigma }_i{\omega }_i\frac{\partial e_i}{\partial p_n}\frac{\partial e_i}{\partial p_1}& ···& {\Sigma }_i{\omega }_i\frac{\partial e_i}{\partial p_n}\frac{\partial e_i}{\partial p_n}\end{array}\right)\left(\begin{array}{c}\Delta p_0\\ \Delta p_1\\ \\ \Delta p_n\end{array}\right)=\left(\begin{array}{c}-{\Sigma }_i{\omega }_i{e}_i\frac{\partial e_i}{\partial p_0}\\ -{\Sigma }_i{\omega }_i{e}_i\frac{\partial e_i}{\partial p_1}\\ ···\\ -{\Sigma }_i{\omega }_i{e}_i\frac{\partial e_i}{\partial p_n}\end{array}\right)$>

如上所述，图像的边缘角及其边缘强度的使用可增加方向分量，从而允许稳定定位抗噪声分量。特别地，通过使用对图像数据的差分处理，可执行不易受亮度影响的稳定搜索。

(相应点搜索线过滤处理)

特别地，对已登记图像执行相应点搜索线的搜索处理来选择相应点搜索线可能非常困难，优选地从图案搜索中消除这样的位置。例如，考虑如图23的已登记图像存在的情况，当自动地设置在该图案上自动设置的相应点搜索线时，如图24所示那样设置。如该图中所示，不仅在周围轮廓上设置相应点搜索线，而且在位于内部中心的附近具有对比度差的部分设置。当通过这种设置在中心附近的相应点搜索线的方式执行边缘匹配时，产生大量具有类似边缘角的部分。因此，当通过使用这些相应点搜索线执行图案搜索时，在相应边缘点检测中相应边缘点更可能变得模糊。

在本实施例中，消除了这种模糊的相应点搜索线，允许稳定、高准确度搜索的性能。具体地说，通过相应点搜索线过滤装置过滤在这种不利区域中设置的相应点搜索线，并且当存在一个具有类似边缘强度和边缘角相应点边缘线时，消除该线。图25示出了过滤来自图24的相应点搜索线的结果的示例。

基于图26的流程图描述以上述方式对相应点搜索线的候选执行相应点搜索线过滤处理的过程的示例。首先，在步骤S2601中，对已登记图像执行相应点搜索线创建处理，以创建用于相应点搜索线的候选。接着，在步骤S2602中，针对已登记图像安排用于相应点搜索线的候选。当安排到创建相应点搜索线的位置时，可在相应点搜索线候选的中部附近检测到相应点搜索线的候选。

此外，在步骤S2603中，沿着相应点搜索线的候选执行相应点搜索线候选的搜索，以分别计算相应点搜索线候选的数量。此外，在步骤S2604中，执行过滤处理，并且在相应点搜索线的候选数量为2或者更大的情况下，确定的相应点搜索线很可能是模糊的，并且因此从相应点搜索线的候选被消除。在步骤S2605中，将剩余相应点搜索线看作是最终相应点搜索线。通过该处理，消除未确定的相应点搜索线，从而可获得更稳定的图案模型结果。

应该注意，在重复细定位步骤的情况下，由于根据重复的次数使相应点搜索线的线长更小，因此预先记录在一次执行相应点搜索线的过滤处理中选择的相应点搜索线，并且可在重复的步骤中使用该信息。可选择地，同样在相应点搜索线变短的情况下，类似地执行相应点搜索线的过滤处理，并且可记录选择的作为处理结果的相应点搜索线。

(相应点搜索线)

此外，通过改变相应点搜索线的线长，可获得改进细定位的稳定性并使其加速。基于粗搜索和细定位之间的缩减比例的差异来确定相应点搜索线的线长。例如，当在未放大图像上执行细定位并且以四分之一的缩减比例执行最终粗搜索时，长度设置为8个像素(2*4＝8)的程度。

(链条过滤装置66)

在如上所述示例中，针对每个段设置至少一个参考点。在本实施例中，在创建段时，选择组成段的链条，以预先构造高可靠性的段并且在每个段中设置参考点。通过图1方框图所示的链条过滤装置66来执行这种特定链条的选择和消除。通过链条过滤装置66的链条选择的参考示例包括平均边缘强度和链条长度。

该链条过滤装置66在登记时和在移动期间执行链条选择。在登记时，提取可组成段的链条。具体地说，执行过滤以消除具有不满足预定链条长度门限的小长度的链条和具有不满足预定边缘强度的低平均边缘强度的链条，因为即使当从这些链条创建了段，段数据的可靠性也是很低的。

同时，在移动期间，由于短链条很可能是噪声，根据待搜索的状态来选择是否使用该链条。例如，用户设置一个长度门限，以消除短链条。在下文中，逐渐详细描述这些。

首先，在基于平均边缘强度执行过滤的情况下，链条过滤装置66通过计算针对每个链条包括的每个边缘点的平均边缘强度并且比较计算值与预设平均边缘强度门限来执行过滤。即，消除具有低平均边缘强度的链条，并仅分段具有平均边缘强度不小于固定强度的链条。针对获得的段设置参考点来创建图案模型，以使可获得基于具有高准确度的边缘的图案模型并且可增强搜索准确度。用户可将平均边缘强度门限设置为包括足够边缘强度来识别图案模型轮廓的这种程度。

此外，在基于链条长度执行过滤的情况下，链条过滤装置66通过比较每个链条长度与预设链条长度门限来执行过滤。即，仅选择具有不小于固定长度的链条长度的链条，并且消除短于固定长度的链条，以使可基于稳定边缘执行图案搜索，以有助于准确度的改进。

同时，也可使用对构成链条的段执行过滤的段选择装置67。类似于上述链条过滤装置66，通过段选择装置67的段选择的参考示例包括平均边缘强度、段长度、是否在附近存在具有类似边缘角的边缘角图像以及相同边缘角的分布不均匀的消除。此外，可不均匀地简单消除短段，但是可以根据组成段的线和圆弧的结合改变过滤段的方法。例如，在从段的集合提取足够长的段并且消除这些组合以发现存在一个或多个弧部分段的情况下，当也存在一条或多条线时，认为较短的段是不必要的并且因此消除或者删除这些。此外，在每个段为线的情况下，当存在三个或更多长段时，即使消除了其他较短段也可保持足够的准确度。如上所述，可根据组成段的组合改变段选择装置67的过滤并且可选择适当的段，以使可更有效地执行搜索。

应该注意，这种情况下的段长度的意思是从组成图案模型的每个段的该线或圆弧的一端到另一端的直线或曲线的长度。此外，可单独提供线长和圆弧长度的各个段长度门限。根据已登记图像、所需准确度等设置段长度门限，或者可基于已登记图像或者待搜索图像的平均段长度设置。

此外，当基于在附近是否存在具有类似边缘角的段执行过滤时，段选择装置67按照包括在每个段中的边缘点的边缘角确定附近是否存在具有类似边缘角的另一段，并且当期存在时消除这种段。即，考虑由于存在具有类似边缘角的段导致图案搜索结果可能不稳定的可能性，消除这种段并接着设置参考点，从而增强图案搜索结果的稳定性。

(试验性的相应边缘点)

接着，基于图29描述求出与细定位中参考点相应的相应边缘点的坐标的过程。首先在相应点搜索线TL上求出相应边缘点，并且找到作为一对的另一个相应边缘点。从这两点找到平均坐标，并且将获得的坐标看作实际相应边缘点的坐标。

具体地说，在图29中，在圆弧段的部分(由图中圆表示的位置)设置参考点KT，并且从左上至右下延伸通过该点的相应点搜索线TL。首先，沿着相应点搜索线TL检查待搜索图像的每个点的边缘强度。在图29的示例中，基于参考点KT求出边缘强度。在作为包括参考点KT的方格顶点的四个点“a”、“b”、“c”和“d”的每个检查边缘强度。求出具有最大边缘强度的点的子像素位置作为试验性相应边缘点。因此，当与点“a”的子像素位置一样计算“e”作为试验性相应边缘点时，接着选择与该试验性相应边缘点“e”相应的一对点。选择这对点以使试验性相应边缘点“e”和这对点将参考点KT夹在中间。假设在选择“f”作为这对点的情况下。此外，从试验性相应边缘点“e”和这对点“f”获得平均坐标。接着将获得的平均坐标作为实际相应边缘点坐标。

在这种方式中，可抑制在波纹形状中相应边缘点的计算，以获得稳定的计算结果。即，在点之间执行细定位的情况下，在较高波形的相应点和较低波形的相应点之间可能会发生大位置位移，但是可通过上述技术减小这种影响。

(通过使用相邻边缘点获得相应边缘点的坐标的方法)

此外，以子像素为单位求出相应边缘点的坐标的方法不限于上述方法，也可使用另一种方法。例如，在下述方法中也可实现求出坐标。以像素为单位在相应点搜索线上搜索相应边缘点，并且将获得的点看作试验性相应边缘点。以像素为单位找出该试验性相应边缘点周围的多个相邻边缘点。求出试验性相应边缘点与多个相邻边缘点的子像素坐标，并且接着求出这些点的平均坐标。通过这种方法，可通过使用试验性相应边缘点和多个相邻边缘点求出实际相应边缘点的位置，并且因此可获得以像素为单位的具有很好准确度的相应边缘点的坐标位置。此外，不使用相应点搜索线而使用多个在试验性相应边缘点周围适当选择的相邻边缘点，可以类似方式准确地确定相应边缘点的坐标位置。

可选择位于试验性相应边缘点周围相同轮廓或者段的边缘点作为如相邻边缘点。此外，通过使用试验性相应边缘点的边缘角，可获得具有类似边缘角的相邻边缘点。优选地，使用设置在中心的试验性相应边缘点的边缘角方向，分别选择与右边和左边临近的边缘点作为相邻边缘点。此外，希望从试验性相应边缘点到相邻边缘点的距离接近，例如在两个像素之内，优选地大约一个像素的量级。这是因为太远的距离造成准确度的恶化。在下文中，基于图65的示意图和图66的流程图描述通过使用相邻边缘点获得相应边缘点的坐标的过程。

首先，在步骤S6601中，以像素为单位在相应点搜索线上搜索试验性相应边缘点。在图65中，带阴影的白圆圈是参考点KT，并且在通过参考点KT的相应点搜索线TL上求出与组成轮廓的段相应的位置。以像素为单位执行搜索，即，以图65中方格的每个交点作为参考，并且在这种情况下的像素坐标中选择(x，y)＝(2，3)。

接着，在步骤S6602中，在以像素为单位的试验性相应边缘点周围以像素为单位选择相邻边缘点。由于试验性相应边缘点的边缘角在叠加到相应点搜索线的方向上具有向量，分别选择夹着相应点搜索线并位于其右和左同时也具有不小于预定值的边缘强度的点作为相邻边缘点。具体地说，选择位于右边的第一相邻边缘点和位于左边的第二相邻边缘点。在图65的示例中，第一相邻边缘点的像素坐标是(2，2)，并且第二相邻边缘点的像素坐标是(1，3)。此时，由于各自相邻边缘点的边缘角是试验性相应边缘点附近的边缘点，所以相邻边缘点很可能具有类似边缘角，并且因此不需要检查边缘角。不必说，可在检查其边缘角的高度相似度之后选择那些边缘点作为相邻边缘点。应该注意，当在附近位置没有具有边缘强度小于预定值的边缘点时，没有选择相邻边缘点。这种情况下，仅通过使用获得的边缘点(试验性相应边缘点和另一相邻边缘点)来计算下文所述的实际相应边缘点。此外，尽管在该示例中选择了在右边和左边的两个相邻边缘点的全部，但是所选择的相邻边缘点的数量也可以是一个或者不少于三个。但是，考虑到准确度和计算处理的负荷之间的平衡，数量优选为两个。

此外，在步骤S6603中，基于试验性相应边缘点和相邻边缘点计算实际相应边缘点的坐标。确定实际相应边缘点的坐标位置作为试验性相应边缘点和相邻边缘点的子像素位置的平均坐标。在图65的示例中，从三个点(作为试验性相应边缘点的子像素位置的黑圆圈表示的TP1；作为第一相邻边缘点的子像素位置由带阴影的圆圈表示的TP2；和作为第二相邻边缘点的子像素位置由画有交叉阴影线的圆表示的TP3)的平均确定相应边缘点。预先从像素值附近计算每个边缘点的子像素位置。可将一种已知的方法应用到计算子像素位置的方法。例如，可从设置在其中心的每个边缘点周围3×3像素的像素值计算子像素位置，或者通过使用关于在边缘角方向上存在的相邻边缘点的信息来计算，或者通过一些其他方式计算。应该注意，计算每个边缘点的子像素位置的时间选择不特别受限制，并且时间可以是紧接着以像素为单位的边缘点确定之后或者是紧接着平均坐标计算之前。

在上述这种方式中，可从三个边缘点的子像素坐标的平均值计算相应边缘点。使用这种方法，可容易地从试验性相应边缘点提取三个边缘点，通过使用许多边缘点可确定高准确度的相应边缘点。例如，在参考点数量为10的情况下，相应边缘点的数量通常为10，但是使用上述方法，可对10个试验性相应边缘点分别在其右边和左边增加多个点，并且因此可从30边缘点计算相应边缘点，从而由于平均效应改善了准确度。具体地说，作为与上述从配对点和试验性相应边缘点两个点求出平均坐标的方法的比较，由于试验性相应边缘点及其增加的两个相邻边缘点三点求出平均坐标，该方法在准确度方面是有利的。应该注意，三点是在以上获得并求平均的，可单独在细定位计算中使用这三点。

(边缘角图像到边缘角位图的转换)

接着，基于图30至图33描述从边缘角图像到边缘角位图的转换。基于采取粗到细的方法，在第一粗搜索中不容易设置缩减图像。这是因为通过图像缩减可能丢失关于搜索必须的特征量的信息。特别地，在基于边缘的搜索中，对于改进搜索中的准确度来说，边缘角信息很重要。因此，在本实施例中，提供即使当减薄装置61进行图像的缩减时使缩减比例很高时仍然能保留边缘角信息的边缘角位图创建装置69和边缘角位图缩减装置78，以在保持足够特征量的同时减小数据量，从而加速处理。

下文描述的是通过减薄装置在缩减图像时获取边缘角信息并保留该信息的过程。首先，检查边缘角图像的每个边缘点的边缘强度，并且在边缘强度大于设置的边缘强度门限的情况下将对应于边缘角方位的位设置为1，并且在其他情况下，将该位设置为0。例如，考虑从图30所示的四个像素(边缘点)“a”至“d”组成的2×2像素的边缘角图像由边缘角位图创建装置69创建边缘角位图的情况。像素“a”至“d”的每个都具有大于门限的边缘强度，并且也具有由箭头表示的边缘强度。根据表示边缘角与位一致的边缘角部分由0至7的八种边缘角位表示该边缘角。

(边缘角位图)

在该边缘角图像到边缘角位图的转换时，将边缘角信息转换为边缘角位。边缘角位是一种针对每个预定角划分边缘角方向的编码。对图31所示的边缘角部分，可应用与如上所述图6B中一样的。在图31的示例中，以45度将作为边缘角方向的密集梯度方向划分为八个部分，并且为每部分分配边缘角位。该示例不是限制性的。这些部分可能还从图31的姿态以22.5度逆时针旋转，成为从水平或者垂直方向的位移22.5度的八个部分，并且以E、SE、S、SW、W、NW、N、NE可从右顺时针标记各边缘角部分，每部分具有45度的宽度，并且接着针对各边缘角部分增加边缘角位标记0、1、2、3、4、5、6、7(上述图52B)。当然，这种划分是示例性的，并且例如，可将边缘角划分为十六部分、四部分或者还可以是三部分或者五部分。

如上所述，当基于图31的边缘角部分将图30所示的边缘角图像数据转换为2×2边缘角位图时，转换的图像如图32所示。如上所述，将位设为与针对由标签“a”、“b”、“c”、“d”划分的四个边缘点的各边缘角相应的边缘角部分。

作为用于获得边缘角位图的方法，除了仅对如上所述不小于某一边缘强度门限的部分执行处理的技术之外，还有一种通过使用边缘强度图像和边缘角图像执行减薄处理的方法，以通过使用为了获得具有某一宽度的边缘角位图而进行减薄处理的边缘角图像获得如上所述的边缘角位图。在执行减薄处理技术的情况下，与上述技术相比处理时间相对较长，但是由于可限制待搜索对象的轮廓部分，所以具有有助于噪声消除的优点。

(边缘角位图的缩减)

如上所述，在通过边缘角位图的表示之后，减小了数据以充分保留边缘角信息。具体地说，数据是合成的，从而如关于每个边缘位标记采用“OR”或每个像素的每个边缘角位的比特相加。例如，在图32的状态中缩减2×2数据的情况下，当将其缩减为1/2长×1/2侧边(＝1/4)来用一个像素“a”表示四个像素“a”至“d”时，缩减数据如图33中所示。如该图所示，在像素“a”至“d”集中在一起的边缘角位缩减图像中合成每个像素的边缘位，并且以对应于边缘角位标记0至7的列来建立边缘角位。通过边缘角位图缩减装置78执行存储在边缘角位缩减图像中边缘角信息的处理。从而，当减小数据量时，即使在缩减之后也能保留边缘角信息，并且因此即使当通过重复缩减增大缩减比例时仍然能保留用于搜索的足够的特征量。

上述压缩处理可改进通常当为了保留足够的用于搜索的特征量抑制缩减比例时搜索处理速度变得不足的问题状态。即使当将执行边缘检测的缩减比例固定为二分之一时，例如可通过用该缩减比例缩减边缘角位图的处理执行足够高速的搜索。可基于至少已登记图像大小或者图案模型的特征数据自动地确定执行边缘检测的缩减比例。此外，可安排用户单独设置缩减比例。

基于图34至图37描述为创建边缘角位缩减图像缩减边缘角位图的过程的示例。在创建边缘角位缩减图像时，应该注意分段问题。即，通过子采样处理简单地执行缩减处理可引起由于待搜索对象的输入图像中的处理起始坐标或者位置的微小位移造成下述分值计算中的大的变化发生。作为避免这种分段问题的缩减方法，可考虑下述两种方法。

第一方法是在缩减处理之后执行扩展的方法。使用图34和图35采用缩减为1/n(n＝2)的处理示例描述该方法。首先，对包括在图34的每个矩形区域中的n×n边缘角位数据执行OR运算。运算结果被代替为表示上述每个n×n区域的边缘角位数据的边缘角位数据。执行该处理可将图像缩减为原始图像的1/n。

由于使该缩减图像处于该状态可引起分段问题的发生，对该图像执行扩展。如图35所示，在缩减之后对图像中每个m×m(该示例中m＝2)矩形区域中的边缘角位数据执行OR运算，并且其结果被代替为表示每个m×m区域的边缘角位数据。在该处理中，没有发生图像缩减。该示例中“m＝2”，但是可以根据期望的待搜索对象形状和大小的改变增加“m”。

另一种方法是在上述缩减处理中为要执行的OR运算采用非常宽的范围并且不执行随后的扩展。通过使用图36，采用将图像缩减为1/n(n＝2)的处理的情况描述该方法。对包括在图36的每个矩形区域的(n+m)×(n+m)(n＝1，m＝1)边缘角位数据执行OR运算。该运算的结果被代替为表示上述区域的中心附近的n×n边缘角位数据的每个的边缘角位数据。执行该处理可将图像缩减为原始图像的1/n。图37示出了在第二方法中n＝2和m＝1的情况。

如图36所示，在不扩展以2×2重复正常缩减的情况下，可能发生分段问题。即，随着搜索区域的左上方坐标中一个像素的改变，在缩减时的像素设置改变，并且因此即使已登记图像与待搜索图像相同分值计算也恶化。与此相反，执行扩展引起不产生这种问题的优点。(角边界内的边缘角位转换处理)

此外，在边缘角位的转换时，当边缘角在角边界附近时建立与组成角边界的两个角区域相应的两个位，并且因此可获得改进稳定性的效果。例如，在上述通过转换由图30所示四个像素“a”至“d”组成的边缘角图像获得的图31的边缘角位图中，当边缘角在E和SE之间的边界附近时，取决于噪声，可建立E部分中的边缘角位，或者可建立SE中的边缘角位。期望这种旋转造成对一致性的计算产生非本质的影响。因此，当边缘角在边界上时，将划分边界的两个边缘角部分均设置为1。从而，可消除由于噪声引起的旋转，并且可获得稳定的一致性的计算结果。具体地说，当边缘角位于在中心设置边缘角部分的边界的预定宽度内(如5.625度)，将面向边界的两个边缘角位设置为1.

应该注意，仅在对待搜索对象的边缘角位转换处理的情况下，执行该对角边界的边缘角位转换处理，并且在图案模型的边缘角位的转换情况下不执行。这是因为在图案的边缘角的转换情况下执行相同的处理引起针对每个边缘点权重的不自然改变。

(边缘角位相邻处理)

此外，尽管仅在上述示例中从边缘角图像到边缘角位图的转换中设置一个边缘角位，但是也可在中心设置相关边缘角部分并且在每个相邻边缘角部分邻近也设置边缘角位之处执行这种边缘角位相邻处理。例如，将每个边缘角位给到相关边缘角部分和与其右边和左边相邻的边缘角部分。此外，这种加权也可能是将两个边缘角位给到相关边缘角部分并且将一个边缘角位给到与右边和左边相邻的每个边缘角部分。此外，增加模糊效果的这种加权也可能是当图案模型的边缘角与待搜索图像的边缘角充分匹配时给出三个位，当角轻微移位时给出一个位，并且当移位较大时给出零位。

同样在这种边缘角位相邻处理中，如上所述，当边界附近存在边缘角时，可考虑由于噪声通过旋转施加的影响。因此在待搜索图像的边缘角位处于边缘角部分的边界上的情况下，在与设置在中心的边界的每个相邻边缘角部分设置两个位，从而避免旋转的影响。

应该注意，尽管在上述示例中使用8位作为边缘角的角分辨率，但是这不是限制性的，并且也可执行通过更高角分辨率(如16位或者32位)的转换。

(并行处理)

此外，通过并行处理由将图案模型的边缘角转换为边缘角位获得的值，可加速搜索处理。图38和图39示出了并行处理填充的边缘数据的示例。图38是并行处理之前图案模型的概念示图，并且图39是并行处理之后图案模型的概念示图。如这些图中所示，将图案模型上关于参考点的边缘位数据横向地安排在用于并行处理的多个数据中，从而加速处理。通常组成计算部分的CPU可以执行四至八字节的并行处理，并且因此可执行四倍速至八倍速的处理。在这种方式中，可通过并行处理处理加速粗搜索。

(通过使用边缘角位缩减图像的粗搜索)

在下文中，描述通过使用这种缩减数据执行粗搜索的过程。对于该边缘角位缩减图像，例如，当未放大图像的大小为640×480并且以320×240(上述二分之一)的大小执行边缘提取时，压缩处理为八分之一的边缘角位图的大小为40×30。如下文所述执行对该边缘角位缩减图像的搜索。首先，在搜索处理之前登记图案模型时，创建如图40A和图40B所示的数据。如该图所示，将图案模型保存为具有位置和角信息的边缘数据阵列。图40A示出了图案模型的示例，并且图40B示出了边缘数据的图案模型的示例。在图40B中，符号x、y表示边缘的坐标位置，并且符号θ表示边缘的角。将该图案模型保存为具有关于图40B所示坐标位置和角信息的边缘数据阵列。

通过使用上述数据和待搜索图像的边缘角位图，重复改变图案的位置和姿态，针对图案的每个位置和姿态连续计算一致性。如下所述执行该计算。首先，确定表示位置和姿态和希望检测到的一致性的仿射转换值。也根据图案模型的缩减标度和待搜索图像的缩减标度创建该仿射转换值。通过使用该仿射转换值，转换边缘位置xi、yi和边缘角θi。转换之后的边缘位置是Xi、Yi，并且转换之后的边缘角是Φi(i是表示边缘索引的脚标)。通过将边缘角Φi以与待搜索图像的情况一样的方式转换为位数据来计算一致性。用于一致性S的表达式如下：

[表达式16]

EABI(x，y)：待搜索图像的边缘角位图

X_i，Y_i：仿射转换之后的参考点位置

AngleToBit(θ)：将边缘角数据转换为位数据的函数

Φ_i：仿射转换之后关于期望的参考点的边缘角

&：AND处理

！：如果左边等于右边则为0，否则为1

：每个参考点的和

如上所述，细定位装置76比较包括在待搜索图像和图案模型中的各边缘点的边缘强度和边缘角。一致性S高表示在那些位置和姿态中图案模型存在的可能性大。在这种方式中，当以确定的缩减比例执行搜索时，改进其处理速度不足的状态，从而为执行搜索保留足够的特征量。此外，由于可以固定为二分之一的用于执行边缘提取的缩减比例执行足够高速的搜索，所以可获得不必确定用于执行边缘提取的缩减比例(通常很复杂)的优点。

(待搜索图像的缩减步骤)

以这种缩减处理，即使以高缩减比例也可保留用于搜索的足够的特征量。在对待搜索图像执行边缘提取处理(如索贝尔滤波)时，当原始大小的未放大图像保持不变时，产生大量不适合提取用于粗搜索的特征量的噪声。因此，在本实施例中，事先创建缩减图像并且接着执行边缘提取处理。从而，可通过图像数据的缩减获得平均效应，也可减小噪声。将作为第一缩减比例的缩减比例(第一缩减比例)设置为原始大小的二分之一。以该大小，可在保留足够搜索必须的特征量的同时通过平均获得噪声减小的效果。

(边缘方向的极性)

此外，使用这种方法，可设置边缘方向的极性的存在或不存在。因此可根据极性改变处理边缘角的方法。通常，不考虑这种极性的概念，而仅考虑边缘方向(角)的概念，并且因此存在一个问题，例如，将边缘方向(角)视为0到180度，导致不能区分不同方位的向量从而造成错误搜索的发生。与此相反，在上述方法中，通过考虑极性的概念覆盖了0到360度从而实现更准确的搜索。

在忽略极性的情况下，通过同时也建立一个反向位的处理可容易地实现对待搜索对象侧的边缘角位转换。否则，可将位均匀地分配给边缘方向而不是方位。例如在粗搜索中，将8个边缘角位作为边缘分辨率均匀地分配给边缘方向，以使获得其重要性不依赖于边缘极性而依赖于边缘方向的分辨率的搜索结果。

(关于旋转角的细定位)

接着，基于图41至图45描述通过使用点与看作误差角的圆弧之间的距离的最小平方法对圆弧段执行细定位的过程。考虑的是通过作为图案模型PM的图案的方式对待搜索图像执行细定位的情况，图案模型PM通过圆弧段和线段表示局部具有凹口的圆，如图41中粗实线所表示的。图41的图案模型PM由一个圆弧段和一条线段构成，并且通常将这种工件形状应用到提供有定向平面表面的圆片上等。图42示出了通过该图案模型PM的方式对待搜索图像已执行粗搜索从而以安排在检测候选的位置中的图案模型PM执行某一级别的定位的状态。考虑的是几乎将图案模型PM叠加到待搜索图像的边缘点上并且仅凹口部分的线段不匹配的状态。应该注意，在这些图中，粗实线表示图案模型PM，并且细线表示待搜索图像的边缘点(输入边缘点IE)。此外，由虚线箭头表示输入边缘点IE的目标点，并且由虚线表示该输入边缘点的切线SL。应该注意，尽管实际切线SL更短并且存在于叠加到细线的图案模型PM上的状态中，为了描述的方便这些图中显示出来的信号线更长。

当从该状态执行细定位时，可期待相对旋转该图案模型以使线段部分匹配，即如图42，即使通过对由图42中的箭头表示的位置的输入边缘点应用最小平方法的旋转，误差也不是必然变得更大。将其中以点与圆弧之间的距离而不是点与直线之间的距离作为误差函数的最小平方法应用到圆弧段。具体地说，应用最小平方法以使将圆形图案模型的半径与作为圆弧的具有待搜索圆形图案模型的中心的图像的边缘点的半径之间的差的绝对值看作误差值。即，在最小平方法中使用的圆弧段的误差函数是具有圆弧段的中心的理想半径与介于圆弧中心和相应边缘点之间的距离之间的差。可由如下表达式表示圆弧段的误差函数：

[表达式17]

$>e=\mathrm{abs}(R_{\mathrm{ideal}}-\sqrt{{(x-x_c)}^2+{(y-y_c)}^2})$>

R_ideal：理想半径

(x_c，y_c)：圆弧的中心坐标

(x，y)：相应边缘点

[表达式18]

$>e=\mathrm{abs}({(x-x_c)}^2+{(y-y_c)}^2-R_{\mathrm{ideal}}^2)$>

R_ideal：理想半径

(x_c，y_c)：圆弧的中心坐标

(x，y)：相应边缘点

因此，如图43所示，箭头的输入边缘点与圆弧模型之间的距离改变不大。即，这意味着可产生如图43所示的图案模型PM逆时针旋转作为充分程度的解。从而可在很少次执行细定位的圆形工件实现角的高准确度。应该注意，在图42和图43的示例中，实际上将由虚线表示的圆形区域叠加到图案模型的细线上，但是为了描述的方便在这些图中轻微地移位和显示。

同时，在通常的最小平方法中，将输入边缘点与切线之间的距离看作误差函数，并且移动图案模型以缩短该距离。因此可认为在合适的旋转方向不旋转图案模型，并且因此具有增加定位位移的相反效果。例如，存在不能从图47所示的状态获得如图48所示逆时针旋转图案模型PM的情况。即，当从图47所示的在由箭头表示的位置形成输入边缘点与切线之间的关系的状态如图48所示旋转图案模型PM时，在输入边缘点离开切线的方向执行旋转，导致不能产生该旋转作为解。与此相反，在本实施例中，由于应用了上述将点与圆弧之间的距离作为误差函数的最小平方法，可在很少次执行细定位中的圆形工件上实现角的高准确度。

(相应边缘点创建处理)

图44示出了在图41的图案模型上进一步执行相应点搜索线的创建处理的示例。如图所示，将一个参考点分配给每个圆弧段和线段的中心，并且以固定间隔从那些点的每个设置参考点，除了段末端边缘附近之外。此外，在各参考点处垂直于段的方向上从内向外设置相应点搜索线。图45示出了通过使用该图案模型对待搜索图像执行粗搜索的状态，并且已将图案模型PM叠加到了确定的检测候选的位置和姿态上。

在这种状态中，沿着每条相应点搜索线执行边缘提取，来搜索针对每个段的相应边缘点。由于相应边缘点是每条相应点搜索线与待搜索图像的边缘点(细线)的交点，例如图45，所以由×表示的点是相应边缘点。在图45的示例中，由于安排在作为粗搜索的结果获得的检测候选的位置的图案模型的圆弧部分与输入边缘点几乎匹配，所以圆弧段的相应边缘点与圆弧段几乎匹配。因此，即使当相对旋转圆形工件时，圆弧的误差函数也不增加，并且因此该自由度不阻止旋转。因此可期望旋转移动作成为解。

另一方面，线段的许多相应边缘点不在线段上。在线段上执行的最小平方法中，由于将点与线之间的距离看作误差函数，所以估计逆时针旋转将整体减小误差函数的值。从中发现，充分期待获得作为通过最小平方法获得的解的逆时针旋转。

(在存在多个相应边缘点候选的情况下的加权处理)

此外，当存在与参考点相应的多个相应边缘点候选时，可对每个相应边缘点执行加权，以改进模糊确定相应边缘点的情况下细定位中的准确度。基于图49A至图49D描述该情况。通过使用作为图案模型的作为具有图49A中粗线表示的两条纵线的矩形的图案模型PM考虑执行细定位的示例。在这种情况下，假设由图49B中的细线表示段SG1和SG2并在粗搜索中获得。在图49B中，仅考虑位于工件右和左的两段SG1、SG2。在垂直于(边缘方向)通过如上所述参考点KT1、KT2的各个段SG1、SG2的方向上设置这些段的相应点搜索线TTL1、TTL2。当在由虚线表示的针对各段SG1、SG2的各参考点KT1、KT2设置相应点搜索线TTL1、TTL2时，可获得位于各相应点搜索线TTL1、TTL2的相应边缘点候选。当仅针对右边段SG1获得一个相应边缘点候选TTA时，针对左边段SG2获得两个相应边缘点候选TTB、TTC。由于从相应边缘点候选中选择与参考点最近的相应边缘点并确定为相应边缘点，所以TTA和TTB每个都变为相应边缘点。在图49B的示例中，由于关于左边段SG2存在多个相应边缘点候选，所以可认为其包括模糊。在这种情况下，问题是在哪个方向移动该段(即图案模型)。特别地，在图49B的情况下，当整个段(即图案模型)由于选择TTB向右移动作为相应边缘点时，其在期望的细定位相反方向上的移动，这不是优选的。

因此，在执行最小平方法的计算时，加权每个相应边缘点。在图49B的示例中，由于针对右边段SG1在参考点KT1的相应点搜索线TTL1上仅存在一个相应边缘点TTA，所以产生“1.0”的权值。另一方面，考虑左边段SG2，在参考点KT2的相应点搜索线TTL2上相应边缘点候选TTB、TTC位于夹在参考点KT2的右边和左边。因此，根据从参考点KT2到每个相应边缘点候选的距离设置对于参考点KT2的相应边缘点TTB的权值。作为确定权重的表达式的示例，如图49D所示，当第一相应边缘点候选与参考点之间的距离为d1并且第二相应边缘点候选与参考点之间的距离为d2(d1≤d2)时，

权值W＝1-α(d1/d2)

其中0＜α＜1。

在上述表达式中，在相应边缘点候选的数量为1的情况下W＝1，并且在相应边缘点候选的数量大于1的情况下W更小。如上所述，在相应边缘点候选数量为1的情况下(即在不模糊的情况下)通过增加权值，可实现以更可能的方向的移动。此外，在相应边缘点候选的数量为多于1的情况下，在将最近的相应边缘点候选作为相应边缘点的同时，相应边缘点与相应边缘点候选之间的位置关系为上述表达式：当把理想点夹在中间时，W＝1-α(较短距离/较长距离)，当没有把理想点夹在中间时“W＝1”。在这种加权运算和加权之后，通过包括在图1所示的作为加权计算装置的计算装置6中的细定位装置76确定段移动方向。

(分值计算)

此外，在通过使用最小平方法执行细定位计算时，也可计算表示相似度的分值。即，将最小平方法应用到相应点搜索线，并且在最终的最小平方法处理中通过相应点的数量与参考点的数量之间的比例计算该分值。在简化方法中，考虑用相应点的数量减去参考点的数量获得的值作为相似度，并且可通过下述表达式求出：

[表达式19]

$>S=\frac{\underset{i=1}{\overset{n}{\Sigma }}1}{\underset{i=1}{\overset{m}{\Sigma }}1}=\frac{n}{m}$>

S：分值

n：相应点的数量

m：参考点的数量

此外，也可将参考点的理想边缘角与相应边缘点的边缘角之间的相似度反映到分值中。在这种情况下，计算每个从最终最小平方法处理中的相应边缘点的边缘角与其相应的参考点的边缘角之间的差异和参考点的数量获得的总的权值的比例作为分值。具体地说，可通过如下表达式计算：

[表达式20]

$>S=\frac{\underset{i=1}{\overset{n}{\Sigma }}\omega \left(\right|{\theta }_i-{\theta }_i^p\left|\right)}{\underset{i=1}{\overset{m}{\Sigma }}1}$>

S：分值

n：相应点的数量

m：参考点的数量

ω(x)：当x＝0时为1的函数，并且随x的增长单调递减

θ_i：相应点的边缘角

θ_i^p：与相应点对应的参考点的角(参考点的理想角)

当段为线时参考点的理想边缘角是垂直于线的方向，并且叠加到相应点搜索线上。在这种方法中，设置以使每个相应边缘点的边缘角与对应于相应边缘点的参考点的理想边缘角之间的差异越小，权值越接近1，且反之，角差异越大，权值越接近0。例如，在角差异为0到18度的情况下将权值设置为0，在角差异为18到36度的情况下将权值设为0.1，并且在角差异为162到180度的情况下将权值设为1。在这种方式中，针对每个参考点计算权值并且对最终获得的权值求平均来计算分值。

在图49B的示例中，为右边的相应边缘点A设置权值为1，并且为左边的相应边缘点B设置权值为0.9。这导致将向左边移动图案模型的动作施加到右边段SG1，并且将向右边移动图案模型的动作施加到左边段SG2。因此，将这些放在一起，向左边移动的权值为1并且向右边移动的权值为0.9，并且因此，图案模型向左边移动，以实现如图49C所示的状态。类似地，再次从图49C执行加权，并且基于加权的结果重复移动处理，以确定最终的细定位。如上所述，根据相应边缘点候选与参考点之间的距离通过加权估计定位图案模型移动的方向，并执行定位。因此可在相对可能的方向移动图案模型，以改进定位的可靠性和稳定性。

(在考虑定位方向中选择段的方法)

尤其当许多线段集中在特定方向时可发生如上所述这种情况。在图49B的示例中，段仅存在于纵向方向(Y轴方向)，并且因此可在X轴方向上实现准确定位。另一方面，由于不存在在横向上(X轴方向)延伸线段，因此不能定义Y轴方向，从而使得在该方向上定位模糊。因此，在选择组成图案模型的段时，为了防止定位方向被集中的特定方向，有意识地选择正交关系的段(如X轴方向和Y轴方向)，以使可获得稳定的定位结果。在下文中，基于图50的流程图描述考虑定位方向来选择段的方法。

首先，在步骤S4901中，在已经获得多个段候选的状态中，按长度分类段候选。应该注意，在圆弧段的情况下，将圆弧的长度看作段长度。

接着，在步骤S4902中，选择最长的段候选作为段，并且还将其设置为参考点段。将垂直于该参考段的方向看作参考角。应该注意，当选择圆弧段时，参考角出现无效的状态。当参考角无效时，不通过角的方式而是仅通过每个段候选的长度的方式选择共轭段。

此外，在步骤S4903中，提取针对参考段作为共轭段的段候选。从参考角搜索是否存在包括在预定角范围之内(这种情况下为第一角范围)的段候选。图51A示出了第一角范围的示例。提取包括在垂直于设置在中心的参考段(90度)的方向的±45度的范围之内(即45度到135度的范围，总共90度的范围)的段候选。

在图51B所示的段候选的示例中，提取其上标有“○”的段候选，消除其上标有“×”的段候选。当选择线段作为共轭段时，参考角变为垂直于那段的方向，并且获得有效状态。当段不是线而是圆弧段时，无条件地提取。这是因为，在圆弧段的情况下，期望角的改变较大并且可因此成为有用信息。此外，在圆弧段的情况下，参考角的状态保持不变。

当提取段候选时，处理转到步骤S4901-1，选择提取的段候选中的最长段候选作为段，并且将其设置为针对参考段的共轭段。此外，在步骤S4905中，确定已选择的段的数量是否达到了预定数量。当达到预定数量时，处理完成。当没有达到预定数量时，处理转到步骤S4906，并且再次设置一个新的参考段作为共轭段。此后，处理返回到步骤S4903，重复处理。应该注意，在选择圆弧段作为共轭段并且将圆弧段看作是参考段的情况下，如上述当参考角为无效状态时不根据角而仅根据长度做出共轭段的选择，并且由于前述表明当参考角为无效的状态时通过执行相同的处理来提取共轭段。

同时，当在步骤S4903中不存在包括在第一角范围内段候选时，处理转到步骤S4904，并且以如上相同的方式从搜索是否存在包括在从第一角范围扩展的第二角范围之内的段候选。在图51A的示例中，把从第一角范围以±5度扩展的40到140度的范围设置为第二角范围的示例。当找到段候选时，处理跳到步骤S4904-1，并且以如上相同的方式，选择最长段并且将其设置为共轭段。

当即使在第二角范围之内也没找到段候选时，在步骤S4904-3中，进一步以如上相同的方式搜索是否存在包括在从第二角范围进一步扩展的第三角范围之内的段候选。在图51A的示例中，把从第二角范围进一步以±5度扩展的35度到145度的范围设置为第三角范围的示例。当找到段候选时，处理以如上相同的方式跳到步骤S4904-1，并且选择最长的段并且将其设置为共轭段。当没有找到段候选时，处理转到步骤S4902，并且重新从段候选中选择最长段作为参考段。应该注意，可根据需要改变角范围的数值、重新设置角范围的次数等。例如，当在步骤S4904-3中没有找到段时，可执行在进一步扩展的角范围中搜索。相反，可不执行步骤S4904-3，并且当在步骤S4904-2中没有找到段时，可立即将处理返回到步骤S4902来复位参考段。

如上所述，由于重复选择近似垂直于参考段的方向的共轭段的操作并且因此选择具有分散角的段，可改进定位的稳定性。通过段创建装置68中的段选择装置67以这种方式选择段。

(图案特征选择功能)

此外，也可提供可根据从待搜索对象获得的图案特征来改变用于组成图案模型的段的选择标准的图案特征选择功能。具体地说，在-图67中所示的已登记图像中尤其有效。在图67中的已登记图像中，在网格框架中显示不同字符和数字。当在这种图像上设置图案窗口PW时，如图67所示，在框架部分中设置许多段SGW而在创建的图案模型中的框架内的字符中设置很少的字符形式段SGM。在这种图案模型中，仅在框架部分中执行定位，导致忽视框架内部的字符或者认为其不重要，以使很难识别字符，并且因此由于框架单元中的定位位移等定位可能失败。

这是由段的选择标准造成的。即，从通常消除噪声分量和连接重要性到更清楚地检测到的边缘点会导致定位准确度的改进的观点优选地选择长段。这是因为考虑到短的轮廓具有大量的噪声分量，并且基于较长线段有利地提取更多准确边缘信息的假设，设置以使从长线段中自动地选择段。换句话说，迄今为止还不存在一种图像处理方法等可优选地选择短线段。因此，在图67的示例中，由于在由直线包围的框架部分中边缘检测趋于相对容易并清楚，所以变得更易于选择在框架部分中创建的段，导致如上所述的定位的失败。特别地，在粗搜索中，由于其是一种简单搜索并且因此，不是使用所有的提取的边缘、链条段等的轮廓信息，而仅选择部分轮廓，当优选地选择的轮廓对准确定位没有贡献时，发生这种错误选择的问题。

与此相反，在本实施例中，设置可从较短轮廓以长度递增的顺序选择轮廓的功能，以根据已登记图像获得适当的搜索结果。此外，通过设置门限并且消除不大于预定长度的线段来实现噪声分量的消除。因此，当有效地消除噪声分量时，可获得高可靠性的搜索结果。

(以轮廓长度分类)

接着，描述两种用于选择短轮廓的方法。首先，基于图68的用户界面显示屏描述一种用于以长度分类轮廓并从短的轮廓中选择预定数量的轮廓的方法。图68是表示图案特征选择功能的图像处理程序选择显示屏200的用户界面的图像显示，用于适当地选择组成已登记图像的图案模型的轮廓。在该显示屏中，用于可分别设置用于粗搜索和细定位的设置，分别把边缘强度下限82、轮廓长度下限83、选择轮廓的数量84和轮廓登记的顺序85看作为设置项。其中，关于图案特征选择函数的项为轮廓长度下限83、选择的轮廓数量84和轮廓登记的顺序85。

通过边缘强度上限81和边缘强度下线82定义作为边缘的检测范围，并且指定消除高于上限值或低于下限值的边缘强度的这种过滤条件。

(轮廓长度下限设置装置)

轮廓长度下限83用作一种轮廓长度下限设置装置，用于设置作为轮廓的检测下限。即，通过长度滤波器过滤短于由轮廓长度下限83定义的下限值的轮廓。这可消除作为短轮廓出现的噪声。此外，使用用户可调的该值，可根据使用环境和过滤的应用适当地调整过滤的强度。此外，轮廓长度下限可以是一个取决于环境的固定值。

(选择数量确定装置)

选择的轮廓数量84用作选择数量确定装置，用于定义选择轮廓的数量。定义轮廓数量的上限用作图案模型可将图案模型简化以缩减处理量，从而寻求搜索时间的缩减。此外，随着选择数量的增加，处理量增加，但是另一方面，可获得高准确度的搜索结果。应该注意，将选择的轮廓数量设置为固定值(如50)可寻求如上所述设置操作的简化。

(选择顺序确定装置)

轮廓登记的顺序85用作选择顺序确定装置，可在轮廓长度递增与递减之间切换选择轮廓的顺序。从而根据作为图像处理对象的图像，设置适当的长度递增或递减顺序的选择方法，以使可以更灵活地和更准确地执行图像处理。

通过设置上述设置项，从多个轮廓中过滤掉接近噪声的这种相当短的轮廓，并且使轮廓可从较短的中顺序地选择，以有效地消除噪声分量并且也适当地选择对定位准确度有影响的段，以使可构成有效的图案模型。

例如考虑的是通过在如图69中所示的网格框架中显示的不同字符和数字的已登记图像上设置图案窗口PW来选择组成图案模型的段的示例。在设置如图70所示的情况下，由于轮廓登记的顺序85设置为“长度递减的顺序”，即，设置以使从较长的到较短的连续地选择轮廓。从而，如图69所示，不需要选择框架部分中的许多段SGW并且在对识别重要的字符和数字的部分中选择很少的段SGM如果该状态保持不变，则不能获得准确定位。

与此相反，如图71所示，将以轮廓登记的顺序85的设置改变为“长度递增的顺序”，即改变设置以从较短的到较长的连续地选择轮廓，其中如图72所示选择框架内的许多字符和数字的段SGM，以使可构成包括适合于已登记图像的轮廓信息的图案模型。

应该注意，分别在图68的示例中的粗搜索和细定位中尽管每个设置项是单独可设的，也可使其在其中之一可设，或者可形成通过图像处理程序或图像处理设备侧定义特定项并且用户的调整是受限的这种组成。减少设置项的数量以允许不特别熟悉操作的用户以简单的方式使用设备可改进可操作性。

此外，对于轮廓，除了段之外的如链条等的轮廓信息也是可用的。例如，在使用通过链条创建装置63获得的链条作为轮廓信息而不将链条近似为线段或圆弧段的情况下，可对链条的选择标准应用如上所述的从短链条中选择链条的技术、使选择顺序可在递增顺序和递减顺序之间切换的技术或者用于消除短于或长于预定门限的链条的技术，并且这也可允许获得类似的动作效应。接着，基于图73和图74的流程图描述用于以轮廓长度的顺序分类轮廓的特定步骤。

首先，基于图73描述通过使用段长度执行分类的情况。首先提取轮廓。首先，在步骤S7301中，对已登记图像执行索贝尔滤波，以得到边缘角图像和边缘强度图像。接着在步骤S7302中，通过使用边缘角图像和边缘强度图像减薄边缘点，以得到轮廓点。具体地说，在通过轮廓提取装置62的边缘角/边缘强度图像创建装置60创建边缘角图像和边缘强度图像之后，通过边缘强度非最大点抑制处理的方式由减薄装置61减薄边缘点。此外，在步骤S7303中，通过链条创建装置63创建链条。具体地说，边缘连锁装置64连接相邻边缘点以创建链条。此外，根据需要通过具有各种特征量的链条过滤装置66执行过滤。

接着，在步骤S7304中，创建段。段创建装置68中的边缘链条分段装置65创建通过以线和/或圆弧近似每个链条获得的段。此外，在步骤S7305中，过滤短段。作为轮廓长度下限设置装置，段选择装置67消除具有不长于下限值的长度的段，以消除噪声分量。

最后，在步骤S7306中，以段长度分类段，以从具有较短长度的段连续地选择组成图案模型的段。段选择装置67用作轮廓分类装置，用于以长度递减的顺序分类轮廓，按长度的顺序分类段，并且进一步以由选择顺序确定装置定义的选择顺序在通过选择数确定装置定义的数量中以段长递增的顺序即连续地从较短的中选择段。因此，构成上述如图72的适用于已登记图像的图案模型。

另一方面，基于图74的流程图描述使用不通过作为轮廓的段的链条的示例。从轮廓点的提取到链条的创建的过程与上述图73中的一样。即，在步骤S7401中，对已登记图像进行索贝尔滤波，以找出边缘角图像和边缘强度图像。接着在步骤S7402中，通过使用边缘角图像和边缘强度图像减薄边缘点，以求出轮廓点。此外，在步骤S7403中，创建链条。

接着，在步骤S7404中，过滤短链条。根据由轮廓长度下限设置装置设置的下限值，链条创建装置63中的链条过滤装置66消除短于轮廓长度下限83的链条。接着，在步骤S7405中，以链条长度的顺序分类链条，以从具有较短长度的链条中连续地选择组成图案模型的链条。同样在这种情况下，链条过滤装置66用作轮廓分类装置，以长度的顺序分类链条，并且进一步以由选择顺序确定装置定义的选择顺序在由选择数确定装置定义的数量中以链条长度递增的顺序选择链条。因此，构成如图72所示的适合于已登记图像的图案模型。

使用这种方法，不需要使段近似的处理，并且由此可因此简化处理。另一方面，由于链条是连接任意不近似为固定几何图形(如线或圆弧)的线段的主体，随后的每个处理变得复杂。根据已登记图像是否为简单的图形、边缘点的检测准确度等来确定选择的方法。

(过滤长的轮廓)

应该注意，尽管在上述示例中以轮廓长度的顺序执行分类，可通过消除长轮廓而不执行分类来构成图案模型。在下文中，基于图75的用户界面显示屏来描述该方法。图75也是表示用于在图像处理程序中为已登记图像设置图案特征选择功能的图像处理程序设置显示屏300的用户界面的图像示图。在该显示屏中，除了边缘强度上限81、边缘强度下限82和轮廓长度下限83之外还给出轮廓长度上限86。边缘强度上限81、边缘强度下限82和轮廓长度下限83类似于上述图68所示，且不重复提供其详细描述。

(轮廓长度上限设置装置)

轮廓长度上限86用作轮廓长度上限设置装置，用于设置轮廓的上限值。即，轮廓长度上限86过滤长于由轮廓长度上限86定义的上限值的轮廓。因此可通过有意消除长轮廓而仅保留短轮廓来构成图案模型，从而因此获得与优选地选择短轮廓的情况类似的效果。

应该注意，在图75的示例中，没有提供选择数确定装置，并且自动地选择预设定义值的数量的轮廓。但是，也可提供选择数确定装置，以允许用户手动地设置轮廓数量。

如上所述，在不以长度的顺序分类轮廓的情况下，可构成优选地选择短轮廓的图案模型，并且也可实现对图67中已登记图像有效的图案搜索。例如，在如图76所示的这种设置条件下，图案模型包括许多在如图77所示的框架部分选择的段SGW。但是通过如图78所示将轮廓长度上限86从100改为20，可构成一种如图79所示的包括许多在框架内的字符或数字的段SGM的图案模型。

基于图80和图81的流程图描述用于过滤长轮廓的过程。首先，图80描述使用段作为轮廓的情况。同样使用这种方法，如上述以轮廓长度分类轮廓的情况，提取轮廓点创建链条。即，在步骤S8001中，对已登记图像进行索贝尔滤波，以求出边缘角图像和边缘强度图像。接着在步骤S8002中，通过使用边缘角图像和边缘强度图像减薄边缘点，以得到轮廓点。最后，在步骤S8003中，创建链条，并且接着在步骤S8004中，创建段。

最后，在步骤S8005中，删除长段和短段。除了段选择装置67消除具有不大于作为轮廓长度下限设置装置的下限值的长度的段之外，段选择装置67还用作轮廓长度上限设置装置，以消除具有大于轮廓长度上限86的长度的段。因此，由于可在噪声分量消除之后选择短段，可构成包括对图79所示的这种情况的定位有效的段的图案模型。尽管待选择的段的数量是一个固定的值，如上所述，可单独提供选择数确定装置以允许用户手动设置。

此外，基于图81描述通过链条代替段构成图案模型的示例。同样在这种情况下，从轮廓点的提取到链条的创建的过程类似于上述图74所示。即，在步骤S8101中，对已登记图像执行索贝尔滤波，以得到边缘角图像和边缘强度图像。在步骤S8102中，通过使用边缘角图像和边缘强度图像减薄边缘点以得到轮廓点。在步骤S8103中，创建链条。

接着，在步骤S8104中，删除长链条和短链条。链条过滤装置66消除具有不大于作为轮廓长度下限设置装置的轮廓长度下限值的长度的链条并且还用作轮廓长度上限设置装置，以删除长于轮廓长度上限86的链条。因此，由于可在消除噪声分量之后选择短链条，可构成包括如图79的这种情况对已登记图像的定位有效的链条的图案模型。尽管选择的链条数为一个固定的值，如上所述，可单独地提供选择数确定装置以允许用户手动设置。

(在考虑段方向的情况下的段选择功能的组合)

在考虑定位方向或角的情况下可与上述段选择功能同时使用图案特征选择功能。即，作为一种用于在以长度分类段或者在过滤长段之后确定选择哪段来组成图案模型的技术，可采用选择接近垂直于参考段的方向的共轭段的方法，如图50的流程图所示的方法等。应该注意，可将该方法用于段的选择，但是不能用于链条的选择。这是因为链条不是以线和/或圆弧近似的，并且因此不具有如段具有的角或方向。

以下基于图82和图83的流程图描述在分类或过滤之后的选择段时考虑垂直于段的方向的示例。首先，图82示出了以段长度分类段的示例。同样在这种情况下，从轮廓点的提取以创建链条和段到从获得的段中过滤短的以分类段的过程类似于上述图73的过程。即，首先在步骤S8201中，对已登记图像进行索贝尔滤波，以求出边缘角图像和边缘强度图像。接着，在步骤S8202中，通过使用边缘角图像和边缘强度图像来减薄边缘点，以得到轮廓点。此外，在步骤S8203中，创建链条，并且接着在步骤S8204中，创建段。接着在步骤S8205中，过滤短的段，并且接着在步骤S8206中，以段长度分类过滤后的段并以长度递增的顺序排列。

在这种状态中，在步骤S8207中，在考虑垂直于每个段的方向的同时从较短的中连续地选择段。在图84的流程图中示出了在图82的步骤S8206之后的特定过程。该流程图几乎类似于图50的流程图，但是其不同在于：在步骤S8401中，设置分类顺序为从较短的中按段长递增的顺序而不是按段长递减的顺序；在步骤S8402中选择最短段作为段候选并将其看作参考段；以及在步骤S8404-1中选择最短段作为段候选并且将其看作共轭段。除了以上所述之外均类似于图50，且因此不重复提供其详细描述。

该方法在其中短段有效并且可替换选择基本垂直的段的已登记图像上执行尤其有效，以构成其中以法线角为正交的这种关系有意选择段的图案模型，从而可在纵向和横向获得稳定的定位结果。

类似地，基于图83的流程图描述在用于过滤具有大长度段的方法中考虑垂直于段的方向的示例。同样在这种情况下，从轮廓点的提取到创建链条和段到过滤短的和长的都类似于上述图80等的过程。即，首先在步骤S8301中，对已登记图像进行索贝尔过滤，以找到边缘角图像和边缘强度图像。接着在步骤S8302中，通过使用边缘角图像和边缘强度图像减薄边缘点，以得到轮廓点。此外在步骤S8303中，创建链条，并且接着在步骤S8304中创建段。接着在步骤S8305中，过滤短段和长段。由于在这种情况下随时需要步骤S8306中的以段长分类段的操作，所以从该观点可将上述图82的方法看作更有效的。其他效果类似于图82中的，并且作为选择接近垂直方向的共轭段的结果，选择具有分散角的段作为图案模型，从而允许定位稳定性的改进。

(对最小平方法的稳定性的改进)

接着描述的是一种用于改进在细定位步骤中执行的最小平方法的稳定性的技术。将最小平方法简单归类为线性方法和非线性方法。在这些方法中的线性最小平方法中，理论上可统一获得解。另一方面，在非线性最小平方法中，通常近似为二次方程，并且因此近似的值不是必须准确的。在一些情况下，在细定位步骤中，可在一个方向上将待检测的位置移动或旋转以降低与粗搜索中获得的位置相比的准确度。例如，在对高对称性的图形(如图85所示的圆形(外圆的中心坐标稍微不同于内圆的中心坐标))执行细定位的情况下，由于即使当围绕其作为旋转轴的中心旋转每个圆时也很难改变误差值，所以可以与其基本旋转圆相反的方向旋转圆，或者因此，可发生角的大的改变以及平行移动量的大的位移。

在通常由二次方程近似的非线性最小二次平方法的求解方法中，采取通过对误差函数E(pi)近似直到试验参数的组“pi”的相邻试验参数的平方次数(quadratic power number)为最小平方法的变量来创建近似误差函数的这种过程，并且通过使用近似误差函数，求出这种试验参数组“pi”以使误差函数最小。

作为一种用于如上所述非线性最小平方法中以小误差值获得解的求解方法，提出如下反向海赛函数(reverse-Hessian)的方法。

这是一种在近似误差函数的计算和从误差函数计算最小试验参数组之后，同时得到具有更高准确度的下一级的试验参数组的方法。但是，在通过使用该反向海赛函数方法找到具有小误差值的解的情况下，可发生如下这种缺陷。基于图86A和图86B进行描述。在图86A和图86B的每一个中，实线表示误差函数，并且虚线表示由近似该误差函数获得的近似的误差函数。在图86A和图86B的每一个中，在表示误差函数的曲线上提供的符号P1表示在上述粗搜索中获得的位置(x，y，θ)。基于在该P1附近的误差函数值作为二次函数获得的是表示由虚线表示的近似误差的二次曲线。

此外，在如图86A所示的情况下，图示描述反向海赛函数方法适当作用的情况，表示这样一种情况，其中由于具有表示近似误差函数的虚线的二次曲线的最小误差值的位置(即P2)与具有由实线表示的误差函数的最小误差值的位置P接近，因此得到具有小误差值的更准确位置P2。

另一方面，在如图86B所示的情况下，图示描述反向海赛函数方法不适当地作用的情况，表示这样一种情况，其中由于具有表示近似误差函数的虚线的二次曲线的最小误差值的位置(即P2)与具有由实线表示的误差函数的最小误差值的位置P远离，因此得到具有小误差值的不准确位置P2。

在上述情况之外，在图86B所示的情况下，当想以反向海赛函数的方法得到解时，可采用试验参数的大的位移作为如上所述的解，作为结果产生细定位的准确度恶化的问题。本发明人发现一种技术，用于提供关于图案模型的移动或旋转的限制，作为抑制反向海赛函数方法以不恰当方式作用的情况下(如图86B所示)发生的技术。即，作为基于反向海赛函数的求解最小平方法的方法，为误差函数增加了一个新的项。具体地说，除上述关于距离(第一误差函数)的项之外，还增加以使由于从试验参数位移而增加误差值的这种项。因此，通过第二误差函数Ed抑制非常大的改变以使可实现如图86A所示的适当的近似。如上所述，可在细定位的步骤中增加适当方向的收敛情况，以避免在非预期方向上的旋转和分散，从而改进定位的可靠性。当最小平方法中的试验性参数为Pi时，第二误差函数为“Pi-P0i”的函数。在下述表达式中示出作为结果获得的误差函数的联立方程的示例：

[表达式21]

E(P₀，P₁，...，P_n)＝E_o(P₀，P₁，...，P₀)+E_d(P₀，P₁，...，P_n)

$>E_d(P_0,P_1,...,P_n)=\underset{i}{\Sigma }{\left(\frac{(P_i-P_{0i})}{{\sigma }_i}\right)}^2$>

在上述表达式中，由表示每个段与其相应边缘点之间的距离的第一误差函数E_o和通过在第一误差函数中将试验性参数的改变量看作第二误差值在该改变并计算第二误差值的累计值时获得的第二误差函数E_d之和来表示总体误差函数E(P)。如上所述，在计算最小平方法中，由于第二误差函数E_d的除了在与理想位置匹配时变为最小值的项之外的相加导致在这种方向上搜索解以使两项都更小，并且抑制试验性参数的非常大的改变，所以可避免在细定位时在错误方向上旋转或扩散的这种情况，以获得稳定处理结果的优点。

工业适应性

优选地，根据本发明的图像数据压缩方法、图像处理中的图案模型定位方法、图像处理设备、图像处理程序以及计算机可读记录介质都可适用于工厂自动化(FA)领域中使用的工件的坐标位置、旋转角等的位置检测，外径、内径、宽度等的位置测量，图像处理中的识别、鉴定、确定、测试等。例如，本发明可用于键合电极的集成电路(IC)上电极等的定位。