There are applications (such as Internet search engines) where short textual strings, for example abstracts or pieces of Web pages, need to be compressed independently of each other. The usual adaptive compression algorithms perform poorly on these short strings due to the lack of necessary data to learn. In this manuscript, we introduce a compression algorithm targeting short text strings; e.g., containing a few hundred symbols. We also target natural language insensitivity, to facilitate its robust compression and fast implementation. The algorithm is based on the following findings. Applying the move-to-front transform (MTFT) after the Burrows-Wheeler transform (BWT) brings the short textual strings to a "normalized form" where the distribution of the resulting "ranks" has a shape similar over the set of natural language strings. This facilitates the use of a static coding method with few variations, which we call shortBWT, where no on-line learning is needed, to encode the ranks. Finally, for short strings, shortBWT runs very fast because the strings fit into the cache of most current computers. The introduction for this paper will review the mathematical bases of BWT and MTF, it will also review our recently published metric for rapidly pre-characterizing the compressibility of such short textual strings when using these transforms.

Object-based compression (OBC) is an emerging technology that combines region segmentation and coding to produce a compact representation of a digital image or video sequence. Previous research has focused on a variety of segmentation and representation techniques for regions that comprise an image. The author has previously suggested [1] partitioning of the OBC problem into three steps: (1) region segmentation, (2) region boundary extraction and compression, and (3) region contents compression. A companion paper [2] surveys implementationally feasible techniques for boundary compression. In this paper, we analyze several strategies for region contents compression, including lossless compression, lossy VPIC, EPIC, and EBLAST compression, wavelet-based coding (e.g., JPEG-2000), as well as texture matching approaches. This paper is part of a larger study that seeks to develop highly efficient compression algorithms for still and video imagery, which would eventually support automated object recognition (AOR) and semantic lookup of images in large databases or high-volume OBC-format datastreams. Example applications include querying journalistic archives, scientific or medical imaging, surveillance image processing and target tracking, as well as compression of video for transmission over the Internet. Analysis emphasizes time and space complexity, as well as sources of reconstruction error in decompressed imagery.

As digital image and video compression technology evolves, it appears that transform based coding or compression techinques will reach asymptotic rate-distortion performance, especially with respect to linear transforms. Although nonlinear compression techniques (for example, based on Markov models) are being developed, progress has been relatively slow due to challenges in theory development. Alternatively, several research teams have produced algorithms for object-based compression (OBC), whereby an image is segmented into areas of similar color or spatial variance. Each segmented region can then be represented in terms of a small region descriptor and somewhat less compact set of boundary descriptors. This paper examines boundary representations and complexity measures for OBC - a previous publication, also related to OBC, overviewed region segmentation techniques. Of particular interest to OBC is the evolution of boundary representations from early approaches such as chain coding or simplical complexes to transform coded descriptors such as Fourier or wavelet-based representations. These techniques precede more modern methods such as hierarchical transforms (e.g., wavelets) and direct compression of Boolean boundary representations. In this paper, the authors develop boundary compression algorithms based on concepts derived from statistical image compression theory and hierarchical codebook representations. The resulting boundary encoding technique is suitable for a wide range of compression applications, in particular, OBC. Performance criteria include computational complexity of the encoding process, as well as space complexity of intermediate and final boundary representations.

Proposed here is a coding scheme based on a 2-dimensional spatial tree entitled 2-MT (2-dimensional Meitei Tree). In this tree structure, we take the element of the upper left corner as the root. From the next level onwards, there are three nodes in each level, namely, left node, middle node and right node. The left and the right nodes are connected to the middle node. Each middle node is connected to the middle node of the next lower level. In other words, only middle nodes have two branches, the right node and the left node. This tree structure is easy to generate and manipulate a matrix (square or rectangular) easily. This avoids the necessity to make the size of an image matrix square and of power 2, as in SPIHT (Set Partitioning in Hierarchical Tree). Also, from the coding implementation point of view, it is much simpler as compared to SPIHT. The corresponding coding scheme based on 2-MT will be known Meitei coding which will be used in our subband compression scheme. This coding scheme is much more flexible and higher compression ratio can be achieved as compared to SPIHT.

We show that the standard image compression algorithms are not suitable for compressing images in correlation pattern recognition since they aim at retaining image fidelity in terms of perceptual quality rather than preserving spectrally significant information for pattern recognition. New compression algorithms for pattern recognition are therefore developed, which are based on the modification of the standard compression algorithms to achieve higher compression ratio and simultaneously to enhance pattern recognition performance. This is done by emphasizing middle and high frequency components and discarding low frequency components according to a new developed distortion measure for compression. The operations of denoising, edge enhancement and compression can be integrated in the encoding process in the proposed compression algorithms. Simulation results show the effectiveness of the proposed compression algorithms.

This paper ties together and extends several recent results we have presented. We previously showed: (i) the usefulness of non-MSE distortion criteria in data compression for time-difference-of-arrival (TDOA) emitter location (SPIE 2001 & 2002), and (ii) the ability to exploit redundancy between radar pulses in a joint TDOA/FDOA (frequency-difference-of-arrival) location scheme (SPIE 2001 & 2002). In (ii) we showed how to compress radar signals by gating around the detected pulses and then putting the pulses into the rows of a matrix which is then compressed through use of the SVD; this approach employed a purely MSE distortion criterion. An open question in this approach was: Is it possible to eliminate some of the pulses from the pulse matrix to increase the compression ratio without significantly sacrificing location accuracy? We resolve this question by applying our proposed non-MSE to the FDOA accuracy and finding the optimal set of pulses to remove from the pulse matrix. The removal of pulses is shown to have negligible impact on the FDOA accuracy but does degrade the TDOA accuracy from that achievable using the SVD-based compression without pulse elimination. However, we demonstrate that the SVD method includes an inherent de-noising effect (common in SVD-based signal processing) that provides an improvement in TDOA accuracy over the case of no compression processing; thus, the overall impact on TDOA/FDOA accuracy is negligible while providing compression ratios on the order of 100:1 for typical radar signals.

Despite the increasing interest in digital watermarking of multimedia data, watermarking of 3D geometrical models has received little attention by the research community. One of the main reasons is that geometric data is intrinsically complex to handle, in addition a lot of diverse attacks can be thought of that are not possible in the 2D and 1D cases. So it is very difficult to develop robust watermarking algorithms for 3D models. In order to overcome the above problems most of the systems proposed so far exploit the knowledge of the original, non marked, mesh for watermark recovery. The practical usefulness of non-blind schemes, though, is very limited, hence the need to develop new blind schemes for 3D watermarking. In this paper we propose a blind watermarking algorithm for 3D meshes. Watermarking is achieved by perturbing the position of the vertices of the model according to a spherical pseudo-random bumped surface. The pseudo-random position and amplitude of the bumps encode the watermark. In order to gain robustness while keeping the distortion to a minimum, the watermark is embedded into a low resolution version of the mesh. The coarse version of the model is obtained by a MAPS1 (Multiresolution Adaptive Parameterization of Surface) algorithm. The base domain produced by this algorithm is used to obtain the full resolution watermarked model from the coarse watermarked one. Watermark recovery is accomplished by means of a standard correlation detector. Experimental results show that the system assure high visual quality of the watermarked model, and that a good degree of robustness can be reached for models with a suffciently high number of faces.

Splatting is a one of the most important object-order volume rendering algorithm. In this paper, a new run length encoding (RLE) accelerated, pre-classification and pre-shade volume splatting algorithm is presented, which enhances the speed of splatting without trading off image quality. This new technique saves rendering time by employing RLE mechanism so that only voxels of interest are processed in splatting. Data structures are defined to fully exploit spatial coherence of volume, including a slice scanline pointer array, a data pointer array, a scanline RLE array and an array storing all data of the non-transparent voxels. And a much fast and accurate sheet buffer splatting method is used in the rendering process, which accelerates the splatting by traversing both the voxel scanline and the image scanline in sheet buffer simultaneously. Experiments practice proves that RLE can efficiently skip over transparent voxels and high speedup can be obtained by using the proposed algorithm. Analysis on speed and memory cost of the algorithm is also conducted. This algorithm may be particularly used in situation where transfer function seldom changes.

Digital watermarking has been recently proposed as the mean for property right protection of digital products. In this paper we analyze the self-similarities of wavelet transform and present a new approach to embed a digital watermark into an image based on the qualified significant wavelet trees (QSWT) of discrete wavelet transform of the image for the purpose of protecting the copyright of the image. Our studies have shown that the watermarked image has a good quality of image, and such a watermark is difficult to detect and unchangeable without the appropriate user cryptogram.

In this paper we study a problem of signal compression how to choose a best mother wavelet from the set S of wavelets. The approach is following: First we calculate a discrete wavelet transform of signal by using one standard wavelet. Then we form coefficients m_i for each scale i from the wavelet expansions coefficients. Coefficients m_i are used for selecting best wavelet from the set S. Selection is classification problem and we have constructed classification algorithm that uses fuzzy similarity that is based on a continuous t-norm called Lukasiewicz algebra. We are using normal and cumulative forms of generalized Lukasiewicz algebra and we have also applied a genetic algorithm into the our classifier to choose appropriate weights in our classification tasks. There are many advantages what we get by using t-norm called Lukasiewicz in classification: 1) Structure has a promising mathematical background 2) Mean of many fuzzy similarities is still a fuzzy similarity 3) Any pseudo-metric induces fuzzy similarity on a given non-empty set X with respect to the Lukasiewicz-conjunction. Algorithm is efficient especially because we have to calculate wavelet transform only once and classification is simple and fast. Algorithm is also very flexible, cause we can implement any type metrics or mean measures into it. As our results we will present a new method to select best mother wavelet from a given set S. We will also show that proposed hybrid method can be used in this kind of analytical problems. The best way to form coefficients m_i and choose metric or measure is depended of class of signals we are working with, which is still unclear.

In this paper the new family of orthogonal compactly supported M-band wavelets is presented. This family is similar to Coiflets since scaling function and all wavelet functions have equal number of vanishing moments. However, the center of these vanishing moments can differ from zero. Equivalent moment conditions are given also for scaling filter. Finally, estimate for asymptotic convergence speed of wavelet sampling approximation of smooth functions is given.

Since few years, Lifting Scheme has proven its utility in compression field. It permits to easily create fast, reversible, separable or no, not necessarily linear, multiresolution analysis for sound, image, video or even 3D graphics. An interesting feature of lifting scheme is the ability to build adaptive transforms for compression, more easily than with other decompositions. Many works have already be done in this subject, especially in lossless or near-lossless compression framework : better compression than with usually used methods can be obtained. However, most of the techniques used in adaptive near-lossless compression can not be extended to higher lossy compression rates, even in the simplest cases. Indeed, this is due to the quantization error introduced before coding, which has not controlled propagation through inverse transform. Authors have put their interest to the classical Lifting Scheme, with linear convolution filters, but they studied criterions to maintain a high level of adaptivity and a good error propagation through inverse transform. This article aims to present relatively simple criterion to obtain filters able to build image and video compression with high compression rate, tested here with the Spiht coder. For this, upgrade and predict filters are simultaneously adapted thanks to a constrained least-square method. The constraint consists in a near-orthogonality inequality, letting sufficiently high level of adaptivity. Some compression results are given, illustrating relevance of this method, even with short filters.

This paper reports about the main results of a project aimed at developing advanced methods for lossless compression of hyperspectral data and at providing implementations on a space-certified processing board. In particular, adaptive DPCM methods exploiting 3D spectral correlation and context-based entropy coding are compared. The algorithms considered utilize "classified" DPCM, where predictors are preliminarily calculated, taking into account the statistical properties of the image being compressed, and then adaptively selected or combined. Starting from a few advanced algorithms recognized as the most relevant, a scheme suitable for onboard implementation has been derived and implemented on a TSC21020 board. The final method developed represents a good compromise between compression results and computational complexity and utilizes a CCSDS Rice encoder. Performances are assessed by means of comparisons with the results obtained by both standard and advanced algorithms providing state-of-the-art and top performances, respectively.

The dominant image processing tasks for hyperspectral data are compression and feature recognition. These tasks go hand-in-hand. Hyperspectral data contains a huge amount of information that need to be processed (and often very quickly) depending on the application. The discrete wavelet transform is the ideal tool for this type of data structure. There are applications that require such processing (especially feature recognition or identification) be done extremely fast and efficiently. Furthermore the higher number of dimensions implies a number of different ways to do these transforms. Much of the work in this area to the present time has been focused on JPEG2000 type compression of each component image involving fairly sophisticated coding techniques; relatively little attention has been paid to other configurations of wavelet transforms of such data, as well as rapid feature identification where compression may not be necessary at all. This paper describes other versions of the 3D wavelet transform that allow the resolution in both the spatial domain and spectral domain to be adjusted separately. Other issues associated with low complexity feature recognition with and without compression using versions of the 3D hyperspectral wavelet transforms will be discussed along with some illustrative calculations.

This paper describes data compression algorithms capable to preserve the scientific quality of remote-sensing data, yet allowing a considerable bandwidth reduction to be achieved. Unlike lossless techniques, by which a moderate a compression ratio (CR) is attainable, due to intrinsic noisiness of the data, and conventional lossy techniques, in which the mean squared error of the decoded data is globally controlled by user, near-lossless methods are capable to locally constrain the maximum error, either absolute or relative, based on the user's requirements. Advanced near-lossless methods rely on differential pulse code modulation (DPCM) schemes, based on either prediction or interpolation. The latter is recommended for lower quality compression (i.e., higher CR), the former for higher-quality, which is the primary concern in remote sensing applications. Goal of this work is to investigate and compare different compression methodologies from the viewpoint of spectral distortion introduced in hyperspectral pixel vectors. The main result of this analysis is that, for a given compression ratio, near-lossless methods, having constrained pixel error, either absolute or relative, are more suitable for preserving the spectral discrimination capability among pixel vectors, which is the principal source of spectral information. Therefore, whenever a lossless compression is not practicable, the use of near-lossless compression is recommended in such application where spectral quality is a crucial point.

In the conversion of an imager’s pixel data from electrons to digital numbers, a scalar quantization is performed. For CMOS sensors used in consumer applications, this scalar quantization is usually performed by an on-chip analog-to-digital converter (ADC) preceded by an amplifier. It is desired that the scalar quantization operation minimize the error between the analog input signal and the quantized output. One approach is to use a non-uniform quantizer for a signal with a known probability density function to minimize the mean square error. The Lloyd-Max algorithm can be used to determine the optimal quantization intervals and reconstruction levels. However, a probability model for the variations of pixels in a sensor is difficult to determine since the sensor can receive a vast number of greatly differing image data. Additionally, a quantizer with non-uniform intervals is difficult to implement, can be unstable, and has limited flexibility. Thus, it is preferred to use a simple linear, uniform quantization step size ADC to sample the sensor’s data. The approach taken in this paper is to develop a scalar quantizer that utilizes knowledge of a sensor’s performance characteristics. The decision and reconstruction levels of a non-uniform quantizer are determined from the noise versus signal characteristics of the sensor. A linear, uniform quantization step size ADC can be used to 'over-encode’ (sample using more bits per pixel than required) the sensor’s data. The number of bits per pixel can then be reduced using a sensor characterization optimized mapping to a lower bit depth. This results in a reduction of the sensor’s digitized data. The conversion function from pixel electrons to the digitized signal value is developed in this paper for a CMOS sensor with small pixel size designed for embedded applications. These sensors will typically exhibit lower signal to noise ratios due to their lower well capacity (lower dynamic range), higher levels of random noise, and higher cross-talk (the loss of photons or electrons from a pixel to neighboring pixels); which makes them ideal for this type of mapping. The performance of the proposed noise-based quantization method is measured through the calculation of mean square errors and relative compressibility of quantized sample images.

Spread-spectrum watermarking scheme adds random noise w into the host signal x to generate watermarked signal s. Blind detector computes inner product or its variants and decides embedded bits by its sign of the inner product. Such detection method is not robust due to high false-positive or false-negative rate. This paper introduces a novel method to reduce detection errors considerably by excluding outliers in the signal. Stable and robust definition of outlier is adopted. Informed watermarking scheme for spread-spectrum is exploited to reduce false-positive and false-negative errors. Such detectors can also enhance detection rate in other watermarking schemes.

In this paper, a new stereo image watermarking scheme using the discrete wavelet transform (DWT) and adaptive disparity estimation is proposed. First, a watermark data is embedded into the right image of a stereo image pair by using the conventional DWT operation. Here, the right image is decomposed into three-level by DWT and then the watermark is embedded into DWT coefficients using the characteristics of the human visual system. Second, the disparity data is extracted by using the watermarked right image and the left image. And then, both of this extracted disparity data and the left image are transmitted to the recipient through the communication channel. At the receiver, the watermarked right image is reconstructed from the received left image and disparity data by use of the adaptive matching algorithm. Basing on the difference between the discrete wavelet-transformed watermarked image and original right image, the embedded watermark image can be extracted from this reconstructed right image. From some experiments using the stereo images of the CCETT's 'Manege' and a watermark image of English alphabet 'NRL', it is found that the PSNRs of the reconstructed right images by using the proposed algorithm improve to 7.6dB for 'Manege' on average by comparing with those of the reconstructed right images through the conventional pixel-based matching algorithm, block-based matching algorithm and DWT-based algorithms. At the same time the PSNRs of the watermark image extracted from these reconstructed right images also improve to 6.51dB on average for 'Manege' images, respectively. These experimental results also suggest a possibility of practical implementation of the stereo image watermarking system based-on the adaptive matching algorithm and the discrete wavelet transform.

In this paper we propose a new method based on Second Generation Wavelets (SGW), a recently emerged mathematic transform, already successfully applied in 3d coding. This new wavelet transform (SGW) applied to meshes is performed using the powerful lifting scheme, keeping the main features of the first generation wavelets whilst introducing some useful properties such as: analysis on general domains (typically arbitrary, non linear domains of Rn), adapted basis for weighted approximation/interpolation and weighted measure and transform adapted to irregular sampled data. Thus in this paper we propose a video coder based on second generation wavelet theory and mesh geometry. In fact, we focus on video coder error images which are mainly composed of high frequencies and singularities, i.e. typically the kind of data that second generation wavelet can successfully process. The main advantage is that these wavelets can be designed to fit exactly on singularities, shapes, textures, and edges. Hence, we can further reduce redundancy and improve coding efficiency over those peculiar settings.

In this paper, an improved second generation digital image watermarking scheme is proposed. This scheme exploits the region feature instead of point or line feature. The region features are retrieved by watershed transform, which allows watermark recovery after common attacks. The experiments have shown that this proposed scheme is robust against compression, noise intrinsically and more robust against geometrical attacks and JPEG compression compared with Kutter’s method. The watermark capacity is improved because the robustness of region feature is more than point or line feature.

The 3-D estimation of human motion captured by a video camera(s) is becoming a challenging scientific task. In this paper, two important problems are addressed: the acquisition of 3-D coordinates of human's body parts, and the key-frame-based human motion prediction. To the key frames, a fuzzy pattern matching method is adopted to detect and get 2-D image coordinates of the face in each image sequence. After stereo matching of the same feature point, we use a binocular imaging model to accomplish the acquisition of 3-D coordinates of the head. Out of the key frames, we use a Kalman estimator to predict the motion of human body parts. At the end of the paper, the experimental result and discussion are given.

In this paper and its sequel, we will examine two fundamental problems related to object recognition for the generalized weak perspective model of image formation. We offer a complete solution to both problems for configurations of point features. Geometric Constraints (Object/Image Equations): The problem of single view recognition is central to many image understanding and computer vision tasks. The results in this paper provide a way to understand the relationship that exists between the 3D geometry and its "residual" in a 2D image. This relationship is completely characterized (for a particular combination of features) by a set of fundamental equations in the 3D and 2D shape coordinates. These equations are know as object/image relations. They can be used to test for the geometric consistency between an object and an image. For example, by fixing point features on a known object, we get constraints on the 2D shape coordinates of possible images of those features. Conversely, if we have specific 2D features in an image, we will get constraints on the 3D shape coordinates of objects capable of producing that image. This yields a test for which object is being viewed. The object/image equations are thus fundamental tools for the identification/recognition problem. In this paper we give the complete solution, and find explicitly, the object/image equations for point features in the generalized weak perspective case. This entails working on spaces known as Grasssmannians and exploiting certain incidence correspondences and the so-called Plucker relations. Vision Metrics: We would like to know if two configurations of a fixed number of points in 2D or 3D are the same if we allow affine transformations. If they are, then we want a distance of zero, and if not, we want a distance that expresses their dissimilarity - always recognizing that we can transform the points. The Procrustes metric, described in the shape theory literature [2], provides such a notion of distance for similarity transformmations. However, it does not allow for weak perspective or perspective transformations and is fixed in a particular dimension. By the later we mean that it cannot be regarded as giving us a notion of "distance" between, say, a 3D configuration of points and a 2D configuration of points, where zero distance corresponds to the 2D points being, say, a generalized weak perspective projection of the 3D points. In the sequel to this paper, we show that generalizations of the Procrustes metric exist in the above cases. Moreover these new metrics are quite natural in the context of the algebro-geometric formulation of the object/image equations mentioned above. These metrics also provide a rigorous foundation for error and statistical analysis in the object recognition problem.