Recent research has demonstrated the capability of behavior signals captured by smartphones and wearables for longitudinal behavior modeling. However, there is a lack of a comprehensive public dataset that serves as an open testbed for fair comparison among algorithms. Moreover, prior studies mainly evaluate algorithms using data from a single population within a short period, without measuring the cross-dataset generalizability of these algorithms. We present the first multi-year passive sensing datasets, containing over 700 user-years and 497 unique users’ data collected from mobile and wearable sensors, together with a wide range of well-being metrics. Our datasets can support multiple cross-dataset evaluations of behavior modeling algorithms’ generalizability across different users and years. As a starting point, we provide the benchmark results of 18 algorithms on the task of depression detection. Our results indicate that both prior depression detection algorithms and domain generalization techniques show potential but need further research to achieve adequate cross-dataset generalizability. We envision our multi-year datasets can support the ML community in developing generalizable longitudinal behavior modeling algorithms.

A deep understanding of how discrimination impacts psychological health and well-being of students could allow us to better protect individuals at risk and support those who encounter discrimination. While the link between discrimination and diminished psychological and physical well-being is well established, existing research largely focuses on chronic discrimination and long-term outcomes. A better understanding of the short-term behavioral correlates of discrimination events could help us to concretely quantify such experiences, which in turn could support policy and intervention design. In this paper we specifically examine, for the first time, what behaviors change and in what ways in relation to discrimination. We use actively-reported and passively-measured markers of health and well-being in a sample of 209 first-year college students over the course of two academic quarters. We examine changes in indicators of psychological state in relation to reports of unfair treatment in terms of five categories of behaviors: physical activity, phone usage, social interaction, mobility, and sleep. We find that students who encounter unfair treatment become more physically active, interact more with their phone in the morning, make more calls in the evening, and spend more time in bed on the day of the event. Some of these patterns continue the next day. Our results further our understanding of the impact of discrimination and can inform intervention work.

Mobile sign language video communication has the potential to be more accessible and affordable if the current recommended video transmission standard of 25 frames per second at 100 kilobits per second (kbps) as prescribed in the International Telecommunication Standardization Sector (ITU-T) Q.26/16 were relaxed. To investigate sign language video intelligibility at lower settings, we conducted a laboratory study, where fluent ASL signers in pairs held real-time free-form conversations over an experimental smartphone app transmitting real-time video at 5 fps/25 kbps, 10 fps/50 kbps, 15 fps/75 kbps, and 30 fps/150 kbps, settings well below the ITU-T standard that save both bandwidth and battery life. The aim of the laboratory study was to investigate how fluent ASL signers adapt to the lower video transmission rates, and to identify a lower threshold at which intelligible real-time conversations could be held. We gathered both subjective and objective measures from participants and calculated battery life drain. As expected, reducing the frame rate/bit rate monotonically extended the battery life. We discovered all participants were successful in holding intelligible conversations across all frame rates/bit rates. Participants did perceive the lower quality of video transmitted at 5 fps/25 kbps and felt that they were signing more slowly to compensate; however, participants' rate of fingerspelling did not actually decrease. This and other findings support our recommendation that intelligible mobile sign language conversations can occur at frame rates as low as 10 fps/50 kbps while optimizing resource consumption, video intelligibility, and user preferences.

Mobile sign language video conversations can become unintelligible due to high video transmission rates causing network congestion and delayed video. In an effort to understand how much sign language video quality can be sacrificed, we evaluated the perceived lower limits of intelligible sign language video transmitted at four low frame rates (1, 5, 10, and 15 frames per second [fps]) and four low fixed bitrates (15, 30, 60, and 120 kilobits per second [kbps]). We discovered an "intelligibility ceiling effect," where increasing the frame rate above 10 fps decreased perceived intelligibility, and increasing the bitrate above 60 kbps produced diminishing returns. Additional findings suggest that relaxing the recommended international video transmission rate, 25 fps at 100 kbps or higher, would still provide intelligible content while considering network resources and bandwidth consumption. As part of this work, we developed the Human Signal Intelligibility Model, a new conceptual model useful for informing evaluations of video intelligibility.

A "discount" version of Q-methodology for HCI, called "HCI-Q", can be used in iterative design cycles to explore, from the point of view of users and other stakeholders, what makes technologies personally significant. Initially, designers critically reflect on their own assumptions about how a design may affect social and individual behavior. Then, designers use these assumptions as stimuli to elicit other people's points of view. This process of critical self-reflection and evaluation helps the designer to assess the fit between a design and its intended social context of use. To demonstrate the utility of HCI-Q for research and design, we use HCI-Q to explore stakeholders' responses to a prototype Alternative and Augmentative Communication (AAC) application called Vid2Speech. We show that our adaptation of Q-methodology is useful for revealing the structure of consensus and conflict among stakeholder perspectives, helping to situate design within the context of relevant value tensions and norms.

Enabling end-users of Augmentative and Alternative Communication (AAC) systems to add personalized video content at runtime holds promise for improving communication, but the requirements for such systems are as yet unclear. To explore this issue, we present Vid2Speech, a prototype AAC system for children with complex communication needs (CCN) that uses personalized video to enhance representations of action words. We describe three design goals that guided the integration of personalized video to enhance AAC in our early-stage prototype: 1) Providing social-temporal navigation; 2) Enhancing comprehension; and 3) Enabling customization in real time. Our system concept represents one approach to realizing these goals, however, we contribute the goals and the system as a starting point for future innovations in personalized video-based AAC.

Video and image quality are often objectively measured using peak signal-to-noise ratio (PSNR), but for sign language video, human comprehension is most important. Yet the relationship of human comprehension to PSNR has not been studied. In this survey, we determine how well PSNR matches human comprehension of sign language video. We use very low bitrates (10-60 kbps) and two low spatial resolutions (192×144 and 320×240 pixels) which may be typical of video transmission on mobile phones using 3G networks. In a national online video-based user survey of 103 respondents, we found that respondents preferred the 320×240 spatial resolution transmitted at 20 kbps and higher; this does not match what PSNR results would predict. However, when comparing perceived ease/difficulty of comprehension, we found that responses did correlate well with measured PSNR. This suggests that PSNR may not be suitable for representing subjective video quality, but can be reliable as a measure for comprehensibility of American Sign Language (ASL) video. These findings are applied to our experimental mobile phone application, MobileASL, which enables real-time sign language communication for Deaf users at low bandwidths over the U.S. 3G cellular network.

The goal of the MobileASL (American Sign Language) research project is to enable sign language communication over the U.S. cellular network, which is low bandwidth and lossy. Data loss can greatly impact the quality of compressed video because of temporal and spatial error propagation. We investigate techniques to minimize the effect of data loss for improving compressed video sign language conversations. As both computational power and bandwidth are limited on cellular devices, we must carefully allocate these resources. Specifically we focus on utilizing feedback to recover from data loss.

MobileASL is a video compression project for two-way, real-time video communication on cell phones, allowing Deaf people to communicate in the language most accessible to them, American Sign Language. Unfortunately, running MobileASL quickly depletes a full battery charge in a few hours. Previous work on MobileASL investigated a method called variable frame rate (VFR) to increase the battery duration. We expand on this previous work by creating two new power saving algorithms, variable spatial resolution (VSR), and the application of both VFR and VSR. These algorithms extend the battery life by altering the temporal and/or spatial resolutions of video transmitted on MobileASL. We found that implementing only VFR extended the battery life from 284 minutes to 307 minutes; implementing only VSR extended the battery life to 306 minutes, and implementing both VFR and VSR extended the battery life to 315 minutes. We evaluated all three algorithms by creating a linguistically accessible online survey to investigate Deaf people's perceptions of video quality when these algorithms were applied. In our survey results, we found that VFR produces perceived video choppiness and VSR produces perceived video blurriness; however, a surprising finding was that when both VFR and VSR are used together, they largely ameliorate the choppiness and blurriness perceived, i.e., they each improve the use of the other. This is a useful finding because using VFR and VSR together saves the most battery life.

The H.264 encoder has input parameters that determine the bit rate and distortion of the compressed video and the encoding complexity. A set of encoder parameters is referred to as a parameter setting. We previously proposed two offline algorithms for choosing H.264 encoder parameter settings that have distortion-complexity performance close to the parameter settings obtained from an exhaustive search, but take significantly fewer encodings. However they generate only a few parameter settings. If there is no available parameter settings for a given encode time, the encoder will need to use a lower complexity parameter setting resulting in a decrease in peak-signal-to-noise-ratio (PSNR). In this paper, we propose two algorithms for finding additional parameter settings over our previous algorithm and show that they improve the PSNR by up to 0.71 dB and 0.43 dB, respectively. We test both our algorithms on Linux and PocketPC platforms.

We describe our system called MobileASL for real-time video communication on the current U.S. mobile phone network. The goal of MobileASL is to enable Deaf people to communicate with Sign Language over mobile phones by compressing and transmitting sign language video in real-time on an off-the-shelf mobile phone, which has a weak processor, uses limited bandwidth, and has little battery capacity. We develop several H.264-compliant algorithms to save system resources while maintaining ASL intelligibility by focusing on the important segments of the video. We employ a dynamic skin-based region-of-interest (ROI) that encodes the skin at higher quality at the expense of the rest of the video. We also automatically recognize periods of signing versus not signing and raise and lower the frame rate accordingly, a technique we call variable frame rate (VFR). We show that our variable frame rate technique results in a 47 % gain in battery life on the phone, corresponding to an extra 68 minutes of talk time. We also evaluate our system in a user study. Participants fluent in ASL engage in unconstrained conversations over mobile phones in a laboratory setting. We find that the ROI increases intelligibility and decreases guessing. VFR increases the need for signs to be repeated and the number of conversational breakdowns, but does not affect the users ’ perception of adopting the technology. These results show that our sign language sensitive algorithms can save considerable resources without sacrificing intelligibility. ACM Classification: H5.2 [Information interfaces and presentation]:Multimedia Information Systems–Video. K.4.2 [Computers and Society]: Social Issues–Assistive technologies for persons with disabilities. General terms:

The goal of the MobileASL project is to increase accessibility by making the mobile telecommunications network available to the signing Deaf community. Video cell phones enable Deaf users to communicate in their native language, American Sign Language (ASL). However, encoding and transmission of real-time video over cell phones is a power-intensive task that can quickly drain the battery.

The MobileASL project aims to increase accessibility by enabling Deaf people to communicate over video cell phones in their native language, American Sign Language (ASL). Real-time video over cell phones can be a computationally intensive task that quickly drains the battery, rendering the cell phone useless. Properties of conversational sign language allow us to save power and bits: namely, lower frame rates are possible when one person is not signing due to turn-taking, and signing can potentially employ a lower frame rate than fingerspelling. We conduct a user study with native signers to examine the intelligibility of varying the frame rate based on activity in the video. We then describe several methods for automatically determining the activity of signing or not signing from the video stream in real-time. Our results show that varying the frame rate during turn-taking is a good way to save power without sacrificing intelligibility, and that automatic activity analysis is feasible.

The H.264/ACV standard provides significant improvements in performance over earlier video coding standards at the cost of increased complexity. Our challenge is to determine H.264 parameter settings that have low complexity but still offer high video quality. In this paper, we propose two fast algorithms for finding the H.264 parameter settings that take about 1% and 8%, respectively, of the number of tests required by an exhaustive search. Both the fast algorithms result in a maximum decrease in peak-signal-to-noise ratio of less than 0.71 dB for different data sets and bitrates

Most bit allocation algorithms for video are geared toward optimizing the average frame distortion. However, video sequences optimized this way may exhibit sudden changes in distortion, or "flicker," which can significantly affect the perceived quality of the sequence. An alternative approach is to minimize the maximum frame distortion, which aims to produce a constant-quality sequence, thus avoiding the flicker problem. In this work, we present a new algorithm for constant-quality video, called MultiStage. We first show how MultiStage works for an embedded bit plane coder, and we then demonstrate that it can be applied to traditional quantization-based coders, such as H.263 and H.264, in conjunction with a novel single-frame block-level rate-distortion optimization algorithm based on multiple-choice knapsack. We show that MultiStage achieves very good results, both in terms of maximum distortion and average distortion

For Deaf people, access to the mobile telephone network in the United States is currently limited to text messaging, forcing communication in English as opposed to American Sign Language (ASL), the preferred language. Because ASL is a visual language, mobile video phones have the potential to give Deaf people access to real-time mobile communication in their preferred language. However, even today's best video compression techniques can not yield intelligible ASL at limited cell phone network bandwidths. Motivated by this constraint, we conducted one focus group and one user study with members of the Deaf Community to determine the intelligibility effects of video compression techniques that exploit the visual nature of sign language. Inspired by eyetracking results that show high resolution foveal vision is maintained around the face, we studied region-of-interest encodings (where the face is encoded at higher quality) as well as reduced frame rates (where fewer, better quality, frames are displayed every second). At all bit rates studied here, participants preferred moderate quality increases in the face region, sacrificing quality in other regions. They also preferred slightly lower frame rates because they yield better quality frames for a fixed bit rate. These results show promise for realtime access to the current cell phone network through signlanguage-specific encoding techniques.

Research Supported By National Science Foundation Grant Number Ccr-0104800. Richard Ladner was supported in part by the Boeing Professor-ship in Computer Science and Engineering. Contact Information: Professor Agnieszka Miguel, Department of Electrical & Computer Engineering Seattle University, 901 12th Avenue, P.O. Box 222000, Seattle, WA 98122-1090, (206)296-5965, [email protected]. ABSTRACT Algorithms for near-lossless compression of hyperspectral images are presented. They guarantee that the intensity of any pixel in the decompressed image(s) differs from its original value by no more than a user-specified quantity. To reduce the bit rate required to code images while providing significantly more compression than lossless algorithms, linear prediction between the bands is used. Each band is predicted by a previously transmitted band. The prediction is subtracted from the original band, and the residual is compressed with a bit plane coder which uses context-based adaptive binary arithmetic coding. To find the best prediction algorithm, the impact of various band orderings and optimization techniques on the compression ratios is studied.

Ringenburg et al. (2004) developed MultiStage, a bit-allocation algorithm for embedded video coders, that generates near-constant quality sequences. In this work, we show how the algorithm can be applied to quantization-based coders, and implement it for H.263. We also describe a novel approach for block-level bit allocation for H.263, cast as a variation on the multiple-choice knapsack problem, and show how to solve it efficiently with dynamic programming. Our results show that very stable quality can be achieved using relatively few coding iterations, with very little sacrifice in mean distortion.

We study the application of unequal loss protection (ULP) algorithms to motion-compensated video over lossy packet networks. In particular, we focus on streaming video applications over the Internet. The original ULP framework applies unequal amounts of forward error correction to embedded data to provide graceful degradation of quality in the presence of increasing packet loss. In this letter, we apply the ULP framework to baseline H.263, a video compression standard that targets low bit rates, by investigating reorderings of the bitstream to make it embedded. The reordering process allows a receiver to display quality video, even at the loss rates encountered in wireless transmissions and the current Internet.

This paper presents an algorithm for lossy compression of hyperspectral images for implementation on field programmable gate arrays (FPGA). To greatly reduce the bit rate required to code images, linear prediction is used between the bands to exploit the large amount of inter-band correlation. The prediction residual is compressed using the set partitioning in hierarchical trees algorithm. To reduce the complexity of the predictive encoder, this paper proposes a bit plane-synchronized closed loop predictor that does not require full decompression of a previous band at the encoder. The new technique achieves almost the same compression ratio as standard closed loop predictive coding and has a simpler on-board implementation.

We present three new bit allocation techniques, the multistage algorithm, the ratio algorithm, and the Pseudo I-frame method. The multistage and ratio algorithms are global interframe bit allocation algorithms for embedded video coders, which attempt to minimize the maximum distortion of any frame. The Pseudo I-frame method breaks a video into segments where bit allocation algorithms should be run, and segments where constant rate bit allocation will suffice. We present experiments, using the group testing for video coder (G. Shavit, et al., 2004), that compare our techniques to constant rate allocation and to a bit allocation algorithm due to Yang and Hemami (Y. Yang, et al., 1999).

Hong and Ladner (2001) used context-based group testing to implement bit-plane coding for image compression. We extend this technique to video coding, by replacing the quantization and entropy-coding stages, of an H.263 standard video coder, with bit-plane coding. We experiment with ways to improve baseline coder, including different classification schemes and cross-frame adaptive coding. Our results indicate that our new coder, GTV (group testing for video), significantly outperforms H.263 at medium to high bit-rates (300+kbps) on most sequences, while allowing very precise rate scalability.

The application of unequal loss protection (ULP) algorithms to motion-compensated video over lossy packet networks is studied. In particular, the focus is on streaming video applications over the Internet. The original ULP framework applies unequal amounts of forward error correction (FEC) to embedded data to provide graceful degradation of quality in the presence of increasing packet loss. The ULP framework is applied to baseline H.263, a non-embedded video compression standard, by investigating re-orderings of the bitstream. The re-ordering process makes the bitstream appear embedded, allowing a receiver to display high quality video even at the high loss rate encountered in wireless transmissions and the current Internet.

This paper explores packet loss recovery for automatic speech recognition (ASR) in spoken dialog systems, assuming an architecture in which a lightweight client communicates with a remote ASR server. Speech is transmitted with source and channel codes optimized for the ASR application, i.e., to minimize word error rate. Unequal amounts of forward error correction, depending on the data's effect on ASR performance, are assigned to protect against packet loss. Experiments with simulated packet loss in a range of loss conditions are conducted on the DARPA Communicator (air travel information) task. Results show that the approach provides robust ASR performance which degrades gracefully as packet loss rates increase. Transmitting at 5.2 Kbps with up to 200 ms added delay, leads to only a 7% relative degradation in word error rate even under extremely adverse network conditions.

This paper introduces group testing for wavelet packets (GTWP), a novel embedded image compression algorithm based on wavelet packets and group testing. This algorithm extends the group testing for wavelets (GTW) algorithm to handle wavelet packets. Like its predecessor, GTWP obtains good compression performance without the use of arithmetic coding. It also shows that the group testing methodology is very flexible and can be applied in many different circumstances.

This paper explores packet loss recovery in client-server Automatic Speech Recognition (ASR) systems. A forward error correction (FEC) system is designed and tested over several channel loss models, at variable amounts of data acquisition delay. In experiments with simulated packet loss, the FEC system provides robust ASR performance which degrades gracefully as packet loss rates increase. Comparing this scheme to several alternatives under low and medium loss channel conditions, we found one approach (multiple transmission plus interpolation) that yielded similar performance, but the FEC system should scale better to lower bit rate conditions.

Summary form only given. We present a simple and efficient scheme for protecting a region of interest (ROI) in an image sent across generalized multiple description networks. To increase the probability that the ROI is received with high quality, we extend the unequal loss protection framework of MD-SPIHT by adding more redundancy to the ROI than to other parts of the image. The SPIHT algorithm orders data progressively and sends the globally important information first. By adding more redundancy to the earlier parts of the bit stream than to the later parts, MD-SPIHT protects data that are globally important to the image quality more than less important data. In this work, wavelet coefficients corresponding to the ROI are scaled by a large factor so that locally important information is sent in the earlier parts of the bit stream. As a result, the ROI is coded to a higher bit rate than the rest of the image and MD-SPIHT automatically assigns more redundancy to the localized ROI than to the background. Therefore, the ROI is heavily protected at the expense of lower protection in the background. The ROI has a higher probability of being received intact and its quality will be higher than the quality of the background. We show two cases in which 3 out of 8 descriptions are received for 35% redundancy assignment. Without ROI scaling, redundancy is spread to all parts of the image and the quality of the ROI is low. When the ROI is scaled, redundancy is concentrated in the ROI and the quality of the received ROI is higher.

This paper describes an algorithm that achieves an approximately optimal assignment of forward error correction to progressive data within the unequal loss protection framework. It first finds the optimal assignment under convex hull and fractional bit allocation assumptions. It then relaxes those constraints to find an assignment that approximates the global optimum. The algorithm has a running time of O(hNlogN) where h is the number of points on the convex hull of the source's utility-cost curve and N is the number of packets transmitted.

We present the unequal loss protection (ULP) framework in which unequal amounts of forward error correction are applied to progressive data to provide graceful degradation of image quality as packet losses increase. We develop a simple algorithm that can find a good assignment within the ULP framework. We use the set partitioning in hierarchical trees coder in this work, but our algorithm can protect any progressive compression scheme. In addition, we promote the use of a PMF of expected channel conditions so that our system can work with almost any model or estimate of packet losses. We find that when optimizing for an exponential packet loss model with a mean loss rate of 20% and using a total rate of 0.2 bits per pixel on the Lenna image, good image quality can be obtained even when 40% of transmitted packets are lost.

Entropy-constrained vector quantization (ECVQ) offers substantially improved image quality over vector quantization (VQ) at the cost of additional encoding complexity. We extend results in the literature for fast nearest neighbor search of VQ to ECVQ. We use a new, easily computed distance that successfully eliminates most codewords from consideration.

We present an algorithm that assigns unequal amounts of forward error correction to progressive data so as to provide graceful degradation as packet losses increase. We use the SPIHT coder to compress images in this work, but our algorithm can protect any progressive compression scheme. The algorithm can also use almost any function as a model of packet loss conditions. We find that for an exponential packet loss model with a mean of 20% and a total rate of 0.2 bpp, good image quality can be obtained, even when 40% of transmitted packets are lost.

We present a simple and efficient scheme for using the Set Partitioning in Hierarchical Trees (SPIHT) image compression algorithm in a generalized multiple description framework. To combat packet loss, controlled amounts of redundancy are added to the original data during the compression process. Unequal loss protection is implemented by varying the amount of redundancy with the importance of data. The algorithm achieves graceful degradation of image quality in the presence of increasing description loss; high image quality is obtained even when over half of the descriptions are lost.

We present an approach to the generalized multiple description problem (V.K. Goyal et al., 1998) that is fundamentally different from previously published algorithms. Our approach uses explicit channel coding in the form of unequal loss protection to obtain a solution that incorporates many important properties: it can be used with any progressive source coder; it generates a balanced encoding with information equally dispersed among the descriptions; it adds a quantifiable amount of redundancy; it adapts that amount of redundancy to expected channel conditions; and it can optimize for different distortion measures. These properties allow the system to gradually improve image quality as the number of received descriptions increases. We compare our system to previously published results and show that forward error correction in multiple description coding can surpass them by a significant margin.

To use wavelet packets for lossy data compression, the following issues must be addressed: quantization of the wavelet subbands, allocation of bits to each subband, and best-basis selection. We present an algorithm for wavelet packets that systematically identifies all bit allocations/best-basis selections on the lower convex hull of the rate-distortion curve. We demonstrate the algorithm on tree-structured vector quantizers used to code image subbands from the wavelet packet decomposition.

We propose a new maximum a posteriori (MAP) detector, without the need for explicit channel coding, to lessen the impact of communication channel errors on compressed image sources. The MAP detector exploits the spatial correlation in the compressed bitstream as well as the temporal memory in the channel to correct channel errors. We first present a technique for computing the residual redundancy inherent in a compressed grayscale image (compressed using VQ). The performance of the proposed MAP detector is compared to that of a memoryless MAP detector. We also investigate the dependence of the performance on memory characteristics of the Gilbert-Elliott channel as well as average channel error rate. Finally, we study the robustness of the proposed MAP detector's performance to estimation errors.

In this paper, an algorithm for wavelet packet trees that can systematically identify all bit allocations/best-basis selections on the lower convex hull of the rate-distortion curve is presented. The algorithm is applied to tree-structured vector quantizers used to code image subbands that result from the wavelet packet decomposition. This method is compared to optimal bit allocation for the discrete wavelet transform.

We present an algorithm for image browsing systems that embeds the output of binary Floyd-Steinberg (1975) error diffusion, or a low bit-depth gray-scale or color error diffused image into higher bit-depth gray-scale or color error diffused images. The benefits of this algorithm are that a low bit-depth halftoned image can be directly obtained from a higher bit-depth halftone for printing or progressive transmission simply by masking one or more bits off of the higher bit-depth image. The embedding can be done in any bits of the output, although the most significant or the least significant bits are most convenient. Due to constraints on the palette introduced by embedding, the image quality for the higher bit-depth halftone may be reduced. To preserve the image quality, we present algorithms for color palette organization, or binary index assignment, to be used as a preprocessing step to the embedding algorithm.

We address the problem of bit allocation to wavelet subbands by extending the recursive optimal pruning algorithm of Kiang, Baker, Sullivan and Chiu (see IEEE Transactions on Image Processing, vol.1, no.4, p.162-9, 1992) to bit allocation. We apply the algorithm to tree-structured vector quantizers used to code image subbands that result from the wavelet decomposition. We compare this method to the GBFOS algorithm, that is, the generalized Breiman, Friedman, Olshen, and Stone (1984) bit allocation, and show that it produces many additional bit allocations that lie close to the rate-distortion curve.

We study image transmission on a lossy packet network in which the loss mechanism is modeled as buffer overflows. A simple error concealment strategy involving table lookups and a buffer allocation scheme with an optimally chosen virtual boundary for a 2 priority class system are described. Significant improvements are achieved by combining these two strategies.

We present an algorithm for image browsing systems that embeds a color halftone into another color halftone of a higher bit depth, as well as embedding a grayscale or binary halftone into a grayscale or color halftone. The benefit of this algorithm is that a low bit-depth halftone can be directly obtained from a higher bit-depth halftone for printing of progressive transmission simply by masking one or more bits off of the color halftone. The embedding can be done in any bit of the output depending on the organization of the image palettes, although the most significant or the least significant bits are most convenient. The embedding algorithm that we describe requires the use of scalar quantizers and ordered vector quantizers. We present several methods for color palette organization, or binary index assignment, to be used in conjunction with the embedded color error diffusion algorithm.

Many variants of vector quantization offer substantially improved image quality at the cost of additional complexity in encoding. Algorithms for increased speed in nearest neighbor searches for full search VQ using the Euclidean distortion measure have been presented previously with excellent results. We extend these results to any variant of VQ such as entropy constrained vector quantization (ECVQ), and Bayes-risk VQ, which uses a Lagrangian distortion measure. Additionally we introduce a variation of the existing techniques which provides additional speedup for full search VQ using Euclidean distortion as well as for those VQs using modified distortion measures.

We describe a new way to organize a full-search vector quantization codebook so that images encoded with it can be sent progressively and have resilience to channel noise. The codebook organization guarantees that the most significant bits (MSBs) of the codeword index are most important to the overall image quality and are highly correlated. Simulations show that the effective channel error rates of the MSBs can be substantially lowered by implementing a maximum a posteriori (MAP) detector similar to one suggested by Phamdo and Farvardin (see IEEE Trans. Inform. Theory, vol.40, no.1, p.156-193, 1994). The performance of the scheme is close to that of pseudo-gray coding at lower bit error rates and outperforms it at higher error rates. No extra bits are used for channel error correction.

The authors have developed a new classified vector quantizer (CVQ) using decomposition and prediction which does not need to store or transmit any side information. To obtain better quality in the compressed images, human visual perception characteristics are applied to the classification and bit allocation. This CVQ has been subjectively evaluated for a sequence of X-ray CT images and compared to a DCT coding method. Nine X-ray CT head images from three patients are compressed at 10:1 and 15:1 compression ratios and are evaluated by 13 radiologists. The evaluation data are analyzed statistically with analysis of variance and Tukey's multiple comparison. Even though there are large variations in judging image quality among readers, the proposed algorithm has shown significantly better quality than the DCT at a statistical, significance level of 0.05. Only an interframe CVQ can reproduce the quality of the originals at 10:1 compression at the same significance level. While the CVQ can reproduce compressed images that are not statistically different from the originals in quality, the effect on diagnostic accuracy remains to be investigated.

Presents an approach for performing edge detection which builds on prior work in fast facet edge detection using tree-structured vector quantization (TSVQ). The authors first extend the approach by using larger image vectors to reduce computational complexity by performing edge detection on multiple pixels at once. They then reduce the computational complexity of the edge detector without sacrificing performance by pruning the TSVQ with an edge detection-based criterion. They present results of edge detector performance on a sequence of images obtained from a mobile robot.>

Examines how the performance of a memoryless vector quantizer changes as a function of its training set size. Specifically, the authors study how well the training set distortion predicts test distortion when the training set is a randomly drawn subset of blocks from the test or training image(s). Using the Vapnik-Chervonenkis (VC) dimension, the authors derive formal bounds for the difference of test and training distortion of vector quantizer codebooks. The authors then describe extensive empirical simulations that test these bounds for a variety of codebook sizes and vector dimensions, and give practical suggestions for determining the training set size necessary to achieve good generalization from a codebook. The authors conclude that, by using training sets comprising only a small fraction of the available data, one can produce results that are close to the results obtainable when all available data are used.>

The authors study codeword index assignment to allow for progressive image transmission of fixed rate full-search vector quantization (VQ). They develop three new methods of assigning indices to a vector quantization codebook and formulate these assignments as labels of nodes of a full-search progressive transmission tree. The tree is used to design intermediate codewords for the decoder so that full-search VQ has a successive approximation character. The binary representation for the path through the tree represents the progressive transmission code. The methods of designing the tree that they apply are the generalized Lloyd algorithm, minimum cost perfect matching from optimization theory, and a method of principal component partitioning. Their empirical results show that the final method gives intermediate signal-to-noise ratios (SNRs) that are close to those obtained with tree-structured vector quantization, yet they have higher final SNRs.

The authors consider data compression of binary error diffused images. The original contribution is using nonlinear filters to decode error-diffused images to compress them in the gray-scale domain; this gives better image quality than directly compressing the binary images. Their method is of low computational complexity and can work with any halftoning algorithm.

The authors combine pruned tree-structured vector quantization (pruned TSVQ) with Itoh's (1987) universal noiseless coder. By combining pruned TSVQ with universal noiseless coding, they benefit from the "successive approximation" capabilities of TSVQ, thereby allowing progressive transmission of images, while retaining the ability to noiselessly encode images of unknown statistics in a provably asymptotically optimal fashion. Noiseless compression results are comparable to Ziv-Lempel and arithmetic coding for both images and finely quantized Gaussian sources.>

A review is presented of vector quantization, the mapping of pixel intensity vectors into binary vectors indexing a limited number of possible reproductions, which is a popular image compression algorithm. Compression has traditionally been done with little regard for image processing operations that may precede or follow the compression step. Recent work has used vector quantization both to simplify image processing tasks, such as enhancement classification, halftoning, and edge detection, and to reduce the computational complexity by performing the tasks simultaneously with the compression. The fundamental ideas of vector quantization are explained, and vector quantization algorithms that perform image processing are surveyed.>

The performance of a vector quantizer can be improved by using a variable-rate code. Three variable-rate vector quantization systems are applied to speech, image, and video sources and compared to standard vector quantization and noiseless variable-rate coding approaches. The systems range from a simple and flexible tree-based vector quantizer to a high-performance, but complex, jointly optimized vector quantizer and noiseless code. The systems provide significant performance improvements for subband speech coding, predictive image coding, and motion-compensated video, but provide only marginal improvements for vector quantization of linear predictive coefficients in speech and direct vector quantization of images. Criteria are suggested for determining when variable-rate vector quantization may provide significant performance improvement over standard approaches.>

The authors apply a lossy compression algorithm to medical images, and quantify the quality of the images by the diagnostic performance of radiologists, as well as by traditional signal-to-noise ratios and subjective ratings. The authors' study is unlike previous studies of the effects of lossy compression in that they consider nonbinary detection tasks, simulate actual diagnostic practice instead of using paired tests or confidence rankings, use statistical methods that are more appropriate for nonbinary clinical data than are the popular receiver operating characteristic curves, and use low-complexity predictive tree-structured vector quantization for compression rather than DCT-based transform codes combined with entropy coding. The authors' diagnostic tasks are the identification of nodules (tumors) in the lungs and lymphadenopathy in the mediastinum from computerized tomography (CT) chest scans. Radiologists read both uncompressed and lossy compressed versions of images. For the image modality, compression algorithm, and diagnostic tasks the authors consider, the original 12 bit per pixel (bpp) CT image can be compressed to between 1 bpp and 2 bpp with no significant changes in diagnostic accuracy. The techniques presented here for evaluating image quality do not depend on the specific compression algorithm and are useful new methods for evaluating the benefits of any lossy image processing technique.

Displacement estimated interframe (DEI) coding, a coding scheme for 3-D medical image data sets such as X-ray computed tomography (CT) or magnetic resonance (MR) images, is presented. To take advantage of the correlation between contiguous slices, a displacement-compensated difference image based on the previous image is encoded. The best fitting distribution functions for the discrete cosine transform (DCT) coefficients obtained from displacement compensated difference images are determined and used in allocating bits and optimizing quantizers for the coefficients. The DEI scheme is compared with 2-D block discrete cosine transform (DCT) as well as a full-frame DCT using the bit allocation technique of S. Lo and H.K. Huang (1985). For X-ray CT head images, the present bit allocation and quantizer design, using an appropriate distribution model, resulted in a 13-dB improvement in the SNR compared to the full-frame DCT using the bit allocation technique. For an image set with 5-mm slice thickness, the DEI method gave about 5% improvement in the compression ratio on average and less blockiness at the same distortion. The performance gain increases to about 10% when the slice thickness decreases to 3 mm.

An application that uses vector quantization (VQ) to speed up the process of gradient magnitude edge detection for image sequences is presented. Because image VQ and this type of edge detection operate on block-based neighborhoods, it is possible to use VQ to perform the edge detection. The image is encoded with a VQ for which the edge/no edge decision has already been made for each block. The process of edge detection becomes a simple lookup of this information. The algorithm behaves as a trainable edge detector which has the advantage of having lower computational complexity than the facet edge detector. For a VQ with an average rate of 6 bits per vector, the method requires 55% of the multiplications and 62% of the additions of the conventional facet edge detector. It also enhances the quality of the output by rejecting low-contrast, high-frequency texture edges.>

A design procedure for a vector quantizer which simultaneously performs halftoning and compression of sampled monochrome images is presented. The design method is based on the generalized Lloyd algorithm which results in a quantizer that is locally optimal under a given weighted-squared-error distortion measure. The optimal system is approximated by means of a computationally efficient vector halftoning algorithm. A test image encoded by this method at 0.094 b/pixel is compared with images of the same rate produced by independent compression and halftoning steps.>

Combined vector quantization and adaptive histogram equalization Pamela C. Cosman Eve A. Riskin Robert M. Gray tDurand Building, Department of Electrical Engineering Stanford University, Stanford, CA, 94305-4055 Department of Electrical Engineering, FT- 10 University of Washington, Seattle, WA 98195 ABSTRACT Adaptive histogram equalization is a contrast enhancement technique in which each pixel is remapped to an intensity proportional to its rank among surrounding pixels in a selected neighborhood. We present work in which adaptive histogram equalization is performed on the codebook of a tree-structured vector quantizer so that encoding with the resulting codebook performs both compression and contrast enhancement. The algorithm was tested on magnetic resonance brain scans from different subjects and the resulting images were significantly contrast enhanced. 1. INTRODUCTION Histogram equalization refers to a set of contrast enhancement techniques which attempt to spread out the intensity levels occurring in an image over the full available range.1 Histogram equalization is a competitor of interactive intensity windowing, which is the established contrast enhancement technique for medical images. In global histogram equalization, one calculates the intensity histogram for the entire image and then remaps each pixel's intensity proportional to its rank among all the pixel intensities. In adaptive histogram equalization (AHE), the histogram is calculated only for pixels in a context region, usually a square, and the remapping is done for the center pixel of the square. This can be called pointwise histogram equalization because, for each point in the image, one calculates the histogram for the square context region centered on that point. Because this is very computationally intensive, the bilinear interpolative version is an alternative that lowers the computational complexity.2 It calculates the histogram for only a set of non-overlapping context regions that cover the image and the reniapping of pixel intensity values is then exact for only the small number of pixels that are at the centers of these context regions. For all other pixels, a bilinear interpolation from the nearest context region centers determines the appropriate remapping function. With the bilinear interpolative version of AHE, the remapping function for a given pixel of intensity i at location (, y) is determined from the nearest 4 context regions as shown in figure 1. Ifm+_ denotes the mapping at the grid pixel (x+, y.) to the upper right of (x, y), and similar subscripts are used for the other surrounding context regions, then the interpolated AHE result is given by2: in(i) = a[bm(i) + (1 — b)m_(i)J + [1 — u]{bm_(i) + (1 — b)m__(i)], b= here y+—y- O-8194-0805-O/92/$4.QO SPIE Vol. 1653 Image Capture, Formatting, and Display (1992) / 213 Downloaded From: http://proceedings.spiedigitallibrary.org/ on 05/20/2014 Terms of Use: http://spiedl.org/terms

Histogram equalization is performed on the codebook of a tree-structured vector quantizer. Encoding with the resulting codebook performs both compression and contrast enhancement. It is also possible to perform intensity windowing on the codebook, or a combination of intensity windowing and histogram equalization so that these need not be separate post-processing steps.>

A vector quantization compression system is presented which is suitable for use in commercial applications, i.e., efficient enough to encode a wide variety of images and simple enough to decode the images in real time using software (for machine compatibility). A fixed-rate code with unbalanced tree structure is used, and a method of unbalanced tree growing is extended. Simple prediction techniques are applied to improve coded image quality.>

A technique is presented for directly designing an unbalanced variable rate tree-structured vector quantizer. The algorithm is an extension of an algorithm for decision tree design which grows the tree one node at a time rather than one layer at a time. The node that is split is the one that yields the greatest slope of decrease in distortion to increase in rate. This is performing a lookahead step of depth one. The authors then modify the growing technique to allow for lookahead of depths two and three. It is found that two- and three-step lookahead provide only slight improvement in the signal to noise ratio of the overall tree (on the order of 0.6 dB).>

P.H. Westerink et al. (1988) developed an optimal bit allocation algorithm that is simplified when all operational distortion-rate functions (which are referred to as quantizer functions) are convex. This algorithm is restated using the generalized Breiman, Friedman, Olshen, and Stone (BFOS) algorithm (a recently developed technique for variable rate vector quantizer design) for both cases of convex and nonconvex quantizer functions (QFs), and its complexity is analyzed. The use of the generalized BFOS algorithm for optimal bit allocation is analysed. It is shown that if each source has a convex quantizer function then the complexity of the algorithm is low.>

A recently developed technique for variable-rate vector quantizer (VQ) design by P.A. Chou et al. (see IEEE Trans. Inf. Theory, vol.35, no.2, p.299-315, 1989) has been applied to both memoryless and predictive VQ of images. This technique, called pruned tree-structured vector quantization (PTSVQ), uses variable-depth encoders that are tree-structured and thus have very low design and search complexity. PTSVQ is applied to a series of medical images, and gains over full-search VQ of up to 3.78 dB in the signal-to-noise-ratio (SNR) are measured. On still images from the USC database, gains of up to 1.63 dB in the peak SNR are realized for predictive PTSVQ over predictive full search VQ, resulting in high image quality at 0.51 bits per pixel.>