Search

Objective In cardiac patient-care, compression of long-term ECG data is essential to minimize the data storage requirement and transmission cost. Hence, this paper presents a novel electrocardiogram data compression technique which utilizes modified run-length encoding of wavelet coefficients. Method First, wavelet transform is applied to the ECG data which decomposes it and packs maximum energy to less number of transform coefficients. The wavelet transform coefficients are quantized using dead-zone quantization. It discards small valued coefficients lying in the dead-zone interval while other coefficients are kept at the formulated quantized output interval. Among all the quantized coefficients, an average value is assigned to those coefficients for which energy packing efficiency is less than 99.99%. The obtained coefficients are encoded using modified run-length coding. It offers higher compression ratio than conventional run-length coding without any loss of information. Results Compression performance of the proposed technique is evaluated using different ECG records taken from the MIT-BIH arrhythmia database. The average compression performance in terms of compression ratio, percent root mean square difference, normalized percent mean square difference, and signal to noise ratio are 17.18, 3.92, 6.36, and 28.27 dB respectively for 48 ECG records. Conclusion The compression results obtained by the proposed technique is better than techniques recently introduced by others. The proposed technique can be utilized for compression of ECG records of Holter monitoring.

Data compression is of great significance to the storage of power dispatch data. The compressed data not only saves a lot of space, but also improves the speed of data retrieval. Therefore, this paper proposes an improved algorithm based on run length encoding to compress power dispatch data. In the case of high data similarity, run length coding and dictionary coding have good compression effects, so this article classifies power dispatch data, and uses an improved run length coding algorithm to compress data with high similarity. For similarity Low data is compressed using the Lz4 algorithm that comes with HBase, and a Base-128 Varints encoding the number of occurrences of elements in the run-length encoding is proposed to further improve the compression rate of similar data. This improved algorithm is proven in experiments In some scenarios, the compression rate is indeed improved.

Genomics and bioinformatics have grown as an independent field and are an area of active research currently. In this work, we first discuss the idea of the genome, its importance and wide-ranging applications in healthcare and medicine. We then give a brief overview of the various file formats used presently to store and manipulate genomic data along with their benefits and shortcomings. Moving on, we analyze and elaborate on how parallel and distributed computing can help in processing large files with genomic data and more importantly address the problem of pattern matching. In particular, we introduce the raspberry-pi and discuss in detail how a Raspberry Pi can accomplish the pattern matching task and how a Raspberry-Pi cluster can enable parallel computing to improvise the performance. This work also includes a brief account of various high-level application programming interfaces and libraries that can be used to parse genomic data like BioPython and Fuzzywuzzy. We conclude this work by summarizing some techniques that can be used for encoding and compressing files with genomic data like Run-Length encoding and genome differential compression respectively among other methods. The proposed work improvises the Genome pattern matching time by more than 50% in a distributed Raspberry Pi Computing environment. This system is useful to detect a particular genome-based abnormality where different pieces of Genome records are present on the different nodes in distributed computing and the input is given to find the disease. It can detect the abnormality within a short time. Also the different approach used here is to use Raspberry Pi based clustering to save cost and the energy.

Data has become an integral part of today’s life. Traditional relational databases are row oriented databases designed for row wise data storage and retrieval which consumes more time to return queries. Recently, Columnar databases have dominated traditional databases due to their effective read operations to and from hard disk to decrease the interval to return queries. Columnar databases are mainly designed for data warehouses where huge amount of data collected from several sources are needed to perform Business Intelligence to build decision making systems. Columnar databases have quicker query performance because the data is packed close together which decreases seek time. They support various compression techniques for quicker data access with the help of aggregation queries to filter the irrelevant data. This paper discusses about various compression techniques such as NULL Suppression, Dictionary Encoding, Run Length Encoding, Bit Vector Encoding and Lempel Ziv Encoding which are being popularly used to optimise the performance of the columnar databases. Database operations are performed on the compressed data to prove the reduction in the requirements of memory and enhancements in the performance.

We propose a binary image encryption method in joint transform correlator (JTC) by aid of the run-length encoding (RLE) and Quick Response (QR) code, which enables lossless retrieval of the primary image. The binary image is encoded with RLE to obtain the highly compressed data, and then the compressed binary image is further scrambled using a chaos-based method. The compressed and scrambled binary image is then transformed into one QR code that will be finally encrypted in JTC. The proposed method successfully, for the first time to our best knowledge, encodes a binary image into a QR code with the identical size of it, and therefore may probe a new way for extending the application of QR code in optical security. Moreover, the preprocessing operations, including RLE, chaos scrambling and the QR code translation, append an additional security level on JTC. We present digital results that confirm our approach.

In this paper, a one-dimensional complex Discrete Anamorphic Stretch Transform (DAST) is proposed for precompression of the ECG signal. Three 1D kernels (Linear, Sublinear, and Superlinear) and a two-tap phase recovery filter are proposed for efficient computation of 1D DAST and inverse DAST. Wavelet transform and Run Length Encoding (RLE) are used as secondary compression schemes. To evaluate the efficacy of this approach, the bandwidth compression (BWC) obtained using the three kernels, and the Percentage root mean square difference (PRD) between the original ECG and reconstructed signal using inverse DAST are computed for the ECG records in the MIT-BIH database. From this, it is found that the BWC factor varies from (1.37–10.6) and it is dependent on the ECG record and the type of kernel and kernel size. The performance of the ECG compression using DAST, Wavelet Transform, and RLE is evaluated next using all the MIT-BIH ECG records for different kernels, kernel sizes, different levels of Wavelet decomposition and various Energy Packing Efficiency. From this study, it is found that the maximum factor by which the average Compression Ratio increases is 3.25, and this is obtained for DAST with Sublinear kernel and 3 level DWT for EPE of 99.9%. The proposed compression scheme combining both DAST and DWT is also found to have a better Compression Ratio and PRD compared to those reported in the literature. DAST is well suited for the precompression of the ECG signal for real-time transmission using channels with limited bandwidth.

Reservoir modeling is a very important task that permits the representation of a geological region of interest, so as to generate a considerable number of possible scenarios. Since its inception, many methodologies have been proposed and, in the last two decades, multiple-point geostatistics (MPS) has been the dominant one. This methodology is strongly based on the concept of training image (TI) and the use of its characteristics, which are called patterns. In this paper, we propose a new MPS method that combines the application of a technique called Locality Sensitive Hashing (LSH), which permits to accelerate the search for patterns similar to a target one, with a Run-Length Encoding (RLE) compression technique that speeds up the calculation of the Hamming similarity. Experiments with both categorical and continuous images show that LSHSIM is computationally efficient and produce good quality realizations. In particular, for categorical data, the results suggest that LSHSIM is faster than MS-CCSIM, one of the state-of-the-art methods.

It is difficult to carry out visualization of the large-scale time-varying data directly, even with the supercomputers. Data compression and ROI (Region of Interest) detection are often used to improve efficiency of the visualization of numerical data. It is well known that the Run Length encoding is a good technique to compress the data where the same sequence appeared repeatedly, such as an image with little change, or a set of smooth fluid data. Another advantage of Run Length encoding is that it can be applied to every dimension of data separately. Therefore, the Run Length method can be implemented easily as a parallel processing algorithm. We proposed two different Run Length based methods. When using the Run Length method to compress a data set, its size may increase after the compression if the data does not contain many repeated parts. We only apply the compression for the case that the data can be compressed effectively. By checking the compression ratio, we can detect ROI. The effectiveness and efficiency of the proposed methods are demonstrated through comparing with several existing compression methods using different sets of fluid data.

The border and parameterized border (p-border) arrays are data structures used in pattern matching applications for traditional strings from the constant alphabet @S, and parameterized strings (p-strings) from the constant alphabet @S and the parameter alphabet @P. In this work, we introduce the structural border array (s-border) as defined for an n-length structural string (s-string) T. The s-string is a p-string with the existence of symbol complements in some alphabet @C. These different alphabets add to both the intricacies and capabilities of pattern matching. For example, the s-string can handle the Watson-Crick base pairings in biological sequences and thus, assists in applications that deal with efficient pattern matching between RNA strands that share similar secondary structures. Initially, we provide a construction that executes in O(n^2) time to build the s-border array. The paper establishes theory to improve the result to O(n) by proving particular properties of the s-border data structure. This result is significant because of the generalization of the s-string, which is a step beyond the p-string. Using the same construction algorithm, we show how to modify the s-string alphabets to also construct the p-border and the traditional border arrays in linear time. The generality of the s-border construction algorithm motivates us to devise pattern matching algorithms for s-matching, p-matching, and traditional matching. Our pattern matching algorithms are ultimately used to address the p-match problem with run-length encoded strings.

The Binary Jumbled String Matching problem is defined as: Given a string $s$ over $\{a,b\}$ of length $n$ and a query $(x,y)$, with $x,y$ non-negative integers, decide whether $s$ has a substring $t$ with exactly $x$ $a$'s and $y$ $b$'s. Previous solutions created an index of size O(n) in a pre-processing step, which was then used to answer queries in constant time. The fastest algorithms for construction of this index have running time $O(n^2/\log n)$ [Burcsi et al., FUN 2010; Moosa and Rahman, IPL 2010], or $O(n^2/\log^2 n)$ in the word-RAM model [Moosa and Rahman, JDA 2012]. We propose an index constructed directly from the run-length encoding of $s$. The construction time of our index is $O(n+\rho^2\log \rho)$, where O(n) is the time for computing the run-length encoding of $s$ and $\rho$ is the length of this encoding---this is no worse than previous solutions if $\rho = O(n/\log n)$ and better if $\rho = o(n/\log n)$. Our index $L$ can be queried in $O(\log \rho)$ time. While $|L|= O(\min(n, \rho^{2}))$ in the worst case, preliminary investigations have indicated that $|L|$ may often be close to $\rho$. Furthermore, the algorithm for constructing the index is conceptually simple and easy to implement. In an attempt to shed light on the structure and size of our index, we characterize it in terms of the prefix normal forms of $s$ introduced in [Fici and Lipt\'ak, DLT 2011]., Comment: v2: only small cosmetic changes; v3: new title, weakened conjectures on size of Corner Index (we no longer conjecture it to be always linear in size of RLE); removed experimental part on random strings (these are valid but limited in their predictive power w.r.t. general strings); v3 published in IPL

Given a pattern P and a text T, both strings over a binary alphabet, the binary jumbled string matching problem consists in telling whether any permutation of P occurs in T. The indexed version of this problem, i.e., preprocessing a string to efficiently answer such permutation queries, is hard and has been studied in the last few years. Currently the best bounds for this problem are O(n^2/log^2n) (with O(n) space and O(1) query time) (Moosa and Rahman (2012) [1]) and O(r^2logr) (with O(|L|) space and O(log|L|) query time) (Badkobeh et al. (2012) [2]), where r is the length of the run-length encoding of T and |L|=O(n) is the size of the index. In this paper we present new results for this problem. Our first result is an alternative construction of the index by Badkobeh et al. (2012) [2] that obtains a trade-off between the space and the time complexity. It has O(r^2logk+n/k) complexity to build the index, O(logk) query time, and uses O(n/k+|L|) space, where k is a parameter. The second result is an O(n^2log^2w/w) algorithm (with O(n) space and O(1) query time), based on word-level parallelism where w is the word size in bits.

It is not always feasible to implement an application specific custom hardware due to cost and time considerations. No instruction set compiler (NISC) architecture is one of the promising directions to design a custom datapath for each application using its execution characteristics. A major challenge with NISC control words is that they tend to be at least 4-5 times larger than regular instruction size, thereby imposing higher memory requirement. A possible solution to counter this is to compress these control words to reduce the code size of the application. This paper proposes an efficient bitmask-based compression technique to drastically reduce the control word size while keeping the decompression overhead in an acceptable range. The main contributions of our approach are (i) smart encoding of constant and less frequently changing bits, (ii) efficient do not care resolution for maximum bitmask coverage using limited dictionary entries, (iii) run length encoding to significantly reduce repetitive control words and (iv) design of an efficient decompression engine to reduce the performance penalty. Our experimental results demonstrate that our approach improves compression efficiency by an average of 20% over the best known control word compression, giving a compression ratio of 25-35%. In addition, our technique only requires 1-3 on-chip RAMs, thus making it suitable for FPGA implementation.

This paper considers a new contour-based representation of binary objects in raster images. Low processing and storage requirements of the decoder, satisfactory compression ratio and generality make this chain coding technique interesting for storing predefined graphical objects in embedded systems. Three improvements of the DDCC code were introduced. Extra Huffman codes are assigned to two frequent pairs of symbols, 135^o directional differences in concave angles are omitted since they do not affect the outer object shape and, finally, longer line segments are run-length encoded. Comparison with six other chain coding techniques of similar implementation complexity confirms that the new technique represents an efficient alternative way to encode 8-connected contours.

In this paper, we study the palindrome retrieval problem with the input string compressed into run-length encoded form. Given a run-length encoded string rle(T), we show how to preprocess rle(T) to support subsequent queries of the longest palindrome centered at any specified position and having any specified number of mismatches between its arms. We present two algorithms for the problem, both taking time and space polynomial in the compressed string size. Let n denote the number of runs of rle(T) and let k denote the number of mismatches. The first algorithm, devised for small k, identifies the desired palindrome in O(logn+min{k,n}) time with O(nlogn) preprocessing time, while the second algorithm achieves O(log2n) query time, independent of k, after O(n2logn)-time preprocessing.

The constrained LCS (CLCS) problem, a recent variant of the longest common subsequence (LCS) problem, has gained much attention. Given two sequences X and Y of lengths n and m, respectively, and the constrained sequence P of length r, previous research shows that the CLCS problem can be solved by either an O(nmr)-time algorithm based upon dynamic programming (DP) techniques or an O(rRloglog(n+m))-time Hunt–Szymanski-like algorithm, where R is the total number of ordered pairs of positions at which the two strings match. In this paper, we investigate the case that X, Y and P are all in run-length encoded (RLE) format, where the numbers of runs are N, M and R, respectively. We first show that when the sequences are encoded, the CLCS problem can be solved by a simple algorithm in O(nmR+nMr+Nmr) time without decompressing the sequences. Then, we propose a more efficient algorithm with O(NMr+r×min{q1,q2}+q3) time, where q1 and q2 denote the numbers of elements in the south and east faces of the matched blocks on the first layer, respectively, and q3 denotes the number of face elements of all fully matched cuboids in the DP lattice.

We present a 3D video-encoding technique called Holovideo that is capable of encoding high-resolution 3D videos into standard 2D videos, and then decoding the 2D videos back into 3D rapidly without significant loss of quality. Due to the nature of the algorithm, 2D video compression such as JPEG encoding with QuickTime Run Length Encoding (QTRLE) can be applied with little quality loss, resulting in an effective way to store 3D video at very small file sizes. We found that under a compression ratio of 134:1, Holovideo to OBJ file format, the 3D geometry quality drops at a negligible level. Several sets of 3D videos were captured using a structured light scanner, compressed using the Holovideo codec, and then uncompressed and displayed to demonstrate the effectiveness of the codec. With the use of OpenGL Shaders (GLSL), the 3D video codec can encode and decode in realtime. We demonstrated that for a video size of 512×512, the decoding speed is 28 frames per second (FPS) with a laptop computer using an embedded NVIDIA GeForce 9400 m graphics processing unit (GPU). Encoding can be done with this same setup at 18 FPS, making this technology suitable for applications such as interactive 3D video games and 3D video conferencing.

In this paper, an optimized wavelet filter bank based methodology is presented for compression of electrocardiogram (ECG) signal. The methodology employs new wavelet filter bank whose coefficients are derived with window techniques such as Kaiser Windows using simple linear optimization and run-length encoding (RLE). The Wavelet based compression techniques minimize the compression distortion, while RLE further increases the compression without any loss of relevant signal information. The developed technique employs a modified thresholding, which improves the compression of signal as compared to earlier existing thresholding technique. A comparative study of performance of different existing methods and the proposed wavelet filter is made in terms of compression ratio ( CR ), percent root mean square difference ( PRD ) and signal-to-noise ratio ( SNR ). When compared, the developed wavelet filter gives better compression ratio and also yields good fidelity parameters as compared to other methods. The simulation result included in this paper shows the clearly increased efficacy and performance in the field of biomedical signal processing.

In this article, we propose a new fast algorithm to compute the squared Euclidean distance transform (E^2DT) on every two-dimensional (2-D) irregular isothetic grids (regular square grids, quadtree based grids, etc.). Our new fast algorithm is an extension of the E^2DT method proposed by Breu et al. [3]. It is based on the implicit order of the cells in the grid, and builds a partial Voronoi diagram of the centers of background cells thanks to a data structure of lists. We compare the execution time of our method with the ones of others approaches we developed in previous works. In those experiments, we consider various kinds of classical 2-D grids in imagery to show the interest of our methodology, and to point out its robustness. We also show that our method may be interesting regarding an application where we extract an adaptive medial axis construction based on a quadtree decomposition scheme.

We present fast methods to describe the surface evolution of large three-dimensional structures. Based on the sparse field level set method and the hierarchical run-length encoding level set data structure optimal figures for the computation time and for the memory consumption are achieved. Furthermore, we introduce a new multi-level-set technique, which is able to incorporate multiple material regions, and which can also handle material specific surface speeds accurately. We also describe an optimal algorithm for the visibility check for unidirectional etching. The presented techniques are demonstrated on various examples.

This paper presents a Fourier descriptor based image alignment algorithm (FDBIA) for applications of automatic optical inspection (AOI) performed in real-time environment. It deliberates component detection and contour tracing algorithms and uses the magnitude and phase information of Fourier descriptors to establish correspondences between the target objects detected in the reference and the inspected images, so the parameters for aligning the two images can be estimated accordingly. To enhance the computational efficiency, the proposed component detection and contour tracing algorithms use the run length encoding (RLE) and Blobs tables to represent the pixel information in the regions of interest. The Fourier descriptors derived from the component boundaries are used to match the target objects. Finally, the transformation parameters for aligning the inspected image with the reference image are estimated based on a novel phase-shifted technique. Experimental results show that the proposed FDBIA algorithm sustains similar accuracy as achieved by the commercial software Easyfind against various rotation and translation conditions. Also, the computational time consumed by the FDBIA algorithm is significantly shorter than that by Easyfind.

Let X and Y be two strings of lengths n and m, respectively, and k and l, respectively, be the numbers of runs in their corresponding run-length encoded forms. We propose a simple algorithm for computing the longest common subsequence of two given strings X and Y in O(kl+min{p"1,p"2}) time, where p"1 and p"2 denote the numbers of elements in the bottom and right boundaries of the matched blocks, respectively. It improves the previously known time bound O(min{nl,km}) and outperforms the time bounds O(kllogkl) or O((k+l+q)log(k+l+q)) for some cases, where q denotes the number of matched blocks.

A one-time signature scheme using run-length encoding is presented, that in the random oracle model offers security against chosen-message attacks. For parameters of interest, the proposed scheme enables about 33% faster verification with a comparable signature size than a construction of Merkle and Winternitz. The public key size remains unchanged (1 hash value). The main price for the faster verification is an increase of the time for signing messages and for key generation.

The problem of computing the similarity of two run-length encoded strings has been studied for various scoring metrics. Many algorithms have been developed for the longest common subsequence metric and some algorithms for the Levenshtein distance metric and the weighted edit distance metric. In this paper we consider similarity based on the affine gap penalty metric which is a more general and rather complicated scoring metric than the weighted edit distance. To compute the similarity in this model efficiently, we convert the problem into a path problem on a directed acyclic graph and use some properties of maximum paths in this graph. We present an O(nm′+n′m) time algorithm for computing the similarity of two run-length encoded strings in the affine gap penalty model, where n and m are the lengths of given two strings whose run-length encoded lengths are n′ and m′, respectively.

We propose a new algorithm for computing the edit distance of an uncompressed string against a run-length-encoded string. For an uncompressed string of length n and a compressed string with M runs, the algorithm computes their edit distance in time O(Mn). This result directly implies an O(min{mN,Mn}) time algorithm for strings of lengths m and n with M and N runs, respectively. It improves the previous best known time bound O(mN+Mn).

The length of the longest common subsequence (LCS) between two strings of M and N characters can be computed by an O( M × N ) dynamic programming algorithm, that can be executed in O( M + N ) steps by a linear systolic array. It has been recently shown that the LCS between run-length-encoded (RLE) strings of m and n runs can be computed by an O( nM + Nm − nm ) algorithm that could be executed in O( m + n ) steps by a parallel hardware. However, the algorithm cannot be directly mapped on a linear systolic array because of its irregular structure. In this paper, we propose a modified algorithm that exhibits a more regular structure at the cost of a marginal reduction of the efficiency of RLE. We outline the algorithm and we discuss its mapping on a linear systolic array.

This study proposes two efficient data hiding methods incorporating both run-length encoding and modular arithmetic. The first method, BRL (hiding bitmap files by run-length), is suitable for embedding simple data with long streams of repeating bits; the second method, GRL (hiding general files by run-length), is good for embedding complicated data with short streams of repeating bits. Both of the new methods embed secret data in each nonoverlapping block composed of only two consecutive pixels, with the image quality controlled by a modular operation. In addition, the concept of run-length encoding - namely recording the number of repeating bits in the secret data and the bit value itself - is applied for simplicity and efficiency. The experimental results demonstrate that BRL and GRL have their own strengths with respect to different types of secret data. Furthermore, on the average, both can outperform other well-accepted image steganographic methods in terms of image quality and embedding capacity.

Many approaches to minutiae extraction have already been proposed for automatic fingerprint matching, and most transform fingerprint images into binary images through state-of-the-art algorithms and submit the binary image to a thinning process. However, this paper proposes an original technique for extracting minutiae based on representing the ridge structure of a fingerprint image as a run length code (RLC). The essential idea is to detect minutiae by searching for the termination points or bifurcation points of ridges in the RLC, rather than in a fingerprint image. Experimental results and a comparative analysis show that the proposed method is fairly reliable and faster than a conventional thinning-based method.

Smooth infinite words over ∑ = {1, 2} are connected to the Kolakoski word K = 221121 ..., defined as the fixpoint of the function Δ that counts the length of the runs of 1's and 2's. In this paper we extend the notion of smooth words to arbitrary alphabets and study some of their combinatorial properties. Using the run-length encoding Δ, every word is represented by a word obtained from the iterations of Δ. In particular we provide a new representation of the infinite Fibonacci word F as an eventually periodic word. On the other hand, the Thue-Morse word is represented by a finite one.

In this paper, an extendable volumetric representation based on run-lengths called spatial run-length encoding (S-RLE) is presented. The S-RLE representation is developed for a haptic shape modeling system that is based on simulated machining processes. In the system, shape modeling is simulated as virtual material removal processes similar to machining processes with volume-based haptic rendering. The object and the tools are represented by S-RLE. The data structure of S-RLE consists of two cross-referenced databases: one is a stack of lists in geometrical domain, recording the runs describing the space occupation of the object; the other is a table in physical domain, describing the physical properties of each element. The latter is extendable to include more diverse physical properties such as parts composed of heterogeneous materials. Algorithms for geometric operations and haptic rendering based on S-RLE are developed. The proposed S-RLE data structure has the features of efficient memory usage, quick collision detection, inherent representation for heterogeneous objects, and fast visual rendering. Copyright 2003 Elsevier Ltd.

Data compression can be used to simultaneously reduce memory, communication and computation requirements of string comparison. In this paper we address the problem of computing the length of the longest common subsequence (LCS) between run-length-encoded (RLE) strings. We exploit RLE both to reduce the complexity of LCS computation from O(M × N) to O(mN + Mn - mn), where M and N are the lengths of the original strings and m and n the number of runs in their RLE representation, and to improve the inherent parallelism of the proposed algorithm, so that it may execute in O(m + n) steps on a systolic array of M + N units.We also discuss the application of the proposed algorithm to the related problem of edit distance (ED) computation.

Many thinning algorithms for 2D binary images, or modifications of existing ones, have been proposed in recent years. The one given herein is surprisingly simple compared to most of them, and still it has theoretically favorable properties. Actually, it provides a connected - single-pixel in width whenever possible - well-centered homototic skeleton that allows shapes to be nearly reconstructed. In addition to these properties, it is also very attractive because of its generalization to higher dimensions. The presented algorithm is based on the application of directional erosions, while retaining those pixels that introduce disconnections. It is shown how this strategy is specially well-suited for run-length encoded images, leading to a very fast and simple thinning algorithm.

Pattern recognition using eigenvectors is a recent active research area. Finding eigenvectors of a large image set, however, has been considered to require too much computation to be practical. We therefore propose a new method for reducing computation of the partial eigenvalue decomposition based on run-length encoding. In this method, called the constant regions method, spatial encoding is used to reduce storage and computation, then coeigenvectors are computed and later converted to eigenvectors. For simple images, and when the number of pixels in an image is much larger than the number of images, the resulting algorithm is shown to grow as the first power of the basic image dimension, rather than the fourth power as for conventional methods. For comparison, the power method, the conjugate gradient method, and a so-called direct method for computing the partial eigenvalue decomposition are also presented, and recommendations are given for when each method should be used. The advantage of the proposed method are verified by tests in which the first several eigenvectors are computed for sets of images having varying complexity. This algorithm is useful for a research area of pattern recognition using eigenvectors.

Many-to-one and one-to-many digital image transformations play a significant role in a variety of imaging communications, visualization, and robotic applications. A method is presented for forwarding mapping frames of TV images in a many-to-one mapping using run length encoding. A digital computer system includes a look-up table memory having the address of each input run-length of pixels (a series of side-by-side pixels) and the address of the single output pixel corresponding thereto. An example is a 512×512 pixel TV frame which, in real time, is mapped onto a log polar coordinate TV frame of 2000-3000 pixels. This method can be used with existing low-cost general purpose computers providing a speed advantage approximating five-hundred percent, and a memory savings of between 10 and 100,000 times, relative to the current art. As a result, electronic imaging systems employing many-to-one or one-to-many image warps may be built in significantly smaller, cheaper, faster and lower power implementations.

Storing ultrasonic data in raw form as it is collected implies the availability of vast backup storage resources. It is shown that by the application of simple compression techniques, the data can be compressed without loss of information by a factor greater than 3. In particular the suitability of A scans to various forms of run length encoding is examined and a particular method is selected and optimized. This involves restricting runs to a maximum of 15 (4 bits) storing long runs as multiples of a 15-length run together with a remainder.

We are concerned with rearranging the order in which data is stored in a database so as to maximize the amount of compression. We consider multi-attribute data defined over finite discrete domains (called categories ) and seek an optimal permutation of the categories for each attribute. We study both deterministic and probabilistic models of data distribution. We show that the deterministic category rearrangement problem is NP-complete (for run length encoding compression methods) via a reduction to the rectilinear traveling salesman problem. For the probabilistic model, we show that the optimal category rearrangement for each attribute has the form of a double pipe organ , which is a generalized version of the well-known pipe organ arrangement found in earlier work on record placement on disk cylinders. For k -dimensional data we obtain an algorithm for finding the optimal arrangement which is O ( n 2 ) for fixed k .

The representation of pictures and maps by piecewise linear surfaces is discussed, Three methods are compared: Run length encoding, description of regions by chain encoding of their boundaries, and description of regions by the vertices of polygonal approximations of their boundaries. The nature of the data determines which is the best method. However, run length encoding seems to be superior for pictures of high detail. Significant increase in compaction ratios is not achieved till one uses polygonal approximations of boundaries, if then. A mixture of the first and the third method can be used to offer an adaptive optimization of the representation.

This paper has two parts. The first part (Sects. 1–5) describes a thining algorithm that operates directly on the run length encoding of a bilevel image. Besides finding strokes that approximate the dark regions of the image, the algorithm determines other features that are useful for character recognition: arcs, holes, endpoints, etc. The second part (Sect. 6) describes the use of the results of the thinning algorithm in a simple demonstration system for document recognition.