共查询到20条相似文献,搜索用时 0 毫秒
1.
The most efficient currently known algorithms for two-dimensional pattern matching with rotations have a worst case time complexity of O(n2m3), where the size of the text is n×n and the size of the pattern is m×m. In this paper we present a new algorithm for the problem whose running time is O(n2m2). 相似文献
2.
3.
XML数据库的查询优化技术是当前数据库领域中的一个研究热点,而小枝模式匹配又是其中的一个研究重点.在总结分析各种小枝模式匹配算法的基础上,提出了一种新的基于Extended Dewey编码的小枝模式匹配方法.该方法首先使用TJFast算法在XML文档的JoinGuide索引上进行预匹配,然后再扫描预匹配结果中的叶子结点序列就可以找出所有的匹配结果.最后,用实验的方法同其它算法作了比较,并对实验结果进行了分析. 相似文献
4.
Real-time pattern matching using projection kernels 总被引:4,自引:0,他引:4
Hel-Or Y Hel-Or H 《IEEE transactions on pattern analysis and machine intelligence》2005,27(9):1430-1445
A novel approach to pattern matching is presented in which time complexity is reduced by two orders of magnitude compared to traditional approaches. The suggested approach uses an efficient projection scheme which bounds the distance between a pattern and an image window using very few operations on average. The projection framework is combined with a rejection scheme which allows rapid rejection of image windows that are distant from the pattern. Experiments show that the approach is effective even under very noisy conditions. The approach described here can also be used in classification schemes where the projection values serve as input features that are informative and fast to extract. 相似文献
5.
Heiberg E. Ebbers T. Wigstrom L. Karlsson M. 《IEEE transactions on visualization and computer graphics》2003,9(3):313-319
This paper describes a novel method for regional characterization of three-dimensional vector fields using a pattern matching approach. Given a three-dimensional vector field, the goal is to automatically locate, identify, and visualize a selected set of classes of structures or features. Rather than analytically defining the properties that must be fulfilled in a region in order to be classified as a specific structure, a set of idealized patterns for each structure type is constructed. Similarity to these patterns is then defined and calculated. Examples of structures of interest include vortices, swirling flow, diverging or converging flow, and parallel flow. Both medical and aerodynamic applications are presented in this paper. 相似文献
6.
针对现有模式匹配算法无法实现大容量模式集快速搜索的不足,提出了一种基于TCAM多字节状态机的模式匹配算法。利用TCAM的掩码特性,切分具有相同匹配字符串的状态集,提出了一种编号编码压缩机制。通过理论证明,集合切分编码利用状态机的已匹配信息,将编号存储改变为编号段存储,大幅压缩了具有相同转移字符串和目的状态的交叉转移路径,减少TCAM表项数目。经理论分析和实验仿真,该算法不仅具有高搜索速率,而且可以减少大量相似表项,降低TCAM存储资源消耗,从而支持大容量的模式集。 相似文献
7.
A common problem of XML query algorithms is that execution time and input size grows rapidly as the size of XML document increases. In this paper, we propose a version-labeling scheme and TwigVersion algorithm to address this problem. The version-labeling scheme is utilized to identify all repetitive structures in XML documents, and the Version Tree is constructed to hold such version information. To process a query, TwigVersion generates a filter through the created Version Tree, and the final answer to the query can be retrieved from the database easily through the filtering process. Both theoretical proof and experimental results reported in this paper demonstrate that the concise structure of Version Tree and the reduced input size make TwigVersion outperform the existing approaches. 相似文献
8.
9.
点模式匹配的概率图模型具有很好的匹配精度,但是计算复杂度较高,当隔离子中包含异常点(outlier)时匹配精度会受到较大的影响。为了提高匹配的速度和精度,提出了一种由粗到精的图模型点模式匹配算法。利用包含特征点的窗口,用标准化互相关方法对特征点进行粗匹配,以减少异常点的数量,提高后续匹配方法的速度和精度。提出了一种新的点模式匹配的概率图模型,这种图模型能综合利用特征点的位置信息和包含特征点的邻域的灰度信息。利用提出的概率图匹配方法对粗匹配所得到的点对进行分段匹配,得到精确的匹配结果。对光学图像和遥感图像的匹配实验显示该方法能显著减少点模式匹配时间,提高匹配的精度。 相似文献
10.
A novel scheme used for controlling access requests in security information system is proposed. In the proposed method, the system administrator chooses distinct prime numbers representing each atomic access right as well as four large prime numbers for encryption. By setting these representative prime numbers as input parameters, the proposed method applies a one-way function combining the Morton number theory transferring into a single value to derive the encrypted compound privilege (ECP). With ECP, verification of right of access can be achieved easily and secretly. Meanwhile, the proposed scheme provides the following advantages: (1) the verification of right of access can be effectively implemented using the Morton sequence with coordinate transformation; (2) the problem of dynamic access control also can be effectively implemented; (3) integrity and confidentiality while controlling system resources can be ensured; (4) the proposed method can decrease the redundancy of the access matrix in some specific circumstances. 相似文献
11.
S.K. Mukhopadhyay S. Mitra M. MitraAuthor vitae 《Computers & Electrical Engineering》2011,37(4):486-497
A software based lossless ECG compression algorithm is developed here. The algorithm is written in the C-platform. The algorithm has applied to various ECG data of all the 12 leads taken from PTB diagnostic ECG database (PTB-DB). Here, a difference array has been generated from the corresponding input ECG data and this is multiplied by a large number to convert the number of arrays into integers. Then those integers are grouped in both forward and reverse direction, out of which few are treated differently. Grouping has been done in such a way that every grouped number resides under valid ASCII value. Then all the grouped numbers along with sign bit and other necessary information are converted into their corresponding ASCII characters. The reconstruction algorithm has also been developed in using the reversed logic and it has been observed that data is reconstructed with almost negligible difference as compared with the original (PRD 0.023%). 相似文献
12.
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. 相似文献
13.
Pele O Werman M 《IEEE transactions on pattern analysis and machine intelligence》2008,30(8):1427-1443
This paper describes a method for robust real time pattern matching. We first introduce a family of image distance measures, the "Image Hamming Distance Family". Members of this family are robust to occlusion, small geometrical transforms, light changes and non-rigid deformations. We then present a novel Bayesian framework for sequential hypothesis testing on finite populations. Based on this framework, we design an optimal rejection/acceptance sampling algorithm. This algorithm quickly determines whether two images are similar with respect to a member of the Image Hamming Distance Family. We also present a fast framework that designs a near-optimal sampling algorithm. Extensive experimental results show that the sequential sampling algorithm performance is excellent. Implemented on a Pentium 4 3 GHz processor, detection of a pattern with 2197 pixels, in 640 x 480 pixel frames, where in each frame the pattern rotated and was highly occluded, proceeds at only 0.022 seconds per frame. 相似文献
14.
Kwok-Wai Cheung Dit-Yan Yeung Chin R.T. 《IEEE transactions on pattern analysis and machine intelligence》2002,24(8):1133-1139
To achieve integrated segmentation and recognition in complex scenes, the model-based approach has widely been accepted as a promising paradigm. However, the performance is still far from satisfactory when the target object is highly deformed and the level of outlier contamination is high. In this paper, we first describe two Bayesian frameworks, one for classifying input patterns and another for detecting target patterns in complex scenes using deformable models. Then, we show that the two frameworks are similar to the forward-reverse setting of Hausdorff matching and that their matching and discriminating properties are complementary to each other. By properly combining the two frameworks, we propose a new matching scheme called bidirectional matching. This combined approach inherits the advantages of the two Bayesian frameworks. In particular, we have obtained encouraging empirical results on shape-based pattern extraction, using a subset of the CEDAR handwriting database containing handwritten words of highly varying shape. 相似文献
15.
随着语义网络中数据量的激增,在RDF数据集中高效查询数据已成为一个亟待解决的问题。传统的基于物化视图的RDF模式匹配方法虽然能降低表的自连接操作次数,加快查询模式重写过程,但在视图集中检索模式匹配的视图等价于子图同构这一NP-hard问题。为了减小查询模式重写代价,提高RDF模式匹配过程效率,引入可排序视图概念,设计包含映射发现算法contain及其扩展算法contain+,简化等长度模式间包含映射发现过程,同时保证模式间的匹配代价与输入数据的规模线性相关。此外,提出基于倒排表/MapReduce检索候选可排序视图的方法,实现RDF模式重写算法rewrite,用以处理不同规模数据集上的模式匹配问题。理论分析及实验证明,基于可排序视图的RDF模式匹配算法能有效地兼顾算法效率及算法可扩展性。 相似文献
16.
17.
Program understanding can be assisted by tools that match patterns in the program source. Lexical pattern matchers provide excellent performance and ease of use, but have a limited vocabulary. Syntactic matchers provide more precision, but may sacrifice performance, robustness, or power. To achieve more of the benefits of both models, we extend the pattern syntax of AWK to support matching of abstract syntax trees, as demonstrated in a tool called TAWK. Its pattern syntax is language‐independent, based on abstract tree patterns. As in AWK, patterns can have associated actions, which in TAWK are written in C for generality, familiarity, and performance. The use of C is simplified by high‐level libraries and dynamic linking. To allow processing of program files containing non‐syntactic constructs such as textual macros, mechanisms have been designed that allow matching of ‘language‐like’ macros in a syntactic fashion. We survey and apply prototypical approaches to concretely demonstrate the tradeoffs in program processing. Our results indicate that TAWK can be used to quickly and easily perform a variety of common software engineering tasks, and the extensions to accommodate non‐syntactic features significantly extend the generality of syntactic matchers. Copyright © 2005 John Wiley & Sons, Ltd. 相似文献
18.
《Information Processing Letters》2014,114(12):700-702
Cayley graphs of finite cyclic group are called circulant graphs and denoted by . For with prime, we give a necessary and sufficient condition for the existence of efficient dominating sets and characterize completely all its efficient dominating sets. 相似文献
19.
The number of spanning trees of a graph G is the total number of distinct spanning subgraphs of G that are trees. In this paper, we present sharp upper bounds for the number of spanning trees of a graph with given matching number. 相似文献
20.
Glatter M Huang J Ahern S Daniel J Lu A 《IEEE transactions on visualization and computer graphics》2008,14(6):1467-1474
Extracting and visualizing temporal patterns in large scientific data is an open problem in visualization research. First, there are few proven methods to flexibly and concisely define general temporal patterns for visualization. Second, with large time-dependent data sets, as typical with today's large-scale simulations, scalable and general solutions for handling the data are still not widely available. In this work, we have developed a textual pattern matching approach for specifying and identifying general temporal patterns. Besides defining the formalism of the language, we also provide a working implementation with sufficient efficiency and scalability to handle large data sets. Using recent large-scale simulation data from multiple application domains, we demonstrate that our visualization approach is one of the first to empower a concept driven exploration of large-scale time-varying multivariate data. 相似文献