Existential rigidity and many modalities in order-sorted logic

Order-sorted logic is a useful tool for knowledge representation and reasoning because it enables representation of sorted terms and formulas along with partially ordered sorts (called sort-hierarchy). However, this logic cannot represent more complex sorted expressions when they are true in any possible world (as rigid) or some possible worlds (as modality) such as time, space, belief, or situation. In this study, we extend order-sorted logic by introducing existential rigidity and many modalities. In the extended logic, sorted modal formulas are interpreted over the Cartesian product of sets of possible worlds. We present a new labeled tableau calculus to check the (un)satisfiability and validity of sorted modal formulas.     

Animating Pictures of Fluid using Video Examples

We propose a system that allows the user to design a continuous flow animation starting from a still fluid image. The basic idea is to apply the fluid motion extracted from a video example to the target image. The system first decomposes the video example into three components, an average image, a flow field and residuals. The user then specifies equivalent information over the target image. The user manually paints the rough flow field, and the system automatically refines it using the estimated gradients of the target image. The user semi-automatically transfers the residuals onto the target image. The system then approximates the average image and synthesizes an animation on the target image by adding the transferred residuals and warping them according to the user-specified flow field. Finally, the system adjusts the appearance of the resulting animation by applying histogram matching. We designed animations of various pictures, such as rivers, waterfalls, fires, and smoke.     

Non-photorealistic, depth-based image editing

Recent works in image editing are opening up new possibilities to manipulate and enhance input images. Within this context, we leverage well-known characteristics of human perception along with a simple depth approximation algorithm to generate non-photorealistic renditions that would be difficult to achieve with existing methods. Once a perceptually plausible depth map is obtained from the input image, we show how simple algorithms yield powerful new depictions of such an image. Additionally, we show how artistic manipulation of depth maps can be used to create novel non-photorealistic versions, for which we provide the user with an intuitive interface. Our real-time implementation on graphics hardware allows the user to efficiently explore artistic possibilities for each image. We show results produced with six different styles proving the versatility of our approach, and validate our assumptions and simplifications by means of a user study.     

Decision-Centric Information Monitoring

We are interested in information management for decision support applications, especially those that monitor distributed, heterogeneous databases to assess time-critical decisions. Users of such applications can easily be overwhelmed with data that may change rapidly, may conflict, and may be redundant. Developers are faced with a dilemma: either filter out most information and risk excluding critical items, or gather possibly irrelevant or redundant information, and overwhelm the decision maker. This paper describes a solution to this dilemma called decision-centric information monitoring (DCIM). First, we observe that decision support systems should monitor only information that can potentially change some decision. We present an architecture for DCIM that meets the requirements implied by this observation. We describe techniques for identifying the highest value information to monitor and techniques for monitoring that information despite autonomy, distribution, and heterogeneity of data sources. Finally, we present lessons learned from building LOOKOUT, which is to our knowledge the first implementation of a top-to-bottom system performing decision-centric information monitoring.     

Replica Placement Strategies in Data Grid

Replication is a technique used in Data Grid environments that helps to reduce access latency and network bandwidth utilization. Replication also increases data availability thereby enhancing system reliability. The research addresses the problem of replication in Data Grid environment by investigating a set of highly decentralized dynamic replica placement algorithms. Replica placement algorithms are based on heuristics that consider both network latency and user requests to select the best candidate sites to place replicas. Due to dynamic nature of Grid, the candidate site holds replicas currently may not be the best sites to fetch replicas in subsequent periods. Therefore, a replica maintenance algorithm is proposed to relocate replicas to different sites if the performance metric degrades significantly. The study of our replica placement algorithms is carried out using a model of the EU Data Grid Testbed 1 [Bell et al. Comput. Appl., 17(4), 2003] sites and their associated network geometry. We validate our replica placement algorithms with total file transfer times, the number of local file accesses, and the number of remote file accesses.     

Dynamic diamond anvil cell (dDAC): a novel device for studying the dynamic-pressure properties of materials

We have developed a unique device, a dynamic diamond anvil cell (dDAC), which repetitively applies a time-dependent load/pressure profile to a sample. This capability allows studies of the kinetics of phase transitions and metastable phases at compression (strain) rates of up to 500 GPa/s (approximately 0.16 s(-1) for a metal). Our approach adapts electromechanical piezoelectric actuators to a conventional diamond anvil cell design, which enables precise specification and control of a time-dependent applied load/pressure. Existing DAC instrumentation and experimental techniques are easily adapted to the dDAC to measure the properties of a sample under the varying load/pressure conditions. This capability addresses the sparsely studied regime of dynamic phenomena between static research (diamond anvil cells and large volume presses) and dynamic shock-driven experiments (gas guns, explosive, and laser shock). We present an overview of a variety of experimental measurements that can be made with this device.     

An efficient Earth Mover's Distance algorithm for robust histogram comparison

We propose EMD-L1: a fast and exact algorithm for computing the Earth Mover's Distance (EMD) between a pair of histograms. The efficiency of the new algorithm enables its application to problems that were previously prohibitive due to high time complexities. The proposed EMD-L1 significantly simplifies the original linear programming formulation of EMD. Exploiting the L1 metric structure, the number of unknown variables in EMD-L1 is reduced to O(N) from O(N2) of the original EMD for a histogram with N bins. In addition, the number of constraints is reduced by half and the objective function of the linear program is simplified. Formally, without any approximation, we prove that the EMD-L1 formulation is equivalent to the original EMD with a L1 ground distance. To perform the EMD-L1 computation, we propose an efficient tree-based algorithm, Tree-EMD. Tree-EMD exploits the fact that a basic feasible solution of the simplex algorithm-based solver forms a spanning tree when we interpret EMD-L1 as a network flow optimization problem. We empirically show that this new algorithm has an average time complexity of O(N2), which significantly improves the best reported supercubic complexity of the original EMD. The accuracy of the proposed methods is evaluated by experiments for two computation-intensive problems: shape recognition and interest point matching using multidimensional histogram-based local features. For shape recognition, EMD-L1 is applied to compare shape contexts on the widely tested MPEG7 shape data set, as well as an articulated shape data set. For interest point matching, SIFT, shape context and spin image are tested on both synthetic and real image pairs with large geometrical deformation, illumination change, and heavy intensity noise. The results demonstrate that our EMD-L1-based solutions outperform previously reported state-of-the-art features and distance measures in solving the two tasks.     

Modeling expert problem solving in a game of chance: a Yahtzee© case study

Although developments on software agents have led to useful applications in automation of routine tasks such as electronic mail filtering, there is a scarcity of research that empirically evaluates the performance of a software agent versus that of a human reasoner, whose problem-solving capabilities the agent embodies. In the context of a game of a chance, namely Yahtzee©, we identified strategies deployed by expert human reasoners and developed a decision tree for agent development. This paper describes the computer implementation of the Yahtzee game as well as the software agent. It also presents a comparison of the performance of humans versus an automated agent. Results indicate that, in this context, the software agent embodies human expertise at a high level of fidelity.     

Selectivity and stability via dendritic nonlinearity

Inspired by recent studies regarding dendritic computation, we constructed a recurrent neural network model incorporating dendritic lateral inhibition. Our model consists of an input layer and a neuron layer that includes excitatory cells and an inhibitory cell; this inhibitory cell is activated by the pooled activities of all the excitatory cells, and it in turn inhibits each dendritic branch of the excitatory cells that receive excitations from the input layer. Dendritic nonlinear operation consisting of branch-specifically rectified inhibition and saturation is described by imposing nonlinear transfer functions before summation over the branches. In this model with sufficiently strong recurrent excitation, on transiently presenting a stimulus that has a high correlation with feed- forward connections of one of the excitatory cells, the corresponding cell becomes highly active, and the activity is sustained after the stimulus is turned off, whereas all the other excitatory cells continue to have low activities. But on transiently presenting a stimulus that does not have high correlations with feedforward connections of any of the excitatory cells, all the excitatory cells continue to have low activities. Interestingly, such stimulus-selective sustained response is preserved for a wide range of stimulus intensity. We derive an analytical formulation of the model in the limit where individual excitatory cells have an infinite number of dendritic branches and prove the existence of an equilibrium point corresponding to such a balanced low-level activity state as observed in the simulations, whose stability depends solely on the signal-to-noise ratio of the stimulus. We propose this model as a model of stimulus selectivity equipped with self-sustainability and intensity-invariance simultaneously, which was difficult in the conventional competitive neural networks with a similar degree of complexity in their network architecture. We discuss the biological relevance of the model in a general framework of computational neuroscience.