12511043
Real-time lossless compression of mosaic video sequences
This paper presents a simple, fast coding technique for lossless compression of mosaic video data. The design of a video codec needs to strike a balance between the compression performance and the codec throughput. Aiming to make the encoding throughput high enough for real-time lossless video compression, we propose a hybrid scheme of inter and intraframe coding. Interframe predictive coding is invoked only when the motion between adjacent frames is modest and a simple motion compensation operation can significantly improve the compression performance. Otherwise, still frame compression is performed to keep the complexity low. Experimental results show that the proposed scheme achieves higher lossless video compression ratio than existing methods such as JPEG-LS and JPEG-2000.
7762229
Edge detection by scale multiplication in wavelet domain
This paper proposes a wavelet based edge detection scheme by scale multiplication. The dyadic wavelet transforms at two adjacent scales are multiplied as a product function to magnify the edge structures and suppress the noise. Unlike many multiscale techniques that first form the edge maps at several scales and then synthesize them together, we determined the edges as the local maxima directly in the scale product after an efficient thrsholding. It is shown that the scale multiplication achieves better results than either of the two scales, especially on the localization performance. The dislocation of neighboring edges is also improved when the width of detection filter is set large to smooth noise. Experiments on natural images are compared with the Laplacian of Gaussian and Canny edge detection algorithms.
11724747
Wavelet estimation of fractional Brownian motion embedded in a noisy environment
This correspondence proposes a wavelet-based fractional Brownian motion (fBm) signal estimation scheme. Despite the fact that wavelet transform approximately whitens the fBm processes, it is observed that statistical dependencies still exist across adjacent wavelet scales and between neighboring wavelet coefficients. These dependencies can be exploited to improve the estimation of fBm signals embedded into noise. The idea is to reorganize the wavelet coefficients into a scale-time mixture model and then carry out the minimum mean-square-error estimation (MMSE) using the model. Experiments show that the proposed scheme obtains better estimates than Wornell and Oppenheim's algorithm, in which the wavelet dependencies are not utilized.
12034638
A block-based inter-band lossless hyperspectral image compressor
We propose a hyperspectral image compressor called BH which considers its input image as being partitioned into square blocks, each lying entirely within a particular band, and compresses one such block at a time by using the following steps: first predict the block from the corresponding block in the previous band, then select a predesigned code based on the prediction errors, and finally encode the predictor coefficient and errors. Apart from giving good compression rates and being fast, BH can provide random access to spatial locations in the image. We hypothesize that BH works well because it accommodates the rapidly changing image brightness that often occurs in hyperspectral images. We also propose an intra-band compressor called LM which is worse than BH, but whose performance helps explain BH's performance.
16021441
Hybrid inter- and intra-wavelet scale image restoration
This paper exploits both the inter- and intra-scale interdependencies that exist in wavelet coefficients to improve image restoration from noise-corrupted data. Using an over-complete wavelet expansion, we group the wavelet coefficients with the same spatial orientation at several scales. We then apply the linear minimum mean squared-error estimation to smooth noise. This scheme exploits the inter-scale correlation information of wavelet coefficients. To exploit the intra-scale dependencies, we calculate the co-variance matrix of each vector locally using a centered square-shaped window. Experiments show that the proposed hybrid scheme significantly outperforms methods exploiting only the intra- or inter-scale dependencies. The performance of noise removal also depends on wavelet filters. In our experiments a biorthogonal wavelet, which best characterizes the image inter-scale dependencies, achieves the best results.
1918361
Canny edge detection enhancement by scale multiplication
The technique of scale multiplication is analyzed in the framework of Canny edge detection. A scale multiplication function is defined as the product of the responses of the detection filter at two scales. Edge maps are constructed as the local maxima by thresholding the scale multiplication results. The detection and localization criteria of the scale multiplication are derived. At a small loss in the detection criterion, the localization criterion can be much improved by scale multiplication. The product of the two criteria for scale multiplication is greater than that for a single scale, which leads to better edge detection performance. Experimental results are presented.
15318356
Variance estimation over sliding windows
Capturing characteristics of large data streams has received considerable attention. The constraints in space and time restrict the data stream processing to only one pass (or a small number of passes). Processing data streams over sliding windows make the problem more difficult and challenging. In this paper, we address the problem of maintaining ∈-approximate variance of data streams over sliding windows. To our knowledge, the best existing algorithm requires O(1/∈2 log N) space, though the lower bound for this problem is Ω(1/∈ log N). We propose the first ∈-approximation algorithm to this problem that is optimal in both space and worst case time. Our algorithm requires O(1/∈ log N) space. Furthermore, its running time is O(1) in worst case.
14817235
Placement Algorithm in Analog-Layout Designs
Analog macrocell placement is an NP-hard problem. This paper presents an attempt to solve this problem by using the optimization flow of a genetic algorithm (GA) enhanced by simulated annealing (SA). The bit-matrix representation is employed to improve the search efficiency. In particular, to reduce the solution space without degrading search opportunities, the technique of cell slide is deployed to transform an absolute placement to a relative placement. Following this cell-slide process, it is proved that, for an initial placement, there always exists a solution that can guarantee no occurrence of overlaps among cells and meet any applicable symmetry constraints pertaining to analog layouts. For the optimization of the algorithm parameters, the fractional factorial experiment using an orthogonal array has been conducted, and the exact parameter values are determined using a meta-GA approach. The experimental results show that, compared with the SA approach, the proposed algorithm consumes less computation time while generating higher quality layouts, comparable to expert manual placements
9504363
The p-hub center allocation problem
Abstract The p -hub center problem is to locate p hubs and to allocate non-hub nodes to hub nodes such that the maximum travel time (or distance) between any origin–destination pair is minimized. We address the p -hub center allocation problem, a subproblem of the location problem, where hub locations are given. We present complexity results and IP formulations for several versions of the problem. We establish that some special cases are polynomially solvable.
100573
A hierarchical method for real-time distance computation among moving convex bodies
Abstract This paper presents the Hierarchical Walk , or H-Walk algorithm, which maintains the distance between two moving convex bodies by exploiting both motion coherence and hierarchical representations. For convex polygons, we prove that H-Walk improves on the classic Lin–Canny and Dobkin–Kirkpatrick algorithms. We have implemented H-Walk for moving convex polyhedra in three dimensions. Experimental results indicate that, unlike previous incremental distance computation algorithms, H-Walk adapts well to variable coherence in the motion and provides consistent performance.
5771208
Image annotation by large-scale content-based image retrieval
Image annotation has been an active research topic in recent years due to its potentially large impact on both image understanding and Web image search. In this paper, we target at solving the automatic image annotation problem in a novel search and mining framework. Given an uncaptioned image, first in the search stage, we perform content-based image retrieval (CBIR) facilitated by high-dimensional indexing to find a set of visually similar images from a large-scale image database. The database consists of images crawled from the World Wide Web with rich annotations, e.g. titles and surrounding text. Then in the mining stage, a search result clustering technique is utilized to find most representative keywords from the annotations of the retrieved image subset. These keywords, after salience ranking, are finally used to annotate the uncaptioned image. Based on search technologies, this framework does not impose an explicit training stage, but efficiently leverages large-scale and well-annotated images, and is potentially capable of dealing with unlimited vocabulary. Based on 2.4 million real Web images, comprehensive evaluation of image annotation on Corel and U. Washington image databases show the effectiveness and efficiency of the proposed approach.