Inplace 2D matching in compressed images

The compressed matching problem is the problem of finding all occurrences of a pattern in a compressed text. In this paper we discuss the 2-dimensional compressed matching problem in Lempel–Ziv compressed images. Given a pattern P of (uncompressed) size m×m, and a text T of (uncompressed) size n×n, both in 2D-LZ compressed form, our algorithm finds all occurrences of P in T. The algorithm is strongly inplace, that is, the amount of extra space used is proportional to the best possible compression of a pattern of size m². The best compression that the 2D-LZ technique can obtain for a file of size m² is O(m). The time for performing the search is O(n²) and the preprocessing time is O(m³). Our algorithm is general in the sense that it can be used for any 2D compression which can be sequentially decompressed in small space.     

Solving a k-Node Minimum Label Spanning Arborescence Problem to Compress Fingerprint Templates

We present a novel approach for compressing relatively small unordered data sets by means of combinatorial optimization. The application background comes from the field of biometrics, where the embedding of fingerprint template data into images by means of watermarking techniques requires extraordinary compression techniques. The approach is based on the construction of a directed tree, covering a sufficient subset of the data points. The arcs are stored via referencing a dictionary, which contains “typical” arcs w.r.t. the particular tree solution. By solving a tree-based combinatorial optimization problem we are able to find a compact representation of the input data. As optimization method we use on the one hand an exact branch-and-cut approach, and on the other hand heuristics including a greedy randomized adaptive search procedure (GRASP) and a memetic algorithm. Experimental results show that our method is able to achieve higher compression rates for fingerprint (minutiae) data than several standard compression algorithms.     

Maximality of compression semigroups

LetG be a connected semisimple Lie group andr an involution onG. Further letL be an open subgroup of the groupG ^r ofr-fixed points andP⊂-G a parabolic subgroup. The semigroupS(L,P)∶={g∈G∶gLP⊂-LP} is called the compression semigroup of theL-orbit of the base point in the flag manifoldG/P. We show that compression semigroups for open orbits and regular symmetric pairs are maximal semigroups. Supported by a DFG Heisenberg-grant.     

Bounding the Compression Loss of the FGK Algorithm

An important issue related to coding schemes is their compression loss. A simple measure ε of the compression loss due to a coding scheme different than Huffman coding is defined by ε = A_C − A_H where A_H is the average code length of a static Huffman encoding and A_C is the average code length of an encoding based on the compression scheme C. When the scheme C is the FGK algorithm, Vitter conjectured that ε ≤ K for some real constant K. Here, we use an amortized analysis to prove this conjecture. We show that ε < 2. Furthermore, we show through an example that our bound is asymptotically tight. This result explains the good performance of FGK that many authors have observed through practical experiments.     

Multifilters with and without Prefilters

To explore the full approximation order and thus compression power of a multifilter, it is usually necessary to incorporate prefilters. Using matrix factorization techniques, we describe an explicit construction of such prefilters. Although in the case of approximation order 1 these prefilters are simply bi-infinite block diagonal matrices, they can become very intricate as soon as one aims for higher approximation order. For this reason, we introduce a particular class of multifilters which we call full rank multifilters. These filters have a peculiar structure which allows us to obtain approximation order without the use of prefilters. The construction of such filters via the lifting scheme is pointed out and examples of the performance of these filters for image compression are given.     

Positive Solutions of Nonlinear Systems with <Emphasis Type="Italic">p</Emphasis>-Laplacian on Finite and Semi-infinite Intervals

Existence and localization results are established for systems of second-order differential equations with p -Laplacian on finite and semi-infinite intervals. For a compact interval, the compression and expansion conditions that are used are related to the first eigenvalue of the p-Laplacian.     

Digital signal processing using Schauder functions

We demonstrate the applicability of a complete nonorthogonal system of Schauder functions to digital signal processing and signal compression. The digital signal processing algorithm is demonstrated in application to the compression of electrocardiogram signals.Translated from Vychislitel'naya i Prikladnaya Matematika, No. 72, pp. 75–77, 1990.     

The Compression Property for Affine Variational Inequalities

In 1965, Gale and Nikaidô showed that for any n × n P-matrix A, the only nonnegative vector that A sends into a nonpositive vector is the origin. They applied that result to derive various results including univalence properties of certain nonlinear functions. In this article, we show that an extension of their result holds with the nonnegative orthant replaced by any nonempty polyhedral convex cone. In place of the P-matrix condition, we require a determinantal condition that we call the compression property. When the polyhedral convex cone is the nonnegative orthant, the compression property reduces to the property of being a P-matrix and we recover the Gale-Nikaidô result. We apply the extended theorem to derive tools useful in the analysis of affine variational inequalities over polyhedral convex cones.     

Fuzzy Relation Equations for Compression/Decompression Processes of Colour Images in the RGB and YUV Colour Spaces

We use particular fuzzy relation equations for compression/decompression of colour images in the RGB and YUV spaces, by comparing the results of the reconstructed images obtained in both cases. Our tests are made over well known images of 256×256 pixels (8 bits per pixel in each band) extracted from Corel Gallery. After the decomposition of each image in the three bands of the RGB and YUV colour spaces, the compression is performed using fuzzy relation equations of “min - →_t” type, where “t” is the Lukasiewicz t-norm and “→_t” is its residuum. Any image is subdivided in blocks and each block is compressed by optimizing a parameter inserted in the Gaussian membership functions of the fuzzy sets, used as coders in the fuzzy equations. The decompression process is realized via a fuzzy relation equation of max-t type. In both RGB and YUV spaces we evaluate and compare the root means square error (RMSE) and the consequentpeak signal to noise ratio (PSNR) on the decompressed images with respect to the original image under several compression rates.     

Biorthogonal wavelet approximation for the coupling of FEM-BEM

Summary. We apply multiscale methods to the coupling of finite and boundary element methods to solve an exterior Dirichlet boundary value problem for the two dimensional Poisson equation. Adopting biorthogonal wavelet matrix compression to the boundary terms with N degrees of freedom, we show that the resulting compression strategy fits the optimal convergence rate of the coupling Galerkin methods, while the number of nonzero entries in the corresponding stiffness matrices is considerably smaller than . Received December 3, 1999 / Revised version received September 22, 2000 / Published online December 18, 2001     

Approximation of dense-<Emphasis Type="Italic">n</Emphasis>/2-subgraph and table compression problems-subgraph and table compression problems

We develop improved approximation algorithms for two NP-hard problems: the dense-n/2-subgraph and table compression. Based on SDP relaxation and advanced rounding techniques, we first propose 0.5982 and 0.5970-approximation algorithms respectively for the dense-2-subgraph problem (DSP) and the table compression problem (TCP). Then we improve these bounds to 0.6243 and 0.6708 respectively for DSP and TCP by adding triangle inequalities to strengthen the SDP relaxation. The results for TCP beat the 0.5 bound of a simple greedy algorithm on this problem, and hence answer an open question of Anderson in an affirmative way.     

Compression and denoising using <Emphasis Type="Italic">l</Emphasis><Subscript>0</Subscript>-norm

In this paper, we deal with l ₀-norm data fitting and total variation regularization for image compression and denoising. The l ₀-norm data fitting is used for measuring the number of non-zero wavelet coefficients to be employed to represent an image. The regularization term given by the total variation is to recover image edges. Due to intensive numerical computation of using l ₀-norm, it is usually approximated by other functions such as the l ₁-norm in many image processing applications. The main goal of this paper is to develop a fast and effective algorithm to solve the l ₀-norm data fitting and total variation minimization problem. Our idea is to apply an alternating minimization technique to solve this problem, and employ a graph-cuts algorithm to solve the subproblem related to the total variation minimization. Numerical examples in image compression and denoising are given to demonstrate the effectiveness of the proposed algorithm.     

Optimal Two-Dimensional Compressed Matching

Recent proliferation of digitized data and the unprecedented growth in the volume of stored and transmitted data motivated the definition of the compressed matching paradigm. This is the problem of efficiently finding a patternPin a compressed textTwithout the need to decompress. We present the firstoptimaltwo-dimensional compressed matching algorithm. The compression under consideration is the two dimensional run-length compression, used by FAX transmission. We achieve optimal time by proving new properties of two-dimensional periodicity. This enables performing duels in which no witness is required. At the heart of the dueling idea lies the concept that two overlapping occurrences of a pattern in a text can use the content of apredetermined text positionorwitnessin the overlap to eliminate one of them. Finding witnesses is a costly operation in a compressed text, thus the importance of witness-free dueling.     

On the Positive Solutions of a Nonlinear Fourth-order Boundary Value Problem with Two Parameters

The existence of m positive solutions is proven for a nonlinear fourth-order boundary value problem with two parameters, where m is an arbitrary natural number. This kind of fourth-order boundary value problems usually describes the equilibrium state of elastic beam where both ends are simply supported. The main ingredient is Krasnosel'skii fixed point theorem of cone expansion–compression type.     

A novel constitutive law for Silicon under contact loading

Silicon (Si) remains the most important semiconductor material to date. The understanding of its deformation behavior under contact (indenter-) loading is crucial to improving technologically relevant abrasive machining techniques (lapping, sawing, grinding). While it has been long established that Si undergoes a series of stress driven phase transitions upon compression and subsequent pressure release, to the authors' knowledge, no material model is available that adequately captures this behavior. In particular, reverse transformation in unloading has received too little attention. A novel phenomenological, thermomechanical model based on experimental observations and MD predictions is presented in this work. It captures both the cd-Si → β-Si transition upon compression and the β-Si → a-Si transition upon rapid decompression, which are most relevant for indenter loading. To control inelasticity in unloading, the dissipation function was augmented by a kinematic constraint on the tensorial internal variable. In stress space, the transformation surfaces are hyperboloids of revolution aligned along the hydrostatic axis. The non-linear model was numerically implemented in a finite element code using an iterative implicit algorithm and successfully applied to simple loading cases. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Determination of the thermal stresses in anisotropic shells of revolution

Using the relations of the improved model of layered anisotropic shells based on the straight line assumption taking account of the thermal compression over the thickness we obtain a resolvent system of equations for shells whose properties depend on temperature. We carry out a study of the stresses in a two-layer cylindrical shell formed by winding as a function of the winding angle. Translated fromMatematicheskie Metody i Fiziko-Mekhanicheskie Polya, Issue 35, 1992, pp. 82–85.     

Compact directed acyclic word graphs for a sliding window

Suffix trees are a well-known and widely-studied data structure highly useful for string matching. The suffix tree of a string w can be constructed in O(n) time and space, where n denotes the length of w. Larsson achieved an efficient algorithm to maintain suffix trees for a sliding window. It contributes to prediction by partial matching (PPM) style statistical data compression scheme. Compact directed acyclic word graphs (CDAWGs) are a more space-economical data structure for indexing strings. In this paper we propose a linear-time algorithm to maintain CDAWGs for a sliding window.     

Interpolatory Wavelet Packets

In this note, we present a construction of interpolatory wavelet packets. Interpolatory wavelet packets provide a finer decomposition of the 2^jth dilate cardinal interpolation space and hence give a better localization for an adaptive interpolation. This can lead to a more efficient compression scheme which, in turn, provides an interpolation algorithm with a smaller set of data for use in applications.     

Operator theory in the Hardy space over the bidisk (I)

In this paper, we identify the vector valued Hardy space with the Hardy space over the bidisk and construct a universal model for thecontractive analytic functions. We will also study some elementary properties of the submodules and show, in some cases, how the operator theoretical properties are related to the module theoretical properties. The last part focus on the study of double commutativity of compression operators.