CN104077775A - Shape matching method and device combining skeleton feature points and shape context - Google Patents

Abstract

Translated fromChinese

本发明公开一种结合骨架特征点和形状上下文的形状匹配方法及装置，其方法包括：对两幅图像中的每幅图像进行去除噪声处理，各得到滤波后的平滑图像；采用OTSU方法对平滑图像进行目标分割，获得二值目标图像；对二值目标图像进行骨架提取，获得骨架特征点，并根据骨架特征点获取所有的骨架端点；并对二值目标图像进行边缘检测，提取所有的边缘点；基于形状上下文描述子，根据骨架端点与边缘点建立直方图；根据相似性度量准则和直方图对两幅图像进行形状匹配。与基于形状上下文的形状匹配方法相比，本发明由于采用骨架特征点，在保持较高的匹配性能的基础上，其复杂度大大降低，为后续实现实时、鲁棒、准确的跟踪提供基础。

The invention discloses a shape matching method and device combining skeleton feature points and shape context. The method includes: performing noise removal processing on each of two images to obtain filtered smooth images; using the OTSU method to smooth Carry out target segmentation on the image to obtain a binary target image; perform skeleton extraction on the binary target image to obtain skeleton feature points, and obtain all skeleton endpoints according to the skeleton feature points; and perform edge detection on the binary target image to extract all edges point; based on the shape context descriptor, build a histogram according to the skeleton endpoint and edge point; perform shape matching on two images according to the similarity measurement criterion and histogram. Compared with the shape matching method based on the shape context, the present invention uses skeleton feature points, while maintaining high matching performance, its complexity is greatly reduced, providing a basis for subsequent real-time, robust, and accurate tracking.

Description

Translated fromChinese

一种结合骨架特征点和形状上下文的形状匹配方法及装置A shape matching method and device combining skeleton feature points and shape context

技术领域technical field

本发明涉及一种形状匹配技术领域，特别涉及一种结合骨架特征点和形状上下文的形状匹配方法及装置，可以应用于用于图像处理、计算机视觉、形状匹配和检索、目标跟踪。The invention relates to the technical field of shape matching, in particular to a shape matching method and device combining skeleton feature points and shape context, which can be applied to image processing, computer vision, shape matching and retrieval, and target tracking.

背景技术Background technique

形状对于人类感知是一个重要的视觉线索，为了从图像中抽取目标，形状模型展现了很大的潜力。目前，形状匹配方法主要分为两类：以形状上下文为代表的基于轮廓的形状匹配方法和以奇点图为代表的基于骨架的形状匹配方法。Shape is an important visual cue for human perception, and shape models show great potential for object extraction from images. At present, shape matching methods are mainly divided into two categories: contour-based shape matching methods represented by shape context and skeleton-based shape matching methods represented by singularity graphs.

其中，基于轮廓的形状匹配方法中形状上下文使用一组直方图来表示整个形状，每个轮廓上的采样点都用一个统计直方图来表示。它是一种信息丰富的描述方法，对局部噪声点不敏感，对小的非线性形变以及存在异常点的情况具有良好的鲁棒性。基于骨架的形状匹配方法中骨架是基于形状特征的物体对象的简化描述方式，把骨架应用于形状匹配和检索有独特的效果。如骨架结构与物体的形状表述一致性，骨架结构具有平移、旋转和尺度不变性；组合了物体目标的形状轮廓和区域信息，反映了目标重要的视觉认知特征。利用骨架表征物体目标的形状区域信息减少了冗余信息，简化了结构分析。此外，将图像提炼成反映其本质的简化表示，可以在保持重要拓扑和几何结构特征的情况下消除轮廓的失真影响。因此，骨架特征对关节和非刚性变形非常鲁棒，但是只包含粗略的结构信息；而轮廓特征含有丰富的信息并且很稳定，但是对变形敏感。基于上述描述，亟需提供一种将骨架特征点与轮廓点结合起来进行形状匹配的方案，以获得稳定准确的形状匹配。Among them, in the contour-based shape matching method, the shape context uses a set of histograms to represent the entire shape, and each sampling point on the contour is represented by a statistical histogram. It is an information-rich description method that is insensitive to local noise points and has good robustness to small nonlinear deformations and the presence of outliers. In the skeleton-based shape matching method, the skeleton is a simplified description method of the object based on the shape feature. Applying the skeleton to the shape matching and retrieval has a unique effect. For example, the skeleton structure is consistent with the shape representation of the object, and the skeleton structure has translation, rotation and scale invariance; it combines the shape outline and area information of the object target, reflecting the important visual cognitive characteristics of the target. Using the skeleton to represent the shape area information of the object target reduces redundant information and simplifies structural analysis. Furthermore, distilling an image into a simplified representation that reflects its essence can remove the distorting effects of contours while preserving important topological and geometrical features. Therefore, skeleton features are very robust to joints and non-rigid deformations, but contain only rough structural information; while contour features are informative and stable, but sensitive to deformations. Based on the above description, it is urgent to provide a scheme that combines skeleton feature points and contour points for shape matching to obtain stable and accurate shape matching.

发明内容Contents of the invention

本发明技术解决问题：针对现有技术的不足，提供一种结合骨架特征点和形状上下文的形状匹配方法及装置，实现对平移、旋转、尺度和非刚性变形下准确的形状匹配。The technical solution of the present invention: Aiming at the deficiencies of the prior art, a shape matching method and device combining skeleton feature points and shape context are provided to realize accurate shape matching under translation, rotation, scale and non-rigid deformation.

为实现这样的目的，本发明的技术方案：一种结合骨架特征点和形状上下文的形状匹配方法，包含以下步骤：To achieve such purpose, the technical solution of the present invention: a shape matching method combining skeleton feature points and shape context, comprising the following steps:

对两幅图像中的每幅图像进行去除噪声处理，各得到滤波后的平滑图像；Perform noise removal processing on each of the two images to obtain a smoothed image after filtering;

采用OTSU方法对所述平滑图像进行目标分割，获得二值目标图像；Using the OTSU method to perform target segmentation on the smooth image to obtain a binary target image;

对所述二值目标图像进行骨架提取，获得骨架特征点，并根据所述骨架特征点获取所有的骨架端点；并对所述二值目标图像进行边缘检测，提取所有的边缘点；Carry out skeleton extraction to described binary target image, obtain skeleton feature point, and obtain all skeleton endpoints according to described skeleton feature point; And carry out edge detection to described binary target image, extract all edge points;

基于形状上下文描述子，根据所述骨架端点与所述边缘点建立直方图；Based on the shape context descriptor, a histogram is established according to the skeleton endpoint and the edge point;

根据相似性度量准则和所述直方图对所述两幅图像进行形状匹配。Perform shape matching on the two images according to the similarity measure criterion and the histogram.

可选地，如上所述的方法中，对所述二值目标图像进行骨架提取，获得骨架特征点，具体包括如下步骤：Optionally, in the method as described above, performing skeleton extraction on the binary target image to obtain skeleton feature points specifically includes the following steps:

将所述二值目标图像中已知的目标点标记为1，背景点标记为0，定义边界点是本身标记为1，而所述边界点的8连通区域中至少有一个点标记为0，以所述边界点为中心的8连通邻域，记中心点为p₁，其邻域的8个点顺时针绕中心点分别记为p₂,p₃,...,p₉,其中所述p₂在所述p₁上方；The known target point in the binary target image is marked as 1, the background point is marked as 0, the boundary point is defined as 1, and at least one point in the 8-connected region of the boundary point is marked as 0, For the 8-connected neighborhood centered on the boundary point, record the center point as p₁ , and the 8 points in the neighborhood clockwise around the center point are respectively recorded as p₂ , p₃ ,...,p₉ , where said p₂ is above said p₁ ;

对所述边界点进行如下(A)和(B)两步操作：Carry out following (A) and (B) two-step operation to described boundary point:

(A)标记同时满足下列条件的边界点：(A) Mark the boundary points that meet the following conditions at the same time:

(a1)2δN(p₁)δ6；(a1)2δN(p₁ )δ6;

(a2)S(p₁)＝1；(a2)S(p₁ )=1;

(a3)$p_2\∀p_4\∀p_6=0;$(a3)$p_2\∀p_4\∀p_6=0;$

(a4)$p_4\∀p_6\∀p_8=0;$(a4)$p_4\∀p_6\∀p_8=0;$

其中N(p₁)是p₁的非零邻点个数，S(p₁)是以p₂,p₃,...,p₉为序时这些点的值从01的个数。当对全部所述边界点检验完毕后，将所有标记了的点除去；Where N(p₁ ) is the number of non-zero neighbors of p₁ , and S(p₁ ) is the number of values of these points from 01 when p₂ , p₃ ,...,p₉ are sequenced. After all the boundary points are checked, all marked points are removed;

(B)标记同时满足下列条件的边界点：(B) Mark the boundary points that meet the following conditions at the same time:

(b1)1δN(p₁)δ6；(b1)1δN(p₁ )δ6;

(b2)S(p₁)＝1；(b2)S(p₁ )=1;

(b3)$p_2\∀p_4\∀p_8=0;$(b3)$p_2\∀p_4\∀p_8=0;$

(b4)$p_2\∀p_6\∀p_8=0;$(b4)$p_2\∀p_6\∀p_8=0;$

以上两步操作(A)和(B)构成一次迭代，反复迭代直至没有点再满足标记条件，所述二值目标图像中剩下的点组成所述骨架特征点。The above two-step operations (A) and (B) constitute one iteration, and the iterations are repeated until no point satisfies the marking condition, and the remaining points in the binary target image form the skeleton feature points.

可选地，如上所述的方法中，根据所述骨架特征点获取所有的骨架端点，具体包括：对每个所述骨架特征点进行八邻域判断，当八邻域中仅有一个所述骨架特征点时，将所述骨架特征点记录为所述骨架端点；对所有的所述骨架特征点进行八邻域判断，获取所有的所述骨架端点。Optionally, in the above-mentioned method, obtaining all skeleton endpoints according to the skeleton feature points specifically includes: performing eight-neighborhood judgment on each of the skeleton feature points, when there is only one of the eight-neighborhoods For skeleton feature points, record the skeleton feature points as the skeleton endpoints; perform eight-neighborhood judgment on all the skeleton feature points to obtain all the skeleton endpoints.

可选地，如上所述的方法中，基于形状上下文描述子，根据所述骨架端点与所述边缘点建立直方图，具体包括如下步骤：Optionally, in the above method, based on the shape context descriptor, the histogram is established according to the skeleton endpoint and the edge point, which specifically includes the following steps:

基于形状上下文描述子，在每一幅图像中，对于每一个所述骨架端点，计算所述骨架端点和每一个所述边缘点的梯度角；Based on the shape context descriptor, in each image, for each of the skeleton endpoints, calculating the gradient angle between the skeleton endpoint and each of the edge points;

对于每一个所述骨架端点，计算所述骨架端点与每一个所述边缘点的相对矢量关系，并根据所述骨架端点和每一个所述边缘点的所述梯度角计算所述骨架端点与每一个所述边缘点的所述相对梯度角关系；For each of the skeleton endpoints, calculate the relative vector relationship between the skeleton endpoint and each of the edge points, and calculate the skeleton endpoint and each edge point according to the gradient angle of the skeleton endpoint and each edge point said relative gradient angle relationship of one of said edge points;

利用所述相对矢量关系以及所述相对梯度角关系在对数极坐标系中建立所述骨架端点对应的所述直方图。The histogram corresponding to the end points of the skeleton is established in a logarithmic polar coordinate system by using the relative vector relationship and the relative gradient angle relationship.

可选地，如上所述的方法中，根据相似性度量准则和所述直方图描述子对所述两幅图像进行形状匹配，具体包括：Optionally, in the method described above, performing shape matching on the two images according to the similarity measure criterion and the histogram descriptor, specifically includes:

根据所述两幅图像中每一个所述骨架端点的所述直方图，利用所述相似性度量准则计算所述两幅图像中的两个所述骨架端点的相似性度量值；calculating, based on the histogram of each of the skeleton endpoints in the two images, the similarity measure values of the two skeleton endpoints in the two images using the similarity measure criterion;

对于所述两幅图像的其中一幅图像中的每一个所述骨架端点，获取另一幅图像中与当前的所述骨架端点的所述相似性度量值最大的所述骨架端点作为匹配点；For each of the skeleton endpoints in one of the two images, obtain the skeleton endpoint in the other image that has the largest similarity metric value with the current skeleton endpoint as a matching point;

利用每一个所述骨架端点及对应的所述匹配点对所述两幅图像进行形状匹配。performing shape matching on the two images by using each of the skeleton endpoints and the corresponding matching points.

可选地，如上所述的方法中，根据所述两幅图像中每一个所述骨架端点的所述直方图，利用所述相似性度量准则计算所述两幅图像中的两个所述骨架端点的相似性度量值，具体采用如下方式实现：Optionally, in the above method, according to the histogram of each of the skeleton endpoints in the two images, the two skeletons in the two images are calculated using the similarity measurement criterion The similarity measure of the endpoint is implemented in the following way:

所述两幅图像中的两个所述骨架端点的相似性度量值计算如下：The similarity measure of the two skeleton endpoints in the two images is calculated as follows:

$\mathrm{<span><span>C</span>C</span>}<span><span>(</span>(</span>{\mathrm{<span><span>p</span>p</span>}}_{\mathrm{<span><span>i</span>i</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>q</span>q</span>}}_{\mathrm{<span><span>j</span>j</span>}}<span><span>)</span>)</span><span><span>=</span>=</span>\frac{\mathrm{<span><span>1</span>1</span>}}{\mathrm{<span><span>2</span>2</span>}}\underset{\mathrm{<span><span>k</span>k</span>}<span><span>=</span>=</span>\mathrm{<span><span>1</span>1</span>}}{\overset{\mathrm{<span><span>K</span>K</span>}}{\mathrm{<span><span>\&Sigma;</span>\&Sigma;</span>}}}\frac{{<span><span>[</span>[</span>{\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>i</span>i</span>}}<span><span>(</span>(</span>\mathrm{<span><span>k</span>k</span>}<span><span>)</span>)</span><span><span>-</span>-</span>{\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>j</span>j</span>}}<span><span>(</span>(</span>\mathrm{<span><span>k</span>k</span>}<span><span>)</span>)</span><span><span>]</span>]</span>}^{\mathrm{<span><span>2</span>2</span>}}}{{\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>i</span>i</span>}}<span><span>(</span>(</span>\mathrm{<span><span>k</span>k</span>}<span><span>)</span>)</span><span><span>+</span>+</span>{\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>j</span>j</span>}}<span><span>(</span>(</span>\mathrm{<span><span>k</span>k</span>}<span><span>)</span>)</span>}$

其中p_i,q_j分别为所述两幅图像中第一幅图像中的第i个骨架端点和所述两幅图像中第二副图像中的第j个骨架端点，h_i(k)为所述第一幅图像上所述第i个骨架端点建立的直方图上第k个bin值，h_j(k)为所述第二幅图像上所述第j个骨架端点建立的直方图上所述第k个bin值，K表示直方图的总bins数目；C(p_i,q_j)表示p_i,q_j两个所述骨架端点的相似性度量值。Where p_i , q_j are respectively the i-th skeleton endpoint in the first image in the two images and the j-th skeleton endpoint in the second image in the two images, h_i (k) is The kth bin value on the histogram established by the i-th skeleton endpoint on the first image, h_j (k) is on the histogram established by the j-th skeleton endpoint on the second image For the kth bin value, K represents the total number of bins in the histogram; C(_pi , q_j ) represents the similarity measure value of the two skeleton endpoints of p_i and q_j .

本发明还提供一种结合骨架特征点和形状上下文的形状匹配装置，包括：The present invention also provides a shape matching device combining skeleton feature points and shape context, including:

去噪处理模块，用于对两幅图像中的每幅图像进行去除噪声处理，各得到滤波后的平滑图像；The denoising processing module is used to perform denoising processing on each image in the two images, each obtaining a filtered smooth image;

目标分割模块，用于采用OTSU方法对所述平滑图像进行目标分割，获得二值目标图像；Target segmentation module, for adopting OTSU method to carry out target segmentation to described smooth image, obtain binary target image;

提取模块，用于对所述二值目标图像进行骨架提取，获得骨架特征点，并根据所述骨架特征点获取骨架端点；并对所述二值目标图像进行边缘检测，提取边缘点；The extraction module is used to perform skeleton extraction on the binary target image, obtain skeleton feature points, and obtain skeleton endpoints according to the skeleton feature points; and perform edge detection on the binary target image to extract edge points;

直方图建立模块，用于基于形状上下文描述子，根据所述骨架端点与所述边缘点建立直方图；A histogram building module, configured to create a histogram according to the skeleton endpoint and the edge point based on the shape context descriptor;

形状匹配模块，用于根据相似性度量准则和所述直方图对所述两幅图像进行形状匹配。A shape matching module, configured to perform shape matching on the two images according to the similarity measure criterion and the histogram.

可选地，如上所述的装置中，所述提取模块，具体用于将所述二值目标图像中已知的目标点标记为1，背景点标记为0，定义边界点是本身标记为1，而所述边界点的8连通区域中至少有一个点标记为0，以所述边界点为中心的8连通邻域，记中心点为p₁，其邻域的8个点顺时针绕中心点分别记为p₂,p₃,...,p₉,其中所述p₂在所述p₁上方；Optionally, in the above-mentioned device, the extraction module is specifically configured to mark the known target point in the binary target image as 1, mark the background point as 0, and mark the defined boundary point itself as 1 , and at least one point in the 8-connected area of the boundary point is marked as 0, and the 8-connected neighborhood centered on the boundary point is marked as p₁ , and the 8 points of its neighborhood go around the center clockwise The points are respectively denoted as p₂ , p₃ ,...,p₉ , wherein the p₂ is above the p₁ ;

对所述边界点进行如下(A)和(B)两步操作：Carry out following (A) and (B) two-step operation to described boundary point:

(A)标记同时满足下列条件的边界点：(A) Mark the boundary points that meet the following conditions at the same time:

(a1)2δN(p₁)δ6；(a1)2δN(p₁ )δ6;

(a2)S(p₁)＝1；(a2)S(p₁ )=1;

(a3)$p_2\&ForAll;p_4\&ForAll;p_6=0;$(a3)$p_2\&ForAll;p_4\&ForAll;p_6=0;$

(a4)$p_4\&ForAll;p_6\&ForAll;p_8=0;$(a4)$p_4\&ForAll;p_6\&ForAll;p_8=0;$

其中N(p₁)是p₁的非零邻点个数，S(p₁)是以p₂,p₃,...,p₉为序时这些点的值从01的个数。当对全部所述边界点检验完毕后，将所有标记了的点除去；Where N(p₁ ) is the number of non-zero neighbors of p₁ , and S(p₁ ) is the number of values of these points from 01 when p₂ , p₃ ,...,p₉ are sequenced. After all the boundary points are checked, all marked points are removed;

(B)标记同时满足下列条件的边界点：(B) Mark the boundary points that meet the following conditions at the same time:

(b1)1δN(p₁)δ6；(b1)1δN(p₁ )δ6;

(b2)S(p₁)＝1；(b2)S(p₁ )=1;

(b3)$p_2\&ForAll;p_4\&ForAll;p_8=0;$(b3)$p_2\&ForAll;p_4\&ForAll;p_8=0;$

(b4)$p_2\&ForAll;p_6\&ForAll;p_8=0;$(b4)$p_2\&ForAll;p_6\&ForAll;p_8=0;$

以上两步操作(A)和(B)构成一次迭代，反复迭代直至没有点再满足标记条件，所述二值目标图像中剩下的点组成所述骨架特征点。The above two-step operations (A) and (B) constitute one iteration, and the iterations are repeated until no point satisfies the marking condition, and the remaining points in the binary target image form the skeleton feature points.

可选地，如上所述的装置中，所述提取模块，具体用于对每个所述骨架特征点进行八邻域判断，当八邻域中仅有一个所述骨架特征点时，将所述骨架特征点记录为所述骨架端点；对所有的所述骨架特征点进行八邻域判断，获取所有的所述骨架端点。Optionally, in the above-mentioned device, the extraction module is specifically configured to perform eight-neighborhood judgment on each of the skeleton feature points, and when there is only one skeleton feature point in the eight-neighborhood, the The skeleton feature points are recorded as the skeleton endpoints; the eight-neighborhood judgment is performed on all the skeleton feature points to obtain all the skeleton endpoints.

可选地，如上所述的装置中，所述直方图建立模块，具体用于基于形状上下文描述子，在每一幅图像中，对于每一个所述骨架端点，计算所述骨架端点和每一个所述边缘点的梯度角；对于每一个所述骨架端点，计算所述骨架端点与每一个所述边缘点的相对矢量关系，并根据所述骨架端点和每一个所述边缘点的所述梯度角计算所述骨架端点与每一个所述边缘点的所述相对梯度角关系；利用所述相对矢量关系以及所述相对梯度角关系在对数极坐标系中建立所述骨架端点对应的所述直方图。Optionally, in the above-mentioned device, the histogram building module is specifically configured to calculate the skeleton endpoint and each skeleton endpoint in each image based on the shape context descriptor. The gradient angle of the edge point; for each of the skeleton endpoints, calculate the relative vector relationship between the skeleton endpoint and each of the edge points, and according to the gradient of the skeleton endpoint and each of the edge points Calculate the relative gradient angle relationship between the skeleton endpoint and each of the edge points; use the relative vector relationship and the relative gradient angle relationship to establish the corresponding skeleton endpoint in the logarithmic polar coordinate system histogram.

可选地，如上所述的装置中，所述形状匹配模块，具体用于根据所述两幅图像中每一个所述骨架端点的所述直方图，利用所述相似性度量准则计算所述两幅图像中的两个所述骨架端点的相似性度量值；对于所述两幅图像的其中一幅图像中的每一个所述骨架端点，获取另一幅图像中与当前的所述骨架端点的所述相似性度量值最大的所述骨架端点作为匹配点；利用每一个所述骨架端点及对应的所述匹配点对所述两幅图像进行形状匹配。Optionally, in the above-mentioned device, the shape matching module is specifically configured to calculate the two images according to the histogram of each of the skeleton endpoints in the two images by using the similarity measure criterion. The similarity measure value of the two skeleton endpoints in the two images; for each of the skeleton endpoints in one of the two images, obtain the relationship between the other image and the current skeleton endpoint The skeleton endpoint with the largest similarity metric value is used as a matching point; each of the skeleton endpoints and the corresponding matching point are used to perform shape matching on the two images.

可选地，如上所述的装置中，所述形状匹配模块，具体用于采用如下方式计算所述两幅图像中的两个所述骨架端点的相似性度量值：Optionally, in the above-mentioned device, the shape matching module is specifically configured to calculate the similarity metric values of the two skeleton endpoints in the two images in the following manner:

$\mathrm{<span><span>C</span>C</span>}<span><span>(</span>(</span>{\mathrm{<span><span>p</span>p</span>}}_{\mathrm{<span><span>i</span>i</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>q</span>q</span>}}_{\mathrm{<span><span>j</span>j</span>}}<span><span>)</span>)</span><span><span>=</span>=</span>\frac{\mathrm{<span><span>1</span>1</span>}}{\mathrm{<span><span>2</span>2</span>}}\underset{\mathrm{<span><span>k</span>k</span>}<span><span>=</span>=</span>\mathrm{<span><span>1</span>1</span>}}{\overset{\mathrm{<span><span>K</span>K</span>}}{\mathrm{<span><span>\&Sigma;</span>\&Sigma;</span>}}}\frac{{<span><span>[</span>[</span>{\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>i</span>i</span>}}<span><span>(</span>(</span>\mathrm{<span><span>k</span>k</span>}<span><span>)</span>)</span><span><span>-</span>-</span>{\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>j</span>j</span>}}<span><span>(</span>(</span>\mathrm{<span><span>k</span>k</span>}<span><span>)</span>)</span><span><span>]</span>]</span>}^{\mathrm{<span><span>2</span>2</span>}}}{{\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>i</span>i</span>}}<span><span>(</span>(</span>\mathrm{<span><span>k</span>k</span>}<span><span>)</span>)</span><span><span>+</span>+</span>{\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>j</span>j</span>}}<span><span>(</span>(</span>\mathrm{<span><span>k</span>k</span>}<span><span>)</span>)</span>}$

其中p_i,q_j分别为所述两幅图像中第一幅图像中的第i个骨架端点和所述两幅图像中第二副图像中的第j个骨架端点，h_i(k)为所述第一幅图像上所述第i个骨架端点建立的直方图上第k个bin值，h_j(k)为所述第二幅图像上所述第j个骨架端点建立的直方图上所述第k个bin值，K表示直方图的总bins数目；C(p_i,q_j)表示p_i,q_j两个所述骨架端点的相似性度量值。Where p_i , q_j are respectively the i-th skeleton endpoint in the first image in the two images and the j-th skeleton endpoint in the second image in the two images, h_i (k) is The kth bin value on the histogram established by the i-th skeleton endpoint on the first image, h_j (k) is on the histogram established by the j-th skeleton endpoint on the second image For the kth bin value, K represents the total number of bins in the histogram; C(pi_, q_j ) represents the similarity measure value of the two skeleton endpoints of p_i and q_j .

本发明与现有技术相比的有益效果在于：The beneficial effect of the present invention compared with prior art is:

(1)本发明对分割后的目标进行骨架提取，获得骨架端点。利用骨架端点与边缘点的关系建立直方图，而不是利用所有的骨架点，这样大大降低了计算复杂度；(1) The present invention performs skeleton extraction on the segmented object to obtain skeleton endpoints. Use the relationship between the skeleton endpoint and the edge point to build a histogram instead of using all the skeleton points, which greatly reduces the computational complexity;

(2)本发明结合骨架特征点和形状上下文，提出一种新的骨架描述子，对平移、旋转、尺度变化和非刚性变形具有不变性；(2) The present invention combines skeleton feature points and shape context to propose a new skeleton descriptor, which is invariant to translation, rotation, scale change and non-rigid deformation;

(3)本发明结合骨架特征点和形状上下文，与基于形状上下文描述子的匹配方法相比，本发明得到的描述子复杂度更低，大大降低了运算时间，同时具有较好的匹配性能；(3) The present invention combines skeleton feature points and shape context, compared with the matching method based on the shape context descriptor, the descriptor complexity obtained by the present invention is lower, greatly reduces the operation time, and has better matching performance;

(4)本发明结合骨架特征点和形状上下文，不仅用于形状匹配和检索，还可用于目标跟踪，尤其是异性扩展目标的跟踪中。(4) The present invention combines skeleton feature points and shape context, not only for shape matching and retrieval, but also for object tracking, especially in the tracking of heterogeneous extended objects.

附图说明Description of drawings

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作一简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。In order to more clearly illustrate the technical solutions in the embodiments of the present invention or the prior art, the following will briefly introduce the drawings that need to be used in the description of the embodiments or the prior art. Obviously, the accompanying drawings in the following description These are some embodiments of the present invention. For those skilled in the art, other drawings can also be obtained according to these drawings without any creative effort.

图1为本发明实施例提供的结合骨架特征点和形状上下文的形状匹配方法的流程图；FIG. 1 is a flow chart of a shape matching method combining skeleton feature points and shape context provided by an embodiment of the present invention;

图2为本发明实施例提供的对形状测试数据库MPEG-7中的carriage-01.gif与carriage-06.gif的匹配结果；Fig. 2 is the matching result of carriage-01.gif and carriage-06.gif in the shape test database MPEG-7 provided by the embodiment of the present invention;

图3为本发明实施例提供的对形状测试数据库中的camel-2.gif与camel-9.gif的匹配结果；Fig. 3 is the matching result of camel-2.gif and camel-9.gif in the shape test database provided by the embodiment of the present invention;

图4为本发明实施例提供的对形状测试数据库中的brick-15.gif与brick-16.gif的匹配结果；Fig. 4 is the matching result of brick-15.gif and brick-16.gif in the shape test database provided by the embodiment of the present invention;

图5为本发明实施例提供的对形状测试数据库中的butterfly-14.gif与butterfly-15.gif的匹配结果；Fig. 5 is the matching result of butterfly-14.gif and butterfly-15.gif in the shape test database provided by the embodiment of the present invention;

图6为本发明实施例提供的对形状测试数据库中的chicken-4.gif与chicken-5.gif的匹配结果；Fig. 6 is the matching result of chicken-4.gif and chicken-5.gif in the shape test database provided by the embodiment of the present invention;

图7为本发明实施例提供的对形状测试数据库中的bird-5.gif与bird-6.gif的匹配结果；Fig. 7 is the matching result of bird-5.gif and bird-6.gif in the shape test database provided by the embodiment of the present invention;

图8为本发明实施例提供的对实际采集的飞机序列中第1帧与第86帧进行匹配的结果。Fig. 8 is a result of matching the first frame and the 86th frame in the actually collected aircraft sequence provided by the embodiment of the present invention.

图9为本发明实施例提供的结合骨架特征点和形状上下文的形状匹配装置的结构示意图。Fig. 9 is a schematic structural diagram of a shape matching device combining skeleton feature points and shape context provided by an embodiment of the present invention.

具体实施方式Detailed ways

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。In order to make the purpose, technical solutions and advantages of the embodiments of the present invention clearer, the technical solutions in the embodiments of the present invention will be clearly and completely described below in conjunction with the drawings in the embodiments of the present invention. Obviously, the described embodiments It is a part of embodiments of the present invention, but not all embodiments. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without creative efforts fall within the protection scope of the present invention.

自形状上下文描述子被提出以来，已经广泛应用于形状匹配和检索中。形状上下文使用一组直方图来表示整个形状，每个轮廓上的采样点都用一个统计直方图来表示。它是一种信息丰富的描述方法，对局部噪声点不敏感，对小的非线性形变以及存在异常点的情况具有良好的鲁棒性。另一方面，骨架能够反映物体的几何结构和拓扑结构，是形状的一种简化，可以处理非刚性变形，但是只包含粗略的结构信息；而轮廓可以很好的表达形状细节信息，在一定程度上对遮挡鲁棒，但是对关节变化和非刚性变形敏感。受此启发，本发明将骨架特征点和形状上下文描述相结合，提出一种骨架描述子，实现平移、旋转、尺度变化以及非刚性变形的准确匹配。Since the shape context descriptor was proposed, it has been widely used in shape matching and retrieval. The shape context uses a set of histograms to represent the entire shape, and each sampling point on the contour is represented by a statistical histogram. It is an information-rich description method that is insensitive to local noise points and has good robustness to small nonlinear deformations and the presence of outliers. On the other hand, the skeleton can reflect the geometric structure and topological structure of the object, which is a simplification of the shape and can handle non-rigid deformation, but only contains rough structural information; while the outline can express the detailed information of the shape very well, to a certain extent Robust to occlusion, but sensitive to joint changes and non-rigid deformations. Inspired by this, the present invention combines skeleton feature points and shape context descriptions, and proposes a skeleton descriptor to achieve accurate matching of translation, rotation, scale change, and non-rigid deformation.

本发明基于形状建模的实现，输入图像为标准形状数据库MPEG-7中的图像。The invention is based on the realization of shape modeling, and the input image is the image in the standard shape database MPEG-7.

图1为本发明实施例提供的结合骨架特征点和形状上下文的形状匹配方法的流程图。本实施例的结合骨架特征点和形状上下文的形状匹配方法的执行主体为一种结合骨架特征点和形状上下文的形状匹配装置，该装置可以采用软件集成。本实施例的结合骨架特征点和形状上下文的形状匹配方法具体可以包括如下步骤：Fig. 1 is a flowchart of a shape matching method combining skeleton feature points and shape context provided by an embodiment of the present invention. The subject of the shape matching method combining skeleton feature points and shape context in this embodiment is a shape matching device combining skeleton feature points and shape context, which can be integrated by software. The shape matching method combining skeleton feature points and shape context in this embodiment may specifically include the following steps:

100、对两幅图像中的每幅图像进行去除噪声处理，各得到滤波后的平滑图像；100. Perform noise removal processing on each of the two images to obtain smoothed images after filtering;

该步骤在对图像进行预处理。由于光照或成像系统的缺陷，获取的待处理图像会受到噪声的影响，从而影响后续的处理。因此，在执行后续的处理算法之前，对待处理图像进行预处理。本实施例的方法中可以采用高斯平滑滤波来去除噪声的影响，得到滤波后的平滑图像。另外，也可以采用中值、均值或双边等滤波方法来对当前帧图像进行去除噪声处理，在此不再限制。This step is preprocessing the image. Due to defects in lighting or imaging systems, acquired images to be processed will be affected by noise, thereby affecting subsequent processing. Therefore, before executing subsequent processing algorithms, the image to be processed is preprocessed. In the method of this embodiment, Gaussian smoothing filtering may be used to remove the influence of noise, and a filtered smooth image may be obtained. In addition, filtering methods such as median, mean, or bilateral can also be used to remove noise from the current frame image, which is not limited here.

101、采用OTSU方法对平滑图像进行目标分割，获得二值目标图像；101. Using the OTSU method to perform target segmentation on a smooth image to obtain a binary target image;

其中OTSU即为最大类间差法，是由日本学者大津(OTSU)于1979年提出的，是一种自适应的阈值确定方法，又叫大津法，简称OTSU。该步骤用于实现目标分割。析原图像序列发现，图像的对比度较差、灰度层次单一、信息量少。一般情况下，扩展目标在空间结构上具有刚性目标的先验紧致特性，轮廓复杂且面积较大，但内部可能有小块的均匀区域，直接采用简单的人为阈值分割方法会出现中空现象。当背景比较单一时，采用OTSU方法可以将目标与背景准确的分割出来。Among them, OTSU is the maximum inter-class difference method, which was proposed by Japanese scholar Otsu (OTSU) in 1979. It is an adaptive threshold determination method, also called Otsu method, OTSU for short. This step is used to achieve object segmentation. The analysis of the original image sequence found that the contrast of the image is poor, the gray level is single, and the amount of information is small. In general, the extended target has the prior compactness of the rigid target in terms of spatial structure. The outline is complex and the area is large, but there may be a small uniform area inside, and the simple artificial threshold segmentation method will appear hollow. When the background is relatively simple, the OTSU method can be used to accurately segment the target and the background.

102、对二值目标图像进行骨架提取，获得骨架特征点，并根据骨架特征点获取所有的骨架端点；并对二值目标图像进行边缘检测，提取所有的边缘点；102. Perform skeleton extraction on the binary target image to obtain skeleton feature points, and obtain all skeleton endpoints according to the skeleton feature points; and perform edge detection on the binary target image to extract all edge points;

该步骤用于实现骨架提取和边缘检测。骨架具有与原物体相同的拓扑和形状信息，能够有效的描述物体，是一种性能优良的几何特征。实现骨架提取的方法有多种思路，中轴变换(medial axis transform，MAT)是一种比较有效的技术。然而该方法需要计算所有边界点到所有区域内部点的距离，计算量非常大。因此，本实施例采用逐次消去边界点的迭代细化算法来提取骨架。This step is used to achieve skeleton extraction and edge detection. The skeleton has the same topology and shape information as the original object, which can effectively describe the object and is a geometric feature with excellent performance. There are many ways to realize skeleton extraction, and medial axis transform (MAT) is a more effective technique. However, this method needs to calculate the distances from all boundary points to all points inside the region, and the amount of calculation is very large. Therefore, this embodiment adopts an iterative thinning algorithm that eliminates boundary points one by one to extract the skeleton.

进一步可选地，本实施例中，骨架端点定义为在该骨架点的八邻域中，只有一个骨架点。根据此定义，对每个骨架点进行八邻域判断，将八邻域中只有一个骨架点的点记录为骨架端点，从而获得所有的所述骨架端点。其中“根据骨架特征点获取所有的骨架端点”，例如具体可以包括：对每个骨架特征点进行八邻域判断，当八邻域中仅有一个骨架特征点时，将该骨架特征点记录为骨架端点；对所有的骨架特征点进行八邻域判断，获取所有的骨架端点。Further optionally, in this embodiment, the skeleton endpoint is defined as having only one skeleton point in eight neighborhoods of the skeleton point. According to this definition, an eight-neighborhood judgment is performed on each skeleton point, and a point with only one skeleton point in the eight-neighborhood is recorded as a skeleton end point, thereby obtaining all the skeleton end points. Wherein "obtaining all skeleton endpoints according to the skeleton feature point", for example, may specifically include: performing eight-neighborhood judgment on each skeleton feature point, and when there is only one skeleton feature point in the eight-neighborhood, record the skeleton feature point as Skeleton endpoints: Perform eight-neighborhood judgments on all skeleton feature points to obtain all skeleton endpoints.

此外，为了获得单像素边缘点，本实施例中的对二值目标图像进行边缘检测，提取所有的边缘点，例如具体可以采用Canny算子对二值目标图像进行边缘检测提取边缘，获得所有的边缘点。In addition, in order to obtain single-pixel edge points, edge detection is performed on the binary target image in this embodiment, and all edge points are extracted. For example, the Canny operator can be used to perform edge detection and edge extraction on the binary target image to obtain all edge point.

103、基于形状上下文描述子，根据骨架端点与边缘点建立直方图；103. Based on the shape context descriptor, establish a histogram according to the skeleton endpoints and edge points;

该步骤结合形状上下文描述子，利用步骤102得到的骨架端点与边缘点之间的相对矢量关系建立直方图。由于形状上下文包含丰富的信息，对小的旋转和局部变形比较鲁棒，因此，借鉴其思想，利用骨架端点与边缘点建立直方图，This step combines the shape context descriptor and uses the relative vector relationship between the skeleton end point and the edge point obtained in step 102 to establish a histogram. Since the shape context contains rich information, it is more robust to small rotations and local deformations. Therefore, drawing on its ideas, using the skeleton endpoints and edge points to establish a histogram,

104、根据相似性度量准则和直方图对两幅图像进行形状匹配。104. Perform shape matching on the two images according to the similarity measurement criterion and the histogram.

例如根据每一个骨架端点对应的直方图，可以利用相似性度量准则计算两幅图像中的两个骨架端点的相似性度量值。也就是说，对于其中一幅图像中的每一个骨架端点，可以计算出该骨架端点与另一幅图像中的每一个骨架端点的相似性度量值，然后可以从中获取相似性度量值最大时对应的骨架端点，作为当前骨架端点在另一幅图像中的匹配点。按照类似的方法，多于前一幅图像中的每一个骨架端点，都可以在另一幅图像中找到对应的匹配点，然后根据多对这样的骨架端点以及对应的匹配点对两幅图像进行形状匹配即可。For example, according to the histogram corresponding to each skeleton endpoint, the similarity measurement criterion of the two skeleton endpoints in the two images can be calculated by using the similarity measurement criterion. That is to say, for each skeleton endpoint in one of the images, the similarity measure between the skeleton endpoint and each skeleton endpoint in the other image can be calculated, and then the corresponding The endpoint of the skeleton is used as the matching point of the current skeleton endpoint in another image. According to a similar method, more than each skeleton endpoint in the previous image can find the corresponding matching point in another image, and then compare the two images according to many pairs of such skeleton endpoints and corresponding matching points. The shapes match.

本实施例的结合骨架特征点和形状上下文的形状匹配方法，对分割后的目标进行骨架提取，获得骨架端点。利用骨架端点与边缘点的关系建立直方图，而不是利用所有的骨架点，这样大大降低了计算复杂度；本实施例的结合骨架特征点和形状上下文，提出一种新的骨架描述子，对平移、旋转、尺度变化和非刚性变形具有不变性；本实施例的技术方案，与基于形状上下文描述子的匹配方法相比，得到的描述子复杂度更低，大大降低了运算时间，同时具有较好的匹配性能；本实施例的技术方案，不仅用于形状匹配和检索，还可用于目标跟踪，尤其是异性扩展目标的跟踪中。In the shape matching method of this embodiment combining skeleton feature points and shape context, skeleton extraction is performed on the segmented object to obtain skeleton endpoints. Use the relationship between the skeleton endpoint and the edge point to build a histogram instead of using all the skeleton points, which greatly reduces the computational complexity; this embodiment combines the skeleton feature points and the shape context to propose a new skeleton descriptor. Translation, rotation, scale change and non-rigid deformation are invariant; compared with the matching method based on the shape context descriptor, the technical solution of this embodiment has lower complexity of the obtained descriptor, greatly reduces the operation time, and has Better matching performance; the technical solution of this embodiment is not only used for shape matching and retrieval, but also can be used for target tracking, especially the tracking of heterosexual extended targets.

可选地，在上述实施例的技术方案的基础上，步骤102中的“对二值目标图像进行骨架提取，获得骨架特征点”，具体采用如下方式提取骨架特征点：Optionally, on the basis of the technical solutions of the above-mentioned embodiments, in step 102, "extracting the skeleton from the binary target image to obtain the skeleton feature points" specifically adopts the following method to extract the skeleton feature points:

将所述二值目标图像中已知的目标点标记为1，背景点标记为0，定义边界点是本身标记为1，而所述边界点的8连通区域中至少有一个点标记为0，以所述边界点为中心的8连通邻域，记中心点为p₁，其邻域的8个点顺时针绕中心点分别记为p₂,p₃,...,p₉,其中所述p₂在所述p₁上方；The known target point in the binary target image is marked as 1, the background point is marked as 0, the boundary point is defined as 1, and at least one point in the 8-connected region of the boundary point is marked as 0, For the 8-connected neighborhood centered on the boundary point, record the center point as p₁ , and the 8 points in the neighborhood clockwise around the center point are respectively recorded as p₂ , p₃ ,...,p₉ , where said p₂ is above said p₁ ;

对所述边界点进行如下(A)和(B)两步操作：Carry out following (A) and (B) two-step operation to described boundary point:

(A)标记同时满足下列条件的边界点：(A) Mark the boundary points that meet the following conditions at the same time:

(a1)2δN(p₁)δ6；(a1)2δN(p₁ )δ6;

(a2)S(p₁)＝1；(a2)S(p₁ )=1;

(a3)$p_2\&ForAll;p_4\&ForAll;p_6=0;$(a3)$p_2\&ForAll;p_4\&ForAll;p_6=0;$

(a4)$p_4\&ForAll;p_6\&ForAll;p_8=0;$(a4)$p_4\&ForAll;p_6\&ForAll;p_8=0;$

其中N(p₁)是p₁的非零邻点个数，S(p₁)是以p₂,p₃,...,p₉为序时这些点的值从01的个数。当对全部所述边界点检验完毕后，将所有标记了的点除去；Where N(p₁ ) is the number of non-zero neighbors of p₁ , and S(p₁ ) is the number of values of these points from 01 when p₂ , p₃ ,...,p₉ are sequenced. After all the boundary points are checked, all marked points are removed;

(B)标记同时满足下列条件的边界点：(B) Mark the boundary points that meet the following conditions at the same time:

(b1)1δN(p₁)δ6；(b1)1δN(p₁ )δ6;

(b2)S(p₁)＝1；(b2)S(p₁ )=1;

(b3)$p_2\&ForAll;p_4\&ForAll;p_8=0;$(b3)$p_2\&ForAll;p_4\&ForAll;p_8=0;$

(b4)$p_2\&ForAll;p_6\&ForAll;p_8=0;$(b4)$p_2\&ForAll;p_6\&ForAll;p_8=0;$

以上两步操作(A)和(B)构成一次迭代，反复迭代直至没有点再满足标记条件，所述二值目标图像中剩下的点组成所述骨架特征点。The above two-step operations (A) and (B) constitute one iteration, and the iterations are repeated until no point satisfies the marking condition, and the remaining points in the binary target image form the skeleton feature points.

进一步可选地，在上述实施例的技术方案的基础上，其中步骤103“基于形状上下文描述子，根据骨架端点与边缘点建立直方图”，具体可以包括如下步骤：Further optionally, on the basis of the technical solutions of the above-mentioned embodiments, the step 103 of "establishing a histogram according to the skeleton endpoints and edge points based on the shape context descriptor" may specifically include the following steps:

(1)基于形状上下文描述子，在每一幅图像中，对于每一个骨架端点，计算骨架端点和每一个边缘点的梯度角，具体计算如下：(1) Based on the shape context descriptor, in each image, for each skeleton endpoint, calculate the gradient angle between the skeleton endpoint and each edge point, the specific calculation is as follows:

对于骨架点p(x,y)而言，其中p(x,y)表示所述骨架点的灰度值，(x,y)表示所述骨架点坐标。那么所述骨架点分别沿X方向和Y方向的梯度为For the skeleton point p(x, y), p(x, y) represents the gray value of the skeleton point, and (x, y) represents the coordinates of the skeleton point. Then the gradients of the skeleton points along the X direction and the Y direction are

Dx＝p(x+1,y)-p(x-1,y)Dx=p(x+1,y)-p(x-1,y)

Dy＝p(x,y+1)-p(x,y-1)Dy=p(x,y+1)-p(x,y-1)

其中p(x+1,y)，p(x-1,y)，p(x,y+1)，p(x,y-1)分别为所述骨架点(x,y)上下左右点的灰度值，Dx和Dy分别为所述骨架点沿X和Y方向的梯度。则所述骨架点的梯度角为Among them, p(x+1, y), p(x-1, y), p(x, y+1), p(x, y-1) are the upper, lower, left, and right points of the skeleton point (x, y) respectively The gray value of , Dx and Dy are the gradients of the skeleton points along the X and Y directions, respectively. Then the gradient angle of the skeleton point is

$\mathrm{<span><span>G</span>G</span>}<span><span>(</span>(</span>\mathrm{<span><span>x</span>x</span>}<span><span>,</span>,</span>\mathrm{<span><span>y</span>the\; y</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\sqrt{{\mathrm{<span><span>Dx</span>Dx</span>}}^{\mathrm{<span><span>2</span>2</span>}}<span><span>+</span>+</span>{\mathrm{<span><span>Dy</span>Dy</span>}}^{\mathrm{<span><span>2</span>2</span>}}}$

G(x,y)为所述骨架点的梯度角。对于边缘点而言，其梯度角的计算方式类似。G(x,y) is the gradient angle of the skeleton point. For edge points, the calculation method of the gradient angle is similar.

(2)对于每一个骨架端点，计算该骨架端点与每一个所述边缘点的相对矢量关系，并根据该骨架端点和每一个边缘点的梯度角计算骨架端点与每一个边缘点的相对梯度角关系，具体计算如下：(2) For each skeleton endpoint, calculate the relative vector relationship between the skeleton endpoint and each edge point, and calculate the relative gradient angle between the skeleton endpoint and each edge point according to the gradient angle between the skeleton endpoint and each edge point The relationship is calculated as follows:

对于骨架端点p，边缘点e，对应的梯度角分别为G(x,y)和Ge(x,y)，其中(x,y)为坐标位置。骨架端点与每一个边缘点的相对矢量关系如下：For the skeleton endpoint p and the edge point e, the corresponding gradient angles are G(x,y) and Ge(x,y) respectively, where (x,y) is the coordinate position. The relative vector relationship between the skeleton endpoint and each edge point is as follows:

$\stackrel{<span><span>\&RightArrow;</span>\&Right\; Arrow;</span>}{\mathrm{<span><span>r</span>r</span>}}<span><span>=</span>=</span>\stackrel{<span><span>\&RightArrow;</span>\&Right\; Arrow;</span>}{\mathrm{<span><span>p</span>p</span>}}<span><span>-</span>-</span>\stackrel{<span><span>\&RightArrow;</span>\&Right\; Arrow;</span>}{\mathrm{<span><span>e</span>e</span>}}$

其中r表示骨架端点与每一个边缘点的二维相对矢量关系，对应于骨架端点与边缘点的坐标位置差分。骨架端点与每一个边缘点的相对梯度角关系如下Where r represents the two-dimensional relative vector relationship between the skeleton endpoint and each edge point, corresponding to the coordinate position difference between the skeleton endpoint and the edge point. The relative gradient angle relationship between the skeleton endpoint and each edge point is as follows

R(x,y)＝G(x,y)-Ge(x,y)R(x,y)=G(x,y)-Ge(x,y)

其中R(x,y)为骨架端点与每一个边缘点的相对梯度角。where R(x,y) is the relative gradient angle between the end point of the skeleton and each edge point.

(3)利用上述得到的该骨架端点对应相对矢量关系以及相对梯度角关系在对数极坐标系中建立该骨架端点对应的直方图。(3) Establish a histogram corresponding to the skeleton endpoint in the logarithmic polar coordinate system by using the relative vector relationship and the relative gradient angle relationship obtained above.

例如，假设给定的目标中包含n个骨架端点，对于第一幅图中目标上的骨架端点p_i，该点与所有边缘点的相对矢量关系的相关直方图h_i可以通过如下公式获得：For example, assuming that a given target contains n skeleton endpoints, for the skeleton endpoint p_i on the target in the first figure, the correlation histogram h_i of the relative vector relationship between this point and all edge points can be obtained by the following formula:

${\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>i</span>i</span>}}^{\mathrm{<span><span>k</span>k</span>}}<span><span>=</span>=</span><span><span>\#</span>\#</span><span><span>\{</span>\{</span>\mathrm{<span><span>q</span>q</span>}<span><span>\&NotEqual;</span>\&NotEqual;</span>{\mathrm{<span><span>p</span>p</span>}}_{\mathrm{<span><span>i</span>i</span>}}<span><span>:</span>:</span><span><span>(</span>(</span>\mathrm{<span><span>q</span>q</span>}<span><span>-</span>-</span>{\mathrm{<span><span>p</span>p</span>}}_{\mathrm{<span><span>i</span>i</span>}}<span><span>)</span>)</span><span><span>\&Element;</span>\&Element;</span>\mathrm{<span><span>bin</span>bin</span>}<span><span>(</span>(</span>\mathrm{<span><span>k</span>k</span>}<span><span>)</span>)</span><span><span>\}</span>\}</span>$

那么，这个直方图定义为p_i的骨架上下文。在对极空间中，直方图的bins是同一的，这使得描述子对近邻像素更加敏感。Then, this histogram is defined as the skeleton context of p_i . In epipolar space, the bins of the histogram are identical, which makes the descriptor more sensitive to neighboring pixels.

进一步可选地，上述实施例中的步骤104“根据相似性度量准则和直方图对两幅图像进行形状匹配”，具体可以包括如下步骤：Further optionally, step 104 in the above-mentioned embodiment "perform shape matching on two images according to the similarity measure criterion and histogram", may specifically include the following steps:

(a)根据两幅图像中每一个骨架端点的直方图，利用相似性度量准则计算两幅图像中的两个骨架端点的相似性度量值；(a) according to the histogram of each skeleton endpoint in the two images, use the similarity measurement criterion to calculate the similarity measure value of the two skeleton endpoints in the two images;

考虑第一幅图中目标骨架端点p_i和第二幅图中目标骨架端点q_j，C_ij＝C(p_i,q_j)表示匹配这两个点的代价(即相似性度量值)。由于描述子是通过直方图来表达的，C_ij可以通过使用χ测试统计来计算，利用相似性度量准则计算两幅图像中的两个骨架端点的相似性度量值可以采用如下公式来计算：Considering the target skeleton endpoint p_i in the first image and the target skeleton endpoint q_j in the second image, C_ij =C(p_i , q_j ) represents the cost of matching these two points (ie, the similarity measure). Since the descriptor is expressed by a histogram, C_ij can be calculated by using the χ test statistic, and the similarity measure value of two skeleton endpoints in two images can be calculated using the similarity measure criterion as follows:

${\mathrm{<span><span>C</span>C</span>}}_{\mathrm{<span><span>ij</span>ij</span>}}<span><span>=</span>=</span>\mathrm{<span><span>C</span>C</span>}<span><span>(</span>(</span>{\mathrm{<span><span>p</span>p</span>}}_{\mathrm{<span><span>i</span>i</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>q</span>q</span>}}_{\mathrm{<span><span>j</span>j</span>}}<span><span>)</span>)</span><span><span>=</span>=</span>\frac{\mathrm{<span><span>1</span>1</span>}}{\mathrm{<span><span>2</span>2</span>}}\underset{\mathrm{<span><span>k</span>k</span>}<span><span>=</span>=</span>\mathrm{<span><span>1</span>1</span>}}{\overset{\mathrm{<span><span>K</span>K</span>}}{\mathrm{<span><span>\&Sigma;</span>\&Sigma;</span>}}}\frac{{<span><span>[</span>[</span>{\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>i</span>i</span>}}<span><span>(</span>(</span>\mathrm{<span><span>k</span>k</span>}<span><span>)</span>)</span><span><span>-</span>-</span>{\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>j</span>j</span>}}<span><span>(</span>(</span>\mathrm{<span><span>k</span>k</span>}<span><span>)</span>)</span><span><span>]</span>]</span>}^{\mathrm{<span><span>2</span>2</span>}}}{{\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>i</span>i</span>}}<span><span>(</span>(</span>\mathrm{<span><span>k</span>k</span>}<span><span>)</span>)</span><span><span>+</span>+</span>{\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>j</span>j</span>}}<span><span>(</span>(</span>\mathrm{<span><span>k</span>k</span>}<span><span>)</span>)</span>}$

其中p_i,q_j分别为两幅图像中第一幅图像中的第i个骨架端点和两幅图像中第二副图像中的第j个骨架端点，h_i(k)为第一幅图像上第i个骨架端点建立的直方图上第k个bin值，h_j(k)为第二幅图像上第j个骨架端点建立的直方图上第k个bin值，K表示直方图的总bins数目；C(p_i,q_j)表示p_i,q_j两个骨架端点的相似性度量值。这样就获得了每个骨架端点的直方图。本发明的bin都表示单元格的意思。Where p_i , q_j are the i-th skeleton endpoint in the first image of the two images and the j-th skeleton endpoint in the second image of the two images, h_i (k) is the first image h_j (k) is the kth bin value on the histogram established by the jth skeleton endpoint on the second image, and K represents the total number of histograms The number of bins; C(p_i , q_j ) represents the similarity measure of the two skeleton endpoints of p_i , q_j . This results in a histogram of the endpoints of each skeleton. The bin of the present invention all represents the meaning of cell.

(b)对于两幅图像的其中一幅图像中的每一个骨架端点，获取另一幅图像中与当前的骨架端点的相似性度量值最大的骨架端点作为匹配点；(b) For each skeleton endpoint in one of the two images, obtain the skeleton endpoint with the largest similarity measure value with the current skeleton endpoint in the other image as a matching point;

(c)利用每一个骨架端点及对应的匹配点对两幅图像进行形状匹配。(c) Perform shape matching on the two images using each skeleton endpoint and the corresponding matching point.

上述实施例中的可选技术方案，可以采用可以结合的方式任意组合，形成本发明的可选实施例，在此不再一一赘述。The optional technical solutions in the above embodiments can be combined in any combination to form optional embodiments of the present invention, which will not be repeated here.

为了验证描述子的有效性，采用标准形状测试数据库中的一些图像进行匹配，得到的匹配结果分别如图2-7所示。其中图2为本发明实施例提供的对形状测试数据库MPEG-7中的carriage-01.gif与carriage-06.gif的匹配结果；图3为本发明实施例提供的对形状测试数据库中的camel-2.gif与camel-9.gif的匹配结果；图4为本发明实施例提供的对形状测试数据库中的brick-15.gif与brick-16.gif的匹配结果；图5为本发明实施例提供的对形状测试数据库中的butterfly-14.gif与butterfly-15.gif的匹配结果；图6为本发明实施例提供的对形状测试数据库中的chicken-4.gif与chicken-5.gif的匹配结果；图7为本发明实施例提供的对形状测试数据库中的bird-5.gif与bird-6.gif的匹配结果。图2-图7中目标上的黑色圆圈表示提取的骨架端点，线段连接两幅图中对应的匹配点。可以看到，当目标出现一定形状变形(图2)、关节变化及缩放(图3)、平移和缩放(图4)、旋转(图5-7)时，采用本发明上述实施例的技术方案的描述子均能实现准确的匹配。这是由于这种描述子结合了骨架特征点和轮廓信息，同时采用形状上下文的思想进行描述子，实现了对平移、旋转、尺度变化以及关节变化和部分变形的不变性。In order to verify the effectiveness of the descriptor, some images in the standard shape test database are used for matching, and the matching results are shown in Figure 2-7. Wherein Fig. 2 is the matching result to carriage-01.gif and carriage-06.gif in the shape test database MPEG-7 provided by the embodiment of the present invention; Fig. 3 is provided to the camel in the shape test database by the embodiment of the present invention -2.gif and the matching result of camel-9.gif; Fig. 4 provides the matching result to brick-15.gif and brick-16.gif in the shape test database provided by the embodiment of the present invention; Fig. 5 is the implementation of the present invention Example provides the matching result of butterfly-14.gif and butterfly-15.gif in the shape test database; FIG. 6 is chicken-4.gif and chicken-5.gif in the shape test database provided by the embodiment of the present invention The matching result; FIG. 7 is the matching result of bird-5.gif and bird-6.gif in the shape test database provided by the embodiment of the present invention. The black circles on the objects in Figures 2-7 indicate the extracted skeleton endpoints, and the line segments connect the corresponding matching points in the two figures. It can be seen that when the target has a certain shape deformation (Figure 2), joint change and scaling (Figure 3), translation and scaling (Figure 4), and rotation (Figure 5-7), the technical solutions of the above-mentioned embodiments of the present invention are adopted The descriptors can achieve accurate matching. This is because this descriptor combines skeleton feature points and contour information, and uses the idea of shape context to describe the descriptor, which realizes the invariance to translation, rotation, scale change, joint change and partial deformation.

为了定量评估本算法的性能，以图5-7的匹配为例，与形状上下文描述子进行比较，得到的正确匹配率以及匹配耗时分别如表1和表2所示。可以看到，虽然骨架上下文描述子获得的匹配正确略低于形状上下文，但是在速度上却提升了12倍之多。In order to quantitatively evaluate the performance of this algorithm, taking the matching in Figure 5-7 as an example, and comparing it with the shape context descriptor, the correct matching rate and matching time are shown in Table 1 and Table 2, respectively. It can be seen that although the matching accuracy obtained by the skeleton context descriptor is slightly lower than that of the shape context, the speed is increased by as much as 12 times.

表1  正确匹配率比较Table 1 Comparison of correct matching rate

描述子descriptor图5Figure 5图6Figure 6图7Figure 7骨架上下文skeleton context57％57%81％81%90％90%形状上下文shape context78.56％78.56%91.89％91.89%66.7％66.7%

表2  匹配耗时比较/sTable 2 Comparison of matching time/s

描述子descriptor图5Figure 5图6Figure 6图7Figure 7骨架上下文skeleton context1.59231.59232.11812.11815.73475.7347形状上下文shape context18.984118.984128.431528.431566.909566.9095

为了验证描述子的适应性，采用真实采集的飞机序列图像进行匹配，获得的匹配结果如图8所示。图8为本发明实施例提供的对实际采集的飞机序列中第1帧与第86帧进行匹配的结果。如图8所示，可以看到，当目标出现自遮挡时，采用本发明的描述子仍然能够实现准确的匹配，从而为后续的跟踪定位奠定基础。In order to verify the adaptability of the descriptor, the real collected aircraft sequence images are used for matching, and the obtained matching results are shown in Figure 8. Fig. 8 is a result of matching the first frame and the 86th frame in the actually collected aircraft sequence provided by the embodiment of the present invention. As shown in FIG. 8 , it can be seen that when the target appears to be self-occluded, the descriptor of the present invention can still achieve accurate matching, thereby laying the foundation for subsequent tracking and positioning.

图9为本发明实施例提供的结合骨架特征点和形状上下文的形状匹配装置的结构示意图。如图9所示，本实施例的结合骨架特征点和形状上下文的形状匹配装置，具体可以包括：去噪处理模块10、目标分割模块11、提取模块12、直方图建立模块13和形状匹配模块14。Fig. 9 is a schematic structural diagram of a shape matching device combining skeleton feature points and shape context provided by an embodiment of the present invention. As shown in FIG. 9 , the shape matching device combining skeleton feature points and shape context in this embodiment may specifically include: a denoising processing module 10, an object segmentation module 11, an extraction module 12, a histogram building module 13 and a shape matching module 14.

其中去噪处理模块10用于对两幅图像中的每幅图像进行去除噪声处理，各得到滤波后的平滑图像；目标分割模块11与去噪处理模块10连接，目标分割模块11用于采用OTSU方法对去噪处理模块10处理得到的平滑图像进行目标分割，获得二值目标图像；提取模块12用于对二值目标图像进行骨架提取，获得骨架特征点，并根据骨架特征点获取骨架端点；并对目标分割模块11得到的二值目标图像进行边缘检测，提取边缘点；直方图建立模块13与提取模块12连接，直方图建立模块13用于基于形状上下文描述子，根据提取模块12得到的骨架端点与边缘点建立直方图；形状匹配模块14与直方图建立模块13连接，形状匹配模块14用于根据相似性度量准则和直方图建立模块13建立的直方图对两幅图像进行形状匹配。Wherein the denoising processing module 10 is used to carry out denoising processing to each image in the two images, and each obtains a smooth image after filtering; the target segmentation module 11 is connected with the denoising processing module 10, and the target segmentation module 11 is used to adopt OTSU The method performs target segmentation on the smooth image obtained by the denoising processing module 10 to obtain a binary target image; the extraction module 12 is used to perform skeleton extraction on the binary target image to obtain skeleton feature points, and obtain skeleton endpoints according to the skeleton feature points; And carry out edge detection to the binary target image that target segmentation module 11 obtains, extract edge point; Histogram establishment module 13 is connected with extraction module 12, and histogram establishment module 13 is used for based on shape context descriptor, obtains according to extraction module 12 Skeleton endpoints and edge points establish a histogram; the shape matching module 14 is connected with the histogram establishing module 13, and the shape matching module 14 is used to perform shape matching on two images according to the similarity measurement criterion and the histogram established by the histogram establishing module 13.

本实施例的结合骨架特征点和形状上下文的形状匹配装置，通过采用上述模块实现结合骨架特征点和形状上下文的形状匹配，与上述相关方法实施例的实现机制相同，详细可以参考上述相关实施例的记载，在此不再赘述。The shape matching device combining skeleton feature points and shape context in this embodiment implements shape matching combining skeleton feature points and shape context by using the above-mentioned modules. records will not be repeated here.

本实施例的结合骨架特征点和形状上下文的形状匹配装置，通过采用上述模块实现对分割后的目标进行骨架提取，获得骨架端点。利用骨架端点与边缘点的关系建立直方图，而不是利用所有的骨架点，这样大大降低了计算复杂度；本实施例的结合骨架特征点和形状上下文，提出一种新的骨架描述子，对平移、旋转、尺度变化和非刚性变形具有不变性；本实施例的技术方案，与基于形状上下文描述子的匹配方法相比，得到的描述子复杂度更低，大大降低了运算时间，同时具有较好的匹配性能；本实施例的技术方案，不仅用于形状匹配和检索，还可用于目标跟踪，尤其是异性扩展目标的跟踪中。The shape matching device of this embodiment that combines skeleton feature points and shape context uses the above modules to extract the skeleton of the segmented object and obtain the skeleton endpoints. Use the relationship between the skeleton endpoint and the edge point to build a histogram instead of using all the skeleton points, which greatly reduces the computational complexity; this embodiment combines the skeleton feature points and the shape context to propose a new skeleton descriptor. Translation, rotation, scale change and non-rigid deformation are invariant; compared with the matching method based on the shape context descriptor, the technical solution of this embodiment has lower complexity of the obtained descriptor, greatly reduces the operation time, and has Better matching performance; the technical solution of this embodiment is not only used for shape matching and retrieval, but also can be used for target tracking, especially the tracking of heterosexual extended targets.

可选地，在上述实施例的技术方案的基础上，其中提取模块12具体用于将目标分割模块11中的二值目标图像中已知的目标点标记为1，背景点标记为0，定义边界点是本身标记为1，而所述边界点的8连通区域中至少有一个点标记为0，以所述边界点为中心的8连通邻域，记中心点为p₁，其邻域的8个点顺时针绕中心点分别记为p₂,p₃,...,p₉,其中所述p₂在所述p₁上方；Optionally, on the basis of the technical solutions of the above-mentioned embodiments, wherein the extraction module 12 is specifically configured to mark the known target points in the binary target image in the target segmentation module 11 as 1, and the background points as 0, define The boundary point itself is marked as 1, and at least one point in the 8-connected area of the boundary point is marked as 0. For the 8-connected neighborhood centered on the boundary point, record the center point as p₁ , and its neighborhood The eight points clockwise around the central point are respectively recorded as p₂ , p₃ ,...,p₉ , wherein the p₂ is above the p₁ ;

对所述边界点进行如下(A)和(B)两步操作：Carry out following (A) and (B) two-step operation to described boundary point:

(A)标记同时满足下列条件的边界点：(A) Mark the boundary points that meet the following conditions at the same time:

(a1)2δN(p₁)δ6；(a1)2δN(p₁ )δ6;

(a2)S(p₁)＝1；(a2)S(p₁ )=1;

(a3)$p_2\&ForAll;p_4\&ForAll;p_6=0;$(a3)$p_2\&ForAll;p_4\&ForAll;p_6=0;$

(a4)$p_4\&ForAll;p_6\&ForAll;p_8=0;$(a4)$p_4\&ForAll;p_6\&ForAll;p_8=0;$

其中N(p₁)是p₁的非零邻点个数，S(p₁)是以p₂,p₃,...,p₉为序时这些点的值从01的个数。当对全部所述边界点检验完毕后，将所有标记了的点除去；Where N(p₁ ) is the number of non-zero neighbors of p₁ , and S(p₁ ) is the number of values of these points from 01 when p₂ , p₃ ,...,p₉ are sequenced. After all the boundary points are checked, all marked points are removed;

(B)标记同时满足下列条件的边界点：(B) Mark the boundary points that meet the following conditions at the same time:

(b1)1δN(p₁)δ6；(b1)1δN(p₁ )δ6;

(b2)S(p₁)＝1；(b2)S(p₁ )=1;

(b3)$p_2\&ForAll;p_4\&ForAll;p_8=0;$(b3)$p_2\&ForAll;p_4\&ForAll;p_8=0;$

(b4)$p_2\&ForAll;p_6\&ForAll;p_8=0;$(b4)$p_2\&ForAll;p_6\&ForAll;p_8=0;$

以上两步操作(A)和(B)构成一次迭代，反复迭代直至没有点再满足标记条件，所述二值目标图像中剩下的点组成所述骨架特征点。The above two-step operations (A) and (B) constitute one iteration, and the iterations are repeated until no point satisfies the marking condition, and the remaining points in the binary target image form the skeleton feature points.

进一步可选地，在上述实施例的技术方案的基础上，其中提取模块12具体用于对每个骨架特征点进行八邻域判断，当八邻域中仅有一个骨架特征点时，将骨架特征点记录为骨架端点；对所有的骨架特征点进行八邻域判断，获取所有的骨架端点。Further optionally, on the basis of the technical solutions of the above-mentioned embodiments, the extraction module 12 is specifically configured to perform eight-neighborhood judgment on each skeleton feature point, and when there is only one skeleton feature point in the eight-neighborhood, the skeleton The feature points are recorded as the skeleton endpoints; the eight-neighborhood judgment is performed on all the skeleton feature points to obtain all the skeleton endpoints.

进一步可选地，在上述实施例的技术方案的基础上，其中直方图建立模块13具体用于基于形状上下文描述子，在每一幅图像中，对于提取模块12提取的每一个骨架端点，计算骨架端点和每一个边缘点的梯度角；对于每一个骨架端点，计算骨架端点与每一个边缘点的相对矢量关系，并根据骨架端点和每一个边缘点的梯度角计算骨架端点与每一个边缘点的相对梯度角关系；利用相对矢量关系以及相对梯度角关系在对数极坐标系中建立骨架端点对应的直方图。Further optionally, on the basis of the technical solutions of the above embodiments, the histogram building module 13 is specifically configured to calculate, in each image, for each skeleton endpoint extracted by the extraction module 12 based on the shape context descriptor The gradient angle between the skeleton endpoint and each edge point; for each skeleton endpoint, calculate the relative vector relationship between the skeleton endpoint and each edge point, and calculate the skeleton endpoint and each edge point according to the gradient angle between the skeleton endpoint and each edge point The relative gradient angle relationship; use the relative vector relationship and the relative gradient angle relationship to establish a histogram corresponding to the end points of the skeleton in the logarithmic polar coordinate system.

进一步可选地，在上述实施例的技术方案的基础上，其中形状匹配模块14具体用于根据直方图建立模块13得到的两幅图像中每一个骨架端点的直方图，利用相似性度量准则计算两幅图像中的两个骨架端点的相似性度量值；对于两幅图像的其中一幅图像中的每一个骨架端点，获取另一幅图像中与当前的骨架端点的相似性度量值最大的骨架端点作为匹配点；利用每一个骨架端点及对应的匹配点对两幅图像进行形状匹配。Further optionally, on the basis of the technical solutions of the above-mentioned embodiments, the shape matching module 14 is specifically used to calculate the histogram of each skeleton endpoint in the two images according to the histogram building module 13 using the similarity measurement criterion The similarity measure of the two skeleton endpoints in the two images; for each skeleton endpoint in one of the two images, obtain the skeleton with the largest similarity measure to the current skeleton endpoint in the other image The endpoints are used as matching points; use each skeleton endpoint and the corresponding matching point to perform shape matching on the two images.

进一步可选地，在上述实施例的技术方案的基础上，其中形状匹配模块14具体用于采用如下方式计算两幅图像中的两个骨架端点的相似性度量值：Further optionally, on the basis of the technical solutions of the above-mentioned embodiments, the shape matching module 14 is specifically configured to calculate the similarity metric values of the two skeleton endpoints in the two images in the following manner:

$\mathrm{<span><span>C</span>C</span>}<span><span>(</span>(</span>{\mathrm{<span><span>p</span>p</span>}}_{\mathrm{<span><span>i</span>i</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>q</span>q</span>}}_{\mathrm{<span><span>j</span>j</span>}}<span><span>)</span>)</span><span><span>=</span>=</span>\frac{\mathrm{<span><span>1</span>1</span>}}{\mathrm{<span><span>2</span>2</span>}}\underset{\mathrm{<span><span>k</span>k</span>}<span><span>=</span>=</span>\mathrm{<span><span>1</span>1</span>}}{\overset{\mathrm{<span><span>K</span>K</span>}}{\mathrm{<span><span>\&Sigma;</span>\&Sigma;</span>}}}\frac{{<span><span>[</span>[</span>{\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>i</span>i</span>}}<span><span>(</span>(</span>\mathrm{<span><span>k</span>k</span>}<span><span>)</span>)</span><span><span>-</span>-</span>{\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>j</span>j</span>}}<span><span>(</span>(</span>\mathrm{<span><span>k</span>k</span>}<span><span>)</span>)</span><span><span>]</span>]</span>}^{\mathrm{<span><span>2</span>2</span>}}}{{\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>i</span>i</span>}}<span><span>(</span>(</span>\mathrm{<span><span>k</span>k</span>}<span><span>)</span>)</span><span><span>+</span>+</span>{\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>j</span>j</span>}}<span><span>(</span>(</span>\mathrm{<span><span>k</span>k</span>}<span><span>)</span>)</span>}$

其中p_i,q_j分别为两幅图像中第一幅图像中的第i个骨架端点和两幅图像中第二副图像中的第j个骨架端点，h_i(k)为第一幅图像上第i个骨架端点建立的直方图上第k个bin值，h_j(k)为第二幅图像上第j个骨架端点建立的直方图上第k个bin值，K表示直方图的总bins数目；C(p_i,q_j)表示p_i,q_j两个骨架端点的相似性度量值。Where p_i , q_j are the i-th skeleton endpoint in the first image of the two images and the j-th skeleton endpoint in the second image of the two images, h_i (k) is the first image h_j (k) is the kth bin value on the histogram established by the jth skeleton endpoint on the second image, and K represents the total number of histograms The number of bins; C(p_i , q_j ) represents the similarity measure of the two skeleton endpoints of p_i , q_j .

上述实施例中的可选技术方案，可以采用可以结合的方式任意组合，形成本发明的可选实施例，在此不再一一赘述。The optional technical solutions in the above embodiments can be combined in any combination to form optional embodiments of the present invention, which will not be repeated here.

上述实施例的结合骨架特征点和形状上下文的形状匹配装置，通过采用上述模块实现结合骨架特征点和形状上下文的形状匹配，与上述相关方法实施例的实现机制相同，详细可以参考上述相关实施例的记载，在此不再赘述。The shape matching device combining skeleton feature points and shape context in the above embodiment uses the above-mentioned modules to realize shape matching combining skeleton feature points and shape context. records will not be repeated here.

上述实施例的结合骨架特征点和形状上下文的形状匹配装置，通过采用上述模块实现对分割后的目标进行骨架提取，获得骨架端点。利用骨架端点与边缘点的关系建立直方图，而不是利用所有的骨架点，这样大大降低了计算复杂度；本实施例的结合骨架特征点和形状上下文，提出一种新的骨架描述子，对平移、旋转、尺度变化和非刚性变形具有不变性；本实施例的技术方案，与基于形状上下文描述子的匹配方法相比，得到的描述子复杂度更低，大大降低了运算时间，同时具有较好的匹配性能；本实施例的技术方案，不仅用于形状匹配和检索，还可用于目标跟踪，尤其是异性扩展目标的跟踪中。In the shape matching device of the above embodiment that combines the skeleton feature points and the shape context, the above modules are used to extract the skeleton of the segmented object and obtain the skeleton endpoints. Use the relationship between the skeleton endpoint and the edge point to build a histogram instead of using all the skeleton points, which greatly reduces the computational complexity; this embodiment combines the skeleton feature points and the shape context to propose a new skeleton descriptor. Translation, rotation, scale change and non-rigid deformation are invariant; compared with the matching method based on the shape context descriptor, the technical solution of this embodiment has lower complexity of the obtained descriptor, greatly reduces the operation time, and has Better matching performance; the technical solution of this embodiment is not only used for shape matching and retrieval, but also can be used for target tracking, especially the tracking of heterosexual extended targets.

以上所描述的装置实施例仅仅是示意性的，其中作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到至少两个网络单元上。可以根据实际的需要选择其中的部分或者全部模块来实现本实施例方案的目的。本领域普通技术人员在不付出创造性的劳动的情况下，即可以理解并实施。The device embodiments described above are only illustrative, and the units described as separate components may or may not be physically separated, and the components shown as units may or may not be physical units, that is, they may be located in one place , or can also be distributed to at least two network elements. Part or all of the modules can be selected according to actual needs to achieve the purpose of the solution of this embodiment. It can be understood and implemented by those skilled in the art without any creative effort.

本发明未详细阐述部分属于本领域技术人员的公知技术。Parts not described in detail in the present invention belong to the known techniques of those skilled in the art.

本技术领域中的普通技术人员应当认识到，以上的实施例仅是用来说明本发明，而并非用作为对本发明的限定，只要在本发明的实质精神范围内，对以上所述实施例变化,变型都将落在本发明权利要求书的范围内。Those of ordinary skill in the art should recognize that the above embodiments are only used to illustrate the present invention, rather than as a limitation to the present invention, as long as within the scope of the spirit of the present invention, changes to the above embodiments , Modifications will fall within the scope of the claims of the present invention.

最后应说明的是：以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。Finally, it should be noted that: the above embodiments are only used to illustrate the technical solutions of the present invention, rather than to limit them; although the present invention has been described in detail with reference to the foregoing embodiments, those of ordinary skill in the art should understand that: it can still be Modifications are made to the technical solutions described in the foregoing embodiments, or equivalent replacements are made to some of the technical features; and these modifications or replacements do not make the essence of the corresponding technical solutions deviate from the spirit and scope of the technical solutions of the various embodiments of the present invention.

Claims (12)

1. in conjunction with a shape matching method for framework characteristic point and Shape context, it is characterized in that, comprise the steps:

Every width image in two width images is removed to noise processed, respectively obtain filtered smoothed image;

Adopt OTSU method to carry out Target Segmentation to described smoothed image, obtain binary object image;

Described binary object image is carried out to skeletal extraction, obtain framework characteristic point, and obtain all skeleton end points according to described framework characteristic point; And described binary object image is carried out to rim detection, extract all marginal points;

Based on Shape context descriptor, according to described skeleton end points and described marginal point, set up histogram;

According to similarity measurement criterion and described histogram, described two width images are carried out to form fit.

2. method according to claim 1, is characterized in that, described binary object image is carried out to skeletal extraction, obtains framework characteristic point, specifically comprises the steps:

Known impact point in described binary object image is labeled as to 1, background dot is labeled as 0, and definition frontier point is that itself is labeled as 1, and in 8 connected regions of described frontier point, has at least a point to be labeled as 0,8 connection neighborhoods centered by described frontier point, note central point is p₁, 8 points of its neighborhood are designated as respectively p around central point clockwise₂, p₃..., p₉, wherein said p₂at described p₁top;

Described frontier point is carried out to (A) and (B) two step operations as follows:

(A) mark meets the frontier point of following condition simultaneously:

(a1)2δN(p₁)δ6；

(a2)S(p₁)＝1；

(a3)$p_2\&ForAll;p_4\&ForAll;p_6=0;$

(a4)$p_4\&ForAll;p_6\&ForAll;p_8=0;$

N (p wherein₁) be p₁non-zero adjoint point number, S (p₁) be with p₂, p₃..., p₉the number of the value of these points from 01 during for order; After whole described frontier points are verified, by all marks point remove;

(B) mark meets the frontier point of following condition simultaneously:

(b1)1δN(p₁)δ6；

(b2)S(p₁)＝1；

(b3)$p_2\&ForAll;p_4\&ForAll;p_8=0;$

(b4)$p_2\&ForAll;p_6\&ForAll;p_8=0;$

Above two steps operations (A) and (B) form an iteration, iterate until do not put and meet flag condition again, and in described binary object image, remaining point forms described framework characteristic point.

3. method according to claim 1, it is characterized in that, according to described framework characteristic point, obtain all skeleton end points, specifically comprise: framework characteristic point described in each is carried out to eight neighborhood judgements, while only having a described framework characteristic point in eight neighborhoods, described framework characteristic point is recorded as to described skeleton end points; All described framework characteristic points are carried out to eight neighborhood judgements, obtain all described skeleton end points.

4. method according to claim 1, is characterized in that, based on Shape context descriptor, according to described skeleton end points and described marginal point, sets up histogram, specifically comprises the steps:

Based on Shape context descriptor, in every piece image, for skeleton end points described in each, calculate the gradient angle of described skeleton end points and marginal point described in each;

For skeleton end points described in each, calculate described skeleton end points and the relative vector relation of marginal point described in each, and according to described skeleton end points and described in each the described gradient angle of marginal point calculate described skeleton end points and the described relative gradient angular dependence of marginal point described in each;

Utilize described relative vector relation and described relative gradient angular dependence to set up the described histogram that described skeleton end points is corresponding in log-polar system.

5. according to the arbitrary described method of claim 1-4, it is characterized in that, according to similarity measurement criterion and described histogram descriptor, described two width images carried out to form fit, specifically comprise:

According to the described histogram of skeleton end points described in each in described two width images, utilize described similarity measurement criterion to calculate the similarity measurement value of two described skeleton end points in described two width images;

For skeleton end points described in each in the wherein piece image of described two width images, obtain in another piece image with the described skeleton end points of the described similarity measurement value maximum of current described skeleton end points as match point;

Utilize two width images described in skeleton end points described in each and corresponding described matching double points to carry out form fit.

6. method according to claim 5, it is characterized in that, according to the described histogram of skeleton end points described in each in described two width images, utilize described similarity measurement criterion to calculate the similarity measurement value of two described skeleton end points in described two width images, specifically realize in the following way:

The similarity measurement value of two described skeleton end points in described two width images is calculated as follows:

$C(p_i,q_j)=\frac{1}{2}\underset{k=1}{\overset{K}{\mathrm{\&Sigma;}}}\frac{{[h_i\left(k\right)-h_j\left(k\right)]}^2}{h_i\left(k\right)+h_j\left(k\right)}$

P wherein_i, q_jbe respectively in described two width images j skeleton end points in the second sub-picture in i skeleton end points in piece image and described two width images, h_i(k) be k bin value on the histogram set up of the above i skeleton end points of described piece image, h_j(k) be the above k bin value of histogram that the above j skeleton end points of described the second width image is set up, K represents histogrammic total bins number; C(p_i, q_j) expression p_i, q_jthe similarity measurement value of two described skeleton end points.

7. in conjunction with a form fit device for framework characteristic point and Shape context, it is characterized in that, comprising:

Denoising module, removes noise processed for the every width image to two width images, respectively obtains filtered smoothed image;

Target Segmentation module, for adopting OTSU method to carry out Target Segmentation to described smoothed image, obtains binary object image;

Extraction module, for described binary object image is carried out to skeletal extraction, obtains framework characteristic point, and obtains skeleton end points according to described framework characteristic point; And described binary object image is carried out to rim detection, extract marginal point;

Histogram is set up module, for based on Shape context descriptor, according to described skeleton end points and described marginal point, sets up histogram;

Form fit module, for carrying out form fit according to similarity measurement criterion and described histogram to described two width images.

8. device according to claim 7, it is characterized in that, described extraction module, specifically for known impact point in described binary object image is labeled as to 1, background dot is labeled as 0, and definition frontier point is that itself is labeled as 1, and in 8 connected regions of described frontier point, has at least a point to be labeled as 0,8 connection neighborhoods centered by described frontier point, note central point is p₁, 8 points of its neighborhood are designated as respectively p around central point clockwise₂, p₃..., p₉, wherein said p₂at described p₁top;

Described frontier point is carried out to (A) and (B) two step operations as follows:

(A) mark meets the frontier point of following condition simultaneously:

(a1)2δN(p₁)δ6；

(a2)S(p₁)＝1；

(a3)$p_2\&ForAll;p_4\&ForAll;p_6=0;$

(a4)$p_4\&ForAll;p_6\&ForAll;p_8=0;$

N (p wherein₁) be p₁non-zero adjoint point number, S (p₁) be with p₂, p₃..., p₉the number of the value of these points from 01 during for order.After whole described frontier points are verified, by all marks point remove;

(B) mark meets the frontier point of following condition simultaneously:

(b1)1δN(p₁)δ6；

(b2)S(p₁)＝1；

(b3)$p_2\&ForAll;p_4\&ForAll;p_8=0;$

(b4)$p_2\&ForAll;p_6\&ForAll;p_8=0;$

Above two steps operations (A) and (B) form an iteration, iterate until do not put and meet flag condition again, and in described binary object image, remaining point forms described framework characteristic point.

9. device according to claim 7, it is characterized in that, described extraction module, specifically for carrying out eight neighborhood judgements to framework characteristic point described in each, while only having a described framework characteristic point in eight neighborhoods, described framework characteristic point is recorded as to described skeleton end points; All described framework characteristic points are carried out to eight neighborhood judgements, obtain all described skeleton end points.

10. device according to claim 7, is characterized in that, described histogram is set up module, specifically for based on Shape context descriptor, in every piece image, for skeleton end points described in each, calculate the gradient angle of described skeleton end points and marginal point described in each; For skeleton end points described in each, calculate described skeleton end points and the relative vector relation of marginal point described in each, and according to described skeleton end points and described in each the described gradient angle of marginal point calculate described skeleton end points and the described relative gradient angular dependence of marginal point described in each; Utilize described relative vector relation and described relative gradient angular dependence to set up the described histogram that described skeleton end points is corresponding in log-polar system.

11. according to the arbitrary described device of claim 7-10, it is characterized in that, described form fit module, specifically for according to the described histogram of skeleton end points described in each in described two width images, utilize described similarity measurement criterion to calculate the similarity measurement value of two described skeleton end points in described two width images; For skeleton end points described in each in the wherein piece image of described two width images, obtain in another piece image with the described skeleton end points of the described similarity measurement value maximum of current described skeleton end points as match point; Utilize two width images described in skeleton end points described in each and corresponding described matching double points to carry out form fit.

12. devices according to claim 11, is characterized in that, described form fit module, specifically for calculating in the following way the similarity measurement value of two described skeleton end points in described two width images:

$C(p_i,q_j)=\frac{1}{2}\underset{k=1}{\overset{K}{\mathrm{\&Sigma;}}}\frac{{[h_i\left(k\right)-h_j\left(k\right)]}^2}{h_i\left(k\right)+h_j\left(k\right)}$

P wherein_i, q_jbe respectively in described two width images j skeleton end points in the second sub-picture in i skeleton end points in piece image and described two width images, h_i(k) be k bin value on the histogram set up of the above i skeleton end points of described piece image, h_j(k) be the above k bin value of histogram that the above j skeleton end points of described the second width image is set up, K represents histogrammic total bins number; C(p_i, q_j) expression p_i, q_jthe similarity measurement value of two described skeleton end points.