In wireless sensor networks (WSNs), how to reduce the power consumption thus lengthen the system life time is one of the key issues to sustain the services. According to the radio model, packet transmission depletes a much more substantial amount of the energy budget when compared to sensing and processing. Therefore, it is desirable to compress or filter the sensing data effectively in order to save the transmission power eventually. Recently, the model-based scheme is proved to be a promising solution, which usually approximate temporal data by a piecewise linear function. In this paper, a tree-structured linear approximation scheme is proposed to compress sensing data according to an optimal rate-distortion (R-D) relationship. The main design goals are two: (1) providing a bottom-up procedure to explore the best-fit piecewise partition for modeling globally, (2) considering the heterogeneity of sensors simultaneously using our proposed rate-distortion adjustment. That is, a distortion allocation procedure is designed to allocate the distortions to sensor nodes for aware of the heterogeneous properties. Thus the proposed spatio-temporal scheme is adaptable to heterogeneous sensors, various sampling rate, and outliers of data. A real-world dataset simulation is applied to demonstrate the effectiveness. For nearly all combinations with distortion requirements, the proposed method shows better performance than the earlier approaches in terms of data reduction.

The application of video streaming is expected to shift to mobile broadband as soon as the Ultra-dense Networks (UDN) and High Efficiency WLAN (HEW) become popular. The motivation of this paper is to propose a distributed delivery scheme for streaming popular videos over UDN wireless environments. The H.264 SVC scalable source coding and the LT codes of rateless channel coding are both considered and integrated to provide reliable and scalable video services wirelessly. In the allocation phase, a hot video clip is both SVC encoded and LT encoded. Then, the coded data are randomly distributed among small-cell stations (SCs) or related attached servers. In the serving phase, one nearby SC immediately decodes its own LT coded data once a request issued and broadcasts them to the requesting user and the neighboring SCs to continue the undone decoding process in parallel. Thus, the clients can receive data from multiple SCs to achieve the goal of bandwidth aggregation. Besides, once the decoding process being completed, the repairing process is ignited to recover the possible node failure if exists. Two data allocation schemes are considered to balance the storage space, transmission bandwidth and fault tolerance requirements. In the ultra-dense scenarios, our simulations show that each request can be served with at least acceptable quality and with one more enhancement layer in average under communication loss rate less than 10% and possible node failures.

BACKGROUND: Unsupervised analyses such as clustering are the essential tools required to interpret time-series expression data from microarrays. Several clustering algorithms have been developed to analyze gene expression data. Early methods such as k-means, hierarchical clustering, and self-organizing maps are popular for their simplicity. However, because of noise and uncertainty of measurement, these common algorithms have low accuracy. Moreover, because gene expression is a temporal process, the relationship between successive time points should be considered in the analyses. In addition, biological processes are generally continuous; therefore, the datasets collected from time series experiments are often found to have an insufficient number of data points and, as a result, compensation for missing data can also be an issue. RESULTS: An affinity propagation-based clustering algorithm for time-series gene expression data is proposed. The algorithm explores the relationship between genes using a sliding-window mechanism to extract a large number of features. In addition, the time-course datasets are resampled with spline interpolation to predict the unobserved values. Finally, a consensus process is applied to enhance the robustness of the method. Some real gene expression datasets were analyzed to demonstrate the accuracy and efficiency of the algorithm. CONCLUSION: The proposed algorithm has benefitted from the use of cubic B-splines interpolation, sliding-window, affinity propagation, gene relativity graph, and a consensus process, and, as a result, provides both appropriate and effective clustering of time-series gene expression data. The proposed method was tested with gene expression data from the Yeast galactose dataset, the Yeast cell-cycle dataset (Y5), and the Yeast sporulation dataset, and the results illustrated the relationships between the expressed genes, which may give some insights into the biological processes involved.

Distributed storage coding has been widely applied on data gathering over unreliable wireless sensor networks (WSNs), where it is essential to ensure the data persistence in case of several sensor failures caused by battery run-out or some physical damage problems surroundings. How to efficiently disseminate and collect the sensing data over WSNs is a key challenge yet. In this study, assumed that there are K sensor nodes equipped with sensing apparatus within N storage sensors, these K numbers of sensors can sense environmental changes and disseminate coded (by Fountain codes) time-series data over WSNs using the simple random walk. In order to perform the Fountain codes over WSNs, the question is to disseminate data in the long range of random walks to preserve the randomness so as to promote the source decoded rate. In this paper, a framework with partial decoding is proposed due to the temporal dependency of time-series sensing data. The reasons are twofold: (a) the complete decoding is not necessary for time-series data since the missing portions can be compensated by that of neighbors; (b) even if the ideal Luby transform (LT) code is optimized in terms of convergence, the complete decoding process is high power-consuming. Furthermore, a mathematical model to estimate the appropriate source decoded rate is given to guarantee the error tolerable level (<; 4% normalized root-mean-square error (NRMSE)). Experimental results show that the communication cost is affordable in the real cases.

This paper presents an Unequal Error Protection (UEP) method for streaming media. Previous researches have shown that UEP rateless codes can provide a low-complexity solution for downloading scalable information. However, the randomized generator of rateless codes leads to uncertainty of decoding probability and decoding priority of input data, and thus it is not suitable for streaming applications. In this paper, a novel UEP method is presented for streaming media. The proposed method, which consists of a hierarchical coding graph as well as low-complexity encoding and decoding operations, preserves the advantage of the UEP rateless codes and characterizes the decoding probability and decoding priority by formulas. The proposed hierarchical coding graph guarantees that high-priority input data are recovered before low-priority ones, so important information can be recovered with low latency, low computation, and high probability. In addition, data in different layers of the proposed UEP are dependently encoded, so that data in different layers can help decode each other. For heterogeneous clients, the proposed UEP codes can help a decoder with recovery of different amount of information according to the network condition and computation ability. Besides, we also extend the proposed UEP codes to a rateless version for downloading of media. Compared with the previous finite-length and rateless UEP codes, our method can recover more high-priority data even in serious packet loss rate (PLR), and the decoding order of data can be assigned by the server.

Lossy compression techniques are commonly used by long-term data-gathering applications that attempt to identify trends or other interesting patterns in an entire system since a data packet need not always be completely and immediately transmitted to the sink. In these applications, a nonterminal sensor node jointly encodes its own sensed data and the data received from its nearby nodes. The tendency for these nodes to have a high spatial correlation means that these data packets can be efficiently compressed together using a rate-distortion strategy. This paper addresses the optimal rate-distortion allocation problem, which determines an optimal bit rate of each sensor based on the target overall distortion to minimize the network transmission cost. We propose an analytically optimal rate-distortion allocation scheme, and we also extend it to a distributed version. Based on the presented allocation schemes, a greedy heuristic algorithm is proposed to build the most efficient data transmission structure to further reduce the transmission cost. The proposed methods were evaluated using simulations with real-world data sets. The simulation results indicate that the optimal allocation strategy can reduce the transmission cost to 6~15% of that for the uniform allocation scheme.

Luby Transform (LT) codes are becoming increasingly important in transmission due to the ability to protect the source data in high reliability economically. LT codes generate rateless packets on-the-fly through randomly chosen encoding degree, so it cannot control or manage the service quality according to distinct service demands of clients. In this article, we extended LT codes with a service-driven control policy. The proposed encoder arranges the encoding degree through the basic building structures via various control policies to fulfill the requests of majority of clients. With the proposed control policies in the multicasting or broadcasting channel, source data of most clients can be recovered as soon as possible. Besides, comparing to LT codes in point-to-point protocol, the proposed codes also introduce lower decoding overhead, better intermediate performance, and built-in unequal error protection property through appropriately arranging the placements of source data in the coding graph.

We propose an unsupervised approach for analyzing gene time-series datasets. Our method combines Affinity Propagation (AP) and the spirit of consensus clustering-- extracting multiple partitions from different time intervals. Without priori knowledge of total number of clusters and exemplars, this method holds the relationship between genes through different time intervals, and eliminates the influence from noises and outliers. We demonstrate our method with both synthetic and real gene expression datasets showing significant improvement in accuracy and efficiency.

In this paper, we proposed a channel coding mechanism for layered videos based on the concept of Luby-Transform (LT) code. In a layered video streaming system, every video layer suffers from equal packet-loss rate; however, lower layers are more important than the higher ones. The proposed mechanism can protect those important layers from packet-loss to some meaningful degree. In other words, lower video layers can be earlier and easier decoded than high layers under the same packet-loss rate. Compared with other Unequal Error Protection schemes using Reed-Solomon code or LT code, the complexity and overhead are largely reduced. Besides, a randomized implement to generate appropriate coding graph on-line was proposed also, thus our mechanism is suitable for real-time applications with devices of limited computation capability and stringent delay requirement.

Proxy-caching strategies, especially prefix caching and interval caching, are commonly used in video-on-demand (VOD) systems to improve both the system performance and the playback experience of users. However, because these caching strategies are designed for homogeneous clients, they do not perform well in the real world where clients are heterogeneous (i.e., different available network bandwidths and different sizes of client-side buffers). This paper investigates the problems caused by heterogeneous client-side buffers. We analyze the theoretical performance of these caching strategies, and then, derive cost functions to measure the corresponding performance gains. Based on these analytical results, we develop a caching strategy that employs both prefix caching and interval caching to minimize the input bandwidth of a proxy. The simulation results demonstrate that the bandwidth requirements of a proxy implementing our caching strategy are significantly lower compared to adopting prefix caching or interval caching alone.

Mode decision is a kernel function of current video standards, especially while dealing with massive coding modes as the latest H.264/AVC variable block size partitions. The mode decision process is extreme time consuming because it contains the kernel motion estimation and intra prediction modules. By applying the concepts of using priority coding orders to encode a sequence, this paper concludes a set of mode decision strategies with observing among priority lists. A computation-aware mode decision scheme is then proposed to the H.264/AVC. As the results demonstrated, coding with priority orders can achieve computation-aware ability automatically and the priority info is very helpful for developing software-based computation-aware mode decision algorithms.

Periodic broadcasting is known as an efficient technique for delivering popular videos by reducing bandwidth requirement for transmitting streaming video to simultaneous viewers. The channel transition problem is a noticed issue to be concerned about the variability of popularity of video and resource management in periodic broadcasting. In this paper, we approach a general seamless channel transition scheme for pyramid-based broadcasting protocols and present the Stairway Channel Transition (SWCT) scheme. Compared to the existing schemes that are only designed for dedicated broadcasting protocols, our design possesses more flexibility, while it does not reduce the performance of the original protocols.

The huge computational complexity of motion estimation (ME) process of a standard video codec has resulted in numerous researches on ME VLSI architecture designs. Especially, the new features, variable-block-size (VBS) partitions and multiple-reference-frames (MRF), in the H.264/AVC bring new challenges and opportunities. Though many VLSI designs have been proposed to deal with the new VBS ME feature, there is still no efficient solution for reducing the MRF complexity without drably repeating the whole ME modules. In this paper, an efficient MRF architecture based on a VBS merging scheme is presented. Based on the previous merging scheme, the new architecture can support up to 16 reference frames with the same ME component requirements as a simple 16x16 fixed-block-size ME architecture pluses a few merging logics and five memory latch chains. The proposed architecture is pipelining designed to achieve fully hardware utilization, whereas using the least hardware cost with our previous proposed embedded merging scheme.

Layer streaming has received extensive attention due to the highly heterogeneous access to the Internet nowadays. In this paper, we propose a cooperative proxy framework, called layered chaining, for streaming layered videos efficiently. The framework can not only provide adaptive video quality to heterogeneous clients according to their available reception bandwidth but also support near-instantaneous playback service to a large number of clients by utilizing the resources available at proxy servers. Moreover, the system performance can be further improved via the cooperation of the proxies. The simulation results show that the layered chaining scheme achieves considerably fine performance in terms of reject rate, proxy buffer utilization, and server load.

The variable block size motion estimation (VBSME) technique can improve the coding efficiency greatly and has been adopted into the latest international video coding standard H.264/AVC. However, the VBSME technique introduces excessive computations comparing to fix block size ones. In H.264/AVC, the possible macroblock partition modes can have up to 259 different combinations, which make the design of an efficient VLSI architecture for H.264/AVC a challenging task. Many VLSI designs for the general motion estimation modules were presented in past decades, and some of them were also implemented as commercial products. Thereby, instead of developing a newly motion estimation module for H.264/AVC, this paper proposes an embedded merging scheme to extend the applicability of existing VLSI architectures. More specifically, the proposed embedded merging scheme only adds a few components into the existing VLSI architecture modules but can empower them to deal with the new H.264/AVC applications.

MPEG-4 FGS (Fine Granularity Scalability) has received tremendous attentions because it has ability to adapt to the network bandwidth variation. In this paper, we present a novel and effective bit-plane coding technique to further improve the coding efficiency of MPEG-4 FGS. The proposed approach reveals three superiorities to the MPEG-4 FGS based bit-plane variable-length coding (VLC): (1) better video quality in about 1.2 dB in terms of average PSNR, (2) less memory requirement, and (3) lower implementation complexity and power dissipation. Thus, it is well suitable for efficient hardware or software implementations.

Periodic broadcasting is known as an efficient technique for delivering popular videos by reducing bandwidth requirement for transmitting streaming video to simultaneous viewers. The channel transition problem is a noticed issue to be concerned about the variability of popularity of video and resource management in periodic broadcasting. In this paper, we approach a general seamless channel transition scheme for pyramid-based broadcasting protocols and present the stairway channel transition (SWCT) scheme. Compared to the existing schemes that are only designed for dedicated broadcasting protocols, our design possesses more flexibility, while it does not reduce the performance of the original protocols.

Content with rapid, moderate, and slow motion is frequently mixed together in real video sequences. Until now, no fast block-matching algorithm (FBMA), including the well-known three-step search (TSS), the block-based gradient descent search (BBGDS), and the diamond search (DS), can efficiently remove the temporal redundancy of sequences with wide range motion content. This paper proposes an adaptive FBMA, called A-TDB, to solve this problem. Based on the characteristics of a proposed predicted profit list, the A-TDB can adaptively switch search patterns among the TSS, DS, and BBGDS, according to the motion content. Experimental results reveal that the A-TDB successfully adopts the search patterns to remove the temporal redundancy of sequences with slow, moderate and rapid motion content.

By forwarding the server stream client by client, a chaining-based scheme is a good way to reduce the server streams for streaming applications in well-connected networks. In this paper, we prove that the minimum number of required server streams in such schemes is n-k+1, where n is the number of client requests and k is a value determined by client buffer sizes and the distribution of requests. In addition, we present an optimal chaining algorithm using a dynamic buffer allocation strategy. Compared to existing chaining schemes, our scheme not only utilizes the backward (basic chaining) and/or forward (adaptive chaining) buffer, but also exploits the buffers of other clients in order to extend the chain as much as possible. In this way, more clients can be chained together and served by the same server stream. Our simulation results show that the requirements of the server streams in the presented scheme are much lower those of existing chaining schemes. We also introduce mechanisms for handling VCR functions and fault exceptions in practical applications.

The fast block-matching algorithm (FBMA), includes the well-known three-step search (TSS), the block-based gradient descent search (BBGDS) and the diamond search (DS), have been developed for motion estimation in designing a video codec. In this paper, an adaptive FBMA, named A-TDB, to solve the block matching problem for varying motions is proposed. Based on the characteristics of a proposed predicted profit list, the A-TDB can adaptively switch the search patterns among the TSS, DS, and BBGDS according to the motion contents.

In this paper, we propose a novel coding dependency among video frames which supports efficient error resilience without adding any redundancy. Our approach is based upon reorganizing the regular GOP structure. The proposed scheme can effectively recover a lost frame and prevent the error propagation phenomenon. For a single frame loss, we guarantee that both of its next and previous frames still can be successfully decoded, thus we have sufficient temporal and spatial information to reconstruct the damaged frame. Our new coding structure even can recover successive lost frames. The experimental results showed that the video quality has a graceful degradation when the loss rate increases rapidly. Comparing with the conventional GOP, PSNR values can improve from 0.5 dB to 3 dB.

On the basis of the emerging peer-to-peer structure and the characteristics of user behavior, this paper proposes a scalable video delivery scheme, named P2PVD, for large scale video-on-demand application. In P2PVD, two types of orders are permitted: reserved and urgent orders. Reserved orders are encouraged with a lower price policy to smooth the network traffic and the server load. A delay-aware dynamic parallel transmission in the requesting peer is introduced to serve the reserved and urgent orders. The supplying peer is carefully designed based on three priority rules to increase the capacity of P2PVD. Experimental results indicate that P2PVD is scalable.

Periodic broadcasting is known as an efficient technique to support near video-on-demand services for delivering popular videos, since it can reduce the bandwidth requirement for transmitting streaming video to simultaneous viewers. The channel transition problem is an issue of concern regarding the variability of the popularity of a video in periodic broadcasting. We present a novel channel transition scheme over the fast broadcasting (FB) scheme. Our proposed scheme has less bandwidth waste than the existing seamless channel transition (SCT) scheme. In addition, no extra service delay and client buffer are needed in our scheme.

A simple and efficient motion-vector-based search engine supporting query by clip is presented for indexing and retrieving of videos. We propose a technique to filter and reconstruct noisy motion vectors to improve the fidelity of the motion activity. In addition to the motion features of intensity and direction, a new motion descriptor, named representative spectrum, extracted by a vector quantization expressing the spatial-temporal distribution of motion activity, is introduced for video indexing. A dynamic programming scheme is also utilized to measure the similarity of two videos based on the concept of common subsequence. Furthermore, a 2-step search of similar videos is employed to reduce the computational complexity. The experimental results indicate that the proposed search engine performs well and the obtained recall and precision values are also high enough.

In this article, we present a novel approach to support fast scan operations for video streaming applications. Our approach is based upon reshaping the ordinary linear encoded GOP (group of pictures) structure into a hierarchically encoded binary tree, along with a proximity-based approximation scheme. Our scheme can support forward and backward fast playback operations at any speed-up factor with few bandwidth requirements even for the normal speed playback.

The emerging H.264/AVC video coding standard takes 50% performance improvement than the H.263. One of the key successful factors is to employee the variable block size matching algorithm in the motion compensation stage. However, the highly computational complexity leads the codec become too complex and hard to implement in some real time applications. Again, large memory requirement to save the middle results limits its usage, too. In this paper, we proposed an embedded merging scheme for fast full search algorithm of H.264/AVC. The proposed scheme cannot only reduce the computation complexity but also provides a better way to be implemented in VLSI hardware.

The performance of streaming caches is not only affected by cache management but also determined by cache cooperation. If caches cooperate together, the desired video may be obtained from other caches thus reducing server load. However, such process increases network traffic between caches. It must be done carefully. This paper proposes a cooperative cache framework to automatically select appropriate cache sources and paths for various network environments. Simulation results demonstrate that the proposed framework is efficient and easy to implement for streaming caches.

We address serious video server load resulting from the VCR functionality, and the restructuring algorithm of frame dependencies is presented to reduce the server load and minimize the requirements of the network bandwidth. The requested frames are transmitted and decoded without sending any redundant data. Thus, even for the VCR operations with high speed factors, the server still sends data at normal transmission rate. The video server cost can significantly reduce as well.

Many fast block-matching algorithms (BMAs) reduce the computational complexity of motion estimation by sophisticatedly inspecting a subset of checking points, and stop only when all those checking points have been examined. This means that the searching process for each current block cannot be interrupted, even when it is performed in a software-based computation environment. Our main goal is to allow the searching process to stop once a specified amount of computation has been performed. A novel computation-aware scheme is proposed, which first dynamically determines the target amount of computation power allocated to a frame, and then allocates this to each block in a computation-distortion-optimized manner. We propose a rate-control-like procedure and a predicted computation-distortion benefit heuristic to realize this scheme. Conventional BMAs, such as full-search block matching, three-step search, new three-step search, four-step search, and diamond search, can be transformed into their corresponding computation-aware BMA versions. In our simulations, the resulting computation-aware BMAs not only exhibit higher efficiency than conventional BMAs, but also allow the motion estimation to terminate after any specified amount of computation has been performed (in units of checking points).

We present an optimal chain-code-like representation to code contour shapes; in addition, this representation can be easily extended to a scalable form which structures shape data as the base layer followed by two enhancement layers. A lossy coding scheme is also presented for low-bit-rate applications. Compared with the block-based CAE (context-based arithmetic encoding) method in MPEG-4 and DCC (differential chain coding) with an arithmetic coder, our method not only has a higher compression ratio with fewer computation steps, but also can be applied to layered transmission. The scalability achieved by our scheme can be recognized both spatially and quality-wise. Compared with other scalable shape coding methods, our scheme is simple but more efficient than progressive polygon encoding methods. In case of a base layer with distortion Dn=0.02, our scheme saves about 20-30% of the number of bits, that is, we have a smaller size base layer, which is important in layered transmission.

The purpose of the rate controller in a MPEG encoder is to allocate bit budget for each picture, and adjusts the quantization scale of each macroblock to control the actual used bits to close to the allocated bit budget for a picture. Multi-pass coding can allocate sufficient bit budget for each picture, but cannot be utilized in the real-time single-pass application. In the proposed algorithm, the complexity of the current picture can be easily obtained from the motion estimation, and therefore can allocate the bit budget for the picture more precisely to maintain a uniform visual quality from picture to picture. An initial quantization scale can also be estimated to increase the coding quality. The extremely simple structure of this framework can be easily implemented as a real-time video coding system by hardware as well as software.

Chaining is a promising technique in alleviating the network and the server load by serving numbers of clients in a single server stream. In this scheme, each client temporarily stores the ongoing media stream in the client buffer and forwards it to another client with adequate buffering delay to meet the next client playback time. Therefore, the clients request the same video program can be chained together if the client buffer is large enough to bridge clients' playback time. However, existing chaining schemes do not efficiently exploit the client buffer space. In this paper, we present an optimal chaining algorithm to fully utilize the client buffer space and hence minimize the required server streams. Our performance comparison demonstrates that the optimal chaining scheme significantly reduces the server load over the existing chaining schemes. More importantly, the proposed scheme can integrate the streaming proxy into the video chain, which makes the video chain more reliable and flexible in real systems. This paper also presents the prototype implementation of the optimal chaining based video-on-demand system.

Video-on-Demand (VoD) systems are attractive multimedia services over the Internet. However, conventional VoD systems can not serve many viewers simultaneously because such large-scale services require considerable server load and network bandwidth. This study proposes a cooperative proxy scheme, consisting of a streaming cache and a query protocol revised from Internet Cache Protocol (ICP), to improve performance of large-scale VoD systems. The streaming cache we proposed attempts to serve the most requests with slightly computation overhead In addition, our query protocol further extends service scalability by satisfying requests "as far as possible", although Web proxies prefer "as near as possible". Simulation results demonstrate that our proxy scheme is efficient especially in large-scale VoD systems.

This paper presents an integrated systolic array design for implementing full-search block matching, 2-D discrete wavelet transform, and full-search vector quantization on the same VLSI architecture. The above three functions are prime essential but with a large amount of computation in video compression. To meet real-time requirements, many systolic arrays are designed for individually performing each of them. In fact, these functions contain the similar computational procedure. The matrix-vector product forms of them are quite similar. In this paper, by carefully extracting the common computation component, an integrated systolic array design that can perform the above three functions is presented. A utilization of 100% to 97% is achieved for executing full-search block matching and full-search vector quantization. When performing the 2-D discrete wavelet transform, the utilization is about 32%. The proposed integrated architecture has lower hardware cost and has a a regular hardware structure. It befits the VLSI implementation for video compression.

We propose a complexity-adaptive fast block matching algorithm design strategy that allows the user to terminate the algorithm at any target computational complexity. Two complexity-adaptive techniques, frame level complexity allocation and block level complexity allocation, are developed to approach the global complexity-distortion optimization A buffer control strategy is proposed to dynamically adjust the target complexity of one frame. The predictive complexity-distortion benefit list (PCDB list) technique is employed to allocate the target complexity into each block. By these techniques, we modify the full-search block matching, three-step search, new three-step search, and four-step search to the complexity-adaptive algorithms. Experimental results show that the complexity-adaptive algorithms could achieve better performance than traditional fixed algorithms from the viewpoint of complexity-distoftion optimization.

The on-demand multicast [1] is a novel scheme to reduce the video delivery cost for the streaming video applications. Unlike the conventional multicast, this scheme enables the transmission of the multicast data to multiple recipients at distinct times. This property is important for the streaming video applications since the users usually access the video program at different times. To deliver the same multicast data to the recipients at distinct times, the on-demand multicast scheme temporarily caches a sliding window of the incoming stream on a router (or a proxy) and then forwards it on different links at distinct times to generate timevariant outgoing streams. By carefully scheduling the departure time on each router's outgoing streams, a video stream can be distributed to the recipients at their expected times. Based on this scheme, this paper presents three routing algorithms on an asymmetric transmission network model, such as cable systems and ADSL systems. The simulation results indicate that our algorithm offers an outstanding performance in reducing the number of multicast streams and the network bandwidth. In addition, our simulation results are valuable to plan the system resources when deploying the video-on-demand systems.

In this paper, we propose a novel fast block matching algorithm design strategy based on the complexity-distortion optimization. The goal of our design is to achieve the maximum image quality under a target computational complexity and to provide a flexible fast block matching algorithm that allows user to terminate algorithm at any target computational complexity. Based on the proposed predictive complexity-distortion benefit list technique, which is employed to predict the motion compensation benefit, we modify the full-search block matching, three-step search, new three-step search, and four-step search to the flexible algorithm. Experimental results show that the flexible algorithms could achieve better performance than traditional fixed complexity algorithms from the viewpoint of complexity-distortion optimization.

Summary form only given. Region-based fractal image compression (Chang et al., 1997) is an attractive variation of fractal image compression algorithm. By segmenting an image into variable sizes of quadtree blocks and then merging these blocks into regions, this algorithm has the potential to encode a still image with a very low bit rate. However, highly visible artifacts become annoying when the coding bit rate is low. A large number of studies have been done in the literature to improve the reconstructed image quality at low bit rates. In this paper, an adaptive image enhancement algorithm for region-based fractal image compression is proposed. By utilizing an algorithm to determine which pixels have to be smoothed, then applying different smoothing filters for various image areas, the proposed algorithm can significantly eliminate the annoying blocking artifacts for images coded with low bit rate.

Several low bit-rate still-image compression methods have been presented, such as SPHIT, hybrid VQ, and the Wu-Chen (see Proc. IEEE ICASSP, 1997) method. In particular, the image "Lena" can be compressed using less than 0.15 bpp at 31.4 dB or higher. These methods exercise the analysis techniques (wavelet or subband) before distributing the bit rate to each piece of an image, thus the dilemma between bit rate and distortion can be solved. In this paper, we propose a simple but comparable method that adopts the technique of side match VQ only. The side match vector quantization (SMVQ) is an effective VQ coding scheme at low bit-rate. The conventional side match (two-sided) VQ utilizes the codeword information of two neighboring blocks to predict the state codebook of an input vector. We propose a hierarchical three-sided side match finite-state vector quantization (HTSMVQ) method that can: (1) make the state codebook size as small as possible-the size is reduced to one if the prediction can perform perfectly; (2) improve the prediction quality for edge blocks; and (3) regularly refresh the codewords to alleviate the error propagation of side match. In the simulation results, the image "Lena" can be coded with a PSNR 34.682 dB at 0.25 bpp. It is better than SPIHT, EZW, FSSQ and hybrid VQ with 34.1, 33.17, 33.1, and 33.7 dB, respectively. At a bit rate lower than 0.15 bpp, only the enhanced version of EZW performs better than our method, at about 0.14 dB.

Let G be an undirected graph and T be a spanning tree of G. In this paper, an efficient parallel algorithm is proposed for determining whether T is an unordered depth-first search tree of G. The proposed algorithm runs in O(m/p+log m) time using p processors on the EREW PRAM, where m is the number of edges contained in G. It is cost-optimal and achieves linear speedup.

Multicast communications is one of the critical techniques to enhance the video-on-demand (VOD) service scale by sharing the communication bandwidth. However, in the typical multicast communication, all receivers are expected to access the same multicast stream at approximately the same time. Therefore, only few customers can be served in the same multicast stream and additional multicast streams are required since most requests issued at different time. We propose a new multicast routing scheme to relax this time constraint, i.e. to allow the customers accessing the same multicast stream at various time. We call this new communications, buffered multicast communications. Furthermore, this type of services can be simply implemented by buffering the incoming streams on the intermediate routing nodes in a multicast tree. Based on this buffering technique, we present two buffered multicast routing algorithms. In addition, our simulation shows that the buffered multicast routing scheme tremendously reduces the transmission cost on the VOD systems. In addition, given the system resources, we derive a formula to accurately estimate the required multicast streams.

Several effective low bit rate still image compression methods have been presented in the past years, such as SPHIT, hybrid VQ, and the Wu and Chen method (see Proc. IEEE ICASSP, 1977). These methods exercise the analysis techniques (wavelet or subband) before distributing the bit rate to each piece of image, thus the tradeoff between bit rate and distortion can be resolved. We propose a simple but comparable method that adopts the technique of side match VQ only. Side match vector quantization (SMVQ) is an efficient VQ coding scheme for low bit rate coding. Conventional side match (two-sided) utilizes the codeword information of two neighboring blocks to predict the state codebook of an input vector. We propose a hierarchical three-sided side match finite-state vector quantization (HTSMVQ) method that can (1) make the state codebook size as small as possible, it can be reduced to 1 if the prediction is performed perfectly; (2) improve the prediction quality for edge blocks; and (3) regularly refresh the codewords to alleviate the error propagation of side match. In the simulation results, the image "Lena" can be coded with a PSNR 34.682 dB at 0.25 bpp. It is better than SPIHT, EZW, FSSQ and hybrid VQ with 34.1, 33.17, 33.1 and 33.7 dB, respectively. At a bit rate lower than 0.15 bpp, only the enhanced versions of EZW perform better than our method by about 0.14 dB.

Fractal image coding is a novel technique for still image compression. A low bit rate region-based fractal image compression algorithm is proposed and several techniques are included as follows. First, we improve the performance of quadtree segmentation by an adaptive threshold. Then, a merging scheme is employed to the resulting quadtree segmentation that combines several similar blocks into a small number of regions. We also provide a quadtree-based segmented chain code to efficiently record the contours of the regions. The experimental results show that the proposed scheme has the lowest bit rate among the existing schemes at the same level of image quality.

This paper presents a new buffer control strategy that regulates the coded bit stream generated by MPEG video codec so that it can be transmitted robustly. This buffer control strategy is regarded as regulating the compressed bit stream to transmit with (pseudo) constant bit rate (CBR) through a fixed rate channel. It dynamically adjusts the quantizer scale for each frame under the consideration of the steady level of coding quality, the allocated bandwidth of transmission, the level of buffer occupancy, as well as the scene change. In the simulations, this strategy is implemented on MPEG coding algorithm and produces constant rate bit stream no matter what bandwidth is allocated or when the scene change occurs. Besides, the objective quality [in peak signal-to-noise ratio (PSNR)] of the proposed strategy is 1.5 dB more than that of TM5 and is almost the same as the results coded without buffer control. In addition, it always holds the smooth property.

In this correspondence, a mean residual vector quantizer (MRVQ) is superimposed on the motion estimator for improving the intraframe coding quality of MPEG. The proposed scheme performs an MRVQ before executing the discrete cosine transformation (DCT) for the purpose of curing the DCT intrinsic trouble of blocking effect at low bit rate.

In recent years, the variable block size (VBS) motion estimation technique has been widely employed to improve the performance of the block matching algorithm (BMA). In VBS, the block size is varied according to the type of motion. The VBS is known to be very efficient for areas containing complex motions. But, it requires a large amount of computation. The computation required is 2 or 5 times compared with the full search BMA. In this paper, a new VBS motion estimation algorithm, called the classified variable block size (CVBS), is proposed to overcome this problem. The algorithm classifies the input blocks into 3 categories: the background, the shade-motion, and the edge-motion. According the characteristics of the classified blocks, various motion estimation techniques are then used to improve the coding performance. The performance of VBS and CVBS under the coding efficiency is investigated. It is shown that the CVBS algorithm requires about 1/6 to 1/10 computations needed by the conventional VBS algorithm.>

Isomorphism relations are utilized to analyze the Hopfield associative memory. When the number of fundamental memories m=/<3, it is proved that two Hopfield associative memories are isomorphic if they have the same mutual distances between the fundamental memories. The number of stable states and the synchronous convergence time of a Hopfield associative memory are shown to be less than or equal to 2 to the power 2(m-1) and 4 to the power 2(m-1), respectively, where m>/=1.

Finite state vector quantization (FSVQ) has been proven during recent years to be a high quality and low bit rate coding scheme. A FSVQ has achieved the efficiency of a small codebook (the state codebook) VQ while maintaining the quality of a large codebook (the master codebook) VQ. However, the large master codebook has become a primary limitation of FSVQ if the implementation is carefully taken into account. A large amount of memory would be required in storing the master codebook and also much effort would be spent in maintaining the state codebook if the master codebook became too large. This problem could be partially solved by the mean/residual technique (MRVQ). That is, the block means and the residual vectors would be separately coded. A new hybrid coding scheme called the finite state residual vector quantization (FSRVQ) is proposed in this paper for the sake of utilizing both advantage in FSVQ and MRVQ. The codewords in FSRVQ were designed by removing the block means so as to reduce the codebook size. The block means were predicted by the neighboring blocks to reduce the bit rate. Additionally, the predicted means were added to the residual vectors so that the state codebooks could be generated entirely. The performance of FSRVQ was indicated from the experimental results to be better than that of both ordinary FSVQ and RMVQ uniformly.

A coding algorithm must have the ability to adapt to changing image characteristics for image sequences. An adaptive finite-state vector quantization (FSVQ) in which the bit rate and the encoding time can be reduced is described. In order to improve the image quality and avoid producing a wrong state for an input vector, a threshold is used in FSVQ to decide whether to switch to a full searching VQ. The codebook is conditionally replenished according to a distortion threshold at a later time to reflect the local statistics of the current frame. After the codebook is replenished, one can quickly reconstruct the state codebooks of FSVQ using the state codebook selection algorithm. In the experiments, the improvement over the static SMVQ is up to 2.40 dB at nearly the same bit rate and the encoding time is only one-ninth the time required by the static SMVQ. Moreover, the improvement over the static VQ is up to 2.91 dB, and the encoding time is only three-fifths the time required by the static VQ for the image sequence 'Claire'.>

A new adaptive tree-structured vector quantization (adaptive TSVQ) with multipath searching is described. The structure of the codebook tree is reorganized at an update interval, without requiring any transmission of side information. The 1-path tree searching algorithm is the simple way to find the closest codeword in TSVQ. But the disadvantage of 1-path searching is that the selected codeworks are not, in general, closest to the input vectors. Hence, the authors propose the multipath searching algorithm to improve the image quality. In an experiment, the improvement over the fixed TSVQ at the same bit rate is up to 2.03 dB when the number of the leaves in the codebook tree is 256 and 4-path searching is applied.>

Relations of stable states between different Hopfield neural nets are shown, and upper bounds to their transient lengths are given. The proofs of the results lie in examining the sinks and the maximum path length of the state transition graph. IfWis the weight matrix of a Hopfield associative memory determined frommreference patterns, the experiments showed thatPmax(G(W,Θ)) is of order O(mn) andTord(GB(W,Θ))=2 whenm=1 or 2, for alln⩾3, wherenis the size of the net and Θ is zero factor

An algorithm known as optimal channel routing (OCR) is proposed which finds an optimal solution for the channel routing problem in VLSI design. The algorithm is an A* algorithm with good heuristics and dominance rules for terminating unnecessary nodes in the searching tree. Experimental results, agreeing with theoretical analysis, show that it behaves quite well in average cases. An optimal solution is obtained for the Deutsch difficult case in 5.5-min-CPU time after the algorithm is implemented in Pascal and run on a VAX 11/750 computer.>