Honours Seminars

The 2000 Honours seminars

The 2000 4th year Seminar Series will be held from 16-20 October. Seminars will be presented by all Honours and Graduate Diploma students whose projects come to completion at the end of 2000.

All seminars will be held in Room 2.28 in the Computer Science Building. Seminars will consist of a 35-minute presentation followed by 5 minutes of questions. The seminars are open to all interested members of the University community.

's postponed seminar has been re-scheduled at

4pm on Wednesday 25 October in Room 2.28 in the CS Building

This year's seminar examination committee consists of:

• Prof. Robyn Owens (Head of Department),

• Dr Lyndon While (4th year Co-ordinator),

• Dr Marion Cottingham,

• Dr Amitava Datta, and

• Dr John Morris,

Any further questions about the Department's Honours or Graduate Diploma Programmes may be directed to our Fourth Year Coordinator, Lyndon While.

Patrick Ip

Fingerprint patterns are rarely perfect. Various types of noise may corrupt the pattern. Therefore, an effective method of enhancing fingerprint images needs to be implemented to facilitate matching and identification.

Enhancement methods range from simple edge enhancement and binarisation to more complex methods. A general approach to fingerprint enhancement is examined. These traditional techniques depend heavily on ridge orientations. Hence, the linear aspects of the fingerprint image are enhanced well. Nevertheless, the objective of improving the image to facilitate matching is not fully accomplished by such methods.

Matching algorithms use the identification of prominent characteristics. These features are often non-linear and near areas of high curvature, therefore enhancement in these areas are often misguided or neglected altogether by the traditional fingerprint enhancement techniques. To address this problem, a general image enhancement algorithm is examined. This method uses second order derivative information to detect features not noticed by first order processes. Therefore, applying a similar process to fingerprint images may help to detect the important characteristics of a fingerprint.

Thang Si Tran

The idea of creating three-dimensional models from images arises because images are 2D projections of the real world, holding less information than the original three-dimensional data. The process of reconstruction attempts to reproject the scene back to its three-dimensional representation as accurately as possible from the data given by its images.

Fast and efficient reconstruction becomes a major factor in applications such as robot vision and navigation where processing time is valuable. With reconstruction now possible from a single image, testing and implementing such a process is a worthy challenge.

This seminar discusses the techniques used to create three-dimensional reconstructions of scenes from a single image. Results from the implementation and testing of two algorithms are presented with the conclusion that vanishing points play an integral part to the whole reconstruction process.

Pak-Ming Wan

Acoustics is the scientific study of sound. Since its development in the early 1900's, it has found uses in architectural design as well as other fields like engineering. The application of acoustic theory is especially important in situations in which aural presentation is crucial (such as performing arts venues for theatre and music) The aim of my project was to design a computer aided software tool to assist acoustical engineers and architects to predict the acoustic performance of an enclosure before it has been constructed.

The AcoustiKit is a Matlab toolkit that I have written to analyse the acoustic of an enclosure. The focus of my discussions will lie with the choice of different models that are available for modelling the acoustics within an enclosure, the choice of models that were eventually implemented in the AcoustiKit, and the functionality of the AcoustiKit.

Jamieson Lee

Laboratory work plays an important part of the learning process for many students. However, there are many aspects of conducting a laboratory session that both students and demonstrators feel can be improved. With the recent advances in Internet technologies, we are beginning to see new possibilities in the way laboratory exercises can be operated.

The Telelabs project was devised as a way for students to remotely access laboratory equipment using the Internet. The feasibility of having such a facility is highly dependent on the design decisions made. In this seminar I will be discussing the issues relating to the user interface and the network that form the fundamental structure of the Telelabs system. Also, through the use of a practical real-life example, a working prototype will be used to demonstrate the design choices that were made, and show how a laboratory experiment can be controlled using the system.

Michael Wager

The path planning problem has been proven both PSPACE complete and NP complete. All the traditional approaches have only had marginal results when trying to tackle this problem. In recent years a roadmap planner has been developed that has had impressive results. I will discuss how the roadmap approach works and compare the results with a traditional potential field planner. I will also talk about my implementation of a planner that is based on the Voronoi diagram and show that this method is not only faster, but is more desirable as well.

Cameron Rochester

Distributed communication has existed on the Internet for many years in a text-based form. The improvement of audio/video streaming technology in recent years has increased the amount of streaming content on the Internet. The use of compression techniques and network technologies has made it possible to create real-time, distributed, multi-user audio communication systems.

This seminar will examine the available technologies that make the design and implementation of streaming audio communication possible. An analysis of the most efficient audio compression and network transportation will be covered. Implementation of the system with reference to Microsoft's DirectShow Application Programmers Interface (API).

Darren Kam

There is no limit to the number of books and web sites dedicated to the art of web design. Self-professed "web design experts" often base their golden theories on personal experiences and philosophies. The existence of such non-specific guidelines purports the need for a scientific study into this rapidly growing field. This was the basis of research known as the Juicer Experiment. The goal of the experiment was to create a tool known as the Juicer to be used for research into web usability as well as marketing purposes. As the name suggests, the Juicer Experiment executed as a live experiment on the Internet to gather statistics from user-monitoring, survey, and feedback techniques.

Research by the Juicer Experiment was centred on a set of hypotheses concerning the effectiveness of web site design. Investigations reveal how the location of graphic and text hyperlinks on a page contributes to user behaviour, the effects of culture on user behaviour, and how animations on web pages deteriorate viewing efficiency. Distortion of survey information and its consequences on market estimation are also discussed in this seminar.

David Chan

People don't speak right. That is one of the many problems which natural language processing systems face when attempting to recognise speech.

A phonemic-based natural language processing system uses phonemes, the basic units of speech, as a basis for building correct words, and eventually correct sentences. My work has been in exploring a data structure which speeds up phoneme-to-word matching, and may be used for any string correction problem where a dictionary of valid strings is known.

I will be discussing this structure, known as a hierarchical file, and the results from my implementation.

Ben Deany

The main thrust of the project was to assess the viability of using adaptive learning techiques, in particular neural networks, to autonomously learn the game of soccer. The assessment was based upon factors including scalability, generality, and retentiveness.

Research in this area is of interest because it is difficult to implement adaptive learning technologies to complex problem domains.

The seminar will discuss the initial decision making process which defined the parameters of the project (including the type of neural network that was used, the training method, and the learning system), the experimental method and trial structure, the implementation and use of Olmec (the custom-built simulator that was used for running trials), and our results and suggestions for further research.

Discussion will culminate in a summary of our results and conclusions, in which it will be stated that this kind of adaptive learning approach seems promising for the given problem domain.

Mark Barnard

Audio speech recognition systems are seriously degraded in noisy environments. The features of speech that are degraded by noise in audio systems are the features of speech that are most distinct visually. An automatic visual speech recognition system should therefore be a beneficial complement to an audio speech recognition system when the audio system is used in a noisy environment.

In order to use visual speech recognition there must be a way of tracking the motion of the lips in the speaker. One of the most common methods of tracking a speakers lips is active contour models or snakes. This seminar introduces a new implementation of snakes that combines outer lip pattern matching and biological constraints, such as smooth lip contour splines. This implementation provides accurate and robust tracking of the inner and outer lip contours.

The data produced by this tracking system is then used to train a time-delay neural network to recognise the words from "one" to "twelve" . The implementation and results of this recognition system will be discussed.

Andrew Lewis

When designing parallel systems, efficient communication between processors can be one of the most difficult problems to overcome. Shared memory models suffer from highly complex interconnections between the processors and memory, and cannot be expanded with any great ease. Implementing algorithms on static structures such as meshes and hyper-cubes can prove difficult if the message passing for the algorithm does not match the structure. Electronic bus systems suffer from low bandwidth and unpredictable message propagation times. In order to solve these problems, a new parallel model, the linear array with reconfigurable pipelined bus system (LARPBS) has been proposed by Pan et al. [PL98]. This system solves many of the problems associated with electronic buses by using optical interconnections that provide high bandwidth and low error rates. Many algorithms have been proposed for the LARPBS [HP95], including quicksort [PHL98], matrix multiplication [LPZ98], and boolean matrix multiplication [Li97]. However, it can be difficult to understand the behavior of these algorithms as the LARPBS may be reconfigured many times during their execution.

We present the virtual LARPBS, a program that simulates the LARPBS. The purpose of the virtual LARPBS is to provide the user with a visual environment for analysing and debugging algorithms designed for the LARPBS, and also to provide a tool for teaching the fundamentals of parallel systems, especially the LARPBS. The simulator can be used as an algorithm development and visualization tool. It is also possible to use the simulator for analysing performance of algorithms designed for the LARPBS model. To our knowledge, this is the first simulator developed for the LARPBS model.

References

[HP95] M. Hamdi and Y. Pan. Efficent parallel algorithms on optically interconnected arrays ofprocessors, IEE Proc. Computers amd Digital Techniques, 142:87-92, March 1995
[Li97] K. Li. Constant time boolean matric multiplication on a linear array with a reconfigurable pipelined bus system. Journal of Supercomputing, 11(4):391-403, 1997.
[LPZ98] K. Li, Y. Pan, and S. Zheng. Fast and processor efficent parallel matrix multiplication algorithms on a linear array with a reconfigurable pipelined bus system. IEE Transactions on Parallel and Distributed Systems, 9(8):705-720, August 1998
[PHL98] Y. Pan, M. Hamdi, and K. Li. Efficent and scalable quicksort on a linear array with a reconfigurable pipelined bus system. Future Generation Computer Systems, 13(6):501-513, June 1998
[PL98] Y. Pan and K. Li. Linear array with a reconfigurable pipelined bus system - concepts and applications. Information Sciences - An International Journal, 106(3/4):237-258, May 1998

Anthony Di Pietro

Learning techniques are an important part of artificial intelligence, as they allow a player to adapt to an unknown or dynamic environment. Predicting opponents' actions is an important part of many games. Using learning techniques to adapt a player's strategy to take advantage of opponents' weaknesses is known as opponent modelling.

We present a comparison of various learning techniques for opponent modelling, using a simple bluffing game known as Bluff. Learning techniques studied include hill climbing, evolutionary algorithms, genetic algorithms, particle swarm optimization, and a new technique we developed, known as dynamic particle swarm optimization. The emphasis is on identifying their respective strengths, weaknesses and idiosyncrasies, so that they may be better chosen and implemented for specific opponent modelling applications in the future.

Nick Jardine

In lazy functional languages such as Haskell, the left-to-right ordering of argument evaluation can cause functions such as && to lose their theoretical commutativity. This problem can be overcome by a technique known as parallel pattern matching, that causes a pattern to not match if any argument fails.

A possible implementation is to make the function strict in all arguments, however the result is that the function will not return if even one argument is in error. We will look at a strategy for enabling functions to be both commutative and non-strict, by evaluating all necessary arguments concurrently. We will also investigate the cost of such a strategy, based around a test implementation. A method for reducing the cost, program transformations, will also be looked at.

Meng Seet

In computer graphics, a complex object has lots of vertices and triangles, and takes a long time to render; collision detection between two complex objects is computationally expensive. A bounding volume is a simple object that encloses a complex object. It can be used as a substitute for the actual object when rendering or for faster collision detection. The simplest bounding volume is a bounding box. It is a rectangular box that encloses a complex object at the extremities for each coordinate axis. It is usually inaccurate and rarely used as a bounding volume.

I present the oriented tribox algorithm: it creates a bounding volume that is an improvement over the bounding box without a huge reduction in speed. The tribox also takes the extremities for the diagonals of the axes. Orienting the tribox allows a tighter fit for badly oriented complex objects.

This seminar will introduce some background information and cover the oriented tribox algorithm in detail. I will also compare the oriented tribox with other bounding volumes and show that it is better. I will also discuss hierarchical decomposition and how this will further improve the accuracy of the oriented tribox representation.

James Strauss

The demand for real-time display of realistic three-dimensional virtual environments on consumer level hardware is growing. As it does, so does the size and complexity of the polygonal models representing objects in these environments. Increases in model complexity currently outpace increases in graphics hardware performance.

Graphical applications that simply render all potentially visible polygons may generate frames at highly variable rates, with no guaranteed upper bound on any single frame. The aim of the level of detail technique is to sacrifice some model complexity in return for greater interactivity in situations where the environment is too complex to be rendered in full detail at the target frame rate.

Given a polygonal model, a continuous level of detail system should facilitate the generation of approximations to the model at arbitrary levels of detail. In polygonal models, areas of concentrated vertices are used to describe fine detail. A Hierarchical Clustering Algorithm exploits this by removing these fine details first.

Development of CLODA, a tool using hierarchical clustering of vertices to automate the production of levels of detail (LODs), will be discussed. Explanations of the advantages and disadvantages of using the hierarchical clustering algorithm and examples of the resulting approximations generated from several geometric models will be presented.

Nick Lowe

The conventional realtime pipeline renders a polygonal scene to a picture using the pinhole camera model. This approach maximises framerate at the cost of realism. Many tools have been added to the realtime pipeline to improve realism. Common tools include the stencil and accumulation buffers. Most implementations of these tools use a small and fixed amount of memory to add volumetric and lens effects respectively.

The primary motivation for my dissertation was to create a faster tool for realism. Typically, processing can be reduced if memory usage is increased. Therefore, a tool that uses a large and variable amount of memory could improve realism without significantly increasing processing. Design and development of this tool led to a new rendering pipeline. The new pipeline introduces the nexus, a persistent scene discretisation, and universal object-orientation.

In this seminar, I will present the conventional pipeline, discuss the new pipeline with particular detail on the nexus and a brief demonstration.

Navid Mavaddat

Vanishing points are the points at which the extensions of parellel lines appear to converge in a perspective drawing. To extract 3d information from pictures we must first determine these vanishing points as they encode critial information about the perspective view of a scene.

Traditionally determining vanishing points has been an erronerous and cumbersome task. I attempt to automate this process through the combination of image analysis techniques and projective geometry. Automatic vanishing point detection assists in the removal of projective distortion in single view metrology and rectification applications.

Ingrid Benussi

There are many people in our community that are affected by some form of hearing limitation. One of these forms of communication is the use of sign language as gestures. Deaf communities in Australia use a sign language called Auslan. Auslan signs use various hand shapes and movement as well as the position of the hands with respect to the upper body. Auslan is different from other sign languages, and has a different grammar from English.

My project is to build a learning tool that aids the unaffected person to learn sign language. As a first step towards this goal, a single hand motion animation is achieved. This prototype uses the Auslan basic hand postures that are requested by the user, the hand motion throughout those hand postures are generated and displayed by using a 3D graphics display.

A human motion animation technique is used where the 3D hand skeleton figures for each of the requested Auslan basic hand postures are generated by using kinematic hand data that consist of the finger joint angles. The motion in between these figures are generated by interpolating them in order to produce in-between skeleton figures. These postures are displayed by applying 3D shapes and rendering them using Java 3D graphics facilities.

Chi Yoong

There is a very interesting twist to the colouring problem for the class of planar graphs. On one hand, colouring the vertices of a planar graph using 2 or less colours can be done in linear time. This is true when 5 or more colours are used as well. Furthermore, all planar graphs are known to be 4-colourable.

On the other hand, 3-colouring the vertices of a planar graph is an NP-hard problem. Although it has been shown that a 4-colouring of a planar graph can be found in O(n^2) time, the algorithm is not practically feasible.

Heuristic techniques are examined as a possible method of colouring planar graphs. The heuristics used are designed to take advantage of properties of planar graphs, and are able to colour a planar graph very efficiently. Even though it is possible that the heuristic algorithms may require exponential time, empirical studies show that this is seldom the case.

Overall, the heuristic algorithms compare favourably against two exact colouring algorithms, the five colouring algorithm and Brelaz's backtrack colouring algorithm.

Steven Cook

Graph colouring is an NP-hard problem, with applications in timetabling, circuit testing, and compiler optimisation. While the problem can be solved optimally for graphs of up to 70 vertices, larger graphs require the use of an approximation heuristic. Past research has shown that the tabu search algorithm is an appropriate heuristic for this problem.

While the tabu search has been successfully adapted to the problem, little research has been published discussing optimisations to the search. For example, the length and structure of the tabu list are crucial to the performance of the search, yet past papers have advocated setting the length to a small constant without taking into account the attributes of the graph being coloured. This seminar will demonstrate the importance of the tabu list, as well as as well as a simple but effective technique for escaping from cycles and a method of diversifying the search.