Efficiency of chain codes to represent binary objects

We present a study of compression efficiency for binary objects or bi-level images for different chain-code schemes. Chain-code techniques are used for compression of bi-level images because they preserve information and allow a considerable data reduction. Furthermore, chain codes are the standard input format for numerous shape-analysis algorithms. In this work we apply chain codes to represent object with holes and we compare their compression efficiency for seven chain codes. We have also compared all these chain codes with the JBIG standard for bi-level images.     

A fast algorithm for constructing nearly optimal prefix codes

Huffman algorithm allows for constructing optimal prefix‐codes with O(n·logn) complexity. As the number of symbols ngrows, so does the complexity of building the code‐words. In this paper, a new algorithm and implementation are proposed that achieve nearly optimal coding without sorting the probabilities or building a tree of codes. The complexity is proportional to the maximum code length, making the algorithm especially attractive for large alphabets. The focus is put on achieving almost optimal coding with a fast implementation, suitable for real‐time compression of large volumes of data. A practical case example about checkpoint files compression is presented, providing encouraging results. Copyright © 2015 John Wiley & Sons, Ltd.     

Mesh Optimization Using Global Error with Application to Geometry Simplification

This paper presents a linear running time optimization algorithm for meshes with subdivision connectivity, e.g., subdivision surfaces. The algorithm optimizes a model using a metric defined by the user. Two functionals are used to build the metric: a rate functional and a distortion (i.e. error) functional. The distortion functional defines the error function to minimize, whereas the rate functional defines the minimization constraint. The algorithm computes approximations within this metric using jointly global error and an optimal vertex selection technique inspired from optimal tree pruning algorithms used in compression. We present an update mechanism, that we name merging domain intersections (MDIs), allowing the control of global error through the optimization process at low cost. Our method has application in progressive model decomposition, compression, rendering, and finite element methods. We apply our method to geometry simplification and present an algorithm to compute a decomposition of a model into a multiresolution hierarchy in O(n log n) time using global error, where n is the number of vertices in the full-resolution model. We show that a direct approach, i.e. not using MDIs, recomputing global error has at least cost O(n²). We analyze the optimality of the algorithm and give several for its properties. We present results for semi-regular meshes obtained from approximation of subdivision surfaces whose connectivity is obtain from (triangulated) quadrilateral quadrisection (e.g. 4-8 or Catmull-Clark subdivision).     

Data Compression for PC Software Distribution

This paper presents the design and implementation of a data compression scheme that can be used for PC software distribution. The method utilizes a lazy parsing strategy and a large sliding-window to obtain good compression ratio. A large window is used to read in characters from a file and a suffix tree is constructed to search for the longest matching substring. Lazy parsing is used to improve the compression performance moderately. Modified unary codes and Huffman codes are used to encode the displacements, copy-lengths and copied symbols. Although the encoder is complex, the expansion phase of such a coder is simple and works very fast; experimental results confirm this fact. Such a compression scheme is most appropriate to be used for PC software distribution.     

Single chains to represent groups of objects

A chain code is a common, compact and size-efficient way to represent the contour shape of an object. When a group of objects is studied using chain codes, previous works require to obtain one chain code for each object. In this paper we assign a single chain to a group of objects, in such a way that all the properties of each object of the group can be recovered from the single chain. In order to achieve higher levels of compression, we propose a lossless method, that consists of representing a group of objects by means of a single chain, and then to apply a context-mixing algorithm. Regarding other methods of compression of the state-of-the-art, our experiments demonstrate that the best compression performance is achieved when our lossless method is applied. In this case more than 15% of a better compression level is reached.     

An efficient raster font compression for embedded systems

This paper presents a new lossless raster font compression method that uses vertex chain code to define character’s outline. Obtained chain codes are compressed by Huffman coding algorithm. The results show that the new method requires least memory space to store the raster fonts among the known methods. Moreover, the font size has almost no impact on the coder efficiency. Due to the low complexity of the decoder that occupies only 2.7 kB of memory space, this method is ideal for use in embedded systems.     

On-line construction of parameterized suffix trees for large alphabets

We consider on-line construction of the suffix tree for a parameterized string, where we always have the suffix tree of the input string read so far. This situation often arises from source code management systems where, for example, a source code repository is gradually increasing in its size as users commit new codes into the repository day by day. We present an on-line algorithm which constructs a parameterized suffix tree in randomized O(n) time, where n is the length of the input string. Our algorithm is the first randomized linear time algorithm for the on-line construction problem.     

On the lexicographical generation of compressed codes

A certain class of algorithms for the lexicographical generation of combinatorial objects can be considered as working on the code tree representation of the objects processed. Then the strategy used by the algorithms in order to find lexicographical successors corresponds to a special kind of tree traversal. If the encoding used is redundant in the sense that the code tree has nodes with only one successor, compression becomes possible which allows for a speed-up in the lexicographical generation. In this note we analyze the average running time saved when compression is applied. For this purpose we consider random code trees within the model of simply generated trees together with the compression as used for the trie and the PATRICIA data structure. We prove general results which quantify the average savings only depending on the generator Θ and the size of the family under consideration. As an example, those results are applied to consider random encodings over an s-ary alphabet. Finally, we comment on connections of our findings to the problem of ranking words of a given language.     

Efficient and exact quantum compression

We present a divide and conquer based algorithm for optimal quantum compression/decompression, using O(n(log⁴n)log log n) elementary quantum operations. Our result provides the first quasi-linear time algorithm for asymptotically optimal (in size and fidelity) quantum compression and decompression. We also outline the quantum gate array model to bring about this compression in a quantum computer. Our method uses various classical algorithmic tools to significantly improve the bound from the previous best known bound of O(n³) for this operation.     

A parallel algorithm for generating chain code of objects in binary images

This paper addresses parallel execution of chain code generation on a linear array architecture. The contours in the proposed algorithm are viewed as a set of edges (or contour segments) that can be traced by a top-down contour tracing method to generate the chain codes for the outer and inner object contours. A parallel algorithm that contains the chain code generating rules and operations needed is also described, and the algorithm is mapped onto a one-dimensional systolic array containing processing elements (PEs) to devise this architecture. The architecture extracts the contours of objects and quickly generates the corresponding chain codes after the image data in all rows are inputted in a linear fashion. The total processing time for generating the chain codes in an N×N image is O(3N). By doing so, the real-time requirement is fulfilled and its execution time is independent of the image content. In addition, a partition method is developed to process an image when the parallel architecture has a fixed number of PEs; say two or more. The total execution time for an N×N image by employing a fixed number of PEs is N(N+1)/M+2(M−1), when M is the fixed number of PEs.     

GF（4）上偶码长自正交码的子码链

基于构造自正交码码树,研究由已知自正交码构造新自正交码的生成矩阵降维方法,采用贪婪策略和BFS算法,提出可行的降维算法。对GF（4）上码长20≤n≤30的自对偶码利用降维算法构造出其子码链及导出其L-链,进而得到45个较好参数达的量子码,其中7个改进了前人所得量子码的参数。     

Is Huffman coding dead?

In recent publications about data compression, arithmetic codes are often suggested as the state of the art, rather than the more popular Huffman codes. While it is true that Huffman codes are not optimal in all situations, we show that the advantage of arithmetic codes in compression performance is often negligible. Referring also to other criteria, we conclude that for many applications, Huffman codes should still remain a competitive choice.     

The Generalized Dimension Exchange Method for Load Balancing in k-ary n-Cubes and Variants

The generalized dimension exchange (GDE) method is a fully distributed load balancing method that operates in a relaxation fashion for multicomputers with a direct communication network. It is parameterized by an exchange parameter λ that governs the splitting of load between a pair of directly connected processors during load balancing. An optimal λ would lead to the fastest convergence of the balancing process. Previous work has resulted in the optimal λ for the binary n-cubes. In this paper, we derive the optimal lambda′s for the k-ary n-cube network and its variants-the ring, the torus, the chain, and the mesh. We establish the relationships between the optimal convergence rates of the method when applied to these structures, and conclude that the GDE method favors high-dimensional k-ary n-cubes. We also reveal the superiority of the GDE method to another relaxation-based method, the diffusion method. We further show through statistical stimulations that the optimal lambda′s do speed up the GDE balancing procedure significantly. Because of its simplicity, the method is readily implementable. We report on the implementation of the method in two data-parallel computations in which the improvement in performance due to GDE balancing is substantial.     

A tree structure of automata for selective image scanning and its implementation

We propose a novel signal scanning method using a tree structure of automata. This method has a kind of image compression capability, about 1/6–1/20 for samples images, by skipping the scan of non-active elements with a selectively activated signal path only to active elements. We also demonstrate the effect of data compression for some examples and an implementation of tree structure on a VLSI chip.     

Evolutionary design of oriented-tree networks using Cayley-type encodings

This paper introduces the oriented-tree network design problem (OTNDP), a general problem of tree network design with several applications in different fields. We also present several adaptations needed by evolutionary algorithms with Cayley-type encodings to tackle the OTNDP. In particular, we present these adaptations in two Cayley-encodings known as Prüfer and Dandelion codes. We include changes in Cayley-encodings to consider rooted trees. We also show how to use a fixed-length encoding for Cayley codes in evolutionary algorithms, and how to guarantee that the optimal solution is included in the search space. Finally, we present several adaptations of the evolutionary algorithm’s operators to deal with Cayley-encodings for the OTNDP. In the experimental part of the paper, we compare the performance of an evolutionary algorithm (implementing the two Cayley-encodings considered) in several OTNDP instances: first, we test the proposed techniques in randomly generated instances, and second, we tackle a real application of the OTNDP: the optimal design of an interactive voice response system (IVR) in a call center.     

Discriminant ECOC: a heuristic method for application dependent design of error correcting output codes

We present a heuristic method for learning error correcting output codes matrices based on a hierarchical partition of the class space that maximizes a discriminative criterion. To achieve this goal, the optimal codeword separation is sacrificed in favor of a maximum class discrimination in the partitions. The creation of the hierarchical partition set is performed using a binary tree. As a result, a compact matrix with high discrimination power is obtained. Our method is validated using the UCI database and applied to a real problem, the classification of traffic sign images.     

A Fast Quartet tree heuristic for hierarchical clustering

The Minimum Quartet Tree Cost problem is to construct an optimal weight tree from the weighted quartet topologies on n objects, where optimality means that the summed weight of the embedded quartet topologies is optimal (so it can be the case that the optimal tree embeds all quartets as nonoptimal topologies). We present a Monte Carlo heuristic, based on randomized hill-climbing, for approximating the optimal weight tree, given the quartet topology weights. The method repeatedly transforms a dendrogram, with all objects involved as leaves, achieving a monotonic approximation to the exact single globally optimal tree. The problem and the solution heuristic has been extensively used for general hierarchical clustering of nontree-like (non-phylogeny) data in various domains and across domains with heterogeneous data. We also present a greatly improved heuristic, reducing the running time by a factor of order a thousand to ten thousand. All this is implemented and available, as part of the CompLearn package. We compare performance and running time of the original and improved versions with those of UPGMA, BioNJ, and NJ, as implemented in the SplitsTree package on genomic data for which the latter are optimized.     

Syntactic compression codes at the zero entropy point

Syntactic compression codes compress the tree, which is the syntax of a binary source message. The ones considered here originate from image processing. The syntactic trees usedhave a constant valency and their binary labels distinguish whether the source substring derived from a node is completely zero or not. We compress them simply by deleting some redundant subtrees.

These codes fall into a theoretically new class of codes which is wider than the classical ones. They are here studied in the neighborhood of a zero of the binary entropy function. There, their behavior is close to that of an infinite run length encoding and the optimum valency is three. Finally, we open a problem, related with automata theory, which perhaps could provide a further link between Information Theory and Algorithmic Information Theory.     

A technique for encoding lines and regions in engineering drawings

An improvement to a method of extracting line and region information from technical drawings is presented. A scheme for compressing this information as it is being found is also given. The encoding scheme is based on a combination of run-length codes, direction chain codes, and Huffman codes. It is efficient, requires minimal storage, and achieves favorable compression ratios. Experimental results from four typical line drawings are presented.     

New adaptive compressors for natural language text

Semistatic byte‐oriented word‐based compression codes have been shown to be an attractive alternative to compress natural language text databases, because of the combination of speed, effectiveness, and direct searchability they offer. In particular, our recently proposed family of dense compression codes has been shown to be superior to the more traditional byte‐oriented word‐based Huffman codes in most aspects. In this paper, we focus on the problem of transmitting texts among peers that do not share the vocabulary. This is the typical scenario for adaptive compression methods. We design adaptive variants of our semistatic dense codes, showing that they are much simpler and faster than dynamic Huffman codes and reach almost the same compression effectiveness. We show that our variants have a very compelling trade‐off between compression/decompression speed, compression ratio, and search speed compared with most of the state‐of‐the‐art general compressors. Copyright © 2008 John Wiley & Sons, Ltd.