OpenRaiser/Intern-Atlas huggingface dataset:
Reversible Languages Having Finitely Many Reduced Automata
Venue: arXiv cs.FL 2017
Year: 2017

Reversible forms of computations are often interesting from an energy efficiency point of view. When the computation device in question is an automaton, it is known that the minimal reversible automaton recognizing a given language is not necessarily unique, moreover, there are languages having arbitrarily large reversible recognizers possessing no nontrivial reversible congruence. However, the exact characterization of this class of languages was open. In this paper we give a forbidden pattern capturing the reversible regular languages having only finitely many reduced reversible automata, allowing an efficient (NL) decision procedure.
Parcellation of Visual Cortex on high-resolution histological Brain Sections using Convolutional Neural Networks
Venue: arXiv cs.CV 2017
Year: 2017

Microscopic analysis of histological sections is considered the "gold standard" to verify structural parcellations in the human brain. Its high resolution allows the study of laminar and columnar patterns of cell distributions, which build an important basis for the simulation of cortical areas and networks. However, such cytoarchitectonic mapping is a semiautomatic, time consuming process that does not scale with high throughput imaging. We present an automatic approach for parcellating histological sections at 2um resolution. It is based on a convolutional neural network that combines topological information from probabilistic atlases with the texture features learned from high-resolution cell-body stained images. The model is applied to visual areas and trained on a sparse set of partial annotations. We show how predictions are transferable to new brains and spatially consistent across sections.
Interpreting and Extending The Guided Filter Via Cyclic Coordinate Descent
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we will disclose that the Guided Filter (GF) can be interpreted as the Cyclic Coordinate Descent (CCD) solver of a Least Square (LS) objective function. This discovery implies a possible way to extend GF because we can alter the objective function of GF and define new filters as the first pass iteration of the CCD solver of modified objective functions. Moreover, referring to the iterative minimizing procedure of CCD, we can derive new rolling filtering schemes. Hence, under the guidance of this discovery, we not only propose new GF-like filters adapting to the specific requirements of applications but also offer thoroughly explanations for two rolling filtering schemes of GF as well as the way to extend them. Experiments show that our new filters and extensions produce state-of-the-art results.
Torque-Controlled Stepping-Strategy Push Recovery: Design and Implementation on the iCub Humanoid Robot
Venue: arXiv cs.RO 2017
Year: 2017

One of the challenges for the robotics community is to deploy robots which can reliably operate in real world scenarios together with humans. A crucial requirement for legged robots is the capability to properly balance on their feet, rejecting external disturbances. iCub is a state-of-the-art humanoid robot which has only recently started to balance on its feet. While the current balancing controller has proved successful in various scenarios, it still misses the capability to properly react to strong pushes by taking steps. This paper goes in this direction. It proposes and implements a control strategy based on the Capture Point concept [1]. Instead of relying on position control, like most of Capture Point related approaches, the proposed strategy generates references for the momentum-based torque controller already implemented on the iCub, thus extending its capabilities to react to external disturbances, while retaining the advantages of torque control when interacting with the environment. Experiments in the Gazebo simulator and on the iCub humanoid robot validate the proposed strategy.
Nighttime sky/cloud image segmentation
Venue: arXiv cs.CV 2017
Year: 2017

Imaging the atmosphere using ground-based sky cameras is a popular approach to study various atmospheric phenomena. However, it usually focuses on the daytime. Nighttime sky/cloud images are darker and noisier, and thus harder to analyze. An accurate segmentation of sky/cloud images is already challenging because of the clouds' non-rigid structure and size, and the lower and less stable illumination of the night sky increases the difficulty. Nonetheless, nighttime cloud imaging is essential in certain applications, such as continuous weather analysis and satellite communication. In this paper, we propose a superpixel-based method to segment nighttime sky/cloud images. We also release the first nighttime sky/cloud image segmentation database to the research community. The experimental results show the efficacy of our proposed algorithm for nighttime images.
Optimizing Memory Efficiency for Convolution Kernels on Kepler GPUs
Venue: arXiv cs.DC 2017
Year: 2017

Convolution is a fundamental operation in many applications, such as computer vision, natural language processing, image processing, etc. Recent successes of convolutional neural networks in various deep learning applications put even higher demand on fast convolution. The high computation throughput and memory bandwidth of graphics processing units (GPUs) make GPUs a natural choice for accelerating convolution operations. However, maximally exploiting the available memory bandwidth of GPUs for convolution is a challenging task. This paper introduces a general model to address the mismatch between the memory bank width of GPUs and computation data width of threads. Based on this model, we develop two convolution kernels, one for the general case and the other for a special case with one input channel. By carefully optimizing memory access patterns and computation patterns, we design a communication-optimized kernel for the special case and a communication-reduced kernel for the general case. Experimental data based on implementations on Kepler GPUs show that our kernels achieve 5.16X and 35.5% average performance improvement over the latest cuDNN library, for the special case and the general case, respectively.
Universal secure rank-metric coding schemes with optimal communication overheads
Venue: arXiv cs.IT 2017
Year: 2017

We study the problem of reducing the communication overhead from a noisy wire-tap channel or storage system where data is encoded as a matrix, when more columns (or their linear combinations) are available. We present its applications to reducing communication overheads in universal secure linear network coding and secure distributed storage with crisscross errors and erasures and in the presence of a wire-tapper. Our main contribution is a method to transform coding schemes based on linear rank-metric codes, with certain properties, to schemes with lower communication overheads. By applying this method to pairs of Gabidulin codes, we obtain coding schemes with optimal information rate with respect to their security and rank error correction capability, and with universally optimal communication overheads, when $ n \leq m $, being $ n $ and $ m $ the number of columns and number of rows, respectively. Moreover, our method can be applied to other families of maximum rank distance codes when $ n > m $. The downside of the method is generally expanding the packet length, but some practical instances come at no cost.
On the decidability of $k$-Block determinism
Venue: arXiv cs.FL 2017
Year: 2017

Brüggemann-Klein and Wood define a one-unambiguous regular language as a language that can be recognized by a deterministic Glushkov automaton. They give a procedure performed on the minimal DFA, the BW-test, to decide whether a language is one-unambiguous. Block determinism is an extension of one-unambiguity while considering non-empty words as symbols and prefix-freeness as determinism. A block automaton is compact if it does not have two equivalent states (same right language). We showed that a language is $k$-block deterministic if it is recognized by some deterministic $k$-block automaton passing the BW-test. In this paper, we show that any $k$-block deterministic language is recognized by a compact deterministic $k$-block automaton passing the BW-test. We also give a procedure which enumerates, for a given language, the finite set of compact deterministic $k$-block automata. It gives us a decidable procedure to test whether a language is $k$-block deterministic.
Optical Communication in Space: Challenges and Mitigation Techniques
Venue: arXiv cs.IT 2017
Year: 2017

In recent years, free space optical communication has gained significant importance owing to its unique features: large bandwidth, license-free spectrum, high data rate, easy and quick deployability, less power and low mass requirements. FSO communication uses the optical carrier in the near infrared band to establish either terrestrial links within the Earth's atmosphere or inter-satellite or deep space links or ground-to-satellite or satellite-to-ground links. However, despite the great potential of FSO communication, its performance is limited by the adverse effects viz., absorption, scattering, and turbulence of the atmospheric channel. This paper presents a comprehensive survey on various challenges faced by FSO communication system for ground-to-satellite or satellite-to-ground and inter-satellite links. It also provides details of various performance mitigation techniques in order to have high link availability and reliability. The first part of the paper will focus on various types of impairments that pose a serious challenge to the performance of optical communication system for ground-to-satellite or satellite-to-ground and inter-satellite links. The latter part of the paper will provide the reader with an exhaustive review of various techniques both at physical layer as well as at the other layers i.e., link, network or transport layer to combat the adverse effects of the atmosphere. It also uniquely presents a recently developed technique using orbital angular momentum for utilizing the high capacity advantage of the optical carrier in case of space-based and near-Earth optical communication links. This survey provides the reader with comprehensive details on the use of space-based optical backhaul links in order to provide high-capacity and low-cost backhaul solutions.
A Predictive Momentum-Based Whole-Body Torque Controller: Theory and Simulations for the iCub Stepping
Venue: arXiv cs.RO 2017
Year: 2017

When balancing, a humanoid robot can be easily subjected to unexpected disturbances like external pushes. In these circumstances, reactive movements as steps become a necessary requirement in order to avoid potentially harmful falling states. In this paper we conceive a Model Predictive Controller which determines a desired set of contact wrenches by predicting the future evolution of the robot, while taking into account constraints switching in case of steps. The control inputs computed by this strategy, namely the desired contact wrenches, are directly obtained on the robot through a modification of the momentum-based whole-body torque controller currently implemented on iCub. The proposed approach is validated through simulations in a stepping scenario, revealing high robustness and reliability when executing a recovery strategy.
Optimizing Trade-offs Among Stakeholders in Real-Time Bidding by Incorporating Multimedia Metrics
Venue: arXiv cs.GT 2017
Year: 2017

Displaying banner advertisements (in short, ads) on webpages has usually been discussed as an Internet economics topic where a publisher uses auction models to sell an online user's page view to advertisers and the one with the highest bid can have her ad displayed to the user. This is also called \emph{real-time bidding} (RTB) and the ad displaying process ensures that the publisher's benefit is maximized or there is an equilibrium in ad auctions. However, the benefits of the other two stakeholders -- the advertiser and the user -- have been rarely discussed. In this paper, we propose a two-stage computational framework that selects a banner ad based on the optimized trade-offs among all stakeholders. The first stage is still auction based and the second stage re-ranks ads by considering the benefits of all stakeholders. Our metric variables are: the publisher's revenue, the advertiser's utility, the ad memorability, the ad click-through rate (CTR), the contextual relevance, and the visual saliency. To the best of our knowledge, this is the first work that optimizes trade-offs among all stakeholders in RTB by incorporating multimedia metrics. An algorithm is also proposed to determine the optimal weights of the metric variables. We use both ad auction datasets and multimedia datasets to validate the proposed framework. Our experimental results show that the publisher can significantly improve the other stakeholders' benefits by slightly reducing her revenue in the short-term. In the long run, advertisers and users will be more engaged, the increased demand of advertising and the increased supply of page views can then boost the publisher's revenue.
Computing Canonical Bases of Modules of Univariate Relations
Venue: arXiv cs.SC 2017
Year: 2017

We study the computation of canonical bases of sets of univariate relations $(p_1,\ldots,p_m) \in \mathbb{K}[x]^{m}$ such that $p_1 f_1 + \cdots + p_m f_m = 0$; here, the input elements $f_1,\ldots,f_m$ are from a quotient $\mathbb{K}[x]^n/\mathcal{M}$, where $\mathcal{M}$ is a $\mathbb{K}[x]$-module of rank $n$ given by a basis $\mathbf{M}\in\mathbb{K}[x]^{n\times n}$ in Hermite form. We exploit the triangular shape of $\mathbf{M}$ to generalize a divide-and-conquer approach which originates from fast minimal approximant basis algorithms. Besides recent techniques for this approach, we rely on high-order lifting to perform fast modular products of polynomial matrices of the form $\mathbf{P}\mathbf{F} \bmod \mathbf{M}$. Our algorithm uses $O\tilde{~}(m^{ω-1}D + n^ω D/m)$ operations in $\mathbb{K}$, where $D = \mathrm{deg}(\det(\mathbf{M}))$ is the $\mathbb{K}$-vector space dimension of $\mathbb{K}[x]^n/\mathcal{M}$, $O\tilde{~}(\cdot)$ indicates that logarithmic factors are omitted, and $ω$ is the exponent of matrix multiplication. This had previously only been achieved for a diagonal matrix $\mathbf{M}$. Furthermore, our algorithm can be used to compute the shifted Popov form of a nonsingular matrix within the same cost bound, up to logarithmic factors, as the previously fastest known algorithm, which is randomized.
SecureTime: Secure Multicast Time Synchronization
Venue: arXiv cs.CR 2017
Year: 2017

Due to the increasing dependency of critical infrastructure on synchronized clocks, network time synchronization protocols have become an attractive target for attackers. We identify data origin authentication as the key security objective and suggest to employ recently proposed high-performance digital signature schemes (Ed25519 and MQQ-SIG)) as foundation of a novel set of security measures to secure multicast time synchronization. We conduct experiments to verify the computational and communication efficiency for using these signatures in the standard time synchronization protocols NTP and PTP. We propose additional security measures to prevent replay attacks and to mitigate delay attacks. Our proposed solutions cover 1-step mode for NTP and PTP and we extend our security measures specifically to 2-step mode (PTP) and show that they have no impact on time synchronization's precision.
Multi-Labelled Value Networks for Computer Go
Venue: arXiv cs.AI 2017
Year: 2017

This paper proposes a new approach to a novel value network architecture for the game Go, called a multi-labelled (ML) value network. In the ML value network, different values (win rates) are trained simultaneously for different settings of komi, a compensation given to balance the initiative of playing first. The ML value network has three advantages, (a) it outputs values for different komi, (b) it supports dynamic komi, and (c) it lowers the mean squared error (MSE). This paper also proposes a new dynamic komi method to improve game-playing strength. This paper also performs experiments to demonstrate the merits of the architecture. First, the MSE of the ML value network is generally lower than the value network alone. Second, the program based on the ML value network wins by a rate of 67.6% against the program based on the value network alone. Third, the program with the proposed dynamic komi method significantly improves the playing strength over the baseline that does not use dynamic komi, especially for handicap games. To our knowledge, up to date, no handicap games have been played openly by programs using value networks. This paper provides these programs with a useful approach to playing handicap games.
Addressing Ambiguity in Multi-target Tracking by Hierarchical Strategy
Venue: arXiv cs.CV 2017
Year: 2017

This paper presents a novel hierarchical approach for the simultaneous tracking of multiple targets in a video. We use a network flow approach to link detections in low-level and tracklets in high-level. At each step of the hierarchy, the confidence of candidates is measured by using a new scoring system, ConfRank, that considers the quality and the quantity of its neighborhood. The output of the first stage is a collection of safe tracklets and unlinked high-confidence detections. For each individual detection, we determine if it belongs to an existing or is a new tracklet. We show the effect of our framework to recover missed detections and reduce switch identity. The proposed tracker is referred to as TVOD for multi-target tracking using the visual tracker and generic object detector. We achieve competitive results with lower identity switches on several datasets comparing to state-of-the-art.
Deep manifold-to-manifold transforming network for action recognition
Venue: arXiv cs.CV 2017
Year: 2017

Symmetric positive definite (SPD) matrices (e.g., covariances, graph Laplacians, etc.) are widely used to model the relationship of spatial or temporal domain. Nevertheless, SPD matrices are theoretically embedded on Riemannian manifolds. In this paper, we propose an end-to-end deep manifold-to-manifold transforming network (DMT-Net) which can make SPD matrices flow from one Riemannian manifold to another more discriminative one. To learn discriminative SPD features characterizing both spatial and temporal dependencies, we specifically develop three novel layers on manifolds: (i) the local SPD convolutional layer, (ii) the non-linear SPD activation layer, and (iii) the Riemannian-preserved recursive layer. The SPD property is preserved through all layers without any requirement of singular value decomposition (SVD), which is often used in the existing methods with expensive computation cost. Furthermore, a diagonalizing SPD layer is designed to efficiently calculate the final metric for the classification task. To evaluate our proposed method, we conduct extensive experiments on the task of action recognition, where input signals are popularly modeled as SPD matrices. The experimental results demonstrate that our DMT-Net is much more competitive over state-of-the-art.
Efficient Decentralized Visual Place Recognition From Full-Image Descriptors
Venue: arXiv cs.RO 2017
Year: 2017

In this paper, we discuss the adaptation of our decentralized place recognition method described in [1] to full image descriptors. As we had shown, the key to making a scalable decentralized visual place recognition lies in exploting deterministic key assignment in a distributed key-value map. Through this, it is possible to reduce bandwidth by up to a factor of n, the robot count, by casting visual place recognition to a key-value lookup problem. In [1], we exploited this for the bag-of-words method [3], [4]. Our method of casting bag-of-words, however, results in a complex decentralized system, which has inherently worse recall than its centralized counterpart. In this paper, we instead start from the recent full-image description method NetVLAD [5]. As we show, casting this to a key-value lookup problem can be achieved with k-means clustering, and results in a much simpler system than [1]. The resulting system still has some flaws, albeit of a completely different nature: it suffers when the environment seen during deployment lies in a different distribution in feature space than the environment seen during training.
Complex Quadrature Spatial Modulation
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we propose a spatial modulation (SM) scheme referred to as complex quadrature spatial modulation (CQSM). In contrast to quadrature spatial modulation (QSM), CQSM transmits two complex signal constellation symbols on the real and quadrature spatial dimensions at each channel use, increasing the spectral efficiency. To this end, signal symbols transmitted at any given time instant are drawn from two different modulation sets. The first modulation set is any of the conventional QAM/PSK alphabets, while the second is a rotated version of it. The optimal rotation angle is obtained through simulations for several modulation schemes and analytically proven for the case of QPSK, where both results coincide. Simulation results showed that CQSM outperformed QSM and generalized SM (GSM) by approximately 5 and 4.5 dB, respectively, for the same transmission rate. Its performance was similar to that of QSM; however, it achieved higher transmission rates. It was additionally shown numerically and analytically that CQSM outperformed QSM for a relatively large number of transmit antennas.
Max-Min Fair Transmit Precoding for Multi-group Multicasting in Massive MIMO
Venue: arXiv cs.IT 2017
Year: 2017

This paper considers the downlink precoding for physical layer multicasting in massive multiple-input-multiple-output (MIMO) systems. We study the max-min fairness (MMF) problem, where channel state information (CSI) at the transmitter is used to design precoding vectors that maximize the minimum spectral efficiency (SE) of the system, given fixed power budgets for uplink training and downlink transmission. Our system model accounts for channel estimation, pilot contamination, arbitrary pathlosses, and multi-group multicasting. We consider six scenarios with different transmission technologies (unicast and multicast), different pilot assignment strategies (dedicated or shared pilot assignments), and different precoding schemes (maximum ratio transmission and zero forcing), and derive achievable spectral efficiencies for all possible combinations. Then we solve the MMF problem for each of these scenarios and for any given pilot length we find the SE maximizing uplink pilot and downlink data transmission policies, all in closed-forms. We use these results to draw a general guideline for massive MIMO multicasting design, where for a given number of base station antennas, number of users, and coherence interval length, we determine the multicasting scheme that shall be used.
Class Specific Feature Selection for Interval Valued Data Through Interval K-Means Clustering
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, a novel feature selection approach for supervised interval valued features is proposed. The proposed approach takes care of selecting the class specific features through interval K-Means clustering. The kernel of K-Means clustering algorithm is modified to adapt interval valued data. During training, a set of samples corresponding to a class is fed into the interval K-Means clustering algorithm, which clusters features into K distinct clusters. Hence, there are K number of features corresponding to each class. Subsequently, corresponding to each class, the cluster representatives are chosen. This procedure is repeated for all the samples of remaining classes. During testing the feature indices correspond to each class are used for validating the given dataset through classification using suitable symbolic classifiers. For experimentation, four standard supervised interval datasets are used. The results show the superiority of the proposed model when compared with the other existing state-of-the-art feature selection methods.