Rate distortion (RD) optimization, which is used to decide the best coding mode of a macroblock (MB) in H.264/AVC video coding standard, is a very efficient technique to improve coding performance. On the other hand, this RD optimization process also incurs a considerable complexity increase of the encoder. To reduce computational cost of RD optimization, fast bit estimation method can be adopted to avoid entropy coding computation during the mode decision process of H.264/AVC encoding [1] [2]. However, previous works [1][2] are all for CAVLC (Context Based Adaptive Variable Length Coding) based RD optimization process and are not accurate for CABAC (Context Based Adaptive Binary Arithmetic Coding) based RD optimization process. As known, compared with CAVLC, CABAC entropy coding provides higher coding efficiency at average bit rate saving of 9%-14% [3]. Hence, it is desirable to find a fast bit estimation method that is suitable for RD optimization with CABAC entropy coding. In this paper, we present such kind of fast bit estimation method. The experiments show that the proposed method can reduce around 30% of the RD optimization time averagely while maintaining the similar coding performance comparing to that of original H.264/AVC with RD optimization enabled.

Though rate control is not normalized in any video coding standards, it plays an important role in video coding/communication area. Rate control algorithms aim to achieve perceivable video quality in video communication applications under some real-world constraints, such as bandwidth, delay, buffer sizes, etc.

IP-multicast is a bandwidth efficient transmission mechanism for group communications. Reliability in IP-multicast, however, poses a set of significant challenges. To address the reliability and scalability issues in IP-multicast, this paper proposes a novel, highly distributed, and lightweight overlay peer-to-peer retransmission architecture that exploits path-diversity by taking advantages of both IP-multicast and an overlay network. An approach that leverages both disjoint-path-finding and periodic selective probing to take into account peer's recent packet loss probability, retransmission delay and recent retransmission success rate is proposed to effectively construct an efficient and dynamic overlay retransmission network. We show that the proposed path diversity overlay retransmission architecture has the potential to significantly reduce the retransmission delay, improve the reliability, playback quality, and scalability of IP-multicast based multimedia applications. Given a deployed IP-multicast network, the proposed overlay retransmission architecture is practical, scalable, and easy to deploy, requiring no change to the existing network infrastructure.

H.264 coding standard offers several coding modes, including intra mode and inter prediction mode with different block sizes. Since intra mode does not need reference from previous frames, in packet loss environment, intra mode can be a good choice to stop error propagation and enhance decoded video quality. To achieve best coding efficiency, such best mode decision is often made upon optimizing rate distortion (RD) constraints. Unfortunately, this RD optimization process incurs a considerable complexity increase of the encoder. To solve the problem, we propose a fast motion estimation and mode decision algorithm for H.264 video coding in packet loss environment. Unlike previous algorithms, our method takes advantage of channel distortion estimation as assistance to decide if an early termination of existing coding mode choices is necessary. Experiment results show that, compared with error resilient coding method proposed in the work of Stockhammer et al. (2002) and Yuan Zhang et al. (2004), the proposed algorithm can enhance speed up to 10 times while maintaining similar average picture quality.

This paper introduces and analyzes a game theoretic approach to routing of multiple real-time multimedia streams through multiple shared links of different link quality metrics. The objective of the proposed method is to achieve fairness and bandwidth efficiency for each stream in the utilization of high quality links. Traditionally this task is managed through pricing and service agreement, and the solutions are frequently sub-optimal. In this paper, the problem of path link sharing among multiple streams is formulated as a non-corporative QoS game. Each stream is a player, whose strategy space is the percentage of utilization of the high quality links. A unique payoff function is introduced, and each player attempts to maximize its expected payoff independently. The existence and uniqueness of a Nash equilibrium (NE) is analyzed. Numerical analysis and simulations are conducted, and the results demonstrate that the NE solutions is able to maximize the successful transmission rate of individual streams with fair link usage.

In this paper, we show how disjoint multipath QoS routing (DMQR) can cooperate with importance-based video layering to achieve reliable video transmission. DMQR algorithm dynamically searches for multiple paths for a flow in an overlay network. The multiple paths selected are mutually disjoint w.r.t. bottleneck links, each of which is the shortest among the widest ones. An importance-based video layering and transmission would be most effective to cooperate with DMQR to deliver satisfactory video quality. The video layering will produce a base layer and a bit-plane-wise enhancement layer. The base layer consists of some vital information, sign bit plane and a few significant bit planes; its packets are most important, will be fully FEC protected and duplicated over multipath selected by DMQR. The enhancement layer includes the rest bit planes; its packets will be FEC protected partially and distributed over multiple paths. Simulation results demonstrate that both layers can be transmitted with improved bandwidth efficiency and end-to-end path reliability with shorter one way delay and jitter.

Exploiting directional antenna technology in wireless networks has become an attractive option because of the potential capacity increase through spatial reuse. Such development apparently has profound impact to wireless multimedia applications. While the advantages of directional transmission in single hop networks (e.g. WLANs and cellular systems) have been evident, it has also been recognized that multi hop directional networks may suffer long transmission delays and frequent link breakages if conventional routing protocols (e.g. AODV and DSR) are used. This is mainly due to the unique feature of directional transmission commonly known as "node deafness". To address this problem, we propose a multi-path routing scheme which focuses more on minimizing per-hop delays instead of traditional route length. We further propose a differentiated service (DiffServ) framework for layered video transport over multi hop directional network using QoS aware multi-path routing as well as class based queuing (CBQ). Both network layer and application layer simulation results are presented to demonstrate the effectiveness of the proposed video transport scheme over directional networks

It is known that video quality fluctuation plays a major negative role on visual perception. In a paper by Lan et al. (2004), we derived close-form approximations to mimic the highly nonlinear rate-distortion (R-D) and distortion-quantization (P-Q) relationships. Using the two close forms, we can allocate the bit rate at the frame-level rather easily so long as a target distortion for each frame is established. In the paper (Lan et al., 2004), we set up the target distortion at each frame using a hypothesis that maintaining constant distortion across frames would ease video quality fluctuation. The extensive experiments showed the constant-distortion bit allocation (CDBA) scheme proposed (Lan et al., 2004) delivered much smoother video quality than the conventional constant bit allocation (CBA) scheme. However, maintaining constant distortion is about the same as maintaining constant peak-signal-to-noise-ratio (PSNR). In scene changes, the picture energy often dramatically changes that could generate significantly different signal-to-noise-ratio (SNR) if constant distortion or constant PSNR is maintained. Although computationally more complex, SNR does represent a more objective measure than PSNR in assessment of picture/video quality. In the paper, we consolidate a constant SNR bit allocation (CSNRBA) scheme that attempts to maintain constant SNR throughout the video frames. Extensive experiments show that the CSNRBA scheme provides smooth video quality in terms of natural colors and sharp objects and silhouettes significantly better than both the CBA and CDBA schemes

The principle and theory of SLCCA (significance linked connected component analysis) coding technology has been further studied in this paper. To enhance SLCCA, we introduce distance-first significance-linked connected component analysis and a combined extension and arithmetic code for symbol sequence. An enhanced SLCCA coding system is constructed. Its PSNR performance is compared with both SLCCA and JPEG2000 on numerous 512times512 gray-scale natural images at three different bit rates, i.e., 0.3, 0.6 and 0.9 bits per pixel. On average, SLCCA+ is superior to SLCCA by 0.45 dB and significantly outperforms JPEG2000 by 3.69 dB. Detailed algorithm and further improvement will be given in a separate paper

Quality fluctuation has a major negative effect on perceptive video quality. In [1], we derived accurate approximations in close-form for the highly nonlinear rate-distortion (R-D) and distortion-quantization (D-Q) relationships, all at the frame-level. Based on the two close forms, we can allocate the bit rate at the frame-level rather easily as far as a target distortion for each frame could be established. In [1], a target distortion was set up for each frame based on a hypothesis that maintaining constant distortion over frames would boast video quality smoothing and extensive experiments showed the constant-distortion bit allocation (CDBA) scheme significantly outperformed the popular constant bit allocation (CBA) scheme in terms of delivered video quality. Maintaining constant distortion is no different from maintaining constant Peak-signal-to-Noise-Ratio (PSNR). In scene changes, however, the picture energy often dramatically changes, producing significantly different Signal-to-Noise-Ratio (SNR) if constant distortion or constant PSNR is maintained. Although computationally more complex, SNR represents a more objective measure than PSNR in assessing picture/video quality. In the paper, an SNR-based bit allocation scheme is developed for video quality smoothing. The algorithm uses a single pass and attempts to maintain constant SNR at the frame level throughout the video sequence. Experimental results on all testing video sequences show that the proposed CSNRBA scheme provides smooth video quality in terms of natural color and sharp objects and silhouette significantly better than both the CBA and CDBA schemes.

Network friendly media security refers to the security technologies that are specifically designed to cope with existing and future multimedia networking infrastructures and technologies so as to ease the deployment and maintain or improve the quality of service performance of multimedia applications. It is especially useful for streaming and mobile multimedia applications where content adaptation is a necessity. In this paper, we analyze the various motivations behind network-friendly security solutions, review some of the most recent approaches, discuss some open issues, and suggest some potential solutions.

Quality fluctuation has a major negative effect on subjective video quality. A desirable single-pass frame-level constant-distortion bit allocation scheme is proposed in the paper for smooth video quality throughout the video sequence. The average distortion of previous coded frames is taken as the target distortion for the current frame. According to the linear rate control algorithm, the distortion and rate are exponential and linear function of the number of zero coefficients, respectively. Based on the target distortion and the distribution of the absolute DCT coefficients, we then derive the closed-form formulas for estimating the number of zero coefficients and the slope /spl theta/ in the linear rate control function as well as the bit budget for the current frame. Experimental results show that the proposed constant-distortion (but variable rate) bit allocation scheme provides much smoother video quality on all testing video sequences than constant bit allocation scheme.

In 1997, we published a high performance scalable bit-rate-oriented wavelet image codec, significance linked connected component analysis (SLCCA). In term of coding efficiency, SLCCA outperforms EZW, SPHIT and JPEG2000, which are each an embedded image codec. SLCCA is optimized for any given bit rate. Although scalable, its coded bit stream is not fully embedded. In the paper, we provide an embedded SLCCA, which improves our previous work on embedded SLCCA. Like, we define a base layer and an enhancement layer for an image. The base layer encoded by SLCCA provides an acceptable image quality while achieving high coding efficiency and scalability. The enhancement layer provides more elaborate bit-rate adaptive granular picture quality enhancement for embedded image coding. The peak signal to noise ratio (PSNR) of the new embedded SLCCA (called ESLCCA) consistently outperforms JPEG2000 that can be as high as 0.5 dB.

The innovation and development brought by the new technologies in our information era have started to appear in education. Distance learning has become a core educational strategy around the world, with extending to a broad cross-section of online universities and virtual universities. The Internet is providing mechanisms for fundamental changes in the way people learn. Video conferencing, Web conferencing and collaboration provide interactive, real-time multimedia communications for distance learning. We review the evolution of technologies and tools in distance learning, and discuss the current state of distance learning, with a focus on the tools or technologies on the Internet available for distance learning. Then we present a newly developed interactive multimedia educational system. The system is based on a new compression algorithm with low bit-rate, software-implemented video codec to achieve real-time, multicast transport. Finally we provide experimental results of this system.

In real-time video communications, the rate control strategies must be utilized to satisfy the end-to-end delay and prevent the encoding buffer from over/underflow. In other words, to acquire the best possible video quality with a minimal quality variation in the playback video, an accurate rate-distortion (R-D) model of the video source is critical in optimizing the bit allocation for video coding. In the paper, an exponential functions based R-D model is proposed for intra-coded frames in video coding. Numerous experiments have consistently shown that the proposed model outperforms other popular R-D models in terms of both the estimation accuracy and computation complexity, making it suitable for rate control in real-time video coding.

Multimedia distribution over the Internet is becoming increasingly popular. A novel framework for Internet video streaming is proposed. For video compression, our previously developed three-dimensional significance-linked connected component analysis (3D-SLCCA) codec is applied. 3D-SLCCA provides high coding efficiency, multiresolution video representation, transmission error resilience, and low computational complexity. For audio coding, the GSM standard is used. For error control, retransmission and error concealment are jointly applied. Multiresolution-multicast transmission is implemented by assigning different multicast group addresses to different video layers. Thus each receiver subscribes to the maximum number of layers that both its hardware resource and network capability can handle. By using a hierarchically structured multicast tree, each node is responsible for caching packets, collecting NACK packets, and sending repair packets. This not only significantly reduces the latency, but also efficiently solves the "ACK implosion" problem. As opposed to data transmission, reliable multicast is not required by the network infrastructure. Based on timing constraint and importance of lost packets, each receiver decides whether to request retransmission or apply error concealment. Finally, synchronization is accomplished by using the timestamp mechanism of RTP.

A novel mobile communications system is proposed, which provides not only effective but also efficient video access for mobile users when communicating over low-bandwidth error-prone wireless links. The middleware implemented by a mobile proxy server at the mobile support station is designed for the seamless integration of mobile users with video servers, so the specific details of the underlying protocols and source/channel coding techniques are hidden to both the video server and mobile client. Based on the concept of application-level framing, the application (video codec in our case) plays a significant role in network communications that most of functionalities of the system are implemented as part of the application. As such, at the application layer, adaptive source- and channel-coding techniques are developed to jointly provide the user with the highest possible video quality. For efficient source coding, our high-performance low-complexity video-coding algorithm called a 3-D significance-linked connected component analysis (3D-SLCCA) is chosen. Due to its high robustness against channel-error propagation, 3D-SLCCA is well suited for wireless environments. For error-resilient channel coding, a multilayer transmission error-control mechanism is developed. Since there is no additional requirement imposed on either the mobile client or the video server, mobile users interact with the server in exactly the same way as stationary users. Extensive computer experiments demonstrate the effectiveness of the proposed system.

In the paper, three error resilient coding schemes are proposed and integrated with our previously developed high performance significance-linked connected component analysis (SLCCA) wavelet image codec. First, the cross-scale significance-links that exploit cross-scale dependency are reduced thereby error resilience of the source codec is increased. Second, hierarchical resynchronization is applied, i.e., resynchronization markers are inserted in the bitstream after each bit-plane and possibly per each scale and/or subband. Third, bit-plane-wise unequal error protection is applied, with the parity bits being exponentially distributed among bit-planes. Extensive performance evaluation demonstrates that the proposed joint source-channel coding algorithm for image transmission is not only highly efficient but also highly robust.

Error resilient coding strategies are proposed and integrated with the high performance significance-linked connected component analysis (SLCCA) wavelet image codec. First, the source bitstream is packetized so that the error propagation within the bitstream is minimized. Second, hierarchical resynchronization is applied, i.e., resynchronization markers are inserted in the bitstream after each bit-plane and possibly per each scale or subband. Third, the significance-links that exploit the cross-scale dependency of wavelet coefficients are reduced. Finally, bit-plane-wise unequal error protection is applied, with the parity bits being exponentially distributed among bit-planes. Extensive performance evaluation over a binary symmetric channel demonstrates the high error resilience and efficiency of the integrated joint source-channel coding strategies with the SLCCA source codec.

In the paper, three error resilient coding schemes are proposed and integrated with our previously developed high performance significance-linked connected component analysis (SLCCA) wavelet image codec. First, the cross-scale significance-links that exploit cross-scale dependency are reduced thereby error resilience of the source codec is increased. Second, hierarchical resynchronization is applied, i.e., resynchronization markers are inserted in the bitstream after each bit-plane and possibly per each scale and/or subband. Third, bit-plane-wise unequal error protection is applied, with the parity bits being exponentially distributed among bit-planes, Extensive performance evaluation demonstrates that the proposed joint source-channel coding algorithm for image transmission is not only highly efficient but also highly robust.

Multimedia distribution over the Internet is becoming increasingly popular. Since the Internet was designed for computer data communication, satisfying the different characteristics and requirements of multimedia streams poses significant challenges. For effective and efficient Internet video streaming, many issues (e.g., multiresolution representation, multicast transmission, error control, synchronization, etc.) must be addressed. In the paper, a novel framework for Internet video streaming is proposed. For video compression, our previously developed three-dimensional significance-linked connected component analysis (3D-SLCCA) codec is applied. 3D-SLCCA provides high coding efficiency, multiresolution video representation, transmission error resilience, and low computational complexity. For audio coding, the GSM standard is used. For error control, retransmission and error concealment are jointly applied. Multiresolution-multicast transmission is implemented by assigning different multicast group addresses to different video layers. Thus each receiver subscribes to the maximum number of layers that both its hardware resource and network capability can handle. By using hierarchically structured multicast tree, each node is responsible for caching packets, collecting NACK packets, and sending repair packets. This not only significantly reduces the latency, but also efficiently solves the "ACK implosion" problem. As opposed to data transmission, reliable multicast is not required by the network infrastructure. Based on timing constraint and the importance of lost packets, each receiver decides whether to request retransmission or apply error concealment. Finally, synchronization is accomplished by using the timestamp mechanism of RTP. When the network does not support multicasting, proxy servers implemented on workstations can be used to perform similar functionalities.

A highly robust channel coding scheme to be seamlessly integrated into our previously developed high performance wavelet based significance-linked connected component analysis (SLCCA) image coding technique is proposed. The SLCCA source coding algorithm is slightly modified to enable synchronization after each bit-plane. Thus even after uncorrectable errors, the decoding can be continued at the next refinement level. An unequal error protection scheme is also developed by using Reed-Solomon codes. The proposed scheme outperforms P.G. Sherwood and K. Zeger's technique (1997; 1998) by 0.66 dB on average for the "Lena" image in peak signal-to-noise ratio. Furthermore, the proposed codec has very low computational complexity, well applicable for the power constrained mobile scenario.

Based on our previously developed significance-linked connected component analysis (SLCCA) data organization and representation strategy, two three-dimensional wavelet video coding techniques are proposed covering a wide range of applications areas. In three-dimensional SLCCA (3D-SLCCA), both the wavelet decomposition and SLCCA data organization and representation strategy are extended to 3-D case. In Haar wavelet SLCCA (N-SLCCA), the SLCCA data organization and representation strategy is separately applied on each of the two temporal subbands obtained by Haar wavelet-based temporal decomposition. The developed codecs not only provide comparable or superior performance in comparison to state-of-the-art video coding standards, but also have several desirable properties such as scalability, low computational complexity, and error resilience, well suited for networked video communications.

A novel system providing effective and efficient access to video archives for mobile users communicating over low-bandwidth error-prone wireless links is proposed. The developed system has three components. First, the middleware, implemented as mobile proxy server located at the mobile support station, is chosen for the seamless integration of both mobile users and video servers by hiding the specific details of the underlying system. Second, for efficient video transmission, our 3D significant-linked connected-component analysis video codec, which is well-suited for wireless environments, is used. Finally, multilayer transmission error control mechanism is applied to cope with channel errors. As a result, no additional requirements are imposed on the mobile client and video server, so that mobile users interact with the server in exactly the same way as stationary users, and all they experience are better picture quality, less jerky video and shorter delays.

A novel middleware-based system providing effective and efficient video access for mobile users communicating over low bandwidth error-prone wireless links is proposed. The middleware, implemented as mobile proxy server located at the mobile support station, is chosen for the seamless integration of mobile users and video servers by hiding the specific details of the underlying system. For efficient video transmission, our three-dimensional significant-linked connected component analysis video codec is well suited for wireless environments, is used. To cope with wireless transmission errors, we propose an multilayer error control mechanism, which incorporates synchronization, unequal forward error protection, and retransmission. As a result, mobile users experience better picture quality, less jerky video, and shorter delays when accessing video files.

A novel hybrid wavelet video coding algorithm termed video significance-linked connected component analysis (VSLCCA) is developed for very low bit-rate applications. In the proposed VSLCCA codec, first, fine-tuned motion estimation based on the H.263 Recommendation is developed to reduce temporal redundancy, and exhaustive overlapped block motion compensation is utilized to ensure coherency in motion compensated error frames. Second, the wavelet transform is applied to each coherent motion compensated error frame to attain global energy compaction. Third, significant fields of wavelet-transformed error frames are organized and represented as significance-linked connected components so that both the within-subband clustering and the cross-scale dependency are exploited. Last, the horizontal and vertical components of motion vectors are encoded separately using adaptive arithmetic coding while significant wavelet coefficients are encoded in bit-plane order by using high order Markov source modeling and adaptive arithmetic coding. Experimental results on eight standard MPEG-4 test sequences show that for intraframe coding, on average the proposed codec exceeds H.263 and ZTE (zero-tree entropy) in peak signal-to-noise ratio by as much as 2.07 and 1.38 dB at 28 kbit/s, respectively. For entire sequence coding, VSLCCA is superior to H.263 and ZTE by 0.35 and 0.71 dB on average, respectively.

Recent success in wavelet image coding is mainly attributed to a recognition of the importance of data organization and representation. There have been several very competitive wavelet coders developed, namely, Shapiro's (1993) embedded zerotree wavelets (EZW), Servetto et al.'s (1995) morphological representation of wavelet data (MRWD), and Said and Pearlman's (see IEEE Trans. Circuits Syst. Video Technol., vol.6, p.245-50, 1996) set partitioning in hierarchical trees (SPIHT). We develop a novel wavelet image coder called significance-linked connected component analysis (SLCCA) of wavelet coefficients that extends MRWD by exploiting both within-subband clustering of significant coefficients and cross-subband dependency in significant fields. Extensive computer experiments on both natural and texture images show convincingly that the proposed SLCCA outperforms EZW, MRWD, and SPIHT. For example, for the Barbara image, at 0.25 b/pixel, SLCCA outperforms EZW, MRWD, and SPIHT by 1.41 dB, 0.32 dB, and 0.60 dB in PSNR, respectively. It is also observed that SLCCA works extremely well for images with a large portion of texture. For eight typical 256x256 grayscale texture images compressed at 0.40 b/pixel, SLCCA outperforms SPIHT by 0.16 dB-0.63 dB in PSNR. This performance is achieved without using any optimal bit allocation procedure. Thus both the encoding and decoding procedures are fast.

Perhaps, Sarnoff Corporation's zerotree entropy (ZTE) coder is the most successful wavelet video coder published so far which exploits the statistical properties of wavelet-transformed images by utilizing novel data representation and organization strategies. A high performance hybrid video coding algorithm termed video significance-linked connected component analysis (VSLCCA) is developed. It is quite encouraging that, at least empirically convinced, the wavelet transform with aids of those published innovative data representation and organization methods can be an invaluable asset in video coding if motion-compensated error frames are coherent. In VSLCCA, time domain motion estimation followed by exhaustive overlapped block motion compensation is utilized to ensure coherency, and then wavelet transform is applied to each error frame with significant wavelet coefficients being encoded by highly efficient SLCCA technique. Experimental results on standard MPEG-4 test sequences show that VSLCCA is superior to H.263 and ZTE by 0.48 dB and 0.77 dB on average, respectively.

An automatic spatio-temporal video sequence segmentation algorithm is proposed. To address this very difficult computer vision problem, several novel algorithms have been developed which use both spatial and temporal information. First, a novel temporal segmentation algorithm is developed based on our previous work in motion estimation. Second, an iterative split-and-merge spatial segmentation scheme is proposed with an initial segmentation being provided by a recursive conditioned dilation operation merging pixels into homogeneous regions, followed by an iterative refinement algorithm to obtain the final spatial segmentation. Third, temporal and spatial segmentation are linked to form spatio-temporal segmentation with the shape of each object being simplified by a morphological close-opening operation to obtain the final segmentation. Performance evaluation shows that the developed algorithm can successfully segment moving objects without any human intervention.

In the paper, our high performance significance-linked connected component analysis (SLCCA) image compression algorithm is extended to three-dimensional wavelet coding resulting in a highly efficient and scalable video codec termed 3DSLCCA. Advantageous features of 3DSLCCA include low computational complexity, rate, spatial, temporal, and SNR scalability, and prevention of error propagation at the price of acceptable degradation in both objective and subjective quality when compared to the state-of-the-art H.263 standard.

An efficient image database system is developed. The most important features of the proposed system include compressed domain indexing, searching by using scalable features, and progressive image transmission. User interaction is involved both at the search refinement stage and in the display of the query results. The most important query types include query by color layout and query by wavelet-coefficient clustering information. The indexing and searching algorithms are tightly coupled with the underlying image compression algorithm by which means the images are stored in the database, reducing both the complexity and the storage requirements of the database management system. In this research, we utilize our previously developed (B.-B. Chai et al., 1997, 1998) high-performance wavelet image coding algorithm, termed "significance-linked connected component analysis", which not only renders a very high compression performance when compared to other top-ranked wavelet image coding algorithms and the JPEG standard, but also inherently supports scalable features and progressive transmission. Computer experiments demonstrate the efficiency of the developed system.

This paper proposes a general model for bidirectional associative memories that associate patterns between the X-space and the Y-space. The general model does not require the usual assumption that the interconnection weight from a neuron in the X-space to a neuron in the Y-space is the same as the one from the Y-space to the X-space. We start by defining a supporting function to measure how well a state supports another state in a general bidirectional associative memory (GBAM). We then use the supporting function to formulate the associative recalling process as a dynamic system, explore its stability and asymptotic stability conditions, and develop an algorithm for learning the asymptotic stability conditions using the Rosenblatt perceptron rule. The effectiveness of the proposed model for recognition of noisy patterns and the performance of the model in terms of storage capacity, attraction, and spurious memories are demonstrated by some outstanding experimental results.

This paper is theoretical. We present sufficient and "almost" necessary conditions for learning compatibility coefficients in relaxation labeling whose satisfaction will guarantee each desired sample labeling to become consistent and each ambiguous or erroneous input sample labeling to be attracted to the corresponding desired sample labeling. The derived learning conditions are parallel and local information based. In fact, they are organized as linear inequalities in unit wise and thus the perceptron like algorithms can be used to solve them efficiently with finite convergence.

Recent success in wavelet image coding is mainly attributed to recognition of the importance of data organization and representation. There have been several very competitive wavelet coders developed, namely, Shapiro's embedded zerotree wavelets (EZW), Servetto et al.'s morphological representation of wavelet data (MRWD), and Said and Pearlman's set partitioning in hierarchical trees (SPIHT). In this paper, we develop a novel wavelet image coder called significance-linked connected component analysis (SLCCA) of wavelet coefficients that extends MRWD by exploiting both within-subband clustering of significant coefficients and cross-subband dependency in significant fields. Extensive computer experiments on both natural and texture images show convincingly that the proposed SLCCA outperforms EZW, MRWD, and SPIHT. For example, for the "Barbara" image, at 0.5 bpp SLCCA outperforms EZW and SPIHT by 1.75 dB and 0.89 dB in PSNR, respectively. This outstanding performance is achieved without using any optimal bit allocation procedure, thus both the encoding and decoding procedures are fast.

Recent success in wavelet image coding is mainly attributed to the recognition of importance of data organization and representation, There have been several very competitive wavelet coders developed, namely, embedded zerotree wavelets (EZW), morphological representation of wavelet data (MRWD), and set partitioning in hierarchical trees (SPIHT). In this paper, we develop a novel wavelet image coder called significance-linked connected component analysis (SLCCA) of wavelet coefficients that extends MRWD by exploiting both within-subband clustering of significant coefficients and cross-subband dependency in significant fields. Computer experiments on both natural and texture images show convincingly that the proposed SLCCA outperforms EZW, MRWD, and SPIHT as well. For example, for the "Barbara" image, at 0.50 bpp SLCCA outperforms EZW and SPIHT by 1.71 dB and 0.85 dB in PSNR, respectively. It is also observed that SLCCA works extremely well for images with a large portion of texture. This outstanding performance is achieved without using any optimal bit allocation procedure. Thus both the encoding and decoding procedures are fast.

A highly efficient algorithm termed adaptive forward-backward vector quantization (AFBVQ) is developed for variable bit rate quantization of linear predictive coding (LPC) coefficients and integrated with the FS1016 Federal Standard Code Excited Linear Predictive (CELP) coder. This results in a high performance low bit rate speech coder called as AFBVQ-CELP which brings in two-fold bit rate reduction by backward LPC indexing and by forward LPC VQ. In AFBVQ, a previously decoded and temporally close speech signal is re-segmented into overlapping blocks. As the LPC coefficients calculated from one of those synthetic blocks are spectrally close to the current unquantized LPC coefficients, the backward LPC indexing is used to encode the current speech block; otherwise, the forward linear prediction is practised with the split vector quantization supported by a very efficient codebook initialization termed Mixture Gaussian Clustering (MGC). When compared to FS1016 CELP coder, AFBVQ-CELP reduces the LPC bit rate by 18 bit-per-frame (bpf) at the same spectral distortion. It means the overall bit rate is reduced from 4.8 kbps (FS1016 CELP) to 4.2 kbps. Furthermore, the proposed AFBVQ consistently outperforms the traditional forward LPC VQ by 3 bpf with the same spectral distortion. Subjective listening tests show that with AFBVQ-CELP the LPC bit rate can be further reduced to 8.4 bpf, resulting in 3.94 kbps overall bit rate without compromising the decoded speech quality.

A novel variable-rate linear predictive coding (LPC) parameter quantization scheme is proposed, in which linear prediction is done by using either the current (forward LPC) or previously decoded (backward LPC) speech blocks. The proposed LPC quantization scheme was integrated into the FS1016 Federal Standard CELP coder. Significant LPC bit rate reduction is achieved without compromising the decoded speech quality.

This paper attempts to consolidate the theoretical foundation of the relaxation labeling processes, explore the connections between the relaxation labeling model and the Hopfield associative memory model, and seek their unification. We start by defining a new labeling assignment space and then formulate the relaxation labeling process as a dynamic system of Lyapunov type, which is equipped with a well-defined energy function and described by a naturally fitted updating rule. We present a consistency condition and show that each /spl omega/-limit point of the dynamic system gives a consistent labeling. We finally make a peace between the multi-label and one-label relaxation labeling and reveal an interesting result that, for a one-label case, the newly formulated relaxation labeling model reduces to the Hopfield associative memory model.

A linear decision binary tree structure is proposed in constructing piecewise linear classifiers with the genetic algorithm (GA) being shaped and employed at each nonterminal node to search for a linear decision function optimal in the sense of maximum impurity reduction. The methodology works for both the two-class and multiclass cases. In comparison to several other well known methods, the proposed binary tree-genetic algorithm (BTGA) is demonstrated to produce a much lower cross validation misclassification rate. Finally, a modified BTGA is applied to the important pap smear cell classification. This results in a spectrum for the combination of the highest desirable sensitivity along with the lowest possible false alarm rate. The multiple choices offered by the spectrum for the sensitivity-false alarm rate combination will provide the flexibility needed for the pap smear slide classification.

Two new motion compensation methods for video coding are presented. The first method named motion-partitioned adaptive block matching algorithm (MPA-BMA) uses motion boundary information as the sub-dividing or merging criteria to form variable-size matching blocks. The second method named predictive block matching algorithm (PBMA) eliminates the need of sending motion data by predicting motion vectors from previously transmitted pixels. The performance evaluation of both algorithms are given in the experiments.

We present a new approach to the modeling and decomposition of Gaussian mixtures by using robust statistical methods. The mixture distribution is viewed as a contaminated Gaussian density. Using this model and the model-fitting (MF) estimator, we propose a recursive algorithm called the Gaussian mixture density decomposition (GMDD) algorithm for successively identifying each Gaussian component in the mixture. The proposed decomposition scheme has advantages that are desirable but lacking in most existing techniques. In the GMDD algorithm the number of components does not need to be specified a priori, the proportion of noisy data in the mixture can be large, the parameter estimation of each component is virtually initial independent, and the variability in the shape and size of the component densities in the mixture is taken into account. Gaussian mixture density modeling and decomposition has been widely applied in a variety of disciplines that require signal or waveform characterization for classification and recognition. We apply the proposed GMDD algorithm to the identification and extraction of clusters, and the estimation of unknown probability densities. Probability density estimation by identifying a decomposition using the GMDD algorithm, that is, a superposition of normal distributions, is successfully applied to automated cell classification. Computer experiments using both real data and simulated data demonstrate the validity and power of the GMDD algorithm for various models and different noise assumptions.

We present a motion compensation technique called motion-partitioned adaptive block matching algorithm (MPA-BMA) for motion compensated video compression. The algorithm offers a good degree of scene adaptation to reduce prediction errors while maintaining a slightly increased amount of side motion data and being computationally affordable. It detects the motion boundaries, partitions the motion field into consistent motion groups and computes more reliable motion data by using variable-sized matching blocks that are adaptively composed. Experiments compare its good performance with the full-search block matching algorithm (BMA).

Optic flow motion analysis represents an important family of visual information processing techniques in computer vision. Segmenting an optic flow field into coherent motion groups and estimating each underlying motion is a very challenging task when the optic flow field is projected from a scene of several independently moving objects. The problem is further complicated if the optic flow data are noisy and partially incorrect. In this paper, the authors present a novel framework for determining such optic flow fields by combining the conventional robust estimation with a modified genetic algorithm. The baseline model used in the development is a linear optic flow motion algorithm due to its computational simplicity. The statistical properties of the generalized linear regression (GLR) model are thoroughly explored and the sensitivity of the motion estimates toward data noise is quantitatively established. Conventional robust estimators are then incorporated into the linear regression model to suppress a small percentage of gross data errors or outliers. However, segmenting an optic flow field consisting of a large portion of incorrect data or multiple motion groups requires a very high robustness that is unattainable by the conventional robust estimators. To solve this problem, the authors propose a genetic partitioning algorithm that elegantly combines the robust estimation with the genetic algorithm by a bridging genetic operator called self-adaptation.

An adaptively refined block matching algorithm (AR-BMA) for motion compensated (MC) video coding is presented. The AR-BMA algorithm requires transmitting the same amount of motion data as the conventional block matching algorithm (BMA) while achieving much higher prediction accuracy by an adaptive refinement scheme that captures the fine motion variations in video scenes. Experimental results show significant reduction of the prediction errors by the AR-BMA as compared with the full-search BMA.>

In order to be able to optimally design morphological shape extraction algorithms operating on binary digital images, a probability theory is needed for finite random sets and probability relations that show how the probability changes as a finite random set is propagated through a morphological operation. In this paper, we develop such a theory for finite random sets. We then demonstrate how to apply this theory for calculating the probability that a set S perturbed by min or max noise N and dilated or eroded by a structuring element K is a subset, superset, or hits a given set R. In some cases we obtain exact results and in some cases we obtain bounds for the desired probability.

The correspondence focuses on the robust 3-D-3-D pose estimation, especially, multiple pose estimation. The robust 3-D-3-D multiple pose estimation problem is formulated as a series of general regressions which involve a successively size-decreasing data set, with each regression relating to one particular pose of interest. Since the first few regressions may carry a severely contaminated Gaussian error noise model, the MF-estimator (Zhuang et al., 1992) is used to solve each regression for each pose of interest. Extensive computer experiments with both real imagery and simulated data are conducted and results are promising. Three distinctive features of the MF-estimator are theoretically discussed and experimentally demonstrated: It is highly robust in the sense that it is not much affected by a possible large portion of outliers or incorrect matches as long as the minimum number of inliers necessary to give a unique solution are provided; It is made virtually independent of initial guesses; It is computationally reasonable and admits an efficient parallel implementation.>

In this paper, a learning algorithm for bidirectional associative memories (BAM's) with optimal stability is presented. According to an objective function that measures the stability and attraction of the BAM, the authors cast the learning procedure into a global minimization problem, solved by a gradient descent technique. This learning rule guarantees the storage of training patterns with basins of attraction as large as possible. The authors also investigate the storage capacity of the BAR/L, the convergence of the learning method, the asymptotic stability of each training pattern and its basin of attraction. To evaluate the performance of the authors' learning strategy, a large number of simulations have been carried out.>

The authors focus on the robust 3D-3D single and multiple pose estimation problems. The robust 3D-3D single pose estimation problem was formulated by R. M. Haralick et al. (1989) as a general regression in terms of a contaminated Gaussian error noise model. The robust 3D-3D multiple pose estimation problem appears much more difficult. This problem is formulated as a series of general regressions involving successively decreasing data size, with each regression related to one particular pose of interest. Since the first few regressions may carry a highly contaminated Gaussian error noise model, a very robust estimator called the MF-estimator, given by X. Zhuang et al. (1992), is used to solve each regression for each desired pose estimation. Computer experiments with real imagery and simulated data were conducted and results are promising.>

A novel learning algorithm for a neuron-weighted associative memory (NWAM) is presented. The learning procedure is cast as a global minimization, solved by a gradient descent rule. An analog neural network for implementing the learning method is described. Some computer simulation experiments are reported.>

The author attempts to solve the structuring function decomposition problem where the structuring function refers to the gray scale structuring element. A morphologically realizable representation for the structuring function that reduces the structuring function decomposition into a series of binary structuring element decompositions is presented. Recursive algorithms that are pipelinable for efficiently performing gray scale morphological operations are developed on the basis of proposed representation and decomposition. The results are beneficial to real-time image analysis in terms of computer architecture and software development.>

Presents a robust and adaptive technique for segmentation of a noisy image. The original image is modeled by an underlying Gibbs random field, and the noise is the mixture of an additive independent Gaussian noise and a salt or pepper noise. The processes of maximum a posteriori segmentation and maximum-likelihood estimation for the image model parameters are carried out simultaneously.>

Designs the optimal learning rule for the Hopfield associative memories (HAM) based on three well recognized criteria, that is, all desired attractors must be made not only isolately stable but also asymptotically stable, and the spurious stable states should be the fewest possible. To construct a satisfactory HAM, those criteria are crucial. The paper first analyzes the real cause of the unsatisfactory performance of the Hebb rule and many other existing learning rules designed for HAMs and then show that three criteria actually amount to widely expanding the basin of attraction around each desired attractor. One effective way to widely expand basins of attraction of all desired attractors is to appropriately dig their respective steep kernal basin of attraction. For this, the authors introduce a concept called the Hamming-stability. The Hamming-stability for all desired attractors can be reduced to a moderately expansive linear separability condition at each neuron and thus the well known Rosenblatt's perceptron learning rule is the right one for learning the Hamming-stability. Extensive and systematic experiments were conducted, convincingly showing that the proposed perceptron. Hamming-stability learning rule did take a good care of three optimal criteria.>

In this paper, we describe an optimal learning algorithm for designing one-layer neural networks by means of global minimization. Taking the properties of a well-defined neural network into account, we derive a cost function to measure the goodness of the network quantitatively. The connection weights are determined by the gradient descent rule to minimize the cost function. The optimal learning algorithm is formed as either the unconstraint-based or the constraint-based minimization problem. It ensures the realization of each desired associative mapping with the best noise reduction ability in the sense of optimization. We also investigate the storage capacity of the neural network, the degree of noise reduction for a desired associative mapping, and the convergence of the learning algorithm in an analytic way. Finally, a large number of computer experimental results are presented.

A robust and adaptive algorithm for segmenting a noisy image is presented. The original (or noise-free) images are modeled by an underlying Gibbs random field (GRF) or equivalently by a Markov random field (MRF), and the driving noise is a mixture of an additive independent Gaussian noise and an outlier process. The processes of maximum a posteriori (MAP) segmentation and maximum-likelihood (ML) estimation for the image model parameters are carried out simultaneously. Both procedures, which are based on stochastic relaxation algorithms with a simulated annealing technique, are efficiently implementable on parallel architectures, such as artificial neural networks. Our proposed method is adaptive in that it recursively segments the noise-corrupted images and estimates the model parameters necessary for the segmentation procedure. We should emphasize that the proposed algorithm is robust in eliminating the effect caused by outliers. Finally, a number of computer simulation experiments are given to demonstrate the robustness and effectiveness of the recursive algorithm.

The authors present a highly robust estimator, known as the model fitting (MF) estimator for general regression. They explain that high robustness becomes possible through partially but completely modeling the unknown log likelihood function. The partial modeling takes place by taking the Bayesian statistical decision rule and a number of important heuristics into consideration while maximizing the log likelihood function. Applications include the automatic selection of multiple thresholds, single rigid motion estimation or multiple rigid motion segmentation, and estimation from two perspective views. It is believed that the proposed MF estimator will aid in solving many robust estimation problems that demand an estimator that is either highly robust or capable of handling contaminated Gaussian mixture models.>

A weighted learning algorithm for bidirectional associative memories (BAMs) by means of global minimization, where each desired pattern is weighted, is described. According to the cost function that measures the goodness of the BAM, the learning algorithm is formulated as a global minimization problem and solved by a gradient descent rule. The learning approach guarantees not only that each desired pattern is stored as a stable state, but also that the basin of attraction is constructed as large as possible around each desired pattern. The existence of the weights, the asymptotic stability of each desired pattern and its basin of attraction, and the convergence of the proposed learning algorithm are investigated in an analytic way. A large number of computer experiments are reported to demonstrate the efficiency of the learning rule.

The authors recently designed and implemented a large-vocabulary, speaker-independent, continuous speech recognition system. The system is based on hidden Markov modeling (HMM) of phoneme-sized acoustic units using continuous mixture Gaussian densities. The main structure of the system is outlined with a focus on a method of generating mixture Gaussian density models through a merging procedure whose efficiency was recently improved significantly. The system has been evaluated on the TIMIT database on a task of vocabulary size 853 and various grammar perplexities. The word accuracies are 92.2%, 84.9%, and 60.1% for the test set perplexities of 25, 106, and 853 (no grammar), respectively.>

Two major structuring element decomposition techniques are compared, and the superiority of the two pixel decomposition techniques over the cellular decomposition technique is shown in terms of the number of pipeline stages. As for the general structuring function decomposition, to the authors' knowledge, there is no efficient algorithm that has been found. The difficulty can be overcome by using an adequate representation of the general gray-scale structuring function. Representing a gray-scale image as a specific 3-D set, i.e. an umbra, makes it easier to shift all morphological theorems from the binary domain to the gray-scale domain; however, a direct umbra representation is not appropriate for the general gray-scale structuring function decomposition. The authors also provide a morphologically realizable representation and decomposition for the general gray-scale structuring function and show recursive algorithms which are pipelineable for efficiently performing gray-scale morphological operations.>

A general algorithm is presented for computationally efficient multidimensional maximum entropy (ME) spectral estimation. The estimator is equivalent to an analog neural net that is governed by an energy function that measures the degree of constraint satisfaction, i.e., correlation-matching property. The multidimensional ME (MDME) spectral-estimation problem is defined. ME spectral estimation is formulated as an initial-value problem. The MDME spectral estimators, or algorithms, for solving the initial-value problem are developed. The neural net algorithm is derived, and simulated experiments with 1D or 2D signals are conducted. In each, the assumed true spectrum is given and autocorrelations at a number of horizontally and vertically equally spaced lags are calculated from the Fourier transform of the true spectrum. The overall results indicate very good performance in estimating ME spectra, even in cases where there are few autocorrelation measurements.>

The authors present a highly robust estimator called an MF-estimator for general regression. It is argued that the kind of estimators needed by computer vision must be highly robust and that the classical robust estimators do not render a high robustness. It is explained that the high robustness becomes possible only through partially but completely modeling the unknown log likelihood function. Partial modeling explores a number of important heuristics implicit in the regression problem and takes place by taking them into consideration with the Bayes statistical decision rule, while maximizing the log likelihood function. Experiments with the simplest location estimation showed that the performance of the MF-estimator was superior to that of the classical M-estimator.>

An open problem of whether or not there exists a solution to the maximum entropy image reconstruction problem is theoretically solved. The convergence of a maximum entropy image reconstruction algorithm proposed by X. Zhuang et al. (IEEE Trans. Acoust., Speech, Signal Processing, vol. ASSP-35, no.2, p.208-18, Feb. 1987) is proven and its fast convergence is derived.>

A simplex-like algorithm is developed for the relaxation labeling process. The algorithm is simple and has a fast convergence property which is summarized as a one-more-step theorem. The algorithm is based on fully exploiting the linearity of the variational inequality and the linear convexity of the consistent-labeling search space in a manner similar to the operation of the simplex algorithm in linear programming.>

Solutions for four different pose estimation problems are presented. Closed-form least-squares solutions are given to the overconstrained 2D-2D and 3D-3D pose estimation problems. A globally convergent iterative technique is given for the 2D-perspective-projection-3D pose estimation problem. A simplified linear solution and a robust solution to the 2D-perspective-projection-2D-perspective-projection pose-estimation problem are also given. Simulation experiments consisting of millions of trials with varying numbers of pairs of corresponding points and varying signal-to-noise ratios (SNRs) with either Gaussian or uniform noise provide data suggesting that accurate inference of rotation and translation with noisy data may require corresponding point data sets with hundreds of corresponding point pairs when the SNR is less than 40 dB. The experimental results also show that the robust technique can suppress the blunder data which come from outliers or mismatched points.>

A description is given of the relationship between morphologically filtering and then sampling vs. sampling, and then morphologically filtering in the sampled domain. The authors also describe the relationship between morphologically filtering vs. sampling, morphologically filtering in the sampled domain, and then reconstructing. Unlike the standard communication sampling theory where for appropriately low-pass filtered images there is commutivity between sampling and filtering, this is not the case for appropriately morphologically simplified images. The relationship which does exist shows that the commutivity holds to within one sampling interval distance in the unsampled domain and to within two sampling intervals in the sampled domain.>

The authors develop an algorithm to determine uniquely the rigid body motion from optical flow and depth, where the depth, however, does not involve any derivative information. Thus, the original assumptions made by D.H. Ballard and O.A. Kimball (1983) and by R.M. Haralick and X. Zhuang (1986) are relaxed. The proposed algorithm is appealing; in contrast to the existing linear optical flow-motion algorithms, it requires only three instead of eight optical flow image points.>

A new method of formulating hidden Markov models (HMM) for isolated word recognition is presented. The authors model probabilities of hidden state sequences as Gibbs distributions (GDs) instead of the conventional products of transition probabilities. This formulation is based on the Hammersley-Clifford theorem which establishes the equivalence between Markov random fields (MRF) and GDs. The Markov chains in HMM are equivalent to one-dimensional, first order neighborhood MRFs. The observation sequences are modeled by the usual autoregressive Gaussian densities. The flexibility in the choice of energy functions in GDs makes it possible to use only a few parameters while maintaining a powerful model. The authors have developed a learning algorithm to estimate the parameters using maximum likelihood estimation and an algorithm to efficiently compute 1-D, first order neighborhood GDs using a lattice structure.>

In his work on motion analysis, Ullman (1979) showed that for the orthographic case, four-point correspondences over three views are sufficient to determine motion and structure of the four-point rigid configuration. However, his method is nonlinear and the conditions of uniqueness and convergence of his algorithm are not made clear. A simple linear algorithm to solve Ullman's problem of determining motion and structure from three orthographic views is presented. Necessary and sufficient conditions of a unique solution are also given.>

For the purposes of object or defect identification required in industrial vision applications, the operations of mathematical morphology are more useful than the convolution operations employed in signal processing because the morphological operators relate directly to shape. The tutorial provided in this paper reviews both binary morphology and gray scale morphology, covering the operations of dilation, erosion, opening, and closing and their relations. Examples are given for each morphological concept and explanations are given for many of their interrelationships.

The article gives a possible solution to an open problem of how to effectively combine the different scales of analysis at the early visual information processing level.

Given a set of corresponding points from two perspective projection images of a moving rigid object, this paper presents a direct and stable algorithm to solve for the parameters of the moving object. This involves determining the rotation, the translation direction and the relative depths of object points. Unlike previous algorithms (see [1]), the current algorithm does not require determining the mode of motion, i.e. if or not the motion is a pure rotation. As easily seen, it is hard or even impossible to determine the mode of motion in the presence of noise,

Given a set of corresponding points from a moving object is two perspective projection images. The paper completely solves the two view motion problem. We show how to use the corresponding point set to determine mode of motion, rotation, translation orientation and relative depths. Also we give a noise robust algorithm which works well under small perturbations.

The three problems: Two view motion analysis, stereo vision and determining a moving camera's position are all the same problem. We explain their equivalence and introduce a noise robust procedure for solving these problems.

A computational method has been developed for solving the maximum entropy spectrum estimation with uncertainty in the correlation measurements This approach depends on first solving an unconstrained optimization problem and then an iterative search for the zero of the constraint equation along a well-defined trajectory. This trajectory is governed by a system of differential equations and the unconstrained optimal solution as the initial condition. The direction of search can be determined easily by evaluating the constraint equation at each iteration. In solving the trajectory, the Gauss-Seidel iterative algorithm is used to solve the symmetric system of equations. The choice of the previous estimate as the initial estimate greatly accelerates the convergence rate of this scheme.

A new algorithm is developed for solving the maximum entropy (ME) image reconstruction problem. This approach involves solving a system of ordinary differential equations with appropriate initial conditions which can be computed easily. Instead of searching in the n+1-dimensional space as required for most ME algorithms, our approach involves solving a 1-dimensional search problem along a well-defined path. Moreover an efficient algorithm is developed to handle this search.