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.
42674644
Shortest Path amidst Disc Obstacles Is Computable
An open question in Exact Geometric Computation is whether there are transcendental computations that can be made "geometrically exact". Perhaps the simplest such problem in computational geometry is that of computing the shortest obstacle-avoiding path between two points p,q in the plane, where the obstacles are a collection of n discs. This problem can be solved in O(n2log n) time in the Real RAM model, but nothing was known about its computability in the standard (Turing) model of computation. We first give a direct proof of the Turing-computability of this problem, provided the radii of the discs are rationally related. We make the usual assumption that the numerical input data are real algebraic numbers. By appealing to effective bounds from transcendental number theory, we further show a single-exponential time upper bound when the input numbers are rational. Our result appears to be the first example of a non-algebraic combinatorial problem which is shown computable. It is also a rare example of transcendental number theory yielding positive computational results.
6661888
A wavelet approach to foveating images
Motivated by applications of foveated images in visualization, we introduce the foveation transform of an image. We study the basic properties of these transforms using the multiresolution framework of Mallat. We also consider practical methods of realizing such transforms. In particular, we introduce a new method for foveating images based on wavelets. Preliminary experimental results are shown.
3079245
Statistics- and Spatiality-Based Feature Distance Measure for Error Resilient Image Authentication
Content-based image authentication typically assesses authenticity based on a distance measure between the image to be tested and its original. Commonly employed distance measures such as the Minkowski measures (including Hamming and Euclidean distances) may not be adequate for content-based image authentication since they do not exploit statistical and spatial properties in features. This paper proposes a feature distance measure for content-based image authentication based on statistical and spatial properties of the feature differences. The proposed statistics- and spatiality-based measure (SSM) is motivated by an observation that most malicious manipulations are localized whereas acceptable manipulations result in global distortions. A statistical measure, kurtosis, is used to assess the shape of the feature difference distribution; a spatial measure, the maximum connected component size, is used to assess the degree of object concentration of the feature differences. The experimental results have confirmed that our proposed measure is better than previous measures in distinguishing malicious manipulations from acceptable ones.
11249256
A unified framework for resolving ambiguity in copy detection
Copy detection is an important component of digital rights management and can be implemented using a retrieval-based approach. Under this approach, a query image, suspected to be a copy, is compared against all the images in the owner database. The comparison is done based on a distance metric in feature space. The performance of such a system depends on the mutual separation of the feature representation of the images in the database. In this paper we propose a framework that increases this mutual separation by literally shifting them away from each other. The idea of modifying the features derives its inspiration from the field of watermarking. It is also important to make sure that the semantics of the images do not change after modification. Thus the focus of this paper is on how to modify the images in the database, so that the mutual separation between the images in feature space is above a certain threshold and the distortion induced is minimized. This problem can be formulated as a non-convex optimization problem which is difficult to solve. We propose a restriction of the problem and solve it using second-order cone programming. We present a practical implementation of our framework, named RAM, which uses AFMT as the feature representation. We conduct experiments to test the performance of RAM.
2005681
Hiding Secret Points Amidst Chaff
Motivated by the representation of biometric and multimedia objects, we consider the problem of hiding noisy point-sets using a secure sketch. A point-set X consists of s points from a d-dimensional discrete domain [0,N – 1]d. Under permissible noises, for every point $\left \langle x_1,..,x_d\right \rangle \in X$, each xi may be perturbed by a value of at most δ. In addition, at most t points in X may be replaced by other points in [0,N – 1]d. Given an original X, we want to compute a secure sketch P. A known method constructs the sketch by adding a set of random points R, and the description of (X∪R) serves as part of the sketch. However, the dependencies among the random points are difficult to analyze, and there is no known non-trivial bound on the entropy loss. In this paper, we first give a general method to generate R and show that the entropy loss of (X∪R) is at most s(dlogΔ+ d + 0.443), where Δ= 2δ+1. We next give improved schemes for d = 1, and special cases for d = 2. Such improvements are achieved by pre-rounding, and careful partition of the domains into cells. It is possible to make our sketch short, and avoid using randomness during construction. We also give a method in d = 1 to demonstrate that, using the size of R as the security measure would be misleading.
36612364
Learning image query concepts via intelligent sampling
In this paper, we propose an active and inductive combined learning method to learn users’ image query concepts. We model query concepts in -CNF, which can be used to express most practical queries. To learn a user’s query concept, we propose MEGA. MEGA initializes a user’s query concept as the conjunction of all disjunctions of at most length of the predicates. It then intelligently selects unlabeled data to present to the user for gathering information to eliminate the maximum expected number of disjunctions. MEGA maximizes the usefulness of each example it generates for learning a user’s query concept and hence expedites the convergence to the target concept. Through analysis and experiments, we show that MEGA can learn a complex image query concept much faster than some traditional schemes.
1261712
Learning the unified kernel machines for classification
Kernel machines have been shown as the state-of-the-art learning techniques for classification. In this paper, we propose a novel general framework of learning the Unified Kernel Machines (UKM) from both labeled and unlabeled data. Our proposed framework integrates supervised learning, semi-supervised kernel learning, and active learning in a unified solution. In the suggested framework, we particularly focus our attention on designing a new semi-supervised kernel learning method, i.e., Spectral Kernel Learning (SKL), which is built on the principles of kernel target alignment and unsupervised kernel design. Our algorithm is related to an equivalent quadratic programming problem that can be efficiently solved. Empirical results have shown that our method is more effective and robust to learn the semi-supervised kernels than traditional approaches. Based on the framework, we present a specific paradigm of unified kernel machines with respect to Kernel Logistic Regresions (KLR), i.e., Unified Kernel Logistic Regression (UKLR). We evaluate our proposed UKLR classification scheme in comparison with traditional solutions. The promising results show that our proposed UKLR paradigm is more effective than the traditional classification approaches.
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.
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.
6932749
Adaptive stream resource management using Kalman Filters
To answer user queries efficiently, a stream management system must handle continuous, high-volume, possibly noisy, and time-varying data streams. One major research area in stream management seeks to allocate resources (such as network bandwidth and memory) to query plans, either to minimize resource usage under a precision requirement, or to maximize precision of results under resource constraints. To date, many solutions have been proposed; however, most solutions are ad hoc with hard-coded heuristics to generate query plans. In contrast, we perceive stream resource management as fundamentally a filtering problem, in which the objective is to filter out as much data as possible to conserve resources, provided that the precision standards can be met. We select the Kalman Filter as a general and adaptive filtering solution for conserving resources. The Kalman Filter has the ability to adapt to various stream characteristics, sensor noise, and time variance. Furthermore, we realize a significant performance boost by switching from traditional methods of caching static data (which can soon become stale) to our method of caching dynamic procedures that can predict data reliably at the server without the clients' involvement. In this work we focus on minimization of communication overhead for both synthetic and real-world streams. Through examples and empirical studies, we demonstrate the flexibility and effectiveness of using the Kalman Filter as a solution for managing trade-offs between precision of results and resources in satisfying stream queries.