OpenRaiser/Intern-Atlas huggingface dataset:
Detection of copy-move forgery in digital images based on DCT
Venue: arXiv cs.CV 2013
Year: 2013

With rapid advances in digital information processing systems, and more specifically in digital image processing software, there is a widespread development of advanced tools and techniques for digital image forgery. One of the techniques most commonly used is the Copy-move forgery which proceeds by copying a part of an image and pasting it into the same image, in order to maliciously hide an object or a region. In this paper, we propose a method to detect this specific kind of counterfeit. Firstly, the color image is converted from RGB color space to YCbCr color space and then the R, G, B and Y-component are splitted into fixed-size overlapping blocks and, features are extracted from the R, G and B-components image blocks on one hand and on the other, from the DCT representation of the R, G, B and Ycomponent image block. The feature vectors obtained are then lexicographically sorted to make similar image blocks neighbors and duplicated image blocks are identified using Euclidean distance as similarity criterion. Experimental results showed that the proposed method can detect the duplicated regions when there is more than one copy move forged area in the image and even in case of slight rotations, JPEG compression, shift, scale, blur and noise addition.
Further Results on Permutation Polynomials over Finite Fields
Venue: arXiv cs.IT 2013
Year: 2013

Permutation polynomials are an interesting subject of mathematics and have applications in other areas of mathematics and engineering. In this paper, we develop general theorems on permutation polynomials over finite fields. As a demonstration of the theorems, we present a number of classes of explicit permutation polynomials on $\gf_q$.
Backhaul-Aware Interference Management in the Uplink of Wireless Small Cell Networks
Venue: arXiv cs.NI 2013
Year: 2013

The design of distributed mechanisms for interference management is one of the key challenges in emerging wireless small cell networks whose backhaul is capacity limited and heterogeneous (wired, wireless and a mix thereof). In this paper, a novel, backhaul-aware approach to interference management in wireless small cell networks is proposed. The proposed approach enables macrocell user equipments (MUEs) to optimize their uplink performance, by exploiting the presence of neighboring small cell base stations. The problem is formulated as a noncooperative game among the MUEs that seek to optimize their delay-rate tradeoff, given the conditions of both the radio access network and the -- possibly heterogeneous -- backhaul. To solve this game, a novel, distributed learning algorithm is proposed using which the MUEs autonomously choose their optimal uplink transmission strategies, given a limited amount of available information. The convergence of the proposed algorithm is shown and its properties are studied. Simulation results show that, under various types of backhauls, the proposed approach yields significant performance gains, in terms of both average throughput and delay for the MUEs, when compared to existing benchmark algorithms.
Affordable Virtual Reality System Architecture for Representation of Implicit Object Properties
Venue: arXiv cs.GR 2013
Year: 2013

A flexible, scalable and affordable virtual reality software system architecture is proposed. This solution can be easily implemented on different hardware configurations: on a single computer or on a computer cluster. The architecture is aimed to be integrated in the workflow for solving engineering tasks and oriented towards presenting implicit object properties through multiple sensorial channels (visual, audio and haptic). Implicit properties represent hidden object features (i.e. magnetization, radiation, humidity, toxicity, etc.) which cannot be perceived by the observer through his or her senses but require specialized equipment in order to expand the sensory ability of the observer. Our approach extends the underlying general scene graph structure incorporating additional effects nodes for implicit properties representation.
Thue's 1914 paper: a translation
Venue: arXiv cs.FL 2013
Year: 2013

This paper includes notes to accompany a reading of Thue's 1914 paper "Probleme uber Veranderungen von Zeichenreihen nach gegebenen Reglen", along with a translation of that paper. Thue's 1914 paper is mainly famous for proving an early example of an undecidable problem, cited prominently by Post. However, Post's paper principally makes use of the definition of Thue systems, described on the first two pages of Thue's paper, and does not depend on the more specific results in the remainder of Thue's paper. A closer study of the remaining parts of that paper highlight a number of important themes in the history of computing: the transition from algebra to formal language theory, the analysis of the "computational power" (in a pre-1936 sense) of rules, and the development of algorithms to generate rule-sets.
A Survey and Taxonomy of Graph Sampling
Venue: arXiv cs.SI 2013
Year: 2013

Graph sampling is a technique to pick a subset of vertices and/ or edges from original graph. It has a wide spectrum of applications, e.g. survey hidden population in sociology [54], visualize social graph [29], scale down Internet AS graph [27], graph sparsification [8], etc. In some scenarios, the whole graph is known and the purpose of sampling is to obtain a smaller graph. In other scenarios, the graph is unknown and sampling is regarded as a way to explore the graph. Commonly used techniques are Vertex Sampling, Edge Sampling and Traversal Based Sampling. We provide a taxonomy of different graph sampling objectives and graph sampling approaches. The relations between these approaches are formally argued and a general framework to bridge theoretical analysis and practical implementation is provided. Although being smaller in size, sampled graphs may be similar to original graphs in some way. We are particularly interested in what graph properties are preserved given a sampling procedure. If some properties are preserved, we can estimate them on the sampled graphs, which gives a way to construct efficient estimators. If one algorithm relies on the perserved properties, we can expect that it gives similar output on original and sampled graphs. This leads to a systematic way to accelerate a class of graph algorithms. In this survey, we discuss both classical text-book type properties and some advanced properties. The landscape is tabularized and we see a lot of missing works in this field. Some theoretical studies are collected in this survey and simple extensions are made. Most previous numerical evaluation works come in an ad hoc fashion, i.e. evaluate different type of graphs, different set of properties, and different sampling algorithms. A systematical and neutral evaluation is needed to shed light on further graph sampling studies.
Generalized Perron--Frobenius Theorem for Nonsquare Matrices
Venue: arXiv cs.NA 2013
Year: 2013

The celebrated Perron--Frobenius (PF) theorem is stated for irreducible nonnegative square matrices, and provides a simple characterization of their eigenvectors and eigenvalues. The importance of this theorem stems from the fact that eigenvalue problems on such matrices arise in many fields of science and engineering, including dynamical systems theory, economics, statistics and optimization. However, many real-life scenarios give rise to nonsquare matrices. A natural question is whether the PF Theorem (along with its applications) can be generalized to a nonsquare setting. Our paper provides a generalization of the PF Theorem to nonsquare matrices. The extension can be interpreted as representing client-server systems with additional degrees of freedom, where each client may choose between multiple servers that can cooperate in serving it (while potentially interfering with other clients). This formulation is motivated by applications to power control in wireless networks, economics and others, all of which extend known examples for the use of the original PF Theorem. We show that the option of cooperation between servers does not improve the situation, in the sense that in the optimal solution no cooperation is needed, and only one server needs to serve each client. Hence, the additional power of having several potential servers per client translates into \emph{choosing} the best single server and not into \emph{sharing} the load between the servers in some way, as one might have expected. The two main contributions of the paper are (i) a generalized PF Theorem that characterizes the optimal solution for a non-convex nonsquare problem, and (ii) an algorithm for finding the optimal solution in polynomial time.
Improving Sparse Associative Memories by Escaping from Bogus Fixed Points
Venue: arXiv cs.NE 2013
Year: 2013

The Gripon-Berrou neural network (GBNN) is a recently invented recurrent neural network embracing a LDPC-like sparse encoding setup which makes it extremely resilient to noise and errors. A natural use of GBNN is as an associative memory. There are two activation rules for the neuron dynamics, namely sum-of-sum and sum-of-max. The latter outperforms the former in terms of retrieval rate by a huge margin. In prior discussions and experiments, it is believed that although sum-of-sum may lead the network to oscillate, sum-of-max always converges to an ensemble of neuron cliques corresponding to previously stored patterns. However, this is not entirely correct. In fact, sum-of-max often converges to bogus fixed points where the ensemble only comprises a small subset of the converged state. By taking advantage of this overlooked fact, we can greatly improve the retrieval rate. We discuss this particular issue and propose a number of heuristics to push sum-of-max beyond these bogus fixed points. To tackle the problem directly and completely, a novel post-processing algorithm is also developed and customized to the structure of GBNN. Experimental results show that the new algorithm achieves a huge performance boost in terms of both retrieval rate and run-time, compared to the standard sum-of-max and all the other heuristics.
Brain MRI Segmentation with Fast and Globally Convex Multiphase Active Contours
Venue: arXiv cs.CV 2013
Year: 2013

Multiphase active contour based models are useful in identifying multiple regions with different characteristics such as the mean values of regions. This is relevant in brain magnetic resonance images (MRIs), allowing the differentiation of white matter against gray matter. We consider a well defined globally convex formulation of Vese and Chan multiphase active contour model for segmenting brain MRI images. A well-established theory and an efficient dual minimization scheme are thoroughly described which guarantees optimal solutions and provides stable segmentations. Moreover, under the dual minimization implementation our model perfectly describes disjoint regions by avoiding local minima solutions. Experimental results indicate that the proposed approach provides better accuracy than other related multiphase active contour algorithms even under severe noise, intensity inhomogeneities, and partial volume effects.
ELB-Trees, An Efficient and Lock-free B-tree Derivative
Venue: arXiv cs.DS 2013
Year: 2013

This technical report is an extension of the paper of the same title, which is to appear at MUCOCOS'13. The technical report proves correctness of the ELB-trees operations' semantics and that the operations are lock-free.
Implementation and optimization of Wavelet modulation in Additive Gaussian channels
Venue: arXiv cs.OH 2013
Year: 2013

In this paper, we investigate the implementation of wavelet modulation (WM) in a digital communication system and propose novel methods to improve its performance. We will put particular focus on the structure of an optimal detector in AWGN channels and address two main methods for inserting the samples of the message signal in different frequency layers. Finally, computer based algorithms are described in order to implement and optimize receivers and transmitters.
Crowdsourcing a Word-Emotion Association Lexicon
Venue: arXiv cs.CL 2013
Year: 2013

Even though considerable attention has been given to the polarity of words (positive and negative) and the creation of large polarity lexicons, research in emotion analysis has had to rely on limited and small emotion lexicons. In this paper we show how the combined strength and wisdom of the crowds can be used to generate a large, high-quality, word-emotion and word-polarity association lexicon quickly and inexpensively. We enumerate the challenges in emotion annotation in a crowdsourcing scenario and propose solutions to address them. Most notably, in addition to questions about emotions associated with terms, we show how the inclusion of a word choice question can discourage malicious data entry, help identify instances where the annotator may not be familiar with the target term (allowing us to reject such annotations), and help obtain annotations at sense level (rather than at word level). We conducted experiments on how to formulate the emotion-annotation questions, and show that asking if a term is associated with an emotion leads to markedly higher inter-annotator agreement than that obtained by asking if a term evokes an emotion.
Categorizing ancient documents
Venue: arXiv cs.CV 2013
Year: 2013

The analysis of historical documents is still a topical issue given the importance of information that can be extracted and also the importance given by the institutions to preserve their heritage. The main idea in order to characterize the content of the images of ancient documents after attempting to clean the image is segmented blocks texts from the same image and tries to find similar blocks in either the same image or the entire image database. Most approaches of offline handwriting recognition proceed by segmenting words into smaller pieces (usually characters) which are recognized separately. Recognition of a word then requires the recognition of all characters (OCR) that compose it. Our work focuses mainly on the characterization of classes in images of old documents. We use Som toolbox for finding classes in documents. We applied also fractal dimensions and points of interest to categorize and match ancient documents.
New bounds for circulant Johnson-Lindenstrauss embeddings
Venue: arXiv cs.IT 2013
Year: 2013

This paper analyzes circulant Johnson-Lindenstrauss (JL) embeddings which, as an important class of structured random JL embeddings, are formed by randomizing the column signs of a circulant matrix generated by a random vector. With the help of recent decoupling techniques and matrix-valued Bernstein inequalities, we obtain a new bound $k=O(ε^{-2}\log^{(1+δ)} (n))$ for Gaussian circulant JL embeddings. Moreover, by using the Laplace transform technique (also called Bernstein's trick), we extend the result to subgaussian case. The bounds in this paper offer a small improvement over the current best bounds for Gaussian circulant JL embeddings for certain parameter regimes and are derived using more direct methods.
Oracle Tractability of Skew Bisubmodular Functions
Venue: arXiv cs.CC 2013
Year: 2013

In this paper we consider skew bisubmodular functions as introduced in [9]. We construct a convex extension of a skew bisubmodular function which we call Lovász extension in correspondence to the submodular case. We use this extension to show that skew bisubmodular functions given by an oracle can be minimised in polynomial time.
Beating O(nm) in approximate LZW-compressed pattern matching
Venue: arXiv cs.DS 2013
Year: 2013

Given an LZW/LZ78 compressed text, we want to find an approximate occurrence of a given pattern of length m. The goal is to achieve time complexity depending on the size n of the compressed representation of the text instead of its length. We consider two specific definitions of approximate matching, namely the Hamming distance and the edit distance, and show how to achieve O(nm^0.5k^2) and O(nm^0.5k^3) running time, respectively, where k is the bound on the distance. Both algorithms use just linear space. Even for very small values of k, the best previously known solutions required O(nm) time. Our main contribution is applying a periodicity-based argument in a way that is computationally effective even if we need to operate on a compressed representation of a string, while the previous solutions were either based on a dynamic programming, or a black-box application of tools developed for uncompressed strings.
On the Effectiveness of Punishments in a Repeated Epidemic Dissemination Game
Venue: arXiv cs.DC 2013
Year: 2013

This work uses Game Theory to study the effectiveness of punishments as an incentive for rational nodes to follow an epidemic dissemination protocol. The dissemination process is modeled as an infinite repetition of a stage game. At the end of each stage, a monitoring mechanism informs each player of the actions of other nodes. The effectiveness of a punishing strategy is measured as the range of values for the benefit-to-cost ratio that sustain cooperation. This paper studies both public and private monitoring. Under public monitoring, we show that direct reciprocity is not an effective incentive, whereas full indirect reciprocity provides a nearly optimal effectiveness. Under private monitoring, we identify necessary conditions regarding the topology of the graph in order for punishments to be effective. When punishments are coordinated, full indirect reciprocity is also effective with private monitoring.
Expand and Contract: Sampling graphs with given degrees and other combinatorial families
Venue: arXiv cs.DS 2013
Year: 2013

Sampling from combinatorial families can be difficult. However, complicated families can often be embedded within larger, simpler ones, for which easy sampling algorithms are known. We take advantage of such a relationship to describe a sampling algorithm for the smaller family, via a Markov chain started at a random sample of the larger family. The utility of the method is demonstrated via several examples, with particular emphasis on sampling labelled graphs with given degree sequence, a well-studied problem for which existing algorithms leave much room for improvement. For graphs with given degrees, with maximum degree $O(m^{1/4})$ where $m$ is the number of edges, we obtain an asymptotically uniform sample in $O(m)$ steps, which substantially improves upon existing algorithms.
Efficiently Listing Combinatorial Patterns in Graphs
Venue: arXiv cs.DS 2013
Year: 2013

Graphs are extremely versatile and ubiquitous mathematical structures with potential to model a wide range of domains. For this reason, graph problems have been of interest since the early days of computer science. Some of these problems consider substructures of a graph that have certain properties. These substructures of interest, generally called patterns, are often meaningful in the domain being modeled. Classic examples of patterns include spanning trees, cycles and subgraphs. This thesis focuses on the topic of explicitly listing all the patterns existing in an input graph. One of the defining features of this problem is that the number of patterns is frequently exponential on the size of the input graph. Thus, the time complexity of listing algorithms is parameterized by the size of the output. The main contribution of this work is the presentation of optimal algorithms for four different problems of listing patterns in graphs, namely the listing of k-subtrees, k-subgraphs, st-paths and cycles. The algorithms presented are framed within the same generic approach, based in a recursive partition of the search space that divides the problem into subproblems. The key to an efficient implementation of this approach is to avoid recursing into subproblems that do not list any patterns. With this goal in sight, a dynamic data structure, called the certificate, is introduced and maintained throughout the recursion. Moreover, properties of the recursion tree and lower bounds on the number of patterns are used to amortize the cost of the algorithm on the size of the output.
Transforming planar graph drawings while maintaining height
Venue: arXiv cs.CG 2013
Year: 2013

There are numerous styles of planar graph drawings, notably straight-line drawings, poly-line drawings, orthogonal graph drawings and visibility representations. In this note, we show that many of these drawings can be transformed from one style to another without changing the height of the drawing. We then give some applications of these transformations.
Balancedness of Arnoux-Rauzy and Brun words
Venue: arXiv cs.FL 2013
Year: 2013

We study balancedness properties of words given by the Arnoux-Rauzy and Brun multi-dimensional continued fraction algorithms. We show that almost all Brun words on 3 letters and Arnoux-Rauzy words over arbitrary alphabets are finitely balanced; in particular, boundedness of the strong partial quotients implies balancedness. On the other hand, we provide examples of unbalanced Brun words on 3 letters.
Caching Gain in Wireless Networks with Fading: A Multi-User Diversity Perspective
Venue: arXiv cs.IT 2013
Year: 2013

We consider the effect of caching in wireless networks where fading is the dominant channel effect. First, we propose a one-hop transmission strategy for cache-enabled wireless networks, which is based on exploiting multi-user diversity gain. Then, we derive a closed-form result for throughput scaling of the proposed scheme in large networks, which reveals the inherent trade-off between cache memory size and network throughput. Our results show that substantial throughput improvements are achievable in networks with sources equipped with large cache size. We also verify our analytical result through simulations.
A Robust Alternating Direction Method for Constrained Hybrid Variational Deblurring Model
Venue: arXiv cs.CV 2013
Year: 2013

In this work, a new constrained hybrid variational deblurring model is developed by combining the non-convex first- and second-order total variation regularizers. Moreover, a box constraint is imposed on the proposed model to guarantee high deblurring performance. The developed constrained hybrid variational model could achieve a good balance between preserving image details and alleviating ringing artifacts. In what follows, we present the corresponding numerical solution by employing an iteratively reweighted algorithm based on alternating direction method of multipliers. The experimental results demonstrate the superior performance of the proposed method in terms of quantitative and qualitative image quality assessments.
Categorizing Influential Authors Using Penalty Areas
Venue: arXiv cs.DL 2013
Year: 2013

The concept of h-index has been proposed to easily assess a researcher's performance with a single two-dimensional number. However, by using only this single number, we lose significant information about the distribution of the number of citations per article of an author's publication list. Two authors with the same h-index may have totally different distributions of the number of citations per article. One may have a very long "tail" in the citation curve, i.e. he may have published a great number of articles, which did not receive relatively many citations. Another researcher may have a short tail, i.e. almost all his publications got a relatively large number of citations. In this article, we study an author's citation curve and we define some areas appearing in this curve. These areas are used to further evaluate authors' research performance from quantitative and qualitative point of view. We call these areas as "penalty" ones, since the greater they are, the more an author's performance is penalized. Moreover, we use these areas to establish new metrics aiming at categorizing researchers in two distinct categories: "influential" ones vs. "mass producers".