OpenRaiser/Intern-Atlas huggingface dataset:
Object Detection Using Keygraphs
Venue: arXiv cs.CV 2013
Year: 2013

We propose a new framework for object detection based on a generalization of the keypoint correspondence framework. This framework is based on replacing keypoints by keygraphs, i.e. isomorph directed graphs whose vertices are keypoints, in order to explore relative and structural information. Unlike similar works in the literature, we deal directly with graphs in the entire pipeline: we search for graph correspondences instead of searching for individual point correspondences and then building graph correspondences from them afterwards. We also estimate the pose from graph correspondences instead of falling back to point correspondences through a voting table. The contributions of this paper are the proposed framework and an implementation that properly handles its inherent issues of loss of locality and combinatorial explosion, showing its viability for real-time applications. In particular, we introduce the novel concept of keytuples to solve a running time issue. The accuracy of the implementation is shown by results of over 800 experiments with a well-known database of images. The speed is illustrated by real-time tracking with two different cameras in ordinary hardware.
Dynamic Gomory-Hu Tree Construction -- fast and simple
Venue: arXiv cs.DS 2013
Year: 2013

A cut tree (or Gomory-Hu tree) of an undirected weighted graph G=(V,E) encodes a minimum s-t-cut for each vertex pair {s,t} \subseteq V and can be iteratively constructed by n-1 maximum flow computations. They solve the multiterminal network flow problem, which asks for the all-pairs maximum flow values in a network and at the same time they represent n-1 non-crossing, linearly independent cuts that constitute a minimum cut basis of G. Hence, cut trees are resident in at least two fundamental fields of network analysis and graph theory, which emphasizes their importance for many applications. In this work we present a fully-dynamic algorithm that efficiently maintains a cut tree for a changing graph. The algorithm is easy to implement and has a high potential for saving cut computations under the assumption that a local change in the underlying graph does rarely affect the global cut structure. We document the good practicability of our approach in a brief experiment on real world data.
Towards Base Rates in Software Analytics
Venue: arXiv cs.SE 2013
Year: 2013

Nowadays a vast and growing body of open source software (OSS) project data is publicly available on the internet. Despite this public body of project data, the field of software analytics has not yet settled on a solid quantitative base for basic properties such as code size, growth, team size, activity, and project failure. What is missing is a quantification of the base rates of such properties, where other fields (such as medicine) commonly rely on base rates for decision making and the evaluation of experimental results. The lack of knowledge in this area impairs both research activities in the field of software analytics and decision making on software projects in general. This paper contributes initial results of our research towards obtaining base rates using the data available at Ohloh (a large-scale index of OSS projects). Zooming in on the venerable 'lines of code' metric for code size and growth, we present and discuss summary statistics and identify further research challenges.
Flexible Visual Quality Inspection in Discrete Manufacturing
Venue: arXiv cs.CV 2013
Year: 2013

Most visual quality inspections in discrete manufacturing are composed of length, surface, angle or intensity measurements. Those are implemented as end-user configurable inspection tools that should not require an image processing expert to set up. Currently available software solutions providing such capability use a flowchart based programming environment, but do not fully address an inspection flowchart robustness and can require a redefinition of the flowchart if a small variation is introduced. In this paper we propose an acquire-register-analyze image processing pattern designed for discrete manufacturing that aims to increase the robustness of the inspection flowchart by consistently addressing variations in product position, orientation and size. A proposed pattern is transparent to the end-user and simplifies the flowchart. We describe a developed software solution that is a practical implementation of the proposed pattern. We give an example of its real-life use in industrial production of electric components.
Combining Spatio-Temporal Appearance Descriptors and Optical Flow for Human Action Recognition in Video Data
Venue: arXiv cs.CV 2013
Year: 2013

This paper proposes combining spatio-temporal appearance (STA) descriptors with optical flow for human action recognition. The STA descriptors are local histogram-based descriptors of space-time, suitable for building a partial representation of arbitrary spatio-temporal phenomena. Because of the possibility of iterative refinement, they are interesting in the context of online human action recognition. We investigate the use of dense optical flow as the image function of the STA descriptor for human action recognition, using two different algorithms for computing the flow: the Farnebäck algorithm and the TVL1 algorithm. We provide a detailed analysis of the influencing optical flow algorithm parameters on the produced optical flow fields. An extensive experimental validation of optical flow-based STA descriptors in human action recognition is performed on the KTH human action dataset. The encouraging experimental results suggest the potential of our approach in online human action recognition.
Multiclass Road Sign Detection using Multiplicative Kernel
Venue: arXiv cs.CV 2013
Year: 2013

We consider the problem of multiclass road sign detection using a classification function with multiplicative kernel comprised from two kernels. We show that problems of detection and within-foreground classification can be jointly solved by using one kernel to measure object-background differences and another one to account for within-class variations. The main idea behind this approach is that road signs from different foreground variations can share features that discriminate them from backgrounds. The classification function training is accomplished using SVM, thus feature sharing is obtained through support vector sharing. Training yields a family of linear detectors, where each detector corresponds to a specific foreground training sample. The redundancy among detectors is alleviated using k-medoids clustering. Finally, we report detection and classification results on a set of road sign images obtained from a camera on a moving vehicle.
Decentralized formation control with connectivity maintenance and collision avoidance under limited and intermittent sensing
Venue: arXiv cs.SY 2013
Year: 2013

A decentralized switched controller is developed for dynamic agents to perform global formation configuration convergence while maintaining network connectivity and avoiding collision within agents and between stationary obstacles, using only local feedback under limited and intermittent sensing. Due to the intermittent sensing, constant position feedback may not be available for agents all the time. Intermittent sensing can also lead to a disconnected network or collisions between agents. Using a navigation function framework, a decentralized switched controller is developed to navigate the agents to the desired positions while ensuring network maintenance and collision avoidance.
Designing Markets for Daily Deals
Venue: arXiv cs.GT 2013
Year: 2013

Daily deals platforms such as Amazon Local, Google Offers, GroupOn, and LivingSocial have provided a new channel for merchants to directly market to consumers. In order to maximize consumer acquisition and retention, these platforms would like to offer deals that give good value to users. Currently, selecting such deals is done manually; however, the large number of submarkets and localities necessitates an automatic approach to selecting good deals and determining merchant payments. We approach this challenge as a market design problem. We postulate that merchants already have a good idea of the attractiveness of their deal to consumers as well as the amount they are willing to pay to offer their deal. The goal is to design an auction that maximizes a combination of the revenue of the auctioneer (platform), welfare of the bidders (merchants), and the positive externality on a third party (the consumer), despite the asymmetry of information about this consumer benefit. We design auctions that truthfully elicit this information from the merchants and maximize the social welfare objective, and we characterize the consumer welfare functions for which this objective is truthfully implementable. We generalize this characterization to a very broad mechanism-design setting and give examples of other applications.
Iterated Variable Neighborhood Search for the resource constrained multi-mode multi-project scheduling problem
Venue: arXiv cs.AI 2013
Year: 2013

The resource constrained multi-mode multi-project scheduling problem (RCMMMPSP) is a notoriously difficult combinatorial optimization problem. For a given set of activities, feasible execution mode assignments and execution starting times must be found such that some optimization function, e.g. the makespan, is optimized. When determining an optimal (or at least feasible) assignment of decision variable values, a set of side constraints, such as resource availabilities, precedence constraints, etc., has to be respected. In 2013, the MISTA 2013 Challenge stipulated research in the RCMMMPSP. It's goal was the solution of a given set of instances under running time restrictions. We have contributed to this challenge with the here presented approach.
Patterns for computational effects arising from a monad or a comonad
Venue: arXiv cs.LO 2013
Year: 2013

This paper presents equational-based logics for proving first order properties of programming languages involving effects. We propose two dual inference system patterns that can be instanciated with monads or comonads in order to be used for proving properties of different effects. The first pattern provides inference rules which can be interpreted in the Kleisli category of a monad and the coKleisli category of the associated comonad. In a dual way, the second pattern provides inference rules which can be interpreted in the coKleisli category of a comonad and the Kleisli category of the associated monad. The logics combine a 3-tier effect system for terms consisting of pure terms and two other kinds of effects called 'constructors/observers' and 'modifiers', and a 2-tier system for 'up-to-effects' and 'strong' equations. Each pattern provides generic rules for dealing with any monad (respectively comonad), and it can be extended with specific rules for each effect. The paper presents two use cases: a language with exceptions (using the standard monadic semantics), and a language with state (using the less standard comonadic semantics). Finally, we prove that the obtained inference system for states is Hilbert-Post complete.
Advanced coding schemes against jamming in telecommand links
Venue: arXiv cs.IT 2013
Year: 2013

The aim of this paper is to study the performance of some coding schemes recently proposed for updating the TC channel coding standard for space applications, in the presence of jamming. Besides low-density parity-check codes, that appear as the most eligible candidates, we also consider other solutions based on parallel turbo codes and extended BCH codes. We show that all these schemes offer very good performance, which approaches the theoretical limits achievable.
Multiple Kernel Learning in the Primal for Multi-modal Alzheimer's Disease Classification
Venue: arXiv cs.LG 2013
Year: 2013

To achieve effective and efficient detection of Alzheimer's disease (AD), many machine learning methods have been introduced into this realm. However, the general case of limited training samples, as well as different feature representations typically makes this problem challenging. In this work, we propose a novel multiple kernel learning framework to combine multi-modal features for AD classification, which is scalable and easy to implement. Contrary to the usual way of solving the problem in the dual space, we look at the optimization from a new perspective. By conducting Fourier transform on the Gaussian kernel, we explicitly compute the mapping function, which leads to a more straightforward solution of the problem in the primal space. Furthermore, we impose the mixed $L_{21}$ norm constraint on the kernel weights, known as the group lasso regularization, to enforce group sparsity among different feature modalities. This actually acts as a role of feature modality selection, while at the same time exploiting complementary information among different kernels. Therefore it is able to extract the most discriminative features for classification. Experiments on the ADNI data set demonstrate the effectiveness of the proposed method.
Cognitive Radio with Random Number of Secondary Number of Users
Venue: arXiv cs.IT 2013
Year: 2013

A single primary user cognitive radio system with multi-user diversity at the secondary users is considered where there is an interference constraint between secondary and primary users. The secondary user with the highest instantaneous SNR is selected for communication from a set of active users which also satisfies the interference constraint. The active number of secondary users is shown to be binomial, negative binomial, or Poisson-binomial distributed depending on various modes of operation. Outage probability in the slow fading scenario is also studied. This is then followed by a derivation of the scaling law of the ergodic capacity and BER averaged across the fading, and user distribution for a large mean number of users. The ergodic capacity and average BER under the binomial user distribution is shown to outperform the negative binomial case with the same mean number of users. Moreover, the Poisson distribution is used to approximate the user distribution under the non-i.i.d interference scenario, and compared with binomial and negative binomial distributions in a stochastic ordering sense. Monte-Carlo simulations are used to supplement our analytical results and compare the performances under different user distributions.
The Gaussian Two-way Diamond Channel
Venue: arXiv cs.IT 2013
Year: 2013

We consider two-way relaying in a Gaussian diamond channel, where two terminal nodes wish to exchange information using two relays. A simple baseline protocol is obtained by time-sharing between two one-way protocols. To improve upon the baseline performance, we propose two compute-and-forward (CF) protocols: Compute-and-forward Compound multiple access channel (CF-CMAC) and Compute-and-forward-Broadcast (CF-BC). These protocols mix the two flows through the two relays and achieve rates better than the simple time-sharing protocol. We derive an outer bound to the capacity region that is satisfied by any relaying protocol, and observe that the proposed protocols provide rates close to the outer bound in certain channel conditions. Both the CF-CMAC and CF-BC protocols use nested lattice codes in the compute phases. In the CF-CMAC protocol, both relays simultaneously forward to the destinations over a Compound Multiple Access Channel (CMAC). In the simpler CF-BC protocol's forward phase, one relay is selected at a time for Broadcast Channel (BC) transmission depending on the rate-pair to be achieved. We also consider the diamond channel with direct source-destination link and the diamond channel with interfering relays. Outer bounds and achievable rate regions are compared for these two channels as well. Mixing of flows using the CF-CMAC protocol is shown to be good for symmetric two-way rates.
Numerical integration on GPUs for higher order finite elements
Venue: arXiv cs.MS 2013
Year: 2013

The paper considers the problem of implementation on graphics processors of numerical integration routines for higher order finite element approximations. The design of suitable GPU kernels is investigated in the context of general purpose integration procedures, as well as particular example applications. The most important characteristic of the problem investigated is the large variation of required processor and memory resources associated with different degrees of approximating polynomials. The questions that we try to answer are whether it is possible to design a single integration kernel for different GPUs and different orders of approximation and what performance can be expected in such a case.
Progressive Compressed Sensing and Reconstruction of Multidimensional Signals Using Hybrid Transform/Prediction Sparsity Model
Venue: arXiv cs.IT 2013
Year: 2013

Compressed sensing (CS) is an innovative technique allowing to represent signals through a small number of their linear projections. Hence, CS can be thought of as a natural candidate for acquisition of multidimensional signals, as the amount of data acquired and processed by conventional sensors could create problems in terms of computational complexity. In this paper, we propose a framework for the acquisition and reconstruction of multidimensional correlated signals. The approach is general and can be applied to D dimensional signals, even if the algorithms we propose to practically implement such architectures apply to 2-D and 3-D signals. The proposed architectures employ iterative local signal reconstruction based on a hybrid transform/prediction correlation model, coupled with a proper initialization strategy.
A note on monadic datalog on unranked trees
Venue: arXiv cs.LO 2013
Year: 2013

In the article 'Recursive queries on trees and data trees' (ICDT'13), Abiteboul et al., asked whether the containment problem for monadic datalog over unordered unranked labeled trees using the child relation and the descendant relation is decidable. This note gives a positive answer to this question, as well as an overview of the relative expressive power of monadic datalog on various representations of unranked trees.
On Lattices of Regular Sets of Natural Integers Closed under Decrementation
Venue: arXiv cs.DM 2013
Year: 2013

We consider lattices of regular sets of non negative integers, i.e. of sets definable in Presbuger arithmetic. We prove that if such a lattice is closed under decrement then it is also closed under many other functions: quotients by an integer, roots, etc.
An information spectrum approach to the capacity region of GIFC
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we present a general formula for the capacity region of a general interference channel with two pairs of users. The formula shows that the capacity region is the union of a family of rectangles, where each rectangle is determined by a pair of spectral inf-mutual information rates. Although the presented formula is usually difficult to compute, it provides us useful insights into the interference channels. In particular, when the inputs are discrete ergodic Markov processes and the channel is stationary memoryless, the formula can be evaluated by BCJR algorithm. Also the formula suggests us that the simplest inner bounds (obtained by treating the interference as noise) could be improved by taking into account the structure of the interference processes. This is verified numerically by computing the mutual information rates for Gaussian interference channels with embedded convolutional codes. Moreover, we present a coding scheme to approach the theoretical achievable rate pairs. Numerical results show that decoding gain can be achieved by considering the structure of the interference.
Online Unsupervised Feature Learning for Visual Tracking
Venue: arXiv cs.CV 2013
Year: 2013

Feature encoding with respect to an over-complete dictionary learned by unsupervised methods, followed by spatial pyramid pooling, and linear classification, has exhibited powerful strength in various vision applications. Here we propose to use the feature learning pipeline for visual tracking. Tracking is implemented using tracking-by-detection and the resulted framework is very simple yet effective. First, online dictionary learning is used to build a dictionary, which captures the appearance changes of the tracking target as well as the background changes. Given a test image window, we extract local image patches from it and each local patch is encoded with respect to the dictionary. The encoded features are then pooled over a spatial pyramid to form an aggregated feature vector. Finally, a simple linear classifier is trained on these features. Our experiments show that the proposed powerful---albeit simple---tracker, outperforms all the state-of-the-art tracking methods that we have tested. Moreover, we evaluate the performance of different dictionary learning and feature encoding methods in the proposed tracking framework, and analyse the impact of each component in the tracking scenario. We also demonstrate the flexibility of feature learning by plugging it into Hare et al.'s tracking method. The outcome is, to our knowledge, the best tracker ever reported, which facilitates the advantages of both feature learning and structured output prediction.
End-to-End Text Recognition with Hybrid HMM Maxout Models
Venue: arXiv cs.CV 2013
Year: 2013

The problem of detecting and recognizing text in natural scenes has proved to be more challenging than its counterpart in documents, with most of the previous work focusing on a single part of the problem. In this work, we propose new solutions to the character and word recognition problems and then show how to combine these solutions in an end-to-end text-recognition system. We do so by leveraging the recently introduced Maxout networks along with hybrid HMM models that have proven useful for voice recognition. Using these elements, we build a tunable and highly accurate recognition system that beats state-of-the-art results on all the sub-problems for both the ICDAR 2003 and SVT benchmark datasets.
Early Fire Detection Using HEP and Space-time Analysis
Venue: arXiv cs.CV 2013
Year: 2013

In this article, a video base early fire alarm system is developed by monitoring the smoke in the scene. There are two major contributions in this work. First, to find the best texture feature for smoke detection, a general framework, named Histograms of Equivalent Patterns (HEP), is adopted to achieve an extensive evaluation of various kinds of texture features. Second, the \emph{Block based Inter-Frame Difference} (BIFD) and a improved version of LBP-TOP are proposed and ensembled to describe the space-time characteristics of the smoke. In order to reduce the false alarms, the Smoke History Image (SHI) is utilized to register the recent classification results of candidate smoke blocks. Experimental results using SVM show that the proposed method can achieve better accuracy and less false alarm compared with the state-of-the-art technologies.
Empowerment -- an Introduction
Venue: arXiv cs.AI 2013
Year: 2013

This book chapter is an introduction to and an overview of the information-theoretic, task independent utility function "Empowerment", which is defined as the channel capacity between an agent's actions and an agent's sensors. It quantifies how much influence and control an agent has over the world it can perceive. This book chapter discusses the general idea behind empowerment as an intrinsic motivation and showcases several previous applications of empowerment to demonstrate how empowerment can be applied to different sensor-motor configuration, and how the same formalism can lead to different observed behaviors. Furthermore, we also present a fast approximation for empowerment in the continuous domain.