OpenRaiser/Intern-Atlas huggingface dataset:
Joint direct estimation of 3D geometry and 3D motion using spatio temporal gradients
Venue: arXiv cs.CV 2018
Year: 2018

Conventional image motion based structure from motion methods first compute optical flow, then solve for the 3D motion parameters based on the epipolar constraint, and finally recover the 3D geometry of the scene. However, errors in optical flow due to regularization can lead to large errors in 3D motion and structure. This paper investigates whether performance and consistency can be improved by avoiding optical flow estimation in the early stages of the structure from motion pipeline, and it proposes a new direct method based on image gradients (normal flow) only. The main idea lies in a reformulation of the positive-depth constraint, which allows the use of well-known minimization techniques to solve for 3D motion. The 3D motion estimate is then refined and structure estimated adding a regularization based on depth. Experimental comparisons on standard synthetic datasets and the real-world driving benchmark dataset KITTI using three different optic flow algorithms show that the method achieves better accuracy in all but one case. Furthermore, it outperforms existing normal flow based 3D motion estimation techniques. Finally, the recovered 3D geometry is shown to be also very accurate.
Test for penetration in Wi-Fi network: attacks on WPA2-PSK and WPA2-Enterprise
Venue: arXiv cs.CR 2018
Year: 2018

In this work the wireless networks security algorithms were analyzed. The fundamentals of the WPA and WPA2 safety algorithms, their weaknesses and ways of attacking WPA and WPA2 Enterprise Wireless Networks are described. Successful attack on the WPA2-PSK and WPA2-Enterprise was carried out during the performance of work. The progress of this attack and its results were described.
A Note on Polynomial Identity Testing for Depth-3 Circuits
Venue: arXiv cs.CC 2018
Year: 2018

Let $C$ be a depth-3 arithmetic circuit of size at most $s$, computing a polynomial $ f \in \mathbb{F}[x_1,\ldots, x_n] $ (where $\mathbb{F}$ = $\mathbb{Q}$ or $\mathbb{C}$) and the fan-in of the product gates of $C$ is bounded by $d$. We give a deterministic polynomial identity testing algorithm to check whether $f\equiv 0$ or not in time $ 2^d \text{ poly}(n,s) $.
Hierarchical Beamforming: Resource Allocation, Fairness and Flow Level Performance
Venue: arXiv cs.NI 2018
Year: 2018

We consider hierarchical beamforming in wireless networks. For a given population of flows, we propose computationally efficient algorithms for fair rate allocation including proportional fairness and max-min fairness. We next propose closed-form formulas for flow level performance, for both elastic (with either proportional fairness and max-min fairness) and streaming traffic. We further assess the performance of hierarchical beamforming using numerical experiments. Since the proposed solutions have low complexity compared to conventional beamforming, our work suggests that hierarchical beamforming is a promising candidate for the implementation of beamforming in future cellular networks.
GANomaly: Semi-Supervised Anomaly Detection via Adversarial Training
Venue: arXiv cs.CV 2018
Year: 2018

Anomaly detection is a classical problem in computer vision, namely the determination of the normal from the abnormal when datasets are highly biased towards one class (normal) due to the insufficient sample size of the other class (abnormal). While this can be addressed as a supervised learning problem, a significantly more challenging problem is that of detecting the unknown/unseen anomaly case that takes us instead into the space of a one-class, semi-supervised learning paradigm. We introduce such a novel anomaly detection model, by using a conditional generative adversarial network that jointly learns the generation of high-dimensional image space and the inference of latent space. Employing encoder-decoder-encoder sub-networks in the generator network enables the model to map the input image to a lower dimension vector, which is then used to reconstruct the generated output image. The use of the additional encoder network maps this generated image to its latent representation. Minimizing the distance between these images and the latent vectors during training aids in learning the data distribution for the normal samples. As a result, a larger distance metric from this learned data distribution at inference time is indicative of an outlier from that distribution - an anomaly. Experimentation over several benchmark datasets, from varying domains, shows the model efficacy and superiority over previous state-of-the-art approaches.
A Distributed Algorithm for Finding Hamiltonian Cycles in Random Graphs in O(log n) Time
Venue: arXiv cs.DC 2018
Year: 2018

It is known for some time that a random graph $G(n,p)$ contains w.h.p. a Hamiltonian cycle if $p$ is larger than the critical value $p_{crit}= (\log n + \log \log n + ω_n)/n$. The determination of a concrete Hamiltonian cycle is even for values much larger than $p_{crit}$ a nontrivial task. In this paper we consider random graphs $G(n,p)$ with $p$ in $\tildeΩ(1/\sqrt{n})$, where $\tildeΩ$ hides poly-logarithmic factors in $n$. For this range of $p$ we present a distributed algorithm ${\cal A}_{HC}$ that finds w.h.p. a Hamiltonian cycle in $O(\log n)$ rounds. The algorithm works in the synchronous model and uses messages of size $O(\log n)$ and $O(\log n)$ memory per node.
A Robust Background Initialization Algorithm with Superpixel Motion Detection
Venue: arXiv cs.CV 2018
Year: 2018

Scene background initialization allows the recovery of a clear image without foreground objects from a video sequence, which is generally the first step in many computer vision and video processing applications. The process may be strongly affected by some challenges such as illumination changes, foreground cluttering, intermittent movement, etc. In this paper, a robust background initialization approach based on superpixel motion detection is proposed. Both spatial and temporal characteristics of frames are adopted to effectively eliminate foreground objects. A subsequence with stable illumination condition is first selected for background estimation. Images are segmented into superpixels to preserve spatial texture information and foreground objects are eliminated by superpixel motion filtering process. A low-complexity density-based clustering is then performed to generate reliable background candidates for final background determination. The approach has been evaluated on SBMnet dataset and it achieves a performance superior or comparable to other state-of-the-art works with faster processing speed. Moreover, in those complex and dynamic categories, the algorithm produces the best results showing the robustness against very challenging scenarios.
Scheduling Policies for Age Minimization in Wireless Networks with Unknown Channel State
Venue: arXiv cs.NI 2018
Year: 2018

Age of information (AoI) is a recently proposed metric that measures the time elapsed since the generation of the last received information update. We consider the problem of AoI minimization for a network under general interference constraints, and time varying channel. We study the case where the channel statistics are known, but the current channel state is unknown. We propose two scheduling policies, namely, the virtual queue based policy and age-based policy. In the virtual queue based policy, the scheduler schedules links with maximum weighted sum of the virtual queue lengths, while in the age-based policy, the scheduler schedules links with maximum weighted sum of a function of link AoI. We prove that the virtual queue based policy is peak age optimal, up to an additive constant, while the age-based policy is at most factor 4 away from the optimal age. Numerical results suggest that both the proposed policies are, in fact, very close to the optimal.
Subspace Estimation from Incomplete Observations: A High-Dimensional Analysis
Venue: arXiv cs.LG 2018
Year: 2018

We present a high-dimensional analysis of three popular algorithms, namely, Oja's method, GROUSE and PETRELS, for subspace estimation from streaming and highly incomplete observations. We show that, with proper time scaling, the time-varying principal angles between the true subspace and its estimates given by the algorithms converge weakly to deterministic processes when the ambient dimension $n$ tends to infinity. Moreover, the limiting processes can be exactly characterized as the unique solutions of certain ordinary differential equations (ODEs). A finite sample bound is also given, showing that the rate of convergence towards such limits is $\mathcal{O}(1/\sqrt{n})$. In addition to providing asymptotically exact predictions of the dynamic performance of the algorithms, our high-dimensional analysis yields several insights, including an asymptotic equivalence between Oja's method and GROUSE, and a precise scaling relationship linking the amount of missing data to the signal-to-noise ratio. By analyzing the solutions of the limiting ODEs, we also establish phase transition phenomena associated with the steady-state performance of these techniques.
RotDCF: Decomposition of Convolutional Filters for Rotation-Equivariant Deep Networks
Venue: arXiv cs.CV 2018
Year: 2018

Explicit encoding of group actions in deep features makes it possible for convolutional neural networks (CNNs) to handle global deformations of images, which is critical to success in many vision tasks. This paper proposes to decompose the convolutional filters over joint steerable bases across the space and the group geometry simultaneously, namely a rotation-equivariant CNN with decomposed convolutional filters (RotDCF). This decomposition facilitates computing the joint convolution, which is proved to be necessary for the group equivariance. It significantly reduces the model size and computational complexity while preserving performance, and truncation of the bases expansion serves implicitly to regularize the filters. On datasets involving in-plane and out-of-plane object rotations, RotDCF deep features demonstrate greater robustness and interpretability than regular CNNs. The stability of the equivariant representation to input variations is also proved theoretically under generic assumptions on the filters in the decomposed form. The RotDCF framework can be extended to groups other than rotations, providing a general approach which achieves both group equivariance and representation stability at a reduced model size.
It's all Relative: Monocular 3D Human Pose Estimation from Weakly Supervised Data
Venue: arXiv cs.CV 2018
Year: 2018

We address the problem of 3D human pose estimation from 2D input images using only weakly supervised training data. Despite showing considerable success for 2D pose estimation, the application of supervised machine learning to 3D pose estimation in real world images is currently hampered by the lack of varied training images with corresponding 3D poses. Most existing 3D pose estimation algorithms train on data that has either been collected in carefully controlled studio settings or has been generated synthetically. Instead, we take a different approach, and propose a 3D human pose estimation algorithm that only requires relative estimates of depth at training time. Such training signal, although noisy, can be easily collected from crowd annotators, and is of sufficient quality for enabling successful training and evaluation of 3D pose algorithms. Our results are competitive with fully supervised regression based approaches on the Human3.6M dataset, despite using significantly weaker training data. Our proposed algorithm opens the door to using existing widespread 2D datasets for 3D pose estimation by allowing fine-tuning with noisy relative constraints, resulting in more accurate 3D poses.
Fully Convolutional Model for Variable Bit Length and Lossy High Density Compression of Mammograms
Venue: arXiv cs.CV 2018
Year: 2018

Early works on medical image compression date to the 1980's with the impetus on deployment of teleradiology systems for high-resolution digital X-ray detectors. Commercially deployed systems during the period could compress 4,096 x 4,096 sized images at 12 bpp to 2 bpp using lossless arithmetic coding, and over the years JPEG and JPEG2000 were imbibed reaching upto 0.1 bpp. Inspired by the reprise of deep learning based compression for natural images over the last two years, we propose a fully convolutional autoencoder for diagnostically relevant feature preserving lossy compression. This is followed by leveraging arithmetic coding for encapsulating high redundancy of features for further high-density code packing leading to variable bit length. We demonstrate performance on two different publicly available digital mammography datasets using peak signal-to-noise ratio (pSNR), structural similarity (SSIM) index and domain adaptability tests between datasets. At high density compression factors of >300x (~0.04 bpp), our approach rivals JPEG and JPEG2000 as evaluated through a Radiologist's visual Turing test.
On the Capacity of MIMO Broadband Power Line Communications Channels
Venue: arXiv cs.IT 2018
Year: 2018

Communications over power lines in the frequency range above 2 MHz, commonly referred to as broadband (BB) power line communications (PLC), has been the focus of increasing research attention and standardization efforts in recent years. BB-PLC channels are characterized by a dominant colored non-Gaussian additive noise, as well as by periodic variations of the channel impulse response and the noise statistics. In this work we study the fundamental rate limits for BB-PLC channels by bounding their capacity while accounting for the unique properties of these channels. We obtain explicit expressions for the derived bounds for several BB-PLC noise models, and illustrate the resulting fundamental limits in a numerical analysis.
Fast reinforcement learning for decentralized MAC optimization
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we propose a novel decentralized framework for optimizing the transmission strategy of Irregular Repetition Slotted ALOHA (IRSA) protocol in sensor networks. We consider a hierarchical communication framework that ensures adaptivity to changing network conditions and does not require centralized control. The proposed solution is inspired by the reinforcement learning literature, and, in particular, Q-learning. To deal with sensor nodes' limited lifetime and communication range, we allow them to decide how many packet replicas to transmit considering only their own buffer state. We show that this information is sufficient and can help avoiding packets' collisions and improving the throughput significantly. We solve the problem using the decentralized partially observable Markov Decision Process (Dec-POMDP) framework, where we allow each node to decide independently of the others how many packet replicas to transmit. We enhance the proposed Q-learning based method with the concept of virtual experience, and we theoretically and experimentally prove that convergence time is, thus, significantly reduced. The experiments prove that our method leads to large throughput gains, in particular when network traffic is heavy, and scales well with the size of the network. To comprehend the effect of the problem's nature on the learning dynamics and vice versa, we investigate the waterfall effect, a severe degradation in performance above a particular traffic load, typical for codes-on-graphs and prove that our algorithm learns to alleviate it.
Scene Understanding Networks for Autonomous Driving based on Around View Monitoring System
Venue: arXiv cs.CV 2018
Year: 2018

Modern driver assistance systems rely on a wide range of sensors (RADAR, LIDAR, ultrasound and cameras) for scene understanding and prediction. These sensors are typically used for detecting traffic participants and scene elements required for navigation. In this paper we argue that relying on camera based systems, specifically Around View Monitoring (AVM) system has great potential to achieve these goals in both parking and driving modes with decreased costs. The contributions of this paper are as follows: we present a new end-to-end solution for delimiting the safe drivable area for each frame by means of identifying the closest obstacle in each direction from the driving vehicle, we use this approach to calculate the distance to the nearest obstacles and we incorporate it into a unified end-to-end architecture capable of joint object detection, curb detection and safe drivable area detection. Furthermore, we describe the family of networks for both a high accuracy solution and a low complexity solution. We also introduce further augmentation of the base architecture with 3D object detection.
Trusted Neural Networks for Safety-Constrained Autonomous Control
Venue: arXiv cs.LG 2018
Year: 2018

We propose Trusted Neural Network (TNN) models, which are deep neural network models that satisfy safety constraints critical to the application domain. We investigate different mechanisms for incorporating rule-based knowledge in the form of first-order logic constraints into a TNN model, where rules that encode safety are accompanied by weights indicating their relative importance. This framework allows the TNN model to learn from knowledge available in form of data as well as logical rules. We propose multiple approaches for solving this problem: (a) a multi-headed model structure that allows trade-off between satisfying logical constraints and fitting training data in a unified training framework, and (b) creating a constrained optimization problem and solving it in dual formulation by posing a new constrained loss function and using a proximal gradient descent algorithm. We demonstrate the efficacy of our TNN framework through experiments using the open-source TORCS~\cite{BernhardCAA15} 3D simulator for self-driving cars. Experiments using our first approach of a multi-headed TNN model, on a dataset generated by a customized version of TORCS, show that (1) adding safety constraints to a neural network model results in increased performance and safety, and (2) the improvement increases with increasing importance of the safety constraints. Experiments were also performed using the second approach of proximal algorithm for constrained optimization --- they demonstrate how the proposed method ensures that (1) the overall TNN model satisfies the constraints even when the training data violates some of the constraints, and (2) the proximal gradient descent algorithm on the constrained objective converges faster than the unconstrained version.
Tree Edit Distance Learning via Adaptive Symbol Embeddings: Supplementary Materials and Results
Venue: arXiv cs.LG 2018
Year: 2018

Metric learning has the aim to improve classification accuracy by learning a distance measure which brings data points from the same class closer together and pushes data points from different classes further apart. Recent research has demonstrated that metric learning approaches can also be applied to trees, such as molecular structures, abstract syntax trees of computer programs, or syntax trees of natural language, by learning the cost function of an edit distance, i.e. the costs of replacing, deleting, or inserting nodes in a tree. However, learning such costs directly may yield an edit distance which violates metric axioms, is challenging to interpret, and may not generalize well. In this contribution, we propose a novel metric learning approach for trees which learns an edit distance indirectly by embedding the tree nodes as vectors, such that the Euclidean distance between those vectors supports class discrimination. We learn such embeddings by reducing the distance to prototypical trees from the same class and increasing the distance to prototypical trees from different classes. In our experiments, we show that our proposed metric learning approach improves upon the state-of-the-art in metric learning for trees on six benchmark data sets, ranging from computer science over biomedical data to a natural-language processing data set containing over 300,000 nodes.
Stochastic Model Predictive Control for Linear Systems using Probabilistic Reachable Sets
Venue: arXiv cs.SY 2018
Year: 2018

In this paper we propose a stochastic model predictive control (MPC) algorithm for linear discrete-time systems affected by possibly unbounded additive disturbances and subject to probabilistic constraints. Constraints are treated in analogy to robust MPC using a constraint tightening based on the concept of probabilistic reachable sets, which is shown to provide closed-loop fulfillment of chance constraints under a unimodality assumption on the disturbance distribution. A control scheme reverting to a backup solution from a previous time step in case of infeasibility is proposed, for which an asymptotic average performance bound is derived. Two examples illustrate the approach, highlighting closed-loop chance constraint satisfaction and the benefits of the proposed controller in the presence of unmodeled disturbances.
On-board Range-based Relative Localization for Micro Aerial Vehicles in indoor Leader-Follower Flight
Venue: arXiv cs.RO 2018
Year: 2018

We present a range-based solution for indoor relative localization by Micro Air Vehicles (MAVs), achieving sufficient accuracy for leader-follower flight. Moving forward from previous work, we removed the dependency on a common heading measurement by the MAVs, making the relative localization accuracy independent of magnetometer readings. We found that this restricts the relative maneuvers that guarantee observability, and also that higher accuracy range measurements are required to rectify the missing heading information, yet both disadvantages can be tackled. Our implementation uses Ultra Wide Band, for both range measurements between MAVs and sharing their velocities, accelerations, yaw rates, and height with each other. We used this on real MAVs and performed leader-follower flight in an indoor environment. The follower MAVs could follow the leader MAV in close proximity for the entire durations of the flights. The followers were autonomous and used only on-board sensors to track and follow the leader.
Private Information Retrieval using Product-Matrix Minimum Storage Regenerating Codes
Venue: arXiv cs.IT 2018
Year: 2018

Private Information Retrieval (PIR) schemes allow a user to retrieve a record from the server without revealing any information on which record is being downloaded. In this paper, we consider PIR schemes where the database is stored using Minimum Storage Regenerating (MSR) codes which is a class of optimal regenerating codes providing efficient repair when a node failure occurs in the system. We analyse the relationship between the costs of privacy, storage and repair, and also construct an explicit PIR scheme that uses the MSR codes from [3] to achieve the optimal curve of the trade-off.
Supervisory Control of Probabilistic Discrete Event Systems under Partial Observation
Venue: arXiv cs.SY 2018
Year: 2018

The supervisory control of probabilistic discrete event systems (PDESs) is investigated under the assumptions that the supervisory controller (supervisor) is probabilistic and has a partial observation. The probabilistic P-supervisor is defined, which specifies a probability distribution on the control patterns for each observation. The notions of the probabilistic controllability and observability are proposed and demonstrated to be a necessary and sufficient conditions for the existence of the probabilistic P-supervisors. Moreover, the polynomial verification algorithms for the probabilistic controllability and observability are put forward. In addition, the infimal probabilistic controllable and observable superlanguage is introduced and computed as the solution of the optimal control problem of PDESs. Several examples are presented to illustrate the results obtained.