Accurate target tracking via Gaussian sparsity and locality-constrained coding in heavy occlusion

This paper presents a Gaussian sparse representation cooperative model for tracking a target in heavy occlusion video sequences by combining sparse coding and locality-constrained linear coding algorithms. Different from the usual method of using ?₁-norm regularization term in the framework of particle filters to form the sparse collaborative appearance model (SCM), we employed the ?₁-norm and ?₂-norm to calculate feature selection, and then encoded the candidate samples to generate the sparse coefficients. Consequently, our method not only easily obtained sparse solutions but also reduced reconstruction error. Compared to state-of-the-art algorithms, our scheme achieved better performance in heavy occlusion video sequences for tracking a target. Extensive experiments on target tracking were carried out to show the results of our proposed algorithm compared with various other target tracking methods.     

Tackling heterogeneous concept drift with the Self-Adjusting Memory (SAM)

Instance matching is the problem of determining whether two instances describe the same real-world entity or not. Instance matching plays a key role in data integration and data cleansing, especially for building a knowledge base. For example, we can regard each article in encyclopedias as an instance, and a group of articles which refers to the same real-world object as an entity. Therefore, articles about Washington should be distinguished and grouped into different entities such as Washington, D.C (the capital of the USA), George Washington (first president of the USA), Washington (a state of the USA), Washington (a village in West Sussex, England), Washington F.C. (a football club based in Washington, Tyne and Wear, England), Washington, D.C. (a novel). In this paper, we proposed a novel instance matching approach Active Instance Matching with Pairwise Constraints, which can bring the human into the loop of instance matching. The proposed approach can generate candidate pairs in advance to reduce the computational complexity, and then iteratively select the most informative pairs according to the uncertainty, influence, connectivity and diversity of pairs. We evaluated our approach one two publicly available datasets AMINER and WIDE-NUS and then applied our approach to the two large-scale real-world datasets, Baidu Baike and Hudong Baike, to build a Chinese knowledge base. The experiments and practice illustrate the effectiveness of our approach.     

Shadow Prices in Territory Division

We consider a geographic optimization problem in which we are given a region R, a probability density function f(?) defined on R, and a collection of n utility density functions u _i (?) defined on R. Our objective is to divide R into n sub-regions R _i so as to “balance” the overall utilities on the regions, which are given by the integrals \(\iint _{R_{i}}f(x)u_{i}(x)\, dA\). Using a simple complementary slackness argument, we show that (depending on what we mean precisely by “balancing” the utility functions) the boundary curves between optimal sub-regions are level curves of either the difference function u _i (x) ? u _j (x) or the ratio u _i (x)/u _j (x). This allows us to solve the problem of optimally partitioning the region efficiently by reducing it to a low-dimensional convex optimization problem. This result generalizes, and gives very short and constructive proofs of, several existing results in the literature on equitable partitioning for particular forms of f(?) and u _i (?). We next give two economic applications of our results in which we show how to compute a market-clearing price vector in an aggregate demand system or a variation of the classical Fisher exchange market. Finally, we consider a dynamic problem in which the density function f(?) varies over time (simulating population migration or transport of a resource, for example) and derive a set of partial differential equations that describe the evolution of the optimal sub-regions over time. Numerical simulations for both static and dynamic problems confirm that such partitioning problems become tractable when using our methods.     

Ranking policies in discrete Markov decision processes

An optimal probabilistic-planning algorithm solves a problem, usually modeled by a Markov decision process, by finding an optimal policy. In this paper, we study the k best policies problem. The problem is to find the k best policies of a discrete Markov decision process. The k best policies, k?>?1, cannot be found directly using dynamic programming. Naïvely, finding the k-th best policy can be Turing reduced to the optimal planning problem, but the number of problems queried in the naïve algorithm is exponential in k. We show empirically that solving k best policies problem by using this reduction requires unreasonable amounts of time even when k?=?3. We then provide two new algorithms. The first is a complete algorithm, based on our theoretical contribution that the k-th best policy differs from the i-th policy, for some i?k, on exactly one state. The second is an approximate algorithm that skips many less useful policies. We show that both algorithms have good scalability. We also show that the approximate algorithms runs much faster and finds interesting, high-quality policies.     

<Emphasis Type="Italic">k</Emphasis>-Nearest neighbors tracking in wireless sensor networks with coverage holes

Target tracking is one of the important applications of wireless sensor networks (WSNs). Most of the existing approaches assume that the nodes are dense enough and ignore the coverage holes which are very common in WSNs because of random deployment of the sensor nodes, block of obstacles, etc. Besides, predicting the target’s location of the next time instance is unwise because of the quite a lot random factors. In this paper, we propose a novel target tracking approach without any predicting, called k-nearest neighbors tracking (k-NNT), to tackle the problems of energy efficiency, continuity and coverage holes. In k-NNT, only the k-nearest neighbors keep active and track the target when more than k nodes can sense the target; the k′-nearest neighbors work when there are only k′ nodes (k′ < k) can sense the target. A sophisticated rotation mechanism is designed to improve the continuity of the tracking process. In the worst case, none of the nodes can sense the target, i.e., the target enters into the coverage holes, and then k-NNT recovers by the Round Up mode (RU mode). The nodes on the perimeter of the coverage hole always keep active for a time threshold t and sense the around environment to find the target in time. Once a node finds the target, the RU mode is over and the irrelevant nodes turn into inactive mode. A series of simulation show that k-NNT performs superiorly compared with several existing approaches in terms of tracking accuracy, continuity and energy efficiency.     

Uncertain top-<Emphasis Type="Italic">k</Emphasis> query processing in distributed environments

The top-k query on uncertain data set has been a very hot topic these years, and there have been many studies on uncertain top-k queries. Unfortunately, most of the existing algorithms only consider centralized processing environments, and they are not suitable for the large-scale data. In this paper, it is the first attempt to process probabilistic threshold top-k queries (an important uncertain top-k query, PT-k for short) in a distributed environment. We propose 3 efficient algorithms. The serial distributed approach adopts a new method, which only requires a few amount of calculations, to serially process PT-k queries in distributed environments. The global sorting first algorithm for PT-k query processing (GSP) is designed for improving the computation speed. In GSP, a distributed sorting operation is performed, and then we compute the candidates for PT-k queries in parallel. The query results can be computed by using a novel incremental method which can reduce the number of calculations. The local filtering first algorithm for PT-k query processing is designed for reducing the network overhead. Specifically, several filtering strategies are proposed to filter out redundant data locally, and then the incremental method in GSP is used to process the PT-k queries. Finally, the effectiveness of our proposed algorithms is verified through a series of experiments.     

An Efficient Lagrangian Interpolation Scheme for Computing Flow Maps and Line Integrals using Discrete Velocity Data

We propose a new class of Lagrangian approaches for constructing the flow maps of given dynamical systems. In the case when only discrete velocity data at mesh points is available, an interpolation step will be required. However, in our proposed approaches all particle trajectories share a common global interpolation at each time step and therefore interpolation operations will not increase the overall computational complexity. The old Lagrangian approaches propose to solve the corresponding ordinary differential equations (ODEs) backward in time to obtain the backward flow map. It is inconvenient and not natural, especially when incorporated with certain computational fluid dynamic solvers, because the velocity field needs to be loaded from the terminal time backward to the initial time. In contrast, our proposed approaches for computing the backward flow map propose to solve the corresponding ODEs forward in time which is more practical. We will also extend the proposed approaches to compute line integrals along any particle trajectory. This paper gives a detailed analysis on the computational complexity and error estimate of the proposed Lagrangian approach. Finally, a wide range of applications of our approaches will be given, including the so-called coherent ergodic partition and the high frequency wave propagations based on geometric optic.     

Separation and concentration of <Emphasis Type="Italic">Phytophthora ramorum</Emphasis> sporangia by inertial focusing in curving microfluidic flows

We present an integrated microfluidic system for performing isolation and concentration of Phytophthora ramorum pathogens using a chip whose working principle is based on inertial lateral migration in curving flows. The chip was fabricated from multiple layers of thermoplastic polymers and features an embedded spiral separation channel along with peristaltic microvalves for fluidic operation and process control. A pumping system paired with a fully programmable pressure manifold is used to boost concentration levels by recirculating the sample liquid multiple times through the separation chip, making it possible to reduce sample volumes from 10 to 1 mL or less. The system was calibrated using fluorescent polymer particles with a nominal diameter of 30 µm which is comparable to that of P. ramorum sporangia. The separation process has been shown to be highly effective and more than 99% of the beads can be recovered in the concentrated batch. Experiments conducted with P. ramorum sporangia have shown that a 5.3-fold increase in pathogen content with 95% recovery can be achieved using three subsequent concentration cycles. The utility of the method has been validated by processing a sample derived from infested Rhododendron leaves where a 6.1-fold increase in the concentration of P. ramorum has been obtained after four concentration cycles. Although specifically designed and demonstrated for sporangia of P. ramorum, the method and related design rules can easily be extended to other microbial organisms, effectively supporting bioanalytical applications where efficient, high-throughput separation of target species is of primary concern.     

Eulerian Based Interpolation Schemes for Flow Map Construction and Line Integral Computation with Applications to Lagrangian Coherent Structures Extraction

We propose and analyze a new class of Eulerian methods for constructing both the forward and the backward flow maps of sufficiently smooth dynamical systems. These methods improve previous Eulerian approaches so that the computations of the forward flow map can be done on the fly as one imports or measures the velocity field forward in time. Similar to typical Lagrangian or semi-Lagrangian methods, the proposed methods require an interpolation at each step. Having said that, the Eulerian method interpolates d components of the flow maps in the d dimensional space but does not require any \((d+1)\)-dimensional spatial-temporal interpolation as in the Lagrangian approaches. We will also extend these Eulerian methods to compute line integrals along any Lagrangian particle. The paper gives a computational complexity analysis and an error estimate of these Eulerian methods. The method can be applied to a wide range of applications for flow map constructions including the finite time Lyapunov exponent computations, the coherent ergodic partition, and high frequency wave propagations using geometric optic.     

A unified integration and component testing approach from deterministic stream X-machine specifications

One of the great benefits of using a stream X-machine to specify a system is its associated testing method. Under certain design for test conditions, this method produces a test suite that can determine the correctness of the implementation under test (IUT), provided that the basic components of the stream X-machine model have been correctly implemented. However, such an approach implies that each component can be tested in isolation from the rest of the system. This is a limitation that, in practice, can be resolved by developing stubs and drivers. However, this adds complexity to the testing process and, furthermore, these new pieces of software can introduce faults that can invalidate the theoretical results of the aforementioned testing method. This paper extends the approach by allowing component testing to be performed in parallel with integration testing, while still guaranteeing the IUT correctness under the given design for test conditions. It also shows how the integration test suite, produced in previous publications, can be reduced.     

Mossar: motion segmentation by using splitting and remerging strategies

This paper presents a novel approach for motion segmentation by using strategies of splitting and remerging. The presented approach, Mossar, hybridizes two existing ones to obtain their potential advantages while covering weaknesses: (1) velocity-based, one of the most widely used approaches that has fairly low accuracy but provides computational simplicity and (2) graph-based, a state-of-the-art approach that provides outstanding accuracy, yet bears high computational complexity and a burden in setting of thresholds. An initial set of key frames is generated by a velocity-based splitting process and then fed into a graph-based remerging process for refinement. We present mechanisms that improve key-frames capturing in the velocity-based approach as well as details on how the graph-based approach is modified and later applied to remerging. The proposed approach also allows users to interactively add or reduce the number of key frames to control segmentation hierarchy without the need to change threshold values and re-run segmentation, as usually done in existing approaches. Our experimental results show that the presented hybrid approach, compared to both velocity-based and graph-based, demonstrates superior performance in terms of accuracy and in comparison to graph-based, our approach has not only less complexity but also a lesser number of thresholds, the values of which can be much more simply determined.     

Encoding process discovery problems in SMT

Information systems, which are responsible for driving many processes in our lives (health care, the web, municipalities, commerce and business, among others), store information in the form of logs which is often left unused. Process mining, a discipline in between data mining and software engineering, proposes tailored algorithms to exploit the information stored in a log, in order to reason about the processes underlying an information system. A key challenge in process mining is discovery: Given a log, derive a formal process model that can be used afterward for a formal analysis. In this paper, we provide a general approach based on satisfiability modulo theories (SMT) as a solution for this challenging problem. By encoding the problem into the logical/arithmetic domains and using modern SMT engines, it is shown how two separate families of process models can be discovered. The theory of this paper is accompanied with a tool, and experimental results witness the significance of this novel view of the process discovery problem.     

HSR: <Emphasis Type="Italic">L</Emphasis><Subscript>1/2</Subscript>-regularized sparse representation for fast face recognition using hierarchical feature selection

In this paper, we propose a novel method for fast face recognition called L _1/2-regularized sparse representation using hierarchical feature selection. By employing hierarchical feature selection, we can compress the scale and dimension of global dictionary, which directly contributes to the decrease of computational cost in sparse representation that our approach is strongly rooted in. It consists of Gabor wavelets and extreme learning machine auto-encoder (ELM-AE) hierarchically. For Gabor wavelets’ part, local features can be extracted at multiple scales and orientations to form Gabor-feature-based image, which in turn improves the recognition rate. Besides, in the presence of occluded face image, the scale of Gabor-feature-based global dictionary can be compressed accordingly because redundancies exist in Gabor-feature-based occlusion dictionary. For ELM-AE part, the dimension of Gabor-feature-based global dictionary can be compressed because high-dimensional face images can be rapidly represented by low-dimensional feature. By introducing L _1/2 regularization, our approach can produce sparser and more robust representation compared to L ₁-regularized sparse representation-based classification (SRC), which also contributes to the decrease of the computational cost in sparse representation. In comparison with related work such as SRC and Gabor-feature-based SRC, experimental results on a variety of face databases demonstrate the great advantage of our method for computational cost. Moreover, we also achieve approximate or even better recognition rate.     

Event-based run-time adaptation in communication-centric systems

Communication-centric systems are software systems built as assemblies of distributed artifacts that interact following predefined communication protocols. Session-based concurrency is a type-based approach to ensure the conformance of communication-centric systems to such protocols. This paper presents a model of session-based concurrency with mechanisms for run-time adaptation. Our model allows us to specify communication-centric systems whose session behavior can be dynamically updated at run-time. We improve on previous work by proposing an event-based approach: adaptation requests, issued by the system itself or by its context, are assimilated to events which may trigger adaptation routines. These routines exploit type-directed checks to enable the reconfiguration of processes with active protocols. We equip our model with a type system that ensures communication safety and consistency properties: while safety guarantees absence of run-time communication errors, consistency ensures that update actions do not disrupt already established session protocols. We provide soundness results for binary and multiparty protocols.     

Answering subgraph queries over massive disk resident graphs

Due to its wide applications, subgraph query has attracted lots of attentions in database community. In this paper, we focus on subgraph query over a single large graph G, i.e., finding all embeddings of query Q in G. Different from existing feature-based approaches, we map all edges into a two-dimensional space R ² and propose a bitmap structure to index R ². At run time, we find a set of adjacent edge pairs (AEP) or star-style patterns (SSP) to cover Q. We develop edge join (EJ) algorithms to address both AEP and SSP subqueries. Based on the bitmap index, our method can optimize I/O and CPU cost. More importantly, our index has the linear space complexity instead of exponential complexity in feature-based approaches, which indicates that our index can scale well with respect to large data size. Furthermore, our index has light maintenance overhead, which has not been considered in most of existing work. Extensive experiments show that our method significantly outperforms existing ones in both online and offline processing with respect to query response time, index building time, index size and index maintenance overhead.     

Motion of spin-half particles in the axially symmetric field of naked singularities of the static <Emphasis Type="Italic">q</Emphasis>-metric

Quantum-mechanical motion of a spin-half particle is examined in the axially symmetric fields of static naked singularities formed by a mass distribution with a quadrupole moment (q-metric). The analysis is performed by means of the method of effective potentials of the Dirac equation generalized to the case where radial and angular variables are not separated. If ?1 < q < qlim, |qlim| ? 1, where q is the quadrupolemoment in proper units, the naked singularities do not exclude the existence of stationary bound states of Dirac particles for a prolate mass distribution in the q-metric along the axial axis. For an oblate mass distribution, the naked singularities of the q-metric are separated from a Dirac particle by infinitely large repulsive barriers followed by a potential well which deepens while moving apart from the equator (from θ = θ _min or θ = π ? θ _min) toward the poles. The poles make an exception, and at 0 < q < q*, there are some points θ _i for particle states with j ≥ 3/2.     

Cache-Oblivious R-Trees

We develop a cache-oblivious data structure for storing a set S of N axis-aligned rectangles in the plane, such that all rectangles in S intersecting a query rectangle or point can be found efficiently. Our structure is an axis-aligned bounding-box hierarchy and as such it is the first cache-oblivious R-tree with provable performance guarantees. If no point in the plane is contained in more than a constant number of rectangles in S, we can construct, for any constant ε, a structure that answers a rectangle query using \(O(\sqrt{N/B}+T/B)\) memory transfers and a point query using O((N/B) ^ε ) memory transfers, where T is the number of reported rectangles and B is the block size of memory transfers between any two levels of a multilevel memory hierarchy. We also develop a variant of our structure that achieves the same performance on input sets with arbitrary overlap among the rectangles. The rectangle query bound matches the bound of the best known linear-space cache-aware structure.     

Property-Preserving Data Reconstruction

We initiate a new line of investigation into online property-preserving data reconstruction. Consider a dataset which is assumed to satisfy various (known) structural properties; e.g., it may consist of sorted numbers, or points on a manifold, or vectors in a polyhedral cone, or codewords from an error-correcting code. Because of noise and errors, however, an (unknown) fraction of the data is deemed unsound, i.e., in violation with the expected structural properties. Can one still query into the dataset in an online fashion and be provided data that is always sound? In other words, can one design a filter which, when given a query to any item I in the dataset, returns a sound item J that, although not necessarily in the dataset, differs from I as infrequently as possible. No preprocessing should be allowed and queries should be answered online.We consider the case of a monotone function. Specifically, the dataset encodes a function f:{1,…,n}?? R that is at (unknown) distance ε from monotone, meaning that f can—and must—be modified at ε n places to become monotone.Our main result is a randomized filter that can answer any query in O(log?² nlog? log?n) time while modifying the function f at only O(ε n) places. The amortized time over n function evaluations is O(log?n). The filter works as stated with probability arbitrarily close to 1. We provide an alternative filter with O(log?n) worst case query time and O(ε nlog?n) function modifications. For reconstructing d-dimensional monotone functions of the form f:{1,…,n} ^d ? ? R, we present a filter that takes (2 ^O(d)(log?n)^4d?2log?log?n) time per query and modifies at most O(ε n ^d ) function values (for constant d).     

Inertial migration of single particle in a square microchannel over wide ranges of <Emphasis Type="Italic">Re</Emphasis> and particle sizes

Inertial migration of particles has been widely used in inertial microfluidic systems to passively manipulate cells/particles. However, the migration behaviors and the underlying mechanisms, especially in a square microchannel, are still not very clear. In this paper, the immersed boundary-lattice Boltzmann method (IB-LBM) was introduced and validated to explore the migration characteristics and the underlying mechanisms of an inertial focusing single particle in a square microchannel. The grid-independence analysis was made first to highlight that the grid number across the thin liquid film (between a particle and its neighboring channel wall) was of significant importance in accurately capturing the migrating particle’s dynamics. Then, the inertial migration of a single particle was numerically investigated over wide ranges of Reynolds number (Re, from 10 to 500) and particle sizes (diameter-to-height ratio a/H, from 0.16 to 0.5). It was interesting to find that as Re increased, the channel face equilibrium (CFE) position moved outward to channel walls at first, and then inflected inwards to the channel center at high Re (Re?>?200). To account for the physical mechanisms behind this behavior, the secondary flow induced by the inertial focusing single particle was further investigated. It was found that as Re increased, two vortices appeared around the particle and grew gradually, which pushed the particle away from the channel wall at high Re. Finally, a correlation was proposed based on the numerical data to predict the critical length L_c (defined to describe the size of fluid domain that was strongly influenced by the particle) according to the particle size a/H and Re.     

Efficiently Storing Well-Composed Polyhedral Complexes Computed Over 3D Binary Images

A 3D binary image I can be naturally represented by a combinatorial-algebraic structure called cubical complex and denoted by Q(I), whose basic building blocks are vertices, edges, square faces and cubes. In Gonzalez-Diaz et al. (Discret Appl Math 183:59–77, 2015), we presented a method to “locally repair” Q(I) to obtain a polyhedral complex P(I) (whose basic building blocks are vertices, edges, specific polygons and polyhedra), homotopy equivalent to Q(I), satisfying that its boundary surface is a 2D manifold. P(I) is called a well-composed polyhedral complex over the picture I. Besides, we developed a new codification system for P(I), encoding geometric information of the cells of P(I) under the form of a 3D grayscale image, and the boundary face relations of the cells of P(I) under the form of a set of structuring elements. In this paper, we build upon (Gonzalez-Diaz et al. 2015) and prove that, to retrieve topological and geometric information of P(I), it is enough to store just one 3D point per polyhedron and hence neither grayscale image nor set of structuring elements are needed. From this “minimal” codification of P(I), we finally present a method to compute the 2-cells in the boundary surface of P(I).