CN107851327A - 粗细搜索方法及图像处理装置 - Google Patents

Abstract

本发明包括：第一搜索步骤，利用模板匹配从第一图像中检测对象物；以及第二搜索步骤，在具有与第一图像相比宽为n倍、长为m倍的分辨率的第二图像中，将与第一搜索步骤中的检测到的位置对应的n像素×m像素的区域作为搜索范围，利用模板匹配从第二图像中检测对象物。粗细搜索中，在第二搜索步骤之前，以将可与模板的相同的元素进行对照运算的n×m个像素的数据存储在连续的存储器地址的方式，将第二图像的数据重新配置于工作存储器上，在第二搜索步骤中，使针对n×m个像素的n×m个对照运算在基于SIMD指令的比n×m少的次数的运算处理中执行。

Description

粗细搜索方法及图像处理装置

技术领域

本发明涉及一种利用模板匹配(template matching)从图像中检测对象物的技术。

背景技术

作为从图像中检测对象物的方法之一，有被称作模板匹配的方法。模板匹配的基本处理是预先准备作为检测对象的物体的模型(模板)，通过对输入图像与模板之间的图像特征的一致度进行评价，而检测图像中的物体的位置或姿势。利用模板匹配的物体检测例如实际用在如下各种领域中，即，工厂自动化(Factory Automation，FA)中的检查或拣货(picking)、机器人·视觉(robotvision)、监视相机等。最近，因图像的高分辨率化或检测对象的种类的增加、对动态图像的实时处理的请求等，而要求模板匹配的进一步的高速化。

作为使利用模板匹配的搜索处理高速化的技术，已知被称作粗细搜索的算法。粗细搜索是指重复如下处理而最终确定出原始分辨率的图像中的物体的位置的方法，所述处理是准备分辨率逐步变化的图像群(称作图像金字塔(image pyramid))，基于低分辨率图像中的搜索结果来限定搜索范围，并针对所述搜索范围在高分辨率图像中进行进一步的搜索。通过逐步缩小搜索范围，而能够减少对照运算的次数，因而能够缩短整体的处理时间。

而且，作为使利用计算机的运算处理高速化的技术，有单指令多数据(singleinstruction multiple data，SIMD)。SIMD是利用一个指令执行多个数据运算的并行处理的一种。例如，在具有128位宽度的SIMD寄存器的处理器的情况下，能够利用1个时钟的指令并行地处理针对16位的8个数据的运算或针对8位的16个数据的运算。专利文献1中公开有为了空间滤波运算的高速化而应用SIMD的例子。而且，非专利文献1中公开了如下：因在响应图(response map)的计算中应用SIMD，所以使每隔T像素而并行的多个特征量在存储器上连续地排列而存储(非专利文献1中取代SIMD而以单一指令多数据流扩展(StreamingSimd Extensions，SSE)这样的用语进行了记载)。

利用SIMD的并行处理对于处理的高速化有效。然而，专利文献1或非专利文献1的方法是对各个文献中公开的处理特殊化的方法，无法应用于所述粗细搜索。

现有技术文献

专利文献

专利文献1：日本专利特开2010-134612号公报

非专利文献

非专利文献1：S.Hinterstoisser，et al.，″Gradient Response Maps for Real-Time Detection of Textureless Objects"，IEEE Transaction on Pattem Analysisand Machine Intelligence，vol.34(5)2012.

发明内容

发明所要解决的问题

本发明鉴于所述实际情况而完成，目的在于提供一种用以使利用粗细搜索的模板匹配更高速化的技术。

解决问题的技术手段

为了达成所述目的，本发明中提供一种粗细搜索方法，包括：第一搜索步骤，利用模板匹配从第一图像中检测对象物；以及第二搜索步骤，在具有与所述第一图像相比宽为n倍、长为m倍(n、m为2以上的整数)的分辨率的第二图像中，将与所述第一搜索步骤中检测到对象物的位置对应的n像素×m像素的区域作为搜索范围，利用模板匹配从所述第二图像中检测所述对象物，所述粗细搜索方法的特征在于：还包括重新配置步骤，所述重新配置步骤在所述第二搜索步骤之前，以将所述第二搜索步骤中可与模板的相同元素进行对照运算的n×m个像素的数据存储在连续的存储器地址的方式，将所述第二图像的数据重新配置于所述工作存储器上；所述第二搜索步骤中，针对存储在工作存储器上的连续的存储器地址中的n×m个像素的n×m个对照运算，通过SIMD指令以比n×m少的次数的运算处理来执行。

根据所述构成，因能够在第二搜索步骤之前进行第二图像的数据的重新配置，所以能够使从工作存储器向SIMD寄存器的数据传输在1个时钟内进行，能够提高利用SIMD运算的并行处理的效率。因此，能够使利用粗细搜索的模板匹配更高速化。

所述重新配置步骤中，优选将从所述第二图像中在宽度方向上邻接的两个像素中的一像素在纵向上相连的(m-1)个像素的数据的复制(copy)插入所述两个像素的数据之间。其原因在于，通过以这种规则进行数据的重新配置，数据重复(冗长性)最小，工作存储器的节约成为可能。

所述重新配置步骤中，优选以将所述第二搜索步骤中使用的模板的各元素的数据存储在连续的n×m个存储器地址中的方式，将所述模板的数据重新配置于工作存储器上。由此，关于模板的数据，也能够使从工作存储器向SIMD寄存器的数据传输在1个时钟内进行，从而能够提高利用SIMD运算的并行处理的效率。

而且，本发明的另一方面提供图像处理装置，包括：模板匹配部，执行利用模板匹配从图像中检测对象物的搜索处理；工作存储器，存储所述搜索处理中使用的数据；数据重新配置部，进行存储于所述工作存储器的数据的重新配置；以及结果输出部，输出所述模板匹配部的处理结果，所述图像处理装置的特征在于：所述模板匹配部在执行了利用模板匹配从第一图像中检测对象物的第一搜索处理后，在具有与所述第一图像相比宽为n倍、长为m倍(n、m为2以上的整数)的分辨率的第二图像中，将与所述第一搜索处理中检测到对象物的位置对应的n像素×m像素的区域作为搜索范围，执行利用模板匹配从所述第二图像中检测所述对象物的第二搜索处理，所述数据重新配置部在所述第二搜索处理之前，以将所述第二搜索处理中可与模板的相同元素进行对照运算的n×m个像素的数据存储在连续的存储器地址的方式，将所述第二图像的数据重新配置于所述工作存储器上，所述第二搜索处理中，针对存储在所述工作存储器上的连续的存储器地址中的n×m个像素的n×m个对照运算，通过SIMD指令以比n×m少的次数的运算处理来执行。

根据所述构成，因能够在第二搜索处理之前进行第二图像的数据的重新配置，所以能够使从工作存储器向SIMD寄存器的数据传输在1个时钟内进行，从而能够提高利用SIMD运算的并行处理的效率。因此，能够使利用粗细搜索的模板匹配更高速化。

另外，本发明也能够作为如下而获取，即，具有上述处理的至少一部分的粗细搜索方法，或者，使用所述粗细搜索方法的物体检测方法或物体识别方法，或者，用于使计算机执行所述方法的程序或非暂时性存储程序的计算机可读记录介质。而且，本发明也能够作为使用所述粗细搜索方法检测或识别物体的图像处理装置或物体识别装置而获取。所述构成及处理只要分别不产生技术上的矛盾则能够相互组合而构成本发明。

发明的效果

根据本发明，能够使利用粗细搜索的模板匹配更高速化。

附图说明

图1表示物体识别装置的整体构成的图。

图2表示物体识别装置的硬件构成的图。

图3表示物体识别装置的功能构成的图。

图4表示从相机获取的图像的一例的图。

图5表示模板的数据构造的一例的图。

图6表示模板的低分辨率化处理的一例的图。

图7概念性地表示粗细搜索算法的图。

图8示意性地表示数据的重排(重新配置)与利用SIMD的高速化的原理的图。

图9表示为了进行对照运算而从工作存储器读取到SIMD寄存器的数据列(datacolumn)的图。

图10表示数据重新配置的另一例的图。

图11表示数据重新配置的另一例的图。

图12表示物体识别处理的流程的流程图。

具体实施方式

本发明涉及一种利用模板匹配的粗细搜索从图像中检测对象物的技术，更详细来说，涉及一种通过利用SIMD的并行化处理而实现粗细搜索的高速化的技术。所述技术能够应用于FA用的图像传感器、计算机视觉、机器视觉等中的物体识别等。以下所述的实施方式中，作为本发明的优选应用例之一，对将本发明应用于判别利用带式输送机搬送的物体的位置及姿势的FA用的图像传感器的例子进行说明。

(物体识别装置的整体构成)

参照图1，对本发明的实施方式的物体识别装置的整体构成及应用情景进行说明。

物体识别装置1是设置于生产线等且使用从相机11获取的图像进行输送机3上的物体2的识别的系统。在输送机3上，多个物体2以任意的姿势行进。物体识别装置1从相机11按照规定的时间间隔获取图像，利用图像处理装置10执行识别图像所包含的各物体2的种类·位置·姿势的处理，并输出所述处理的结果。物体识别装置1的输出(识别结果)例如被用于拣货·机器人的控制、加工装置或打印装置的控制、物体2的检查·测量等中。

(硬件构成)

参照图2对物体识别装置1的硬件构成进行说明。物体识别装置1大致上包含相机11及图像处理装置10。

相机11是用于将物体2的数字图像提取到图像处理装置10的摄像元件，例如能够适合用于互补金属氧化物半导体(Complementary Metal-Oxide-Semiconductor，CMOS)相机或电荷耦合元件(Charge-Coupled Device，CCD)相机。输入图像的格式(分辨率、彩色/单色、静止图像/动画、灰度、数据格式等)为任意，根据物体2的种类或感测的目的适当选择即可。在将可见光像以外的特殊图像(X射线图像、热图像等)用于物体识别或检查的情况下，也可使用与所述图像匹配的相机。

图像处理装置10包括中央处理器(Central Processing Unit，CPU)110、用作工作存储器的主存储器112、作为固定存储部的硬盘114、相机接口116、输入接口118、显示控制器120、可编程控制器(Programmable Logic Controller，PLC)接口122、通信接口124、数据读写器126。这些各部经由总线128而彼此能够进行数据通信地连接。

相机接口116是将CPU 110与相机11之间的数据传输中转的部分，具有用于暂时存储来自相机11的图像数据的图像缓冲器116a。输入接口118将CPU 110与输入部(鼠标13、键盘、触摸屏、步进控制器等)之间的数据传输中转。显示控制器120连接于液晶监控器等显示器12，控制所述显示器12中的显示。PLC接口122将CPU 110与PLC 4之间的数据传输中转。通信接口124将CPU 110与控制台(或者个人计算机或服务器装置)等之间的数据传输中转。数据读写器126将CPU 110与作为存储介质的存储卡14之间的数据传输中转。

图像处理装置10能够包含具有通用的体系结构的计算机，CPU(处理器)110通过读取并执行存储在硬盘114或存储卡14中的程序，而提供各种功能。这种程序以存储在存储卡14或光盘等计算机可读记录介质中的状态流通，或者通过因特网等而提供(下载)。另外，本实施方式的程序可作为单个应用程序而提供，也可作为编入到其他程序的一部分的模块而提供。而且，其功能的一部分或全部也可由专用集成电路(Application SpecificIntegrated Circuit，ASIC)等专用电路代替。

(功能构成)

图3表示物体识别装置1的功能构成。图3所示的功能通过图像处理装置10执行程序而实现。物体识别装置1大致上具备作为模板制作装置20的功能部及作为物体识别处理装置30的功能部。模板制作装置20是制作在物体识别处理中所使用的模板的功能部。由模板制作装置20制作的模板被登记在物体识别处理装置30的模板数据库(data base，DB)31中。物体识别处理装置30是通过对从相机11获取到的图像执行利用模板匹配的粗细搜索而识别图像中的物体的功能部。物体识别处理装置30具有模板DB 31、图像获取部32、图像金字塔生成部33、特征抽出部34、数据重新配置部35、模板匹配部36、识别结果输出部37。以后将对这些功能的详细情况进行叙述。

图4表示从相机11获取的图像的一例。如图4所示，图像中包含多个物体2，且，各物体2的位置(XYZ坐标)及姿势(绕XYZ这3轴的角度)为任意。除了是完全的球体的情况之外，如果物体相对于相机11的姿势(朝向)不同，则图像中映出的物体的形态(形状、颜色等)也不同。因此，在使用了二维(two dimension，2D)图像的一般的模板匹配中为了识别任意姿势的三维(three dimension，3D)物体，针对物体的每个姿势而准备个别的模板，并进行这些模板的利用暴力搜索的匹配。

(模板)

模板是表现作为检测对象的物体的图像特征的数据。模板的格式可以是任何格式，本实施方式中，如图5所示，使用记述了图像中的多个特征点的特征量的排列格式的数据。图5右侧的模板的各行表示一个特征点的信息，特征点的信息包含特征点的坐标x、y及特征量的值val。

作为特征量，例如能够使用像素值(亮度)、亮度梯度方向、量化梯度方向、方向梯度直方图(Histogram of Oriented Gradients，HoG)、类哈尔(HAAR-like)、尺度不变特征转换(Scale-Invariant Feature Transform，SIFT)等。亮度梯度方向以连续值表现以特征点为中心的局部区域中的亮度的梯度方向(角度)，量化梯度方向以离散值表现以特征点为中心的局部区域中的亮度的梯度方向(例如，利用0～7的1字节的信息保存8个方向)。关于图5的特征量val，表示以2进数表述量化梯度方向的例子。各个位表示0度、45度、90度、135度、180度、225度、270度、315度的方向。

模板能够通过使用物体的图像进行特征点检测及特征量抽出的处理而制作。关于特征点检测及特征量抽出，能够利用公知的方法，因而此处省略详细说明。作为模板的基础的图像能够通过拍摄实际的物体而获得。或者，在能够获得物体的三维计算机辅助设计(Computer Aided Design，CAD)数据的情况下，通过使用三维计算机图形进行绘制(rendering)处理，而能够获得所期望的姿势(视点、旋转角)及光源下的图像。

详细情况将于以后进行叙述，但本实施方式中，因进行使用了分辨率逐步变化的多个图像(图像金字塔)的粗细搜索，所以需要准备与各个分辨率相应的模板。作为制作分辨率不同的多个模板的方法，有根据分辨率不同的多个物体图像分别制作模板的方法、及通过对根据最高分辨率的物体图像制作的模板实施低分辨率化处理而制作所需分辨率的模板的方法。低分辨率化处理是指如下处理，即，基于各特征点的位置关系将位于附近的多个特征点整合，由此降低模板的分辨率。图6表示将模板的分辨率设为1/2的例子。在将分辨率设为1/2的情况下，将2×2的范围内的附近特征点整合为一个特征点。图6的例子中，将四个特征点(1，1)、(1，2)、(2，1)、(2，2)的特征量的值整合所得的结果为低分辨率模板的特征点(1，1)的特征量的值。而且，将三个特征点(1，3)、(1，4)、(2，4)的特征量的值整合所得的结果为低分辨率模板的特征点(1，2)的特征量的值。另外，这是低分辨率化处理的一例。因模板可视作为像素值具有特征量的值的图像数据，所以能够使用公知的图像分辨率变换处理。

(粗细搜索)

接下来，对粗细搜索法进行说明。粗细搜索是使利用模板匹配的搜索处理高速化的算法，也称作粗精搜索、金字塔搜索、金字塔搜寻、由粗到精的搜索(Coarse to FineSearch)。

图7概念性地表示粗细搜索算法。粗细搜索中，使用分辨率逐步变化的第一层至第k层(k为2以上的整数)的k张图像群(图像金字塔)。第一层图像分辨率最低，按照第二层、…、第k层的顺序而分辨率增高。比起第i层图像(i＝1、2、…、k-1)，第(i+1)层图像具有宽为n倍、长为m倍(n、m为2以上的整数)的分辨率。长与宽的倍率也可不同(即，也可n≠m)。

图7是k＝3、n＝2、m＝2的例子。第三层图像与原图像对应，随着到第二层图像、第一层图像，分辨率一次降低1/2。例如，在第三层图像(原图像)为640像素×480像素的视频图形阵列(Video Graphics Array，VGA)尺寸的图像的情况下，第二层图像为320像素×240像素，第一层图像为160像素×120像素的分辨率。

粗细搜索中，首先，对最低分辨率的第一层图像进行利用模板匹配的搜索处理，检测第一层图像中的物体的存在位置(候补)。在图7的第一层图像中由黑色的四边形所示的像素表示检测位置。接下来，在对第二层图像的搜索处理中，与第一层图像中的检测位置对应的第二层图像内的区域被设定为搜索范围。图7的例子中，因第二层图像为与第一层图像相比宽为2倍、长为2倍的分辨率，所以搜索范围为2像素×2像素的区域。而且，对第二层图像，仅对所述搜索范围进行搜索处理。同样地，基于第二层图像中的检测结果来设定第三层图像中的搜索范围，进行对所述搜索范围的搜索处理，并最终确定出第三层图像(原图像)内的物体位置。

例如，如果将第三层用模板的元素数设为t，则在利用通常的模板匹配在第三层图像内进行详尽搜索的情况下，所需的对照运算的次数为640×480×t＝307200×t。与此相对，在粗细搜索的情况下，因仅对第一层图像进行详尽搜索，所以第一层图像的搜索处理所需的对照运算的次数为160×120×(t/4)，以后因搜索范围受到限定，所以第二层图像的搜索处理中为2×2×(t/2)即可，第三层图像的搜索处理中为2×2×t即可，可以是合计4806×t次的对照运算。即，图7的例子中，可将对照运算的次数减少至约1/64，从而可实现处理速度的大幅提高。

(利用SIMD的高速化)

接下来，对通过使用基于SIMD指令的并行处理而使粗细搜索进一步高速化的算法进行说明。

模板匹配中，在模板的各元素的数据与图像的各像素的数据之间进行对照运算。利用像素的数据所表示的特征量将四则运算或逻辑运算等各种运算用作对照运算。例如，在特征量为亮度的情况下使用减法运算或减法运算的绝对值等的对照运算。而且，在特征量为量化梯度方向的情况下使用异或(exclusive OR)等对照运算。进行对照运算时，如果使用SIMD指令使多个对照运算在一次运算处理中执行，则能够实现搜索处理的高速化。其中，关于基于SIMD指令的并行处理有效，限于如下情况，即，一次SIMD指令中同时运算的多个数据(即，存储于SIMD寄存器的多个数据)排列于工作存储器上连续的存储器地址中。其原因在于，如果是连续的存储器地址中所存储的数据，则能够以1个时钟的指令从工作存储器传输到SIMD寄存器，但在各数据存在于工作存储器上的隔开的地址的情况下，从工作存储器向SIMD寄存器的数据传输则需要数个时钟(即，从工作存储器向SIMD寄存器的数据传输出现瓶颈)，从而担心并行处理的效果被抵消。因此，本实施方式中，因将基于SIMD指令的并行处理的效率最大限度地提高，所以在搜索处理之前进行图像数据的重新配置(重排)。此时，本算法的特征在于：通过着眼于粗细搜索中可参照的数据的范围(搜索范围)的规则性，来进行最适合于粗细搜索的数据的重排。

图8示意性表示数据的重排(重新配置)与利用SIMD的高速化的原理。图8中，为了简化说明，将第一层图像的尺寸设为4像素×3像素，第二层图像的尺寸设为8像素×6像素(即，n＝m＝2)。而且，将第一层用模板的尺寸设为1×1，第二层用模板的尺寸设为2×2。图8中，A0～A11表示第一层图像的各像素的索引，B0～B47表示第二层图像的各像素的索引。而且，P0表示第一层用模板的元素的索引，Q0～Q3表示第二层用模板的各元素的索引。另外，第一层图像及第二层图像的各像素中设定与模板的各元素相同的特征量的数据。

第一层的搜索处理中，使用第一层用模板搜索第一层图像的整体。具体来说，将第一层用模板从第一层图像的左上的像素A0按顺序开始应用，进行P0与A0、P0与A1、…、P0与A11共计12次的对照运算。而且，一旦检测到特征量的类似度超过规定的阈值的像素，则所述像素作为物体的存在位置的候补。图8是像素A5作为存在位置的候补而检测到的例子。

第二层图像中，与第一层图像的像素A5对应的区域是(B18、B19、B26、B27)的2像素×2像素的区域。所述区域设定于第二层的搜索处理中的搜索范围内。第二层的搜索处理中，因对如下情况下的四个位置进行搜索，所以所需的对照运算的组合为以下的16个，所述情况是(1)将第二层用模板的元素Q0应用于第二层图像的像素B18的位置的情况，(2)将元素Q0应用于像素B19的位置的情况，(3)将元素Q0应用于像素B26的位置的情况，(4)在将元素Q0应用于像素B27的位置的情况。

(1)Q0与B18、Q1与B19、Q2与B26、Q3与B27

(2)Q0与B19、Q1与B20、Q2与B27、Q3与B28

(3)Q0与B26、Q1与B27、Q2与B34、Q3与B35

(4)Q0与B27、Q1与B28、Q2与B35、Q3与B36

此处，如果着眼于与模板的相同元素进行对照运算的像素，则与元素Q0进行对照运算的四个像素(B18、B19、B26、B27)、与元素Q1进行对照运算的四个像素(B19、B20、B27、B28)、与元素Q2进行对照运算的四个像素(B26、B27、B34、B35)、与元素Q3进行对照运算的四个像素(B27、B28、B35、B36)均在第二层图像中如2×2的区块那样排列。因此，以在第二层图像中如2×2的区块那样排列的任意四个像素在工作存储器上连续的地址中排列的方式，重新配置第二层图像的数据。图8中，按照向第二层图像的原来的像素(由白底图示的像素)的下一地址插入所述像素的列方向(纵向)上邻接的像素的复制(由阴影图示的像素)这一规则来进行数据的重新配置。另外，最终行中，因不存在列方向上邻接的像素，所以插入虚设的数据即可。

另一方面，也对第二层用模板进行数据的重新配置。具体来说，如图8所示，制作一个数据列，其中模板的各个元素Q0～Q3的4个元素连续地配置。

如果进行所述数据的重新配置作为预处理(事先准备)，则例如元素Q0与四个像素(B18、B19、B26、B27)之间的四个对照运算能够以如下3个时钟执行：

(1)将数据列(B18、B19、B26、B27)从工作存储器向SIMD寄存器#1传输，

(2)将数据列(Q0、Q0、Q0、Q0)从工作存储器向SIMD寄存器#2传输，

(3)基于SIMD指令的一次性运算。

如图9(A)～图9(D)所示，不仅元素Q0的对照运算，关于元素Q1与像素(B19、B20、B27、B28)之间的对照运算、元素Q2与像素(B26、B27、B34、B35)之间的对照运算、元素Q3与像素(B27、B28、B35、B36)之间的对照运算，也能够进行利用SIMD的有效率的并行处理。

数据的重新配置的方法(排列方法)不限定于图8的例子。例如，如图10(A)～图10(D)所示，也可准备可与模板的相同元素进行对照运算的四个像素的全部组合的数据列。所述排列方法与图8的排列方法相比，虽然所需的存储器大小增加，但与图8的排列方法同样地，能够进行利用SIMD的有效率的并行处理。

以上的说明中，第二层的搜索处理的搜索范围为2像素×2像素的区域，可与模板的相同元素进行对照运算的像素数为四个的原因在于，第一层图像与第二层图像的分辨率之比为宽2倍、长2倍(n＝m＝2)。在分辨率之比并非为2倍的情况下，当然也能够进行相同的处理。而且，不仅第一层图像与第二层图像之间，第二层图像与第三层图像之间、…、第i层图像与第(i+1)层图像之间、…、第(k-1)层图像与第k层图像之间也能够进行相同的处理。

如果加以概括，则在考虑具有与第一图像相比宽为n倍、长为m倍(n、m为2以上的整数)的分辨率的第二图像时，与对第一图像的搜索处理中所检测到的位置对应的第二图像中的搜索范围为n像素×m像素的区域。因此，对第二图像的搜索处理中可与模板的相同元素进行对照运算的像素数为n×m个。因此，以所述n×m个像素的数据存储在连续的存储器地址的方式，将第二图像的数据重新配置于工作存储器上。据此，n×m个像素的数据列以1个时钟便能够传输到SIMD寄存器，n×m个对照运算能够在基于SIMD指令的一次运算处理中执行。作为数据的重新配置的方法，宜为将第二图像中行方向(宽度方向)上邻接的两个像素中的一像素在列方向(纵向)上相连的(m-1)个像素的数据的复制插入所述两个像素的数据之间。其原因在于，如果按照这种规则来重新配置，则数据的重复(冗长性)最小，工作存储器的节约成为可能。图11表示n＝2、m＝3的例子。

(物体识别处理)

接下来，按照图12的流程对利用物体识别处理装置30执行的物体识别处理的流程进行说明。

首先，图像获取部32从相机11获取图像(步骤S10)。接下来，图像金字塔生成部33根据步骤S10中获取到的原图像生成低分辨率图像，从而生成图像金字塔(步骤S11)。本实施方式中，如图7所示，使用包含第一层图像(160像素×120像素)、第二层图像(320像素×240像素)、第三层图像(640像素×480像素)这3张图像的图像金字塔。

接下来，特征抽出部34对图像金字塔的各层图像实施特征抽出处理(步骤S12)。此处抽出的特征量是与模板的特征量相同种类的特征量，本实施方式中使用量化梯度方向。作为对第一层图像的特征抽出处理的结果，获得具有与第一层图像相同的分辨率且具有以在第一层图像的各像素位置抽出的特征量的数据(特征值)作为像素值的图像(以后称作第一层特征图像)。同样地，获得作为对第二层图像的特征抽出处理结果的第二层特征图像，获得作为对第三层图像的特征抽出处理结果的第三层特征图像。第一层特征图像～第三层特征图像也构成图像金字塔。

接下来，数据重新配置部35将第二层特征图像与第三层特征图像各自的数据重新配置于工作存储器上(步骤S13)。所述重新配置处理是用以使后段的利用粗细搜索的模板匹配的对照处理高速化的预处理。数据重新配置的具体方法如前所述。

接下来，模板匹配部36使用第一层特征图像与第一层用模板执行第一搜索处理(步骤S14)。另外，在多种物体为检测对象的情况下或针对物体的每个姿势而有模板的情况下，对每个模板重复步骤S14的处理。

然后，模板匹配部36基于第一搜索处理的检测结果来设定第二层特征图像的搜索范围，使用第二层特征图像与第二层用模板执行第二搜索处理(步骤S15)。第二搜索处理中，如所述那样，针对存储在工作存储器上连续的存储器地址中的2×2个像素的四个对照运算，通过SIMD指令在一次运算处理中执行。在多种物体为检测对象的情况下或针对物体的每个姿势有模板的情况下，针对每个模板重复步骤S15的处理。而且，在第一搜索处理中检测到多个物体的存在位置候补的情况下，针对每个检测到的候补重复步骤S15的处理。

然后，模板匹配部36基于第二搜索处理的检测结果来设定第三层特征图像的搜索范围，使用第三层特征图像与第三层用模板执行第三搜索处理(步骤S16)。第三搜索处理中，也如所述那样，针对存储在工作存储器上连续的存储器地址中的2×2个像素的四个对照运算，通过SIMD指令在一次运算处理中执行。在多种物体为检测对象的情况下或针对物体的每个姿势有模板的情况下，针对每个模板重复步骤S16的处理。而且，在第二搜索处理中检测到多个物体的存在位置候补的情况下，针对每个检测到的候补重复步骤S16的处理。

以上的处理的结果为，能够确定出具有与原图像相同分辨率的第三层特征图像中的物体的存在位置。而且，在使用多个模板的情况下，能够识别出与哪个模板最匹配、物体的种类或姿势。这种识别结果被识别结果输出部37输出到外部装置或显示器(步骤S17)。识别结果的信息例如用于拣货·机器人的控制、加工装置或打印装置的控制、物体2的检查·测量等。

(本实施方式的优点)

根据以上所述的构成，通过在搜索处理之前进行工作存储器上的数据的重新配置，而能够以1个时钟进行从工作存储器向SIMD寄存器的数据传输，从而能够提高利用SIMD运算的并行处理的效率。因此，能够使利用粗细搜索的模板匹配更高速化。

(变形例)

所述实施方式的构成只不过表示本发明的一具体例，并非旨在限定本发明的范围。本发明在不脱离其技术思想的范围内能够采用各种具体的构成。

例如，所述实施方式中，是在执行粗细搜索前重新配置图像整体的数据，但也可基于第一搜索处理的检测结果，仅将图像内的必要区域的数据重新配置。由此，预计将减少重新配置数据所需的时间及存储器。而且，所述实施方式中，以一次SIMD运算执行n×m个对照运算，但在n×m个对照运算中使用的数据大于SIMD寄存器的数据范围的情况下等一次SIMD运算中无法执行的情况下，也可以多次(其中为比n×m少的次数)的SIMD运算执行n×m个对照运算。即，只要能够将n×m个对照运算置换成比n×m少的次数的SIMD运算，则能够实现搜索处理的高速化。

符号的说明

1：物体识别装置

2：物体

3：输送机

10：图像处理装置

11：相机

20：模板制作装置

30：物体识别处理装置

31：模板DB

32：图像获取部

33：图像金字塔生成部

34：特征抽出部

35：数据重新配置部

36：模板匹配部

37：识别结果输出部

Claims (5)

1.一种粗细搜索方法，其特征在于，包括：

第一搜索步骤，利用模板匹配从第一图像中检测对象物；以及

第二搜索步骤，在具有与所述第一图像相比宽为n倍、长为m倍(n、m为2以上的整数)的分辨率的第二图像中，将与所述第一搜索步骤中检测到对象物的位置对应的n像素×m像素的区域作为搜索范围，利用模板匹配从所述第二图像中检测所述对象物，所述粗细搜索方法还包括：

重新配置步骤，所述重新配置步骤在所述第二搜索步骤之前，以将所述第二搜索步骤中可与模板的相同元素进行对照运算的n×m个像素的数据存储在连续的存储器地址的方式，将所述第二图像的数据重新配置于工作存储器上；

所述第二搜索步骤中，针对存储在所述工作存储器上的连续的存储器地址中的n×m个像素的n×m个对照运算，通过单指令流多数据流指令以比n×m少的次数的运算处理来执行。

2.根据权利要求1所述的粗细搜索方法，其特征在于：

所述重新配置步骤中，将从所述第二图像中在宽度方向上邻接的两个像素中的一像素在纵向上相连的(m-1)个像素的数据的复制插入所述两个像素的数据之间。

3.根据权利要求1或2所述的粗细搜索方法，其特征在于：

所述重新配置步骤中，以将所述第二搜索步骤中使用的模板的各元素的数据存储在连续的n×m个存储器地址中的方式，将所述模板的数据重新配置于工作存储器上。

4.一种程序，其特征在于：使计算机执行根据权利要求1至3中任一项所述的粗细搜索方法的各步骤。

5.一种图像处理装置，包括：

模板匹配部，执行利用模板匹配从图像中检测对象物的搜索处理；

工作存储器，存储所述搜索处理中使用的数据；

数据重新配置部，进行存储于所述工作存储器的数据的重新配置；以及

结果输出部，输出所述模板匹配部的处理结果，所述图像处理装置的特征在于：

所述模板匹配部在执行了利用模板匹配从第一图像中检测对象物的第一搜索处理后，在具有与所述第一图像相比宽为n倍、长为m倍(n、m为2以上的整数)的分辨率的第二图像中，将与所述第一搜索处理中检测到对象物的位置对应的n像素×m像素的区域作为搜索范围，执行利用模板匹配从所述第二图像中检测所述对象物的第二搜索处理，

所述数据重新配置部在所述第二搜索处理之前，以将所述第二搜索处理中可与模板的相同元素进行对照运算的n×m个像素的数据存储在连续的存储器地址的方式，将所述第二图像的数据重新配置于所述工作存储器上，

所述第二搜索处理中，针对存储在所述工作存储器上的连续的存储器地址中的n×m个像素的n×m个对照运算，通过单指令流多数据流指令以比n×m少的次数的运算处理来执行。