OpenRaiser/Intern-Atlas huggingface dataset:
Forward Stagewise Additive Model for Collaborative Multiview Boosting
Venue: arXiv cs.LG 2016
Year: 2016

Multiview assisted learning has gained significant attention in recent years in supervised learning genre. Availability of high performance computing devices enables learning algorithms to search simultaneously over multiple views or feature spaces to obtain an optimum classification performance. The paper is a pioneering attempt of formulating a mathematical foundation for realizing a multiview aided collaborative boosting architecture for multiclass classification. Most of the present algorithms apply multiview learning heuristically without exploring the fundamental mathematical changes imposed on traditional boosting. Also, most of the algorithms are restricted to two class or view setting. Our proposed mathematical framework enables collaborative boosting across any finite dimensional view spaces for multiclass learning. The boosting framework is based on forward stagewise additive model which minimizes a novel exponential loss function. We show that the exponential loss function essentially captures difficulty of a training sample space instead of the traditional `1/0' loss. The new algorithm restricts a weak view from over learning and thereby preventing overfitting. The model is inspired by our earlier attempt on collaborative boosting which was devoid of mathematical justification. The proposed algorithm is shown to converge much nearer to global minimum in the exponential loss space and thus supersedes our previous algorithm. The paper also presents analytical and numerical analysis of convergence and margin bounds for multiview boosting algorithms and we show that our proposed ensemble learning manifests lower error bound and higher margin compared to our previous model. Also, the proposed model is compared with traditional boosting and recent multiview boosting algorithms.
Blind Deconvolution of PET Images using Anatomical Priors
Venue: arXiv cs.CV 2016
Year: 2016

Images from positron emission tomography (PET) provide metabolic information about the human body. They present, however, a spatial resolution that is limited by physical and instrumental factors often modeled by a blurring function. Since this function is typically unknown, blind deconvolution (BD) techniques are needed in order to produce a useful restored PET image. In this work, we propose a general BD technique that restores a low resolution blurry image using information from data acquired with a high resolution modality (e.g., CT-based delineation of regions with uniform activity in PET images). The proposed BD method is validated on synthetic and actual phantoms.
The Rainbow at the End of the Line --- A PPAD Formulation of the Colorful Carathéodory Theorem with Applications
Venue: arXiv cs.CG 2016
Year: 2016

Let $C_1,...,C_{d+1}$ be $d+1$ point sets in $\mathbb{R}^d$, each containing the origin in its convex hull. A subset $C$ of $\bigcup_{i=1}^{d+1} C_i$ is called a colorful choice (or rainbow) for $C_1, \dots, C_{d+1}$, if it contains exactly one point from each set $C_i$. The colorful Carathéodory theorem states that there always exists a colorful choice for $C_1,\dots,C_{d+1}$ that has the origin in its convex hull. This theorem is very general and can be used to prove several other existence theorems in high-dimensional discrete geometry, such as the centerpoint theorem or Tverberg's theorem. The colorful Carathéodory problem (CCP) is the computational problem of finding such a colorful choice. Despite several efforts in the past, the computational complexity of CCP in arbitrary dimension is still open. We show that CCP lies in the intersection of the complexity classes PPAD and PLS. This makes it one of the few geometric problems in PPAD and PLS that are not known to be solvable in polynomial time. Moreover, it implies that the problem of computing centerpoints, computing Tverberg partitions, and computing points with large simplicial depth is contained in $\text{PPAD} \cap \text{PLS}$. This is the first nontrivial upper bound on the complexity of these problems. Finally, we show that our PPAD formulation leads to a polynomial-time algorithm for a special case of CCP in which we have only two color classes $C_1$ and $C_2$ in $d$ dimensions, each with the origin in its convex hull, and we would like to find a set with half the points from each color class that contains the origin in its convex hull.
On Hybrid Pilot for Channel Estimation in Massive MIMO Uplink
Venue: arXiv cs.IT 2016
Year: 2016

This paper introduces a hybrid pilot-aided channel estimation technique for mitigating the effect of pilot contamination for the uplink of multi-cell multiuser massive MIMO systems. The proposed hybrid pilot is designed such that it enjoys the complementary advantages between time-multiplexed (TM) pilot and time-superimposed (TS) pilot, and thereby, allows superior solution to the conventional pilot schemes. We mathematically characterize the impact of hybrid pilot on the massive MIMO uplink by deriving a closed-form approximation for the uplink achievable rate. In large-number-of-antennas regime, we obtain the asymptotically optimal solution for hybrid pilot by jointly designing the TM pilot and the TS pilot. It is shown that either TM pilot or TS pilot has the advantages for large frame-size and limited frame-size transmission, respectively, while the hybrid pilot scheme can offer a superior performance to that employing either TM pilot or TS pilot. Numerical results demonstrate the effectiveness of the proposed design.
Adapting Deep Network Features to Capture Psychological Representations
Venue: arXiv cs.CV 2016
Year: 2016

Deep neural networks have become increasingly successful at solving classic perception problems such as object recognition, semantic segmentation, and scene understanding, often reaching or surpassing human-level accuracy. This success is due in part to the ability of DNNs to learn useful representations of high-dimensional inputs, a problem that humans must also solve. We examine the relationship between the representations learned by these networks and human psychological representations recovered from similarity judgments. We find that deep features learned in service of object classification account for a significant amount of the variance in human similarity judgments for a set of animal images. However, these features do not capture some qualitative distinctions that are a key part of human representations. To remedy this, we develop a method for adapting deep features to align with human similarity judgments, resulting in image representations that can potentially be used to extend the scope of psychological experiments.
Information Security as Strategic (In)effectivity
Venue: arXiv cs.CR 2016
Year: 2016

Security of information flow is commonly understood as preventing any information leakage, regardless of how grave or harmless consequences the leakage can have. In this work, we suggest that information security is not a goal in itself, but rather a means of preventing potential attackers from compromising the correct behavior of the system. To formalize this, we first show how two information flows can be compared by looking at the adversary's ability to harm the system. Then, we propose that the information flow in a system is effectively information-secure if it does not allow for more harm than its idealized variant based on the classical notion of noninterference.
Reference Governor Strategies for Vehicle Rollover Avoidance
Venue: arXiv cs.SY 2016
Year: 2016

The paper addresses the problem of vehicle rollover avoidance using reference governors applied to modify the driver steering input in vehicles with an active steering system. Several reference governor designs are presented and tested with a detailed nonlinear simulation model. The vehicle dynamics are highly nonlinear for large steering angles, including the conditions where the vehicle approaches a rollover onset, which necessitates reference governor design changes. Simulation results show that reference governor designs are effective in avoiding rollover. The results also demonstrate that the controllers are not overly conservative, adjusting the driver steering input only for very high steering angles.
Semi-Fragile Image Authentication based on CFD and 3-Bit Quantization
Venue: arXiv cs.MM 2016
Year: 2016

There is a great adventure of watermarking usage in the context of conventional authentication since it does not require additional storage space for supplementary metadata. However JPEG compression, being a conventional method to compress images, leads to exact authentication breaking. We discuss a semi-fragile watermarking system for digital images tolerant to JPEG/JPEG2000 compression. Recently we have published a selective authentication method based on Zernike moments. But unfortunately it has large computational complexity and not sufficiently good detection of small image modifications. In the current paper it is proposed (in contrast to Zernike moments approach) the usage of image finite differences and 3-bit quantization as the main technique. In order to embed a watermark (WM) into the image, some areas of the Haar wavelet transform coefficients are used. Simulation results show a good resistance of this method to JPEG compression with $\mbox{\rm CR}\leq 30\%$ (Compression Ratio), high probability of small image modification recognition, image quality assessments $\mbox{\rm PSNR}\geq 40$ (Peak signal-to-noise ratio) dB and $\mbox{\rm SSIM}\geq 0.98$ (Structural Similarity Index Measure) after embedding and lower computation complexity of WM embedding and extraction. All these properties qualify this approach as effective.
SANTIAGO: Spine Association for Neuron Topology Improvement and Graph Optimization
Venue: arXiv cs.CV 2016
Year: 2016

Developing automated and semi-automated solutions for reconstructing wiring diagrams of the brain from electron micrographs is important for advancing the field of connectomics. While the ultimate goal is to generate a graph of neuron connectivity, most prior automated methods have focused on volume segmentation rather than explicit graph estimation. In these approaches, one of the key, commonly occurring error modes is dendritic shaft-spine fragmentation. We posit that directly addressing this problem of connection identification may provide critical insight into estimating more accurate brain graphs. To this end, we develop a network-centric approach motivated by biological priors image grammars. We build a computer vision pipeline to reconnect fragmented spines to their parent dendrites using both fully-automated and semi-automated approaches. Our experiments show we can learn valid connections despite uncertain segmentation paths. We curate the first known reference dataset for analyzing the performance of various spine-shaft algorithms and demonstrate promising results that recover many previously lost connections. Our automated approach improves the local subgraph score by more than four times and the full graph score by 60 percent. These data, results, and evaluation tools are all available to the broader scientific community. This reframing of the connectomics problem illustrates a semantic, biologically inspired solution to remedy a major problem with neuron tracking.
Mapping mobility patterns to public spaces in a medium-sized city using geolocated tweets
Venue: arXiv cs.SI 2016
Year: 2016

This research evidences the usefulness of open big data to map mobility patterns in a medium-sized city. Motivated by the novel analysis that big data allow worldwide and in large metropolitan areas, we developed a methodology aiming to complement origin-destination surveys with à la carte spatial boundaries and updated data at a minimum cost. This paper validates the use of Twitter data to map the impact of public spaces on the different parts of the metropolitan area of Concepción, Chile. Results have been validated by local experts and evidence the main mobility patterns towards spaces of social interaction like malls, leisure areas, parks and so on. The map represents the mobility patterns from census districts to different categories of public spaces with schematic lines at the metropolitan scale and it is centred in the city of Concepción (Chile) and its surroundings (~10 kilometres).
Learning Joint Representations of Videos and Sentences with Web Image Search
Venue: arXiv cs.CV 2016
Year: 2016

Our objective is video retrieval based on natural language queries. In addition, we consider the analogous problem of retrieving sentences or generating descriptions given an input video. Recent work has addressed the problem by embedding visual and textual inputs into a common space where semantic similarities correlate to distances. We also adopt the embedding approach, and make the following contributions: First, we utilize web image search in sentence embedding process to disambiguate fine-grained visual concepts. Second, we propose embedding models for sentence, image, and video inputs whose parameters are learned simultaneously. Finally, we show how the proposed model can be applied to description generation. Overall, we observe a clear improvement over the state-of-the-art methods in the video and sentence retrieval tasks. In description generation, the performance level is comparable to the current state-of-the-art, although our embeddings were trained for the retrieval tasks.
A combined Approach Based on Fuzzy Classification and Contextual Region Growing to Image Segmentation
Venue: arXiv cs.CV 2016
Year: 2016

We present in this paper an image segmentation approach that combines a fuzzy semantic region classification and a context based region-growing. Input image is first over-segmented. Then, prior domain knowledge is used to perform a fuzzy classification of these regions to provide a fuzzy semantic labeling. This allows the proposed approach to operate at high level instead of using low-level features and consequently to remedy to the problem of the semantic gap. Each over-segmented region is represented by a vector giving its corresponding membership degrees to the different thematic labels and the whole image is therefore represented by a Regions Partition Matrix. The segmentation is achieved on this matrix instead of the image pixels through two main phases: focusing and propagation. The focusing aims at selecting seeds regions from which information propagation will be performed. Thepropagation phase allows to spread toward others regions and using fuzzy contextual information the needed knowledge ensuring the semantic segmentation. An application of the proposed approach on mammograms shows promising results
Database of handwritten Arabic mathematical formulas images
Venue: arXiv cs.CV 2016
Year: 2016

Although publicly available, ground-truthed database have proven useful for training, evaluating, and comparing recognition systems in many domains, the availability of such database for handwritten Arabic mathematical formula recognition in particular, is currently quite poor. In this paper, we present a new public database that contains mathematical expressions available in their off-line handwritten form. Here, we describe the different steps that allowed us to acquire this database, from the creation of the mathematical expression corpora to the transcription of the collected data. Currently, the dataset contains 4 238 off-line handwritten mathematical expressions written by 66 writers and 20 300 handwritten isolated symbol images. The ground truth is also provided for the handwritten expressions as XML files with the number of symbols, and the MATHML structure.
Maximum-Likelihood Detection for Energy-Efficient Timing Acquisition in NB-IoT
Venue: arXiv cs.NI 2016
Year: 2016

Initial timing acquisition in narrow-band IoT (NB-IoT) devices is done by detecting a periodically transmitted known sequence. The detection has to be done at lowest possible latency, because the RF-transceiver, which dominates downlink power consumption of an NB-IoT modem, has to be turned on throughout this time. Auto-correlation detectors show low computational complexity from a signal processing point of view at the price of a higher detection latency. In contrast a maximum likelihood cross-correlation detector achieves low latency at a higher complexity as shown in this paper. We present a hardware implementation of the maximum likelihood cross-correlation detection. The detector achieves an average detection latency which is a factor of two below that of an auto-correlation method and is able to reduce the required energy per timing acquisition by up to 34%.
Fault-Tolerant Gathering of Mobile Robots with Weak Multiplicity Detection
Venue: arXiv cs.DC 2016
Year: 2016

There has been a wide interest in designing distributed algorithms for tiny robots. In particular, it has been shown that the robots can complete certain tasks even in the presence of faulty robots. In this paper, we focus on gathering of all non-faulty robots at a single point in presence of faulty robots. We propose a wait-free algorithm (i.e., no robot waits for other robot and algorithm instructs each robot to move in every step, unless it is already at the gathering location), that gathers all non-faulty robots in semi-synchronous model without any agreement in the coordinate system and with weak multiplicity detection (i.e., a robot can only detect that either there is one or more robot at a location) in the presence of at most $n-1$ faulty robots for $n\geqslant 3$. We show that the required capability for gathering robots is minimal in the above model, since relaxing it further makes gathering impossible to solve. Also, we introduce an intermediate scheduling model \textit{ASYNC$_{IC}$} between the asynchronous ( i.e., no instantaneous movement or computation) and the semi-synchronous (i.e., both instantaneous movement and computation) as the asynchronous model with instantaneous computation. Then we propose another algorithm in \textit{ASYNC$_{IC}$} model for gathering all non-faulty robots with weak multiplicity detection without any agreement on the coordinate system in the presence of at most $\lfloor n/2\rfloor-2$ faulty robots for $n\geqslant 7$.
ASP for Minimal Entailment in a Rational Extension of SROEL
Venue: arXiv cs.AI 2016
Year: 2016

In this paper we exploit Answer Set Programming (ASP) for reasoning in a rational extension SROEL-R-T of the low complexity description logic SROEL, which underlies the OWL EL ontology language. In the extended language, a typicality operator T is allowed to define concepts T(C) (typical C's) under a rational semantics. It has been proven that instance checking under rational entailment has a polynomial complexity. To strengthen rational entailment, in this paper we consider a minimal model semantics. We show that, for arbitrary SROEL-R-T knowledge bases, instance checking under minimal entailment is Π^P_2-complete. Relying on a Small Model result, where models correspond to answer sets of a suitable ASP encoding, we exploit Answer Set Preferences (and, in particular, the asprin framework) for reasoning under minimal entailment. The paper is under consideration for acceptance in Theory and Practice of Logic Programming.
An $\widetilde{O}(n)$ Queries Adaptive Tester for Unateness
Venue: arXiv cs.DS 2016
Year: 2016

We present an adaptive tester for the unateness property of Boolean functions. Given a function $f:\{0,1\}^n \to \{0,1\}$ the tester makes $O(n \log(n)/ε)$ adaptive queries to the function. The tester always accepts a unate function, and rejects with probability at least 0.9 if a function is $ε$-far from being unate.
Parameterized Algorithms for the Maximum Agreement Forest Problem on Multiple Rooted Multifurcating Trees
Venue: arXiv cs.DS 2016
Year: 2016

The Maximum Agreement Forest problem has been extensively studied in phylogenetics. Most previous work is on two binary phylogenetic trees. In this paper, we study a generalized version of the problem: the Maximum Agreement Forest problem on multiple rooted multifurcating phylogenetic trees, from the perspective of fixed-parameter algorithms. By taking advantage of a new branch-and-bound strategy, two parameterized algorithms, with running times $O(2.42^k m^3 n^4)$ and $O(2.74^k m^3 n^5)$, respectively, are presented for the hard version and the soft version of the problem, which correspond to two different biological meanings to the polytomies in multifurcating phylogenetic trees.
Convolutional Oriented Boundaries
Venue: arXiv cs.CV 2016
Year: 2016

We present Convolutional Oriented Boundaries (COB), which produces multiscale oriented contours and region hierarchies starting from generic image classification Convolutional Neural Networks (CNNs). COB is computationally efficient, because it requires a single CNN forward pass for contour detection and it uses a novel sparse boundary representation for hierarchical segmentation; it gives a significant leap in performance over the state-of-the-art, and it generalizes very well to unseen categories and datasets. Particularly, we show that learning to estimate not only contour strength but also orientation provides more accurate results. We perform extensive experiments on BSDS, PASCAL Context, PASCAL Segmentation, and MS-COCO, showing that COB provides state-of-the-art contours, region hierarchies, and object proposals in all datasets.
Resolving Spatial-Time Conflicts In A Set Of Any-angle Or Angle-constrained Grid Paths
Venue: arXiv cs.AI 2016
Year: 2016

We study the multi-agent path finding problem (MAPF) for a group of agents which are allowed to move into arbitrary directions on a 2D square grid. We focus on centralized conflict resolution for independently computed plans. We propose an algorithm that eliminates conflicts by using local re-planning and introducing time offsets to the execution of paths by different agents. Experimental results show that the algorithm can find high quality conflict-free solutions at low computational cost.
Deep Convolution Networks for Compression Artifacts Reduction
Venue: arXiv cs.CV 2016
Year: 2016

Lossy compression introduces complex compression artifacts, particularly blocking artifacts, ringing effects and blurring. Existing algorithms either focus on removing blocking artifacts and produce blurred output, or restore sharpened images that are accompanied with ringing effects. Inspired by the success of deep convolutional networks (DCN) on superresolution, we formulate a compact and efficient network for seamless attenuation of different compression artifacts. To meet the speed requirement of real-world applications, we further accelerate the proposed baseline model by layer decomposition and joint use of large-stride convolutional and deconvolutional layers. This also leads to a more general CNN framework that has a close relationship with the conventional Multi-Layer Perceptron (MLP). Finally, the modified network achieves a speed up of 7.5 times with almost no performance loss compared to the baseline model. We also demonstrate that a deeper model can be effectively trained with features learned in a shallow network. Following a similar "easy to hard" idea, we systematically investigate three practical transfer settings and show the effectiveness of transfer learning in low-level vision problems. Our method shows superior performance than the state-of-the-art methods both on benchmark datasets and a real-world use case.