Genome sequencing has rapidly advanced in the last decade, making it easier for anyone to obtain digital genomes at low costs from companies such as Helix, MyHeritage, and 23andMe. Companies now offer their services in a direct-to-consumer (DTC) model without the intervention of a medical institution. Thereby, providing people with direct services for paternity testing, ancestry testing and disease susceptibility testing (DST) to infer diseases' predisposition. Genome analyses are partly motivated by curiosity and people often want to partake without fear of privacy invasion. Existing privacy protection solutions for DST adopt cryptographic techniques to protect the genome of a patient from the party responsible for computing the analysis. Said techniques include homomorphic encryption, which can be computationally expensive and could take minutes for only a few single-nucleotide polymorphisms (SNPs). A predominant approach is a solution that computes DST over encrypted data, but the design depends on a medical unit and exposes test results of patients to the medical unit, making the design uncomfortable for privacy-aware individuals. Hence it is pertinent to have an efficient privacy-preserving DST solution with a DTC service. We propose a novel DTC model that protects the privacy of SNPs and prevents leakage of test results to any other party save for the genome owner. Conversely, we protect the privacy of the algorithms or trade secrets used by the genome analyzing companies. Our work utilizes a secure obfuscation technique in computing DST, eliminating expensive computations over encrypted data. Our approach significantly outperforms existing state-of-the-art solutions in runtime and scales linearly for equivalent levels of security. As an example, computing DST for 10,000 SNPs requires approximately 96 milliseconds on commodity hardware. With this efficient and privacy-preserving solution which is also simulation-based secure, we open possibilities for performing genome analyses on collectively shared data resources.

Protocols for securely testing the equality of two encrypted integers are common building blocks for a number of proposals in the literature that aim for privacy preservation. Being used repeatedly in many cryptographic protocols, designing efficient equality testing protocols is important in terms of computation and communication overhead. In this work, we consider a scenario with two parties where party A has two integers encrypted using an additively homomorphic scheme and party B has the decryption key. Party A would like to obtain an encrypted bit that shows whether the integers are equal or not but nothing more. We propose three secure equality testing protocols, which are more efficient in terms of communication, computation or both compared to the existing work. To support our claims, we present experimental results, which show that our protocols achieve up to 99% computation-wise improvement compared to the state-of-the-art protocols in a fair experimental set-up.

Due to privacy threats associated with computation of outsourced data, processing data on the encrypted domain has become a viable alternative. Secure computation of encrypted data is relevant for analysing datasets in areas (such as genome processing, private data aggregation, cloud computations) that require basic arithmetic operations. Performing division operation over-all encrypted inputs has not been achieved using homomorphic schemes in non-interactive modes. In interactive protocols, the cost of obtaining an encrypted quotient (from encrypted values) is computationally expensive. To the best of our knowledge, existing homomorphic solutions on encrypted division are often relaxed to consider public or private divisor. We acknowledge that there are other techniques such as secret sharing and garbled circuits adopted to compute secure division, but we are interested in homomorphic solutions. We propose an efficient and interactive two-party protocol that computes the fixed-point quotient of two encrypted inputs, using an efficient and secure comparison protocol as a sub-protocol. Our proposal provides a computational advantage, with a linear complexity in the digit precision of the quotient. We provide proof of security in the universally composable framework and complexity analyses. We present experimental results for two cryptosystem implementations in order to compare performance. An efficient prototype of our protocol is implemented using additive homomorphic scheme (Paillier), whereas a non-efficient fully-homomorphic scheme (BGV) version is equally presented as a proof of concept and analyses of our proposal.

The increasing demand for data mining in business intelligence has led to a significant growth in the adoption of data mining as a service paradigm which enables companies to outsource their data and mining tasks to a cloud service provider. Despite the popularity of the paradigm, the companies hesitate to enable the cloud providers' access to their data considering customer privacy and intellectual property. In this paper, we propose a privacy-preserving two-party protocol which aims to mine direct sequential patterns from outsourced protected data. We focus on direct sequential pattern mining since it is a widely used primitive in business process analysis. Considering the accuracy and confidentiality, we choose encryption over statistical methods for data protection and processing. To be able to process the encrypted data, we adopt a homomorphic encryption scheme, ElGamal cryptosystem. The novelty of our scheme is that it introduces an encryption switching method that enables us to use both multiplicative and additive homomorphism on ElGamal cryptosystem. The results of our analyses show that our protocol is more efficient than the state-of-the-art proposals in terms of computational cost with a similar communication cost.

The growing complexity of software with respect to technological advances encourages model-based analysis of software systems for validation and verification. Process mining is one recently investigated technique for such analysis which enables the discovery of process models from event logs collected during software execution. However, the usage of logs in process mining can be harmful to the privacy of data owners. While for a software user the existence of sensitive information in logs can be a concern, for a software company, the intellectual property of their product and confidential company information within logs can pose a threat to company's privacy. In this paper, we propose a privacy-preserving protocol for the discovery of process models for software analysis that assures the privacy of users and companies. For this purpose, our proposal uses encrypted logs and processes them using cryptographic protocols in a two-party setting. Furthermore, our proposal applies data packing on the cryptographic protocols to optimize computations by reducing the number of repetitive operations. The experiments show that using data packing the performance of our protocol is promising for privacy-preserving software analysis. To the best of our knowledge, our protocol is the first of its kind for the software analysis which relies on processing of encrypted logs using process mining techniques.

In this paper, we first discuss the essential requirements for a fingerprint (perceptual hash)-based distributed video identification system in peer-to-peer (P2P) networks in comparison with traditional central database implementations of fingerprints. This discussion reveals that first, fingerprint sizes of existing video fingerprint methods are not compatible with the cache sizes of current P2P clients; second, fingerprint extraction durations during a query are not at tolerable levels for a user in the network; third, the repetitive patterns in the extracted fingerprints avoid the uniform distribution of storage and traffic load among the peers; and finally, the existing methods do not provide a solution to synchronize the fingerprint extraction from the shared video and queried video. In order to solve the mentioned requirements, we propose a baseline method using only the difference of video frame means, which decreases the fingerprint sizes to typical cache sizes, by increasing the granularity levels from seconds to minutes. We then develop a novel algorithm which utilizes reference points on one-dimensional frame mean sequence for the synchronization of fingerprint extraction. This algorithm is extended with a hierarchical decoding approach based on Gaussian scales, which only decodes a subset of video frames without needing a full decoding. Finally, an analysis on the effect of design parameters to the fingerprint probability distribution is performed to avoid repetitive patterns. Our ultimate solution reduces the fingerprint sizes into kilobytes, extraction time to seconds, and search duration into milliseconds, and achieves about 90% detection rates with 1–4 min granularities, while enabling a fair distribution of storage load among the peers at the same time.

In smart grids, providing power consumption statistics to the customers and generating recommendations for managing electrical devices are considered to be effective methods that can help to reduce energy consumption. Unfortunately, providing power consumption statistics and generating recommendations rely on highly privacy-sensitive smart meter consumption data. From the past experience, we see that it is essential to find scientific solutions that enable the utility providers to provide such services for their customers without damaging customers’ privacy. One effective approach relies on cryptography, where sensitive data is only given in the encrypted form to the utility provider and is processed under encryption without leaking content. The proposed solutions using this approach are very effective for privacy protection but very expensive in terms of computation and communication. In this paper, we focus on an essential operation for designing a privacy-preserving recommender system for smart grids, namely comparison, that takes two encrypted values and outputs which one is greater than the other one. We improve the state-of-the-art comparison protocol based on Homomorphic Encryption in terms of computation and communication by 56 and 25 % , respectively, by introducing algorithmic changes and data packing. As the smart meters are very limited devices, the overall improvement achieved is promising for the future deployment of such cryptographic protocols for enabling privacy enhanced services in smart grids.

Clustering is a very important tool in data mining and is widely used in on-line services for medical, financial and social environments. The main goal in clustering is to create sets of similar objects in a data set. The data set to be used for clustering can be owned by a single entity, or in some cases, information from different databases is pooled to enrich the data so that the merged database can improve the clustering effort. However, in either case, the content of the database may be privacy sensitive and/or commercially valuable such that the owners may not want to share their data with any other entity, including the service provider. Such privacy concerns lead to trust issues between entities, which clearly damages the functioning of the service and even blocks cooperation between entities with similar data sets. To enable joint efforts with private data, we propose a protocol for distributed clustering that limits information leakage to the untrusted service provider that performs the clustering. To achieve this goal, we rely on cryptographic techniques, in particular homomorphic encryption, and further improve the state of the art of processing encrypted data in terms of efficiency by taking the distributed structure of the system into account and improving the efficiency in terms of computation and communication by data packing. While our construction can be easily adjusted to a centralized or a distributed computing model, we rely on a set of particular users that help the service provider with computations. Experimental results clearly indicate that the work we present is an efficient way of deploying a privacy-preserving clustering algorithm in a distributed manner.

In an increasing number of image and video processing problems, cryptographic techniques are used to enforce content access control, identity verification and authentication, and privacy protection. The combination of cryptography and signal processing is an exciting emerging field. This introductory paper gives an overview of approaches and challenges that exist in applying cryptographic primitives to important image and video processing problems, including (partial) content encryption, secure face recognition, and secure biometrics. This paper aims to help the community in appreciating the utility and challenges of cryptographic techniques in image and video processing.

Recommender systems have become an important tool for personalization of online services. Generating recommendations in online services depends on privacy-sensitive data collected from the users. Traditional data protection mechanisms focus on access control and secure transmission, which provide security only against malicious third parties, but not the service provider. This creates a serious privacy risk for the users. In this paper, we aim to protect the private data against the service provider while preserving the functionality of the system. We propose encrypting private data and processing them under encryption to generate recommendations. By introducing a semitrusted third party and using data packing, we construct a highly efficient system that does not require the active participation of the user. We also present a comparison protocol, which is the first one to the best of our knowledge, that compares multiple values that are packed in one encryption. Conducted experiments show that this work opens a door to generate private recommendations in a privacy-preserving manner.

Online recommender systems enable personalized service to users. The underlying collaborative filtering techniques operate on privacy sensitive user data, which could be misused by the service provider. To protect user privacy, we propose to encrypt the data and generate recommendations by processing them under encryption. Thus, the service provider observes neither user preferences nor recommendations. The proposed method uses homomorphic encryption and se cure multi-party computation (MPC) techniques, which introduce a significant overhead in computational complexity. We minimize the introduced overhead by packing data and using cryptographic protocols particularly developed for this purpose. The proposed cryptographic protocol is implemented to test its correctness and performance.

Content identification in peer-to-peer (P2P) networks has until now been achieved by using metadata or cryptographic hashes. However, with increasing number of duplicates in different names and formats especially in (unmanaged) P2P networks, these tools have become insufficient for proper content finding and access right management. A complementary possible approach is to identify the content in P2P networks by using perceptual hashes, (or fingerprints) extracted from the perceptual features of the content robust to typical processing. In this paper, we first discuss the essential differences in fingerprint size, fingerprint extraction complexity, and fingerprint search methodology for a video identification system in P2P networks compared with central database applications. Then we propose a novel method optimized for P2P networks that uses only differences of video frame means. The proposed method reduces the fingerprint sizes into kilobytes, extraction time to seconds, and search duration into milliseconds. Furthermore, the uniform distribution of the extracted fingerprints enables the usage of existing DHT-based keyword search methods for fingerprint queries.

Identification of a video file in current peer-to-peer (P2P) networks is achieved by its tag or by a (100-200 bits) cryptographic hash of the entire file. However, these approaches fail when the tag is changed or some small insertions, deletions or format changes are applied to the video by a user in the network. A complementary approach is to tag a video with a few hundreds of bits of information, which we call perceptual tags, extracted from perceptual features of the content robust to typical processing. In this paper, we first give the basic requirements for the extraction and distribution of these perceptual tags in a P2P network considering the characteristics of the peers (ordinary internet users), such as low computational power and low bandwidth. Then, we propose a novel method that extracts N (64-256) bits of robust perceptual tags for a video file by using only the mean of video frames. The proposed method also achieves the uniform distribution of perceptual tags among the peers needed for the state of the art DHT-based indexing implementations in P2P networks.

In this paper we analyze the substantial performance gap between distributed video coding (DVC) and well known state-of-the-art coders. We take a modular approach towards analyzing the performance loss in DVC and investigate 3 key components. These are quantization, bit stream generation and motion estimation. Their respective contributions to the total performance loss varies with the video properties. For low motion sequences the first two components dominate. For more difficult sequences the motion estimation alone is responsible for more than half the loss. We show that it is possible to reduce this loss by repeating the motion estimation after partial decoding. Finally, we discuss advances in recent literature.

The ongoing research in distributed video coding (DVC) for low complexity encoding is trying to shorten the substantial performance gap to well known state-of-the-art coders. One way of reducing this gap is to improve the quality of the motion compensated prediction. In this paper we investigate which motion estimation method to apply in DVC, comparing possible methods to produce a motion compensated prediction. We use interpolation as well as extrapolation methods. Our results show that even with a very simple DCT scheme for the Wyner Ziv frames, extrapolation can outperform the widely used interpolation.

An audio fingerprint is a compact yet very robust representation of the perceptually relevant parts of an audio signal. It can be used for content-based audio identification, even when the audio is severely distorted. Audio compression changes the fingerprint slightly. We show that these small fingerprint differences due to compression can be used to estimate the signal-to-noise ratio (SNR) of the compressed audio file compared to the original. This is a useful content-based distortion estimate, when the original, uncompressed audio file is unavailable. The method uses the audio fingerprints only. For stochastic signals distorted by additive noise, an analytical expression is obtained for the average fingerprint difference as function of the SNR level. This model is based on an analysis of the Philips robust hash (PRH) algorithm. We show that for uncorrelated signals, the bit error rate (BER) is approximately inversely proportional to the square root of the SNR of the signal. This model is extended to correlated signals and music. For an experimental verification of our proposed model, we divide the field of audio fingerprinting algorithms into three categories. From each category, we select an algorithm that is representative for that category. Experiments show that the behavior predicted by the stochastic model for the PRH also holds for the two other algorithms.

It is well known that a compression trade-off exists between the spatial and temporal video quality. Various temporal scalability techniques have been considered for lowering the encoded frame rate such that the freed bit rate can be used to increase the PSNR quality of the remaining frames. Temporal scalability in the SVC extension of the MPEG4/AVC codec (ITU-T and ISO/IEC, 2006) is realized by the hierarchical B-frame structure or the open loop MCTF approach. We investigate the usefulness of the hierarchical B-frame structure as a tool for scaling the bit rate. We use the patented video quality metric (VQM) to measure the subjective quality, in this way explicitly taking into account temporal artifacts due to frame rate reduction. Our results indicate that there is little to no quality gain by exchanging frame rate for increased spatial quality at a given constant bit rate.

Many distributed video coders are implemented using sophisticated error correction codes that use soft information (conditional probabilities) as a priori knowledge. This a priori information models the dependency behavior between the input data and side-information. In this paper we analyze both a symbol and bit plane-based approach using LDPC codes. We show both theoretically and experimentally that a bit plane-based encoder has the same performance as a symbol-based coder, if an appropriate dependency model is chosen. We argue that due to a significant complexity reduction a bit plane-based coder is preferable over a symbol-based approach.

The processing and encryption of multimedia content are generally considered sequential and independent operations. In certain multimedia content processing scenarios, it is, however, desirable to carry out processing directly on encrypted signals. The field of secure signal processing poses significant challenges for both signal processing and cryptography research; only few ready-to-go fully integrated solutions are available. This study first concisely summarizes cryptographic primitives used in existing solutions to processing of encrypted signals, and discusses implications of the security requirements on these solutions. The study then continues to describe two domains in which secure signal processing has been taken up as a challenge, namely, analysis and retrieval of multimedia content, as well as multimedia content protection. In each domain, state-of-the-art algorithms are described. Finally, the study discusses the challenges and open issues in the field of secure signal processing.

Fingerprinting is an essential tool to shun legal buyers of digital content from illegal redistribution. In fingerprinting schemes, the merchant embeds the buyer's identity as a watermark into the content so that the merchant can retrieve the buyer's identity when he encounters a redistributed copy. To prevent the merchant from dishonestly embedding the buyer's identity multiple times, it is essential for the fingerprinting scheme to be anonymous. Kuribayashi and Tanaka, 2005, proposed an anonymous fingerprinting scheme based on a homomorphic additive encryption scheme, which uses basic quantization index modulation (QIM) for embedding. In order, for this scheme, to provide sufficient security to the merchant, the buyer must be unable to remove the fingerprint without significantly degrading the purchased digital content. Unfortunately, QIM watermarks can be removed by simple attacks like amplitude scaling. Furthermore, the embedding positions can be retrieved by a single buyer, allowing for a locally targeted attack. In this paper, we use robust watermarking techniques within the anonymous fingerprinting approach proposed by Kuribayashi and Tanaka. We show that the properties of an additive homomorphic cryptosystem allow for creating anonymous fingerprinting schemes based on distortion compensated QIM (DC-QIM) and rational dither modulation (RDM), improving the robustness of the embedded fingerprints. We evaluate the performance of the proposed anonymous fingerprinting schemes under additive-noise and amplitude-scaling attacks.

This paper addresses the problem of deriving measures that express the degree of the reliability of motion vectors estimated by a block-matching motion estimation method. We express the block matching motion estimation scheme in the probabilistic framework as a maximum-likelihood estimation scheme. Subsequently, we derive the confidence measures in terms of the a posteriori probabilities and the likelihoods of the estimated vectors. The assumptions about the type of the likelihood, that is, about the underlying conditional probability distribution of the motion compensated intensity differences (e.g., Laplacian) are derived from the objective criterion of the block-matching estimator. All parameters are estimated from data that are derived as by-product of the motion estimation scheme and our method, practically, introduces no additional computational cost. The derivation of the confidence measures is incorporated in a multiscale scheme. Experimental results are presented for image sequences with known ground-truth motion.

Research in distributed video coding for low complexity encoding has shown that without knowledge of the correlation between source and side information (i.e. the behavior of the dependency channel), the performance is substantially below that of well known state-of-the-art video coders. In a practical system the decoder needs to estimate the statistics in this dependency channel. In this paper we investigate the relation between the compression ratio and the sensitivity of the estimated channel model parameter at the decoder side. We observe that this is a hard task, but not unrealistic. We show that the tolerable parameter range is very dependent on the compression ratio and the (actual) statistics in the dependency channel.

In distributed video source coding side-information at the decoder is generated as a temporal prediction based on previous frames. This creates a virtual dependency channel between the source video at the encoder and the side information at the decoder. In recent years, distributed source coders were introduced with sophisticated error correction codes, like turbo codes and LDPC codes. Although these codes performs well on noisy network communication channels, it is far from obvious that these codes can handle the non-stationary noise in the dependency channel as encountered in distributed video coders. In this paper we study the consequences of inaccurate modeling of the dependency channel on turbo and LDPC coding and show that the performance depends greatly on the choice of the probabilistic model for the dependency channel. The results show that LDPC codes are less sensitive to inaccuracies in the dependency channel models.

We propose a fully decentralized collaborative filtering approach that is self-organizing and operates in a distributed way. The relevances between downloading files (items) are stored locally at these items in so called item-based buddy tables and are updated each time that the items are downloaded. We then propose to use the language model to build recommendations for the different users based on the buddy tables of those items a user has downloaded previously. We have tested and compared our distributed collaborative filtering approach to centralized collaborative filtering and showed that it has similar performance. It is therefore a promising technique to facilitate recommendations in peer-to-peer networks.

The use of digital video offers immense opportunities for creators; however, the ability for anyone to make perfect copies and the ease by which those copies can be distributed also facilitate misuse, illegal copying and distribution ("piracy"), plagiarism, and misappropriation. Popular Internet software based on a peer-to-peer architecture has been used to share copyrighted movies, music, software, and other materials. Concerned about the consequences of illegal copying and distribution on a massive scale, content owners are interested in digital rights management (DRM) systems which can protect their rights and preserve the economic value of digital video. A DRM system protects and enforces the rights associated with the use of digital content. Unfortunately, the technical challenges for securing digital content are formidable and previous approaches have not succeeded. We overview the concepts and approaches for video DRM and describe methods for providing security, including the roles of encryption and video watermarking. Current efforts and issues are described in encryption, watermarking, and key management. Lastly, we identify challenges and directions for further investigation in video DRM.

In video communications over error-prone channels, compressed video streams are extremely sensitive to bit errors. Often random and burst bit errors impede correct decoding of parts of a received bitstream. Video decoders normally utilize error concealment techniques to repair a damaged decoded frame, but the effectiveness of these error concealment schemes relies heavily on correctly locating errors in the bitstream. In this paper, we propose a fragile watermark-based error detection and localization scheme called "force even watermarking (FEW)". A fragile watermark is forced onto quantized DCT coefficients at the encoder. If at the decoder side the watermark is no longer intact, errors exist in the bitstream associated with a particular macro-block (MB). Thanks to the watermark, bitstream errors can accurately be located at MB level, which facilitates proper error concealment. This paper describes the algorithm, model and analysis of the watermarking procedure. Our simulation results show that compared to the syntax-based error detection schemes, the proposed FEW scheme significantly improves the error detection capabilities of the video decoder, while the peak signal-to-noise ratio loss and additional computational costs due to watermark embedding and extraction are small.

Abstract Streaming multimedia content in real‐time over a wireless link is a challenging task because of the rapid fluctuations in link conditions that can occur due to movement, interference, and so on. The popular IEEE 802.11 standard includes low‐level tuning parameters like the transmission rate. Standard device drivers for today's wireless products are based on gathering statistics and consequently, adapt rather slowly to changes in conditions. To meet the strict latency requirements of streaming applications, we designed and implemented an advanced hybrid control algorithm that uses signal‐strength (SNR) information to achieve fast responses. Since SNR readings are quite noisy, we do not use that information to directly control the rate setting, but rather as a safeguard limiting the range of feasible settings to choose from. We report on real‐time experiments involving two laptops equipped with IEEE 802.11a wireless interface cards. The results show that using SNR information greatly enhances responsiveness in comparison to statistics‐based rate controllers. Finally, we will present the results of an experiment with real‐time video streaming to a moving laptop in an office‐like environment. Our hybrid control algorithm effectively prevented many packet losses, thereby achieving a much higher video quality than the statistics‐based algorithm. Copyright © 2005 John Wiley & Sons, Ltd.

Quantization-based watermarking schemes are vulnerable to amplitude scaling. Therefore, the scaling factor needs to be estimated at the decoder side, such that the received (attacked) watermarked image can be inversely scaled prior to detection of embedded message bits. In this paper we propose a maximum likelihood (ML) approach to the estimation of the amplitude scaling factor and the variance of the noise in the attack channel. We model the probability density function (PDF) of the received (attacked) watermarked image amplitudes in case quantization index modulation with distortion compensation (QIM-DC) is used. Using this PDF, the ML estimator can be formulated. Our approach also handles the case that (subtractive) dithered quantization is employed. The behavior of the likelihood as a function of the scale and noise variance is such that efficient gradient-based optimization is unlikely to be successful. Hence, alternative optimization approaches need to be considered in future work.

The perceptual satisfaction of a user watching video on a tiny mobile device is constrained by the display capability and network bandwidth. To maximize the user's perceptual satisfaction in this constrained environment, we propose a new method to represent the video content adaptively in real-time on tiny devices according to the user's attention. First, a sampling based dynamic attention model is proposed to obtain and maintain the user's attention in the video streams. Second, based on the most attended regions and sequences extracted, the attention based representation is introduced to achieve a higher perceptual satisfaction on a small display. Experiments with users show the effectiveness of our proposed method in a video surveillance application.

Peer-to-peer (P2P) networks are generally considered to be free havens for pirated content, in particular with respect to music. We describe a solution for the problem of copyright infringement in P2P networks for music sharing. In particular, we propose a P2P protocol that integrates the functions of identification, tracking, and sharing of music with those of licensing, monitoring, and payment. This highly decentralized music-aware P2P protocol will allow access to large amounts of music of guaranteed quality; it merges in a natural way the policing functions for copyright protection and an efficient music-management infrastructure for the benefit of the user.

Geometrical transformations are one of the most important issues to be solved to increase the robustness of digital image watermarking systems. This paper presents an efficient method for inverting geometrical distortions that may spatially desynchronise a watermark detector. We propose a strategy that is scalable in transform complexity, since in some cases a simple transformation is sufficient to compensate the geometrical distortion while in other cases a more complex transform is needed. The strategy is implemented using an orthogonal polynomial mapping, which is efficiently scalable in complexity. To estimate the parameters of the polynomial, we use feature points. The results of the watermark detection after image registration are presented in the form of bit error rate (BER).

In this paper we present the initial results of experiments where encoded video data is transmitted over an IEEE 802.11a wireless link. The changing link state and the perhaps changing constraints imposed by mobile device or user, moves the optimal settings of both the video encoder and the IEEE 802.11 network layer. The video encoder and the network layer negotiates their options facilitated by a quality of service negotiation scheme called "adaptive resource contracts", thereby jointly optimizing their parameters. When time is a constraint, this optimization has to be fast and simple, maybe even at the cost of finding suboptimal solutions, as long as the found settings gives a better quality of service than fixed parameter settings.

This paper addresses the problem of deriving measures that express the degree of the reliability of motion vectors estimated by a block matching motion estimation method. We express the block matching motion estimation scheme in the probabilistic framework and derive the confidence measures in terms of the a-posteriori probabilities of the estimated vectors. The type of the underlying conditional probability distribution of the motion compensated intensity differences (e.g. Laplacian) is derived from the objective criterion of the block matching estimator. All parameters are estimated from data that are derived as a by-product of the motion estimation scheme. The derivation is incorporated in a multiscale scheme. Experimental results are presented for image sequences with known ground-truth motion.

Temporal restoration of image sequences may fail because of erroneously estimated motion. Motion estimation failures may occur for several reasons -complicated motion, severe artefacts, or a combination of both. We present an algorithm that tries to overcome at least the problems related to severe artefacts. It consists of a spatial restoration, which is supposed to recover the general image structure within the missing areas, followed by a temporal restoration. Performing spatial restoration first has the advantage that motion estimation during temporal restoration can rely on the spatially restored frames. The efficiency of the spatial restoration scheme is demonstrated for both artificial and real life examples. Restoration results when using only temporal restoration are presented for the real life sequences. Finally, we compare both restoration methods with the results of the proposed spatiotemporal algorithm and show its superior behaviour.

The robustness against geometrical attacks remains one of the most challenging issues in watermarking of images and video. This paper presents several improvements of the video watermarking approach presented in Haitsma et al. (2001), namely (i) using a temporally low-pass watermark and (ii) synchronization to resist attacks along the temporal axis. In order to improve the watermark detection performance, we propose to use an amplitude-limiting filter and a whitening filter during the watermark extraction process. Experimental results show that the proposed techniques achieve good performance.

Digital watermarking consists of hiding subliminal information into digital media content, also called host data. It can be the basis of many applications, including security and media asset management. In this paper, we focus on the imperceptibility requirement for image watermarking. We present the main features of the human visual system (HVS) to be translated into watermarking technology. This paper highlights the need for dedicated inputs from the human vision community. The human visual system (HVS) is very complex and able to deal with a huge amount of information. Roughly speaking, it is composed of a receiver with a pre-processing stage, the eye and the retina, a transmission channel, the optic nerve, and a processing engine, the visual cortex. Mainly because of our lack of knowledge about brain behavior, i.e. about the way a stimulus is processed through its huge neural network, the large effort to understand and model the HVS behavior has partly remained fruitless. The aim of this paper is not to provide a thorough description of the HVS. For complete HVS models and more specific details, the reader is referred to existing literature. Here, we only try to understand, in a synthetic way and from an engineering perspective, the HVS features on which the designer of a watermarking algorithm can rely, i.e. its sensitivity and masking capabilities.

Coring is a well-known technique for removing noise from images. The mechanism of coring consists of transforming a noise-degraded image into a frequency-domain representation, followed by a reduction of the image transform coefficients by a (nonlinear) coring function. After inverse transforming the cored coefficients, the noise-reduced image is obtained. We show that coring can be embedded into MPEG encoders with relatively little additional complexity. We exploit the statistical properties of the DCT coefficients to find the optimal Bayesian coring function for each of the DCT coefficients. Experimental results show the effectiveness of the MPEG-embedded coring function on compressing noisy image sequences.

We present in this paper the DANCERS: a system for automated indexing of broadcast news programs. The system output - a topic-based report organization structure - is obtained in three major steps. In the first step, the visual and the speech stream of a news program are analyzed in order to partition the program into report segments. In the second step, the transcribed speech of each of the report segments is matched with the content of a large pre-specified textual topic database. This database covers a large number of topics and can be updated any time. The result of the matching procedure is a list of probable topics per report segment that are used in the last step to merge related neighboring segments into reports. Each report is indexed by the topic that served as merging criterion for report segments.

This paper addresses the problem of spatio-temporal segmentation of video sequences. An initial intensity segmentation method (watershed segmentation) provides a number of initial segments which are subsequently labeled, with a known number of labels, according to motion information. The label field is modeled as a Markov random field where the statistical spatial and and temporal interactions are expressed on the basis of the initial watershed segments. The labeling criterion is the maximization of the conditional a posteriori probability of the label field given the motion hypotheses, the estimate of the label field of the previous frame, and the image intensities. For the optimization, an iterative motion estimation-labeling algorithm is proposed and experimental results are presented.

This paper proposes the differential energy watermarking (DEW) algorithm for JPEG/MPEG streams. The DEW algorithm embeds label bits by selectively discarding high frequency discrete cosine transform (DCT) coefficients in certain image regions. The performance of the proposed watermarking algorithm is evaluated by the robustness of the watermark, the size of the watermark, and the visual degradation the watermark introduces. These performance factors are controlled by three parameters, namely the maximal coarseness of the quantizer used in pre-encoding, the number of DCT blocks used to embed a single watermark bit, and the lowest DCT coefficient that we permit to be discarded. We follow a rigorous approach to optimizing the performance and choosing the correct parameter settings by developing a statistical model for the watermarking algorithm. Using this model, we can derive the probability that a label bit cannot be embedded. The resulting model can be used, for instance, for maximizing the robustness against re-encoding and for selecting adequate error correcting codes for the label bit string.

Blotches are common artifacts in old film sequences that manifest themselves as disturbing bright or dark spots. Existing methods for detecting blotches can achieve high detection rates. High detection rates are only useful if the corresponding number of false alarms is not too high, visible artifacts in the corrected sequence result otherwise. We show that the performance of blotch detectors can be improved significantly by taking statistical influence of noise on the detection mechanism into account. Further improvements are achieved first by using a double-stage detection strategy and second by a constrained dilation technique.

We present in this paper a novel image CODEC, providing an easy access to the spatial image content. This access is eased by a highly simple decompression procedure but also by the fact that the spatial image content is accessible directly on the compressed image. A reduction of the content access work is obtained while still achieving a good compression factor and a high perceptual quality of reconstructed images. This image CODEC was primarily developed to suite emerging applications on large-scale image databases.

Within the Mobile Multimedia Communication (MMC) project at the Delft University of Technology, five different multi-disciplinary areas of research can be indicated. In each of these areas, results are produced which can be in conflict with each other. In order to come up with a concept for a complete future system, these results have to be combined in a consistent and realistic, quantitative way. This paper presents the outcome of this effort. A qualitative and quantitative description is given of a complete system with a targeted time of operation within six years. As a result, the viability of a consistent and working MMC system around the targeted time (i.e. by 2005) is thereby made clear and possible future problems are indicated.

We present a newly developed strategy for automatically segmenting movies into logical story units. A logical story unit can be understood as an approximation of a movie episode, which is a high-level temporal movie segment, characterized either by a single event (dialog, action scene, etc.) or by several events taking place in parallel. Since we consider a whole event and not a single shot to be the most natural retrieval unit for the movie category of video programs, the proposed segmentation is the crucial first step toward a concise and comprehensive content-based movie representation for browsing and retrieval purposes. The automation aspect is becoming increasingly important with the rising amount of information to be processed in video archives of the future. The segmentation process is designed to work on MPEG-DC sequences, where we have taken into account that at least a partial decoding is required for performing content-based operations on MPEG compressed video streams. The proposed technique allows for carrying out the segmentation procedure in a single pass through a video sequence.

Temporal intensity flicker is a common artifact in old film sequences. Removing disturbing temporal fluctuations in image intensities is desirable because it increases both the subjective quality and, where image sequences are stored in a compressed format, the coding efficiency. We describe a robust technique that corrects intensity flicker automatically by equalizing local frame means and variances in the temporal sense. The low complexity of our method makes it suitable for hardware implementation. We tested the proposed method on sequences with artificially added intensity flicker and on original film material. The results show a great improvement.

This paper addresses the problem of segmentation of image sequences into moving objects. The segmentation (label) field is modeled by applying a Markov random field on regions provided by a watershed algorithm. The algorithm iterates between a motion estimation and a segmentation step. Temporal consistency is introduced by tracking the segmentation in time.

Software-only MPEG video compression is flexible and usually cost-effective way to generate high quality MPEG video streams. Because the encoding rate is low on general purpose processors, a parallel encoder running on a network of workstations is an attractive platform for speeding up the computation. Constant bit rate encoding and scene change handling are, however, challenging jobs in such distributed implementations. First we present a simple but effective scene change handling algorithm in which the computational load imposed by cut detection is shared among the resources. An important aspect is that our method does not increase the communication overhead in the system. Then, a two-pass bit allocation and rate control algorithm is described, which guarantees the VBV compliance of the bit streams.

This paper discusses a new technique for shape coding for mobile video communication using polar coordinates and the DCT. First the Cartesian x and y shape coordinate functions are transformed to the domain of polar coordinates yielding an r and a /spl phi/ function. Then these functions are transformed using a DCT. Using Cartesian coordinates means describing the shape in terms of straight lines and blocks, while for using polar coordinates this is in terms of circles and curves. Because of this more natural representation, compression can be more efficient and degradation due to errors or low bit rates will be more graceful. Using a spectral decomposition enables bit-rate and distortion control, error-resilience and layered coding while degrading the shape as a whole without specific local artifacts or errors. Bit allocation is possible using standard techniques and the computational load is low. A first implementation shows promising results around 1 to 2 bits per shape point, allowing an error of 2 to 1 pixels respectively.

We propose a vision model for predicting the perceptibility of coding errors in digital image sequences. Eye movements have a significant effect on distortion visibility, and hence they form an important part of the model. A modified motion estimator is used to predict the eye movements of a viewer when watching an image sequence. The spatio-temporal frequency sensitivity and masking effects are included in the model. The model is based on a decomposition of the signal into frequency and orientation bands to allow accurate modeling of spatial masking by a contrast transducer. We describe how the proposed quality measure can be used to compress image sequences using a constrained MPEG-2 encoder.

Original video signals are often corrupted by a certain amount of noise originating from the camera electronics. As a result of the gamma correction in cameras, the observed noise is signal dependent. We present a spatio-temporal order-statistic (OS) noise filter that takes into account the gamma correction in the camera. The calculation of the filter coefficients requires higher-order order-statistics (HOOS) of the noise process. We make use of a range test (RT) to determine locally from which neighboring signal values an estimate should be formed. The noise filter that we arrive at is adaptive and computationally efficient.

The most important visual artefacts that result from DCT based image compression are mosquito noise and blocking. Mosquito noise becomes visible due to the uniform spatial distribution of the quantization noise in blocks which contain textured as well as flat regions, which results in clearly visible noise in the flat regions. Spatial noise shaping is an encoder based technique which can be used to reduce mosquito noise by "hiding" the noise in that part of the block where it has the lowest visibility. We propose an efficient noise-shaping algorithm which gives accurate control of the spatial noise distribution. The encoder based technique is fully compatible with the JPEG and MPEG standards. Experiments show that noise shaping leads to a significant mosquito noise reduction.

The European Community (EC) sponsored project SMASH is investigating the needs and technological possibilities for multimedia storage device "at the home". Key frame extraction is an important preprocessing step for visual searching tools in image and video information. We describe two novel components of a key frame extraction system. Assuming that shot detection has taken place and that a frame-to-frame action measure is given, we propose a global key frame allocation method, which needs as input the user defined key frame rate, and an estimate for the average cumulative action. After assigning a number of key frames to a shot, an algorithm is proposed that distributes the key frames over the shot such that an optimal L/sub 1/ approximation of the cumulative action function is obtained.

Denoising images by means of thresholding transform coefficients has become popular. The discrete wavelet transform (DWT) seems to be very useful in this context. We propose a method for achieving a spatio-temporal decomposition of image sequences by combining the spacial Simoncelli (1992) pyramid with, in a temporal direction, wavelets. The directionally sensitive filter banks of the Simoncelli pyramid lead to better separation of signal and noise compared to a separable DWT. Including motion compensated temporal information further improves this separation. The directional sensitive filters also make it possible to locally estimate the amount of noise and the orientation of image structures. This information can be used to control the thresholding operation.

We propose a new measure of perceptual image quality based on a multiple channel human visual system (HVS) model for use in digital image compression. The model incorporates the HVS light sensitivity, spatial frequency and orientation sensitivity, and masking effects. The model is based on the concept of local band-limited contrast (LBC) in oriented spatial frequency bands. This concept leads to a simple masking function. The model has the flexibility to account for the changes in frequency sensitivity as a function of local luminance and is consistent with masking experiments using gratings and edges. Numerical scaling experiments with a test panel and a set a test images that were coded using different coding algorithms showed that the proposed measure correlates better with perceptual image quality than the conventional SNR measure.

We show how a model of the human visual system (HVS) can be used for encoder based perceptual optimization of JPEG. The HVS model takes into account the effects of light sensitivity, frequency sensitivity, and masking effects and is based on a hierarchy of oriented band pass filters. The model can be used to calculate a local frequency sensitivity, which in turn can be used to calculate perceptual weighting factors for each DCT coefficient in every block in the image. The proposed method is not limited to DCT based coders but is applicable to other coding schemes as well. The weighting factors can be used for adaptive quantization matrix design and for adaptive thresholding. We introduce a refinement of the adaptive thresholding technique that we call soft thresholding.

In this paper, a thorough review is presented of noise reduction filters for digital image sequences. Detailed descriptions of several spatiotemporal and temporal noise reduction algorithms are provided. To aid in comparing between these different algorithms, we classify them based on their support (i.e., 3-D or 1-D filter) and whether or not motion compensation is employed. Several algorithms from each of the four categories are implemented and tested on real sequences degraded to various signal-to-noise ratios. These experimental results are discussed and analyzed to determine the overall advantages and disadvantages of the four general classifications, as well as, the individual filters.>

Multiresolution transmission of compressed video is performed using subbands. Multistage quantization is necessary for efficient embedded video transmission on rate constrained channels. This paper investigates the performance of a number of multistage scalar quantization techniques: concatenated coding, conditional entropy coding and conditional quantization. Intraframe as well as interframe coding approaches are investigated with these multistage quantization techniques on high definition and standard definition source material.>

In this paper, a new spatio-temporal filtering method for removing noise from image sequences is proposed. This method combines the use of motion compensation and signal decomposition to account for the effects of object motion. Because of object motion, image sequences are temporally nonstationary, which requires the use of adaptive filters. By motion compensating the sequence prior to filtering, nonstationarities, i.e., parts of the signal that are momentarily not stationary, can be reduced significantly. However, since not all nonstationarities can be accounted for by motion, a motion-compensated signal still contains nonstationarities. An adaptive algorithm based on order statistics is described that decomposes the motion-compensated signal into a noise-free nonstationary part and a noisy stationary part. An RLS filter is then used to filter the noise from the stationary signal. Our new method is experimentally compared with various noise filtering approaches from literature.

Object based coding schemes require some kind of texture coding for the objects. We investigate fractal coding techniques for this purpose. The quadtree structure which is used as a basis for the description of object shape is also used as a framework for the fractal coding.>

Even original video sequences are often corrupted by a certain amount of noise. As a result of the gamma-correction in cameras, the observation noise is signal-dependent. We present a spatio-temporal order statistic (OS) noise-filter that takes into account the gamma-correction in the camera. This filter uses higher-order order statistics (HOOS). We make use of a range-test (RT) to determine on which signal values an estimate should be based. The noise-filter obtained in this way is adaptive and computationally efficient.>

In a spatially adaptive subsampling scheme, the subsampling lattice is adapted to the local spatial frequency content of an image sequence. In this paper, we use rate-distortion theory to show that spatially adaptive subsampling gives a better performance than subsampling with a fixed sampling lattice. A new algorithm that optimally assigns sampling lattices to different parts of the image is presented. The proposed spatially adaptive subsampling method can be applied within a motion-compensated coding scheme as well. Experiments show an increased performance over fixed lattice subsampling.

In this paper we introduce a block based vector field estimation technique which is based upon a genetic algorithm and which exploits the dual sensor nature of a stereoscopic signal in order to accelerate its convergence. This vector field estimation technique has been designed to produce smooth vector fields at a small block size without sacrificing accuracy. Conversely (false) accuracy does not impinge upon the smoothness of the vector field.

The MPEG video coding algorithm is used in a large variety of video recording applications. A key constraint for video coding algorithms for consumer (tape) recorder applications is the bit stream editability requirement; i.e., it must be possible to replace N consecutive frames by N new consecutive frames on the storage media, using at most the same number of bits. In this paper this constraint is satisfied by the use of a forward rate control mechanism, such that each group of pictures (GoP) will be encoded using a fixed number of bits (within a tolerance margin to be minimized). The problem of performing a forward state allocation (quantizer step allocation) is limited to the picture level by performing a pre-allocation, assigning a fraction of the available bits to each of the frames of a GoP. The state allocation per picture amounts to the correct selection of the quantization step size for all slices. This is done by forming parametric models for both the rate (R) and the distortion (D), such that for a particular slice, the R-D curve can be predicted. Using the R-D curves of every slice of the picture, the state allocation can be performed. With the described algorithm the GoP rate error is within 4% in the stationary mode; if a non-stationary mode that includes a re-allocation based on feedback information is added, the error is within 1%.

Compatibility among video contribution and distribution standards is becoming increasingly important due to emerging new services within broadband communication networks. A compatible video data compression system that uses nonorthogonal spatio-temporal subband decompositions is introduced. It supports a hierarchy of video standards, including both progressively scanned and interlaced signals. Simulations show that the quality of the encoded signals is mainly determined by the near-perfect behavior of the spatio-temporal filter and decimation units.>

Motion pictures have a temporal rate of 24 frames per second, while most of the conventional video displays and recording devices utilize a rate of 60 fields per second. In the case of high-definition television (HDTV) systems, some proposals in the US require a video rate of 60 frames per second. Upconversion of motion picture film to 60 frames per second is important since motion picture constitutes a high-quality source material for HDTV. The authors address the problem of motion-compensated upconversion of 24 frames/s digitized motion pictures to 60 frames/s digital video signals.>

A new block-adaptive image identification and restoration method for images degraded by slowly varying blurs is described. Essentially, the proposed method assumes that the blur is stationary within a small subimage, and locally identifies the image and blurs parameters. The iterative expectation-maximization (EM) image identification-restoration algorithm is used in a semi-recursive manner to identify and restore overlapping subimages.>

Two intraframe hierarchical coding schemes based on a subband coding strategy are proposed for the broadband integrated services digital network (BISDN). High-definition TV (HDTV) and extended-quality TV (EQTV) coexist on the network. The two schemes presented code the HDTV signal for the 135 Mb/s channel, while the EQTV signal is coded for the 45 Mb/s subchannel. A theoretical analysis of hierarchical coding shows that if the EQTV signal is coded first and the HDTV signal is coded next, it is possible to obtain two optimally coded signal. This is realized in the first hierarchical coding scheme: the refinement system. An alternative for the refinement system is the selection system, which optimally codes the HDTV signal only, but has a simpler coding structure. The higher complexity of the refinement system results in higher-quality EQTV.>

A hierarchical blur identification method which is able to identify severe blurs having a relatively large support size is proposed. The method is based on the expectation-maximization algorithm and begins by identifying a low-pass version of the point-spread function (PSF) from a reduced-resolution version of the blurred image. The result is used to initialize the identification of the PSF from a higher-resolution image. By repeating this process, the support size and resolution of the identified PSF are gradually increased, achieving an efficient identification of large PSFs.>

The Broadband Integrated Services Digital Network (BISDN) based on lightwave technology is supposed to become the all-purpose exchange area communications network of the future. All digital video services are integrated with applications ranging from videophone, teleconferencing to digital TV (signals according to the CCIR rec. 601) and High Definition TV (HDTV) distribution. A desirable feature of the various video services is the upward and downward compatibility in resolution in order to guarantee a free exchange of services, transmitters and receivers. This paper proposes an n-level progressive hierachical intraframe coding scheme based on subband coding. In this scheme several spatial low-resolution services are available as subsets of the coded HDTV data which can directly be received at lower bit rates. Progressive coding of the HDTV signal is employed in order to prevent quantization errors from propagating to higher resolution signals. Special attention is given to the design of the quantizers required for the progressive coding, and to the incorporation of the side panels coding.

In this paper we discuss the use of maximum likelihood estimation procedures for the identification of unknowns blur from a blurred image. The main focus will be on the problem of estimating the coefficients of relatively large point-spread functions, and the estimation of the support size of point-spread functions in general. Two improved blur identification techniques are proposed which are both based on the expectation- maximization algorithm. In the first method we describe the point-spread function by a parametric model, while in the second method resolution pyramids are employed to identify the point-spread function in a hierarchical manner.

The authors present a maximum-likelihood blur identification method, which estimates the required parameters from the observed noisy blurred image itself, and use the expectation-maximization algorithm to solve the resulting complicated problem of optimizing the likelihood function. A priori information about the unknown parameters in the form of initial conditions and parametric image and blur models are incorporated to make the algorithm applicable to realistic blurs and to improve the identification results. Experimental results are presented on a 256 pixel*256 pixel synthetically blurred by a 2-D Gaussian point spread function with various standard deviations. The approach results in a flexible iterative algorithm that is computationally far more efficient than directly optimizing the likelihood function.>

In [1] a regularized iterative algorithm was described which has been shown to be very suitable for solving the ill-posed image restoration problem. By incorporating deterministic constraints and adaptivity this very general algorithm is capable of achieving both noise suppression and ringing reduction in the restoration process. It consumes, however, considerable computation to obtain a (visually) stable solution due to the low convergence speed of the algorithm. The purpose of this paper is to investigate the possibilities for speeding up the convergence of this restoration method. To this end we compare the classical steepest descent algorithm (with linear convergence) with a conjugate gradients based method (superlinear convergence) and a new Q-th order converging algorithm. The latter solution method has the highest convergence rate, but is restricted in its application to space-invariant image restoration with a linear constraint. Although the actual convergence speed of the algorithms involved generally depends on the image data to be restored, it will be shown that for real-life images the constrained conjugate gradients algorithm yields a considerable convergence speed improvement.

A regularized iterative algorithm is described which solves the ill-posed image restoration problem in a numerically stable way by incorporating a priori knowledge about the original image. Three kinds of a priori knowledge are used: the first type imposes an upperbound on the residual signal, and the second type restricts the high-frequency content of the (restored) signal. We show that by the use of weighted norms in defining the above-mentioned types of a priori knowledge the algorithm concentrates on restoration in the vicinity of edges, and on noise suppression in flat regions. In this way the algorithm is capable of handling spatially varying image statistics in a pleasing manner for the human observer. The third kind of a priori knowledge is a deterministic constraint, representing a closed convex set in the solution space. The convergence and the limiting solution of the proposed algorithm are established. In order to show the significance of our approach we present some preliminary experimental results.