BEST : an efficient algorithm for mining frequent unordered embedded subtrees

This paper presents an algorithm for mining unordered embedded subtrees using the balanced-optimal-search canonical form (BOCF). A tree structure guided scheme based enumeration approach is defined using BOCF for systematically enumerating the valid subtrees only. Based on this canonical form and enumeration technique, the balanced optimal search embedded subtree mining algorithm (BEST) is introduced for mining embedded subtrees from a database of labelled rooted unordered trees. The extensive experiments on both synthetic and real datasets demonstrate the efficiency of BEST over the two state-of-the-art algorithms for mining embedded unordered subtrees, SLEUTH and U3.

Adapting “8-bit” motion style to 3D computer animation for Wreck-it Ralph

Tangled (2011) demonstrated that Walt Disney Animation has successfully extended the traditional Disney animation aesthetic to the 3D medium. The very next film produced by the studio however, Wreck-it Ralph (2012), required the animators (trained in the traditional Disney style) to develop a limited style of animation inspired by the 8-bit motion of 1980s video games. This paper examines the 8-bit style motion in Wreck-it Ralph to understand if and how the principles of animation were adapted for the film.

Force controlled hexapod walking

This thesis is a study on controlling methods for six-legged robots. The study is based on mathematical modeling and simulation. A new joint controller is proposed and tested in simulation that uses joint angles and leg reaction force as inputs to generate a torque, and a method to optimise this controller is formulated and validated. Simulation shows that hexapod can walk on flat ground based on PID controllers with just four target configurations and a set of leg coordination rules, which provided the basis for the design of the new controller.

Decision support for the efficient annotation of bioacoustic events

Acoustic sensors allow scientists to scale environmental monitoring over large spatiotemporal scales. The faunal vocalisations captured by these sensors can answer ecological questions, however, identifying these vocalisations within recorded audio is difficult: automatic recognition is currently intractable and manual recognition is slow and error prone. In this paper, a semi-automated approach to call recognition is presented. An automated decision support tool is tested that assists users in the manual annotation process. The respective strengths of human and computer analysis are used to complement one another. The tool recommends the species of an unknown vocalisation and thereby minimises the need for the memorization of a large corpus of vocalisations. In the case of a folksonomic tagging system, recommending species tags also minimises the proliferation of redundant tag categories. We describe two algorithms: (1) a “naïve” decision support tool (16%–64% sensitivity) with efficiency of O(n) but which becomes unscalable as more data is added and (2) a scalable alternative with 48% sensitivity and an efficiency ofO(log n). The improved algorithm was also tested in a HTML-based annotation prototype. The result of this work is a decision support tool for annotating faunal acoustic events that may be utilised by other bioacoustics projects.

Visual place recognition for persistent robot navigation in changing environments

This thesis demonstrates that robots can learn about how the world changes, and can use this information to recognise where they are, even when the appearance of the environment has changed a great deal. The ability to localise in highly dynamic environments using vision only is a key tool for achieving long-term, autonomous navigation in unstructured outdoor environments. The proposed learning algorithms are designed to be unsupervised, and can be generated by the robot online in response to its observations of the world, without requiring information from a human operator or other external source.

Numerical investigation of upstream fuel injection through porous media for scramjet engines via surrogate-assisted evolutionary algorithms

A multi-objective design optimization study has been conducted for upstream fuel injection through porous media applied to the first ramp of a two-dimensional scramjet intake. The optimization has been performed by coupling evolutionary algorithms assisted by surrogate modeling and computational fluid dynamics with respect to three design criteria, that is, the maximization of the absolute mixing quantity, total pressure saving, and fuel penetration. A distinct Pareto optimal front has been obtained, highlighting the counteracting behavior of the total pressure against the mixing efficiency and fuel penetration. The injector location and size have been identified as the key design parameters as a result of a sensitivity analysis, with negligible influence of the porous properties in the configurations and conditions considered in the present study. Flowfield visualization has revealed the underlying physics associated with the effects of these dominant parameters on the shock structure and intensity.

Towards universal search design

For people with cognitive disabilities, technology is more often thought of as a support mechanism, rather than a source of division that may require intervention to equalize access across the cognitive spectrum. This paper presents a first attempt at formalizing the digital gap created by the generalization of search engines. This was achieved through the development of a mapping of cognitive abilities required by users to execute low- level tasks during a standard Web search task. The mapping demonstrates how critical these abilities are to successfully use search engines with an adequate level of independence. It will lead to a set of design guidelines for search engine interfaces that will allow for the engagement of users of all abilities, and also, more importantly, in search algorithms such as query suggestion and measure of relevance (i.e. ranking).

Design, construction and evaluation of systems to predict risk in obstetrics

We present a systematic, practical approach to developing risk prediction systems, suitable for use with large databases of medical information. An important part of this approach is a novel feature selection algorithm which uses the area under the receiver operating characteristic (ROC) curve to measure the expected discriminative power of different sets of predictor variables. We describe this algorithm and use it to select variables to predict risk of a specific adverse pregnancy outcome: failure to progress in labour. Neural network, logistic regression and hierarchical Bayesian risk prediction models are constructed, all of which achieve close to the limit of performance attainable on this prediction task. We show that better prediction performance requires more discriminative clinical information rather than improved modelling techniques. It is also shown that better diagnostic criteria in clinical records would greatly assist the development of systems to predict risk in pregnancy. We present a systematic, practical approach to developing risk prediction systems, suitable for use with large databases of medical information. An important part of this approach is a novel feature selection algorithm which uses the area under the receiver operating characteristic (ROC) curve to measure the expected discriminative power of different sets of predictor variables. We describe this algorithm and use it to select variables to predict risk of a specific adverse pregnancy outcome: failure to progress in labour. Neural network, logistic regression and hierarchical Bayesian risk prediction models are constructed, all of which achieve close to the limit of performance attainable on this prediction task. We show that better prediction performance requires more discriminative clinical information rather than improved modelling techniques. It is also shown that better diagnostic criteria in clinical records would greatly assist the development of systems to predict risk in pregnancy.

Identifying weak linear features with the "coalescing shortest path image transform"

The detection of line-like features in images finds many applications in microanalysis. Actin fibers, microtubules, neurites, pilis, DNA, and other biological structures all come up as tenuous curved lines in microscopy images. A reliable tracing method that preserves the integrity and details of these structures is particularly important for quantitative analyses. We have developed a new image transform called the "Coalescing Shortest Path Image Transform" with very encouraging properties. Our scheme efficiently combines information from an extensive collection of shortest paths in the image to delineate even very weak linear features. © Copyright Microscopy Society of America 2011.

DroplIT, an improved image analysis method for droplet identification in high-throughput crystallization trials

The application of robotics to protein crystallization trials has resulted in the production of millions of images. Manual inspection of these images to find crystals and other interesting outcomes is a major rate-limiting step. As a result there has been intense activity in developing automated algorithms to analyse these images. The very first step for most systems that have been described in the literature is to delineate each droplet. Here, a novel approach that reaches over 97% success rate and subsecond processing times is presented. This will form the seed of a new high-throughput system to scrutinize massive crystallization campaigns automatically. © 2010 International Union of Crystallography Printed in Singapore-all rights reserved.

An observation about circular shortest paths: Dealing with additional constraints using branch and bound

Circular shortest paths represent a powerful methodology for image segmentation. The circularity condition ensures that the contour found by the algorithm is closed, a natural requirement for regular objects. Several implementations have been proposed in the past that either promise closure with high probability or ensure closure strictly, but with a mild computational efficiency handicap. Circularity can be viewed as a priori information that helps recover the correct object contour. Our "observation" is that circularity is only one among many possible constraints that can be imposed on shortest paths to guide them to a desirable solution. In this contribution, we illustrate this opportunity under a volume constraint but the concept is generally applicable. We also describe several adornments to the circular shortest path algorithm that proved useful in applications. © 2011 IEEE.

Tubule detection in testis images using boundary weighting and circular shortest path

In studies of germ cell transplantation, measureing tubule diameters and counting cells from different populations using antibodies as markers are very important. Manual measurement of tubule sizes and cell counts is a tedious and sanity grinding work. In this paper, we propose a new boundary weighting based tubule detection method. We first enhance the linear features of the input image and detect the approximate centers of tubules. Next, a boundary weighting transform is applied to the polar transformed image of each tubule region and a circular shortest path is used for the boundary detection. Then, ellipse fitting is carried out for tubule selection and measurement. The algorithm has been tested on a dataset consisting of 20 images, each having about 20 tubules. Experiments show that the detection results of our algorithm are very close to the results obtained manually. © 2013 IEEE.

What patient information allows us to make accurate predictions of outcome?

Only some of the information contained in a medical record will be useful to the prediction of patient outcome. We describe a novel method for selecting those outcome predictors which allow us to reliably discriminate between adverse and benign end results. Using the area under the receiver operating characteristic as a nonparametric measure of discrimination, we show how to calculate the maximum discrimination attainable with a given set of discrete valued features. This upper limit forms the basis of our feature selection algorithm. We use the algorithm to select features (from maternity records) relevant to the prediction of failure to progress in labour. The results of this analysis motivate investigation of those predictors of failure to progress relevant to parous and nulliparous sub-populations.

Using upper bounds on attainable discrimination to select discrete valued features

Selection of features that will permit accurate pattern classification is a difficult task. However, if a particular data set is represented by discrete valued features, it becomes possible to determine empirically the contribution that each feature makes to the discrimination between classes. This paper extends the discrimination bound method so that both the maximum and average discrimination expected on unseen test data can be estimated. These estimation techniques are the basis of a backwards elimination algorithm that can be use to rank features in order of their discriminative power. Two problems are used to demonstrate this feature selection process: classification of the Mushroom Database, and a real-world, pregnancy related medical risk prediction task - assessment of risk of perinatal death.

A Likelihood-Maximizing Framework for Enhanced In-Car Speech Recognition Based on Speech Dialog System Interaction

Speech recognition in car environments has been identified as a valuable means for reducing driver distraction when operating noncritical in-car systems. Under such conditions, however, speech recognition accuracy degrades significantly, and techniques such as speech enhancement are required to improve these accuracies. Likelihood-maximizing (LIMA) frameworks optimize speech enhancement algorithms based on recognized state sequences rather than traditional signal-level criteria such as maximizing signal-to-noise ratio. LIMA frameworks typically require calibration utterances to generate optimized enhancement parameters that are used for all subsequent utterances. Under such a scheme, suboptimal recognition performance occurs in noise conditions that are significantly different from that present during the calibration session – a serious problem in rapidly changing noise environments out on the open road. In this chapter, we propose a dialog-based design that allows regular optimization iterations in order to track the ever-changing noise conditions. Experiments using Mel-filterbank noise subtraction (MFNS) are performed to determine the optimization requirements for vehicular environments and show that minimal optimization is required to improve speech recognition, avoid over-optimization, and ultimately assist with semireal-time operation. It is also shown that the proposed design is able to provide improved recognition performance over frameworks incorporating a calibration session only.