An Approximation Algorithm for Binary Searching in Trees

We consider the problem of computing efficient strategies for searching in trees. As a generalization of the classical binary search for ordered lists, suppose one wishes to find a (unknown) specific node of a tree by asking queries to its arcs, where each query indicates the endpoint closer to the desired node. Given the likelihood of each node being the one searched, the objective is to compute a search strategy that minimizes the expected number of queries. Practical applications of this problem include file system synchronization and software testing. Here we present a linear time algorithm which is the first constant factor approximation for this problem. This represents a significant improvement over previous O(log n)-approximation.     

Spherical Correlation of Visual Representations for 3D Model Retrieval

In recent years we have seen a tremendous growth in the amount of freely available 3D content, in part due to breakthroughs for 3D model design and acquisition. For example, advances in range sensor technology and design software have dramatically reduced the manual labor required to construct 3D models. As collections of 3D content continue to grow rapidly, the ability to perform fast and accurate retrieval from a database of models has become a necessity. At the core of this retrieval task is the fundamental challenge of defining and evaluating similarity between 3D shapes. Some effective methods dealing with this challenge consider similarity measures based on the visual appearance of models. While collections of rendered images are discriminative for retrieval tasks, such representations come with a few inherent limitations such as restrictions in the image viewpoint sampling and high computational costs. In this paper we present a novel algorithm for model similarity that addresses these issues. Our proposed method exploits techniques from spherical signal processing to efficiently evaluate a visual similarity measure between models. Extensive evaluations on multiple datasets are provided.     

Predicate Logic Based Image Grammars for Complex Pattern Recognition

Predicate logic based reasoning approaches provide a means of formally specifying domain knowledge and manipulating symbolic information to explicitly reason about different concepts of interest. Extension of traditional binary predicate logics with the bilattice formalism permits the handling of uncertainty in reasoning, thereby facilitating their application to computer vision problems. In this paper, we propose using first order predicate logics, extended with a bilattice based uncertainty handling formalism, as a means of formally encoding pattern grammars, to parse a set of image features, and detect the presence of different patterns of interest. Detections from low level feature detectors are treated as logical facts and, in conjunction with logical rules, used to drive the reasoning. Positive and negative information from different sources, as well as uncertainties from detections, are integrated within the bilattice framework. We show that this approach can also generate proofs or justifications (in the form of parse trees) for each hypothesis it proposes thus permitting direct analysis of the final solution in linguistic form. Automated logical rule weight learning is an important aspect of the application of such systems in the computer vision domain. We propose a rule weight optimization method which casts the instantiated inference tree as a knowledge-based neural network, interprets rule uncertainties as link weights in the network, and applies a constrained, back-propagation algorithm to converge upon a set of rule weights that give optimal performance within the bilattice framework. Finally, we evaluate the proposed predicate logic based pattern grammar formulation via application to the problems of (a) detecting the presence of humans under partial occlusions and (b) detecting large complex man made structures as viewed in satellite imagery. We also evaluate the optimization approach on real as well as simulated data and show favorable results.     

Human–Computer Collaboration for Visual Analytics: an Agent-based Framework

The visual analytics community has long aimed to understand users better and assist them in their analytic endeavors. As a result, numerous conceptual models of visual analytics aim to formalize common workflows, techniques, and goals leveraged by analysts. While many of the existing approaches are rich in detail, they each are specific to a particular aspect of the visual analytic process. Furthermore, with an ever-expanding array of novel artificial intelligence techniques and advances in visual analytic settings, existing conceptual models may not provide enough expressivity to bridge the two fields. In this work, we propose an agent-based conceptual model for the visual analytic process by drawing parallels from the artificial intelligence literature. We present three examples from the visual analytics literature as case studies and examine them in detail using our framework. Our simple yet robust framework unifies the visual analytic pipeline to enable researchers and practitioners to reason about scenarios that are becoming increasingly prominent in the field, namely mixed-initiative, guided, and collaborative analysis. Furthermore, it will allow us to characterize analysts, visual analytic settings, and guidance from the lenses of human agents, environments, and artificial agents, respectively.     

Human–Machine Interaction in Intelligent Robotic Systems: A Unifying Consideration with Implementation Examples

In this paper, we propose a two-layer sensor fusion scheme for multiple hypotheses multisensor systems. To reflect reality in decision making, uncertain decision regions are introduced in the hypotheses testing process. The entire decision space is partitioned into distinct regions of correct, uncertain and incorrect regions. The first layer of decision is made by each sensor indepedently based on a set of optimal decision rules. The fusion process is performed by treating the fusion center as an additional virtual sensor to the system. This virtual sensor makes decision based on the decisions reached by the set of sensors in the system. The optimal decision rules are derived by minimizing the Bayes risk function. As a consequence, the performance of the system as well as individual sensors can be quantified by the probabilities of correct, incorrect and uncertain decisions. Numerical examples of three hypotheses, two and four sensor systems are presented to illustrate the proposed scheme.     

HMM machine learning and inference for Activities of Daily Living recognition

In a human-centric smart space, Activities of Daily Living (ADL) analysis can provide very useful information for elder care and long-term care services. ADL is defined as an assessment of a person’s functional status. Many recent researches concentrate on designing a good Context Aware Computing System to automate the actions necessarily triggered by ADL recognitions. Implementing a correct ADL recognition engine is a hard work, but will repay the system with lower inference errors and higher system dependability. A good ADL recognition engine is required to adjust its inference strategy based on the learning capability in order to avoid a high error rate, especially in real world inputs with a significant difference as compared to those in the training phase. In this paper, we proposed a powerful inference engine based on the Hidden Markov Model, called the Adaptive Learning Hidden Markov Model (ALHMM), which combines the Viterbi and Baum–Welch algorithms to enhance the accuracy and learning capability. The assessments of ALHMM are conducted on the Python platform and show the practical feasibility of Activity Recognition in residential homes. Such a technique can provide the key answer required for advancing the state-of-the-art in context-aware computing and applications in real life.     

Visual feedback with multiple cameras in a UAVs Human–Swarm Interface

In all situations in which a wide area has to be monitored, a practice emerging in recent years consists in using Unmanned Aerial Vehicles (UAVs), and in particular multirotors. Even if many steps forward have been taken toward the fully autonomous control of UAVs, a human pilot is usually in charge of controlling the robots. However, teleoperating UAVs can become a hard task whenever it is necessary to deploy a swarm of robots instead of a single unit, to the end of increasing the area under observation. In this case, the organization of robots in a structured formation may reduce the effort of the operator to control the swarm.When controlling a team of robots, the typology of visual feedback is crucial. It is known that, while overall awareness and pattern recognition are optimized by exocentric views, i.e., with cameras from above the swarm, the immediate environment is often better viewed egocentrically, i.e., with cameras on board the robots.In this article we present the implementation of a human–robot interface for the control of a swarm of UAVs, with a focus on the analysis of the effects of different visual feedbacks on the performance of human operators.     

Human Motion Tracking with a Kinematic Parameterization of Extremal Contours

This paper addresses the problem of human motion tracking from multiple image sequences. The human body is described by five articulated mechanical chains and human body-parts are described by volumetric primitives with curved surfaces. If such a surface is observed with a camera, an extremal contour appears in the image whenever the surface turns smoothly away from the viewer. We describe a method that recovers human motion through a kinematic parameterization of these extremal contours. The method exploits the fact that the observed image motion of these contours is a function of both the rigid displacement of the surface and of the relative position and orientation between the viewer and the curved surface. First, we describe a parameterization of an extremal-contour point velocity for the case of developable surfaces. Second, we use the zero-reference kinematic representation and we derive an explicit formula that links extremal contour velocities to the angular velocities associated with the kinematic model. Third, we show how the chamfer-distance may be used to measure the discrepancy between predicted extremal contours and observed image contours; moreover we show how the chamfer distance can be used as a differentiable multi-valued function and how the tracker based on this distance can be cast into a continuous non-linear optimization framework. Fourth, we describe implementation issues associated with a practical human-body tracker that may use an arbitrary number of cameras. One great methodological and practical advantage of our method is that it relies neither on model-to-image, nor on image-to-image point matches. In practice we model people with 5 kinematic chains, 19 volumetric primitives, and 54 degrees of freedom; We observe silhouettes in images gathered with several synchronized and calibrated cameras. The tracker has been successfully applied to several complex motions gathered at 30 frames/second.     

A recursive genetic framework for evolutionary decision-making in problems with high dynamism

Communication and coordination are the main cores for reaching a constructive agreement among multi-agent systems (MASs). Dividing the overall performance of MAS to individual agents may lead to group learning as opposed to individual learning, which is one of the weak points of MASs. This paper proposes a recursive genetic framework for solving problems with high dynamism. In this framework, a combination of genetic algorithm and multi-agent capabilities is utilised to accelerate team learning and accurate credit assignment. The argumentation feature is used to accomplish agent learning and the negotiation features of MASs are used to achieve a credit assignment. The proposed framework is quite general and its recursive hierarchical structure could be extended. We have dedicated one special controlling module for increasing convergence time. Due to the complexity of blackjack, we have applied it as a possible test bed to evaluate the system’s performance. The learning rate of agents is measured as well as their credit assignment. The analysis of the obtained results led us to believe that our robust framework with the proposed negotiation operator is a promising methodology to solve similar problems in other areas with high dynamism.     

Recursive formulations for multibody systems with frictional joints based on the interaction between bodies

In practice, the clearances of joints in a great number of mechanical systems are well under control. In these cases, some of the existing methods become unpractical because of the little differences in the order of magnitude between relative movements and computational errors. Assuming that the effects of impacts are negligible, we proved that both locations and forces of contacts in joints can be fully determined by parts of joint reaction forces. Based on this fact, a method particularly suited for multibody systems possessing frictional joints with tiny clearances is presented. In order to improve the efficiency of computation, recursive formulations are proposed based on the interactions between bodies. The proposed recursive formulations can improve the computation of joint reaction forces. With the methodology presented in this paper, not only the motion of bodies in a multibody system but also the details about the contacts in joints, such as forces of contacts and locations of contact points, can be obtained. Even with the assumption of impact free, the instants of possible impacts can be detected without relying upon any ambiguous parameters, as indicated by numerical examples in this paper.     

A Spectral Stochastic Semi-Lagrangian Method for Convection-Diffusion Equations with Uncertainty

Real life convection-diffusion problems are characterized by their inherent or externally induced uncertainties in the design parameters. This paper presents a spectral stochastic finite element semi-Lagrangian method for numerical solution of convection-diffusion equations with uncertainty. Using the spectral decomposition, the stochastic variational problem is reformulated to a set of deterministic variational problems to be solved for each Wiener polynomial chaos. To obtain the chaos coefficients in the corresponding deterministic convection-diffusion equations, we implement a semi-Lagrangian method in the finite element framework. Once this representation is computed, statistics of the numerical solution can be easily evaluated. These numerical techniques associate the geometrical flexibility of the finite element method with the ability offered by the semi-Lagrangian method to solve convection-dominated problems using time steps larger than its Eulerian counterpart. Numerical results are shown for a convection-diffusion problem driven with stochastic velocity and for an incompressible viscous flow problem with a random force. In both examples, the proposed method demonstrates its ability to better maintain the shape of the solution in the presence of uncertainties and steep gradients.     

An approximation-based load-balancing algorithm with admission control for cluster web servers with dynamic workloads

The growth of web-based applications in business and e-commerce is building up demands for high performance web servers for better throughputs and lower user-perceived latency. These demands are leading to a widespread substitution of powerful single servers by robust newcomers, cluster web servers, in many enterprise companies. In this respect the load-balancing algorithms play an important role in boosting the performance of cluster servers. The previous load-balancing algorithms which were designed for the handling of static contents in web services suffer from significant performance degradation under dynamic and database-driven workloads. Regarding this, we propose an approximation-based load-balancing algorithm with admission control for cluster-based web servers in this study. Since it is difficult to accurately determine the loads of web servers through feedbacks from distributed agents in web servers, we propose an analytical model of a web server to estimate the web servers’ loads. To achieve this, the algorithm classifies requests based on their service times and track numbers of outstanding requests for each class of each web server node and also based on their resource demands to dynamically estimate the loads of each node. For the error handling of the model a proportional integral (PI) controller from control theory is used. Then the estimated available capacity of each web server is used for load balancing and admission control decisions. The implementation results with a standard benchmark confirm the effectiveness of the proposed scheme, which improves both the mean response time and the throughput of the cluster compared to rival load-balancing algorithms, and also avoids situations in which the cluster is overloaded, even when the request rates are beyond the cluster capacity.     

Network Bandwidth-aware job scheduling with dynamic information model for Grid resource brokers

A resource broker with a user-friendly interface for job submission developed on a platform constructed using the Globus toolkit is proposed. The broker employs a domain-based network information model and dynamic version to measure network statuses, and also monitors and collects resource statuses and network-related information as the basis of its brokerage. A network bandwidth-aware job scheduling algorithm for brokering suitable Grid resources to communication-intensive jobs based on improving and preserving the advantages of our previously developed network information model is also proposed. Using timely information, the resource broker effectively matches Grid resources and user requests, thus improving job execution efficiency.     

Tractable Structures for Constraint Satisfaction with Truth Tables

The way the graph structure of the constraints influences the complexity of constraint satisfaction problems (CSP) is well understood for bounded-arity constraints. The situation is less clear if there is no bound on the arities. In this case the answer depends also on how the constraints are represented in the input. We study this question for the truth table representation of constraints. We introduce a new hypergraph measure adaptive width and show that CSP with truth tables is polynomial-time solvable if restricted to a class of hypergraphs with bounded adaptive width. Conversely, assuming a conjecture on the complexity of binary CSP, there is no other polynomial-time solvable case. Finally, we present a class of hypergraphs with bounded adaptive width and unbounded fractional hypertree width.     

A Linear-Time Algorithm for Hamming Distance with Shifts

The Hamming distance with shifts was introduced by Bookstein et al. as a generalization of the traditional Hamming distance to allow a tunable degree of fuzziness when comparing two binary sequences of the same length. We present a linear-time algorithm for computing this distance. The previous best time bound was quadratic.     

Contact identification for assembly–disassembly simulation with a haptic device

Assembly/Disassembly (A/D) simulations using haptic devices are facing difficulties while simulating insertion/extraction operations, such as removing cylinders from holes. In order to address this configuration as well as others, an approach based on contact identification between components is presented in this paper. This approach can efficiently contribute either to a new A/D simulation preparation process relying on two types of shape representations (mesh and CAD NURBS models), or directly to the real time simulation process when it is performed with 6D haptic devices. The model processing pipeline is described and illustrated to show how information can be propagated and used for contact detection. Then, the contact identification process is introduced and illustrated through an example.

Time-extended multi-robot coordination for domains with intra-path constraints

Many applications require teams of robots to cooperatively execute tasks. Among these domains are those in which successful coordination must respect intra-path constraints, which are constraints that occur on the paths of agents and affect route planning. This work focuses on multi-agent coordination for disaster response with intra-path precedence constraints, a compelling application that is not well addressed by current coordination methods. In this domain a group of fire truck agents attempt to address fires spread throughout a city in the wake of a large-scale disaster. The disaster has also caused many city roads to be blocked by impassable debris, which can be cleared by bulldozer robots. A high-quality coordination solution must determine not only a task allocation but also what routes the fire trucks should take given the intra-path precedence constraints and which bulldozers should be assigned to clear debris along those routes.     

3D Human Motion Tracking with a Coordinated Mixture of Factor Analyzers

A major challenge in applying Bayesian tracking methods for tracking 3D human body pose is the high dimensionality of the pose state space. It has been observed that the 3D human body pose parameters typically can be assumed to lie on a low-dimensional manifold embedded in the high-dimensional space. The goal of this work is to approximate the low-dimensional manifold so that a low-dimensional state vector can be obtained for efficient and effective Bayesian tracking. To achieve this goal, a globally coordinated mixture of factor analyzers is learned from motion capture data. Each factor analyzer in the mixture is a “locally linear dimensionality reducer” that approximates a part of the manifold. The global parametrization of the manifold is obtained by aligning these locally linear pieces in a global coordinate system. To enable automatic and optimal selection of the number of factor analyzers and the dimensionality of the manifold, a variational Bayesian formulation of the globally coordinated mixture of factor analyzers is proposed. The advantages of the proposed model are demonstrated in a multiple hypothesis tracker for tracking 3D human body pose. Quantitative comparisons on benchmark datasets show that the proposed method produces more accurate 3D pose estimates over time than those obtained from two previously proposed Bayesian tracking methods.     

Searching for filters with 'interesting' output distributions: an uninteresting direction to explore?

It has been independently proposed, by Barlow, Field, Intrator and co-workers, that the receptive fields of neurons in V1 are optimized to generate 'sparse', Kurtotic, or 'interesting' output probability distributions. We investigate the empirical evidence for this further and argue that filters can produce 'interesting' output distributions simply because natural images have variable local intensity variance. If the proposed filters have zero DC, then the probability distribution of filter outputs (and hence the output Kurtosis) is well predicted simply from these effects of variable local variance. This suggests that finding filters with high output Kurtosis does not necessarily signal interesting image structure. It is then argued that finding filters that maximize output Kurtosis generates filters that are incompatible with observed physiology. In particular the optimal difference-of-Gaussian (DOG) filter should have the smallest possible scale, an on-centre off-surround cell should have a negative DC, and that the ratio of centre width to surround width should approach unity. This is incompatible with the physiology. Further, it is also predicted that oriented filters should always be oriented in the vertical direction, and of all the filters tested, the filter with the highest output Kurtosis has the lowest signal-to-noise ratio (the filter is simply the difference of two neighbouring pixels). Whilst these observations are not incompatible with the brain using a sparse representation, it does argue that little significance should be placed on finding filters with highly Kurtotic output distributions. It is therefore argued that other constraints are required in order to understand the development of visual receptive fields.