Faster two-dimensional pattern matching with rotations

The most efficient currently known algorithms for two-dimensional pattern matching with rotations have a worst case time complexity of O(n²m³)$\mathrm{O}(n^2{m}^3)$, where the size of the text is n×n$n\times n$ and the size of the pattern is m×m$m\times m$. In this paper we present a new algorithm for the problem whose running time is O(n²m²)$\mathrm{O}(n^2{m}^2)$.     

Efficient two-dimensional pattern matching in the presence of errors

We give an algorithm for two-dimensional pattern matching in the presence of errors. We find that the complexity of our algorithm is O(kn₁n₂ log n₂ + n₁²n₂ + kn₁m₁m₂), where the pattern is an n₁ × n₂ array, the text is an m₁ × m₂ array and k is the number of mismatches allowed.     

Point pattern matching by relaxation

Let $\text{P}\text{= P}{}_1\text{, …, P}{}_{\mathrm{m}}$ and $\text{Q}\text{= Q}{}_1\text{, …, Q}{}_{\mathrm{n}}$ be two patterns of points. Each pairing (P_i, Q_j) of a point of $\text{P}$ with a point of $\text{Q}$ defines a relative displacement δ_ij of the two patterns. We can define a figure of merit for δ_ij according to how closely other point pairs coincide under δ_ij. If there exists a displacement δ₀ for which $\text{P}$ and $\text{Q}$ match reasonably well, the pairings for which δ_ij ? δ₀ will have high merit scores, while other pairings will not. The scores can then be recomputed, giving weights to the other point pairs based on their own scores; and this process can be iterated. When this is done, the scores of pairs that correspond under δ₀ remain relatively high, while those of other pairs become low. Examples of this method of point pattern matching are given, and its possible advantages relative to other methods are discussed.     

A note on pattern reproduction in tessellation structures

Tessellation structures that reproduce arbitrary patterns are special cases of tessellation structures having local transformations that are linear operators. We introduce a novel formulation of tessellation structures which emphasizes the connection between these structures and concepts of functional analysis. Using this formulation a behavioral analysis technique is developed which implies the earlier results on pattern reproduction and generalizes them to tessellation structures whose state alphabets are arbitrary fields of non-zero characteristic and whose tessellation arrays are arbitrary countable abelian groups. It is also shown that a local transformation can be chosen to produce at a specified time any desired set of “copies” of an initial pattern each multiplied by a specified scalar. We then indicate that connections exist between linear tessellation structures and linear partial differential equations which describe wave propagation by giving an example of a classical form of pattern reproduction.     

Outsourced pattern matching

In secure delegatable computation, computationally weak devices (or clients) wish to outsource their computation and data to an untrusted server in the cloud. While most earlier work considers the general question of how to securely outsource any computation to the cloud server, we focus on concrete and important functionalities and give the first protocol for the pattern matching problem in the cloud. Loosely speaking, this problem considers a text T that is outsourced to the cloud \({\textsc {S}}\) by a sender \({\textsc {SEN}}\). In a query phase, receivers \({\textsc {REC}}_1, \ldots , {\textsc {REC}}_l\) run an efficient protocol with the server \({\textsc {S}}\) and the sender \({\textsc {SEN}}\) in order to learn the positions at which a pattern of length m matches the text (and nothing beyond that). This is called the outsourced pattern matching problem which is highly motivated in the context of delegatable computing since it offers storage alternatives for massive databases that contain confidential data (e.g., health-related data about patient history). Our constructions are simulation-based secure in the presence of semi-honest and malicious adversaries (in the random oracle model) and limit the communication in the query phase to O(m) bits plus the number of occurrences—which is optimal. In contrast to generic solutions for delegatable computation, our schemes do not rely on fully homomorphic encryption but instead use novel ideas for solving pattern matching, based on a reduction to the subset sum problem. Interestingly, we do not rely on the hardness of the problem, but rather we exploit instances that are solvable in polynomial time. A follow-up result demonstrates that the random oracle is essential in order to meet our communication bound.     

Practical pattern matching

Humans are fascinated by patterns, and they can spot them well - in fact, that's one area where humans excel over computers. But research is producing interesting competition as scientists discover and employ new methods of automated pattern recognition. Practical applications include finding genes, detecting cancer-causing chemicals in molecules, searching out potential terrorists, and predicting terrorist threat levels, as well as recognizing speech patterns and creating a nanotechnology resource library.     

Labeled point pattern matching by fuzzy relaxation

A method of matching labeled point patterns is described on the basis of a fuzzy relaxation. The method is applicable to labeled point patterns which differ by geometrical transformations, such as translation, rotation and scale change. In this method, the point pairs are considered to be the pattern primitives. The pattern primitives are geometrically transformed in the process of relaxation so as to minimize a measure of mismatch between the primitive pairs. The compatible primitive pairs between the two labeled point patterns are established after only a few iterations of relaxation and the corresponding points are obtained from the primitive pairs. As an example, the method is applied to the matching of constellations.     

Refactoring pattern matching

Defining functions by pattern matching over the arguments is advantageous for understanding and reasoning, but it tends to expose the implementation of a datatype. Significant effort has been invested in tackling this loss of modularity; however, decoupling patterns from concrete representations while maintaining soundness of reasoning has been a challenge. Inspired by the development of invertible programming, we propose an approach to program refactoring based on a right-invertible language rinv—every function has a right (or pre-) inverse. We show how this new design is able to permit a smooth incremental transition from programs with algebraic datatypes and pattern matching, to ones with proper encapsulation, while maintaining simple and sound reasoning.     

Two-dimensional object recognition by matching local properties of contour points

This paper describes a two-stage Hough procedure for two-dimensional object recognition based on matching local properties of a model set of contour points. The procedure makes use of three strategies: subdivision of the parameter space, classification by multiple properties, and non-maximum suppression. The first stage estimates likely values in a coarsely quantized space of position and orientation. The second stage verifies these estimates in a more precise space with a large set of model points. In both cases, matching of model points to image contour points is based on tangent, curvature and contrast. The evaluation of the parameter space is greatly simplified by simultaneous non-maximum suppression over neighborhoods of both parameters. Experiments show that these strategies are both efficient and robust, even in the case of complex and partial data. One example uses overlapping parts, such as might occur in industrial situations.     

Shape matching of two-dimensional objects

In this paper we present results in the areas of shape matching of nonoccluded and occluded two-dimensional objects. Shape matching is viewed as a ``segment matching' problem. Unlike the previous work, the technique is based on a stochastic labeling procedure which explicitly maximizes a criterion function based on the ambiguity and inconsistency of classification. To reduce the computation time, the technique is hierarchical and uses results obtained at low levels to speed up and improve the accuracy of results at higher levels. This basic technique has been extended to the situation where various objects partially occlude each other to form an apparent object and our interest is to find all the objects participating in the occlusion. In such a case several hierarchical processes are executed in parallel for every object participating in the occlusion and are coordinated in such a way that the same segment of the apparent object is not matched to the segments of different actual objects. These techniques have been applied to two-dimensional simple closed curves represented by polygons and the power of the techniques is demonstrated by the examples taken from synthetic, aerial, industrial and biological images where the matching is done after using the actual segmentation methods.     

Algorithms for pattern matching

This paper describes four algorithms of varying complexity used for pattern matching, and investigates their behaviour. The algorithms are tested using patterns of varying length from several alphabets. It is concluded that although there is no overall ‘best’ algorithm, the more complex algorithms are worth considering as they are generally more efficient in terms of number of comparisons made and execution time.     

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.     

Two-dimensional on-line bin packing problem with rotatable items

In this paper, we consider a two-dimensional version of the on-line bin packing problem, in which each rectangular item that should be packed into unit square bins is “rotatable” by $\text{90°}$. Two on-line algorithms for solving the problem are proposed. The second algorithm is an extension of the first algorithm, and the worst-case ratio of the second one is at least 2.25 and at most 2.565.     

Lower bounds for on-line two-dimensional packing algorithms

Summary Many problems, such as cutting stock problems and the scheduling of tasks with a shared resource, can be viewed as two-dimensional bin packing problems. Using the two-dimensional packing model of Baker, Coffman, and Rivest, a finite list L of rectangles is to be packed into a rectangular bin of finite width but infinite height, so as to minimize the total height used. An algorithm which packs the list in the order given without looking ahead or moving pieces already packed is called an on-line algorithm. Since the problem of finding an optimal packing is NP-hard, previous work has been directed at finding approximation algorithms. Most of the approximation algorithms which have been studied are on-line except that they require the list to have been previously sorted by height or width. This paper examines lower bounds for the worst-case performance of on-line algorithms for both non-preordered lists and for lists preordered by increasing or decreasing height or width.This author's work was supported by the Joint Services Electronics Program (U.S. Army, U.S. Navy and U.S. Air Force) under Contract DAAG-29-78-C-0016     

Approximate pattern matching in a pattern database system

This work is concerned with the organization of a large database of binary pictures (normalized for size, rotation and position) and with the efficient “inexact match” of an input pattern against the whole database. Current techniques in pattern analysis use matching algorithms without any regard to the global organization of the storage representations of the models they are to match. Consequently, the algorithms are only practical for small databases. This paper discusses the design of a pattern database system and the economy that it provides for the matching problem. The database organization is based on the quad-tree representation of binary patterns. Given an arbitrary decomposition D (or partition) of a pattern P and an arbitrary function f on the pattern, we repeatedly apply f on D(P), D(D(P))P, … to obtain higher and higher levels of abstraction f(D)(P)), f(D(D(P))), … of the pattern. The computed values obtained after the jth application of f are used to label the ith level of the pyramid. The specific representation used in this paper is called the sum-quad-tree, in which each level of the tree stores the sum of the labels of its sons. The lowest level of the sum-quad-tree corresponds to the individual pixels and is the nth level (i.e. node m at level n implies v(m) = 0 or v(m) = 1). Nodes at the jth level of the sum-quad-tree correspond to sums of 2^n?j × 2^n?j picture points, so that the 0th level contains the number of 1's in the pattern. The pyramid representation is used as a hierarchical (n-level) indexing scheme of the database. The advantage of this organization is that the matching algorithms presented reject most of the patterns in the database by utilizing the relatively small in size index tables and thus avoid the overhead of unnecessary CPU time and $\text{I}\text{O}$ operation between main memory and secondary storage.