OpenRaiser/Intern-Atlas huggingface dataset:
ORBSLAM-based Endoscope Tracking and 3D Reconstruction
Venue: arXiv cs.CV 2016
Year: 2016

We aim to track the endoscope location inside the surgical scene and provide 3D reconstruction, in real-time, from the sole input of the image sequence captured by the monocular endoscope. This information offers new possibilities for developing surgical navigation and augmented reality applications. The main benefit of this approach is the lack of extra tracking elements which can disturb the surgeon performance in the clinical routine. It is our first contribution to exploit ORBSLAM, one of the best performing monocular SLAM algorithms, to estimate both of the endoscope location, and 3D structure of the surgical scene. However, the reconstructed 3D map poorly describe textureless soft organ surfaces such as liver. It is our second contribution to extend ORBSLAM to be able to reconstruct a semi-dense map of soft organs. Experimental results on in-vivo pigs, shows a robust endoscope tracking even with organs deformations and partial instrument occlusions. It also shows the reconstruction density, and accuracy against ground truth surface obtained from CT.
Tracking Completion
Venue: arXiv cs.CV 2016
Year: 2016

A fundamental component of modern trackers is an online learned tracking model, which is typically modeled either globally or locally. The two kinds of models perform differently in terms of effectiveness and robustness under different challenging situations. This work exploits the advantages of both models. A subspace model, from a global perspective, is learned from previously obtained targets via rank-minimization to address the tracking, and a pixel-level local observation is leveraged si- multaneously, from a local point of view, to augment the subspace model. A matrix completion method is employed to integrate the two models. Unlike previous tracking methods, which locate the target among all fully observed target candidates, the proposed approach first estimates an expected target via the matrix completion through partially observed target candidates, and then, identifies the target according to the estimation accuracy with respect to the target candidates. Specifically, the tracking is formulated as a problem of target appearance estimation. Extensive experiments on various challenging video sequences verify the effectiveness of the proposed approach and demonstrate that the proposed tracker outperforms other popular state-of-the-art trackers.
NoFAQ: Synthesizing Command Repairs from Examples
Venue: arXiv cs.PL 2016
Year: 2016

Command-line tools are confusing and hard to use for novice programmers due to their cryptic error messages and lack of documentation. Novice users often resort to online help-forums for finding corrections to their buggy commands, but have a hard time in searching precisely for posts that are relevant to their problem and then applying the suggested solutions to their buggy command. We present a tool, NoFAQ, that uses a set of rules to suggest possible fixes when users write buggy commands that trigger commonly occurring errors. The rules are expressed in a language called FixIt and each rule pattern-matches against the user's buggy command and the corresponding error message, and uses these inputs to produce a possible fixed command. Our main contribution is an algorithm based on lazy VSA for synthesizing FixIt rules from examples of buggy and repaired commands. The algorithm allows users to add new rules in NoFAQ without having to manually encode them. We present the evaluation of NoFAQ on 92 benchmark problems and show that NoFAQ is able to instantly synthesize rules for 81 benchmark problems in real time using just 2 to 5 input-output examples for each rule.
Learning and Inferring Relations in Cortical Networks
Venue: arXiv cs.NE 2016
Year: 2016

A pressing scientific challenge is to understand how brains work. Of particular interest is the neocortex,the part of the brain that is especially large in humans, capable of handling a wide variety of tasks including visual, auditory, language, motor, and abstract processing. These functionalities are processed in different self-organized regions of the neocortical sheet, and yet the anatomical structure carrying out the processing is relatively uniform across the sheet. We are at a loss to explain, simulate, or understand such a multi-functional homogeneous sheet-like computational structure - we do not have computational models which work in this way. Here we present an important step towards developing such models: we show how uniform modules of excitatory and inhibitory neurons can be connected bidirectionally in a network that, when exposed to input in the form of population codes, learns the input encodings as well as the relationships between the inputs. STDP learning rules lead the modules to self-organize into a relational network, which is able to infer missing inputs,restore noisy signals, decide between conflicting inputs, and combine cues to improve estimates. These networks show that it is possible for a homogeneous network of spiking units to self-organize so as to provide meaningful processing of its inputs. If such networks can be scaled up, they could provide an initial computational model relevant to the large scale anatomy of the neocortex.
Low-rank Multi-view Clustering in Third-Order Tensor Space
Venue: arXiv cs.CV 2016
Year: 2016

The plenty information from multiple views data as well as the complementary information among different views are usually beneficial to various tasks, e.g., clustering, classification, de-noising. Multi-view subspace clustering is based on the fact that the multi-view data are generated from a latent subspace. To recover the underlying subspace structure, the success of the sparse and/or low-rank subspace clustering has been witnessed recently. Despite some state-of-the-art subspace clustering approaches can numerically handle multi-view data, by simultaneously exploring all possible pairwise correlation within views, the high order statistics is often disregarded which can only be captured by simultaneously utilizing all views. As a consequence, the clustering performance for multi-view data is compromised. To address this issue, in this paper, a novel multi-view clustering method is proposed by using \textit{t-product} in third-order tensor space. Based on the circular convolution operation, multi-view data can be effectively represented by a \textit{t-linear} combination with sparse and low-rank penalty using "self-expressiveness". Our extensive experimental results on facial, object, digits image and text data demonstrate that the proposed method outperforms the state-of-the-art methods in terms of many criteria.
American Sign Language fingerspelling recognition from video: Methods for unrestricted recognition and signer-independence
Venue: arXiv cs.CL 2016
Year: 2016

In this thesis, we study the problem of recognizing video sequences of fingerspelled letters in American Sign Language (ASL). Fingerspelling comprises a significant but relatively understudied part of ASL, and recognizing it is challenging for a number of reasons: It involves quick, small motions that are often highly coarticulated; it exhibits significant variation between signers; and there has been a dearth of continuous fingerspelling data collected. In this work, we propose several types of recognition approaches, and explore the signer variation problem. Our best-performing models are segmental (semi-Markov) conditional random fields using deep neural network-based features. In the signer-dependent setting, our recognizers achieve up to about 8% letter error rates. The signer-independent setting is much more challenging, but with neural network adaptation we achieve up to 17% letter error rates.
A short review and primer on event-related potentials in human computer interaction applications
Venue: arXiv cs.HC 2016
Year: 2016

The application of psychophysiology in human-computer interaction is a growing field with significant potential for future smart personalised systems. Working in this emerging field requires comprehension of an array of physiological signals and analysis techniques. Event-related potentials, termed ERPs, are a stimulus- or action-locked waveform indicating a characteristic neural response. ERPs derived from electroencephalography have been extensively studied in basic research, and have been applied especially in the field of brain-computer interfaces. For ecologically-valid settings there are considerable challenges to application, however recent work shows some promise for ERPs outside the lab. Here we present a short review on the application of ERPs in human-computer interaction. This paper aims to serve as a primer for the novice, enabling rapid familiarisation with the latest core concepts. We put special emphasis on everyday human-computer interface applications to distinguish from the more common clinical or sports uses of psychophysiology. This paper is an extract from a comprehensive review of the entire field of ambulatory psychophysiology, including 12 similar chapters, plus application guidelines and systematic review. Thus any citation should be made using the following reference: B. Cowley, M. Filetti, K. Lukander, J. Torniainen, A. Henelius, L. Ahonen, O. Barral, I. Kosunen, T. Valtonen, M. Huotilainen, N. Ravaja, G. Jacucci. The Psychophysiology Primer: a guide to methods and a broad review with a focus on human-computer interaction. Foundations and Trends in Human-Computer Interaction, vol. 9, no. 3-4, pp. 150--307, 2016.
Time scale modeling for consensus in sparse directed networks with time-varying topologies
Venue: arXiv cs.SY 2016
Year: 2016

The paper considers the consensus problem in large networks represented by time-varying directed graphs. A practical way of dealing with large-scale networks is to reduce their dimension by collapsing the states of nodes belonging to densely and intensively connected clusters into aggregate variables. It will be shown that under suitable conditions, the states of the agents in each cluster converge fast toward a local agreement. Local agreements correspond to aggregate variables which slowly converge to consensus. Existing results concerning the time-scale separation in large networks focus on fixed and undirected graphs. The aim of this work is to extend these results to the more general case of time-varying directed topologies. It is noteworthy that in the fixed and undirected graph case the average of the states in each cluster is time-invariant when neglecting the interactions between clusters. Therefore, they are good candidates for the aggregate variables. This is no longer possible here. Instead, we find suitable time-varying weights to compute the aggregate variables as time-invariant weighted averages of the states in each cluster. This allows to deal with the more challenging time-varying directed graph case. We end up with a singularly perturbed system which is analyzed by using the tools of two time-scales averaging which seem appropriate to this system.
Offline Drawing of Dynamic Trees: Algorithmics and Document Integration
Venue: arXiv cs.CG 2016
Year: 2016

While the algorithmic drawing of static trees is well-understood and well-supported by software tools, creating animations depicting how a tree changes over time is currently difficult: software support, if available at all, is not integrated into a document production workflow and algorithmic approaches only rarely take temporal information into consideration. During the production of a presentation or a paper, most users will visualize how, say, a search tree evolves over time by manually drawing a sequence of trees. We present an extension of the popular $\TeX$ typesetting system that allows users to specify dynamic trees inside their documents, together with a new algorithm for drawing them. Running $\TeX$ on the documents then results in documents in the SVG format with visually pleasing embedded animations. Our algorithm produces animations that satisfy a set of natural aesthetic criteria when possible. On the negative side, we show that one cannot always satisfy all criteria simultaneously and that minimizing their violations is NP-complete.
A note on how the problem of Partion of Integers show in Caching
Venue: arXiv cs.NI 2016
Year: 2016

In this article, we show how the finding the number of partitions of same size of a positive integer show up in caching networks. We present a stochastic model for caching where user requests (represented with positive integers) are a random process with uniform distribution and the sum of user requests plays an important role to tell us about the nature of the caching process. We discuss Euler's generating function to compute the number of partitions of a positive integer of same size. Also, we derive a simple approximation for guessing the guessing the number of partitions of same size and discuss some special sequences. Lastly, we present a simple algorithm to enumerate all the partitions of a positive integer of same size.
1-Bend RAC Drawings of 1-Planar Graphs
Venue: arXiv cs.CG 2016
Year: 2016

A graph is 1-planar if it has a drawing where each edge is crossed at most once. A drawing is RAC (Right Angle Crossing) if the edges cross only at right angles. The relationships between 1-planar graphs and RAC drawings have been partially studied in the literature. It is known that there are both 1-planar graphs that are not straight-line RAC drawable and graphs that have a straight-line RAC drawing but that are not 1-planar. Also, straight-line RAC drawings always exist for IC-planar graphs, a subclass of 1-planar graphs. One of the main questions still open is whether every 1-planar graph has a RAC drawing with at most one bend per edge. We positively answer this question.
Construction of Zero Cross Correlation Code using a type of Pascal's Triangle Matrix for Spectral Amplitude Coding Optical Code Division Multiple Access networks
Venue: arXiv cs.IT 2016
Year: 2016

In this paper a new method to construct zero cross correlation code with the help of Pascal's triangle pattern called Pascal's Triangle Matrix Code (PTMC) for Spectral Amplitude Coding Optical Code Division Multiple Access (SAC-OCDMA) system is successfully developed. The advantages of this code are simplicity of code construction, flexibility of choosing code weight and number of users. The numerical comparison shows that the newly constructed code is better in code length than the existing codes such as Optical Orthogonal Code (OOC), Hadamard, Modified Frequency Hopping (MFH) and Modified Double Weight (MDW) codes and it supports more users than other Optical Spectrum Code Division Multiple Access (OSCDMA) codes.
WNetKAT: A Weighted SDN Programming and Verification Language
Venue: arXiv cs.NI 2016
Year: 2016

Programmability and verifiability lie at the heart of the software-defined networking paradigm. While OpenFlow and its match-action concept provide primitive operations to manipulate hardware configurations, over the last years, several more expressive network programming languages have been developed. This paper presents WNetKAT, the first network programming language accounting for the fact that networks are inherently weighted, and communications subject to capacity constraints (e.g., in terms of bandwidth) and costs (e.g., latency or monetary costs). WNetKAT is based on a syntactic and semantic extension of the NetKAT algebra. We demonstrate several relevant applications for WNetKAT, including cost- and capacity-aware reachability, as well as quality-of-service and fairness aspects. These applications do not only apply to classic, splittable and unsplittable (s; t)-flows, but also generalize to more complex network functions and service chains. For example, WNetKAT allows to model flows which need to traverse certain waypoint functions, which may change the traffic rate. This paper also shows the relation between the equivalence problem of WNetKAT and the equivalence problem of the weighted finite automata, which implies undecidability of the former. However, this paper also succeeds to prove the decidability of another useful problem, which is sufficient in many practical scnearios: whether an expression equals to 0. Moreover, we initiate the discussion of decidable subsets of the whole language.
A Distributed Multilevel Force-directed Algorithm
Venue: arXiv cs.DC 2016
Year: 2016

The wide availability of powerful and inexpensive cloud computing services naturally motivates the study of distributed graph layout algorithms, able to scale to very large graphs. Nowadays, to process Big Data, companies are increasingly relying on PaaS infrastructures rather than buying and maintaining complex and expensive hardware. So far, only a few examples of basic force-directed algorithms that work in a distributed environment have been described. Instead, the design of a distributed multilevel force-directed algorithm is a much more challenging task, not yet addressed. We present the first multilevel force-directed algorithm based on a distributed vertex-centric paradigm, and its implementation on Giraph, a popular platform for distributed graph algorithms. Experiments show the effectiveness and the scalability of the approach. Using an inexpensive cloud computing service of Amazon, we draw graphs with ten million edges in about 60 minutes.
Interpolations of Smoke and Liquid Simulations
Venue: arXiv cs.GR 2016
Year: 2016

We present a novel method to interpolate smoke and liquid simulations in order to perform data-driven fluid simulations. Our approach calculates a dense space-time deformation using grid-based signed-distance functions of the inputs. A key advantage of this implicit Eulerian representation is that it allows us to use powerful techniques from the optical flow area. We employ a five-dimensional optical flow solve. In combination with a projection algorithm, and residual iterations, we achieve a robust matching of the inputs. Once the match is computed, arbitrary in between variants can be created very efficiently. To concatenate multiple long-range deformations, we propose a novel alignment technique. Our approach has numerous advantages, including automatic matches without user input, volumetric deformations that can be applied to details around the surface, and the inherent handling of topology changes. As a result, we can interpolate swirling smoke clouds, and splashing liquid simulations. We can even match and interpolate phenomena with fundamentally different physics: a drop of liquid, and a blob of heavy smoke.
Spatial Multiplexing of QPSK Signals with a Single Radio: Antenna Design and Over-the-Air Experiments
Venue: arXiv cs.IT 2016
Year: 2016

The paper describes the implementation and performance analysis of the first fully-operational beam-space MIMO antenna for the spatial multiplexing of two QPSK streams. The antenna is composed of a planar three-port radiator with two varactor diodes terminating the passive ports. Pattern reconfiguration is used to encode the MIMO information onto orthogonal virtual basis patterns in the far-field. A measurement campaign was conducted to compare the performance of the beam-space MIMO system with a conventional 2-by-?2 MIMO system under realistic propagation conditions. Propagation measurements were conducted for both systems and the mutual information and symbol error rates were estimated from Monte-Carlo simulations over the measured channel matrices. The results show the beam-space MIMO system and the conventional MIMO system exhibit similar finite-constellation capacity and error performance in NLOS scenarios when there is sufficient scattering in the channel. In comparison, in LOS channels, the capacity performance is observed to depend on the relative polarization of the receiving antennas.
Devito: automated fast finite difference computation
Venue: arXiv cs.MS 2016
Year: 2016

Domain specific languages have successfully been used in a variety of fields to cleanly express scientific problems as well as to simplify implementation and performance opti- mization on different computer architectures. Although a large number of stencil languages are available, finite differ- ence domain specific languages have proved challenging to design because most practical use cases require additional features that fall outside the finite difference abstraction. Inspired by the complexity of real-world seismic imaging problems, we introduce Devito, a domain specific language in which high level equations are expressed using symbolic expressions from the SymPy package. Complex equations are automatically manipulated, optimized, and translated into highly optimized C code that aims to perform compa- rably or better than hand-tuned code. All this is transpar- ent to users, who only see concise symbolic mathematical expressions.
One-Minute Derivation of The Conjugate Gradient Algorithm
Venue: arXiv cs.DS 2016
Year: 2016

One of the great triumphs in the history of numerical methods was the discovery of the Conjugate Gradient (CG) algorithm. It could solve a symmetric positive-definite system of linear equations of dimension N in exactly N steps. As many practical problems at that time belonged to this category, CG algorithm became rapidly popular. It remains popular even today due to its immense computational power. But despite its amazing computational ability, mathematics of this algorithm is not easy to learn. Lengthy derivations, redundant notations, and over-emphasis on formal presentation make it much difficult for a beginner to master this algorithm. This paper aims to serve as a starting point for such readers. It provides a curt, easy-to-follow but minimalist derivation of the algorithm by keeping the sufficient steps only, maintaining a uniform notation, and focusing entirely on the ease of reader.
1700 Forests
Venue: arXiv cs.DM 2016
Year: 2016

Since ordered trees and Dyck paths are equinumerous, so are ordered forests and grand-Dyck paths that start with an upwards step.
Look, no Beacons! Optimal All-in-One EchoSLAM
Venue: arXiv cs.RO 2016
Year: 2016

We study the problem of simultaneously reconstructing a polygonal room and a trajectory of a device equipped with a (nearly) collocated omnidirectional source and receiver. The device measures arrival times of echoes of pulses emitted by the source and picked up by the receiver. No prior knowledge about the device's trajectory is required. Most existing approaches addressing this problem assume multiple sources or receivers, or they assume that some of these are static, serving as beacons. Unlike earlier approaches, we take into account the measurement noise and various constraints on the geometry by formulating the solution as a minimizer of a cost function similar to \emph{stress} in multidimensional scaling. We study uniqueness of the reconstruction from first-order echoes, and we show that in addition to the usual invariance to rigid motions, new ambiguities arise for important classes of rooms and trajectories. We support our theoretical developments with a number of numerical experiments.
Visibility Representations of Boxes in 2.5 Dimensions
Venue: arXiv cs.CG 2016
Year: 2016

We initiate the study of 2.5D box visibility representations (2.5D-BR) where vertices are mapped to 3D boxes having the bottom face in the plane $z=0$ and edges are unobstructed lines of sight parallel to the $x$- or $y$-axis. We prove that: $(i)$ Every complete bipartite graph admits a 2.5D-BR; $(ii)$ The complete graph $K_n$ admits a 2.5D-BR if and only if $n \leq 19$; $(iii)$ Every graph with pathwidth at most $7$ admits a 2.5D-BR, which can be computed in linear time. We then turn our attention to 2.5D grid box representations (2.5D-GBR) which are 2.5D-BRs such that the bottom face of every box is a unit square at integer coordinates. We show that an $n$-vertex graph that admits a 2.5D-GBR has at most $4n - 6 \sqrt{n}$ edges and this bound is tight. Finally, we prove that deciding whether a given graph $G$ admits a 2.5D-GBR with a given footprint is NP-complete. The footprint of a 2.5D-BR $Γ$ is the set of bottom faces of the boxes in $Γ$.