Efficient quadtree coding of images and video

Optical Flow Based Co-located Reference Frame for Video Compression

This paper proposes a novel bi-directional motion compensation framework that extracts existing motion information associated with the reference frames and interpolates an additional reference frame candidate that is co-located with the current frame. The approach generates a dense motion field by performing optical flow estimation, so as to capture complex motion between the reference frames without recourse to additional side information. The estimated optical flow is then complemented by transmission of offset motion vectors to correct for possible deviation from the linearity assumption in the interpolation. Various optimization schemes specifically tailored to the video coding framework are presented to further improve the performance. To accommodate applications where decoder complexity is a cardinal concern, a block-constrained speed-up algorithm is also proposed. Experimental results show that the main approach and optimization methods yield significant coding gains across a diverse set of video sequences. Further experiments focus on the trade-off between performance and complexity, and demonstrate that the proposed speed-up algorithm offers complexity reduction by a large factor while maintaining most of the performance gains.

Early CU Depth Decision and Reference Picture Selection for Low Complexity MV-HEVC

The Multi-View extension of High Efficiency Video Coding (MV-HEVC) has improved the coding efficiency of multi-view videos, but this comes at the cost of the extra coding complexity of the MV-HEVC encoder. This coding complexity can be reduced by efficiently reducing time-consuming encoding operations. In this work, we propose two methods to reduce the encoder complexity. The first one is Early Coding unit Splitting (ECS), and the second is the Efficient Reference Picture Selection (ERPS) method. In the ECS method, the decision of Coding Unit (CU) splitting for dependent views is made on the CU splitting information obtained from the base view, while the ERPS method for dependent views is based on selecting reference pictures on the basis of the temporal location of the picture being encoded. Simulation results reveal that our proposed methods approximately reduce the encoding time by 58% when compared with HTM (16.2), the reference encoder for MV-HEVC.

Computational cell analysis for label-free detection of cell properties in a microfluidic laminar flow

Although a flow cytometer, being one of the most popular research and clinical tools for biomedicine, can analyze cells based on the cell size, internal structures such as granularity, and molecular markers, it provides little information about the physical properties of cells such as cell stiffness and physical interactions between the cell membrane and fluid. In this paper, we propose a computational cell analysis technique using cells' different equilibrium positions in a laminar flow. This method utilizes a spatial coding technique to acquire the spatial position of the cell in a microfluidic channel and then uses mathematical algorithms to calculate the ratio of cell mixtures. Most uniquely, the invented computational cell analysis technique can unequivocally detect the subpopulation of each cell type without labeling even when the cell type shows a substantial overlap in the distribution plot with other cell types, a scenario limiting the use of conventional flow cytometers and machine learning techniques. To prove this concept, we have applied the computation method to distinguish live and fixed cancer cells without labeling, count neutrophils from human blood, and distinguish drug treated cells from untreated cells. Our work paves the way for using computation algorithms and fluidic dynamic properties for cell classification, a label-free method that can potentially classify over 200 types of human cells. Being a highly cost-effective cell analysis method complementary to flow cytometers, our method can offer orthogonal tests in companion with flow cytometers to provide crucial information for biomedical samples.

Learning to Detect Video Saliency With HEVC Features

Saliency detection has been widely studied to predict human fixations, with various applications in computer vision and image processing. For saliency detection, we argue in this paper that the state-of-the-art High Efficiency Video Coding (HEVC) standard can be used to generate the useful features in compressed domain. Therefore, this paper proposes to learn the video saliency model, with regard to HEVC features. First, we establish an eye tracking database for video saliency detection, which can be downloaded from https://github.com/remega/video_database. Through the statistical analysis on our eye tracking database, we find out that human fixations tend to fall into the regions with large-valued HEVC features on splitting depth, bit allocation, and motion vector (MV). In addition, three observations are obtained with the further analysis on our eye tracking database. Accordingly, several features in HEVC domain are proposed on the basis of splitting depth, bit allocation, and MV. Next, a kind of support vector machine is learned to integrate those HEVC features together, for video saliency detection. Since almost all video data are stored in the compressed form, our method is able to avoid both the computational cost on decoding and the storage cost on raw data. More importantly, experimental results show that the proposed method is superior to other state-of-the-art saliency detection methods, either in compressed or uncompressed domain.

VirtualMicroscopy: ultra-fast interactive microscopy of gigapixel/terapixel images over internet

As digital imaging technology advances, gigapixel or terapixel super resolution microscopic images become available. We have built a real time virtual microscopy technique for interactive analysis of super high resolution microscopic images over internet on standard desktops, laptops or mobile devices. The presented virtual microscopy technique is demonstrated to perform as fast as using a microscopy locally without any delay to assess gigapixel ultra high resolution image data through wired or wireless internet by a Tablet or a standard PC. More importantly, the presented technology enables analysis of super high resolution microscopic image across sites and time and allows multi-person analysis at the same time, which greatly speed up data analysis process and reduces miscommunication among scientists and doctors. A web site has been created for illustration purposes. (http://www-o.ntust.edu.tw/~cweiwang/VirtualMicroscopy).

Enhanced three-dimensional discrete cosine transform based compression method for integral images by adaptive three-dimensional block construction

In this paper, we propose an efficient compression method for integral images based on three-dimensional discrete cosine transform (3D-DCT). Even though the existing 3D-DCT based techniques are efficient, they may not be optimized to the characteristics of integral images, such as applying a fixed size block construction and a fixed scanning in placing 2D blocks to construct a 3D block. Therefore, we propose a variable size block construction and a scanning method adaptive to characteristics of integral images, which are realized by adaptive 3D block modes. Experimental results show that the proposed method gives significant improvement in coding efficiency. In particular, at the high bit rates, the proposed method is more improved, since overhead bits for signaling of the 3D block modes take a smaller part of the total bits.

Adaptive compression of slowly varying images transmitted over Wireless Sensor Networks

In this article a scheme for image transmission over Wireless Sensor Networks (WSN) with an adaptive compression factor is introduced. The proposed control architecture affects the quality of the transmitted images according to: (a) the traffic load within the network and (b) the level of details contained in an image frame. Given an approximate transmission period, the adaptive compression mechanism applies Quad Tree Decomposition (QTD) with a varying decomposition compression factor based on a gradient adaptive approach. For the initialization of the proposed control scheme, the desired a priori maximum bound for the transmission time delay is being set, while a tradeoff among the quality of the decomposed image frame and the time needed for completing the transmission of the frame should be taken under consideration. Based on the proposed control mechanism, the quality of the slowly varying transmitted image frames is adaptively deviated based on the measured time delay in the transmission. The efficacy of the adaptive compression control scheme is validated through extended experimental results.

Wavelet-based joint estimation and encoding of depth-image-based representations for free-viewpoint rendering

We propose a wavelet-based codec for the static depth-image-based representation, which allows viewers to freely choose the viewpoint. The proposed codec jointly estimates and encodes the unknown depth map from multiple views using a novel rate-distortion (RD) optimization scheme. The rate constraint reduces the ambiguity of depth estimation by favoring piecewise-smooth depth maps. The optimization is efficiently solved by a novel dynamic programming along trees of integer wavelet coefficients. The codec encodes the image and the depth map jointly to decrease their redundancy and to provide a RD-optimized bitrate allocation between the two. The codec also offers scalability both in resolution and in quality. Experiments on real data show the effectiveness of the proposed codec.

Universal image compression using multiscale recurrent patterns with adaptive probability model

In this work, we further develop the multidimensional multiscale parser (MMP) algorithm, a recently proposed universal lossy compression method which has been successfully applied to images as well as other types of data, as video and ECG signals. The MMP is based on approximate multiscale pattern matching, encoding blocks of an input signal using expanded and contracted versions of patterns stored in a dictionary. The dictionary is updated using expanded and contracted versions of concatenations of previously encoded blocks. This implies that MMP builds its own dictionary while the input data is being encoded, using segments of the input itself, which lends it a universal flavor. It presents a flexible structure, which allows for easily adding data-specific extensions to the base algorithm. Often, the signals to be encoded belong to a narrow class, as the one of smooth images. In these cases, one expects that some improvement can be achieved by introducing some knowledge about the source to be encoded. In this paper, we use the assumption about the smoothness of the source in order to create good context models for the probability of blocks in the dictionary. Such probability models are estimated by considering smoothness constraints around causal block boundaries. In addition, we refine the obtained probability models by also exploiting the existing knowledge about the original scale of the included blocks during the dictionary updating process. Simulation results have shown that these developments allow significant improvements over the original MMP for smooth images, while keeping its state-of-the-art performance for more complex, less smooth ones, thus improving MMP's universal character.

Medical image compression using DCT-based subband decomposition and modified SPIHT data organization

OBJECTIVE

The work proposed a novel bit-rate-reduced approach for reducing the memory required to store a remote diagnosis and rapidly transmission it.

METHOD

In the work, an 8x8 Discrete Cosine Transform (DCT) approach is adopted to perform subband decomposition. Modified set partitioning in hierarchical trees (SPIHT) is then employed to organize data and entropy coding. The translation function can store the detailed characteristics of an image. A simple transformation to obtain DCT spectrum data in a single frequency domain decomposes the original signal into various frequency domains that can further compressed by wavelet-based algorithm. In this scheme, insignificant DCT coefficients that correspond to a particular spatial location in the high-frequency subbands can be employed to reduce redundancy by applying a proposed combined function in association with the modified SPIHT.

RESULTS AND CONCLUSIONS

Simulation results showed that the embedded DCT-CSPIHT image compression reduced the computational complexity to only a quarter of the wavelet-based subband decomposition, and improved the quality of the reconstructed medical image as given by both the peak signal-to-noise ratio (PSNR) and the perceptual results over JPEG2000 and the original SPIHT at the same bit rate. Additionally, since 8x8 fast DCT hardware implementation being commercially available, the proposed DCT-CSPIHT can perform well in high speed image coding and transmission.

Space-frequency quantization for image compression with directionlets

The standard separable 2-D wavelet transform (WT) has recently achieved a great success in image processing because it provides a sparse representation of smooth images. However, it fails to efficiently capture 1-D discontinuities, like edges or contours. These features, being elongated and characterized by geometrical regularity along different directions, intersect and generate many large magnitude wavelet coefficients. Since contours are very important elements in the visual perception of images, to provide a good visual quality of compressed images, it is fundamental to preserve good reconstruction of these directional features. In our previous work, we proposed a construction of critically sampled perfect reconstruction transforms with directional vanishing moments imposed in the corresponding basis functions along different directions, called directionlets. In this paper, we show how to design and implement a novel efficient space-frequency quantization (SFQ) compression algorithm using directionlets. Our new compression method outperforms the standard SFQ in a rate-distortion sense, both in terms of mean-square error and visual quality, especially in the low-rate compression regime. We also show that our compression method, does not increase the order of computational complexity as compared to the standard SFQ algorithm.

On rate-distortion models for natural images and wavelet coding performance

Operational rate-distortion (RD) functions of most natural images, when compressed with state-of-the-art wavelet coders, exhibit a power-law behavior D alpha R(-gamma) at moderately high rates, with gamma being a constant depending on the input image, deviating from the well-known exponential form of the RD function D alpha 2(-xiR) for bandlimited stationary processes. This paper explains this intriguing observation by investigating theoretical and operational RD behavior of natural images. We take as our source model the fractional Brownian motion (fBm), which is often used to model nonstationary behaviors in natural images. We first establish that the theoretical RD function of the fBm process (both in 1-D and 2-D) indeed follows a power law. Then we derive operational RD function of the fBm process when wavelet encoded based on water-filling principle. Interestingly, both the operational and theoretical RD functions behave as D alpha R(-gamma). For natural images, the values of gamma are found to be distributed around 1. These results lend an information theoretical support to the merit of multiresolution wavelet compression of self-similar processes and, in particular, natural images that can be modelled by such processes. They may also prove useful in predicting performance of RD optimized image coders.

Interactive visualization of multiresolution image stacks in 3D

Conventional microscopy, electron microscopy, and imaging techniques such as MRI and PET commonly generate large stacks of images of the sectioned brain. In other domains, such as neurophysiology, variables such as space or time are also varied along a stack axis. Digital image sizes have been progressively increasing and in virtual microscopy, it is now common to work with individual image sizes that are several hundred megapixels and several gigabytes in size. The interactive visualization of these high-resolution, multiresolution images in 2D has been addressed previously [Sullivan, G., and Baker, R., 1994. Efficient quad-tree coding of images and video. IEEE Trans. Image Process. 3 (3), 327-331]. Here, we describe a method for interactive visualization of multiresolution image stacks in 3D. The method, characterized as quad-tree based multiresolution image stack interactive visualization using a texel projection based criterion, relies on accessing and projecting image tiles from multiresolution image stacks in such a way that, from the observer's perspective, image tiles all appear approximately the same size even though they are accessed from different tiers within the images comprising the stack. This method enables efficient navigation of high-resolution image stacks. We implement this method in a program called StackVis, which is a Windows-based, interactive 3D multiresolution image stack visualization system written in C++ and using OpenGL. It is freely available at http://brainmaps.org.

Image coding with geometric wavelets

This paper describes a new and efficient method for low bit-rate image coding which is based on recent development in the theory of multivariate nonlinear piecewise polynomial approximation. It combines a binary space partition scheme with geometric wavelet (GW) tree approximation so as to efficiently capture curve singularities and provide a sparse representation of the image. The GW method successfully competes with state-of-the-art wavelet methods such as the EZW, SPIHT, and EBCOT algorithms. We report a gain of about 0.4 dB over the SPIHT and EBCOT algorithms at the bit-rate 0.0625 bits-per-pixels (bpp). It also outperforms other recent methods that are based on "sparse geometric representation." For example, we report a gain of 0.27 dB over the Bandelets algorithm at 0.1 bpp. Although the algorithm is computationally intensive, its time complexity can be significantely reduced by collecting a "global" GW n-term approximation to the image from a collection of GW trees, each constructed separately over tiles of the image.

On the number of rectangular tilings

Adaptive multiscale representations via quadtree splitting and two-dimensional (2-D) wavelet packets, which amount to space and frequency decompositions, respectively, are powerful concepts that have been widely used in applications. These schemes are direct extensions of their one-dimensional counterparts, in particular, by coupling of the two dimensions and restricting to only one possible further partition of each block into four subblocks. In this paper, we consider more flexible schemes that exploit more variations of multidimensional data structure. In the meantime, we restrict to tree-based decompositions that are amenable to fast algorithms and have low indexing cost. Examples of these decomposition schemes are anisotropic wavelet packets, dyadic rectangular tilings, separate dimension decompositions, and general rectangular tilings. We compute the numbers of possible decompositions for each of these schemes. We also give bounds for some of these numbers. These results show that the new rectangular tiling schemes lead to much larger sets of 2-D space and frequency decompositions than the commonly-used quadtree-based schemes, therefore bearing the potential to obtain better representation for a given image.

Fast search for best representations in multitree dictionaries

We address the best basis problem--or, more generally, the best representation problem: Given a signal, a dictionary of representations, and an additive cost function, the aim is to select the representation from the dictionary which minimizes the cost for the given signal. We develop a new framework of multitree dictionaries, which includes some previously proposed dictionaries as special cases. We show how to efficiently find the best representation in a multitree dictionary using a recursive tree-pruning algorithm. We illustrate our framework through several examples, including a novel block image coder, which significantly outperforms both the standard JPEG and quadtree-based methods and is comparable to embedded coders such as JPEG2000 and SPIHT.

Rate-distortion optimized tree-structured compression algorithms for piecewise polynomial images

This paper presents novel coding algorithms based on tree-structured segmentation, which achieve the correct asymptotic rate-distortion (R-D) behavior for a simple class of signals, known as piecewise polynomials, by using an R-D based prune and join scheme. For the one-dimensional case, our scheme is based on binary-tree segmentation of the signal. This scheme approximates the signal segments using polynomial models and utilizes an R-D optimal bit allocation strategy among the different signal segments. The scheme further encodes similar neighbors jointly to achieve the correct exponentially decaying R-D behavior (D(R) - c(o)2(-c1R)), thus improving over classic wavelet schemes. We also prove that the computational complexity of the scheme is of O(N log N). We then show the extension of this scheme to the two-dimensional case using a quadtree. This quadtree-coding scheme also achieves an exponentially decaying R-D behavior, for the polygonal image model composed of a white polygon-shaped object against a uniform black background, with low computational cost of O(N log N). Again, the key is an R-D optimized prune and join strategy. Finally, we conclude with numerical results, which show that the proposed quadtree-coding scheme outperforms JPEG2000 by about 1 dB for real images, like cameraman, at low rates of around 0.15 bpp.

Combining fractal image compression and vector quantization

In fractal image compression, the code is an efficient binary representation of a contractive mapping whose unique fixed point approximates the original image. The mapping is typically composed of affine transformations, each approximating a block of the image by another block (called domain block) selected from the same image. The search for a suitable domain block is time-consuming. Moreover, the rate distortion performance of most fractal image coders is not satisfactory. We show how a few fixed vectors designed from a set of training images by a clustering algorithm accelerates the search for the domain blocks and improves both the rate-distortion performance and the decoding speed of a pure fractal coder, when they are used as a supplementary vector quantization codebook. We implemented two quadtree-based schemes: a fast top-down heuristic technique and one optimized with a Lagrange multiplier method. For the 8 bits per pixel (bpp) luminance part of the 512 x 512 Lena image, our best scheme achieved a peak-signal-to-noise ratio of 32.50 dB at 0.25 bpp.

Region-based fractal image compression

A fractal coder partitions an image into blocks that are coded via self-references to other parts of the image itself. We present a fractal coder that derives highly image-adaptive partitions and corresponding fractal codes in a time-efficient manner using a region-merging approach. The proposed merging strategy leads to improved rate-distortion performance compared to previously reported pure fractal coders, and it is faster than other state-of-the-art fractal coding methods.

Wavelet image compression--the quadtree coding approach

Perfect reconstruction, quality scalability, and region-of-interest coding are basic features needed for the image compression schemes used in telemedicine applications. This paper proposes a new wavelet-based embedded compression technique that efficiently exploits the intraband dependencies and uses a quadtree-based approach to encode the significance maps. The algorithm produces a losslessly compressed embedded data stream, supports quality scalability, and permits region-of-interest coding. Moreover, experimental results obtained on various images show that the proposed algorithm provides competitive lossless/lossy compression results. The proposed technique is well suited for telemedicine applications that require fast interactive handling of large image sets, over networks with limited and/or variable bandwidth.

Region adaptive subband image coding

We present a region adaptive subband image coding scheme using the statistical properties of image subbands for various subband decompositions. Motivated by analytical results obtained when the input signal to the subband decomposition is a unit step function, we analyze the energy packing properties toward the lower frequency subbands, edges, and the dependency of energy distribution on the orientation of the edges, in subband decomposed images. Based on these investigations and ideal analysis/synthesis filtering done in the frequency domain, the region adaptive subband image coding scheme extracts suitably shaped regions in each subband and then uses adaptive entropy-constrained quantizers for different regions under the assumption of a generalized Gaussian distribution for the image subbands. We also address the problem of determining an optimal subband decomposition among all possible decompositions. Experimental results show that visual degradations in the reconstructed image are negligible at a bit rate of 1.0 b/pel and reasonable quality images are obtainable at rates as low as 0.25 b/pel.

A fast exhaustive search algorithm for rate-constrained motion estimation

A fast exhaustive search algorithm for rate-constrained motion estimation is presented. The motion vectors are selected from a search window based on a rate-distortion criterion by successively eliminating the search positions depending on the rate constraint. The estimation performance of the proposed algorithm is identical to the performance of the rate-constrained full search algorithm, with considerable reduction in computation. Simulation results indicate that the number of matching calculations decreases as the constraint on the rate increases.

An optimal quadtree-based motion estimation and motion-compensated interpolation scheme for video compression

We propose an optimal quadtree (QT)-based motion estimator for video compression. It is optimal in the sense that for a given bit budget for encoding the displacement vector field (DVF) and the QT segmentation, the scheme finds a DVF and a QT segmentation which minimizes the energy of the resulting displaced frame difference (DFD). We find the optimal QT decomposition and the optimal DVF jointly using the Lagrangian multiplier method and a multilevel dynamic program. We introduce a new, very fast convex search for the optimal Lagrangian multiplier lambda(*), which results in a very fast convergence of the Lagrangian multiplier method. The resulting DVF is spatially inhomogeneous, since large blocks are used in areas with simple motion and small blocks in areas with complex motion. We also propose a novel motion-compensated interpolation scheme which uses the same mathematical tools developed for the QT-based motion estimator. One of the advantages of this scheme is the globally optimal control of the tradeoff between the interpolation error energy and the DVF smoothness. Another advantage is that no interpolation of the DVF is required since we directly estimate the DVF and the QT-segmentation for the frame which needs to be interpolated. We present results with the proposed QT-based motion estimator which show that for the same DFD energy the proposed estimator uses about 25% fewer bits than the commonly used block matching algorithm. We also experimentally compare the interpolated frames using the proposed motion compensated interpolation scheme with the reconstructed original frames.

On the reconstruction of quadtree data

Image compression schemes consist of compression and decompression phases. Often, the decompression phase includes mechanisms for improving the quality of the resulting image. Quadtree compression is one such type of compression. Reconstructed quadtree images can be blocky because of the nature of the compression method, unless additional processing, generally smoothing, is performed. We propose improvements over the reconstruction method described by Shusterman and Feder. The improvements consist of the introduction of a simpler and more effective 2 x 2 reconstruction filter to replace the suggested 3 x 3 filter, and the addition of a reconstruction threshold to preserve image edges. This method is compared experimentally to the original algorithm and also to JPEG compression in terms of complexity and resulting image quality.

Joint space-frequency segmentation using balanced wavelet packet trees for least-cost image representation

We examine the question of how to choose a space varying filterbank tree representation that minimizes some additive cost function for an image. The idea is that for a particular cost function, e.g., energy compaction or quantization distortion, some tree structures perform better than others. While the wavelet tree represents a good choice for many signals, it is generally outperformed by the best tree from the library of wavelet packet frequency-selective trees. The double-tree library of bases performs better still, by allowing different wavelet packet trees over all binary spatial segments of the image. We build on this foundation and present efficient new pruning algorithms for both one- and two-dimensional (1-D and 2-D) trees that will find the best basis from a library that is many times larger than the library of the single-tree or double-tree algorithms. The augmentation of the library of bases overcomes the constrained nature of the spatial variation in the double-tree bases, and is a significant enhancement in practice. Use of these algorithms to select the least-cost expansion for images with a rate-distortion cost function gives a very effective signal adaptive compression scheme. This scheme is universal in the sense that, without assuming a model for the signal or making use of training data, it performs very well over a large class of signal types. In experiments it achieves compression rates that are competitive with the best training-based schemes.

A video compression scheme with optimal bit allocation among segmentation, motion, and residual error

We present a theory for the optimal bit allocation among quadtree (QT) segmentation, displacement vector field (DVF), and displaced frame difference (DFD). The theory is applicable to variable block size motion-compensated video coders (VBSMCVC), where the variable block sizes are encoded using the QT structure, the DVF is encoded by first-order differential pulse code modulation (DPCM), the DFD is encoded by a block-based scheme, and an additive distortion measure is employed. We derive an optimal scanning path for a QT that is based on a Hilbert curve. We consider the case of a lossless VBSMCVC first, for which we develop the optimal bit allocation algorithm using dynamic programming (DP). We then consider a lossy VBSMCVC, for which we use Lagrangian relaxation, and show how an iterative scheme, which employs the DP-based solution, can be used to find the optimal solution. We finally present a VBSMCVC, which is based on the proposed theory, which employs a DCT-based DFD encoding scheme. We compare the proposed coder with H.263. The results show that it outperforms H.263 significantly in the rate distortion sense, as well as in the subjective sense.