29826505
Enhancing DPF for near-replica image recognition
Dynamic Partial Function (DPF), which dynamically selects a subset of features to measure pairwise image similarity, has been shown to be very effective in near-replica image recognition. DPF, however, suffers from the one-size-fits-all problem: it requires that all pairwise similarity measurements must use the same number of features. We propose methods for enhancing DPF's performance by allowing different numbers of features to be selected in a pairwise manner. Through extensive empirical studies, we show that our three schemes: thresholding, sampling and weighting, and hybrid schemes of these three basic approaches, substantially outperform DPF in near-replica image recognition.
18150673
The anatomy of a multimodal information filter
The proliferation of objectionable information on the Internet has reached a level of serious concern. To empower end-users with the choice of blocking undesirable and offensive websites, we propose a multimodal information filter, named MORF. In this paper, we present MORF's core components: its confidence-based classifier, a Cross-bagging ensemble scheme, and multimodal classification algorithm. Empirical studies and initial statistics collected from the MORF filters deployed at sites in the U.S. and Asia show that MORF is both efficient and effective, due to our classification methods.
9408458
PBIR-MM: multimodal image retrieval and annotation
We demonstrate PBIR-MM, an integrated system that we have built for conducting multimodal image retrieval. The system combines the strengths of content-based soft annotation (CBSA), multimodal relevance feedback through active learning, and perceptual distance formulation and indexing. PBIR-MM supports multimodal query and annotation in any combination of its three basic modes: seed-by-nothing, seed-by-keywords, and seed-by-content. We demonstrate PBIR-MM on a couple of very large image sets provided by image vendors and crawled from the Internet.
7236137
Efficient top-k hyperplane query processing for multimedia information retrieval
A query can be answered by a binary classifier, which separates the instances that are relevant to the query from the ones that are not. When kernel methods are employed to train such a classifier, the class boundary is represented as a hyperplane in a projected space. Data instances that are farthest from the hyperplane are deemed to be most relevant to the query, and that are nearest to the hyperplane to be most uncertain to the query. In this paper, we address the twin problems of efficient retrieval of the approximate set of instances (a) farthest from and (b) nearest to a query hyperplane. Retrieval of instances for this hyperplane-based query scenario is mapped to the range-query problem allowing for the reuse of existing index structures. Empirical evaluation on large image datasets confirms the effectiveness of our approach.
2439726
Concept boundary detection for speeding up SVMs
Support Vector Machines (SVMs) suffer from an O(n2) training cost, where n denotes the number of training instances. In this paper, we propose an algorithm to select boundary instances as training data to substantially reduce n. Our proposed algorithm is motivated by the result of (Burges, 1999) that, removing non-support vectors from the training set does not change SVM training results. Our algorithm eliminates instances that are likely to be non-support vectors. In the concept-independent preprocessing step of our algorithm, we prepare nearest-neighbor lists for training instances. In the concept-specific sampling step, we can then effectively select useful training data for each target concept. Empirical studies show our algorithm to be effective in reducing n, outperforming other competing downsampling algorithms without significantly compromising testing accuracy.
10743717
Support vector machine active learning for image retrieval
Relevance feedback is often a critical component when designing image databases. With these databases it is difficult to specify queries directly and explicitly. Relevance feedback interactively determinines a user's desired output or query concept by asking the user whether certain proposed images are relevant or not. For a relevance feedback algorithm to be effective, it must grasp a user's query concept accurately and quickly, while also only asking the user to label a small number of images. We propose the use of a support vector machine active learning algorithm for conducting effective relevance feedback for image retrieval. The algorithm selects the most informative images to query a user and quickly learns a boundary that separates the images that satisfy the user's query concept from the rest of the dataset. Experimental results show that our algorithm achieves significantly higher search accuracy than traditional query refinement schemes after just three to four rounds of relevance feedback.
1511497
On the Possibility of Non-invertible Watermarking Schemes
Recently, there are active discussions on the possibility of non-invertible watermarking scheme. A non-invertible scheme prevents an attacker from deriving a valid watermark from a cover work. Recent results suggest that it is difficult to design a provably secure non-invertible scheme. In contrast, in this paper, we show that it is possible. We give a scheme based on a cryptographically secure pseudo-random number generator (CSPRNG) and show that it is secure with respect to well-accepted notion of security. We employ the spread spectrum method as the underlying watermarking scheme to embed the watermark. The parameters chosen for the underlying scheme give reasonable robustness, false alarm and distortion. We prove the security by showing that, if there is a successful attacker, then there exists a probabilistic polynomial-time algorithm that can distinguish the uniform distribution from sequences generated by the CSPRNG, and thus contradicts the assumption that the CSPRNG is secure. Furthermore, in our scheme the watermark is statistically independent from the original work, which shows that it is not necessary to enforce a relationship between them to achieve non-invertibility.
14264886
Geometric properties of watermarking schemes
A variety of image watermarking schemes have been proposed using orthogonal transformations, projections, and coding techniques to embed imperceptible watermarks into images. Analytical studies of the watermarking problem have typically been based on studying the performance limits of these known algorithms. In contrast, this paper formalizes the watermarking problem in an "algorithm independent" framework, representing any watermarking algorithm as a partition of the image space into a collection of sets, and defining requirements of these sets that must be met by any solution to the watermarking problem. Specifically, these requirements define and constrain the false-alarm ratio, distortion, robustness and security of a watermarking system. Using this formalism, we first characterize common features of algorithms that solve the watermarking problem. We show how the requirements defined earlier force important differences between watermarking signal sets and classical communication systems signal sets. Next, we show how common components of existing watermarking algorithms (e.g. transformations, projections, and coding) can be associated with specific requirements of the watermarking definition. Finally, we show how our new formalism of the watermarking problem provides a procedure for optimal design of watermarking systems to target specified false-alarm, distortion, and robustness objectives.
9658544
Effect of Malicious Synchronization
We study the impact of malicious synchronization on computer systems that serve customers periodically. Systems supporting automatic periodic updates are common in web servers providing regular news update, sports scores or stock quotes. Our study focuses on the possibility of launching an effective low rate attack on the server to degrade performance measured in terms of longer processing time and request drops due to timeouts. The attackers are assumed to behave like normal users and send one request per update cycle. The only parameter utilized in the attack is the timing of the requests sent. By exploiting the periodic nature of the updates, a small number of attackers can herd users' update requests to a cluster and arrive in a short period of time. Herding can be used to discourage new users from joining the system and to modify the user arrival distribution, so that the subsequent burst attack will be effective. While the herding based attacks can be launched with a small amount of resource, they can be easily prevented by adding a small random component to the length of the update interval.
1227971
Rotation of foveated image in the wavelet domain
An advantage of wavelet transform is its efficiency in representing natural images, that is, a natural image can be accurately represented by only a small number of retained wavelet coefficients. It is interesting to know whether some common image operations, e.g., rotation, can be performed very fast in wavelet domain. Preferably, the running time should depend only on the number of retained coefficients, not the size of the original image. However, it is not clear how this can be achieved. In this paper, we consider rotation and images with a special structure: foveated images. Wavelet coefficients of a foveated image vanish outside an arrangement of circles. We exploit this structure to derive algorithms that accurately approximate rotation. The running time is /spl Theta/(m) where m is the number of retained coefficients. Experiments show the accuracy of the approximation.
31284444
Error Resilient Image Authentication Using Feature Statistical and Spatial Properties
The pervasive distribution of digital images triggers an emergent need of authenticating degraded images by lossy compression and transmission. This paper proposes a robust content-based image authentication scheme for image transmissions over lossy channels. Content-based image authentication typically assesses authenticity based on a distance measure of feature differences between the testing image and its original. Commonly employed distance measures such as the Minkowski measures may not be adequate for content-based image authentication since they do not exploit statistical and spatial properties of the feature differences. This proposed error resilient scheme is based on a statistics- and spatiality-based measure (SSM) of feature differences. This measure is motivated by an observation that most malicious manipulations are localized whereas acceptable manipulations cause global distortions. Experimental results show that SSM is better than previous used measures in distinguishing malicious manipulations from acceptable ones, and the proposed SSM-based scheme is robust to transmission errors and other acceptable manipulations, and is sensitive malicious image modifications.