Block prediction and reference frame generation play a central role in contemporary video codecs and hold significant potential for improving compression efficiency. For motion vectors of varying reliability, directly averaging the bi-directional reference blocks introduces noise in block prediction. In advanced video codecs such as AV2, the generation of co-located reference frames (CLRFs) within the temporal interpolated prediction (TIP) module is also performed at the block level. However, the imprecise vectors in the motion field cause the associated block pairs to exhibit weak correlation in their high-frequency components, which is not addressed by existing methods. This creates an opportunity for the transformdomain temporal prediction (TDTP) approach. This work proposes an adaptive TDTP framework for block prediction. Independent linear predictors (LPs) are trained for each AC coefficient to estimate the corresponding temporal correlation. A novel adaptive backward updating scheme for linear predictors is employed, in which reconstructed blocks are used to update the statistics and refine LP parameters without introducing additional bitrate overhead. Simulation results on the TIP module in AV2 demonstrate that the proposed approach effectively adapts to frame statistics and enhances the efficiency of compound inter-prediction.

Encoding video frames at adaptive resolutions has been shown to be an effective strategy, as it balances the trade-off between side information and residual data based on frame size and content. Reference Picture Resampling (RPR) in the Versatile Video Coding (H.266/VVC) standard allows for motion compensation between frames with different resolutions, overcoming the limitation that resolution switching points must occur at intra random-access points (IRAP), and that all frames within a closed GOP must be encoded at a single resolution. Frame rescaling is a critical step in RPR; however, applying a single upscaling filter to all video frames of different resolutions is not ideal. In this paper, an adaptive upscaling filter selection scheme is proposed, which incorporates Wiener filter trained at the frame level. The rate-distortion (RD) performance of various upscaling filters is compared to determine the optimal adaptive filter. The Wiener filter coefficients are reduced and compressed using predictive coding. Experimental results on VVC test model (VTM) 23.3 show average BD rate gains of 0.33% for 4K, 2.15% for 1080p and 2.11% for 480p video sequences at a 2.0x RPR scaling ratio under random-access configurations. At a 1.5x RPR scaling ratio, the BD rate gains are 0.57% for 4K, 2.22% for 1080p and 4.71% for 480p video sequences.

The challenge of coding delay is becoming increasingly recognized as a barrier to the broader implementation of Higher Order Ambisonics (HOA), which is a highly flexible format for spatial audio encoding and reproduction. A low latency is essential for various applications, such as virtual reality, interactive gaming, and live online music sessions. Unfortunately, significant strides in the development of spatial audio codecs often compromise on latency to enhance compression efficiency. This work presents a low-delay codec designed for the compression of HOA signals. The codec uses a combination of singular value decomposition, short-term linear prediction, cascaded long-term prediction, and sub-band coding, as well as entropy coding, in order to maximally compress HOA signals while maintaining a low delay. A variety of configurations allow for algorithmic delays between 54 samples to 206 samples, at the cost of bitrate given a fixed quality level. The proposed codec outperforms the low-delay implementation of a standard codec for HOA lossy compression, both in terms of delay and bitrate at medium and higher quality levels.

Coding delay has emerged as a significant obstacle to wider adoption of Higher Order Ambisonics (HOA), a promising flexible format employed in representation and coding of spatial audio. Low delay is critical in many applications, such as virtual reality, gaming, and online music performance, a good subset of which further require lossless compression. However, major advances in spatial audio codec design often sacrifice low delay in order to maximize compression gains. We present a new lossless, ultra-low delay HOA codec, optimized to take advantage of both the spatial and temporal redundancies in HOA data, while maintaining an extremely low delay. The presented codec has an algorithmic delay of one single sample, at the cost of increased computational complexity. This codec outperforms the state-of-the-art for lossless, low-delay HOA coding, both in terms of delay and bitrate.

This paper proposes an effective universal (on-the-Hy’’ mechanism for stochastic codebook generation in lossy coding of Markov sources. Earlier work has shown that the ratedistortion bound can be asymptotically achieved by a “natural type selection” (NTS) mechanism that iteratively considers asymptotically long source strings (from an unknown distribution P) and regenerates the codebook from a distribution obtained within a maximum likelihood distribution estimation framework, based on observation of a set of K codewords that “d-match’’ (i.e., satisfy the distortion constraint for) a respective set of K independently generated source words. This result was later generalized, in a straightforward manner, to account for source memory, by considering the source as a vector source, i.e., a sequence of super-symbols from a corresponding super-alphabet. While ensuring asymptotic optimality, this extension suffered from a significant practical flaw: it requires asymptotically long vectors or super-symbols, hence exponentially large super-alphabet, in order to approach the rate-distortion bound, even for finite memory sources, e.g., Markov sources. Such exponentially large super-alphabet implies that even a single NTS iteration is intractable, thus compromising the promise of NTS to approach the rate-distortion function, in practice, for sources with memory. This work describes a considerably more efficient and tractable mechanism to achieve asymptotically optimal performance given a prescribed memory constraint, within a practical framework tailored to Markov sources. Specifically, the algorithm finds, asymptotically, the optimal codebook reproduction distribution, within a constrained set of distributions satisfying a prescribed Markovian property, e.g., of the same order as the source, which achieves the minimum per letter coding rate while maintaining a specified distortion level.

Machine learning applications have exploded in recent years due to the availability of huge data sets as well as advances in computational and storage capabilities. Although successful methods have been proposed to reduce learning system complexity while maintaining required accuracy levels, theoretical understanding of the underlying trade-offs remains elusive. In this paper, the classical supervised learning problem is reformulated within a rate-distortion framework. It provides insights into crucial accuracy-complexity trade-offs, by considering the overall learning system as consisting of two components. The first is tasked with extracting (learning) from the source the minimal number of information bits necessary to ultimately achieve the prescribed output accuracy. The learned bits are then used to retrieve the desired output from the second component, an appropriately designed codebook. The premise here is that an optimal system is characterized by having to learn the minimum amount of information from the source, just sufficient to yield the system output at the desired precision, which implies efficiency in terms of system complexity, generalization and training data requirements. The design and training of such a reformulated system is detailed in this paper, and asymptotically optimal performance achieving the rate-distortion bound is established.

With the advent of immersive multimedia technologies, interest in dynamic point cloud compression standards, such as video-based point cloud compression (V-PCC), has been steadily growing. At the core of V-PCC, conventional video codecs such as High Efficiency Video Coding are employed for encoding the geometry video, attribute video and the occupancy map. Standard video codecs perform temporal prediction using motion compensation by simple pixel-copying from the reference frame. However, conventional pixel-domain prediction does not exploit spatial correlation within the block. This is highly sub-optimal especially due to large homogeneous regions in the geometry video. In this paper, spatial decorrelation is first achieved via the Discrete Cosine Transform. Prediction is then performed in the transform domain, where the observed variation in temporal correlation across frequencies is exploited for a more accurate prediction. Design of the correlation filters required for this procedure poses challenges. The inherent instability in closed-loop design is tackled using the Asymptotic Closed Loop paradigm which uses an iterative open-loop algorithm that asymptotically converges to closed-loop operation. Experimental results on geometry videos generated from common test conditions show significant bitrate savings of up to 5.8% (about 3% on average) and highlight the efficacy of our approach.

Most video coding systems employ separable transforms due to their low computational complexity and storage requirements, and despite their sub-optimal decorrelating capabilities. To achieve better decorrelation, recent codecs further apply a non-separable secondary transform to low-frequency primary transform coefficients of the intra-prediction residual. This paper focuses on effective design of non-separable secondary transforms for the inter-prediction residual. As the combination of primary and secondary transforms yields a set of ultimate transform coefficients for which the default zig-zag scan order is sub-optimal, we complement the secondary transform design with the design of corresponding coefficient scanning order modes that facilitate effective entropy coding. A critical stability challenge in this joint design, due to error propagation through the codec's prediction loop, is circumvented by leveraging the asymptotic closed loop (ACL) design paradigm. ACL operates in open-loop in each iteration to ensure stability, but in a manner that ultimately converges to parameter optimization for closed-loop operation. Experimental results show an average gains in BD rate of 0.76% for CIF and 0.41% for HD sequences, over the AV1 codec (libaom).

Adaptive prediction is an important tool for efficient compression of non-stationary signals. A common approach to achieve adaptivity is to switch between a set of prediction modes, designed to capture variations in signal statistics. The design poses several challenges including: i) catastrophic instability due to statistical mismatch driven by propagation through the prediction loop, and ii) severe non-convexity of the cost surface that is often riddled with poor local minima. Motivated by these challenges, this paper presents a near-optimal method for designing prediction modes for adaptive compression. The proposed method builds on a stable, open-loop platform, but with a subterfuge that ensures that the design is asymptotically optimized for closed-loop operation. The non-convexity is handled by deterministic annealing, a powerful optimization tool to avoid poor local minima. To demonstrate the impact of the proposed approach on practical applications, we consider adaptive, transform-domain predictor design for enhancing standard video coding. Experimental results validate the benefits of the proposed design in terms of significant performance gains for both predictive compression systems in general and video coding in particular.

Spherical video coding is critical to the success of many virtual reality and related applications. This paper focuses on an important class of spherical videos whose dynamics involve camera motion. A common approach to spherical video coding is to project from the sphere onto a plane (or planes), where a standard video coder is applied. The projection induces warping resulting in complex non-linear motion in the projected domain that severely comprises the performance of motion models in standard coders. To overcome this shortcoming, we propose a new motion model that captures the motion field on the sphere, and capitalizes on insights into the perceived motion on the sphere due to camera translation. Specifically, surrounding static points are perceived as moving along their respective geodesics, which all intersect at the points where the camera velocity vector intersects the sphere. We analyze the rate of translation along geodesics and its dependence on the elevation of a pixel on the sphere with respect to the camera velocity vector. The analysis leads to a motion vector modulation scheme that perfectly captures the perceived motion of each pixel. Complementary to the new motion model, we propose a search grid tailored to capture expected geodesic motion on the sphere for effective motion estimation. The proposed method yields significant bit-rate savings over employing standard HEVC after projection, which validates its efficacy.

This paper proposes an effective and asymptotically optimal framework for stochastic, adaptive codebook regeneration for sequential (“on the fly”) lossy coding of continuous alphabet sources. Earlier work has shown that the rate-distortion bound can be asymptotically achieved for discrete alphabet sources, by a “natural type selection” (NTS) algorithm. At each iteration$n$, a maximum-likelihood framework is used to estimate the reproduction distribution most likely to generate the empirical types of a sequence of$K$length-$l$codewords that respectively “d-match” (i.e., are within distortion$d$from) a sequence of$K$length-$\ell$source words. The reproduction distribution estimated at iteration$n$is used to regenerate the codebook for iteration$n+1$. The sequence of reproduction distributions was shown to converge, asymptotically in$K, n$, and$\ell$, to the optimal distribution that achieves the rate-distortion bound for discrete alphabet sources. This work generalizes the NTS framework to handle sources over more general (e.g., continuous) alphabet spaces, which often preclude a natural interpretation of the concept of “type”. We show, for continuous alphabet sources and fixed block length$\ell$, that as$K\rightarrow \infty$and$n \rightarrow \infty$, the sequence of estimated reproduction distributions converges, in the weak convergence sense, to a distribution that achieves the rate-distortion bound, albeit for an auxiliary distortion measure introduced as subterfuge to effectively impose a maximum distortion constraint over$K$blocks. Leveraging this result, we establish that the sequence of reproduction distributions converges, asymptotically in$\ell$, to the optimal codebook reproduction distribution$Q^{\ast}$that achieves the rate-distortion bound, with respect to the original distortion measure.

Directional beamforming with large antenna arrays is key to mitigating the substantial signal loss experienced at the millimeter wave frequency band, important to fifth generation (5G) cellular systems and next generation wireless local area networks, where it entails a significant increase in the number of beams. This paper is motivated by the realization that the underlying problem of finding the optimal set of beam steering directions will benefit from fundamental signal processing methodologies, and specifically from basic principles and algorithms for cluster analysis. Earlier work by authors established the equivalence between the problem of optimizing a set of beam steering directions and the classical problems of clustering and quantizer design, albeit with an unusual distortion measure. Subsequently in [1], a k-means-like approach was derived to optimize beam steering directions and guarantee convergence to at least locally optimal solution. The main contribution of this work is the derivation of a global optimization approach within the deterministic annealing framework, to circumvent poor local optima that riddle the cost surface. Simulation results show that the approach delivers considerable gains over the baseline uniform beam steering technique, specifically, up to 6 dB and 13 dB gains, in terms of average and 10th percentile of the power array factor, respectively, as well as up to 6.5 dB gain in the average Signal-to-Noise Ratio (SNR).

Bi-directional motion compensated prediction is widely utilized in video coding. Conventionally, the encoder searches for two motion vectors pointing to reference frames in both directions, and transmits these motion vectors to the decoder. Recognizing that the two reference frames are already available to the decoder, prior work proposed decoder-side motion estimation to extract motion information or optical flow, at the cost of dramatic increase in decoder complexity. This paper proposes a novel bi-directional motion compensation mode that efficiently utilizes the motion information that is already available to the decoder, without recourse to extensive search. An estimation theory based approach is proposed and utilized to provide a high quality prediction, which adaptively combines contributions from multiple motion-compensated references. Experimental results show that the proposed method, while yielding a greatly reduced decoder side complexity, introduces a significant coding gain for a diverse set of video sequences.

Many virtual and augmented reality applications depend critically on efficient compression of spherical videos. Current approaches apply a projection geometry to map a spherical video onto the plane(s), wherein a standard codec can be used for compression. Video coders employ simple pixel copying from reference frames for inter-prediction, which ignores underlying spatial correlations, and is hence suboptimal. A novel paradigm of transform domain temporal prediction (TDTP) was developed previously in our lab to effectively overcome this suboptimality of standard video coding. This paper is motivated by the observation that projected spherical videos exhibit significantly more statistical variation due to i) the choice of projection geometry and ii) position of the block on the sphere, which reflect variations in sampling density and various statistical features. To account for such variations, we propose geometry and region adaptive TDTP that is tailored to spherical videos. For a given geometry, the sphere is divided into regions, according to expected signal statistics, and prediction filters are designed for each region. Experimental results show significant performance gains as evidence for the efficacy of TDTP in spherical video coding.

Transform coding is a key component of video coders, tasked with spatial decorrelation of the prediction residual. There is growing interest in adapting the transform to local statistics of the inter-prediction residual, going beyond a few standard trigonometric transforms. However, the joint design of multiple transform modes is highly challenging due to critical stability problems inherent to feedback through the codec's prediction loop, wherein training updates inadvertently impact the signal statistics the transform ultimately operates on, and are often counter-productive (and sometimes catastrophic). It is the premise of this work that a truly effective switched transform design procedure must account for and circumvent this shortcoming. We introduce a data-driven approach to design optimal transform modes for adaptive switching by the encoder. Most importantly, to overcome the critical stability issues, the approach is derived within an asymptotic closed loop (ACL) design framework, wherein each iteration operates in an effective open loop, and is thus inherently stable, but with a subterfuge that ensures that, asymptotically, the design approaches closed loop operation, as required for the ultimate coder operation. Experimental results demonstrate the efficacy of the proposed optimization paradigm which yields significant performance gains over the state-of-the-art.

In this paper, we present new results on the achievable rate-distortion regions in networked scalable compression problems, based on a flexible codebook generation and binning method. First, we consider the problem of scalable coding in the presence of decoder side information, for which the prior work analyzed the two important cases the degraded side information where source X and the side information variables (Y1, Y2) form a Markov chain in the order of either X - Y1-Y2or X - Y2- Y1. First, we present an example non-Markov side information scenario where the proposed coding strategy achieves a strictly larger rate-distortion region compared to prior work. We then consider the problem of multi-user successive refinement where different users that are connected to a central server via links with different noiseless capacities strive to reconstruct the source in a progressive fashion. It is shown that a prior rate-distortion region is suboptimal in general, albeit its optimality for a Gaussian source with MSE distortion, and the proposed coding scheme achieves points beyond the achievable region of prior work.

This paper proposes an effective mechanism for stochastic codebook generation for lossy coding, using source examples. Earlier work has shown that the rate-distortion bound can be asymptotically achieved by a “natural type selection” (NTS) mechanism which iteratively considers asymptotically long source strings (from given distribution P) and regenerates the codebook according to the type of the first codeword to “d-match” the source string (i.e., satisfy the distortion constraint), where the sequence of codebook generating types converges to the optimal reproduction distribution. While ensuring optimality, earlier results had a significant practical flaw, due to the order of limits at which the convergence is achieved. More specifically, NTS iterations indexed by n presume asymptotically large ℓ, but the codebook size grows exponentially with ℓ. The reversed order of limits is practically preferred, wherein most codebook regeneration iterations involve manageable string lengths. This work describes a dramatically more efficient mechanism to achieve the optimum within a practical framework. It is specifically shown that it is sufficient to individually encode many source strings of short fixed length ℓ, then find the maximum likelihood estimate for the distribution Qn+1that would have generated the observed sequence of d-matching codeword strings, then use Qn+1to generate a new codebook for the next iteration. The sequence of distributions Q1, Q2, ... converges to the optimal reproduction distribution Qℓ*(P, d), achievable at finite length ℓ. It is further shown that Qℓ*(P, d) converges to the optimal reproduction distribution Q*(P, d) that achieves the rate-distortion bound R(P, d), asymptotically in string length ℓ.

This paper proposes a generalized stochastic mechanism for codebook generation in lossy coding settings for sources with memory. Earlier work has shown that the rate-distortion bound can be asymptotically achieved for discrete memoryless sources by a “natural type selection” (NTS) algorithm. In iteration n, the distribution that is most likely to produce the types of a sequence of K codewords of finite length I that “dmatch” a respective sequence of K source words of length I, (i.e., which satisfy the distortion constraint), is used to regenerate the codebook for iteration n+1. The resulting sequence of codebook generating distributions converges to the optimal distribution Q* that achieves the rate-distortion bound for the memoryless source, asymptotically in I, K, and n. This work generalizes the NTS algorithm to account for sources with memory. The algorithm encodes mI-length source words consisting of I vectors (or super-symbols) of length m. We show that for finite m and I, the sequence of codebook reproduction distributions Q0,m,l, Q1,m,l,... (each computed after observing a sequence of K d-match events) converges to the optimal achievable distribution Q*m,l(within a set of achievable distributions determined by m and I), asymptotically in K and n. It is further shown that Q*m,lconverges to the optimal reproduction distribution Q* that achieves the rate-distortion bound for sources with memory, asymptotically in m and I.

The VR180 format is gaining considerable traction among the various promising immersive multimedia formats that will arguably dominate future multimedia consumption applications. VR180 enables stereo viewing of a hemisphere about the user. The increased field of view and the stereo setting result in extensive volumes of data that strongly motivate the pursuit of novel efficient compression tools tailored to this format. This paper's focus is on the critical inter-view prediction module that exploits correlations between camera views. Existing approaches mainly consist of projection to a plane where traditional multi-view coders are applied, and disparity compensation employs simple block translation in the plane. However, warping due to the projection renders such compensation highly suboptimal. The proposed approach circumvents this shortcoming by performing geodesic disparity compensation on the sphere. It leverages the observation that, as an observer moves from one view point to the other, all points on surrounding objects are perceived to move along respective geodesics on the sphere, which all intersect at the two points where the axis connecting the two view points pierces the sphere. Thus, the proposed method performs inter-view prediction on the sphere by moving pixels along their predefined respective geodesics, and accurately captures the perceived deformations. Experimental results show significant bitrate savings and evidence the efficacy of the proposed approach.

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.

Current video coders employ motion compensated pixel-to-pixel prediction, which largely ignores significant spatial correlations and the fact that true temporal correlations vary with spatial frequency. Earlier work from our lab proposed to first spatially decorrelate the block of pixels by performing temporal prediction in the transform domain, and to effectively account for both spatial and temporal correlations. To adapt to variations in video signal statistics, the encoder switches between a set of appropriately designed prediction modes.This setting critically depends on efficient offline learning of transform domain temporal prediction modes. Significant challenges include: i) issues of instability and mismatched statistics inherent to closed loop design; and ii) severe non-convexity of the cost function trapping the system in poor local minima. Statistics mismatch is tackled by an appropriate paradigm for system design in a stable open loop fashion, but which asymptotically mimics closed loop operation. The non-convexity is handled by deterministic annealing, a powerful non-convex optimization tool whose probabilistic formulation allows for direct optimization of the cost function with respect to the discrete set of prediction modes, and whose annealing schedule avoids poor local minima. Experimental results validate the method's efficacy.

In order to increase system capacity and transmission rates, fifth-generation (5G) cellular and 802.11ad/ay wireless systems will use millimeter wave frequencies (24GHz-70GHz), which require large antenna arrays and narrow beamforming to mitigate the impact of substantial path-loss. While narrow beamforming maximizes array gain it also entails a significant increase in the number of beams needed to maintain the desired cell coverage. Consequently, there is a considerable increase in the complexity of beam management for initial user access and then tracking. This paper proposes a novel beam steering algorithm to maximize coverage given a prescribed size for the codebook of beam directions. The proposed approach leverages the observation that the problem of finding the optimal set of beam pointing angles can be mapped to the classical quantizer design problem in source coding, albeit with a somewhat unusual distortion measure. A variant of the Generalized Lloyd Algorithm is derived and employed to find the optimal codebook of beam placement angular directions. Numerical results show up to 2 dB gains in average power array factor, in comparison with the conventional uniformly spaced beam steering approach. These performance gains can be traded for codebook size reduction and a corresponding reduction in beam management complexity.

Adaptive prediction is important in the compression of non-stationary signals, and a common remedy is to switch between appropriately designed prediction modes. This paper presents a near optimal procedure to design prediction modes for an adaptive compression system. The main challenges include: instability and mismatched statistics during closed loop design; and the severe non-convexity of the cost function trapping the system in poor local minima. The statistical mismatch is circumvented through a largely open loop (hence stable) design that is devised to asymptotically optimize the prediction modes for closed loop operation. The non-convexity of the cost function is handled by the deterministic annealing paradigm, a powerful non-convex optimization framework devised to avoid poor local minima. Experimental results provide substantial gains validating the efficacy of the proposed design technique.

The MPEG-H 3D audio standard applies singular value decomposition (SVD) to the input higher order ambisonics data, then encodes each predominant (foreground) sound component independently using a standard core audio codec. The residual (background) signal is encoded in the ambisonic domain. This paper is motivated by the observations: i) separate coding of SVD components ignores spatial inter channel masking effects; ii) compression in both SVD and ambisonic domains is difficult to perceptually optimize; iii) Only few predominant components are encoded due to the prohibitive side information cost of specifying SVD basis vectors. The proposed coding architecture overcomes the first two concerns by performing all compression in the SVD domain with a masking threshold that is calculated jointly for all encoded components, thereby accounting for cross-component masking. The third shortcoming is circumvented by a novel method for extending a given set of SVD basis vectors at no side information cost, by computing (at both encoder and decoder) basis vectors to span the null space of the transmitted basis vectors. Experimental results provide evidence for substantial objective and subjective gains.

Emerging immersive multimedia applications critically depend on efficient compression of spherical (360-degree) videos. Current approaches project spherical video onto planes for coding with standard codecs, without accounting for the properties of spherical video, a severe sub-optimality that motivates this work. A common type of spherical video is dominated by camera translation. We recently proposed a powerful motion compensation technique for such videos which builds on the observation that, with camera translation, stationary points are perceived as moving along geodesics that meet at the point where the camera translation vector intersects the sphere. However, the approach follows standard coding procedures and translates all pixels in a block by the same amount on their respective geodesics, which is sub-optimal. This paper analyzes the appropriate rate of translation along geodesics and its dependence on the elevation of a pixel on the sphere with respect to the camera velocity pole. The analysis leads to a new approach that modulates the effective motion vectors within a block such that they perfectly capture the perceived individual motion of each pixel. Consistent gains in the experiments provide evidence for the efficacy of the proposed approach.

This paper proposes a multi-layer multi-reference prediction framework for effective video compression. Current AOM/AV1 baseline uses three reference frames for the inter prediction of each video frame. This paper first presents a new coding tool that extends the total number of reference frames in both forward and backward prediction directions. A multi-layer framework is then described, which suggests the encoder design and places different reference frames within one Golden Frame (GF) group to different layers. The multi-layer framework leverages the existing coding tools in the AV1 baseline, including the tool of "show_existing_frame" and the reference frame buffer update module of a wide flexibility. The use of extended ALTREF_FRAMEs is proposed, and multiple ALTREF_FRAME candidates are selected and widely spaced within one GF group. ALTREF_FRAME is a constructed, no-show reference obtained through temporal filtering of a look-ahead frame. In the multi-layer structure, one reference frame may serve different roles for the encoding of different frames through the virtual index manipulation. The experimental results have been collected over several video test sets of various resolutions and characteristics both texture- and motion-wise, which demonstrate that the proposed approach achieves a consistent coding gain compared to the AV1 baseline. For instance, using PSNR as the distortion metric, an average bitrate saving of 5.57+% in BDRate is obtained for the CIF-level resolution set, some of which has a gain of up to 13+%, and 4.47% on average for the VGA-level resolution set, some of which up to 18+%.

Conventional video coders rely heavily on pixel-domain block matching to remove temporal redundancies. This prediction structure constrains pixels within a block to use the same motion vector, which is ineffective for blocks with complex motion. To mitigate this shortcoming we recently proposed a new paradigm of adaptive interpolated motion compensation (AIMC), wherein neighboring motion vectors are considered as pointers to multiple estimation sources, which are linearly combined to form the final prediction, with weights chosen from pre-trained K-sets to capture variations in statistics. While promising initial results were obtained for fixed block sizes, this paper extends the approach to the important setting of variable block size partitioning, which has become standard in state-of-the-art video coding. Specifically, we propose a non-trivial generalization of AIMC to account for arbitrary block partitioning by “virtually” breaking a block to match its non-causal neighbors, and creating an interpolation tree structure, whose nodes extend from the original partitioning. This provides multiple estimates at the leaf nodes of the tree and enables an effective AIMC implementation. Experimental results validate the proposed paradigm with significant bit rate savings over conventional motion compensated prediction.

Scalable coding is potentially useful in content distribution over unreliable channels, as it enables meaningful reconstruction when the hierarchical bitstream is only partially received. However, its deployment in conjunction with predictive coding may result in considerable performance degradation when errors due to packet loss propagate through the prediction loop. Despite this, most existing predictive scalable coding techniques employ components whose design completely ignores the effects of unreliable channel conditions. This paper proposes an efficient design technique for predictive scalable coding systems, which effectively accounts for: i) all available information at a given layer by optimizing its prediction parameters within an estimation-theoretic framework; ii) the uncertainty due to packet loss via estimation and minimization of end-to-end distortion. It further leverages an asymptotic closed loop design technique for the predictor and quantizer modules, which provides the stability benefits of open-loop design, while ultimately optimizing the system for closed-loop operation. Experimental results provide compelling evidence for the effectiveness of the approach, with considerable performance gains over existing design techniques, in terms of end-to-end signal-to-noise ratio.

Spherical video is the key driving factor for the growth of virtual reality and augmented reality applications, as it offers truly immersive experience by capturing the entire 3D surroundings. However, it represents an enormous amount of data for storage/transmission and success of all related applications is critically dependent on efficient compression. A frequently encountered type of content in this video format is due to translational motion of the camera (e.g., a camera mounted on a moving vehicle). Existing approaches simply project this video onto a plane and use block based translational motion model for capturing the motion of the objects between the frames. This ad-hoc simplified approach completely ignores the complex deformities of objects caused due to the combined effect of the moving camera and projection onto a plane, rendering it significantly suboptimal. In this paper, we provide an efficient solution tailored to this problem. Specifically, we propose to perform motion compensated prediction by translating pixels along their geodesics, which intersect at the poles corresponding to the camera velocity vector. This setup not only captures the surrounding objects' motion exactly along the geodesics of the sphere, but also accurately accounts for the deformations caused due to projection on the sphere. Experimental results demonstrate that the proposed framework achieves very significant gains over existing motion models.

Spherical video is becoming prevalent in virtual and augmented reality applications. With the increased field of view, spherical video needs enormous amounts of data, obviously demanding efficient compression. Existing approaches simply project the spherical content onto a plane to facilitate the use of standard video coders. Earlier work at UCSB was motivated by the realization that existing approaches are suboptimal due to warping introduced by the projection, yielding complex non-linear motion that is not captured by the simple translational motion model employed in standard coders. Moreover, motion vectors in the projected domain do not offer a physically meaningful model. The proposed remedy was to capture the motion directly on the sphere with a rotational motion model, in terms of sphere rotations along geodesics. The rotational motion model preserves the shape and size of objects on the sphere. This paper implements and tests the main ideas from the previous work [1] in the context of a full-fledged, unconstrained coder including, in particular, bi-prediction, multiple reference frames and motion vector refinement. Experimental results provide evidence for considerable gains over HEVC.

Clinical observations indicate that during critical care at the hospitals, a patient's sleep positioning and motion have a significant effect on recovery rate. Unfortunately, there is no formal medical protocol to record, quantify, and analyze motion of patients. There are very few clinical studies that use manual analysis of sleep poses and motion recordings to support medical benefits of patient positioning and motion monitoring. Manual processes do not scale, are prone to human errors, and put strain on an already taxed healthcare workforce. This study introduces multimodal, multiview motion analysis and summarization for healthcare (MASH). MASH is an autonomous system, which addresses these issues by monitoring healthcare environments and enabling the recording and analysis of patient sleep-pose patterns. MASH uses three RGB-D cameras to monitor patients in a medical intensive care unit (ICU) room. The proposed algorithms estimate pose direction at different temporal resolutions and use keyframes to efficiently represent pose transition dynamics. MASH combines deep features computed from the data with a modified version of hidden Markov model (HMM) to flexibly model pose duration and summarize patient motion. The performance is evaluated in ideal (BC: bright and clear/occlusion-free) and natural (DO: dark and occluded) scenarios at two motion resolutions and in two environments: a mock-up and a medical ICU. The usage of deep features is evaluated and their performance compared with engineered features. Experimental results using deep features in DO scenes increase performance from $\text{86.7}\%$ to $\text{93.6}\%$, while matching the classification performance of engineered features in BC scenes. The performance of MASH is compared with HMM and C3D. The overall overtime tracing and summarization error rate across all methods increased when transitioning from the mock-up to the the medical ICU data. The proposed keyframe estimation helps achieve a $\text{78}\%$ transition classification accuracy.

Conventional pixel-domain block matching temporal (inter) prediction is suboptimal, since it ignores the underlying spatial correlation. Hence in our recent research we proposed transform domain temporal prediction (TDTP), wherein spatially decorrelated transform coefficients are individually predicted. Later we proposed extended block TDTP (EB-TDTP), which fully exploits spatial correlation around reference block boundaries. However, the transform domain temporal correlation exploited by (EB-)TDTP interferes with the frequency response of sub-pixel interpolation filters. Thus, in this paper, we propose to replace the standard sub-pixel interpolation with filters which are jointly designed with EB-TDTP based on statistics of the data, for either separable or non-separable interpolation structures. We also employ a two-loop asymptotic closed-loop (ACL) approach for statistically stable off-line design. Experiments show that our framework can achieve up to 1dB gain in PSNR over HEVC.

This paper considers near optimal design of predictive compression system that accounts for packet loss over unreliable networks. Major challenges to address include, propagation of errors due to packet loss through the prediction loop, mismatch between statistics used for design and during operation, and above all a cost function that is fraught with poor local minima. Accurately estimating and minimizing the end-to-end distortion (EED), in combination with asymptotic closed-loop (ACL) design that employs open-loop iterations, but mimics closed-loop operation on convergence, was proposed to address the first two challenges. However the severe non-convexity of the cost function, especially due to the piece-wise linear nature of the quantizer function, makes this a particularly challenging optimization problem. We propose to tackle this via a new design approach in the deterministic annealing framework to avoid poor local minima, coupled with the ACL approach to minimize EED estimate. This effectively addresses all the major challenges, and leads to a near optimal design of error-resilient predictive compression system. Substantial performance improvement obtained in experimental evaluations demonstrates the efficacy of the proposed approach.

Scalable video coding suffers from the under-utilization of base layer information, where usually only the reconstruction in the base layer is used for enhancement layer prediction. Prior work from our lab proposed an optimal estimation-theoretic (ET) approach for quality scalable coding, wherein the estimates are obtained by utilizing all the available information from base layer quantization interval and enhancement layer distribution for transform coefficients. While this approach was proposed for fixed block size encoding, modern codecs employ variable block size quadtree structured partitioning, which results in different partitions at base layer and enhancement layer based on the rate-distortion trade-off, thus makes the base layer information not directly usable in the enhancement layer. Other new tools such as hybrid transform and the rate-distortion optimized quantizer (RDOQ) also have an impact on the information available for optimal estimation. In this paper, we generalize the ET framework for quality scalable video coding to account for the quadtree structured partitioning, hybrid transform and the RDOQ adjustment. Experimental evidence is provided for consistent coding gains over standard SHVC.

Temporal prediction plays a crucial role in most video coding applications. However, due to error propagation via the prediction loop, it also increases the vulnerability to channel loss. The standard counter measure to mitigate error propagation is the `intra refresh' mode, which in effect resets temporal prediction to block error propagation, but at a significant rate overhead. This on/off switch for temporal prediction is overly crude to optimize the compression-resilience tradeoff. In this paper, we propose a novel framework that significantly expands the options available to counter error propagation by introducing optimally controlled soft resets, wherein intra and inter predictions are combined with adjustable weights to control the dependency on previous frames while accounting for the overall rate and distortion. Since the optimal control of such soft resets can only be achieved if the encoder can effectively estimate its impact on the end-to-end distortion (EED), we propose to extend the well known recursive optimal per-pixel estimation (ROPE) approach to accurately account for the soft reset mode, then optimize encoder mode decisions to minimize the estimated EED for the given rate. Experimental results show that the proposed framework achieves significant performance gains for video streaming over unreliable networks.

Current video coders rely heavily on block-based motion compensation, which is known to accurately capture pure translation, but to (at best) approximate all other types of motion, such as rotation and zoom. Moreover, as motion vectors are obtained through pixel-domain block matching to optimize a rate-distortion cost, and do not necessarily represent the actual motion, the model should not be considered a proper sampling of the underlying pixel motion field. This paper explicitly treats several neighboring motion vectors as pointers to multiple observation sources for estimating a pixel in the current frame. The corresponding optimal linear estimation coefficients are derived for predicting each pixel, given the observations obtained based on nearby motion vectors. Prediction coefficients are further adapted to local statistics by switching between predefined sets of coefficients, which are trained offline through a procedure of “K-modes” clustering. Experimental results outside the training set validate this paradigm with significant bit rate savings over conventional motion compensated prediction.

The recent boom in the field of virtual and augmented reality has dramatically increased the prevalence of spherical video. Given the enormous amount of data consumed by spherical video, it is critical to achieve efficient compression for storage and transmission. Prevalent approaches simply project (via different geometries) the spherical video onto planes for processing with traditional 2D video coding standards. However, such approaches are significantly sub-optimal as standard video coders only allow for block translations in the critical tool of motion compensated prediction, which is incompatible with the expected motion in projected spherical video. Specifically, the effective sampling density varies over the sphere and the resulting locally varying warping yields complex non-linear motion in the projected domain. Hence, translation in the projected domain does not preserve an object's shape and size on the sphere, and its corresponding motion vector does not have a useful physical interpretation. Instead, we propose to characterize the motion directly on the sphere with a rotational motion model, specifically, in terms of sphere rotations along geodesics. This model preserves object shape and size on the sphere. A motion vector in this model implicitly specifies an axis of rotation and the degree of rotation about that axis, to convey the actual motion of objects on the sphere. Complementary to the novel motion model, we further propose an effective motion search technique that is tailored to the sphere's geometry. Experimental results demonstrate that the proposed framework achieves significant gains over prevalent motion models, across various projection geometries.

Multimedia content is required at different quality levels due to heterogeneous network conditions and diverse consumption devices. A conventional scalable coder generates a layered bitstream, wherein a base layer produces a coarse reconstruction, and successive layers refine the quality, incrementally. However most multimedia sources are not successively refinable under their relevant distortion metrics. When a source is not successively refinable, conventional scalable coding introduces a performance penalty, while at the other extreme, independent coding is clearly wasteful in resources. As an alternative, we recently proposed a framework with a relaxed hierarchical structure to separate and transmit information common to different quality levels, along with individual bitstreams for each quality level. This framework offers the exibility to operate at various tradeoff points between conventional scalable coding and independent coding.In this paper we propose a technique to jointly design scalar quantizers acrosslayers of this framework, while focusing on the setting of two quality levels. We need three layers for two quality levels, one common layer sent to both receivers and two individual layers, which refine the common layer to two different required quality levels. We propose an iterative approach for designing the three scalar quantizers, wherein at each iteration one quantizer's intervals are updated to minimize the overall cost function while the others are fixed, and the iterations are repeated until convergence. Given the common layer quantizer intervals, for each of the individual layer, refining quantizers for all the intervals of the common layer are jointly designed to minimize the overall cost function. We also develop (\Lloyd algorithm style") optimal interval update rules for the common layer quantizer that minimizes the overall cost while accounting for the current individual layer quantizers.We provide experimental results for Laplacian sources, as many practical applications, model multimedia sources by the Laplacian distribution. The results clearly demonstrate that, by exploiting the concept of common information, the proposed approach can achieve all intermediate operating points at considerably better performance compared to the convex hull between non-scalable and scalable coding. Also we obtain interesting operating points, with distortions very close to non-scalable coding, but with a 14% reduction in total transmit rate compared to non-scalable coding.In this paper we propose a technique to jointly design scalar quantizers across layers of this framework, while focusing on the setting of two quality levels. We need three layers for two quality levels, one common layer sent to both receivers and two individual layers, which refine the common layer to two different required quality levels. We propose an iterative approach for designing the three scalar quantizers, wherein at each iteration one quantizer's intervals are updated to minimize the overall cost function while the others are fixed, and the iterations are repeated until convergence. Given the common layer quantizer intervals, for each of the individual layer, refining quantizers for all the intervals of the common layer are jointly designed to minimize the overall cost function. We also develop (“Lloyd algorithm style”) optimal interval update rules for the common layer quantizer that minimizes the overall cost while accounting for the current individual layer quantizers. We provide experimental results for Laplacian sources, as many practical applications, model multimedia sources by the Laplacian distribution. The results clearly demonstrate that, by exploiting the concept of common information, the proposed approach can achieve all intermediate operating points at considerably better performance compared to the convex hull between non-scalable and scalable coding. Also we obtain interesting operating points, with distortions very close to non-scalable coding, but with a 14% reduction in total transmit rate compared to non-scalable coding.

Traditional temporal prediction relies on motion compensated pixel copying operations. Such per-pixel temporal prediction was shown in prior work to be sub-optimal since it ignores the underlying spatial correlation. Transform domain temporal prediction (TDTP) was thus proposed previously to first achieve spatial decorrelation within the block using DCT, then apply an optimal one-to-one prediction per frequency. However, for sub-pixel motion compensation, the low-pass filter used for interpolation interferes with TDTP. In this paper, we propose an extended block based TDTP, which: i) completely disentangles spatial and temporal correlations to fully account for the sub-pixel interpolation effect, and ii) fully exploits spatial correlations around reference block boundary. Experimental evidence is provided for substantial coding gains over standard HEVC.

This paper extends the well-known source coding problem of multiple descriptions, in its general and basic setting, to analog source-channel coding scenarios. Encoding-decoding functions that optimally map between the (possibly continuous valued) source and the channel spaces are numerically derived. The main technical tool is a non-convex optimization method, namely, deterministic annealing, which has recently been successfully used in other mapping optimization problems. The obtained functions exhibit several interesting structural properties, map multiple source intervals to the same interval in the channel space, and consistently outperform the known competing mapping techniques.

While several real world signals, such as speech, image and sensor network data, are modeled as hidden Markov sources (HMS) for recognition and analysis applications, their typical compression exploits temporal correlations by modeling them as simple (non-hidden) Markov sources. However, the inherent hidden Markov nature of these sources implies that an observed sample depends, in fact, on all past observations, thus rendering simple Markov modeling suboptimal. Motivated by this realization, previous work from our lab derived a technique to optimally quantize and compress HMS. In this paper we build on, and considerably extend, these results to the problem of scalable coding of HMS. At the base layer, as proposed earlier, the approach tracks an estimate of the state probability distribution and adapts the encoder structure accordingly. At the enhancement layer, the state probability distribution is refined using available information from past enhancement layer reconstructed samples, and this refined estimate is further combined with quantization information from the base layer, to effectively characterize the probability density of the current sample conditioned on all available information. We update code parameters on the fly, at each observation, at both the encoder and the decoder and at both layers. Experimental results validate the superiority of the proposed approach with considerable gains over standard predictive coding employing a simple Markov model.

Today's diverse data consumption devices and heterogeneous network conditions require content to be coded at different quality levels. Conventional scalable coding, which generates hierarchical layers that refine quality incrementally, introduces a performance penalty, as most sources are not successively refinable at finite delays for the distortion measure employed and the combination of rates at each layer. On the other hand encoding different copies at required quality levels is clearly wasteful in resources. We previously proposed a common information based framework with a relaxed hierarchical structure to generate common and individuals bit-streams for different quality levels, to provide the flexibility of operating at points between conventional scalable coding and independent coding. In this paper we propose a quantizer design technique for this layered coding framework, which enables extracting common information between two quality levels with negligible performance penalty. Experimental results for Laplacian sources, which are prevalent in practical multimedia systems, substantiate the effectiveness of our proposed technique.

Prediction is used in virtually all compression systems. When such a compressed signal is transmitted over unreliable networks, packet losses can lead to significant error propagation through the prediction loop. Despite this, the conventional design technique completely ignores the effect of packet losses, and estimates the prediction parameters to minimize the mean squared prediction error, and optimizes the quantizer to minimize the reconstruction error at the encoder. While some design techniques have been proposed to accurately estimate and minimize the end-to-end distortion at the decoder that accounts for packet losses, they operate in a closed-loop, which introduces a mismatch between statistics used for design and statistics used in operation, causing a negative impact on convergence and stability of the design procedure. Instead, we propose in this paper an effective technique for predictive compression system design that accounts for the instability caused by error propagation due to packet losses, and enjoys stable statistics during design by employing open-loop iterations that on convergence mimic closed-loop operation. Simulation results for a compression system with a first order linear predictor demonstrate the utility of the proposed approach, which offers significant performance improvements over existing design techniques.

The accuracy of end-to-end distortion (EED) estimation is crucial to achieving effective error resilient video coding. An established solution, the recursive optimal per-pixel estimate (ROPE), does so by tracking the first and second moments of decoder-reconstructed pixels. An alternative estimation approach, the spectral coefficient-wise optimal recursive estimate (SCORE), tracks instead moments of decoder-reconstructed transform coefficients, which enables accounting for transform domain operations. However, the SCORE formulation relies on a fixed transform block size, which is incompatible with recent standards. This paper proposes a non-trivial generalization of the SCORE framework which, in particular, accounts for arbitrary block size combinations involving the current and reference block partitions. This seemingly intractable objective is achieved by a two-step approach: i) Given the fixed block size moments of a reference frame, estimate moments of transform coefficients for the codec-selected current block partition; ii) Convert the current results to transform coefficient moments corresponding to a regular fixed block size grid, to facilitate EED estimation for the next frame. Experimental results first demonstrate the accuracy of the proposed estimate in conjunction with transform domain temporal prediction. Then the estimate is leveraged to optimize the coding mode and yields considerable gains in rate-distortion performance.

Robust registration of unimodal and multimodal images is a key task in biomedical image analysis, and is often utilized as an initial step on which subsequent analysis techniques critically depend. We propose a novel probabilistic framework, based on a variant of the 2D hidden Markov model, namely, the turbo hidden Markov model, to capture the deformation between pairs of images. The hidden Markov model is tailored to capture spatial transformations across images via state transitions, and modality-specific data costs via emission probabilities. The method is derived for the unimodal setting (where simpler matching metrics may be used) as well as the multimodal setting, where different modalities may provide very different representations for a given class of objects, necessitating the use of advanced similarity measures. We utilize a rich model with hundreds of model parameters to describe the deformation relationships across such modalities. We also introduce a local edge-adaptive constraint to allow for varying degrees of smoothness between object boundaries and homogeneous regions. The parameters of the described method are estimated in a principled manner from training data via maximum likelihood learning, and the deformation is subsequently estimated using an efficient dynamic programming algorithm. Experimental results demonstrate the improved performance of the proposed approach over the state-of-the-art deformable registration techniques, on both unimodal and multimodal biomedical data sets.

This paper presents a new achievable rate-distortion region for the general L channel multiple descriptions (MDs) problem. A well-known general region for this problem is due to Venkataramani, Kramer, and Goyal (VKG). Their encoding scheme is an extension of the El Gamal-Cover (EC) and Zhang-Berger (ZB) coding schemes to the L channel case and includes a combinatorial number of refinement codebooks, one for each subset of the descriptions. As in ZB, the scheme also allows for a single common codeword to be shared by all descriptions. This paper proposes a novel encoding technique involving combinatorial message sharing (CMS), where every subset of the descriptions may share a distinct common message. This introduces a combinatorial number of shared codebooks along with the refinement codebooks of. These shared codebooks provide a more flexible framework to tradeoff redundancy across the messages for resilience to descriptions loss. We derive an achievable rate-distortion region for the proposed technique, and show that it subsumes the VKG region for general sources and distortion measures. We further show that CMS provides a strict improvement of the achievable region for any source and distortion measures for which some two-description subset is such that ZB achieves points outside the EC region. We then show a more surprising result: CMS outperforms VKG for a general class of sources and distortion measures, including scenarios where the ZB and EC regions coincide for all two-description subsets. In particular, we show that CMS strictly improves on VKG, for the L-channel quadratic Gaussian MD problem, for all L ≥ 3, despite the fact that the EC region is complete for the corresponding two-descriptions problem. Consequently, the correlated quantization scheme (an extreme special case of VKG) that has been proven to be optimal for several cross sections of the L-channel quadratic Gaussian MD problem is strictly suboptimal in general. Using the encoding principles derived, we show that the CMS scheme achieves the complete rate-distortion region for several asymmetric cross sections of the L-channel quadratic Gaussian MD problem.

Current video coders exploit temporal dependencies via prediction that consists of motion-compensated pixel copying operations. Such per-pixel temporal prediction ignores important underlying spatial correlations, as well as considerable variations in temporal correlation across frequency components. In the transform domain, however, spatial decorrelation is first achieved, allowing for the true temporal correlation at each frequency to emerge and be properly accounted for, with particular impact at high frequencies, whose lower correlation is otherwise masked by the dominant low frequencies. This paper focuses on effective design of transform domain temporal prediction that: i) fully accounts for the effects of sub-pixel interpolation filters, and ii) circumvents the challenge of catastrophic design instability due to quantization error propagation through the prediction loop. We design predictors conditioned on frequency and sub-pixel position, employing an iterative open-loop (hence stable) design procedure that, on convergence, approximates closed-loop operation. Experimental results validate the effectiveness of both the asymptotic closed-loop design procedure and the transform-domain temporal prediction paradigm, with significant and consistent performance gains over the standard.

Automated segmentation of electron microcope (EM) images is a challenging problem, but the presence of related images of a different modality can be a valuable resource. This paper describes a method to effectively utilize complementary information, if available, in EM segmentation. Images of both modalities are oversegmented into superpixels. A 2D hidden Markov model (HMM) is set up on the superpixel graph to determine the optimal superpixel mapping between images. This mapping is used to transfer labels and generate preliminary segmentations in the EM domain, whose boundaries are then refined, to eliminate imprecisions due to the su-perpixel grid, using a 1D HMM based contour refinement method. The performance of the proposed approach is demonstrated on a challenging dataset, and significant improvement is observed over related techniques.

This paper studies the problem of global optimization of zero-delay source-channel codes that map between the source space and the channel space, under a given transmission power constraint and for the mean-square-error distortion. Particularly, we focus on two well-known network settings: the Wyner-Ziv setting where only a decoder has access to side information and the distributed setting where independent encoders transmit over independent channels to a central decoder. Prior work derived the necessary conditions for optimality of the encoder and decoder mappings, along with a greedy optimization algorithm that imposes these conditions iteratively, in conjunction with the heuristic noisy channel relaxation method to mitigate poor local minima. While noisy channel relaxation is arguably effective in simple settings, it fails to provide accurate global optimization in more complicated settings considered in this paper. We propose a powerful nonconvex optimization method based on the concept of deterministic annealing-which is derived from information theoretic principles and was successfully employed in several problems including vector quantization, classification, and regression. We present comparative numerical results that show strict superiority of the proposed method over greedy optimization methods as well as prior approaches in literature.

This paper considers the problem of optimal zero-delay jamming over an additive noise channel. Building on a sequence of recent results on conditions for linearity of optimal estimation, and of optimal mappings in source-channel coding, the saddle-point solution to the jamming problem is derived for general sources and channels, without recourse to Gaussianity assumptions. The linearity conditions are shown to play a pivotal role in jamming, in the sense that the optimal jamming strategy is to effectively force both the transmitter and the receiver to default to linear mappings, i.e., the jammer ensures, whenever possible, that the transmitter and the receiver cannot benefit from non-linear strategies. This result is shown to subsume the known result for Gaussian source and channel. The conditions and general settings where such unbeatable strategy can indeed be achieved by the jammer are analyzed. Moreover, a numerical procedure is provided to approximate the optimal jamming strategy in the remaining (source-channel) cases where the jammer cannot impose linearity on the transmitter and the receiver. Next, the analysis is extended to vector sources and channels. This extension involves a new aspect of optimization: the allocation of available transmit and jamming power over source and channel components. Similar to the scalar setting, the saddle-point solution is derived using the linearity conditions in vector spaces. The optimal power allocation strategies for the jammer and the transmitter have an intuitive interpretation as the jammer allocates power according to water-filling over the channel eigenvalues, while the transmitter performs water-pouring (reverse water-filling) over the source eigenvalues.

There has been considerable interest in distributed source coding (DSC) in recent years, primarily due to its potential contributions to low-power sensor networks. However, two major obstacles pose an existential threat to practical deployment of such techniques: the exponential growth of decoding complexity with network size and coding rates and the critical requirement of resilience to bit errors and erasures, given the severe channel conditions in many wireless sensor network applications. This article proposes a novel, unified approach for large-scale, error/erasure-resilient DSC that incorporates an optimally designed, nearest neighbor classifier-based decoding framework, where the design explicitly controls performance versus decoding complexity. Motivated by the highly nonconvex nature of the cost function, we present a deterministic annealing-based optimization algorithm for the joint design of the system parameters, which further enhances the performance over the greedy iterative descent technique. Simulation results on both synthetic and real sensor network data provide strong evidence for performance gains compared to other state-of-the-art techniques and may open the door to practical deployment of DSC in large sensor networks. Moreover, the framework provides a principled way to naturally scale to large networks while constraining decoder complexity, thereby enabling performance gains that increase with network size.

The hidden Markov model (HMM) is widely used to model processes in several real world applications, including speech processing and recognition, image understanding and sensor networks. A problem of concern is that of quantization of the sequence of observations generated by an HMM, which is referred as a hidden Markov source (HMS). Despite the importance of the problem, and the well-defined structure of the process, there has been very limited work addressing the optimal quantization of HMS, and conventional approaches focus on optimization of parameters of known quantization schemes. This paper proposes a method that directly tracks the state probability distribution of the underlying source and optimizes the encoder structure according to the estimated HMS status. Unlike existing approaches, no stationarity assumption is needed, and code parameters are updated on they: with each observation, both the encoder and the decoder refine the estimated probability distribution over the states. The main approach is then specialized to a practical variant involving switched quantizers, and an algorithm that iteratively optimizes the quantize codebooks is derived. Numerical results show superiority of the proposed approach over prior methods.

Most modern video compression codecs, like VP9, HEVC and H.264, encode square or rectangular blocks either by inter prediction or intra prediction. A joint inter-intra predictor that combines motion compensation and intra extrapolation by two novel weighting schemes is proposed to improve compression quality. Prior work on joint prediction employs inter-intra weights that only rely on the pixel locations. As an enhancement, we design a weighting approach by also considering the angle of intra prediction, which is the actual direction that the intra prediction errors evolve. Moreover, our second approach, inspired by prior work on geometric-partition-based motion compensation, breaks the limitation of traditional quad-tree partition by jointly using different predictors that implies soft step weighting functions for new and existing objects co-occurring around irregular motion edges. The proposed joint prediction approaches deliver consistent coding gains, as shown by extensive experiments on the experimental branch of VP9, Google's open source video compression tool.

This paper studies the optimization of zero-delay analog mappings in a network setting that involves distributed coding. The cost surface is known to be non-convex, and known greedy methods tend to get trapped in poor locally optimal solutions that depend heavily on initialization. We derive an optimization algorithm based on the principles of “deterministic annealing”, a powerful global optimization framework that has been successfully employed in several disciplines, including, in our recent work, to a simple zero-delay analog communications problem. We demonstrate strict superiority over the descent based methods, as well as present example mappings whose properties lend insights on the workings of the solution and relations with digital distributed coding.

Scalable coders generate hierarchically layered bitstreams to serve content at different quality levels, wherein the base layer provides a coarse quality reconstruction and successive layers incrementally refine the quality. However, it is widely recognized that there is an inherent performance penalty due to the scalable coding structure, when compared to independently encoded copies. To mitigate this loss we propose a layered compression framework, having roots in information theoretic concepts, which relaxes the strict hierarchical constraints, wherein only a “subset” of the information of a lower quality level is shared with higher quality levels. In other words, there is flexibility to also have “private” information at each quality level, beside information that is common to multiple levels. We employ this framework within the MPEG Scalable AAC and propose an optimization scheme to jointly select parameters of all the layers. Experimental evaluation results demonstrate the utility of the flexibility provided by the proposed framework.

Recent video coding techniques allow for decoupling of the transform block partition from that employed for prediction. For example, HEVC allows a transform block to overlap multiple prediction blocks. This paper is premised on the observation that in order to truly realize the potential of such enhanced flexibility, it is necessary to account for and mitigate considerable side effects due to stitching together independently predicted blocks, including the emergence of spurious high frequency components from sharp transitions across boundaries, which undermine the transform efficacy. The proposed solution involves an appropriately designed pre-filtering approach to mitigate boundary transition effects whenever a transform spans data from multiple prediction blocks. Moreover, this filtering technique enables extending the flexibility in decoupling prediction and transform structures, as various restrictions may now be eliminated. In particular, it makes it possible and beneficial to allow a transform block to span residual data from both inter and intra predicted blocks, whereas HEVC necessarily forces a single type of prediction in each coding unit. The method is further extended to include motion refinement that accounts for the pre-filtering approach. Experiments provide evidence for consistent coding gains over HEVC and VP9.

Conventional “pixel copying” prediction used in current video standards was shown in previous work to be sub-optimal compared to 2-D non-separable Markov model based recursive extrapolation approaches. The premise of this paper is that in order to achieve the full potential of these approaches it is necessary to account for several requirements, namely, the design of prediction modes (and respective extrapolation filters) must optimize a rate-distortion cost rather than minimize the mean squared prediction error; the filters must be of sufficient complexity to cover all necessary directions; and the approach must include adaptation to available information indicative of local statistics. Hence, the proposed system employs four-tap recursive extrapolation filters that can predict from all standard directions, combined with a filter design method that accounts for the overall rate-distortion cost in conjunction with the codec decisions, along with adaptation of filter coefficients to relevant local information provided by encoder decisions on target bit rate and block size. Experimental evidence is provided for substantial coding gains over conventional intra coding.

Automated spatial alignment of images from different modalities is an important problem, particularly in bio-medical image analysis. We propose a novel probabilistic framework, based on a variant of the 2D hidden Markov model (2D HMM), to capture the deformation between multi-modal images. Smoothness is ensured via transition probabilities of the 2D HMM and cross-modality similarity via class-conditional, modality-specific emission probabilities. The method is derived for general multi-modal settings, and its performance is demonstrated for an application in cellular microscopy. We also present an efficient algorithm for parameter estimation. Experiments on synthetic and real biological data show improvement over state-of-the-art multi-modal image fusion techniques.

The problem of scalable coding while exploiting the decoder side information is considered. Prior work considered the two important cases concerning the degraded side information where source X and the side information variables (Y1, Y2) form a Markov chain in the order of either X − Y1− Y2or X − Y2− Y1. While the encoding schemes for these settings differ considerably, they are both based on the combination of conditional codebook encoding, a standard tool in scalable coding, and random binning, conventionally used in decoder side information problems. In this paper, an encoding scheme is proposed solely on the basis of random binning, which essentially performs scalable and Wyner-Ziv coding simultaneously. Proposed scheme achieves the rate-distortion regions of prior results. A practical advantage of the unifying scheme is the fact that random binning can be realized via practical tools such as nested lattice codes and channel codes. Finally, motivated by the proposed encoding scheme, a network interpretation of scalable coding is considered. An achievable region is derived for this problem setting and the potential benefits of networked scalable coding are shown.

Exploration versus exploitation in a sensor field with a mobile agent is examined in the context of source coding. The encoder is the low complexity data gathering agent. The decoder is a high complexity fusion center. The encoder first sends a coarse description of the random field, then transmits a refined description of a region of interest, i.e., a subset of the correlated sources in the first stage and so on. The main source coding challenge is that the receiver wants to refine a subset of the correlated sources that is unknown to the encoder a priori. The conventional approach of scalable coding via conditional codebook encoding (CCE) requires a codebook that is exponential in size with respect to the number of sources and also the number of refinement stages. This paper studies an alternative approach, using random binning (RB), in lieu of CCE. The universality of RB plays a key role, as the encoder does not know a priori which sources the decoder wants to refine. It is shown that RB does not introduce any loss and can effectively replace CCE while providing significant storage reduction in terms of the number of codewords stored. Achievable rate regions are derived for the single and the multi-terminal encoding settings.

This paper proposes an optimization method, based on information theoretic ideas, to a class of distributed control problems. As a particular test case, the well-known and numerically “over-mined” problem of decentralized control and implicit communication, commonly referred to as Witsenhausen's counterexample, is considered. The key idea is to randomize the zero-delay mappings. which become “soft”, probabilistic mappings to be optimized in a deterministic annealing process, by incorporating a Shannon entropy constraint in the problem formulation. The entropy of the mapping is controlled and gradually lowered to zero to obtain deterministic mappings, while avoiding poor local minima. For the particular test case, our approach obtains new mappings that shed light on the structure of the optimal solution, as well as achieving a small improvement in total cost over the state of the art in numerical approaches to this problem. Proposed method is general and applicable to any problem of similar nature.

Audio compression systems exploit periodicity in signals to remove inter-frame redundancies via the long term prediction (LTP) tool. This simple tool capitalizes on the periodic component of the waveform by selecting a past segment as the basis for prediction of the current frame. However, most audio signals are polyphonic in nature, containing a mixture of several periodic components. While such polyphonic signals may themselves be periodic with overall period equaling the least common multiple of the individual component periods, the signal rarely remains sufficiently stationary over the extended period, rendering the LTP tool suboptimal. Instead of seeking a past segment that represents a “compromise” for incompatible component periods, we propose a more complex filter that predicts every periodic component of the signal from its immediate history, and this is achieved by cascading LTP filters, each corresponding to individual periodic component. We also propose a recursive “divide and conquer” technique to estimate parameters of all the LTP filters. We then demonstrate the effectiveness of cascaded LTP in two distinct settings of the ultra low delay Bluetooth Subband Codec and the MPEG Advanced Audio Coding (AAC) standard. In MPEG AAC, we specifically adapt the cascaded LTP parameter estimation to take into account the perceptual distortion criteria, and also propose a low decoder complexity variant. Objective and subjective results for all the settings validate the effectiveness of the proposal on a variety of polyphonic signals.

This paper focuses on prediction optimality in spatially scalable video coding. It draws inspiration from an estimation-theoretic prediction framework for quality (SNR) scalability earlier developed by our group, which achieved optimality by fully accounting for relevant information from the current base layer (e.g., quantization intervals) and the enhancement layer, to efficiently calculate the conditional expectation that forms the optimal predictor. It was central to that approach that all layers reconstruct approximations to the same original transform coefficient. In spatial scalability, however, the layers encode different resolution versions of the signal. To approach optimality in enhancement layer prediction, this paper departs from existing spatially scalable codecs that employ pixel domain resampling to perform interlayer prediction. Instead, it incorporates a transform domain resampling technique that ensures that the base layer quantization intervals are accessible and usable at the enhancement layer despite their differing signal resolutions, which in conjunction with prior enhancement layer information, enable optimal prediction. A delayed prediction approach that complements this framework for spatial scalable video coding is then provided to further exploit future base layer frames for additional enhancement layer coding performance gains. Finally, a low-complexity variant of the proposed estimation-theoretic prediction approach is also devised, which approximates the conditional expectation by switching between three predictors depending on a simple condition involving information from both layers, and which retains significant performance gains. Simulations provide experimental evidence that the proposed approaches substantially outperform the standard scalable video codec and other leading competitors.

This paper studies the zero-delay source-channel coding problem, and specifically the problem of obtaining the vector transformations that optimally map between the m-dimensional source space and k-dimensional channel space, under a given transmission power constraint and for the mean square error distortion. The functional properties of the cost are studied and the necessary conditions for the optimality of the encoder and decoder mappings are derived. An optimization algorithm that imposes these conditions iteratively, in conjunction with the noisy channel relaxation method to mitigate poor local minima, is proposed. The numerical results show strict improvement over prior methods. The numerical approach is extended to the scenario of source-channel coding with decoder side information. The resulting encoding mappings are shown to be continuous relatives of, and in fact subsume as special case, the Wyner-Ziv mappings encountered in digital distributed source coding systems. A well-known result in information theory pertains to the linearity of optimal encoding and decoding mappings in the scalar Gaussian source and channel setting, at all channel signal-to-noise ratios (CSNRs). In this paper, the linearity of optimal coding, beyond the Gaussian source and channel, is considered and the necessary and sufficient condition for linearity of optimal mappings, given a noise (or source) distribution, and a specified a total power constraint are derived. It is shown that the Gaussian source-channel pair is unique in the sense that it is the only source-channel pair for which the optimal mappings are linear at more than one CSNR values. Moreover, the asymptotic linearity of optimal mappings is shown for low CSNR if the channel is Gaussian regardless of the source and, at the other extreme, for high CSNR if the source is Gaussian, regardless of the channel. The extension to the vector settings is also considered where besides the conditions inherited from the scalar case, additional constraints must be satisfied to ensure linearity of the optimal mappings.

The two most prevalent notions of common information (CI) are due to Wyner and Gács-Körner and both the notions can be stated as two different characteristic points in the lossless Gray-Wyner region. Although the information theoretic characterizations for these two CI quantities can be easily evaluated for random variables with infinite entropy (e.g., continuous random variables), their operational significance is applicable only to the lossless framework. The primary objective of this paper is to generalize these two CI notions to the lossy Gray-Wyner network, which hence extends the theoretical foundation to general sources and distortion measures. We begin by deriving a single letter characterization for the lossy generalization of Wyner's CI, defined as the minimum rate on the shared branch of the Gray-Wyner network, maintaining minimum sum transmit rate when the two decoders reconstruct the sources subject to individual distortion constraints. To demonstrate its use, we compute the CI of bivariate Gaussian random variables for the entire regime of distortions. We then similarly generalize Gács and Körner's definition to the lossy framework. The latter half of this paper focuses on studying the tradeoff between the total transmit rate and receive rate in the Gray-Wyner network. We show that this tradeoff yields a contour of points on the surface of the Gray-Wyner region, which passes through both the Wyner and Gács-Körner operating points, and thereby provides a unified framework to understand the different notions of CI. We further show that this tradeoff generalizes the two notions of CI to the excess sum transmit rate and receive rate regimes, respectively.

This paper considers the problem of minimum cost communication of correlated sources over a network with multiple sinks, which consists of distributed source coding followed by routing. We introduce a new routing paradigm called dispersive information routing (DIR), wherein the intermediate nodes are allowed to split a packet and forward subsets of the received bits on each of the forward paths. This paradigm opens up a rich class of research problems, which focus on the interplay between encoding and routing in a network. Unlike conventional routing methods such as in [1], DIR ensures that each sink receives just the information needed to reconstruct the sources it is required to reproduce. We demonstrate using simple examples that the proposed approach offers better asymptotic performance than conventional routing techniques. We show that, under certain assumptions on the cost function, the problem of finding the minimum cost under DIR essentially reduces to characterizing an achievable rate region for a new multiterminal information theoretic setup. While it is possible to derive an achievable region for this setup using prior results from general multiterminal source coding [3], these techniques do not exploit the underlying problem structure and thereby lead to suboptimal regions. In this paper, we propose a new coding scheme, using principles from multiple descriptions encoding [2], and show that it strictly improves upon a corresponding variant of coding scheme in [3]. We further show that the new coding scheme achieves the complete rate region for certain special cases of the general setup and thereby achieves the minimum communication cost under this routing paradigm.

A novel intra prediction scheme, based on recursive extrapolation filters, is introduced. Standard intra prediction largely consists of copying boundary pixels (or linear combinations thereof) along certain directions, which reflects an overly simplistic model for the underlying spatial correlations. As an alternative, we view the image signal as a 2-D non-separable Markov model, whose corresponding correlation model better captures the nuanced directionality effects within blocks. This viewpoint motivates the design of a set of prediction modes represented by three-tap extrapolation filters, which replace the standard “pixel-copying” prediction modes, and provide efficient prediction at modest complexity. The Markov property is exploited by recursive predictions from nearest neighbors without recourse to simplistic separability assumptions, and while effectively accounting for correlation decay with distance from available boundary pixels. Coefficients for the set of mode filters are first trained by an efficient “k-modes” iterative technique designed to monotonically decrease the mean squared prediction error, and are then adjusted to directly optimize the overall rate-distortion objective. This prediction scheme complements the hybrid (cosine and sine) transform coding approach developed by our group, to achieve consistent coding gains, as shown for standard and commercial intra coders such as H.264/AVC and VP8.

This paper builds on our recent work on optimal prediction in spatially scalable video coding, and is inspired by earlier work in our lab on optimal approaches for quality (or SNR) scalability. The approach we propose herein complements the optimal enhancement-layer prediction, enabled by transform domain resampling that ensures the base layer information is maximally accessible and usable at the enhancement layer despite their differing signal resolutions, with an optimal approach to quantization and entropy coding that exploits all available information, encapsulated in the appropriate conditional distribution for transform coefficients, to yield a unified coding engine for spatial scalability. For such quantizers to fully exploit base layer information, the enhancement layer transform block size must proportionally match the signal block transformed at the base layer. The overall system incorporates switching that applies the full estimation-theoretic quantizer and entropy coder at the right block size, but may optionally employ other block sizes where it defaults to optimal prediction followed by standard quantization. It is experimentally shown that the proposed scheme provides considerable performance gains over conventional codec and other leading competitors.

This paper studies a particular sensor network model which involves one single Gaussian source observed by many sensors, subject to additive independent Gaussian observation noise. Sensors communicate with the receiver over an additive Gaussian multiple access channel. The aim of the receiver is to reconstruct the underlying source with minimum mean squared error. The scenario of interest here is one where some of the sensors act as adversary (jammer): they strive to maximize distortion. We show that the ability of transmitter sensors to secretly agree on a random event, that is “coordination”, plays a key role in the analysis. Depending on the coordination capability of sensors and the receiver, we consider two problem settings. The first setting involves transmitters with “coordination” capabilities in the sense that all transmitters can use identical realization of randomized encoding for each transmission. In this case, the optimal strategy for the adversary sensors also requires coordination, where they all generate the same realization of independent and identically distributed Gaussian noise. In the second setting, the transmitter sensors are restricted to use fixed, deterministic encoders and this setting, which corresponds to a Stackelberg game, does not admit a saddle-point solution. We show that the the optimal strategy for all sensors is uncoded communications where encoding functions of adversaries and transmitters are in opposite directions. For both settings, digital compression and communication is strictly suboptimal.

In this paper, we study the zero-delay source-channel coding problem, and specifically the problem of obtaining the vector transformations that optimally map between the m-dimensional source space and the k-dimensional channel space, under a given transmission power constraint and for the mean square error distortion. We first study the functional properties of this problem and show that the objective is concave in the source and noise densities and convex in the density of the input to the channel. We then present the necessary conditions for optimality of the encoder and decoder mappings. A well known result in information theory pertains to the linearity of optimal encoding and decoding mappings in the scalar Gaussian source and channel setting, at all channel signal-to-noise ratios (CSNRs). In this paper, we study this result more generally, beyond the Gaussian source and channel, and derive the necessary and sufficient condition for linearity of optimal mappings, given a noise (or source) distribution, and a specified power constraint. We also prove that the Gaussian source-channel pair is unique in the sense that it is the only source-channel pair for which the optimal mappings are linear at more than one CSNR value. Moreover, we show the asymptotic linearity of optimal mappings for low CSNR if the channel is Gaussian regardless of the source and, at the other extreme, for high CSNR if the source is Gaussian, regardless of the channel.

This paper focuses on the problem of L-channel quadratic Gaussian multiple description (MD) coding. We recently introduced a new encoding scheme in [1] for general L-channel MD problem, based on a technique called `Combinatorial Message Sharing' (CMS), where every subset of the descriptions shares a distinct common message. The new achievable region subsumes the most well known region for the general problem, due to Venkataramani, Kramer and Goyal (VKG) [2]. Moreover, we showed in [3] that the new scheme provides a strict improvement of the achievable region for any source and distortion measures for which some 2-description subset is such that the Zhang and Berger (ZB) scheme achieves points outside the El-Gamal and Cover (EC) region. In this paper, we show a more surprising result: CMS outperforms VKG for a general class of sources and distortion measures, which includes scenarios where for all 2-description subsets, the ZB and EC regions coincide. In particular, we show that CMS strictly extends VKG region, for the L-channel quadratic Gaussian MD problem for all L ≥ 3, despite the fact that the EC region is complete for the corresponding 2-descriptions problem. Using the encoding principles derived, we show that the CMS scheme achieves the complete rate-distortion region for several asymmetric cross-sections of the L-channel quadratic Gaussian MD problem, which have not been considered earlier.

This paper studies optimization of zero-delay source-channel codes, and specifically the problem of obtaining globally optimal transformations that map between the source space and the channel space, under a given transmission power constraint and for the mean square error distortion. Particularly, we focus on the setting where the decoder has access to side information, whose cost surface is known to be riddled with local minima. Prior work derived the necessary conditions for optimality of the encoder and decoder mappings, along with a greedy optimization algorithm that imposes these conditions iteratively, in conjunction with the heuristic “noisy channel relaxation” method to mitigate poor local minima. While noisy channel relaxation is arguably effective in simple settings, it fails to provide accurate global optimization results in more complicated settings including the decoder with side information as considered in this paper. We propose a global optimization algorithm based on the ideas of “deterministic annealing” - a non-convex optimization method, derived from information theoretic principles with analogies to statistical physics, and successfully employed in several problems including clustering, vector quantization and regression. We present comparative numerical results that show strict superiority of the proposed algorithm over greedy optimization methods as well as over the noisy channel relaxation.

A novel filtering approach that naturally combines information from both intra-frame and motion compensated referencing for efficient prediction is proposed to fully exploit the spatio-temporal correlations of video signals, thereby achieving superior compression performance. Inspiration was drawn from our recent work on extrapolation filter based intra prediction, which views the spatial signal as a non-separable first-order Markov process and employs a 3-tap recursive filter to effectively capture the statistical characteristics. This work significantly extends the scope to further incorporate motion compensated reference in a filtering framework, whose coefficients were optimized via a “k-modes”-like iteration that accounts for various factors in the compression process including variation in statistics in the prediction loop, to minimize the rate-distortion cost. Experiments validate the efficacy of the proposed spatio-temporal approach, which translates into consistent coding performance gains.

Current scalable audio coders typically optimize performance at a particular layer without regard to impact on other layers, and are thus unable to provide a performance trade-off between different layers. In the particular case of MPEG Scalable Advanced Audio Coding (S-AAC) and Scalable-to-Lossless (SLS) coding, the base-layer is optimized first followed by successive optimization of higher layers, which ensures optimality of the base-layer but results in a scalability penalty that progressively increases with the enhancement layer index. The ability to trade-off performance between different layers enables alignment to the real world requirement for audio quality commensurate with the bandwidth afforded by a user. This work provides the means to better control the performance tradeoffs, and the distribution of the scalability penalty, between the base and enhancement layers. Specifically, it proposes an efficient joint optimization algorithm that selects the encoding parameters for each layer while accounting for the rate-distortion costs in all layers. The efficacy of the technique is demonstrated in the two distinct settings of S-AAC, and SLS High Definition Advanced Audio Coding. Objective and subjective tests provide evidence for substantial gains, and represent a significant step toward bridging the gap with the non-scalable coder.

Current video coders employ predictive coding with motion compensation to exploit temporal redundancies in the signal. In particular, blocks along a motion trajectory are modeled as an auto-regressive (AR) process, and it is generally assumed that the prediction errors are temporally independent and approximate the innovations of this process. Thus, zero-delay encoding and decoding is considered efficient. This paper is premised on the largely ignored fact that these prediction errors are, in fact, temporally dependent due to quantization effects in the prediction loop. It presents an estimation-theoretic delayed decoding scheme, which exploits information from future frames to improve the reconstruction quality of the current frame. In contrast to the standard decoder that reproduces every block instantaneously once the corresponding quantization indices of residues are available, the proposed delayed decoder efficiently combines all accessible (including any future) information in an appropriately derived probability density function, to obtain the optimal delayed reconstruction per transform coefficient. Experiments demonstrate significant gains over the standard decoder. Requisite information about the source AR model is estimated in a spatio-temporally adaptive manner from a bit-stream conforming to the H.264/AVC standard, i.e., no side information needs to be sent to the decoder in order to employ the proposed approach, thereby compatibility with the standard syntax and existing encoders is retained.

Randomized (dithered) quantization is a method capable of achieving white reconstruction error independent of the source. Dithered quantizers have traditionally been considered within their natural setting of uniform quantization. In this paper we extend conventional dithered quantization to nonuniform quantization, via a subterfage: dithering is performed in the companded domain. Closed form necessary conditions for optimality of the compressor and expander mappings are derived for both fixed and variable rate randomized quantization. Numerically, mappings are optimized by iteratively imposing these necessary conditions. The resulting quantizer renders the reconstruction error white with negligible performance loss compared to the optimal quantizer. The framework is extended to include an explicit constraint that deterministic or randomized quantizers yield reconstruction error that is uncorrelated with the source. Surprising theoretical results show direct and simple connection between the optimal constrained quantizers and their unconstrained counterparts. Numerical results for the Gaussian source provide strong evidence that the proposed constrained randomized quantizer outperforms the conventional dithered quantizer, as well as the constrained deterministic quantizer.

This paper is concerned with transform coding of correlated sources in conjunction with variable rate quantization at high resolution. The approach builds on our prior work on optimality conditions for transform coding in the point-to-point setting. The first contribution involves transform coding with decoder side information. In this setting, side information is only available to the decoder, whereas the encoder knows the joint statistics. The necessary and sufficient condition for optimality of a unitary transform in the side information setting is derived, namely, such transform minimizes a conditional divergence-based measure of inter-dependence of the transform coefficients, given the side information. This optimality result subsumes prior, known results that were restricted to the Gaussian case, where the conditional Karhunen-Loeve transform is optimal. The second contribution involves distributed transform coding, where two correlated sources are to be transform coded separately, but decoded jointly. The necessary and sufficient condition for optimality of unitary transforms in the distributed coding setting is derived. It is then specialized to produce closed form optimal transforms for specific source densities, including the case of jointly Gaussian sources.

This paper focuses on prediction optimality in spatially scalable video coding. It is inspired by the earlier estimation-theoretic prediction framework developed by our group for quality (SNR) scalability, which achieved optimality by fully accounting for relevant information from the current base layer (e.g., quantization intervals) and the enhancement layer, to efficiently calculate the conditional expectation that forms the optimal predictor. It was central to that approach that all layers reconstruct approximations to the same original transform coefficient. In spatial scalability, however, the layers encode different resolution versions of the signal. To approach optimality in enhancement layer prediction, the current work departs from existing spatially scalable codecs that employ pixel-domain resampling to perform inter-layer prediction. Instead, it incorporates a transform-domain resampling technique that ensures that the base layer quantization intervals are accessible and usable at the enhancement layer, which in conjunction with prior enhancement layer information, enable optimal prediction. Simulations provide experimental evidence that the proposed approach achieves substantial enhancement layer coding gains over the standard.

This paper proposes a frame loss concealment technique for audio signals, which is designed to overcome the main challenge due to the polyphonic nature of most music signals and is inspired by our recent research on compression of such signals. The underlying idea is to employ a cascade of long term prediction filters (tailored to the periodic components) to circumvent the pitfalls of naive waveform repetition, and to enable effective time-domain prediction of every periodic component from the immediate history. In the first phase, a cascaded filter is designed from available past samples and is used to predict across the lost frame(s). Available future reconstructed samples allow refinement of the filter parameters to minimize the squared prediction error across such samples. In the second phase a prediction is similarly performed in reverse from future samples. Finally the lost frame is interpolated as a weighted average of forward and backward predicted samples. Objective and subjective evaluation results for the proposed approach, in comparison with existing techniques, all incorporated within an MPEG AAC low delay decoder, provide strong evidence for considerable gains across a variety of polyphonic signals.

A novel coding paradigm is proposed to jointly optimize the prediction, quantization, and entropy coding modules, thereby approaching optimality in scalable video coding. It departs from conventional video coding schemes that consider prediction, transformation, quantization, and entropy coding, as largely separate sequential functional components. The method draws inspiration from an early estimation-theoretic approach, developed by our group for enhancement layer prediction, which efficiently combines all the information available to the enhancement layer coder, to produce the optimal prediction. The framework is significantly expanded here to also incorporate optimization of entropy-constrained quantization and arithmetic coding, while fully accounting for hitherto ignored relevant factors, inherent to predictive scalable coding, including information from the base layer quantization operation, and from the enhancement layer motion compensated reference. Experimental evidence is provided for substantial coding gains over conventional scalable video coding.

A novel scalable video coding (SVC) scheme is proposed for video transmission over loss networks, which builds on an estimation-theoretic (ET) framework for optimal prediction and error concealment, given all available information from both the current base layer and prior enhancement layer frames. It incorporates a recursive end-to-end distortion estimation technique, namely, the spectral coefficient-wise optimal recursive estimate (SCORE), which accounts for all ET operations and tracks the first and second moments of decoder reconstructed transform coefficients. The overall framework enables optimization of ET-SVC systems for transmission over lossy networks, while accounting for all relevant conditions including the effects of quantization, channel loss, concealment, and error propagation. It thus resolves longstanding difficulties in combining truly optimal prediction and concealment with optimal end-to-end distortion and error-resilient SVC coding decisions. Experiments demonstrate that the proposed scheme offers substantial performance gains over existing error-resilient SVC systems, under a wide range of packet loss and bit rates.

There has been considerable interest in distributed source coding within the compression and sensor network research communities in recent years, primarily due to its potential contributions to low-power sensor networks. However, two major obstacles pose an existential threat on practical deployment of such techniques in real world sensor networks, namely, the exponential growth of decoding complexity with network size and coding rates, and the critical requirement for error-resilience given the severe channel conditions in many wireless sensor networks. Motivated by these challenges, this paper proposes a novel, unified approach for large scale, error-resilient distributed source coding, based on an optimally designed classifier-based decoding framework, where the design explicitly controls the decoding complexity. We also present a deterministic annealing (DA) based global optimization algorithm for the design due to the highly non-convex nature of the cost function, which further enhances the performance over basic greedy iterative descent technique. Simulation results on data, both synthetic and from real sensor networks, provide strong evidence that the approach opens the door to practical deployment of distributed coding in large sensor networks. It not only yields substantial gains in terms of overall distortion, compared to other state-of-the-art techniques, but also demonstrates how its decoder naturally scales to large networks while constraining the complexity, thereby enabling performance gains that increase with network size.

This paper is concerned with the optimal linear transforms in zero-delay source channel coding for Gaussian sources and channels. In preparation for the main results, we first consider the classical problem in the point-to-point setting, which had already been solved by Lee and Petersen, where we provide an alternative proof using majorization. We then analyze the performance of linear source-channel coding in the low signal-to-noise ratio (SNR) regime. We show that at asymptotically low SNR, or equivalently as the power tends to zero, the powerdistortion function of zero delay linear coding achieves optimum theoretically achievable performance. Finally, we consider zero-delay source-channel coding with decoder side information. Here, subject to structural constraints on the encoder, we find the optimal encoder-decoder pair in closed form. We analyze two structures: i) the encoder is constrained to be linear where we show that the optimal transform is product of matrices including as factor the conditional Karhunen Loéve transform (KLT) of the source given the side information. ii) the encoder consists of linear transformation followed by individual optimal nonlinear mapping of each transform coefficient. Using majorization principles, we show that the optimal transform does not depend on the nonlinearities introduced, as long as they are scale invariant, hence the optimal transform is also a product involving the conditional KLT of the source.

This paper proposes a new multiple description (MD) coding method and an associated achievable rate-distortion region for L ≥ 2 channels. The proposed scheme randomly bins codebooks chosen from the codebook structure, similar to that of the recently proposed combinatorial message sharing (CMS) scheme designed for conditional codebook encoding. The proposed scheme effectively performs multilayer random binning for each subset of the description, which hence enables to utilize the symmetry of a “subset” of the description rates wherever it exists. The new scheme specializes in to the conventional multilayer random binning as an extreme special case.

The two most prevalent notions of common information are due to Wyner and Gács-Körner and both the notions can be stated as two different characteristic points in the lossless Gray-Wyner region. Although these quantities can be easily evaluated for random variables with infinite entropy (eg. continuous random variables), the operational significance underlying their definition is applicable only to the lossless framework. The primary objective of this paper is to generalize these two notions of common information to the lossy Gray-Wyner network, which extends the theoretical intuition underlying their definitions for general sources and distortion measures. We begin with the lossy generalization of Wyner's common information, defined as the minimum rate on the shared branch of the Gray-Wyner network at minimum sum rate when the two decoders reconstruct the sources subject to individual distortion constraints. We derive a complete single letter information theoretic characterization for this quantity and use it to compute the common information of symmetric bivariate Gaussian random variables. We then derive similar results to generalize Gács-Körner's definition to the lossy framework. These two characterizations allow us to carry the practical insight underlying the two notions of common information to general sources and distortion measures.

There are two common types of encoding paradigms in multiple descriptions (MD) coding: i) an approach based on conditional codebook generation, which was originally initiated by El-Gamal and Cover for the 2 channel setting and later extended to more than 2 channels by Venkataramani, Kramer and Goyal (VKG), ii) and an approach based on Slepian and Wolf's random binning technique, proposed by Pradhan, Puri and Ramchandran (PPR) for L >; 2 descriptions. It is well known that the achievable region due to PPR subsumes the VKG region for the symmetric Gaussian MD problem. Motivated by several practical advantages of random binning based methods over the conditional codebook encoding, this paper focuses on the following important questions: Does a random binning based scheme achieve the performance of conditional codebook encoding, even for the 2 descriptions scenario? Are random binning based approaches beneficial for settings that are not fully symmetric? This paper answers both these questions in the affirmative. Specifically, we propose a 2 descriptions coding scheme, based on random binning, which subsumes the currently known largest region for this problem due to Zhang and Berger. Moreover, we propose its extensions to L >; 2 channels and derive the associated achievable regions. The proposed scheme enjoys the advantages of both encoding paradigms making it particularly useful when there is symmetry only within a subset of the descriptions.

This paper focuses on a new framework for scalable coding of information based on principles derived from common information of two dependent random variables. In the conventional successive refinement setting, the encoder generates two layers of information called the base layer and the enhancement layer. The first decoder, which receives only the base layer, produces a coarse reconstruction of the source, whereas the second decoder, which receives both the layers, uses the enhancement layer to refine the information further leading to a finer reconstruction. It is popularly known that asymptotic rate-distortion optimality at both the decoders is possible if and only if the source-distortion pair is successively refinable. However when the source is not successively refinable under the given distortion metric, it is impossible to achieve rate-distortion optimality at both the layers simultaneously. For this reason, most practical system designers resort to storing two individual representations of the source leading to significant overhead in transmission/storage costs. Inspired by the breadth of applications, in this paper, we propose a new framework for scalable coding wherein a subset of the bits sent to the first decoder is not sent to the second decoder. That is, the encoder generates one common bit stream which is routed to both the decoders, but unlike the conventional successive refinement setting, both the decoders receive an additional individual bitstream. By relating the proposed framework with the problem of common information of two dependent random variables, we derive a single letter characterization for the minimum sum rate achievable for the proposed setting when the two decoders are constrained to receive information at their respective rate-distortion functions. We show using a simple example that the proposed framework provides a strictly better asymptotic sum rate as opposed to the conventional scalable coding setup when the source-distortion pair is not successively refinable.

This paper addresses the L-channel multiple descriptions problem for a Gaussian source under mean squared error (MSE) distortion metric. We focus on particular cross-sections of the general rate-distortion region where a subset the 2L- 1 distortion constraints are not imposed. Specifically, we assume that certain descriptions are never received simultaneously at the decoder and thereby the transmitted codewords require joint typicality only within prescribed subsets. We derive a new encoding scheme and an associated rate-distortion region wherein joint typicality of codewords only within the prescribed subsets is maintained. We show that enforcing joint typicality of all the codewords entails strict suboptimality in the achievable rate-distortion region. Specifically, we consider a 3 descriptions scenario wherein descriptions 1 and 3 are never received simultaneously at the decoder and show that a strictly larger achievable region is obtained when the encoder maintains joint typicality of codewords only within the required subsets. To prove these results, we derive a lemma called the `subset typicality lemma' which plays a critical role in establishing the new achievable region.

This paper proposes a novel approach to jointly optimize spatial prediction and the choice of the subsequent transform in video and image compression. Under the assumption of a separable first-order Gauss-Markov model for the image signal, it is shown that the optimal Karhunen-Loeve Transform, given available partial boundary information, is well approximated by a close relative of the discrete sine transform (DST), with basis vectors that tend to vanish at the known boundary and maximize energy at the unknown boundary. The overall intraframe coding scheme thus switches between this variant of the DST named asymmetric DST (ADST), and traditional discrete cosine transform (DCT), depending on prediction direction and boundary information. The ADST is first compared with DCT in terms of coding gain under ideal model conditions and is demonstrated to provide significantly improved compression efficiency. The proposed adaptive prediction and transform scheme is then implemented within the H.264/AVC intra-mode framework and is experimentally shown to significantly outperform the standard intra coding mode. As an added benefit, it achieves substantial reduction in blocking artifacts due to the fact that the transform now adapts to the statistics of block edges. An integer version of this ADST is also proposed.

When is optimal estimation linear? It is well known that when a Gaussian source is contaminated with Gaussian noise, a linear estimator minimizes the mean square estimation error. This paper analyzes, more generally, the conditions for linearity of optimal estimators. Given a noise (or source) distribution, and a specified signal-to-noise ratio (SNR), we derive conditions for existence and uniqueness of a source (or noise) distribution for which theLpoptimal estimator is linear. We then show that if the noise and source variances are equal, then the matching source must be distributed identically to the noise. Moreover, we prove that the Gaussian source-channel pair is unique in the sense that it is the only source-channel pair for which the mean square error (MSE) optimal estimator is linear at more than one SNR values. Furthermore, we show the asymptotic linearity of MSE optimal estimators for low SNR if the channel is Gaussian regardless of the source and, vice versa, for high SNR if the source is Gaussian regardless of the channel. The extension to the vector case is also considered where besides the conditions inherited from the scalar case, additional constraints must be satisfied to ensure linearity of the optimal estimator.

Error resilient video coding critically relies on the accuracy of end to-end distortion estimation. An established solution, the recursive optimal per-pixel estimate (ROPE), is based on tracking the first and second moments of the decoder reconstructed pixels. This paper is focused on an alternative estimation approach, the spectral coefficient-wise optimal recursive estimate (SCORE), whose recursion is performed in the transform domain. The SCORE formulation is extended to derive a new technique for effective end-to-end distortion estimation, which accounts for sub-pixel motion compensation. Specifically, this technique exploits properties of the transform, such as coefficient de-correlation and energy compaction, to overcome ROPE's remaining shortcoming due to the proliferation of cross-correlation terms requiring excessive complexity or relatively crude approximations. Experiments show that the accuracy of SCORE matches ROPE in the full-pixel motion compensation setting, where ROPE is known to be optimal. More importantly, in the problematic setting of sub-pixel motion compensation, SCORE substantially outperforms ROPE and yields highly accurate distortion estimation.

Canonical distributed quantization schemes do not scale to large sensor networks due to the exponential decoder storage complexity that they entail. Prior efforts to tackle this issue have largely been limited to the suboptimal schemes of source grouping and decoding, thus failing to use all available information at the decoder. We propose a new decoding paradigm where all received bits are used in decoding. Essentially, to decode each source, we partition the space of received bit-tuples using a nearest neighbor quantizer at a decoding rate consistent with the allowed complexity and each partition is then mapped to a reconstruction value for that source. To avoid local minima in design, we resort to deterministic annealing to determine the nearest neighbor partition function (the partitioning prototypes) from the training set. Results on several data-sets show substantial gains over naive and other competing approaches.

A novel scalable coding approach is proposed for video transmission over lossy networks, which builds on two estimation-theoretic (ET) paradigms previously developed by our group: (1) an ET approach to enhancement layer prediction in scalable video coding (ET-SVC) that optimally combines all available information from both the current base layer and prior enhancement layer frames, and (2) the spectral coefficient-wise optimal recursive estimate (SCORE) of end-to-end distortion. SCORE provides the encoder with an estimate of distortion per decoder-reconstructed transform coefficient, accounting for the effects of quantization, concealment, packet loss and error propagation via the prediction loop. The current work significantly extends the scope of SCORE to encompass the setting of ET-SVC, whose prediction involves non-linear operations. This advance enables optimization of ET-SVC systems for transmission over lossy networks, thereby combining optimal prediction with optimal mode decisions at the enhancement layer. Experiments first demonstrate the estimation accuracy of SCORE in the settings of the ET-SVC coder. They then show considerable gains when SCORE is incorporated into ET-SVC to optimize encoding decisions under a wide range of packet loss and bit rates.

It is well-known for transform coding of multivariate Gaussian sources, that the Karhunen Loeve transform (KLT) minimizes the mean square error distortion. However, finding the optimal transform for general non-Gaussian sources has been an open problem for decades, despite several important advances that provide some partial answers regarding KLT optimality. In this paper, we present a necessary and sufficient condition for optimality of a transform when high resolution, variable rate quantizers are employed. We present not only a complete characterization of when KLT is optimal, but also a determining condition for optimality of a general (non-KLT) transform. This necessary and sufficient condition is shown to have direct connections to the well studied source separation problem. This observation can impact source separation itself, as illustrated with a new optimality result. Finally, we combine the transform optimality condition with algorithmic tools from source separation, to derive a practical numerical method to search for the optimal transform in source coding.

This paper considers the problem of optimal multi-hop routing of correlated sources over a network with multiple sinks and arbitrary network demands. We recently introduced a new routing paradigm in [10] called `dispersive information routing' (DIR), wherein the intermediate nodes are allowed to split a packet and forward a subset of the received bits on each forward path. DIR ensures that each sink receives just the information it requires to decode the sources it intends to reconstruct, and thereby outperforms conventional routing techniques in the literature. We proposed an encoding scheme called `power binning' which achieves complete rate region and the minimum cost under this paradigm when each sink is allowed to receive packets only from the sources it wants to reconstruct. This paper considers the optimum encoding scheme when every source can (possibly) communicate with every sink irrespective of what the sinks reconstruct. This generalization happens to be considerably more complex and we derive an achievable rate region and an associated achievable cost using principles from distributed source coding and multiple descriptions encoding.

This paper presents a new achievable rate-distortion region for the L-channel multiple descriptions problem. Currently, the most popular region for this problem is due to Venkataramani, Kramer and Goyal [3]. Their encoding scheme is an extension of the Zhang-Berger scheme to the L-channel case and includes a combinatorial number of refinement codebooks, one for each subset of the descriptions. All the descriptions also share a single common codeword, which introduces redundancy, but assists in better coordination of the descriptions. This paper proposes a novel encoding technique involving `Combinatorial Message Sharing', where every subset of the descriptions may share a distinct common message. This introduces a combinatorial number of shared codebooks along with the refinement codebooks of [3]. These shared codebooks provide a more flexible framework to trade off redundancy across the messages for resilience to descriptions loss. We derive an achievable rate-distortion region for the proposed technique, and show that it subsumes the achievable region of [3].

We recently proposed a new coding scheme for the L-channel multiple descriptions (MD) problem for general sources and distortion measures involving `Combinatorial Message Sharing' (CMS) [7] leading to a new achievable rate-distortion region. Our objective in this paper is to establish that this coding scheme strictly subsumes the most popular region for this problem due to Venkataramani, Kramer and Goyal (VKG) [3]. In particular, we show that for a binary symmetric source under Hamming distortion measure, the CMS scheme provides a strictly larger region for all L>; 2. The principle of the CMS coding scheme is to include a common message in every subset of the descriptions, unlike the VKG scheme which sends a single common message in all the descriptions. In essence, we show that allowing for a common codeword in every subset of descriptions provides better freedom in coordinating the messages which can be exploited constructively to achieve points outside the VKG region.

This paper considers the problem of characterizing the optimal tradeoff between the total transmit versus receive rate in the Gray-Wyner network. This tradeoff plays a crucial role in many important practical applications including establishing fundamental limits in databases for correlated sources and in minimum cost routing for networks. We develop the insight into this tradeoff by defining two quantities C(X, Y; R' ) and K(X,Y;R"), which quantify the shared rate as a function of the total transmit and receive rates respectively. Closely tied up with this tradeoff is the notion of common information of two dependent random variables. The two most influential definitions are due to Wyner [2] and Gács-Körner [1]. Though it is well know that these definitions can be characterized as two extreme points in the Gray-Wyner region, no contour with operational significance is known which connects them. We will show that the tradeoff between transmit and receive rates leads to a contour of points on the boundary of Gray-Wyner region which passes through the operating points of Wyner and Gács-Körner. We use these properties to derive alternate characterizations for the two definitions of common information under a broader unified framework.

Temporal prediction in standard video coding is performed in the spatial domain, where each pixel block is predicted from a motion-compensated pixel block in a previously reconstructed frame. Such prediction treats each pixel independently and ignores underlying spatial correlations. In contrast, this paper proposes a paradigm for motion-compensated prediction in the transform domain, that eliminates much of the spatial correlation before individual frequency components along a motion trajectory are independently predicted. The proposed scheme exploits the true temporal correlations, that emerge only after signal decomposition, and vary considerably from low to high frequency. The scheme spatially and temporally adapts to the evolving source statistics via a recursive procedure to obtain the cross-correlation between transform coefficients on the same motion trajectory. This recursion involves already reconstructed data and precludes the need for any additional side-information in the bit-stream. Experiments demonstrate substantial performance gains in comparison with the standard codec that employs conventional pixel domain motion-compensated prediction.

This letter investigates source-channel coding for error-resilient video streaming using redundant encoding. We estimate the end-to-end distortion per redundantly encoded macroblock (MB) via extension of the recursive optimal per-pixel estimate to encompass redundant transmissions. Redundant encoding is formulated as joint optimization of the MB parameters in the primary and redundant transmissions. We present three encoding strategies with different gain-complexity tradeoffs. The proposed methods are general in nature, and could be implemented on top of any (hybrid) video codec. Simulation results employing H.264's redundant slice mechanism show significant performance gains over conventional error-resilient encoding methods and naive redundant encoding schemes.

This paper focuses on contour tracking, an important problem in computer vision, and specifically on open contours that often directly represent a curvilinear object. Compelling applications are found in the field of bioimage analysis where blood vessels, dendrites, and various other biological structures are tracked over time. General open contour tracking, and biological images in particular, pose major challenges including scene clutter with similar structures (e.g., in the cell), and time varying contour length due to natural growth and shortening phenomena, which have not been adequately answered by earlier approaches based on closed and fixed end-point contours. We propose a model-based estimation algorithm to track open contours of time-varying length, which is robust to neighborhood clutter with similar structures. The method employs a deformable trellis in conjunction with a probabilistic (hidden Markov) model to estimate contour position, deformation, growth and shortening. It generates a maximum a posteriori estimate given observations in the current frame and prior contour information from previous frames. Experimental results on synthetic and real-world data demonstrate the effectiveness and performance gains of the proposed algorithm.

We consider approaches for similarity search in correlated, high-dimensional data sets, which are derived within a clustering framework. We note that indexing by “vector approximation” (VA-File), which was proposed as a technique to combat the “Curse of Dimensionality,” employs scalar quantization, and hence necessarily ignores dependencies across dimensions, which represents a source of suboptimality. Clustering, on the other hand, exploits interdimensional correlations and is thus a more compact representation of the data set. However, existing methods to prune irrelevant clusters are based on bounding hyperspheres and/or bounding rectangles, whose lack of tightness compromises their efficiency in exact nearest neighbor search. We propose a new cluster-adaptive distance bound based on separating hyperplane boundaries of Voronoi clusters to complement our cluster based index. This bound enables efficient spatial filtering, with a relatively small preprocessing storage overhead and is applicable to euclidean and Mahalanobis similarity measures. Experiments in exact nearest-neighbor set retrieval, conducted on real data sets, show that our indexing method is scalable with data set size and data dimensionality and outperforms several recently proposed indexes. Relative to the VA-File, over a wide range of quantization resolutions, it is able to reduce random IO accesses, given (roughly) the same amount of sequential IO operations, by factors reaching 100X and more.

This paper focuses on optimal analog mappings for zero-delay, distributed source-channel coding. The objective is to obtain the optimal vector transformations that map between m-dimensional source spaces and k-dimensional channel spaces, subject to a prescribed power constraint and assuming the mean square error distortion measure. Closed-form necessary conditions for optimality of encoding and decoding mappings are derived. An iterative de- sign algorithm is proposed, which updates encoder and decoder mappings by sequentially enforcing the complementary optimality conditions at each iteration. The obtained encoding functions are shown to be a continuous relative of, and in fact subsume as a special case, the Wyner-Ziv mappings encountered in digital distributed source coding systems, by mapping multiple source intervals to the same channel interval. Example mappings and performance results are presented for Gaussian sources and channels.

Current video coding schemes employ motion compensation to exploit the fact that the signal forms an auto-regressive process along the motion trajectory, and remove temporal redundancies with prior reconstructed samples via prediction. However, the decoder may, in principle, also exploit correlations with received encoding information of future frames. In contrast to current decoders that reconstruct every block immediately as the corresponding quantization indices are available, we propose an estimation-theoretic delayed decoding scheme which leverages quantization and motion information of one or more future frames to refine the reconstruction of the current block. The scheme, implemented in the transform domain, efficiently combines all available (including future) information in an appropriately derived conditional pdf, to obtain the optimal delayed reconstruction of each transform coefficient in the frame. Experiments demonstrate substantial gains over the standard H.264 decoder. The scheme learns the autoregressive model from information available to the decoder, and compatibility with the standard syntax and existing encoders is retained.

This paper proposes a new approach to combined spatial (Intra) prediction and adaptive transform coding in block-based video and image compression. Context-adaptive spatial prediction from available, previously decoded boundaries of the block, is followed by optimal transform coding of the prediction residual. The derivation of both the prediction and the adaptive transform for the prediction error, assumes a separable first-order Gauss-Markov model for the image signal. The resulting optimal transform is shown to be a close relative of the sine transform with phase and frequencies such that basis vectors tend to vanish at known boundaries and maximize energy at unknown boundaries. The overall scheme switches between the above sine-like transform and discrete cosine transform (per direction, horizontal or vertical) depending on the prediction and boundary information. It is implemented within the H.264/AVC intra mode, is shown in experiments to significantly outperform the standard intra mode, and achieve significant reduction of the blocking effect.

Predictive coding eliminates redundancy due to correlations between the current and past signal samples, so that only the innovation, or prediction residual, needs to be encoded. However, the decoder may, in principle, also exploit correlations with future samples. Prior decoder enhancement work mainly applied a non-causal filter to smooth the regular decoder reconstruction. In this work we broaden the scope to pose the problem: Given an allowed decoding delay, what is the optimal decoding algorithm for predictively encoded sources? To exploit all information available to the decoder, the proposed algorithm recursively estimates conditional probability densities, given both past and available future information, and computes the optimal reconstruction via conditional expectation. We further derive a near-optimal low complexity approximation to the optimal decoder, which employs a time-invariant lookup table or codebook approach. Simulations indicate that the latter method closely approximates the optimal delayed decoder, and that both considerably outperform the competition.

This paper considers the problem of distributed source coding for a large sensor network. A typical shortcoming of current approaches to true distributed coding is the exponential growth of the decoder codebook size with the number of sources in the network. This growth in complexity renders many traditional approaches impractical for even moderately sized sensor networks. Inspired by our recent results on fusion coding for selective retrieval, we propose a new distributed coding approach that scales to a large number of sources. Central to our approach is a “bit-subset selector” module whose role is to judiciously extract an appropriate subset of the received bits for decoding per individual source. This, together with joint design of all system components, enables direct optimization of the decoder complexity-distortion tradeoff, and thereby the desired scalability. Experiments on both real and synthetic data-sets show considerable gains over heuristic schemes.

MPEG-4 High-Definition Advanced Audio Coding (HD-AAC) enables scalable-to-lossless (SLS) audio coding with an Advanced Audio Coding (AAC) base layer, and fine-grained enhancements based on the MPEG SLS standard. While the AAC core offers better perceptual quality at lossy bit-rates, its inclusion has been observed to compromise the ultimate lossless compression performance as compared to the SLS `non-core' (i.e., without an AAC base layer) codec. In contrast, the latter provides excellent lossless compression but with significantly degraded audio quality at low bit-rates. We propose a trellis-based approach to directly optimize the trade-off between the quality of the AAC core and the lossless compression performance of SLS. Simulations to test the effectiveness of the approach demonstrate the capability to adjust the trade-off to match application specific needs. Moreover, such optimization can in fact achieve an AAC core of superior perceptual quality while maintaining state-of-the-art (and surprisingly sometimes even better) lossless compression, all this in compliance with the HD-AAC standard.

Temporal prediction in standard video coding is performed in the spatial domain, where each pixel is predicted from a motion-compensated reconstructed pixel in a prior frame. This paper is premised on the realization that such standard prediction treats each pixel independently and ignores underlying spatial correlations, while transform-domain prediction would eliminate much of the spatial correlation before signal components (transform coefficients) are independently predicted. Moreover, the true temporal correlations emerge after signal decomposition, and vary considerably from low to high frequency components. This precise nature of the temporal dependencies is entirely masked in spatial domain prediction by the high temporal correlation coefficient (ρ ≈ 1) imposed on all pixels by the dominant low frequency components. We derive optimal transform-domain per-coefficient predictors for three main settings: basic inter-frame prediction; bi-directional prediction; and enhancement-layer prediction in scalable coding. Experimental results provide evidence for substantial performance gains in all settings.

Scalable video coding (SVC) employs inter-frame prediction at the base and/or the enhancement layers. Since the base layer can be encoded/decoded independent of the enhancement layers, we consider here the potential gains when prediction at the enhancement layers is delayed to accumulate and incorporate additional future information from the base layer. We build on two basic estimation-theoretic (ET) approaches developed by our group: an ET approach for enhancement layer prediction that optimally combines current base layer with prior enhancement layer information, and our recent ET approach for delayed decoding. The proposed technique fully exploits all the available information from the base layer, including any future frame information, and past enhancement layer information. It achieves considerable gains over zero-delay techniques including both standard SVC, and SVC with optimal ET prediction (but with zero encoding delay).

Tracking of curvilinear structures is a task of fundamental importance in the quantitative analysis of biological structures such as neurons, blood vessels, retinal interconnects, microtubules, etc. The state of the art HMM-based contour tracking scheme for tracking microtubules, while performing well in most scenarios, can miss the track if, during its growth, it intersects another microtubule in its neighbourhood. In this paper we present a graphical model-based tracking algorithm which propagates across frames information about the dynamics of all the microtubules. This allows the algorithm to faithfully differentiate the contour of interest from others that contribute to the clutter, and maintain tracking accuracy. We present results of experiments on real microtubule images captured using fluorescence microscopy, and show that our proposed scheme outperforms the existing HMM-based scheme.

We present a method for object tracking over time sequence imagery. The image plane is represented with a 4-connected planar graph where vertices are associated with pixels. On each image, the outer contour of the object is localized by finding the optimal cycle in the graph such that a cost function based on temporal, appearance and shape priors is minimized. Our contribution is the particle filtering-based framework to integrate the shape cue with the temporal and appearance cues. We demonstrate that incorporating the shape prior yields promising performance improvement over temporal and appearance priors on various object tracking scenarios.

This paper considers the problem of minimizing the communication cost for a general multi-hop network with correlated sources and multiple sinks. For the single sink scenario, it has been shown that this problem can be decoupled, without loss of optimality, into two separate subproblems of distributed source coding and finding the optimal routing (transmission structure). It has further been established that, under certain assumptions, such decoupling also applies in the general case of multiple sinks and arbitrary network demands. We show that these assumptions are significantly restrictive, and further provide examples to substantiate the loss, including settings where removing the assumptions yields unbounded performance gains. Finally, an approach to solving the unconstrained problem, where routing and coding cannot be decoupled, is derived based on Han and Kobayashi's achievability region for multi-terminal coding.

When is optimal estimation linear? It is well-known that, in the case of a Gaussian source contaminated with Gaussian noise, a linear estimator minimizes the mean square estimation error. This paper analyzes more generally the conditions for linearity of optimal estimators. Given a noise (or source) distribution, and a specified signal to noise ratio (SNR), we derive conditions for existence and uniqueness of a source (or noise) distribution that renders the Lpnorm optimal estimator linear. We then show that, if the noise and source variances are equal, then the matching source is distributed identically to the noise. Moreover, we prove that the Gaussian source-channel pair is unique in that it is the only source-channel pair for which the MSE optimal estimator is linear at more than one SNR values.

In this paper, we consider the problem of minimum cost joint compression and routing for networks with multiple-sinks and correlated sources. We introduce a routing paradigm, called dispersive information routing, wherein the intermediate nodes are allowed to forward a subset of the received bits on subsequent paths. This paradigm opens up a rich class of research problems which focus on the interplay between encoding and routing in a network. What makes it particularly interesting is the challenge in encoding sources such that, exactly the required information is routed to each sink, to reconstruct the sources they are interested in. We demonstrate using simple examples that our approach offers better asymptotic performance than conventional routing techniques. We also introduce a variant of the well known random binning technique, called `power binning', to encode and decode sources that are dispersively transmitted, and which asymptotically achieves the minimum communication cost within this routing paradigm.

Transmission of compressed video over unreliable networks is vulnerable to errors and error propagation. Multi-hypothesis motion compensated prediction (MHMCP) which was originally developed to improve compression efficiency has been shown to have a good error resilience property. In this paper we improve the overall performance of MHMCP in packet loss scenarios by performing optimal mode switching within a rate distortion framework. The approach builds on the recursive optimal per-pixel estimate (ROPE), which is extended by re-deriving recursion formulas for the more complex MHMCP setting, so as to achieve an accurate estimation of the end-to-end distortion. Simulation results show significant performance gains over the standard MHMCP scheme and the importance of performing effective mode decisions. We also show results with comparison to conventional ROPE.

Many important audio coding applications, such as streaming and playback of stored audio, involve offline compression. In such scenarios, encoding delays no longer represent a major concern. Despite this fact, most current audio encoders constrain delay by making encoding decisions on a per frame basis. This paper is concerned with delayed-decision approaches to optimize the encoding operation for the entire audio file. Trellis-based dynamic programming is used for efficient search in the parameter space. A two-layered trellis effectively optimizes the choice of quantization and coding parameters within a frame, as well as window decisions and bit distribution across frames, while minimizing a psychoacoustically relevant distortion measure under a prescribed bit-rate constraint. The bitstream thus produced is standard compatible and there is no additional decoding delay. Objective and subjective results indicate substantial gains over the reference encoder.

This paper is concerned with optimization of the motion compensated prediction framework to improve the error resilience of video coding for transmission over lossy networks. First, accurate end-to-end distortion estimation is employed to optimize both motion estimation and prediction within an overall rate-distortion framework. Low complexity practical variants are proposed: a method to approximate the optimal motion via simple distortion and source coding rate models, and a source-channel prediction method that uses the expected decoder reference frame for prediction. Second, reference frame generation is revisited as a problem of filter design to optimize the error resilience versus coding efficiency tradeoff. The special cases of leaky prediction and weighted prediction (i.e., finite impulse response filtering), are analyzed. A novel reference frame generation approach, called "generalized source-channel prediction", is proposed, which involves infinite impulse response filtering. Experimental results show significant performance gains and substantiate the effectiveness of the proposed encoder optimization approaches.

This paper is concerned with optimal transform coding in conjunction with dithered quantization. While the optimal deterministic quantizer's error is uncorrelated with the reconstructed value, the dithered quantizer yields quantization errors that are correlated with the reconstruction but are white and independent of the source. These properties offer potential benefits, but also have implications on the optimization of the rest of the coder. We derive the optimal transform for consequent dithered quantization. For fixed rate coding, we show that the transform derived for dithered quantization is universally optimal (for all sources), unlike the conventional quantization case where optimality of the Karhunen-Loeve transform is guaranteed for Gaussian sources. Moreover, we establish variable rate coding optimality for Gaussian sources.

Summary form only given: Dithered quantization has useful properties such as producing quantization noise independent of the source and continous reconstruction at the decoder side. Dithered quantizers have traditionally been considered within their natural setting of uniform quantization framework. A uniformly distributed (with step size matched to the quantization interval) dither signal is added before quantization and the same dither signal is subtracted from the quantized value at the decoder side (only subtractive dithering is considered in this paper). The quantized values are entropy coded conditioned on the dither signal. This work proposes and analyzes optimal (non-uniform) dithered quantization. One immediate problem with nonuniform dithered quantization is how to apply dithering for unequal quantization intervals. This problem is circumvented by performing dithering in the companded domain. After appropriate companding, uniform dither can be applied. The quantization problem is defined as finding the optimal compander mapping that minimizes the mean square error. To solve the problem, some approximations of rate and distortion expressions and to the compander mapping are used. First, we only consider the piecewise linear compander which is also used in deterministic quantizers. Also, we assume the error in each half quantization interval (the interval between the decision boundary and the reconstruction) is constant and only a function of the intervals length, i.e., identical to the case where for each interval a uniform dithered quantizer is applied. We also assume that rate can be approximated by the rate of the deterministic quantizer which uses the same compander. We derive the necessary conditions for optimality and design the compander by iterating between the necessary conditions.

Motivated by the paradigm of event-based monitoring, which can potentially alleviate the inherent bandwidth and energy constraints associated with wireless sensor networks, we consider the problem of joint coding of correlated sources under a cost criterion that is appropriately conditioned on event occurrences. The underlying premise is that individual sensors only have access to partial information and, in general, cannot reliably detect events. Hence, sensors optimally compress and transmit the data to a fusion center, so as to minimize the expected distortion in segments containing events. In this work, we derive and demonstrate the approach in the setting of entropy constrained distributed vector quantizer design,using a modified distortion criterion that appropriately accounts for the joint statistics of the events and the observation data. Simulation results show significant gains over conventional design as well as existing heuristic based methods, and provide experimental evidence to support the promise of our approach.

Three-dimensional (3D) integration of a single high performance microprocessor die and multiple DRAM dies has been considered as a viable option to tackle the looming memory wall problem. Meanwhile, on-chip decoupling capacitors are becoming increasingly important to ensure power delivery integrity, particularly for high-performance integrated circuits. Targeting at 3D processor-DRAM integrated computing systems, this paper proposes to use 3D stacked DRAM dies to provide decoupling capacitors for the processor die. This can well leverage the superior capacitor fabrication ability of DRAM to eliminate the area penalty of decoupling capacitor insertion on the processor die. For its practical implementation, a simple uniform decoupling capacitor network design strategy is presented, and circuit SPICE simulations and computer system simulations are carried out to quantitatively demonstrate the effectiveness and illustrate various design trade-offs.

Current audio coding standards employ the modified discrete cosine transform (MDCT) where overlapped frames of audio are windowed and transformed to the frequency domain. Encoding parameters are chosen so as to minimize a distortion measure subject to a rate constraint. At the decoder, inverse transformation involves additional windowing and overlap-add of frames. An analysis of the time domain error in the reconstructed frame reveals that distortion metrics based solely on the MDCT domain error are in fact unable to capture the effects of windowing and overlap-add at the decoder. The main contribution of this paper is a modified distortion metric that does capture these effects via modified discrete sine transform analysis. When incorporated into an Advanced Audio Coder the proposed distortion metric significantly improves subjective quality of reconstructed audio.

This paper considers the problem of scalable distributed coding of correlated sources that are communicated to a central unit. The general setting is typically encountered in sensor networks. The conditions of communication channels between the source encoders and fusion center may be time-varying and it is often desirable to guarantee a base layer of coarse information during channel fades. In addition the desired system should be robust to various scenarios of channel failure and should utilize all the available information to attain the best possible compression efficiency. Although a standard dasiaLloyd-stylepsila distributed coder design algorithm can be generalized to scalable distributed source coding, the resulting algorithm depends heavily on initialization and will virtually always converge to a poor local minimum on the distortion-cost surface. We propose an efficient initialization scheme for such a system, which employs a properly designed multi-stage distributed coder. In our prior work, we highlighted the fundamental conflict that arises when multi-stage coding is directly combined with distributed quantization. Here we use the multi-stage distributed coding system to initialize a scalable distributed coder and propose an iterative algorithm for joint design of all system components once the structural constraint is removed. Simulation results show considerable gains over randomly initialized scalable distributed coder design.

This paper revisits the problem of source-channel coding for error-resilient video streaming, using redundant encoding. We propose a new method to jointly optimize the macroblock (MB) mode in both the primary and the secondary, redundant encoding. Encoding decisions are based on end-to-end distortion using the ROPE estimate, and are adaptive at the MB level. Further, we present a reduced complexity approach to redundant encoding. The proposed methods are general in nature, and could be implemented on top of any (hybrid) video codec. An example implementation employs the redundant slice mechanism of H.264 (JM 13.2). Simulation results show significant performance gains over conventional methods such as fixed redundant encoding schemes or non-redundant optimal MB mode selection.

In this paper, we present an algorithm for occlusion boundary detection. The main contribution is a probabilistic detection framework defined on spatio-temporal lattices, which enables joint analysis of image frames. For this purpose, we introduce two complementary cost functions for creating the spatio-temporal lattice and for performing global inference of the occlusion boundaries, respectively. In addition, a novel combination of low-level occlusion features is discriminatively learnt in the detection framework. Simulations on the CMU Motion Dataset provide ample evidence that proposed algorithm outperforms the leading existing methods.

Motivated by the need to efficiently leverage user relevance feedback in content-based retrieval from image databases, we propose a fast, clustering-based indexing technique for exact nearest-neighbor search that adapts to the Mahalanobis distance with a varying weight matrix. We derive a basic property of point-to-hyperplane Mahalanobis distance, which enables efficient recalculation of such distances as the Mahalanobis weight matrix is varied. This property is exploited to recalculate bounds on query-cluster distances via projection on known separating hyperplanes (available from the underlying clustering procedure), to effectively eliminate noncompetitive clusters from the search and to retrieve clusters in increasing order of (the appropriate) distance from the query. We compare performance with an existing variant of VA-File indexing designed for relevance feedback, and observe considerable gains.

It has been recently discovered that complementary graph entropy characterizes (and offers new insights into) the minimum asymptotic rate for zero-error source coding with decoder side information. This paper presents new results that build on and complement this discovery. Specifically, i) previously unknown subadditivity properties of complementary graph entropy are derived, and ii) zero-error coding rates are characterized in terms of complementary graph entropy for two multiterminal coding scenarios. For both scenarios, the rate characterization implies no rate loss relative to point-to-point source coding.

Motivated by sensor networks, we consider the fusion storage of correlated sources in a database, such that any subset of them may be efficiently retrieved in the future. Only statistical information about future queries is available during encoding and storage. Fusion coding of correlated sources poses new challenges due to the conflicting objectives of exploiting inter-source correlations and enabling efficient selective retrieval. Practical signal compression imposes additional constraints on system complexity. We propose a shared-descriptions approach for the design of lossy fusion coding systems, to manage the precise tradeoffs between storage rate, retrieval rate, distortion and system complexity, within one unified framework. An iterative descent algorithm is derived for the design of such fusion coders. The optimized system provides significant gains over traditional quantization techniques that are not directly optimized for fusion coding.

This paper considers the problem of distributed scalable coding of correlated sources that are communicated to a central unit. The general setting is typically encountered in sensor networks. The conditions of communication channels between the sensor sources and fusion center may be time-varying and it is often desirable to guarantee a base layer of coarse information during channel fades. Specifically, we consider a multi-stage coding system to perform such distributed scalable coding of correlated sources. This problem poses new challenges. We show that mere extensions of distributed coding ideas to include multi-stage coding yield poor rate-distortion performance, due to underlying conflicts between the objectives of scalable and distributed coding. An appropriate system paradigm is developed which allows such tradeoffs to be explicitly controlled within joint optimization of all the system components. We propose an iterative joint design technique and derive the necessary conditions for optimality which yield its update rules. Simulation results show substantial gains over single source (separate) multi-stage coding as well as naive extensions to incorporate scalability in distributed scalable coding schemes.

The fact that audio compression for streaming or storage is usually performed offline alleviates traditional constraints on encoding delay. We propose a rate-distortion optimized approach, within the MPEG Advanced Audio Coding framework, to trade delay for optimal window switching, resource allocation and selection of quantization and coding parameters for the entire audio file using a two-layered trellis. Stages of the outer trellis correspond to audio frames, nodes represent window choices, and branches implement transition constraints. The inner trellis operates within each node of the outer layer and has stages corresponding to scalefactor bands and nodes representing combinations of quantization and coding parameters. A suitable cost, comprising bit consumption and psychoacoustic distortion, is optimized via multiple passes through the two-layered trellis to achieve the desired bitrate. The procedure thus optimizes most of the encoding decisions involved in audio compression. Objective and subjective tests show considerable performance gains.

This paper considers the problem of predictive fusion coding for storage of multiple spatio-temporally correlated sources so as to enable efficient selective retrieval of data from subsets of sources as designated by future queries. Only statistical information about future queries is available during encoding. While temporal correlations can be exploited by coding over large blocks, the growth in encoding complexity renders this approach impractical and hence the interest in a low complexity predictive coding approach. However, the design of optimal predictive fusion coding systems is considerably complicated by the presence of the prediction loop, and the potentially exponential growth of the query sets. We propose a complexity-constrained predictive fusion coder and derive an iterative algorithm for its design, which is based on the "Asymptotic Closed Loop" framework and hence, circumvents convergence and stability issues of traditional predictive quantizer design. The proposed predictive fusion coder optimizes the distortion - retrieval rate tradeoff, given a fixed storage capacity, and provides significant gains over storage schemes that perform only joint compression or memoryless fusion coding of all sources.

This paper presents an open contour tracking method that employs an arc-emission hidden Markov model (HMM). The algorithm encodes the shape information of the structure in a spatially deformable trellis model that is iteratively modified to account for observations in subsequent frames. As the open contour is determined on the trellis of an HMM, a dynamic programming procedure reduces the computational complexity to linear in the length of the structure (or contour). The method was developed for tracking general curvilinear structures, and tested on subcellular image sequences, where microtubules grow, shrink and undergo lateral motion from frame to frame. Microtubule length changes are modeled by the addition of appropriate transient and absorbing states to the HMM. Our results provide experimental evidence for the proposed algorithm's capability to track non-rigid curvilinear objects in challenging environments in terms of noise and clutter.

Motivated by the need to efficiently leverage user relevance feedback in content-based retrieval from image databases, we propose a fast, clustering-based indexing technique for exact nearest-neighbor search that adapts to the Mahalanobis distance with a varying weight matrix. We derive a basic property of point-to-hyperplane Mahalanobis distance, which enables efficient recalculation of such distances as the Mahalanobis weight matrix is varied. This property is exploited to recalculate bounds on query-cluster distances via projection on known separating hyperplanes (available from the underlying clustering procedure), to effectively eliminate noncompetitive clusters from the search and to retrieve clusters in increasing order of (the appropriate) distance from the query. We compare performance with an existing variant of VA-File indexing designed for relevance feedback, and observe considerable gains.

Two dimensional hidden markov models (2D-HMMs) provide substantial benefits for many computer vision and image analysis applications. Many fundamental image analysis problems, including segmentation and classification, are target applications for the 2D- HMMs. As opposed to the i.i.d. assumption of the image observations, the naturally existing spatial correlations can be readily modeled by solving the 2D-HMM decoding problem. However, computational complexity of the 2D-HMM decoding grows exponentially with the image size and is known to be NP-hard. In this paper, we present a conditional iterative decoding (CID) algorithm for the approximate decoding of 2D-HMMs. We compare the performance of the CID algorithm to the Turbo-HMM (T-HMM) decoding algorithm and show that CID gives promising results. We demonstrate the proposed algorithm on modeling spatial deformations of human faces in recognizing people across their different facial expressions.

This paper revisits the problem of source-channel coding for error-resilient video streaming. We propose a new method to enable adaptive redundancy in the bitstream: fine-grain retransmission. Redundancy decisions are made per macroblock (MB), which are locally adaptive and of low overhead, as opposed to coarse packet-level redundancy (e.g. forward error correction). In this scheme, the encoder jointly optimizes the coding mode and redundancy per MB. A corresponding algorithm is presented for exploiting this redundancy at the decoder. The proposed method is general in nature, and can be implemented on top of any (hybrid) video codec. An example implementation is provided, which uses the redundant slice mechanism of H.264 (JM 13.2 reference software). Simulation results show significant performance gains over conventional error-resilient coding techniques.

We consider the problem of storing data from multiple correlated sources in a database, so as to enable efficient future retrieval of data from select subsets of the sources, where only statistical information about queries may be available in advance. This setting poses new challenges in terms of the precise tradeoffs between storage rate, retrieval rate and distortion. We derive a gradient descent algorithm to optimize the joint encoding (storage) procedure, the decoder, and the retrieval procedure via mapping from queries to subsets of the stored data to retrieve and decode, so that the average retrieval rate-distortion cost is minimized, given a pre-specified overall storage capacity (or rate). Experiments conducted on real and synthetic data-sets demonstrate that our selective retrieval procedure is able to achieve significantly better trade-offs than joint compression, with retrieval speed-ups reaching 5X and distortion gains of up to 3.5 dB possible.

We propose a frame loss concealment technique for decoders compatible with MPEG advanced audio coding (AAC). The spectral information of the lost frame is estimated in the modified discrete cosine transform (MDCT) domain via efficient techniques that are tailored to individual source signal components: in noise-like spectral bins the MDCT coefficients are obtained by shaped-noise insertion, while coefficients in tone-dominant bins are estimated by frame interpolation followed by a refinement procedure so as to optimize the fit of the concealed frames with neighboring frames. Experimental results demonstrate that the proposed technique offers performance superior to techniques adopted in commercial AAC decoders.

We consider approaches for exact similarity search in a high dimensional space of correlated features representing image datasets, based on principles of clustering and vector quantization. We develop an adaptive cluster distance bound based on separating hyperplanes, that complements our index in selectively retrieving clusters that contain data entries closest to the query. Experiments conducted on real data-sets confirm the efficiency of our approach with random disk IOs reduced by 100X, as compared with the popular vector approximation-file (VA-File) approach, when allowed (roughly) the same number of sequential disk accesses, with relatively low preprocessing storage and computational costs.

Tracing of curvilinear structures is one of the fundamental tools in the quantitative analysis of biological images, for extracting information about structures such as blood vessels, neurons, microtubules, and similar entities. Due to the limitations in biological sample preparation and fluorescence imaging, typical images in live cell studies exhibit severe noise and considerable clutter. These images are manually analyzed through a laborious and approximate set of quantification tasks. In this paper, we describe a constrained optimization method for extracting curvilinear structures from live cell fluorescence images. We show that the proposed method is largely insensitive to frequent intersections, intensity variations along the curve, and generates successful traces within noisy regions. We demonstrate the results of our approach on live cell microtubule images.

The recursive optimal per-pixel estimate (ROPE) is an effective end-to-end distortion estimation scheme. Most existing ROPE-based applications assume that: (i) the encoder knows exactly the actual packet loss rate and (ii) the decoder error concealment scheme; (iii) no deblocking in-loop filtering is employed. However, in practice, these assumptions may not all be valid. In this paper, we investigate the impact of mismatch between assumed and actual conditions on the performance of ROPE and corresponding rate-distortion optimized coding mode selection. Useful conclusions are drawn from extensive experimental results.

This paper investigatesdistributedpredictivecoding of correlated sources with memory, which are communicated to a central receiver. This is the setting typically encountered in sensor networks. While source memory may be exploited by distributed coding of large source blocks (vectors), the growth in complexity (and delay) is often unacceptable in practice, hence the interest in a low complexity predictive approach. We first consider the inherent "conflict" between distributed and predictive coding due to the impact of distributed quantization on the prediction loop. This is coupled with the effects of closed loop prediction, which destabilize standard Lloyd-like code design methods. An iterative algorithm is derived, which optimizes the overall system while imposing zero decoder drift due to distributed quantization. The approach circumvents convergence and stability issues of traditional predictive quantizer design by employing an "asymptotic closed loop" framework which is adapted for distributed predictive system design. The scheme efficiently utilizes both the temporal and inter-source correlations and subsumes as extreme special cases both separate source predictive coding, and distributed coding of memoryless correlated sources.

We present an automated method for the tracking and dynamics modeling of microtubules -a major component of the cytoskeleton- which provides researchers with a previously unattainable level of data analysis and quantification capabilities. The proposed method improves upon the manual tracking and analysis techniques by i) increasing accuracy and quantified sample size in data collection, ii) eliminating user bias and standardizing analysis, iii) making available new features that are impractical to capture manually, iv) enabling statistical extraction of dynamics patterns from cellular processes, and v) greatly reducing required time for entire studies. An automated procedure is proposed to track each resolvable microtubule, whose aggregate activity is then modeled by mixtures of Hidden Markov Models to uncover dynamics patterns of underlying cellular and experimental conditions. Our results support manually established findings on an actual microtubule dataset and illustrate how automated analysis of spatial and temporal patterns offers previously unattainable insights to cellular processes.

This paper considers the design of efficient quantizers for a distributed source coding system. The information is encoded at independent terminals and transmitted across separate channels, any of which may fail. The scenario subsumes a wide range of vector quantization problems. Greedy descent methods rely heavily on initialization, and the presence of numerous 'poor' local optima on the distortion cost surface strongly motivates the use of a global design algorithm. We propose a deterministic annealing approach for the design of all components of a generic distributed source coding system. Our approach avoids many poor local optima, is independent of initialization, and does not assume any prior information on the underlying source distribution. Simulation results show significant gains over an iterative greedy algorithm.

This paper proposes an efficient method for frame loss concealment within the advanced audio coding (AAC) decoder, which can effectively mitigate the adverse impact of transmission errors on the reconstruction quality. The lost frame information is estimated in the modified discrete cosine transform (MDCT) domain in terms of magnitude and sign of the coefficients. A computationally efficient approach that is capable of providing accurate estimation is employed for the magnitude estimate. Enhanced sign estimation is developed and implemented, which exploits extra information from encoder. Extensive subjective quality evaluation demonstrates that the proposed method achieves substantial quality improvement with minimal encoder assistance.

The focus of this work is on the design of efficient quantizers for correlated sources subject to complexity limitations on the encoding terminals. Existing iterative descent methods rely heavily on initialization, and the prevalence of numerous 'poor' local optima strongly motivates the use of a global design algorithm. We propose a multiple-prototype based deterministic annealing approach for the joint design of all components of a generic distributed source coding system. Our approach avoids many poor local optima, is independent of initialization and does not assume any prior information on the underlying source distribution. Simulation results show substantial gains over a Lloyd-like iterative algorithm

This paper proposes an error-resilient modification of conventional (encoder-reconstruction based) prediction framework in video coding. The technique is called generalized source-channel prediction (GSCP) and generates a prediction reference for the next frame as a weighted sum of the current frame reconstruction and the prediction reference of the last frame. Compared to existing leaky prediction, GSCP achieves better coding efficiency in single layer video coding, and specifically better exploits the robustness benefits offered by Intra coded macroblocks in past frames so as to reduce error propagation in the future frames. Significant performance gains were observed in simulations and support the effectiveness of GSCP.

This paper presents a multilevel (ML) flash memory on-chip error correction system design based on the concept of trellis coded modulation (TCM). This is motivated by the non-trivial modulation process in ML memory storage and the effectiveness of TCM on integrating coding with modulation to provide better performance. Using code storage 2bits/cell flash memory as a test vehicle, the effectiveness of TCM-based systems, in terms of error-correcting performance, coding redundancy, silicon cost, and operation latency, has been successfully demonstrated

This paper considers the problem of selecting a set of parameter values from a given parameter space, in order to perform rate-distortion optimization in the context of audio compression. Due to interdependencies between parameters, separate optimization of parameter values is inherently suboptimal, yet a straightforward brute-force joint search involves prohibitive computational complexity. This work proposes a new method for joint rate-distortion optimization, while accounting for interparameter dependencies. The optimal solution is achieved, at significantly reduced complexity as compared to a brute-force search, by employing a Viterbi search over a trellis. Two objective distortion metrics are specifically considered: the average, and the maximum noise-to-mask ratio. Subjective (AB/MOS) and objective (average/maximum noise-to-mask ratio) tests demonstrate considerable gains at low bit rates of 16 kbps per channel for a 44.1-kHz sampled audio signal using the proposed approach.

We propose two quantization techniques for improving the bit-rate scalability of compression systems that optimize a weighted squared error (WSE) distortion metric. We show that quantization of the base-layer reconstruction error using entropy-coded scalar quantizers is suboptimal for the WSE metric. By considering the compandor representation of the quantizer, we demonstrate that asymptotic (high resolution) optimal scalability in the operational rate-distortion sense is achievable by quantizing the reconstruction error in the compandor's companded domain. We then fundamentally extend this work to the low-rate case by the use of enhancement-layer quantization which is conditional on the base-layer information. In the practically important case that the source is well modeled as a Laplacian process, we show that such conditional coding is implementable by only two distinct switchable quantizers. Conditional coding leads to substantial improvement over the companded scalable quantization scheme introduced in the first part, which itself significantly outperforms standard techniques. Simulation results are presented for synthetic memoryless Laplacian sources with mu-law companding, and for real-world audio signals in conjunction with MPEG AAC. Using the objective noise-mask ratio (NMR) metric, the proposed approaches were found to result in bit-rate savings of a factor of 2 to 3 when implemented within the scalable MPEG AAC. Moreover, the four-layer scalable coder consisting of 16-kb/s layers achieves performance close to that of the 64-kb/s nonscalable coder on the standard test database of 44.1-kHz audio

The desire for large size, high-speed, and low-power on-chip memory necessitates early and accurate estimates of memory performance. A new performance model as well as an early cache design tool and predictor of access and cycle time for cache stack (PRACTICS) has been developed for on-chip static random access memory (SRAM) cache design that includes both delay and dynamic-power models. Efficient models for distributed interconnect delays, verified by Cadence simulations, are introduced, and their necessity is demonstrated. In the delay model, the access time is estimated by decomposing each component into several equivalent lumped resistance-capacitance (RC) circuits and using an appropriate order pi model to approximate the distributed wire delays of each stage. The dynamic-power model calculates the charging power dissipation of the load capacitances using the same equivalent lumped RC circuits. The delay model has been validated with an Intel 18-Mb SRAM at the 180-nm node, achieving accuracy to within 10% of the measured results. The dynamic-power model has been validated with an International Business Machines Corporation (IBM) 18-Mb SRAM at the 180-nm node, to within 13% of the measured power consumption. Detailed comparisons between PRACTICS and cache access and cycle time model (CACTI) in both validation cases indicate that an improved wire delay, appropriate circuit structures, and technology dependent parameters are necessary to accurately predict large cache memory performance at deep submicrometer technology nodes. PRACTICS is used to analyze the access time and power consumption in terms of cache sizes and various degrees of associativity for architectural studies. In addition, the PRACTICS simulation results show that repeater insertion reduces the access time significantly, with a small overhead in dynamic-power consumption for large size cache design at deep submicrometer technology

This correspondence presents a novel application of the theta function defined by Lovasz. The problem of coding for transmission of a source through a channel without error when the receiver has side information about the source is analyzed. Using properties of the Lovasz theta function, it is shown that separate source and channel coding is asymptotically suboptimal in general. By contrast, in the case of vanishingly small probability of error, separate source and channel coding is known to be asymptotically optimal. For the zero-error case, it is further shown that the joint coding gain can in fact be unbounded. Since separate coding simplifies code design and use, conditions on sources and channels for the optimality of separate coding are also derived

Rate-distortion optimized motion compensation was originally proposed to improve the source coding efficiency of low bit-rate video coding. This paper investigates the potential benefits of extensions to explicitly handle transmission over lossy networks. The important impact of appropriate motion compensation on error resilience is identified and exploited to enhance performance. The expected end-to-end distortion, rather than the source coding distortion, is employed in the rate-distortion optimization criterion. The accuracy of the distortion estimate is crucial when optimizing over the motion vectors (as compared to the less sensitive inter/intra mode decision), and is ensured here by adopting the recursive optimal per-pixel estimate (ROPE) method. The main objective is to assess the gains achievable by such source-channel motion compensation, and this is given priority over complexity considerations. Significant performance gains in simulation demonstrate the potential of rate-distortion optimized motion compensation to improve the error resilience of video coding.

This paper is concerned with open questions and modifications to expand the applicability of the recursive optimal per-pixel estimate (ROPE) of end-to-end distortion, which are particularly relevant to H.264. One open question involves the emergence of cross-correlation terms in the case of sub-pixel prediction or other pixel filtering operations. A new and improved low-complexity approximation is proposed, which accounts for the inter-pixel distance. Another open question involves the commonly ignored effects of rounding and clipping. The cumulative impact of rounding on the distortion estimate is shown to be extensive at low to medium packet-loss rates. Two schemes are proposed for effective rounding and clipping error compensation. Simulation results for H.264 with 1/4-pel prediction show that the revised ROPE maintains low complexity and achieves estimation accuracy that closely matches that of ROPE in the simpler case of full-pixel prediction, where it is optimal.

Motivated by the sensor network setting, we consider lossless storage of correlated discrete memoryless sources. The underlying tradeoff is between exploitation of inter-source correlation for low rate storage and efficient (low rate) selective retrieval from the fusion storage. We define the problem of shared descriptions (SD) source coding and relate it to the storage and retrieval problem. We present an achievable rate region for the SD problem and use it to characterize the storage vs. retrieval tradeoff

This paper proposes a new measure of "distance" between faces. This measure involves the estimation of the set of possible transformations between face images of the same person. The global transformation, which is assumed to be too complex for direct modeling, is approximated by a patchwork of local transformations, under a constraint imposing consistency between neighboring local transformations. The proposed system of local transformations and neighboring constraints is embedded within the probabilistic framework of a two-dimensional hidden Markov model. More specifically, we model two types of intraclass variabilities involving variations in facial expressions and illumination, respectively. The performance of the resulting method is assessed on a large data set consisting of four face databases. In particular, it is shown to outperform a leading approach to face recognition, namely, the Bayesian intra/extrapersonal classifier.

This correspondence investigates the behavior of the compound channel under a zero-error constraint. We derive expressions for the capacity when a) neither the encoder nor decoder has side-information about the channel; b) when only the encoder has such side-information. These expressions are given in terms of capacities of appropriately defined sets of graphs. We clarify that an earlier treatment of the zero-error capacity of a compound channel corresponds to the case where the decoder has side-information about the channel. We also characterize the minimum asymptotic rate for the source coding dual of the compound channel problem, namely, source coding with compound side information. Finally, we contrast the zero-error and asymptotically vanishing error capacities of the compound channel.

This correspondence focuses on a significant distinction between two hierarchical type covering strategies, namely, weak and strong covering, and on the impact of this distinction on known results. In particular, it is demonstrated that the rate region for weak covering, whose natural use is in scalable source coding, is generally larger than the rate region for strong covering, which is primarily useful in hierarchical guessing. This correspondence also presents a corrected converse result for the hierarchical guessing problem.

This paper presents an algorithm to optimize the tradeoff between rate and expected end-to-end distortion of a video sequence transmitted over a packet network. The approach optimizes the source coding parameters, slicing, network QoS class selection and/or error control coding parameters, and accounts for the effects of compression, packetization, error propagation, and concealment at the decoder. It builds on, and substantially extends the applicability of, the recursive optimal per-pixel estimate (ROPE) technique for end-to-end distortion estimation. A trellis-based algorithm is introduced in order to overcome macroblock interdependencies in the estimation procedure, and allow adaptive slicing. Moreover, we propose a complementary packetization scheme to efficiently arrange the slices into packets for FEC protection while minimizing rate loss due to padding. Simulations demonstrate consistent gains over currently used techniques.

A cache access time model, PRACTICS (predictor of access and cycle time for cache stack), has been developed to optimize the memory array architecture for the minimum access and cycle times of on-chip memory using circuit models based on Cadence simulations. Lumped RC models have been used to approximate the distributed RC interconnect network in the access time models. Both SRAM and DRAM models have been validated with industrial designs. The limited influences of gate far-out and transistor size on the cache array architecture indicate that interconnect delay is dominant at deep submicron technologies.

Motion-compensated prediction that accounts for loss in the channel is achieved by the source-channel prediction (SCP) method, which is based on the expected decoder reconstruction of past frames (rather than their encoder reconstruction). The decoder reconstruction is estimated by exploiting the recursive optimal per-pixel estimate (ROPE), which explicitly accounts for the quantization distortion, channel loss, error propagation, as well as the decoder operation and achieves improved error resilience. We take this paradigm further by noting that the decoder can, in turn, be reoptimized to match the modification introduced to the encoder for SCP. Simulation results demonstrate substantial performance gains over conventional decoding. We then examine the benefits of re-optimizing the encoder for the newly matched decoder, and then reoptimizing the decoder, etc. and note that further incremental gains are minor. Hence, one complete round of SCP optimization offers significant gains, but multiple reoptimization iterations may not be cost-effective.

The compound channel is one of the simplest generalizations of the discrete memoryless channel (DMC). In this paper, we characterize the zero-error capacity when neither the encoder nor the decoder is informed of the choice of DMC s. We present a complete characterization of the compound channel capacities

A basic problem in information theory is source coding under a distortion constraint when the decoder has side-information about the source. In this paper the problem of variable length coding of a memoryless source under a maximum distortion constraint when there is side-information solely at the decoder is focused. Using a combinatorial approach, a nonsingle-letter expression for the minimum asymptotic average rate as well as single-letter bounds on this rate is derived

This paper describes the guessing subject to rate-distortion theory. The concept of type covering is the set of vectors with the identical distortion balls. The main use of hierarchical type covering was the determination of achievable error exponents in scalable source coding. Weak covering is sufficient for that purpose. Strong covering is necessary for hierarchical guessing. The two covering strategies and their characterizations lead to different rate regions.

This paper investigates the relationship between rate-distortion theory and efficient content-based data retrieval from high-dimensional databases. We consider database design as the encoding of a data object sequence, and retrieval from the database as the decoding of the sequence using side information (i.e., the query) available only at the decoder. We show that, in this setting, the optimal asymptotic tradeoff between the search time R/sub s/ (bits per data object read from the storage device) and the expected search accuracy D/sub s/ (relevance of the retrieved data set) is given by the Wyner-Ziv solution with a side-information-dependent distortion measure. Moreover, the data indexing and retrieval problem is, in general, inseparable from the data compression problem. Data items selected by the search procedure, which can be stored in the disk with a limited total rate of R/sub r/ /spl ges/ R/sub s/, need to be presented at a prescribed expected reconstruction quality D/sub r/. This is, hence, a problem of scalable source coding or successive refinement, albeit with differing layer distortion measures to quantify search and reconstruction quality, respectively. We derive a single-letter characterization of all achievable quadruples {R/sub s/,R/sub r/,D/sub s/,D/sub r/}, and prove conditions for "successive refinability" without rate loss. Finally, we show that the special case D/sub s/=D/sub r/=0 is nontrivial and of practical interest in this context, as it can impose "acceptable" search and reconstruction qualities for each individual data item and for the entire query space with high probability, in contradistinction with standard average distortion requirements. The region of achievable {R/sub s/,R/sub r/} is obtained by adapting Rimoldi's characterization to a new regular scalable coding problem.

The standard scalable coding of stereophonic audio suffers from significant performance loss because of (1) poor prediction gain at the enhancement-layer and (2) direct requantization of the reconstruction error, which is suboptimal for the noise-mask ratio (NMR) criterion. To mitigate such performance loss, this paper proposes an integrated approach which employs two complementary techniques, namely, the estimation theoretic (ET) predictor and the conditional enhancement-layer quantizer (CELQ). The ET predictor has been shown to combine information from various sources for efficient enhancement-layer prediction, while CELQ efficiently handles scalable quantization to minimize NMR. We demonstrate that the proposed combined approach can achieve major performance gains in terms of bit rate reduction and reconstruction quality enhancement. For example, the proposed 2/spl times/16 kbit/s two layer coder achieves considerably improved reconstruction quality compared to that of the conventional 4/spl times/16 kbit/s four layer coder, despite expending only 50% of the standard scalable coder bit rate.

While the hidden Markov model (HMM) has been extensively applied to one-dimensional problems, the complexity of its extension to two-dimensions grows exponentially with the data size and is intractable in most cases of interest. We introduce an efficient algorithm for approximate decoding of 2D HMMs, i.e., searching for the most likely state sequence. The basic idea is to approximate a 2D HMM with a turbo-HMM (T-HMM), which consists of horizontal and vertical 1D HMMs that "communicate", and allow iterated decoding (ID) of rows and columns by a modified version of the forward-backward algorithm. We derive the approach and its re-estimation equations. We then compare its performance to another algorithm designed for decoding 2D HMMs: the path constrained variable state Viterbi (PCVSV) algorithm (Li, J. et al., IEEE Trans. on Sig. Processing, vol.48, no.2, 2000). Finally, we combine our approach with PCVSV and show that the combination outperforms each algorithm taken separately.

This paper introduces a novel deformable model for face mapping and its application to automatic person identification. While most face recognition techniques directly model the face, our goal is to model the transformation between face images of the same person. As a global face transformation may be too complex to be modeled in its entirety, it is approximated by a set of local transformations with the constraint that neighboring transformations must be consistent with each other. Local transformations and neighboring constraints are embedded within the probabilistic framework of a two-dimensional hidden Markov model (2-D HMM). Experimental results on a face identification task show that the new approach compares favorably to the popular Fisherfaces algorithm.

Accurate end-to-end distortion estimation is critical to efficient rate-distortion (R-D) optimization of encoder decisions for video transmission over lossy packet networks. This work focuses on extensions of the recursive optimal per-pixel estimate (ROPE), which has been shown to provide accurate end-to-end distortion estimation. Of particular interest are difficulties due to sub-pixel prediction and other pixel averaging operations, for which the existing ROPE encounters cross-correlation terms, whose exact estimation requires prohibitive storage and computational complexity. In this paper, we propose two model-based methods, which approximate the cross-correlation of two pixels as a function of their available first and second marginal moments. This allows an approximate extension of ROPE to handle sub-pixel prediction and other pixel averaging operations, at no additional storage cost, and no significant additional complexity. Simulations provide evidence for the performance gains of the proposed methods, and in particular, demonstrate that the resulting accuracy is very close to that of ROPE when it is optimal, i.e., in the case of full pixel prediction.

Motion compensated prediction in conventional video coders is based on the encoder reconstruction of the previous frame where motion is estimated so as to minimize the encoder prediction error. Such design paradigms optimize the prediction at the encoder and ignore the effects of packet loss. In this paper, we propose a new prediction framework, which uses the expected decoder reconstruction of past frames for prediction. Moreover, the motion estimation criterion is accordingly modified to minimize the expected decoder prediction error. The approach builds on the recursive optimal per-pixel estimate (ROPE), which ensures accurate estimation of the expected values of decoder quantities. The proposed prediction scheme achieves better error resilience performance than its conventional counterpart.

The design of vector quantizers for diversity-based communication over two or more channels of possibly differing capacities and failure probabilities, is considered. The crucial dependence of current design techniques on initialization, especially of index assignment, is well recognized. Instead, we propose to pursue a deterministic annealing approach which is independent of initialization, does not assume any prior knowledge of the source density, and avoids many poor local minima of the cost surface. The approach consists of iterative optimization of a random encoder at gradually decreasing levels of randomness as measured by the Shannon entropy. At the limit of zero entropy, a hard multiple description (MD) quantizer is obtained. This process is directly analogous to annealing processes in statistical physics. Via an alternative derivation, we show that it may also be interpreted as approximating the minimum rate sums among points on the convex hull of the MD achievable rate-distortion region of El Gamal and Cover, subject to constraints on the sizes of the reproduction alphabets. To illustrate the potential of our approach, we present simulation results that show substantial performance gains over existing design techniques.

Let (X,Y) be a pair of random variables distributed over a finite product set V/spl times/W according to a probability distribution P(x,y). The following source coding problem is considered: the encoder knows X, while the decoder knows Y and wants to learn X without error. The minimum zero-error asymptotic rate of transmission is shown to be the complementary graph entropy of an associated graph. Thus, previous results in the literature provide upper and lower bounds for this minimum rate (further, these bounds are tight for the important class of perfect graphs). The algorithmic aspects of instantaneous code design are considered next. It is shown that optimal code design is NP-hard. An optimal code design algorithm is derived. Polynomial-time suboptimal algorithms are also presented, and their average and worst case performance guarantees are established.

The problem of separate zero-error coding of correlated sources is considered. Inner and outer single-letter bounds are established for the achievable rate region, and conditions for their coincidence are investigated. It is shown that successive encoding combined with time sharing is not always an optimal coding strategy. Conditions for its optimality are derived. The inner bound to the achievable rate region follows as a special case of the single-letter characterization of a generalized zero-error multiterminal rate-distortion problem. The applications of this characterization to a problem of remote computing are also explored. Other results include (i) a product-space characterization of the achievable rates, (ii) bounds for finite block length, and (iii) asymptotic fixed-length rates.

The characterization of the set of achievable rate and distortion values for scalable source coding is extended to additionally account for error exponents, namely, the negative normalized asymptotic log likelihood of error events at different layers. The "error" at each layer is defined as the event that the source block is not reproduced within the prespecified fidelity at the corresponding decoder. We consider separate error events at each layer so as to allow a tradeoff analysis for the error exponents when the rate and distortion values are fixed. For two-step coding of discrete memoryless sources, we derive a single-letter characterization of the region of all achievable 6-tuples (R/sub 1/, R/sub 2/, E/sub 1/, E/sub 2/, D/sub 1/, D/sub 2/), i.e., the rate, error exponent, and distortion levels at each layer. We also analyze the special case of successive refinability, where (R/sub 1/, E/sub 1/, D/sub 1/) and (R/sub 2/, E/sub 2/, D/sub 2/) individually achieve the nonscalable bounds. A surprising outcome of the analysis is that for any D/sub 1/, D/sub 2/, and E/sub 1/, there exists a finite threshold E/spl circ//sub 2//spl ges/E/sub 1/ such that successive refinability is ensured for all E/sub 2//spl ges/E/spl circ//sub 2/.

Methods for determining and computing the rate-distortion (RD) bound for N-layer scalable source coding of a finite memoryless source are considered. Optimality conditions were previously derived for two layers in terms of the reproduction distributions q/sub y1/ and q/sub y2/|y/sub 1/. However, the ignored and seemingly insignificant boundary cases, where q/sub y1/=0 and q/sub y2/|y/sub 1/ is undefined, have major implications on the solution and its practical application. We demonstrate that, once the gap is filled and the result is extended to N-layers, it is, in general, impractical to validate a tentative solution, as one has to verify the conditions for all conceivable q/sub yi+1/,...,y/sub N/|y/sub 1/,...,y/sub i/ at each (y/sub 1/,...,y/sub i/) such that q/sub y1/,...,y/sub i/=0. As an alternative computational approach, we propose an iterative algorithm that converges to the optimal joint reproduction distribution q/sub y1/,...,y/sub N/, if initialized with q/sub y1/,...,y/sub N/>0 everywhere. For nonscalable coding (N=1), the algorithm specializes to the Blahut-Arimoto (1972) algorithm. The algorithm may be used to directly compute the RD bound, or as an optimality testing procedure by applying it to a perturbed tentative solution q. We address two additional difficulties due to the higher dimensionality of the RD surface in the scalable (N>1) case, namely, identifying the sufficient set of Lagrangian parameters to span the entire RD bound; and the problem of efficient navigation on the RD surface to compute a particular RD point.

Rate-distortion bounds for scalable coding, and conditions under which they coincide with nonscalable bounds, have been extensively studied. These bounds have been derived for the general tree-structured refinement scheme, where reproduction at each layer is an arbitrarily complex function of all encoding indexes up to that layer. However, in most practical applications (e.g., speech coding) "additive" refinement structures such as the multistage vector quantizer are preferred due to memory limitations. We derive an achievable region for the additive successive refinement problem, and show via a converse result that the rate-distortion bound of additive refinement is above that of tree-structured refinement. Necessary and sufficient conditions for the two bounds to coincide are derived. These results easily extend to abstract alphabet sources under the condition E{d(X,a)}

Let finite source and reproduction alphabets X and Y and a distortion measure d: X/spl times/Y/spl rarr/[0,/spl infin/) be given. We study the minimum asymptotic rate required to describe a source distributed over X within a (given) distortion threshold D at every sample. The problem is hence a min-max problem, and the distortion measure is extended to vectors as follows: for x/sup n//spl isin/X/sup n/, y/sup n//spl isin/Y/sup n/, d(x/sup n/, y/sup n/)=max/sub i/d(x/sub i/, y/sub i/). In the graph-theoretic formulation we introduce, a code for the problem is a dominating set of an equivalent distortion graph. We introduce a linear programming lower bound for the minimum dominating set size of an arbitrary graph, and show that this bound is also the minimum asymptotic rate required for the corresponding source. Turning then to the optimality of scalar coding, we show that scalar codes are asymptotically optimal if the underlying graph is either an interval graph or a tree.

We propose an efficient enhancement-layer quantizer which considerably improves the bit rate scalability of the multi-layer Advanced Audio Coder (AAC). The scheme exploits the statistical dependence of the enhancement-layer signal on the base-layer quantization parameters. It fundamentally extends the prior work on compander domain scalability, which was shown to be asymptotically optimal for entropy coded uniform scalar quantizer, to systems with non-uniform base-layer quantization. We show that an enhancement-layer quantization which is conditional on the base-layer information can be efficiently implemented within the AAC framework to achieve major performance gains. Moreover, in the important case that the source is well modeled as Laplacian, we show that the optimal conditional quantizer is implementable by only two distinct switchable quantizers depending on whether or not the base-layer quantizer employed the “zero dead-zone.” Hence, major savings in bit rate are recouped at virtually no additional computational cost. For example, the proposed four layer scalable coder consisting of 16kbps layers achieves performance close to a 60kbps non-scalable coder on the standard test database of 44.1kHz audio.

This paper is concerned with performance optimization of point-to-point communication of scalable video over lossy networks. A variant of the recursive optimal per-pixel estimate (ROPE) is developed and embedded within a rate-distortion (RD) optimized mode selection scheme for SNR scalable video coding. The system allows predicting the current base layer frame from past enhancement layer frame data. Drift management and adaptive bit rate allocation are both RD optimized within this framework. The ROPE method. ensures accurate estimation (at the encoder) of the over-all decoder distortion, which is critical to the substantial performance gains achieved. A low complexity layer sequential optimization scheme is proposed as well, which approximate!; the more complex joint optimization scheme, while maintaining most of the performance gains.

We propose an iterative optimization algorithm for the generic class of clustering-based indexing for approximate similarity searching. It was previously shown that clustering is a powerful component of approximate searching that reduces the number of retrieved data points. The objective of the proposed algorithm is to maximize the expected search quality given the query distribution. The problem is decomposed into minimization over three mapping functions, and fixed-point iterations of the algorithm alternately optimizing one mapping while fixing the other two. We demonstrate via experiments on real high dimensional data sets that the algorithm significantly improves the time/accuracy efficiency over heuristic clustering design.

This paper is concerned with adaptive and robust video streaming over lossy networks. A general system is described which is compatible with virtually all application settings. The delivery procedure is optimized within a rate-distortion framework with the aid of an efficient real-time end-to-end distortion estimation algorithm. The estimate fully accounts for the effects of (prior) quantization, packet loss and error propagation, as well as error concealment. It features high accuracy and low complexity, and requires a small amount of pre-computed side information. It is shown that various error-resilient schemes can be optimized within the proposed framework. In particular, unequal error protection through forward error control is employed in the simulations to demonstrate the achievable performance gains.

In this paper, we introduce a novel indexing technique based on efficient compression of the feature space for approximate similarity searching in large multimedia databases. Its main novelty is that state-of-the-art tools from the discipline of data compression are adopted to optimize the complexity-performance tradeoff in large data sets. The design procedure optimizes the query access time by jointly accounting for both database distribution and query statistics. We achieve efficient compression by using appropriate vector quantization (VQ) techniques, namely, multi-stage VQ and split-VQ, which are especially suited for limited memory applications. We partition the data set using the accumulated query history, and each partition of data points is separately compressed using a vector quantizer tailored to its distribution. The employed VQ techniques inherently provide a spectrum of points to choose from on the time/accuracy plane. This property is especially crucial for large multimedia databases where I/O time is a bottleneck, because it offers the flexibility to trade time for better accuracy. Our experiments demonstrate speedups of 20 to 35 over a VA-file technique that has been adapted for approximate nearest neighbor searching.

Two approaches are proposed for the design of tied-mixture hidden Markov models (TMHMM). One approach improves parameter sharing via partial tying of TMHMM states. To facilitate tying at the substate level, the state emission probabilities are constructed in two stages or, equivalently, are viewed as a mixture of mixtures of Gaussians. This paradigm allows, and is complemented with, an optimization technique to seek the best complexity-accuracy tradeoff solution, which jointly exploits Gaussian density sharing and substate tying. Another approach to enhance model training is combined training and reduction of model parameters. The procedure starts by training a system with a large universal codebook of Gaussian densities. It then iteratively reduces the size of both the codebook and the mixing coefficient matrix, followed by parameter re-training. The additional cost in design complexity is modest. Experimental results on the ISOLET database and its E-set subset show that substate tying reduces the classification error rate by over 15%, compared to standard Gaussian sharing and whole-state tying. TMHMM design with combined training and reduction of parameters reduces the classification error rate by over 20% compared to conventional TMHMM design. When the two proposed approaches were integrated, 25% error rate reduction over TMHMM with whole-state tying was achieved.

We derive an asymptotically optimal multi-layer coding scheme for entropy-coded scalar quantizers (SQ) that minimizes the weighted mean-squared error (WMSE). The optimal entropy-coded SQ is non-uniform in the case of WMSE. The conventional multi-layer coder quantizes the base-layer reconstruction error at the enhancement-layer, and is sub-optimal for the WMSE criterion. We consider the compander representation of the quantizer, and propose to implement scalability in the compressed domain. We show that such a multi-layer coding system achieves the operational rate-distortion bound given by the non-scalable entropy-coded SQ, at the limit of high resolution. Simulation results for a synthetic memoryless Laplace source with /spl mu/-law companding are presented for various values of layer rates. Substantial gains are also achieved on the "real-world" sources of audio signals, when the optimal multi-layer approach is applied to a two-layer scalable MPEG-4 Advanced Audio Coder.

The design of predictive quantizers generally suffers from difficulties due to the prediction loop, which have an impact on the convergence and the stability of the design procedure. We previously proposed an asymptotically closed-loop approach to quantizer design for predictive coding applications, which benefits from the stability of open-loop design while asymptotically optimizing the actual closed-loop system. In this paper, we present an enhancement to the approach where joint optimization of both predictor and quantizer is performed within the asymptotically closed-loop framework. The proposed design method is tested on synthetic sources (first-order Gauss and Laplacian-Markov sequences), and on natural sources, in particular, line spectral frequency parameters of speech signals.

We address the issue of optimizing side information rate for efficient audio coding. In coders such as the MPEG-4 AAC, at rates around 16 kbps to 48 kbps, the side information rate forms a substantial part of the total rate. The parameter search procedure in the verification model optimizes each band separately and results in poor performance at low rates. We propose to jointly optimize the encoding parameter of all the bands. The near-optimal solution using a brute force search has drastic computational complexity. However, the same solution is obtained at a much reduced complexity using a Viterbi search through a trellis. The search procedure is developed and evaluated for two objective measures, the average and the maximum noise-mask ratio. For both the measures, the trellis-based search yields substantially better solutions. In particular, trellis-based optimization of maximum noise-mask ratio greatly improves the performance of AAC at low rates. The resulting bit stream is standard-compatible, and the additional complexity due to the proposed optimization is only incurred at the encoder.

Perceptual harmonic cepstral coefficients (PHCC) are proposed as features to extract from speech for recognition in noisy environments. A weighting function, which depends on the prominence of the harmonic structure, is applied to the power spectrum to ensure accurate representation of the voiced speech spectral envelope. The harmonics' weighted power spectrum undergoes mel-scaled band-pass filtering, and the log-energy of the filters' output is discrete cosine transformed to produce cepstral coefficients. Lower spectral clipping is applied to the power spectrum, followed by within-filter root-power amplitude compression to reduce amplitude variation without compromise of the gain invariance properties. Experiments show significant recognition gains of PHCC over MFCC, with 23% and 36% error rate reduction for the Mandarin digit database in white and babble noise environments.

In standard predictive video coders, intra-mode coding of macroblocks (MBs) provides packet loss resilience, at the cost of reduced compression efficiency. Conventional mode selection algorithms are "greedy" as they focus on minimization of distortion of current MB, while ignoring the effect of this selection on subsequent frames. This paper proposes an algorithm for prescient mode selection: the coding modes of MBs are chosen while taking into account the distortion of subsequent frames. The problem is formulated as one of joint selection of MB coding modes, for a group of pictures, so as to minimize the rate-distortion cost. The straightforward solution based on dynamic programming requires enormous computational complexity. We propose an iterative algorithm which obtains a locally optimal solution at feasible complexity. The total decoder distortion is computed using recursive optimal per-pixel estimate (ROPE) which accurately accounts for the effects of quantization, packet loss, error propagation, and error concealment. Simulation results show consistent improvement over our previous "greedy" ROPE-RD mode selection, and substantial gains over other (non-ROPE) mode selection schemes.

This paper presents a significant modification of our previously proposed speech recognizer's front-end based on perceptual harmonic cepstral coefficients. The spectrum is split into two frequency bands, which correspond to the harmonic and non-harmonic components. A weighting function, which depends both on the voiced/unvoiced/ transitional classification and on the prominence of harmonic structures, is applied to the harmonic band, and ensures accurate representation of the voiced and transitional speech spectral envelope. Conventional smoothed spectrum is used in the non-harmonic band. The mixed spectrum undergoes melscaled band-pass filtering, and the log-energy of the filters' output is discrete cosine transformed to produce cepstral coefficients. Experiments with Mandarin digit and E-set databases show significant recognition gains over plain perceptual harmonic cepstral coefficients and considerable gains over standard techniques.

Many conventional speech recognition systems are based on the use of hidden Markov models (HMM) within the context of discriminant-based pattern classification. While the speech recognition objective is a low rate of misclassification, HMM design has been traditionally approached via maximum likelihood (ML) modeling which is, in general, mismatched with the minimum error objective and hence suboptimal. Direct minimization of the error rate is difficult because of the complex nature of the cost surface, and has only been addressed previously by discriminative design methods such as generalized probabilistic descent (GPD). While existing discriminative methods offer significant benefits, they commonly rely on local optimization via gradient descent whose performance suffers from the prevalence of shallow local minima. As an alternative, we propose the deterministic annealing (DA) design method that directly minimizes the error rate while avoiding many poor local minima of the cost. The DA is derived from fundamental principles of statistical physics and information theory. In DA, the HMM classifier's decision is randomized and its expected error rate is minimized subject to a constraint on the level of randomness which is measured by the Shannon entropy. The entropy constraint is gradually relaxed, leading in the limit of zero entropy to the design of regular nonrandom HMM classifiers. An efficient forward-backward algorithm is proposed for the DA method. Experiments on synthetic data and on a simplified recognizer for isolated English letters demonstrate that the DA design method can improve recognition error rates over both ML and GPD methods.

We present a source-channel coding system for operation over code-division multiple-access channels with time-varying conditions. The proposed system consists of a multistage vector quantizer (MSVQ) in conjunction with unequal protection against channel errors. The receiver estimates the channel conditions and decodes as many stages of the quantizer as can be reliably decoded. The approach to system design and optimization is first derived and evaluated for a system that employs hard decoding of stage indices. The approach is then extended to the more general case of weighted decoding. Simulation results are given for transmission of Gauss-Markov sources over broadcast and slow fading channels. Consistent and substantial improvement is achieved over the standard MSVQ with equal error protection, and the gains, in terms of source signal-to-noise ratio, are in the range of 3-5 dB.

This correspondence builds on the asymptotic closed-loop approach to predictive vector quantizer design (Khalil et al. 2001), and extends it to the design of predictive multistage vector quantizers for low bit rate video coding. The design approach resolves longstanding shortcomings, in particular, design stability and empty-cell problems. Simulation results show substantial gains over traditional design approaches.

The basic vector quantization (VQ) technique employed in video coding belongs to the category of predictive vector quantization (PVQ), as it involves quantization of the (motion compensated) frame prediction error. It is well known that the design of PVQ suffers from fundamental difficulties, due to the prediction loop, which have an impact on the convergence and the stability of the design procedure. We propose an approach to PVQ design that enjoys the stability of open-loop design while it ensures ultimate optimization of the closed-loop system. The method is derived for general predictive quantization, and we demonstrate it on video compression at low bit rates, where it provides substantial improvement over standard open and closed loop design techniques. Further, the approach outperforms standard DCT-based video coding.

A method is proposed for efficient scalability in predictive coding, which overcomes known fundamental shortcomings of the prediction loop at enhancement layers. The compression efficiency of an enhancement-layer is substantially improved by casting the design of its prediction module within an estimation-theoretic framework, and thereby exploiting all information available at that layer for the prediction of the signal, and encoding of the prediction error. While the most immediately important application is in video compression, the method is derived in a general setting and is applicable to any scalable predictive coder. Thus, the estimation-theoretic approach is first developed for basic DPCM compression and demonstrates the power of the technique in a simple setting that only involves straightforward prediction, scalar quantization, and entropy coding. Results for the scalable compression of first-order Gauss-Markov and Laplace-Markov signals illustrate the performance. A specific estimation algorithm is then developed for standard scalable DCT-based video coding. Simulation results show consistent and substantial performance gains due to optimal estimation at the enhancement-layers.

Consider approximate (lossy) matching of a source string /spl sim/P, with a random codebook generated from reproduction distribution Q, at a specified distortion d. Previous work determined the minimum coding rate R/sub 1/=R(P, Q, d) for this setting. We observe that for a large word length and with high probability, the matching codeword is typical with a distribution Q/sub 1/ which is different from Q. If a new random codebook is generated /spl sim/Q/sub 1/, then the source string will favor codewords which are typical with a new distribution Q/sub 2/, resulting in a minimum coding rate R/sub 2/=R(P, Q/sub 1/, d), and so on. We show that the sequences of distributions Q/sub 1/, Q/sub 2/,... and rates R/sub 1/, R/sub 2/,..., generated by this procedure, converge to an optimum reproduction distribution Q*, and the rate-distortion function R(P, d), respectively. We also derive a fixed rate-distortion slope version of this natural type selection process. In the latter case, an iteration of the process stochastically simulates an iteration of the Blahut-Arimoto (1972) algorithm for rate-distortion function computation (without recourse to prior knowledge of the underlying source distribution). To strengthen these limit statements, we also characterize the steady-state error of these procedures when iterating at a finite string length. Implications of the main results provide fresh insights into the workings of lossy variants of the Lempel-Ziv algorithm for adaptive compression.

Robustness to packet loss is a critical requirement for video communication over packet switched networks. Intra-coding is an important tool to mitigate the effects of packet loss by limiting error propagation. This work proposes an algorithm for intra/inter coding mode selection, while utilizing the feedback channel that carries acknowledgement information about received packets. The overall distortion in frame reconstruction at the decoder due to quantization, error concealment (after packet loss) and error propagation is estimated at pixel-level precision, and is dynamically refined based on the feedback information. The estimate is then integrated into a rate-distortion (RD) framework for optimal selection of coding mode for each macroblock. Simulation results demonstrate that precise distortion estimation enables the coder to achieve substantial and consistent gain in PSNR over known state-of-the-art feedback-based mode selection modes.

An approach is proposed for partial tying of states of tied-mixture hidden Markov models. To facilitate tying at the sub-state level, the state emission probabilities are constructed in two stages, or equivalently, are viewed as a "mixture of mixtures of Gaussians." This paradigm allows, and is complemented with, an optimization technique to seek the best complexity-accuracy tradeoff solution, which jointly exploits Gaussian density sharing and sub-state tying. Experimental results on the E-set show that the classification error rate is reduced by over 20% compared to standard Gaussian sharing and whole-state tying. The approach is then embedded within the recently developed procedure of combined parameter training and reduction technique. Experiments with the overall technique show that the error rate is further reduced by 8%.

The design of a multi-stage vector quantizer (MSVQ) based source-channel coding system is optimized for packet networks. Resilience to packet loss is further enhanced by a proposed interleaving approach that ensures that a single lost packet only eliminates a subset of the vector stages. The design is optimized while taking into account compression efficiency, packet loss rate, and the interleaving technique in use. The new source-channel-optimized MSVQ is tested on memoryless line spectral frequency (LSF) parameter quantization in speech coders. A source-channel-optimization MSVQ is shown to yield a gain of up to 2.0 dB in SNR, for coding the LSFs, over traditional MSVQ and to substantially enhance the robustness of packetized speech transmission. Although the formulation is given in the context of packet networks, the work is directly extendible to the broader category of erasure channels.

The design of a source-channel system based on the multi-stage vector quantizer (MSVQ) is optimized for packet networks. Resilience to packet loss is further enhanced by a proposed interleaving scheme that ensures that a single lost packet only eliminates a subset of the vector stages. The design is optimized while taking into account compression efficiency, packet loss rate, and the interleaving technique in use. Simulation results demonstrate that the packet network-optimized MSVQ outperforms traditional MSVQ for a variety of images and channel conditions, with gains of up to 2.0 dB in PSNR. Although the formulation is given in the context of packet networks, the work is directly extendible to the broader category of erasure channels.

This work considers the design of a multi-stage vector quantizer (MSVQ) for application to the motion compensated prediction error of video signals. It is well known that the design of predictive vector quantizers suffers from fundamental difficulties due to the prediction loop, which have an impact on the convergence and the stability of the design procedure. We propose an approach to predictive MSVQ design that enjoys the stability of open-loop design while ensuring ultimate optimization of the closed-loop system. The proposed design method is tested on video compression at low bit rates, where it significantly outperforms widely-used closed-loop design techniques, and achieves improvement over the H.263 standard.

This work is concerned with the design of multiple description (MD) compression systems with emphasis on video coding. Although inter-frame prediction is critical to the performance of video coders, the problem of efficient prediction in MD systems has not been satisfactorily resolved. We focus on quantizer based MD coding and propose an estimation theoretic (ET) approach to prediction and reconstruction. The advantage of ET prediction is two fold: (1) It takes into account all the information available at each decoder for an optimal estimate; (2) It mitigates the degradation due to quantization in the prediction feedback loop. The ET approach is first shown to achieve significant gains in the simpler setting of predictive MD coding of synthetic Gauss-Markov and Laplace-Markov processes. We then present performance results for MD compression of video sequences and demonstrate consistent and substantial PSNR gains over conventional techniques.

This work introduces two complementary techniques to improve the packet loss resilience of scalable video coding systems. First, a "switch per-pixel" error concealment (SPEC) scheme is proposed, which allows the decoder to exploit information from both the current base layer and previous enhancement-layer frame for the reconstruction of missing enhancement-layer blocks. Based on the packet loss history and the quantized base-layer data, the algorithm switches per pixel between the two information sources. SPEC is shown to consistently outperform standard concealment methods. The second main contribution is concerned with encoder decision optimization. Enhancement layer prediction modes are selected so as to minimize the overall decoder reconstruction distortion, which is due to quantization, packet loss and error propagation. The distortion computation uses a recursive optimal per-pixel estimate (ROPE) to accurately account for the effects of error concealment as well as spatial and temporal error propagation. Simulation results show that ROPE-based mode selection substantially outperforms conventional prediction mode selection schemes. Finally, the combination of SPEC at the decoder and ROPE-based mode selection at the encoder is shown to achieve significant additional performance gains.

A deterministic annealing algorithm for the design of tiedmixture HMM recognizers is proposed, which reduces the training sensitivity to parameter initialization, automatically smoothes the classification error cost function to allow gradientbased optimization, and seeks better solutions than known techniques. The new approach introduces randomness into the classification rule during the training process, and minimizes the expected error rate while controlling the level of randomness via a constraint on the Shannon entropy. As the entropy constraint is gradually relaxed, the effective cost function converges to the classification error rate and the system becomes a hard (nonrandom) recognizer. Experiments show that the proposed method outperforms design by maximum likelihood reestimation and by generalized probabilistic descent.

Perceptual harmonic cepstral coefficients (PHCC) are proposed as features to extract for speech recognition. Pitch estimation and classification into voiced, unvoiced, and transitional speech are performed by a spectro-temporal auto-correlation technique. A peak picking algorithm is then employed to precisely locate pitch harmonics. A weighting function, which depends on the classification and the pitch harmonics, is applied to the power spectrum and ensures accurate representation of the voiced speech spectral envelope. The harmonics weighted power spectrum undergoes mel-scaled band-pass filtering, and the logenergy of the filters' output is discrete cosine transformed to produce cepstral coefficients. For perceptual considerations, within-filter cubic-root amplitude compression is applied to reduce amplitude variation without compromise of the gain invariance properties. Experiments show substantial recognition gains of PHCC over MFCC, with 48% and 15% error rate reduction for the Mandarin digit database and E-set, respectively.

Resilience to packet loss is a critical requirement in predictive video coding for transmission over packet-switched networks, since the prediction loop propagates errors and causes substantial degradation in video quality. This work proposes an algorithm to optimally estimate the overall distortion of decoder frame reconstruction due to quantization, error propagation, and error concealment. The method recursively computes the total decoder distortion at pixel level precision to accurately account for spatial and temporal error propagation. The accuracy of the estimate is demonstrated via simulation results. The estimate is integrated into a rate-distortion (RD)-based framework for optimal switching between intra-coding and inter-coding modes per macroblock. The cost in computational complexity is modest. The framework is further extended to optimally exploit feedback/acknowledgment information from the receiver/network. Simulation results both with and without a feedback channel demonstrate that precise distortion estimation enables the coder to achieve substantial and consistent gains in PSNR over known state-of-the-art RD- and non-RD-based mode switching methods.

This paper applies ideas from fractal compression and optimization theory to attack the problem of efficient content-based image indexing and retrieval. Similarity of images is measured by block matching after optimal (geometric, photometric, etc.) transformation. Such block matching which, by definition, consists of localized optimization, is further governed by a global dynamic programming technique (Viterbi algorithm) that ensures continuity and coherence of the localized block matching results. Thus, the overall optimal transformation relating two images is determined by a combination of local block-transformation operations subject to a regularization constraint. Experimental results on a sample of seventy five binary images from the MPEG-7 database demonstrate the power and potential of the proposed approach.

This paper proposes an algorithm for content-based image indexing whose formulation of similarity is borrowed from methods for fractal compression. Unlike most traditional block-based image indexing algorithms, the proposed method employs dynamic programming to exploit inter-block dependencies. A regularization constraint is globally imposed, and the overall optimal transformation relating two images is efficiently determined by application of the Viterbi algorithm. Preliminary experimental results on a sample of eighty binary images from the MPEG-7 database are presented.

A new learning algorithm is proposed for piecewise regression modeling. It employs the technique of deterministic annealing to design space partition regression functions. While the performance of traditional space partition regression functions such as CART and MARS is limited by a simple tree-structured partition and by a hierarchical approach for design, the deterministic annealing algorithm enables the joint optimization of a more powerful piecewise structure based on a Voronoi partition. The new method is demonstrated to achieve consistent performance improvements over regular CART as well as over its extension to allow arbitrary hyperplane boundaries. Comparison tests, on several benchmark data sets from the regression literature, are provided.

This work is concerned with the problem of designing robust, vector quantizer (VQ)-based communication systems for operation over time-varying Gaussian channels. Transmission energy allocation to VQ codeword bits, according to their error sensitivities, is a powerful tool for improving robustness to channel noise. The power of this technique can be further enhanced by appropriately combining it with index assignment methods. We pose the corresponding joint optimization problem and suggest a simple iterative algorithm for finding a locally optimal solution. The susceptibility of the solution to poor local minima is significantly reduced by an enhanced version of the algorithm which invokes the method of noisy channel relaxation whereby the VQ system is optimized while gradually decreasing the assumed level of channel noise. In a series of experiments, the resulting combined technique is shown to outperform standard pseudo-Gray coding by up to 3.5 dB and to exhibit graceful degradation at mismatched channel conditions. Finally, we extend these ideas to the case where both the transmitter and the receiver have information on the current state of a time-varying channel. The proposed method is based on switched encoding and adaptive decoding. Experimental results show that the proposed system achieves close to optimal performance.

This paper is concerned with the design problem of coded modulation schemes which provide unequal error protection (UEP) against Gaussian noise. Starting with the case of two bit streams, we consider two classes of UEP schemes: time-division coded modulation (TDCM) and superposition coded modulation (SCM). The early result of Bergmanns and Cover (1974) ensures the asymptotic superiority of SCM. However, accounting for the fact that practical channel codes do not achieve capacity, we show that the validity of this result depends on the prescribed degree of inequality in protection of the streams. To complement the straightforward design and use of TDCM schemes, we propose methods to decode and design SCM schemes. The design examples substantiate the conclusions obtained from performance analysis. We extend the results to the case of UEP of multiple (more than two) bit streams, where a hybrid of SCM and TDCM must also be considered. We show that, for a large range of unequal protection levels, the hybrid scheme outperforms both SCM and TDCM.

This article proposes a method to design a vector quantizer (VQ) for robust performance under noisy channel conditions. By re-optimizing the quantizer at progressively lower levels of assumed channel noise, the design is less susceptible to poor local optima. The method is applied to: (1) channel-optimized VQ design; and (2) index assignment for a source-optimized VQ. For both problems, we demonstrate substantial performance improvements over commonly used techniques.

We attack the general problem of HMM-based speech recognizer design, and in particular, the problem of isolated letter recognition in the presence of background noise. The standard design method based on maximum likelihood (ML) is known to perform poorly when applied to isolated letter recognition. The minimum classification error (MCE) approach directly targets the ultimate design criterion and offers substantial improvements over the ML method. However, the standard MCE method relies on gradient descent optimization which is susceptible to shallow local minima traps. We propose to overcome this difficulty with a powerful optimization method based on deterministic annealing (DA). The DA method minimizes a randomized MCE cost subject to a constraint on the level of entropy which is gradually relaxed. It may be derived based on information-theoretic or statistical physics principles. DA has a low implementation complexity and outperforms both standard ML and the gradient descent based MCE algorithm by a factor of 1.5 to 2.0 on the benchmark CSLU spoken letter database. Further, the gains are maintained under a variety of background noise conditions.

A new method is proposed for efficient SNR scalability in predictive video coding. It is of low complexity, and it is applicable to standard DCT-based video compression with motion compensation. Information that is only available to the enhancement layers is exploited to improve the quality of their frame prediction without compromising the usefulness of the compressed data provided by the base layer(s). More specifically, the next frame prediction for use by an enhancement-layer decoder is obtained by combining, or switching between transform coefficients from: i) the reconstructed base-layer frame; and ii) the predicted enhancement-layer frame. The combining rule depends on the compressed residual of the base layer, and on the parameters used for this compression. The method is applied to standard DCT-based predictive video coding, and preliminary simulation shows consistent, substantial improvement in the performance of enhancement layers. The proposed method may be easily combined with known temporal scalability methods to provide further improvement of the performance of enhancement layers over a wide range of bit rates.

We present a source-channel coding system consisting of a multi-stage vector quantizer in conjunction with unequal protection against channel errors. The receiver estimates the channel conditions and decodes as many stages of the quantized signal as can be reliably decoded. The proposed overall system is optimized for robustness to time-varying noisy channels. Two versions of the system are designed and evaluated, which involve: (i) hard, and (ii) weighted decoding of the stage indices. Simulation results are given for Gauss-Markov sources transmitted over broadcast and fading channels. Consistent and substantial improvement is achieved over the standard multi-stage vector quantizer with equal error protection, and the gains are in the range of 3 to 5 dB.

The deterministic annealing approach to clustering and its extensions has demonstrated substantial performance improvement over standard supervised and unsupervised learning methods in a variety of important applications including compression, estimation, pattern recognition and classification, and statistical regression. The application-specific cost is minimized subject to a constraint on the randomness of the solution, which is gradually lowered. We emphasize the intuition gained from analogy to statistical physics. Alternatively the method is derived within rate-distortion theory, where the annealing process is equivalent to computation of Shannon's rate-distortion function, and the annealing temperature is inversely proportional to the slope of the curve. The basic algorithm is extended by incorporating structural constraints to allow optimization of numerous popular structures including vector quantizers, decision trees, multilayer perceptrons, radial basis functions, and mixtures of experts.

Many image compression techniques require the quantization of multiple vector sources with significantly different distributions. With vector quantization (VQ), these sources are optimally quantized using separate codebooks, which may collectively require an enormous memory space. Since storage is limited in most applications, a convenient way to gracefully trade between performance and storage is needed. Earlier work addressed this problem by clustering the multiple sources into a small number of source groups, where each group shares a codebook. We propose a new solution based on a size-limited universal codebook that can be viewed as the union of overlapping source codebooks. This framework allows each source codebook to consist of any desired subset of the universal code vectors and provides greater design flexibility which improves the storage-constrained performance. A key feature of this approach is that no two sources need be encoded at the same rate. An additional advantage of the proposed method is its close relation to universal, adaptive, finite-state and classified quantization. Necessary conditions for optimality of the universal codebook and the extracted source codebooks are derived. An iterative design algorithm is introduced to obtain a solution satisfying these conditions. Possible applications of the proposed technique are enumerated, and its effectiveness is illustrated for coding of images using finite-state vector quantization, multistage vector quantization, and tree-structured vector quantization.

We attack the problem of robust and efficient image compression for transmission over noisy channels. To achieve the dual goals of high compression efficiency and low sensitivity to channel noise we introduce a multimode coding framework. Multimode coders are quasi-fixed length in nature, and allow optimization of the tradeoff between the compression capability of variable-length coding and the robustness to channel errors of fixed length coding. We apply our framework to develop multimode image coding (MIC) schemes for noisy channels, based on the adaptive DCT. The robustness of the proposed MIC is further enhanced by the incorporation of a channel protection scheme suitable for the constraints on complexity and delay. To demonstrate the power of the technique we develop two specific image coding algorithms optimized for the binary symmetric channel. The first, MIC1, incorporates channel optimized quantizers and the second, MIC2, uses rate compatible punctured convolutional codes within the multimode framework. Simulations demonstrate that the multimode coders obtain significant performance gains of up to 6 dB over conventional fixed length coding techniques.

A new and effective design method is presented for statistical regression functions that belong to the class of mixture models. The class includes the hierarchical mixture of experts (HME) and the normalized radial basis functions (NRBF). Design algorithms based on the maximum likelihood (ML) approach, which emphasize a probabilistic description of the model, have attracted much interest in HME and NRBF models. However, their design objective is mismatched to the original squared-error regression cost and the algorithms are easily trapped by poor local minima on the cost surface. In this paper, we propose an extension of the deterministic annealing (DA) method for the design of mixture-based regression models. We construct a probabilistic framework, but unlike the ML method, we directly optimize the squared-error regression cost, while avoiding poor local minima. Experimental results show that the DA method outperforms standard design methods for both HME and NRBF regression models.

In this work we address the problem of designing robust, vector quantizer (VQ) based communication systems for operation over time-varying Gaussian channels. Transmission energy allocation (TEA) to VQ codeword bits, according to their error sensitivities, is a powerful tool for improving robustness to channel noise. The power of this technique can be further enhanced by appropriately combining it with index assignment methods. We pose the corresponding joint optimization problem and suggest a simple iterative algorithm for finding a locally optimal solution. The susceptibility of the solution to poor local minima is significantly reduced by an enhanced version of the algorithm which invokes the the method of noisy channel relaxation, whereby, the VQ system is optimized while gradually decreasing the assumed level of channel noise. The resulting combined technique is shown to outperform standard pseudo-Gray coding by up to 3.5 dB, and to exhibit graceful degradation at mismatched channel conditions. We conclude with a brief discussion of the impact of TEA on the peak-to-average energy ratio of the transmitted modulated signals.

We attack the problem of designing robust image compression schemes for transmission over noisy channels. To achieve the dual goals of high compression efficiency and low sensitivity to channel noise, we introduce a multimode coding framework. Multimode coders are quasi-fixed length in nature, and this enables optimal tradeoff between the compression capability of variable-length coding and the robustness of fixed length coding. The framework lends itself to a natural incorporation of conventional source-channel coding mechanisms, and thus provides a joint design methodology for the source and channel coding components. We first derive a general Lagrangian based algorithm to design the multimode coder which optimizes the overall rate-distortion performance. We then apply our framework to develop multimode image coding (MIC) schemes for noisy channels. We demonstrate the benefits of the multimode approach by developing two specific image compression algorithms in conjunction with the following source-channel coding mechanisms: (i) channel optimized quantizers, and (ii) transmission energy allocation. Simulations demonstrate that substantial gains of up to 7 dB can be achieved by MICs over conventional approaches.

Motion compensation is formulated as quantization of the true motion field and optimized within an overall rate-distortion framework. The desired accuracy in motion estimation is achieved by designing the codebook of the motion quantizer for the target rate. We propose an iterative algorithm for the codebook design which optimizes the compression performance of the coder by directly minimizing the overall rate-distortion cost. A multistage structure is imposed on the codebook to obtain a practical motion quantization scheme, which is optimized through a joint design of the stages. Simulation results on video sequences are presented which demonstrate that RD optimized motion vector quantization outperforms conventional motion compensation and can achieve significant gains of 1.3 dB in the PSNR of the reconstructed picture. Further, the multiresolution nature of multistage motion quantization makes it applicable for scalable video coding applications.

We focus on the design of robust video compression schemes for transmission over noisy channels. A multimode video coding framework is introduced, which enables optimizing the tradeoff between the conflicting objectives of high compression efficiency and error resilience. The starting point is a simple block-based predictive coder, with no motion compensation, for which we develop the robust multimode video compression scheme. The proposed iterative design algorithm for multimode video coders directly minimizes the overall rate-distortion cost. We show that several conventional joint source-channel coding mechanisms can be incorporated within a multimode scheme to further enhance the video coder performance. Simulation results of compressing benchmark video sequences for transmission over noisy channel conditions are presented. They demonstrate that multimode coders outperform conventional fixed length approaches and can achieve substantial gains of more than 6 dB in PSNR of the reconstructed picture.

We study the structure and design of a vector quantizer (VQ) for robust performance under noisy channel conditions. We develop some new insights about the geometrical structure of such a VQ, and introduce noisy channel relaxation-a novel design approach. In particular, the approach is used to attack two basic problems: (1) optimize the VQ for a given noisy channel; and (2) optimize index assignment while maintaining optimality for the noiseless channel. For problem (1) we show consistent improvements over descent methods at the cost of manageable increase in complexity (by a factor of up to three). For problem (2) we obtain index assignment with a quality significantly better than known methods, but at computational complexity that grows many times slower.

In vector quantization, one approximates an input random vector, Y, by choosing from a finite set of values known as the codebook. We consider a more general problem where one may not have direct access to Y but only to some statistically related random vector X. We observe X and would like to generate an approximation to Y from a codebook of candidate vectors. This operation, called generalized vector quantization (GVQ), is essentially that of quantized estimation. An important special case of GVQ is the problem of noisy source coding wherein a quantized approximation of a vector, Y, is obtained from observation of its noise-corrupted version, X. The optimal GVQ encoder has high complexity. We overcome the complexity barrier by optimizing a structurally-constrained encoder. This challenging optimization task is solved via a probabilistic approach, based on deterministic annealing, which overcomes problems of shallow local minima that trap simpler descent methods. We demonstrate the successful application of our method to the coding of noisy sources.

We address unsupervised learning subject to structural constraints, with particular emphasis placed on clustering with an imposed decision tree structure. Most known methods are greedy, optimizing one node of the tree at a time to minimize a local cost. By constrast, we develop a joint optimization method, derived based on information-theoretic principles and closely related to known methods in statistical physics. The approach is inspired by the deterministic annealing algorithm for unstructured data clustering, which was based on maximum entropy inference. The new approach is founded on the principle of minimum cross-entropy, using informative priors to approximate the unstructured clustering solution while imposing the structural constraint. The resulting method incorporates supervised learning principles applied in an unsupervised problem setting. In our approach, the tree “grows” by a sequence of bifurcations that occur while optimizing an effective free energy cost at decreasing temperature scales. Thus, estimates of the tree size and structure are naturally obtained at each temperature in the process. Examples demonstrate considerable improvement over known methods.

Current methods for the design of pruned or unbalanced tree-structured vector quantizers such as the generalized Breiman-Friedman-Olshen-Stone (GBFOS) algorithm proposed in 1980 are effective, but suffer from several shortcomings. We identify and clarify issues of suboptimality including greedy growing, the suboptimal encoding rule, and the need for time sharing between quantizers to achieve arbitrary rates. We then present the leaf-optimal tree design (LOTD) method which, with a modest increase in design complexity, alters and reoptimizes tree structures obtained from conventional procedures. There are two main advantages over existing methods. First, the optimal entropy-constrained nearest-neighbor rule is used for encoding at the leaves; second, explicit quantizer solutions are obtained at all rates without recourse to time sharing. We show that performance improvement is theoretically guaranteed. Simulation results for image coding demonstrate that close to 1 dB reduction of distortion for a given rate can be achieved by this technique relative to the GBFOS method.

Many compression applications consist of compressing multiple sources with significantly different distributions. In the context of vector quantization (VQ) these sources are typically quantized using separate codebooks. Since memory is limited in most applications, a convenient way to gracefully trade between performance and storage is needed. Earlier work addressed this problem by clustering the multiple sources into a small number of source groups, where each group shares a codebook. As a natural generalization, we propose the design of a size-limited universal codebook consisting of the union of overlapping source codebooks. This framework allows each source codebook to consist of any desired subset of the universal codevectors and provides greater design flexibility which improves the storage-constrained performance. Further advantages of the proposed approach include the fact that no two sources need be encoded at the same rate, and the close relation to universal, adaptive, and classified quantization. Necessary conditions for optimality of the universal codebook and the extracted source codebooks are derived. An iterative descent algorithm is introduced to impose these conditions on the resulting quantizer. Possible applications of the proposed technique are enumerated and its effectiveness is illustrated for coding of images using finite-state vector quantization.

The authors address the variable rate tree-structured vector quantizer design problem, wherein the rate is measured by the quantizer's entropy. For this problem, tree pruning via the generalized Breiman-Friedman-Olshen-Stone (1980) algorithm obtains solutions which are optimal over the restricted solution space consisting of all pruned trees derivable from an initial tree. However, the restrictions imposed on such solutions have several implications. In addition to depending on the tree initialization, growing and pruning solutions result in tree-structured vector quantizers which use a sub-optimal encoding rule. To remedy the latter problem, they consider a "tree-constrained" version of entropy-constrained vector quantizer design. This leads to an optimal tree-structured encoding rule for the leaves. In practice, though, improvements obtained in this fashion are limited by the tree initialization, as well as by the sub-optimal encoding performed at non-leaf nodes. To address these problems, they develop a joint optimization method which is inspired by the deterministic annealing algorithm for data clustering, and which extends their previous work on tree-structured vector quantization. The method is based on the principle of minimum cross entropy, using informative priors to approximate the unstructured solution while imposing the structural constraint. As in the original deterministic annealing method, the number of distinct codevectors (and hence the tree) grows by a sequence of bifurcations in the process, which occur as solutions of a free energy minimization. Their method obtains performance gains over growing and pruning methods for variable rate quantization of Gauss-Markov and Gaussian mixture sources.>

The deterministic annealing algorithm for data clustering is extended to address the trellis quantizer design problem. The approach is derived within information theory and probability theory, using the principle of maximum entropy to induce a distribution over all possible path encodings of the training set. The resulting method is intimately connected to estimation procedures on Markov chains. Performance gains over known methods are obtained for memoryless, multimodal scalar sources as well as for the vector Gaussian and Laplacian sources. The method is also suggested for an estimation problem in hidden Markov models. For a Gaussian mixture state example, this approach achieves a greater likelihood value than the best result of standard Baum-Welch re-estimation, based on numerous initializations within the data.>

The authors present a new approach to combined source-channel vector quantization. The method, derived within information theory and probability theory, utilizes deterministic annealing to avoid some local minima that trap conventional descent algorithms such as the generalized Lloyd algorithm. The resulting vector quantizers satisfy the necessary conditions for local optimality for the noisy channel case. They tested the method against several versions of the noisy channel generalized Lloyd algorithm on stationary, first order Gauss-Markov sources with a binary symmetric channel. The method outperformed other methods under all test conditions, with the gains over noisy channel GLA growing with the codebook size. The quantizers designed using deterministic annealing are also shown to behave robustly under channel mismatch conditions. As a comparison with a separate source-channel system, over a large range of test channel conditions, the method outperformed a bandwidth-equivalent system incorporating a Hamming code. Also, for severe channel conditions, the method produces solutions with explicit error control coding.>

In rate-distortion theory, results are often derived and stated in terms of the optimizing density over the reproduction space. In this paper, the problem is reformulated in terms of the optimal mapping from the unit interval with Lebesgue measure that would induce the desired reproduction probability density. This results in optimality conditions that are "random relatives" of the known Lloyd (1982) optimality conditions for deterministic quantizers. The validity of the mapping approach is assured by fundamental isomorphism theorems for measure spaces. We show that for the squared error distortion, the optimal reproduction random variable is purely discrete at supercritical distortion (where the Shannon (1948) lower bound is not tight). The Gaussian source is thus the only source that produces continuous reproduction variables for the entire range of positive rate. To analyze the evolution of the optimal reproduction distribution, we use the mapping formulation and establish an analogy to statistical mechanics. The solutions are given by the distribution at isothermal statistical equilibrium, and are parameterized by the temperature in direct correspondence to the parametric solution of the variational equations in rate-distortion theory. The analysis of an annealing process shows how the number of "symbols" grows as the system undergoes phase transitions. Thus, an algorithm based on the mapping approach often needs but a few variables to find the exact solution, while the Blahut (1972) algorithm would only approach it at the limit of infinite resolution. Finally, a quick "deterministic annealing" algorithm to generate the rate-distortion curve is suggested. The resulting curve is exact as long as continuous phase transitions in the process are accurately followed.>

A new structure permits improved solutions which approximate the exhaustive-search multistage solution. A deterministic annealing design method capitalizing on this structure is formulated within the framework of information theory. The sequential search constraint is included as a prior, and the principal of minimum cross entropy is invoked. The method obtains improvement over both the standard sequential design and joint optimization approaches.>

We present a new algorithm for cluster-oriented scheduling (COS) in pipelined data path synthesis. First, cluster structure information is extracted from the corresponding linear graph representation of a data flow graph (DFG). Then, scheduling and allocation globally interact with the cluster information under the timing constraints of pipeline latency and data initialization interval (DII). Using this technique, the costs of registers, multiplexors, and interconnection were reduced dramatically in both the FIR and elliptic filter examples.>

A deterministic annealing approach to clustering is derived on the basis of the principle of maximum entropy. This approach is independent of the initial state and produces natural hierarchical clustering solutions by going through a sequence of phase transitions. It is modified for a larger class of optimization problems by adding constraints to the free energy. The concept of constrained clustering is explained, and three examples are are given in which it is used to introduce deterministic annealing. The previous clustering method is improved by adding cluster mass variables and a total mass constraint. The traveling salesman problem is reformulated as constrained clustering, yielding the elastic net (EN) approach to the problem. More insight is gained by identifying a second Lagrange multiplier that is related to the tour length and can also be used to control the annealing process. The open path constraint formulation is shown to relate to dimensionality reduction by self-organization in unsupervised learning. A similar annealing procedure is applicable in this case as well.>

A new approach to the combined source-channel vector quantizer design problem is presented. The method utilizes deterministic annealing to avoid local minima that trap conventional descent algorithms. The temperature is used to control the fuzziness of the encoder and decoder association probabilities. In the low temperature limit, the method reduces to a descent method that is an analog of the generalized Lloyd algorithm (GLA) for noisy channels. Thus, in this sense, it is a generalization of noisy channel GLA (NC-GLA). Simulations were performed in order to compare the approach with several versions of NC-GLA. The method outperformed the other methods under all test conditions. Moreover, the gains over other methods grow with the codebook size.>

A deterministic annealing approach is suggested to search for the optimal vector quantizer given a set of training data. The problem is reformulated within a probabilistic framework. No prior knowledge is assumed on the source density, and the principle of maximum entropy is used to obtain the association probabilities at a given average distortion. The corresponding Lagrange multiplier is inversely related to the 'temperature' and is used to control the annealing process. In this process, as the temperature is lowered, the system undergoes a sequence of phase transitions when existing clusters split naturally, without use of heuristics. The resulting codebook is independent of the codebook used to initialize the iterations.>

It is argued that VLSI design assurance in a university setting requires developing an environment in which a multiplicity of reliable designs can be produced by inexperienced designers at minimal costs. Two issues in design verification and testing are examined: the first relates to design for testability; the second is the practical verification of designs once they are implemented in silicon. It is concluded that as problems associated with design assurance are solved, the results should be of value to a broader community and especially to ASIC (application-specific integrated circuit) designers.>

The author presents a philosophy of VLSI design education based on four premises: managing a VLSI design requires a hierarchical approach; a library of standard cells simplifies and increases design reliability; VLSI design requires interaction between the designer and a supportive CAE (computer-aided engineering) environment; and to allow reliable design by inexperienced designers, the CAE environment must assure design correctness. Training inexperienced designers requires providing feedback (including grades) on whether or not their designs work. The CAE tools must provide this feedback at all levels of the design process: layout circuit, logic and architecture. Assuring that designs work is a necessary part of design education. To achieve this, feedback to designers is essential at all levels and stages of the design process.>

The features and limitations of time- and frequencydivision miltiplexed (TDM and FDM) systems for providing interactive services on broad-band communication networks are considered. We find that TDM systems make efficient use of bandwidth for digital signal rates below 10 kbits/s while FDM systems are efficient for analog signals and digital signal rates above 1 kbit/s. Although TDM and FDM systems can employ static allocation in which fixed channels are assigned to subscribers, dynamic allocation increases the efficiency of bandwidth usage by an order of magnitude. A TDM interrupt scheme appears to be the most efficient way to identify requests and process control signals in a dynamic allocation system, but introduces a problem of interference between simultaneous signals (not present with a polling technique for request identification).

We discuss the impact of an evolving cable television technology on educational practice. The possible performance levels of a broad-band cable system, the quality of televised instruction, and the demands televised instruction would place on cable capacity are outlined. Social factors affecting individual preference and institutional resistance to cable education are considered.

The congestion in broad-band communications networks resulting from the increased demand for interactive services is considered. It is shown that services such as a video library could not be provided to the majority of subscribers in a conventional CATV network. A design is developed for a space division multiplex broad-band network which can be expanded at minimum cost to meet an increasing demand for interactive services. The network contains two signal distribution networks: a cablecast system similar to the Rediffusion system, and a switched communication network providing point-to-point circuits for both one-way and two-way services. All broad-band signals are transmitted to the subscribers in the 1- to 10-MHz spectrum, permitting the use of twisted pair video cables and a minimum number of cable amplifiers. The broad-band cable network (BCN) is organized around 15 local switching exchanges and one central exchange. Multipoint switches in local exchanges under wired-logic circuit control connect individual subscriber communication lines to any channel. Crosspoint matrix switching groups in the local and central exchanges connect communication circuits in the broad-band communication network under programmed computer control. This network is accessed via links terminating on one channel of the multiposition switches. Per-subscriber costs are estimated to be 190 dollars for a cablecast system serving 3800 subscribers. Additional expenditures per subscriber of 40 dollars for fixed costs and 40 dollars for variable costs would provide interactive services. The range of interactive services provided would be extremely flexible, including both one-way video library service and point-to-point two-way communications.