SUMMARY: Existing clustering methods for characterizing cell populations from single-cell RNA sequencing are constrained by several limitations stemming from the fact that clusters often cannot be homogeneous, particularly for transitioning populations. On the other hand, dominant cell populations within samples can be identified independently by their strong gene co-expression signatures using methods unrelated to partitioning. Here, we introduce a clustering method, CASCC (co-expression-assisted single-cell clustering), designed to improve biological accuracy using gene co-expression features identified using an unsupervised adaptive attractor algorithm. CASCC outperformed other methods as evidenced by multiple evaluation metrics, and our results suggest that CASCC can improve the analysis of single-cell transcriptomics, enabling potential new discoveries related to underlying biological mechanisms. AVAILABILITY AND IMPLEMENTATION: The CASCC R package is publicly available at https://github.com/LingyiC/CASCC and https://zenodo.org/doi/10.5281/zenodo.10648327.

During the last ten years, many research results have been referring to a particular type of cancer-associated fibroblasts associated with poor prognosis, invasiveness, metastasis and resistance to therapy in multiple cancer types, characterized by a gene expression signature with prominent presence of genes COL11A1, THBS2 and INHBA. Identifying the underlying biological mechanisms responsible for their creation may facilitate the discovery of targets for potential pan-cancer therapeutics. Using a novel computational approach for single-cell gene expression data analysis identifying the dominant cell populations in a sequence of samples from patients at various stages, we conclude that these fibroblasts are produced by a pan-cancer cellular transition originating from a particular type of adipose-derived stromal cells naturally present in the stromal vascular fraction of normal adipose tissue, having a characteristic gene expression signature. Focusing on a rich pancreatic cancer dataset, we provide a detailed description of the continuous modification of the gene expression profiles of cells as they transition from APOD-expressing adipose-derived stromal cells to COL11A1-expressing cancer-associated fibroblasts, identifying the key genes that participate in this transition. These results also provide an explanation to the well-known fact that the adipose microenvironment contributes to cancer progression.

Bulk samples of the same patient are heterogeneous in nature, comprising of different subpopulations (subclones) of cancer cells. Cells in a tumor subclone are characterized by unique mutational genotype profile. Resolving tumor heterogeneity by estimating the genotypes, cellular proportions and the number of subclones present in the tumor can help in understanding cancer progression and treatment. We present a novel method, ChaClone2, to efficiently deconvolve the observed variant allele fractions (VAFs), with consideration for possible effects from copy number aberrations at the mutation loci. Our method describes a state-space formulation of the feature allocation model, deconvolving the observed VAFs from samples of the same patient into three matrices: subclonal total and variant copy numbers for mutated genes, and proportions of subclones in each sample. We describe an efficient sequential Monte Carlo (SMC) algorithm to estimate these matrices. Extensive simulation shows that the ChaClone2 yields better accuracy when compared with other state-of-the-art methods for addressing similar problem and it offers scalability to large datasets. Also, ChaClone2 features that the model parameter estimates can be refined whenever new mutation data of freshly sequenced genomic locations are available. MATLAB code and datasets are available to download at: https://github.com/moyanre/method2.

SUMMARY: We developed 2DImpute, an imputation method for correcting false zeros (known as dropouts) in single-cell RNA-sequencing (scRNA-seq) data. It features preventing excessive correction by predicting the false zeros and imputing their values by making use of the interrelationships between both genes and cells in the expression matrix. We showed that 2DImpute outperforms several leading imputation methods by applying it on datasets from various scRNA-seq protocols. AVAILABILITY AND IMPLEMENTATION: The R package of 2DImpute is freely available at GitHub (https://github.com/zky0708/2DImpute). CONTACT: [email protected]. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: DNA pooling constitutes a cost effective alternative in genome wide association studies. In DNA pooling, equimolar amounts of DNA from different individuals are mixed into one sample and the frequency of each allele in each position is observed in a single genotype experiment. The identification of haplotype frequencies from pooled data in addition to single locus analysis is of separate interest within these studies as haplotypes could increase statistical power and provide additional insight. RESULTS: We developed a method for maximum-parsimony haplotype frequency estimation from pooled DNA data based on the sparse representation of the DNA pools in a dictionary of haplotypes. Extensions to scenarios where data is noisy or even missing are also presented. The resulting method is first applied to simulated data based on the haplotypes and their associated frequencies of the AGT gene. We further evaluate our methodology on datasets consisting of SNPs from the first 7Mb of the HapMap CEU population. Noise and missing data were further introduced in the datasets in order to test the extensions of the proposed method. Both HIPPO and HAPLOPOOL were also applied to these datasets to compare performances. CONCLUSIONS: We evaluate our methodology on scenarios where pooling is more efficient relative to individual genotyping; that is, in datasets that contain pools with a small number of individuals. We show that in such scenarios our methodology outperforms state-of-the-art methods such as HIPPO and HAPLOPOOL.

Mining gene expression profiles has proven valuable for identifying signatures serving as surrogates of cancer phenotypes. However, the similarities of such signatures across different cancer types have not been strong enough to conclude that they represent a universal biological mechanism shared among multiple cancer types. Here we present a computational method for generating signatures using an iterative process that converges to one of several precise attractors defining signatures representing biomolecular events, such as cell transdifferentiation or the presence of an amplicon. By analyzing rich gene expression datasets from different cancer types, we identified several such biomolecular events, some of which are universally present in all tested cancer types in nearly identical form. Although the method is unsupervised, we show that it often leads to attractors with strong phenotypic associations. We present several such multi-cancer attractors, focusing on three that are prominent and sharply defined in all cases: a mesenchymal transition attractor strongly associated with tumor stage, a mitotic chromosomal instability attractor strongly associated with tumor grade, and a lymphocyte-specific attractor.

Abstract Summary:We present a visualization tool applied on genome-wide association data, revealing disease-associated haplotypes, epistatically interacting loci, as well as providing visual signatures of multivariate correlations of genetic markers with respect to a phenotype. Availability:Freely available on the web at: http://www.ee.columbia.edu/~anastas/sdplots Contact: [email protected] Supplementary information: Supplementary data are available at Bioinformatics online.

MOTIVATION: Conserved motifs often represent biological significance, providing insight on biological aspects such as gene transcription regulation, biomolecular secondary structure, presence of non-coding RNAs and evolution history. With the increasing number of sequenced genomic data, faster and more accurate tools are needed to automate the process of motif discovery. RESULTS: We propose a deterministic sequential Monte Carlo (DSMC) motif discovery technique based on the position weight matrix (PWM) model to locate conserved motifs in a given set of nucleotide sequences, and extend our model to search for instances of the motif with insertions/deletions. We show that the proposed method can be used to align the motif where there are insertions and deletions found in different instances of the motif, which cannot be satisfactorily done using other multiple alignment and motif discovery algorithms. AVAILABILITY: MATLAB code is available at http://www.ee.columbia.edu/~kcliang

It has been shown that electropherograms of DNA sequences can be modeled with hidden Markov models. Basecalling, the procedure that determines the sequence of bases from the given eletropherogram, can then be performed using the Viterbi algorithm. A training step is required prior to basecalling in order to estimate the HMM parameters. In this paper, we propose a Bayesian approach which employs the Markov chain Monte Carlo (MCMC) method to perform basecalling. Such an approach not only allows one to naturally encode the prior biological knowledge into the basecalling algorithm, it also exploits both the training data and the basecalling data in estimating the HMM parameters, leading to more accurate estimates. Using the recently sequenced genome of the organism Legionella pneumophila we show that the MCMC basecaller outperforms the state-of-the-art basecalling algorithm in terms of total errors while requiring much less training than other proposed statistical basecallers.

Computational analysis of gene expression data from microarrays has been useful for medical diagnosis and prognosis. The ability to analyze such data at the level of biological modules, rather than individual genes, has been recognized as important for improving our understanding of disease-related pathways. It has proved difficult, however, to infer pathways from microarray data by deriving modules of multiple synergistically interrelated genes, rather than individual genes. Here we propose a systems-based approach called Entropy Minimization and Boolean Parsimony (EMBP) that identifies, directly from gene expression data, modules of genes that are jointly associated with disease. Furthermore, the technique provides insight into the underlying biomolecular logic by inferring a logic function connecting the joint expression levels in a gene module with the outcome of disease. Coupled with biological knowledge, this information can be useful for identifying disease-related pathways, suggesting potential therapeutic approaches for interfering with the functions of such pathways. We present an example providing such gene modules associated with prostate cancer from publicly available gene expression data, and we successfully validate the results on additional independently derived data. Our results indicate a link between prostate cancer and cellular damage from oxidative stress combined with inhibition of apoptotic mechanisms normally triggered by such damage.

We present a unique FPGA that uses a mix of digital and large-signal analog computation for the simulation of gene regulatory networks. The prototype IC consists of a 4x5 array of configurable logic blocks along with programmable interconnect. It can simulate a network of pathways involving up to 20 genes and their associated proteins. The circuit design takes advantage of a number of analogies between CMOS circuits and gene networks. For example, a capacitor charge is used to represent a protein concentration, currents represent protein production, and a transistor switch network is used to compute the influences of activator and repressor proteins on gene expression. A simulation shows how the chip can predict oscillatory behavior in a particular well-known three-gene system.

We demonstrate that digital signal processing of biomolecular sequences provides powerful approaches for solving highly relevant problems in bioinformatics by properly mapping character strings into numerical sequences. As examples, we show that color spectrograms visually provide, in the form of local texture, significant information about biomolecular sequences, thus facilitating understanding of local nature, structure and function; we provide an optimization procedure predicting protein-coding regions in DNA sequences including reading frame and coding direction, using both the magnitude and the phase of properly defined Fourier transforms; and we present a digital filtering approach to the process of translating nucleic acids into proteins. These approaches result in alternative mathematical formulations and often provide improved computational techniques for the solution of useful problems in genomic information science and technology.

MOTIVATION: Frequency-domain analysis of biomolecular sequences is hindered by their representation as strings of characters. If numerical values are assigned to each of these characters, then the resulting numerical sequences are readily amenable to digital signal processing. RESULTS: We introduce new computational and visual tools for biomolecular sequences analysis. In particular, we provide an optimization procedure improving upon traditional Fourier analysis performance in distinguishing coding from noncoding regions in DNA sequences. We also show that the phase of a properly defined Fourier transform is a powerful predictor of the reading frame of protein coding regions. Resulting color maps help in visually identifying not only the existence of protein coding areas for both DNA strands, but also the coding direction and the reading frame for each of the exons. Furthermore, we demonstrate that color spectrograms can visually provide, in the form of local 'texture', significant information about biomolecular sequences, thus facilitating understanding of local nature, structure and function.

A novel and simple approach for defining end-to-end quality of service (QoS) in video-on-demand (VoD) services is presented. Using this approach, we derive a schedulable region for a video server which guarantees end-to-end QoS, where a specific QoS required in the video client translates into a QoS specification for the video server. Our methodology is based on a generic model for VoD services, which is extendible to any VoD system. In this kind of system, both the network and the video server are potential sources of QoS degradation. Specifically, we examine the effect that impairments in the video server and video client have on the video quality perceived by the end user. The Columbia VoD testbed is presented as an example to validate the model through experimental results. Our model can be connected to network QoS admission control models to create a unified approach for admission control of incoming video requests in the video server and network.

This paper addresses the issue of hierarchical coding of digital television. A two-layer coding scheme is presented to provide compatibility of standard-definition television (SDTV) and high-definition television (HDTV). The scheme is based on a spatio-temporal pyramid coding technique. We address the problem of interlaced-to-interlaced two-layer compatible coding where both layers are interlaced. The resolution translation is important for the visual quality of the SDTV layer and for the performance of the HDTV layer. A motion-compensated up/down deinterlacing scheme is used to improve the performance. A spatio-temporal averaging technique is used to give a better compatible prediction so that the HDTV layer has a high compression performance. To offer an improved prediction, systematic analysis of the remaining statistical redundancy of the enhancement signal is conducted. Based on an autoregressive model of the difference signal, a Kalman statistical filtering is used to exploit such a redundancy. We combine a recursive filtering and discrete cosine transform (DCT) coding using QR decomposition, where Q is an orthonormal matrix and R is an upper triangular matrix. The error accumulation is cancelled in the DCT frequency domain. The results show peak signal-to-noise-ratio improvements over simulcast as high as 1.2 dB. The new technique, which is referred to as spatial scalability using a Kalman filter (SSKF), achieves a comparable or better picture quality than that of a nonscalable approach for high-quality video coding. The near optimal performance is demonstrated by the white Gaussian noise property of the residual signal.

An algorithmic architecture of video compression at very low bit rate is presented. This architecture incorporates block-based as well as segment-based coding algorithms and manages them in a cooperative way in which different approaches are applied to different image frames iteratively: I and P frames are coded by block-based algorithm and O frames are coded by segment-based algorithm. An extra degree of freedom in video coding is introduced in order to achieve higher compression ratios while maintaining good visual quality. Every other frame in the image sequence is coded using block-based coding (ITU-T H.263) with motion (block-matching, 2D translations) and color (DCT) coefficients. These I and P frames are allocated with more bits, generating images with higher spatial accuracy, and providing the coder with generic coding capability. Between every two P frames, the O frame is coded using segment-based algorithm providing the motion (rigid 2D source models, 3D motions) and shape (polygon or spline approximation) information. Since only motion prediction is provided, pixel values are copied or interpolated from neighboring P frames. With good segmentation and affine transform, the prediction can preserve the natural shapes of the objects and give natural motion information which is sufficient for very low bitrate coding. These frames are allocated with less bits, generating images with less temporal accuracy, but providing the coder with higher compression efficiency.

This paper describes our progress in developing an advanced video-on-demand (VOD) testbed, which will accommodate various multimedia research and applications such as Electronic News on Demand, Columbia's Video Course Network, and Digital Libraries. Two different prototypes have been completed. The first generation of the testbed was based on a constant-bit-rate (CBR) video server utilizing Ethernet delivery. Contents were encoded and stored as MPEG-2 audio/video elementary streams. Software encoders/decoders were used in content generation and playback. The second generation of the testbed was enhanced with the capability of transmitting true MPEG-2 transport streams over the campus ATM network as well as the wide-area NYNET ATM network. A real-time video pump and a distributed application control protocol (MPEG-2's DSM-CC) have been incorporated. Hardware decoders and set-tops are being incorporated to test wide-area video interoperability. Our VOD testbed also provides an advanced platform for implementing proof-of-concept prototypes of related research. Our current research focus covers video transmission with heterogeneous quality-of-service (QoS) provision, video storage architecture design, content-based video indexing and browsing, multi-resolution (MR) video coding, efficient manipulation of compressed video, and advanced user interfaces. An important aim is to enhance interoperability. Accommodation of practical multimedia applications and interoperability testing with external VOD systems are currently being undertaken.

We analyze different retransmission (ARQ) schemes for error control in multicast protocols geared toward real-time, multimedia applications. We discuss why retransmission schemes are not inappropriate for such applications, but in fact can be quite effective. We present a quantitative analysis of such schemes, as well as simulation results, taking into account four different parameters (and not just the source throughput): (1) the probability of dropping a packet due to limited time for retransmissions; (2) the average time required to deliver a packet correctly to end receivers; (3) the number of times a packet will be retransmitted; and (4) the cost to the network, in terms of packet duplications, of retransmitting a packet. We reach the counter-intuitive conclusion that the optimum scheme, in terms of all four of the above parameters, in the most general scenarios (where several hosts with widely varying propagation delays and 'quality of connections' are participating in the session) is to immediately retransmit packets-preferably multicast-upon reception of a NACK from any receiver. We also demonstrate, again through quantitative analysis, the circumstances under which it would be beneficial (as well as those under which it would be counter-productive) to multicast control messages in the hope of suppressing duplicates and preventing the source from being overwhelmed by control messages.

We introduce the concept of dynamic rate shaping, a technique to adapt the rate of compressed video bitstreams (MPEG-1, MPEG-2, H.261, as well as JPEG) to dynamically varying bit rate constraints. The approach provides an interface (or filter) between the encoder and the network, with which the encoder's output can be perfectly matched to the network's quality of service characteristics. Since the presented algorithms do not require interaction with the encoder, they are fully applicable to precoded, stored video (e.g., video-on-demand systems). By decoupling the encoder and the network, universal interoperability can be achieved. In essence, DRS bridges the gap between CBR and VBR video, allowing a continuum of possibilities between the two. A set of low-complexity algorithms for so-called unconstrained dynamic rate shaping are presented, and both optimal and extremely fast designs are discussed. Experimental results are provided using actual MPEG-2 bitstreams.

Utilizing the Viterbi algorithm, a forward dynamic programming technique, and a compact disparity graph representation, reconstruction of intermediate views is made possible, including those objects whose views are occluded from various viewpoints. Based on the camera configuration for the capture of multiview images, and the one-to-one correspondence between a real world point and its multiview images, a number of geometric constraints are generated and taken advantaged of. In our proposal, the Viterbi algorithm is used to compute a dense disparity field for every pixel on the left extreme view and consistently for those pixels on the right extreme view. Thus even objects, present in one extreme view but not the other, can be accurately projected onto an intermediate frame. Furthermore, in the presence of obstructed-revealed-obstructed (ORO) objects, whose views are obstructed in both extreme views but revealed in some intermediate views, a third image composed of all ORO objects is incorporated. The large set of multiview images are then reduced to a maximum of three images along with their dense disparity maps, thus accounting for all objects viewable from a range of viewpoints. A simple view interpolation procedure is developed for accurate construction of all intermediate images, whether the originally captured ones or virtually added ones.

An architecture and associated protocols are presented for managing multicast addresses and performing connection control for multicast communication applications. A scheme to partition the multicast address space on the basis of the network number is proposed (an underlying IP-based internetworking environment is assumed), and its performance and scaling characteristics are discussed. A protocol is then developed to provide for dynamic allocation and release of multicast addresses, as well as maintaining state information for a connection. The protocol is independent of the address partitioning scheme; it is also shown to be robust and efficient. Finally, we describe two different mechanisms that enable the use of a common port number by all session participants.

We describe a distributed architecture for managing multicast addresses in the global Internet. A multicast address space partitioning scheme is proposed, based on the unicast host address and a per-host address management entity. By noting that port numbers are an integral part of end-to-end multicast addressing we present a single, unified solution to the two problems of dynamic multicast address management and port resolution. We then present a framework for the evaluation of multicast address management schemes, and use it to compare our design with three approaches, as well as a random allocation strategy. The criteria used for the evaluation are blocking probability and consistency, address acquisition delay, the load on address management entities, robustness against failures, and processing and communications overhead. With the distributed scheme the probability of blocking for address acquisition is reduced by several orders of magnitude, to insignificant levels, while consistency is maintained. At the same time, the address acquisition delay is reduced to a minimum by serving the request within the host itself. It is also shown that the scheme generates much less control traffic, is more robust against failures, and puts much less load on address management entities as compared with the other three schemes. The random allocation strategy is shown to be attractive primarily due to its simplicity, although it does have several drawbacks stemming from its lack of consistency (addresses may be allocated more than once).>

In this paper, we present a nonlinear interpolation scheme for still image resolution enhancement. The algorithm is based on a source model emphasizing the visual integrity of detected edges and incorporates a novel edge fitting operator that has been developed for this application. A small neighborhood about each pixel in the low-resolution image is first mapped to a best-fit continuous space step edge. The bilevel approximation serves as a local template on which the higher resolution sampling grid can then be superimposed (where disputed values in regions of local window overlap are averaged to smooth errors). The result is an image of increased resolution with noticeably sharper edges and, in all tried cases, lower mean-squared reconstruction error than that produced by linear techniques.

A two-layer coding approach with a spatial pyramid to achieve compatibility has been known to have several advantages. The first layer can have optimal performance. Rate control can be distributed between layers. However, the compression performance and the overall complexity at the high resolution layer suffer because of the requirement of compatibility. Therefore, good compatibility prediction is a crucial factor for a spatial scalability approach. In the paper, the authors focus on obtaining the best compatibility prediction, assuming that a spatially upsampled block and a motion compensated block are available. A spatio-temporal averaging technique has been shown to provide improvement. With a linear regression analysis, further improvement in prediction is shown. Better compatibility prediction can be obtained by assigning the spatio-temporal weights adaptively for individual pixels. The authors found that a pel-adaptive recursive estimation using Kalman filters gives a good compatibility prediction. The new difference signal has the statistical property of white Gaussian noise. The additional complexity is moderate and the bits for sending side information is insignificant. The resultant picture quality of the approach approximates the picture quality of the noncompatible single-layer approach.>

We analyze the problem of optimal data partitioning of MPEG-2 coded video in an operational rate-distortion context. The optimal algorithm is characterized and shown to have high complexity and delay. A causally optimal algorithm based on Lagrangian optimization is proposed, that optimally solves the problem for intra (I) pictures, while it provides an optimal solution for predicted/interpolated (P/B) pictures when the additional constrains of causal operation and/or low-delay are imposed. A memoryless version of the algorithm, theoretically optimal for intra-pictures only, is shown to perform almost identically but with significantly less computational complexity. Finally, a fast, suboptimal algorithm using slice-based optimization is also proposed, and is shown to perform quite close (within 1 dB) to the causally optimal one.>

It is now recognized worldwide that all television services, including HDTV, will eventually become digital, but there is wide disagreement about the optimum timing for transforming existing analog systems. A major driving force is the ongoing partial merging of television and digital computers in interactive multimedia services involving digital television and applications in areas like information (news), education, medical, entertainment, etc. A major target is to maximize interoperability of video services at all levels, including various resolutions, different transmission and storage mechanisms, as well as bit rates. This paper provides an overview of the current status in digital television, techniques used, future prospects, and research areas that need to be investigated. The maturity of compression techniques needed for digital video storage and transmission, and the establishment of international standards for digital television representation, like MPEG-2, have greatly contributed in this transformation. Recent developments are mentioned, including the American "Grand Alliance" FCC effort for digital terrestrial HDTV broadcasting, and also other efforts for digital television by cable and DBS. The concept of hierarchical multiresolution coding is also explained, and some of its techniques are briefly described.>

The authors mathematically analyze the drift of low-resolution images obtained from a smaller IDCT of a subset of the DCT coefficients of the full-resolution images in motion-compensated hybrid predictive/DCT coding such as MPEG-2, which allows for frequency scalability. Using this mathematical structure, they derive a low-resolution decoder that has the theoretically minimum possible drift, and propose techniques for implementation that produce substantial improvement in real sequences. The minimum drift can also be used as a milestone, to be compared with other techniques of drift reduction (of worse performance but lower complexity). For the case where leakage is used to reduce the drift, the authors determine a minimum-energy non-uniform DCT-domain leakage matrix which is no more complex than uniform leakage, but gives a substantial improvement. Finally, they note that DCT-based pyramidal coding is essentially the same as the drift case, and thus they use the same mathematical structure to derive the theoretically-best upward predictor in pyramidal coding.>

We describe and evaluate the performance of the algorithms used in Columbia University's "Xphone" multimedia communication system. The system assumes a "best-effort" operating system and network, and provides synchronized video/audio acquisition/playback (locally or across a network) with minimized and bounded end-to-end delay. Synchronization is achieved using an algorithm based on time-stamps and device state information. The effects of jitter (delay variation) are mitigated using silence detection; the end-to-end delay is kept bounded using a restart mechanism. Finally, for live video sources, we describe a source bit-rate adaptation algorithm that maximizes the video image quality to the available network bandwidth and video display window size.

This paper presents the video coding technique proposed by Columbia University for the second phase of ISO's MPEG standardization effort (MPEG-2) for coding at bit-rates up to 10 Mbit/s. The technique is a direct extension of the coding algorithm used for MPEG-1, suitable for interlaced video by allowing macroblock-by-macroblock adaptive field-based or frame-based coding. Separate coding of the odd and even fields is allowed as an option, so that fields of one parity use information from the already coded fields of the opposite parity. This option has near-optimum performance, and also conveniently provides scalability (in the sense of multiresolution representation), useful for achieving graceful degradation in the presence of transmission errors. It also permits easy modification for compatibility with MPEG-1. Another feature includes escape to a non-DCT coding technique for blocks containing sharp edges. Based on both subjective and objective evaluations, extensive computer simulations have been conducted to optimize the criteria of using various modes.

A compatible enhanced definition television (EDTV) terrestrial broadcasting technique providing for digitally assisted interpolation of the missing lines of interlaced television image sequences resulting in 525/60/1:1 displayed video is presented. An auxiliary bit stream of compressed data consisting of coded motion and reconstruction-mode information can be used to improve greatly the quality of received television images. Due to the restricted bandwidth available, coding operations for the deinterlacing process are implemented on a block basis, over which a limited quad-tree segmentation is applied to enhance reconstruction quality where possible. Receiver complexity is kept low since all necessary motion estimation is performed at the transmitter site. Simulation results demonstrate that this technique enables high-quality progressive image representation within the constrained-transmission environment of the traditional interlaced broadcast.>

A digital halftoning technique for the efficient transformation of gray-scale images into bilevel ones, based on the progressive generation of the bilevel image pixels in a parallel way, is presented. An image distortion criterion, in which the gray-tone image is approximated by a filtered version of the halftoned image, is used for this purpose. A combined scheme is also derived in which continuous-tone images are progressively coded and transmitted in bilevel form and can be reconstructed in gray-scale form.>

A nonlinear interpolation scheme for image-resolution enhancement is presented. The algorithm is based upon a source model emphasizing edges and incorporates a hybrid local edge-fitting operator which has been developed for this application. A small neighbourhood about each pixel in the low-resolution image is first mapped to a best-fit continuous-space step-edge. This bilevel approximation serves as a local template upon which the higher-resolution sampling grid can then be superimposed. Disputed values in regions of overlap are averaged to smooth errors. The result is an image of increased resolution with noticeably sharper edges and lower reconstruction error than produced by linear techniques.>

Most improved definition television (IDTV) receivers use progressive scanning to reduce artifacts associated with interlacing (e.g. interline flicker, line crawl, etc). We propose some novel techniques of motion compensated interpolation of the missing lines of interlaced monochrome and color sequences, reducing the artifacts associated with interlacing, and effectively increasing the vertical resolution of the image sequences. Time-recursive motion compensated prediction is introduced, in which all previously displayed history (not just the previous field) is used to predict the missing pixel values. The next future field is also used for the same purpose, by a look-ahead scheme. Motion estimation is done using a quadtree-based segmented block-matching technique with half pixel accuracy. To avoid artifacts and obtain full resolution in still regions, like background, motion adaptation is used as well. We also discuss how to apply this algorithm to pyramid coding to achieve better compression rate and compatibility of progressive with interlaced format standards.

Digital image halftoning is treated as an optimization problem to which neural networks provide an efficient parallel solution. An image distortion measure is introduced in which the gray-tone image is approximated by a filtered version of the halftoned image. This distortion measure is minimized by using a near-neighborhood-connected symmetric neural network. The filter used in the distortion measure is estimated on the basis of a training set of gray-tone and bilevel images. This filter is then used for the reconstruction of a gray-tone image from its halftoned version. The above procedure, combined with a postprocessing of the reconstructed image by a nonlinear edge-preserving noise-smoothing filter, provides images of good quality.>

The authors extend earlier work (ibid., vol.36, p.834-44, Jul. 1988) in modeling video sources using interframe coding schemes and in carrying out buffer queueing analysis for the multiplexing of several such sources. The previous models and analysis were suitable for relatively uniform activity scenes. Here, models are considered for scenes with multiple activity levels which lead to sudden changes in the coder output bit rates. Such models apply to talker-listener alternating scenes, as well as to situations where there is a mix of dissimilar services, e.g., television and videotelephony. Correlated Markov models for the corresponding sources are given. A flow-equivalent queueing analysis is used to obtain common buffer queue distributions and probabilities of packet loss. The results demonstrate the efficiency of packet video on a single link, due to the smoothing effect of multiplexing several variable-bit-rate video sources.>

A technique is presented for coding images that are bilevel in nature but have been captured in continuous-tone format. Following various stages of image processing, a three-level image is generated, and compressed to about 0.1 to 0.2 b/pixel. The technique has been implemented in the IBM freeze-frame videoconferencing system.>

Stability conditions for nonlinear recursive filters are established. The results are applied to nonlinear recursive filters of the form y(n)=f(x(n), y(n-1)). In the case of image filtering by incorporating with a multi-directional scheme, a two-dimensional nonlinear recursive image filter, satisfying these conditions, with combined edge-sharpening and noise-smoothing characteristics has been developed. It can be used for image enhancement or restoration, or as a pre-processor for coding techniques.>

Models and results are presented that assess the performance of statistical multiplexing of independent video sources. Presented results indicate that the probability of buffering (or delaying) video data beyond an acceptable limit drops dramatically as the number of multiplexed sources increases beyond one. This demonstrates that statistical or asynchronous time-division multiplexing (TDM) can efficiently absorb temporal variations of the bit rate of individual sources without the significant variations in reception quality exhibited by multimode videocoders for synchronous TDM or circuit-switched transmission. Two source models are presented. The first model is an autoregressive continuous-state, discrete-time Markov process, which was used to generate source data in simulation experiments. The second model is a discrete-state, continuous-time Markov process that was used in deriving a fluid-flow queuing analysis. The presented study shows that both models generated consistent numerical results in terms of queuing performance.>

A new gray-scale image coding technique has been developed, in which an extended DPCM approach has been combined with entropy coding. This technique has been implemented in a freeze-frame videoconferencing system which is now operational at IBM sites throughout the world. Following image preprocessing, the two fields of the interlaced 512 x 480 pixel video frame are compressed sequentially with different algorithms. The reconstructed image quality is improved by subsequent image postprocessing, the final reconstructed image being almost indistinguishable from the original image. Typical gray-scale video images compress to about a half bit per pixel and transmit over 4.8 kbit/s dial-up telephone lines in about a half minute. The gray-scale image processing and compression algorithms are described in this paper.

In an effort to enhance the practical applicability of information theory, to image processing, various findings regarding the entropy rate of two-dimensional random fields are presented. In particular, equivalent representations of the entropy rate of a random field are given, and the entropy rates of various random fields including the Ising model are mentioned.

A Gibbsian probability measure is defined on the set of possible shapes of simple (i.e., not self-intersecting) and closed curves on a discretized lattice. Expressions have been derived for such quantifies as the entropy, average perimeter length, and area in terms of the model parameters, and an iterative procedure has been devised for generating sample objects according to this distribution.

In order to apply the results of information theory to the efficient storage or transmission of images, it is necessary to model the image source distribution and specify an appropriate fidelity criterion. One useful source model results from separating the log intensity random field of a typical image into the sum of two nearly independent random fields with a simpler description. It has also been found that under certain conditions a frequency-weighted squared-error fidelity criterion is satisfactory for evaluating the images. Thus it is important to consider the situation in which the source output is the sum of two independent random entities with known rate-distortion functions with respect to a (perhaps frequency-weighted) squared-error criterion. These rate-distortion functions are used to provide new bounds to the rate-distortion function of the additive source with respect to the same criterion. In one example considered, the new bounds are the tightest known in certain distortion regions. Examples from image coding are given, including a comparison of the performances of various encoding schemes.