Pattern matching in the Hamming distance with thresholds

It has long been known that pattern matching in the Hamming distance metric can be done in time, where n is the length of the text, m is the length of the pattern, and Σ is the alphabet. The classic algorithm for this is due to Abrahamson and Kosaraju. This paper considers the following generalization, motivated by the situation where the entries in the text and pattern are analog, or distorted by additive noise, or imprecisely given for some other reason: in any alignment of the pattern with the text, two aligned symbols a and b contribute +1 to the similarity score if they differ by no more than a given threshold θ, otherwise they contribute zero. We give an time algorithm for this more general version of the problem; the classic Hamming distance matching problem is the special case of θ=0.     

Hybrid image matching combining Hausdorff distance with normalized gradient matching

Image matching has been a central problem in computer vision and image processing for decades. Most of the previous approaches to image matching can be categorized into the intensity-based and edge-based comparison. Hausdorff distance has been widely used for comparing point sets or edge maps since it does not require point correspondences. In this paper, we propose a new image similarity measure combining the Hausdorff distance with a normalized gradient consistency score for image matching. The normalized gradient consistency score is designed to compare the normalized image gradient fields between two images to alleviate the illumination variation problem in image matching. By combining the edge-based and intensity-based information for image matching, we are able to achieve robust image matching under different lighting conditions. We show the superior robustness property of the proposed image matching technique through experiments on face recognition under different lighting conditions.     

使用汉明距离约束的LBP人脸识别算法

提出了一种新的使用汉明距离约束的LBP（局部二值化模式）人脸识别算法。传统的LBP算子使用一致性模式（Uniform Pattern）来描述图像的局部特征,并且把其他非一致性模式都归并到另外的一个类中去,对于受光照和表情变化影响的图像,这种方法的准确性会降低。假定光照、姿态、表情的影响都可以看作是某种“噪声”,把信道编码中广泛应用的汉明距离引入到LBP算法中,减少由于这些噪声干扰产生的错误率。在FRGC上的实验结果显示：对于无约束环境下的人脸图片来说,该方法要优于传统的基于LBP的人脸识别方法。     

The communication complexity of the Hamming distance problem

We investigate the randomized and quantum communication complexity of the Hamming Distance problem, which is to determine if the Hamming distance between two n-bit strings is no less than a threshold d. We prove a quantum lower bound of Ω(d) qubits in the general interactive model with shared prior entanglement. We also construct a classical protocol of O(dlogd) bits in the restricted Simultaneous Message Passing model with public random coins, improving previous protocols of O(d²) bits [A.C.-C. Yao, On the power of quantum fingerprinting, in: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 77-81], and O(dlogn) bits [D. Gavinsky, J. Kempe, R. de Wolf, Quantum communication cannot simulate a public coin, quant-ph/0411051, 2004].     

Adaptive Low Resolution Pruning for fast Full Search-equivalent pattern matching

Several recent proposals have shown the feasibility of significantly speeding-up pattern matching by means of Full Search-equivalent techniques, i.e. without approximating the outcome of the search with respect to a brute force investigation. These techniques are generally heavily based on efficient incremental calculation schemes aimed at avoiding unnecessary computations. In a very recent and extensive experimental evaluation, Low Resolution Pruning turned out to be in most cases the best performing approach. In this paper we propose a computational analysis of several incremental techniques specifically designed to enhance the efficiency of LRP. In addition, we propose a novel LRP algorithm aimed at minimizing the theoretical number of operations by adaptively exploiting different incremental approaches. We demonstrate the effectiveness of our proposal by means of experimental evaluation on a large dataset.     

一种基于鲁棒Hausdorff距离的目标匹配算法

在传统的基于边缘位置的Hausdorff距离匹配的基础上,将边缘的梯度信息引入到距离度量当中,构造了一种新的三维距离函数。在此基础上,提出了一种鲁棒的三维Hausdorff距离及其目标匹配算法,采用粗匹配与精匹配相结合的两步匹配策略有效解决了由距离度量维数增加所导致的算法复杂性增大的问题。实验表明,该算法相对于传统的基于边缘位置的Hausdorff距离目标匹配算法在鲁棒性上有很大的提高。     

用线性码构造DNA计算编码的海明距离

最小海明距离是DNA计算编码性能的重要评价标准。利用线性码来构造DNA计算编码的最小海明距离是一种有效的方法,关键在于构造相应的监督矩阵。为了寻找监督矩阵,提出了监督矩阵的搜索算法和优化方法,及两个必要性定理;作为介于最小海明距离上限与下限之间的编码存在性的判断依据,给出了两个关于线性码存在性定理;最后给出了三字母表DNA计算编码相关的监督矩阵搜索算法结果,以及当最小海明距离一定时,接近编码数量上限的部分线性码的存在性结果。根据这些结果和存在性定理,可以推断常用DNA计算编码最小海明距离的存在性。     

Accurate M-hausdorff distance similarity combining distance orientation for matching multi-modal sensor images

Although Hausdorff distance (HD) has been widely used in an object identification between same modality images, the object identification between different modality images are challenging because of the poor edge correspondence coming from heterogeneous image characteristics. This paper proposes a robust Hausdorff distance similarity (accurate M-HD: AMHD) between multi-modal sensor data. To improve robustness against the outliers when comparing the pairs of multi-modal images, the AMHD utilizes the orientation information of each point in addition to the distance transform (DT) map as a similarity criterion. In the AMHD scheme, the DT map is generated by applying dead-reckoning signed DT, and the distance orientation (DO) map is constructed by employing the Kirsch compass kernel to the DT map, respectively. Using the additional information on the DO, the proposed similarity can precisely examine the outliers including non-correspondent edges and noises, and discard false correspondent distances efficiently. The computer simulations show that the proposed AMHD yields superior performance at aligning multi-modal sensor data (visible-thermal IR face images) over those achieved by the conventional robust schemes in terms of the position error between the ground truth and the computed position.     

哈明距离下1-重心问题的反问题

主要讨论哈明距离下网络中的1-重心问题的反问题。1-重心问题的反问题主要研究如何尽可能少地改变网络中的参数值,使得给定的顶点到其他顶点的加权距离之和不超过一个给定的上界。证明了在哈明距离下该问题是NP困难的。并运用动态规划的思想,在考虑改变顶点的权的情况下,对一般网络进行了求解。     

基于距离融合的图像特征点匹配方法

针对ORB算法中特征点缺乏尺度不变性导致算法误匹配率高,以及二进制鲁棒独立基本特征（BRIEF）算法的描述子易受噪声影响的问题,提出了改进的特征点匹配方法。采用加速的具有鲁棒性的特征（SURF）算法进行特征点提取,利用带有方向信息的BRIEF算法进行特征点描述;在特征点邻域内选取随机点对,并对随机点对的灰度大小比较和相似度比较分别进行编码,采用汉明距离计算两种编码的差异;利用自适应加权融合的方式实现特征点相似性距离度量。实验结果表明,改进方法对于尺度变化、光照变化以及模糊变化的图像具有更好的适应性,与传统ORB特征点匹配方法相比能够获得更高的特征点正确匹配率,且该特征点匹配方法可用于改善图像拼接的性能。     

Swap and mismatch edit distance

There is no known algorithm that solves the general case of theapproximate string matching problem with the extended edit distance, where the edit operations are: insertion, deletion, mismatch and swap, in timeo(nm), wheren is the length of the text andm is the length of the pattern. In an effort to study this problem, the edit operations were analysed independently. It turns out that the approximate matching problem with only the mismatch operation can be solved in timeO(n √m logm). If the only edit operation allowed is swap, then the problem can be solved in timeO(n logm logσ), whereσ=min(m, |Σ|). In this paper we show that theapproximate string matching problem withswap andmismatch as the edit operations, can be computed in timeO(n √m logm). Amihood Amir was partially supported by NSF Grant CCR-01-04494 and ISF Grant 35/05. This work is part of Estrella Eisenberg’s M.Sc. thesis. Ely Porat was partially supported by GIF Young Scientists Program Grant 2055-1168.6/2002.     

基于汉明距离的DNA编码约束研究

DNA计算是将现实问题进行编码映射到DNA分子上,通过生物实验产生出代表问题的解的DNA分子,最后通过检测技术提取出该DNA分子。高质量的DNA编码可以尽可能避免或减少计算过程中出现的错误,并使检测阶段易于提取出代表问题的解的DNA分子。对DNA编码约束进行了研究,分析了基于汉明距离的编码约束可以有效降低DNA分子间相似程度,减少DNA计算过程中DNA分子间的相互干扰,从而提高DNA计算的有效性和可靠性。还证明了基于汉明距离的编码约束存在等价的序列组合,降低了编码计算的复杂度。     

A pattern matching system

This paper describes a pattern matching system which has been implemented as a set of library procedures. The system provides a concise and consistent method of pattern definition and facilities for defining context sensitive pattern matching, defining repetitive patterns and defining alternatives. The operations available to the user allow him to identify if a substring matches a pattern, to extract that substring, to replace that substring and to associate a name with that substring. The system has applications in information retrieval, text manipulation and language processing.     

基于汉明距离的无线传感器网络密钥预分配方案*

无线传感器网络自身的特征,如网络规模庞大,动态的拓扑结构,有限的计算、通信和存储能力等,使得传统的密钥分配和管理机制无法直接应用。基于汉明距离提出了一种新的适用于无线传感器网络的密钥预分配方案。该方案将对称密钥系统和非对称密钥系统结合起来,并借助汉明距离的概念在无线传感器网络中实现了密钥的分配和管理。与随机密钥预分配方案相比,本方案在健壮性和安全性方面具有一定的优势,其计算和存储开销也不大,具有一定的实用性。     

隐私保护DNA序列汉明距离计算问题

DNA序列承载着人体重要的生物学信息，如何在保护隐私的情况下正确地对不同的DNA序列进行比对，成为亟待研究的科学问题。汉明距离在一定程度上刻画了两个DNA序列的相似程度，在保护隐私的情况下，研究DNA序列的汉明距离计算问题。首先定义了DNA序列的0-1编码规则，该规则将长度为n的DNA序列编码成长度为4n的0-1串，证明了两个DNA序列的汉明距离等于它们的0-1编码串的汉明距离的一半。以此结论为基础，以GM加密算法为主要密码学工具，构造了计算DNA序列汉明距离的一个安全两方计算协议。在半诚实攻击者模型下，证明了协议的正确性，给出了基于模拟器的安全性证明，并对协议的效率进行了分析。     

Approximate regular expression pattern matching with concave gap penalties

Given a sequenceA of lengthM and a regular expressionR of lengthP, an approximate regular expression pattern-matching algorithm computes the score of the optimal alignment betweenA and one of the sequencesB exactly matched byR. An alignment between sequencesA=a₁a₂ ... a_M andB=b₁b₂... b_N is a list of ordered pairs, (i₁,j₁), (i₂j₂), ..., (i_t,j_tt) such that i_k < i_k+1 and j_k < j_k+1. In this case the alignmentaligns symbols a_ik and b_jk, and leaves blocks of unaligned symbols, orgaps, between them. A scoring schemeS associates costs for each aligned symbol pair and each gap. The alignment's score is the sum of the associated costs, and an optimal alignment is one of minimal score. There are a variety of schemes for scoring alignments. In a concave gap penalty scoring schemeS={, w}, a function (a, b) gives the score of each aligned pair of symbolsa andb, and aconcave function w(k) gives the score of a gap of lengthk. A function w is concave if and only if it has the property that, for allk > 1, w(k + 1) –w(k) w(k) –w(k –1). In this paper we present an O(MP(logM + log² P)) algorithm for approximate regular expression matching for an arbitrary and any concavew. This work was supported in part by the National Institute of Health under Grant RO1 LM04960.     

Point Set pattern matching ind-dimensions

In this paper we apply computational geometry techniques to obtain an efficient algorithm for the following point set pattern matching problem. Given a setS ofn points and a setP ofk points in thed-dimensional Euclidean space, determine whetherP matches anyk-subset ofS, where a match can be any similarity, i.e., the setP is allowed to undergo translation, rotation, reflection, and global scaling. Motivated by the need to traverse the sets in an orderly fashion to shun exponential complexity, we circumvent the lack of a total order for points in high-dimensional spaces by using an extension of one-dimensional sorting to higher dimensions (which we call circular sorting). This mechanism enables us to achieve the orderly traversal we sought. An optimal algorithm (in time and space) is described for performing circular sorting in arbitrary dimensions. The time complexity of the resulting algorithm for point set pattern matching is O(n logn+kn) for dimension one and O(kn^d) for dimensiond2.Supported in part by CNPq-Conselho Nacional de Desenvolvimento Cientifico e Tecnológico (Brazil) under Grants 200331/79, 300157/90-8, and 500787/91-3.Supported in part by the National Science Foundation under Grant CCR 8901815.     

A pattern matching macro processor

A general-purpose pattern matching macro processor is described. Macro patterns can be defined using regular expressions. Macro calls are treated by balancing pattern matching at the token unit level, allowing options, alternatives and repetition. Thus, text in a language with a nested structure can be dealt with. In a macro body, Algol-style macro-time operations are allowed, which improves writing and reading. Our macro processor can also be used as a tool for language conversion since it incorporates a feature to declare language-dependent constructs such as comments, string notations and parentheses pairs. Although our macro processor is not biased towards any particular language, it has successfully converted an Algol 68-style text into a Fortran text. Problems of language conversion using macros are briefly discussed based upon the experience obtained through this macro processor.     

Rotation-invariant pattern matching with color ring-projection

In this paper, we propose a rotation-invariant pattern-matching scheme for detecting objects in complex color images. The complexity and computational load for matching colored objects in arbitrary orientations are reduced significantly by the 1-D color ring-projection representation. It can rapidly select the possible locations of a reference template in the input scene by computing the normalized correlation of 1-D color ring-projection patterns. Objects in the candidate locations are then verified by the pixel-to-pixel template matching. To make the pixel-based matching invariant to rotation, a color feature is used as pixel density, and the axis of least second moment is employed to estimate the rotational angle of a colored pattern. The proposed method has shown promising result based on experiments on a variety of natural and industrial images.