OpenRaiser/Intern-Atlas huggingface dataset:
Human Re-identification by Matching Compositional Template with Cluster Sampling
Venue: arXiv cs.CV 2015
Year: 2015

This paper aims at a newly raising task in visual surveillance: re-identifying people at a distance by matching body information, given several reference examples. Most of existing works solve this task by matching a reference template with the target individual, but often suffer from large human appearance variability (e.g. different poses/views, illumination) and high false positives in matching caused by conjunctions, occlusions or surrounding clutters. Addressing these problems, we construct a simple yet expressive template from a few reference images of a certain individual, which represents the body as an articulated assembly of compositional and alternative parts, and propose an effective matching algorithm with cluster sampling. This algorithm is designed within a candidacy graph whose vertices are matching candidates (i.e. a pair of source and target body parts), and iterates in two steps for convergence. (i) It generates possible partial matches based on compatible and competitive relations among body parts. (ii) It confirms the partial matches to generate a new matching solution, which is accepted by the Markov Chain Monte Carlo (MCMC) mechanism. In the experiments, we demonstrate the superior performance of our approach on three public databases compared to existing methods.
Learning Latent Spatio-Temporal Compositional Model for Human Action Recognition
Venue: arXiv cs.CV 2015
Year: 2015

Action recognition is an important problem in multimedia understanding. This paper addresses this problem by building an expressive compositional action model. We model one action instance in the video with an ensemble of spatio-temporal compositions: a number of discrete temporal anchor frames, each of which is further decomposed to a layout of deformable parts. In this way, our model can identify a Spatio-Temporal And-Or Graph (STAOG) to represent the latent structure of actions e.g. triple jumping, swinging and high jumping. The STAOG model comprises four layers: (i) a batch of leaf-nodes in bottom for detecting various action parts within video patches; (ii) the or-nodes over bottom, i.e. switch variables to activate their children leaf-nodes for structural variability; (iii) the and-nodes within an anchor frame for verifying spatial composition; and (iv) the root-node at top for aggregating scores over temporal anchor frames. Moreover, the contextual interactions are defined between leaf-nodes in both spatial and temporal domains. For model training, we develop a novel weakly supervised learning algorithm which iteratively determines the structural configuration (e.g. the production of leaf-nodes associated with the or-nodes) along with the optimization of multi-layer parameters. By fully exploiting spatio-temporal compositions and interactions, our approach handles well large intra-class action variance (e.g. different views, individual appearances, spatio-temporal structures). The experimental results on the challenging databases demonstrate superior performance of our approach over other competing methods.
Fast Finite Field Hartley Transforms Based on Hadamard Decomposition
Venue: arXiv cs.NA 2015
Year: 2015

A new transform over finite fields, the finite field Hartley transform (FFHT), was recently introduced and a number of promising applications on the design of efficient multiple access systems and multilevel spread spectrum sequences were proposed. The FFHT exhibits interesting symmetries, which are exploited to derive tailored fast transform algorithms. The proposed fast algorithms are based on successive decompositions of the FFHT by means of Hadamard-Walsh transforms (HWT). The introduced decompositions meet the lower bound on the multiplicative complexity for all the cases investigated. The complexity of the new algorithms is compared with that of traditional algorithms.
Adaptive Scene Category Discovery with Generative Learning and Compositional Sampling
Venue: arXiv cs.CV 2015
Year: 2015

This paper investigates a general framework to discover categories of unlabeled scene images according to their appearances (i.e., textures and structures). We jointly solve the two coupled tasks in an unsupervised manner: (i) classifying images without pre-determining the number of categories, and (ii) pursuing generative model for each category. In our method, each image is represented by two types of image descriptors that are effective to capture image appearances from different aspects. By treating each image as a graph vertex, we build up an graph, and pose the image categorization as a graph partition process. Specifically, a partitioned sub-graph can be regarded as a category of scenes, and we define the probabilistic model of graph partition by accumulating the generative models of all separated categories. For efficient inference with the graph, we employ a stochastic cluster sampling algorithm, which is designed based on the Metropolis-Hasting mechanism. During the iterations of inference, the model of each category is analytically updated by a generative learning algorithm. In the experiments, our approach is validated on several challenging databases, and it outperforms other popular state-of-the-art methods. The implementation details and empirical analysis are presented as well.
Towards a solid solution of real-time fire and flame detection
Venue: arXiv cs.CV 2015
Year: 2015

Although the object detection and recognition has received growing attention for decades, a robust fire and flame detection method is rarely explored. This paper presents an empirical study, towards a general and solid approach to fast detect fire and flame in videos, with the applications in video surveillance and event retrieval. Our system consists of three cascaded steps: (1) candidate regions proposing by a background model, (2) fire region classifying with color-texture features and a dictionary of visual words, and (3) temporal verifying. The experimental evaluation and analysis are done for each step. We believe that it is a useful service to both academic research and real-world application. In addition, we release the software of the proposed system with the source code, as well as a public benchmark and data set, including 64 video clips covered both indoor and outdoor scenes under different conditions. We achieve an 82% Recall with 93% Precision on the data set, and greatly improve the performance by state-of-the-arts methods.
60 GHz MAC Standardization: Progress and Way Forward
Venue: arXiv cs.NI 2015
Year: 2015

Communication at mmWave frequencies has been the focus in the recent years. In this paper, we discuss standardization efforts in 60 GHz short range communication and the progress therein. We compare the available standards in terms of network architecture, medium access control mechanisms, physical layer techniques and several other features. Comparative analysis indicates that IEEE 802.11ad is likely to lead the short-range indoor communication at 60 GHz. We bring to the fore resolved and unresolved issues pertaining to robust WLAN connectivity at 60 GHz. Further, we discuss the role of mmWave bands in 5G communication scenarios and highlight the further efforts required in terms of research and standardization.
Alignment based Network Coding for Two-Unicast-Z Networks
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we study the wireline two-unicast-Z communication network over directed acyclic graphs. The two-unicast-Z network is a two-unicast network where the destination intending to decode the second message has apriori side information of the first message. We make three contributions in this paper: 1. We describe a new linear network coding algorithm for two-unicast-Z networks over directed acyclic graphs. Our approach includes the idea of interference alignment as one of its key ingredients. For graphs of a bounded degree, our algorithm has linear complexity in terms of the number of vertices, and polynomial complexity in terms of the number of edges. 2. We prove that our algorithm achieves the rate-pair (1, 1) whenever it is feasible in the network. Our proof serves as an alternative, albeit restricted to two-unicast-Z networks over directed acyclic graphs, to an earlier result of Wang et al. which studied necessary and sufficient conditions for feasibility of the rate pair (1, 1) in two-unicast networks. 3. We provide a new proof of the classical max-flow min-cut theorem for directed acyclic graphs.
Design of a Mobile Face Recognition System for Visually Impaired Persons
Venue: arXiv cs.CY 2015
Year: 2015

It is estimated that 285 million people globally are visually impaired. A majority of these people live in developing countries and are among the elderly population. One of the most difficult tasks faced by the visually impaired is identification of people. While naturally, voice recognition is a common method of identification, it is an intuitive and difficult process. The rise of computation capability of mobile devices gives motivation to develop applications that can assist visually impaired persons. With the availability of mobile devices, these people can be assisted by an additional method of identification through intelligent software based on computer vision techniques. In this paper, we present the design and implementation of a face detection and recognition system for the visually impaired through the use of mobile computing. This mobile system is assisted by a server-based support system. The system was tested on a custom video database. Experiment results show high face detection accuracy and promising face recognition accuracy in suitable conditions. The challenges of the system lie in better recognition techniques for difficult situations in terms of lighting and weather.
Measure the similarity of nodes in the complex networks
Venue: arXiv cs.SI 2015
Year: 2015

Measure the similarity of the nodes in the complex networks have interested many researchers to explore it. In this paper, a new method which is based on the degree centrality and the Relative-entropy is proposed to measure the similarity of the nodes in the complex networks. The results in this paper show that, the nodes which have a common structure property always have a high similarity to others nodes. The nodes which have a high influential to others always have a small value of similarity to other nodes and the marginal nodes also have a low similar to other nodes. The results in this paper show that the proposed method is useful and reasonable to measure the similarity of the nodes in the complex networks.
Face frontalization for Alignment and Recognition
Venue: arXiv cs.CV 2015
Year: 2015

Recently, it was shown that excellent results can be achieved in both face landmark localization and pose-invariant face recognition. These breakthroughs are attributed to the efforts of the community to manually annotate facial images in many different poses and to collect 3D faces data. In this paper, we propose a novel method for joint face landmark localization and frontal face reconstruction (pose correction) using a small set of frontal images only. By observing that the frontal facial image is the one with the minimum rank from all different poses we formulate an appropriate model which is able to jointly recover the facial landmarks as well as the frontalized version of the face. To this end, a suitable optimization problem, involving the minimization of the nuclear norm and the matrix $\ell_1$ norm, is solved. The proposed method is assessed in frontal face reconstruction (pose correction), face landmark localization, and pose-invariant face recognition and verification by conducting experiments on $6$ facial images databases. The experimental results demonstrate the effectiveness of the proposed method.
Authentication Systems in Internet of Things
Venue: arXiv cs.CR 2015
Year: 2015

This paper analyses the various authentication systems implemented for enhanced security and private re-position of an individual's log-in credentials. The first part of the paper describes the multi-factor authentication (MFA) systems, which, though not applicable to the field of Internet of Things, provides great security to a user's credentials. MFA is followed by a brief description of the working mechanism of interaction of third party clients with private resources over the OAuth protocol framework and a study of the delegation based authentication system in IP-based IoT.
DeepID3: Face Recognition with Very Deep Neural Networks
Venue: arXiv cs.CV 2015
Year: 2015

The state-of-the-art of face recognition has been significantly advanced by the emergence of deep learning. Very deep neural networks recently achieved great success on general object recognition because of their superb learning capacity. This motivates us to investigate their effectiveness on face recognition. This paper proposes two very deep neural network architectures, referred to as DeepID3, for face recognition. These two architectures are rebuilt from stacked convolution and inception layers proposed in VGG net and GoogLeNet to make them suitable to face recognition. Joint face identification-verification supervisory signals are added to both intermediate and final feature extraction layers during training. An ensemble of the proposed two architectures achieves 99.53% LFW face verification accuracy and 96.0% LFW rank-1 face identification accuracy, respectively. A further discussion of LFW face verification result is given in the end.
Scaling Laws for Disturbance Propagation in Cyclic Dynamical Networks
Venue: arXiv cs.SY 2015
Year: 2015

Our goal is to analyze performance of stable linear dynamical networks subject to external stochastic disturbances. The square of the $\mathcal H_2$-norm of the network is used as a performance measure to quantify the expected steady-state dispersion of the outputs of the network. We show that this performance measure can be tightly bounded from below and above by some spectral functions of the state-space matrices of the network. This result is applied to a class of cyclic linear networks and shown that their performance measure scale quadratically with the network size.
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping
Venue: arXiv cs.CC 2015
Year: 2015

Classic similarity measures of strings are longest common subsequence and Levenshtein distance (i.e., the classic edit distance). A classic similarity measure of curves is dynamic time warping. These measures can be computed by simple $O(n^2)$ dynamic programming algorithms, and despite much effort no algorithms with significantly better running time are known. We prove that, even restricted to binary strings or one-dimensional curves, respectively, these measures do not have strongly subquadratic time algorithms, i.e., no algorithms with running time $O(n^{2-\varepsilon})$ for any $\varepsilon > 0$, unless the Strong Exponential Time Hypothesis fails. We generalize the result to edit distance for arbitrary fixed costs of the four operations (deletion in one of the two strings, matching, substitution), by identifying trivial cases that can be solved in constant time, and proving quadratic-time hardness on binary strings for all other cost choices. This improves and generalizes the known hardness result for Levenshtein distance [Backurs, Indyk STOC'15] by the restriction to binary strings and the generalization to arbitrary costs, and adds important problems to a recent line of research showing conditional lower bounds for a growing number of quadratic time problems. As our main technical contribution, we introduce a framework for proving quadratic-time hardness of similarity measures. To apply the framework it suffices to construct a single gadget, which encapsulates all the expressive power necessary to emulate a reduction from satisfiability. Finally, we prove quadratic-time hardness for longest palindromic subsequence and longest tandem subsequence via reductions from longest common subsequence, showing that conditional lower bounds based on the Strong Exponential Time Hypothesis also apply to string problems that are not necessarily similarity measures.
Information theoretic approach to robust multi-Bernoulli sensor control
Venue: arXiv cs.IT 2015
Year: 2015

A novel sensor control solution is presented, formulated within a Multi-Bernoulli-based multi-target tracking framework. The proposed method is especially designed for the general multi-target tracking case, where no prior knowledge of the clutter distribution or the probability of detection profile are available. In an information theoretic approach, our method makes use of Rènyi divergence as the reward function to be maximized for finding the optimal sensor control command at each step. We devise a Monte Carlo sampling method for computation of the reward. Simulation results demonstrate successful performance of the proposed method in a challenging scenario involving five targets maneuvering in a relatively uncertain space with unknown distance-dependent clutter rate and probability of detection.
A discontinuous Galerkin method for cohesive zone modelling
Venue: arXiv cs.CE 2015
Year: 2015

We propose a discontinuous finite element method for small strain elasticity allowing for cohesive zone modeling. The method yields a seamless transition between the discontinuous Galerkin method and classical cohesive zone modeling. Some relevant numerical examples are presented.
Toward Fully Coordinated Multi-level Multi-carrier Energy Efficient Networks
Venue: arXiv cs.NI 2015
Year: 2015

Enabling coordination between products from different vendors is a key characteristic of the design philosophy behind future wireless communication networks. As an example, different devices may have different implementations, leading to different user experiences. A similar story emerges when devices running different physical and link layer protocols share frequencies in the same spectrum in order to maximize the system-wide spectral efficiency. In such situations, coordinating multiple interfering devices presents a significant challenge not only from an interworking perspective (as a result of reduced infrastructure), but also from an implementation point of view. The following question may then naturally arise: How to accommodate integrating such heterogeneous wireless devices seamlessly? One approach is to coordinate the spectrum in a centralized manner. However, the desired autonomous feature of future wireless systems makes the use of a central authority for spectrum management less appealing. Alternately, intelligent spectrum coordination have spurred great interest and excitement in the recent years. This paper presents a multi-level (hierarchical) power control game where users jointly choose their channel control and power control selfishly in order to maximize their individual energy efficiency. By hierarchical, we mean that some users' decision priority is higher/lower than the others. We propose two simple and nearly-optimal algorithms that ensure complete spectrum coordination among users. Interestingly, it turns out that the complexity of the two proposed algorithms is, in the worst case, quadratic in the number of users, whereas the complexity of the optimal solution (obtained through exhaustive search) is N!.
Machine-Checked Proofs For Realizability Checking Algorithms
Venue: arXiv cs.SE 2015
Year: 2015

Virtual integration techniques focus on building architectural models of systems that can be analyzed early in the design cycle to try to lower cost, reduce risk, and improve quality of complex embedded systems. Given appropriate architectural descriptions, assume/guarantee contracts, and compositional reasoning rules, these techniques can be used to prove important safety properties about the architecture prior to system construction. For these proofs to be meaningful, each leaf-level component contract must be realizable; i.e., it is possible to construct a component such that for any input allowed by the contract assumptions, there is some output value that the component can produce that satisfies the contract guarantees. We have recently proposed (in [1]) a contract-based realizability checking algorithm for assume/guarantee contracts over infinite theories supported by SMT solvers such as linear integer/real arithmetic and uninterpreted functions. In that work, we used an SMT solver and an algorithm similar to k-induction to establish the realizability of a contract, and justified our approach via a hand proof. Given the central importance of realizability to our virtual integration approach, we wanted additional confidence that our approach was sound. This paper describes a complete formalization of the approach in the Coq proof and specification language. During formalization, we found several small mistakes and missing assumptions in our reasoning. Although these did not compromise the correctness of the algorithm used in the checking tools, they point to the value of machine-checked formalization. In addition, we believe this is the first machine-checked formalization for a realizability algorithm.
RELEAF: An Algorithm for Learning and Exploiting Relevance
Venue: arXiv cs.LG 2015
Year: 2015

Recommender systems, medical diagnosis, network security, etc., require on-going learning and decision-making in real time. These -- and many others -- represent perfect examples of the opportunities and difficulties presented by Big Data: the available information often arrives from a variety of sources and has diverse features so that learning from all the sources may be valuable but integrating what is learned is subject to the curse of dimensionality. This paper develops and analyzes algorithms that allow efficient learning and decision-making while avoiding the curse of dimensionality. We formalize the information available to the learner/decision-maker at a particular time as a context vector which the learner should consider when taking actions. In general the context vector is very high dimensional, but in many settings, the most relevant information is embedded into only a few relevant dimensions. If these relevant dimensions were known in advance, the problem would be simple -- but they are not. Moreover, the relevant dimensions may be different for different actions. Our algorithm learns the relevant dimensions for each action, and makes decisions based in what it has learned. Formally, we build on the structure of a contextual multi-armed bandit by adding and exploiting a relevance relation. We prove a general regret bound for our algorithm whose time order depends only on the maximum number of relevant dimensions among all the actions, which in the special case where the relevance relation is single-valued (a function), reduces to $\tilde{O}(T^{2(\sqrt{2}-1)})$; in the absence of a relevance relation, the best known contextual bandit algorithms achieve regret $\tilde{O}(T^{(D+1)/(D+2)})$, where $D$ is the full dimension of the context vector.
Optimal component labeling algorithms for mesh-connected computers and VLSI
Venue: arXiv cs.DS 2015
Year: 2015

Given an undirected graph $G$ of $n$ weighted edges, stored one edge per processor in a square mesh of $n$ processors, we show how to determine the connected components and a minimal spanning forest in $Θ(\sqrt{n})$ time. More generally, we show how to solve these problems in $Θ(n^{1/d})$ time when the mesh is a $d$-dimensional cube, where the implied constants depend upon $d$.