206577228
Fast Trellis-Coded Color Quantization of Images
We examine color quantization of images using trellis-coded quantization (TCQ) in both the RGB domain and YUV domain. Together with a simple dithering scheme, an eight-bit trellis-coded color quantizer reproduces images that are visually indistinguishable from the 24-bit originals. It can be viewed as a predictive trellis-coded color quantization scheme. We also study trellis-coded vector quantization (TCVQ) for color quantization. Our proposed TCQ-based color quantization schemes are universal in the sense that no training or look-up table is needed. The complexity of TCQ is linear with respect to image size, making trellis-coded color quantization suitable for color printing, real-time interactive graphics and window-based display environment.
9060129
Extended Depth-of-Field Microscope Imaging: MPP Image Fusion VS. WAVEFRONT CODING
Biomedical specimens thicker than the microscope depth-of-field (DOF) produces images of limited quality where a part of the specimen is in focus and others out of focus. Even the best in-focus image always contains objects that are blurred. These blurred contents make the quantitative and accurate analysis of the specimen difficult. The problem can be remedied by extending the DOF of the imaging system. One way to achieve this is to apply digital image fusion, a software technique that combines multiple images into a carefully synthesized image. Another way, albeit more expensive, is to incorporate modification in the optical system. In this paper we describe an extended DOF method that is based on multiscale pointwise product (MPP) image fusion, and compare it with the state-of-the-art wavefront coding technique which involves optical modification. We show competitive performance of our method and contrast its pros and cons with those of the wavefront coding.
15323037
Successive refinement for the Wyner-Ziv problem and layered code design
We examine successive refinement for the Wyner-Ziv problem described in a recent paper by Steinberg and Merhav, where the authors showed that if the side information for all stages is identical, then the jointly Gaussian source with squared error distortion measure is successively refinable. We first extend this result to the case where the difference between the source and the side information is Gaussian and independent of the side information. As a byproduct, we give an alternative proof that the Wyner-Ziv problem for these sources has no rate loss-a result that was recently shown by Pradhan et al. through invoking the duality between the Gaussian Wyner-Ziv problem and the Costa problem. We then perform layered Wyner-Ziv code design for this general type of source based on nested scalar quantization, bit-plane coding, and low-density parity check (LDPC) code-based Slepian-Wolf coding (source coding with side information). We show that density evolution can be used to analyze the Slepian-Wolf code performance, provided that certain symmetry conditions, which have been dubbed dual symmetry, are satisfied by the hypothetical channel between the source and the side information. We also show that the dual symmetry condition is indeed satisfied by the hypothetical channel in our Slepian-Wolf coding setup. This justifies the use of density evolution in our LDPC code-based Slepian-Wolf code design for Wyner-Ziv coding. For the jointly Gaussian source, our layered coder performs 1.29 to 3.45 dB from the Wyner-Ziv bound for rates ranging from 0.47 to 4.68 bits per sample. When the side information is Laplacian and the source equals the side information plus an independent Gaussian noise term, our layered coder performs 1.33 to 3.90 dB from the Wyner-Ziv bound for rates ranging from 0.48 to 4.64 bits per sample.
19385806
Lossy-to-lossless compression of medical volumetric data using three-dimensional integer wavelet transforms
We study lossy-to-lossless compression of medical volumetric data using three-dimensional (3-D) integer wavelet transforms. To achieve good lossy coding performance, it is important to have transforms that are unitary. In addition to the lifting approach, we first introduce a general 3-D integer wavelet packet transform structure that allows implicit bit shifting of wavelet coefficients to approximate a 3-D unitary transformation. We then focus on context modeling for efficient arithmetic coding of wavelet coefficients. Two state-of-the-art 3-D wavelet video coding techniques, namely, 3-D set partitioning in hierarchical trees (Kim et al., 2000) and 3-D embedded subband coding with optimal truncation (Xu et al., 2001), are modified and applied to compression of medical volumetric data, achieving the best performance published so far in the literature-both in terms of lossy and lossless compression.
8002270
Audio coding and image denoising based on the nonuniform modulated complex lapped transform
Xiong and Malvar recently introduced a nonuniform modulated complex lapped transform (NMCLT) with good time-localization and controllable frequency resolution by using an oversampled nonuniform filter bank to generate its real and the imaginary components. In this paper, we first show that oversampling in the NMCLT is not necessary in theory but a by-product of fast implementation in practice. We also point out that the amount of oversampling, which can be flexibly controlled, depends on the application. We then describe in detail the implementation of the inverse transform, which was not addressed clearly by Xiong and Malvar. We present the first applications of the NMCLT to audio coding and image denoising. A scalable audio coder has been implemented by controlling the amount of oversampling and exploiting redundancy among the NMCLT coefficients via predictive coding. Experimental results show that the audio coder reduces pre-echoes and improves the sound quality of audio clips with transient sounds. A simple denoising algorithm based on the NMCLT has also been devised to provide images with better visual quality than those obtained with wavelet-based soft thresholding.
6799009
On packetization of embedded multimedia bitstreams
We study the problem of packetizing embedded multimedia bitstreams to improve the error resilience of source (compression) codes. This problem is important because of the increasing popularity of embedded compression methodology and its suitability for scalable streaming media over IP or/and mobile IP. We study various packetization schemes against packet erasure at both low and high bit rates. Maximizing packetization efficiency for embedded bitstreams is formulated as a discrete optimization problem and globally optimal packetization (OP) algorithms are proposed under different settings. Suboptimal packetization algorithms are also devised to reduce the complexity of the OP algorithms. In order to assess their effectiveness, the proposed packetization algorithms are used to packetize embedded image and video bitstreams with simulated packet loss. Experimental results show that our OP algorithms slightly outperforms suboptimal ones. In addition to confirming the superiority of the OP algorithms, these results also provide justification of heuristic packetization methods published in the literature.
16467768
Automatic Leveling System for E-Learning Examination Pool Using Entropy-Based Decision Tree
In this paper, we propose an automatic leveling system for e-learning examination pool using the algorithm of the decision tree. The automatic leveling system is built to automatically level each question in the examination pool according its difficulty. Thus, an e-learning system can choose questions that are suitable for each learner according to individual background. Not all attributes are relevant to the classification, in other words, the decision tree tells the importance of each attribute.
6666618
Low-Power Design for Real-Time Systems
Real-time Systems often are located in the special environments where the power consumption is a big concern. Upon presence of timing constraints, the low power design on the real-time systems has significant impact on the performance as well as the schedulability of the systems. The system developers are facing the challenges for reducing the power consumption and meeting the timing constraints in the real-time systems.This paper represents one of few attempts to address the issue of the low power design on real-time systems. We present two power reduction methods: one is at the software compilation level and the other at the operating system level. Given a real-time program, an inter-instruction power reduction technique is proposed to transform the program to another one with lower power consumption. In addition, a scheduling algorithm for real-time operating systems is proposed to reschedule real-time programs when the execution time of the programs is changed. Therefore, the proposed scheduling algorithm works together with the proposed power reduction technique to make sure all programs meet their deadlines and to improve the system schedulability. We also evaluate the performance of the proposed inter-instruction reduction method by comparing it with the cold scheduling algorithm and show that the proposed method outperforms the cold scheduling algorithm and reduces more energy power.
5724521
Motorcycle Graphs and Straight Skeletons
We present a new algorithm to compute motorcycle graphs. It runs in $O(n \sqrt{n}\log n)$ time when n is the number of motorcycles. We give a new characterization of the straight skeleton of a nondegenerate polygon. For a polygon with n vertices and h holes, we show that it yields a randomized algorithm that reduces the straight skeleton computation to a motorcycle graph computation in expected $O(n\sqrt{h+1}\log^2 n)$ time. Combining these results, we can compute the straight skeleton of a nondegenerate polygon with h holes and with n vertices, among which r are reflex vertices, in $O(n\sqrt{h+1}\log^2 n+r \sqrt{r} \log r)$ expected time. In particular, we cancompute the straight skeleton of a nondegenerate polygon with n vertices in $O(n\sqrt{n}\log^2n)$ expected time.
15245491
Efficient Expected-Case Algorithms for Planar Point Location
Planar point location is among the most fundamental search problems in computational geometry. Although this problem has been heavily studied from the perspective of worst-case query time, there has been surprisingly little theoretical work on expected-case query time. 
 
We are given an n-vertex planar polygonal subdivision S satisfying some weak assumptions (satisfied, for example, by all convex subdivisions). 
 
We are to preprocess this into a data structure so that queries can be answered efficiently. We assume that the two coordinates of each query point are generated independently by a probability distribution also satisfying some weak assumptions (satisfied, for example, by the uniform distribution). 
 
In the decision tree model of computation, it is well-known from information theory that a lower bound on the expected number of comparisons is entropy(S). We provide two data structures, one of size O(n2) that can answer queries in 2 entropy(S) + O(1) expected number of comparisons, and another of size O(n) that can answer queries in (4 + O(1/√log n)) entropy(S)+O(1) expected number of comparisons. These structures can be built in O(n2) and O(n log n) time respectively. Our results are based on a recent result due to Arya and Fu, which bounds the entropy of overlaid subdivisions.
16505104
Approximate minimum weight Steiner triangulation in three dimensions
ApproximateMinimumWeightSteinerTriangulationinThreeDimensionsSiu-WingChengyTamal K. DeyAbstractDicultyofminimumweighttriangulationap oinsetinR2is well known.In this pap er we study the minimumweight triangulation problem for p olyhedra and general ob-stacle set in three dimensions.The weight of a triangulationin three dimensionsis assumed to b e the total surface areaof alltrianglesinvolved.It isshownthat ap olyhedronPof sizencan b e triangulated withO(2log) tetrahedra intimeO(n2log3) approximating the minimum weight trian-gulation ofPwithin a constant factor. No such prior resultisknown.Thesameb oundsalsoholdfor a3Dp ointsettriangulationallowingSteiner p oints.We consider anothersetting called general obstacle set, where the convex hull ofa set ofntrianglesis triangulatedconforming to the inputtriangles.In thiscase we show thatour metho dpro ducesa triangulati onof sizeO(n3log) in time) ap-proximating the weight of the minimum wt triangulationwithin a constant factor. This is a considerable improvementover theO(n6) b ound known for this case [3]. It is shown in[3] that minimumweighttriangulationisgo o dfor averagecase ray sho oting in three dimensions.This further substan-tiates the signi cance of our result.1Intro ductionThe minimum weight triangulation (MWT) problem ismostwell-knownintheplane,whereatriangulationwiththeminimumtotaledgelengthissoughtfora2Dp ointset.Theproblemisnotknowntob eNP-hard but no p olynomial-time algorithm is known.Re-centlyanapproximation algorithm withconstantfac-tor p erformance guarantee has b een designed for MWTby Levcop oulos and Krznaric[10].In another versionof theproblem Steinerp ointsareallowed andamini-mum weight Steinertriangulation (MWST)among allp ossibleSteinertriangulationsisdesired.Inparticu-lar, MWT is also a Steiner triangulation but with zeroSteiner p oints.Eppstein [8] showed how to approximatethe MWST of a 2Dp oint set within a constant factor.Instead of a 2Dp oint set, general inputs such as planarstraight line graphs (PSLG) have also b eenconsideredDepartment of Computer Science, HKUST, Hong Kong.e-mail: scheng@cs.ust.hkyDepartmentofCSE,I ITKharagpur,Kharagpur721302,India. e-mail: dey@cse.iitkgp.ernet.infor their applications in ray sho oting [3, 7]. A triangula-tion of a PSLG is the decomp osition of the convex hullof its verticeswhere the input line segments app ear asedges.When Steiner p oints are allowed these segmentsmay app ear as union of edges.Aronov and Fortune [3]observe that the technique of [8] applies to this case topro duce a p olynomial size triangulation approximatingMWSTwithinaconstantfactor.Inthesp ecialcasewhen the input PSLG is a p olygon p ossibly with holes,Cheng and Lee [7] presented an algorithm with b oth sizeand running timeO(nlog), whereis the numb er ofedges.Thetriangulationofap ointsetin3Disthedecomp osition of its convex hull into disjoint tetrahedra.The weight of the triangulation is the sum of the area ofthe triangles in it.Instead of p oint sets, the input mayconsist of a set of triangles with disjoint relative interior,acounterpartofPSLGin3D.Inthissettingcalledgeneral obstacle set, a minimum weight triangulation ofthe convex hull is sought where the input triangles haeto b e conformed.A sp ecial case arises when the inputtrianglesformtheb oundaryofap olyhedronwhoseinterioristob etriangulatedwithminimumweight.Noticethattheformulationofminimumweighttriangulation problem in these cases must allow Steinerp oints since there are arrangements of triangles in threespace such as the b oundary of Schonardt p olyhedron forwhich no triangulation is p ossible without Steiner p oints[12].WeconsiderMWSTproblemforthreedi erentcategories of inputs:p olyhedra, p oint sets, and generalobstaclesets.Of course,thisleaves op entheproblemof MWT of a 3Dp oint set since a p oint set can alwaysb e triangulated without Steiner p oints.ResultonMWSTprobleminthreedimensionsisscarce.Eppstein, in his pap er [8], acknowledges the dif- culty of the problem and observes the obstacles in gen-eralizing a metho d working in two dimension. When thelengths of the edges are taken as weights, he shows thatthemetho dcanb emo di edtopro duceanO(logn)-factorapproximation toMWSTofap ointset.How-ever,withareasoftrianglestakenastheweights,metho d could not b e generalized.Aronov and Fortune[3], building up on the technique of Eppstein showed hotopro duceanO(n6)sizetriangulation approximatingthe MWST of a general obstacle set.They argued that1