480/490 project proposals for 2003

This is a list of suggested project proposals. We invite you to select three that you think will interest you and let us know your preferences on the Project request form by 7 March. Some of the projects are for Cosc480 only or for Cosc490 only. Please keep your choices to the correct paper.

If you have a project of your own you would like to undertake instead, please discuss it with me or one of the staff. In the past we have often created special projects so that students can follow their interests. But you must have the agreement of a supervisor first.

I know it is tedious, but please put the number and title of each of your choices on the form. Numbers alone are too easy to muddle and mistakes can make you miss your first choice.

Geoff Wyvill

## 1       A computational model of visually-guided reaching  (490/480)

##### Alistair Knott <alik@cs.otago.ac.nz>

The project is to build a virtual robot, which can use its arm and hand to reach and grasp a target object which it sees. Below is some background about the project.

When we reach for an object to pick it up, we use several different sources of information to help us.

Most obviously, we use VISUAL information to tell us where the object is and what shape it is. We also use PROPRIOCEPTIVE information from the muscles to tell us where our arm and hand are.

Finally, we need to know what the velocity and acceleration of the hand/arm is. Since we canıt get this information directly from sense data, we maintain an INTERNAL MODEL of the hand and arm, which estimates their velocities and accelerations as they move.

A MOTOR CONTROLLER is a function which controls an agentıs motor system in real time. At each time point it takes the three types of information outlined above, and returns the commands to be sent to the motor system at that point. (See Jordan, 1996 for an introduction to this area.) One very influential model of motor control is a system called MOSAIC (Haruno et al, 2001), which is able to learn a set of different controller functions, suitable for different circumstances (for instance, conditions in which the object is in different locations, or the arm is carrying different tools).

A 480 project would be to reimplement a stripped-down version of MOSAIC, which is able to learn a single motor controller function.

A 490 project would be to reimplement a more detailed version of MOSAIC, which can learn two separate controller functions for the hand/arm: one for when it is carrying an object, and one for when it is moving by itself.

In both cases, the controller would guide the movements of a virtualı robot arm, rather than a real one. It would be very useful if the student doing this project were also taking COSC460 (Neural Networks) and COSC451 (Language and Sensorimotor Cognition). COSC343 (Artificial Intelligence) would also provide useful background for both projects.

Haruno M, Wolpert D & Kawato M (2001). MOSAIC model for sensorimotor learning and control. Neural Computation 13,2201-2220.

http://hera.ucl.ac.uk/sml/publications/papers/HarWolKaw01.pdf

Jordan, M (1998). Computational aspects of motor control and motor learning. In H. Heuer and S. Keele (Eds.), Handbook of Perception and Action: Motor Skills. New York: Academic Press.

http://www.cs.berkeley.edu/~jordan/papers/heuer-keele.ps.gz

2.      A computational model of visual attention  (490/480)

##### Alistair Knott <alik@cs.otago.ac.nz>

The aim of this project is to build a system that takes information about an agentıs visual environment, and decides on a set of hot spotsı in this environment which deserve to be looked at in more detail. Some background for the project is given below.

Even though the human retina captures information from a wide area in the visual field, human beings apparently donıt process all this information simultaneously, in parallel. We perceive the world in a much more directed way, by pointing our eyes at one particular object or place, and ATTENDING TOı this for a small period of time, then moving on to another object or place. These directions of attention are very frequent: we make around 3 of them every second, throughout our waking lives. If this is the way we sample the visual array, the question arises: HOW DO WE DECIDE WHAT TO ATTEND TO NEXT? We clearly have to make this decision before performing any actions of attention. (Otherwise we beg the question of how we decide to perform these subsidiary actions of attention!) It seems as though there is a process that operates in parallel across the visual field, which computes for each point in the field how SALIENT it is, based on very simple information about the contrast at this point, or the motion energy. This information is gathered together into a saliency mapı of the visual field. At any point in time, the most active point in this map determines whereabouts the agent attends to next. For a review of this idea, see Mozer and Sitton (1998), or Itti and Koch (2000) for more detail.

A 480 project would reimplement Itti and Kochıs model of the saliency map. The input of the system would be a visual image (either a real photograph, or perhaps a line drawing, depending on the emphasis the student wants in the project). The output of the system would be a ranked list of points within this image, in order of decreasing salience. The aim of the project would be for this list of points to roughly correspond to the order in which a human being would fixate points in the image. However, there wouldnıt be time to evaluate the model formally, so an intuitive idea about the most salient objects in the scene will be employed to give a rough idea of the systemıs success.

A 490 project would reimplement Itti and Kochıs model as for the 480 project, and also to investigate how this model can be used within the visual object recognition system. Briefly, the idea is that the object recognition system ends up working out information about WHAT KIND OF OBJECT is in the visual field at any given point in time, but throws away information about WHERE the object is. Unless attention is focussed in a particular location by the saliency map, the object recognition system can be confused, and combine information about several distinct objects at different locations in the visual field. (See Mozer and Sitton, 1998 for a good introduction to this topic.) The system to be built for this project would take as input an image, and as output execute a series of directions of attention to points within this image, controlled by the saliency map, with a simple object recognition algorithm being executed at each point.

It would be very useful if the student doing this project were also taking COSC460 (Neural Networks) and COSC451 (Language and Sensorimotor Cognition). COSC343 (Artificial Intelligence) would also provide useful background for both projects.

Itti L and Koch C. A saliency-based search mechanism for overt and covert shifts of visual attention. Vision Research 40(10-12):1489-1506. http://iLab.usc.edu/publications/doc/Itti_Koch00vr.pdf

Mozer, M. C., & Sitton, M. (1998). Computational modeling of spatial attention. In H. Pashler (Ed.), Attention (pp. 341-393). London: UCL Press. http://www.cs.colorado.edu/%7Emozer/papers/attn_modeling.html

3.      A computer-aided tool for teaching conversational Maori  (490/480)

Alistair Knott <alik@cs.otago.ac.nz>

Thereıs a large project under way in the AI lab at the moment to build a MACHINE TRANSLATION system, that takes a sentence in English and returns a translation of the sentence in Maori (or vice versa). Our aim is eventually to embed this system in a computer tool to help people learn how to speak Maori. A succession of students have been working on this tool. You can see a couple of prototypes at:  http://tutoko.otago.ac.nz:8080/teKaitito/.

Currently, we have two systems. One system is a straight sentence translation tool. Another system allows the user to enter into a DIALOGUE with the computer. The user can tell the system facts, either in English or Maori. The system responds with acknowledgements, if it understands the user, or with follow-up questions or error messages if it doesnıt understand. The user can also ask the system questions him/herself. (At the moment, s/he can only ask the system about things that s/he has already told it, which is a bit of a drawback.) Thereıs a summary of both systems in Knott et al (2002).

The aim of the project is to build a prototype language-teaching system on top of the current dialogue engine. In this system, the computer will play the role of a Maori language tutor: it will tell the user a simple story, and then ask the user questions, to ascertain whether the user has understood the story, and to check the correctness of the userıs responses. Many of the low-level components of this system are already in place. We already have fairly sophisticated grammars for both English and Maori (although their syntactic and lexical coverage is still very small). We also have a module for telling stories (built last year by another 490 student). We also have a method for detecting various different kinds of grammatical mistakes in Maori (or English, for that matter). And we also have coreı a dialogue engine (also built by one of last yearıs 490 students, during his spare time). The aim of current project is to concentrate on implementing various high-level TEACHING STRATEGIES. The system might have a high-level goal to make the user understand a particular syntactic construction, and design a set of questions with this goal in mind. If mistakes are made, the system should respond with helpful points. NOTE: you donıt have to be a Maori speaker to do this project! All of the work will be at a fairly high level of abstraction, dealing with how to build a system that can implement a certain kind of dialogue-based teaching strategy.

A 480 project would build a simple teaching strategy with a single fixed goal: for instance, to teach the user about the word order or Maori sentences.

A 490 project would build a set of teaching strategies, with different sets of stories and tutorial questions for different educational goals.

A Knott, I Bayard, S de Jager and N Wright: An architecture for bilingual and bidirectional NLP. Proceedings of the 2nd Australasian Natural Language Processing Workshop, Canberra Australia pp63--70, December 2002 http://www.cs.otago.ac.nz/staffpriv/alik/papers/tk-anlp.ps.gz.

4.      Temporal logic  (490/480)

There are a number of choices one has to make if one intends to model a system whose state can change with time. One of the choices is whether to use a temporal or a dynamic logic. If a temporal approach is chosen, then one has a choice between a first-order or a modal language. Whichever type of language is selected, one has a choice between using instants or intervals. And so on. The purpose of this project is to gain an overview of and familiarity with the range of approaches that are available. You would start with some directed reading, compare approaches and report on your findings.

5.      Logics of belief  (490/480)

Willem Labuschagne <willem@cs.otago.ac.nz>

Since Plato, philosophers have regarded knowledge as beliefs that are true and that are in some sense justified rather than being true merely by accident. Logics of knowledge (epistemic logics) are well-understood and involve modal languages having a particular kind of semantics. There is far less agreement on how to model agents who have beliefs that may be mistaken (i.e. false). The purpose of this project is to gain an overview of and familiarity with the range of approaches that have been proposed for logics of belief (doxastic logics). You would start with some directed reading, compare approaches and report on your findings.

6.      Affective computing  (490/480)

Willem Labuschagne <willem@cs.otago.ac.nz>

Affective computing can mean either of two things. It can refer to the recognition of human emotions by software (as in the work of Rosalyn Picardıs lab at MIT on user interfaces) or to agent architectures that include emotion-analogs that play a role in the decision-making of the agent. I am interested in the latter. The purpose of this project, which might properly be described as a project in Cognitive Science, is to distill from the literature in cognitive psychology a coherent picture of the role played by emotions (i.e. affectı) in human thinking and decision-making. It may be possible to restrict the scope of investigation to certain basic emotionsı, but this will have to become evident as the study progresses, because one of the things to establish is whether or not the evidence suggests that humans have a set of basic emotions. In order to further restrict the scope, I would suggest that emphasis be given to the effect of emotions on categorisation and defeasible reasoning. This is a very open-ended investigation and it is not easy to predict what may emerge from it.

7.      Networking simulation in Linux Kernel  (490)

Zhiyi Huang <hzy@cs.otago.ac.nz>

The project aims to implement a networking simulator (by modules) inside the Linux Kernel. The simulator will provide real network interfaces without involving hardware. It will be used as a platform for students to practise implementation of networking protocols such as TCP/IP in advanced networking papers. The project requires only the simulation of unreliable point-to-point connection in Ethernet.

The implementation will start with a working Linux driver program (module). It is (must be) written in C. The issues in the project include programming in Linux kernel, asynchronous I/O, and conceptual design of the networking simulator.

This project is a good starting point to understanding Linux kernel, network drivers and API for the I/O subsystem. It is both challenging and fun.

8.      Anatomy of Linux networking source code  (490)

Zhiyi Huang <hzy@cs.otago.ac.nz>

After studying the source code, write a detailed report on the structure of the source code, description of important functions and their relationship, so that interested developers will be able to extend, adapt or revise the source code for other purposes.

9.      Parallel programming over cluster computers  (490)

Zhiyi Huang <hzy@cs.otago.ac.nz>

If you have a time-consuming computational problem, bring it over to our cluster computers (networks of up to 32 PCs). You will be able to parallelize the problem with tools such as Message Passing Interface (MPI), Parallel Virtual Machine (PVM), and Distributed Shared Memory (DSM). Your parallel programs will be used as benchmarks to measure the performance of the above parallel programming tools over cluster computers.

10.    Equilibria for knowledge games  (490)

Hans van Ditmarsch <hans@cs.otago.ac.nz>

In a knowledge game a number of cards is dealt to a number of players. Game actions consist of either questions and answers about cards, or announcements about winning. An example of such a game is Cluedo. Even though the question of how to model game states and game actions is fully answered [Hans van Ditmarsch, Knowledge games, PhD thesis, Groningen, 2000], it is not clear what the optimal strategies are for playing knowledge games. A strategy for a player is a sequence of choices of actions for every conceivable game state that may occur. Knowledge games are games of imperfect information, where strategies are likely to be mixed. That means that a strategy could be to ask either question A or question B but with a known probability of choosing A or B. The goal of this project can be stated as follows: find two non-trivial game actions, for which you can determine which of the two is to be preferred. In terms of Cluedo: is it better to ask Scarlett did it in the kitchen with a knifeı or Green did it in the library with a ropeı? This seems trivial, but, I assure you, is not so. A more ambitious goal is to determine this for two arbitrary game actions. And an even more ambitious goal is to determine optimal strategies for playing knowledge games.

Work in this area would include a substantial familiarization with literature in game theory (microeconomics).

11.    Public communication of secrets  (480)

Hans van Ditmarsch <hans@cs.otago.ac.nz>

Consider the following ³russian cards² problem: ³From a pack of seven different cards, two players each draw three cards and the third player gets the remaining card. How can the players with three cards openly communicate each other all their cards without the third player learning from any of their cards who holds it?² This problem has been exhaustively investigated, which culminated in [Hans van Ditmarsch, The Russian Cards Problem, to appear in Studia Logica], see my homepage. There are 102 different solutions. Mike Atkinsonıs theory group intends to investigate generalizations of this problem in this semester, i.e. semester 1 of 2003.

The formulation of a more general problem is known: for which card deals can to players communicate their hands in this way? As are the precise constraints that a solution should satisfy. The project is to compute solutions for other cases, and/or even to find all solutions for those cases, preferably by an implementation.

This project does not have any course prerequisites, but requires of course programming experience. You may use the programming language of your preference. My help consists in analyzing the algorithms you try to implement. I can probably only help you out with details of the programme IF the language is Prolog or functional. This is a very workable project, ONLY available as 480, and can be finished with any amount of found results.

12.    Logical dynamics of your favourite game  (490)

Hans van Ditmarsch <hans@cs.otago.ac.nz>

Various card games involve moves where facts (such as people holding cards) do not change but knowledge about the facts does change. As part of my PhD research I described the game of Cluedo, to which purpose I developed a generally applicable language for logical dynamics. Various other games, in particular card games, and also various other multiagent systems (such as those involving security protocols) can be described with this language. For example: the family game, memory, ... Choose a game, or multi-agent system, and provide a full logical specification, including the dynamics. The real challenge is to come up with a good example yourself of sufficient depthı: it is likely I am unaware of actually very suitable examples and games. The topic of this project is rather open and more practical than theoretical.

This requires working knowledge of logical knowledge representation, as taught in the papers Artificial Intelligence and Applied Logic. The last course (paperı) is a must.

13     Creating real-time shaders for realistic facial animation  (490/480)

Scott King <sking@cs.otago.ac.nz>

With the development of Cg and fast graphics hardware, it is now possible to create extremely fast shaders for increased realism of computer graphics. Writing these shaders will be a very good skill for those wanting to enter the entertainment and game industry.

The goal of this project is to produce shaders to increase the realism of our facial animation system.  We currently have the start of a skin shader.  This project will start by continuing development of that shader.  Shaders for the lips, eyes, tongue and hair will also be required.  Another aspect of this project may include writing equivalent Renderman shaders.

Cg is shader language very similar to C developed by NVIDIA that allows the use of the powerful GPUs in graphics cards. http://developer.nvidia.com/view.asp?PAGE=cg_main

This project requires a good understanding of computer graphics.  COSC342 or the equivalent is necessary.  As well, you should probably be enrolled in COSC455.  Our system runs under linux, but it is possible to develop the shaders under windows.  This project does not require any research, but research is certainly possible.  However, it will be necessary to be able to read and implement research papers.

14.    Motion capture  (490/480)

Scott King <sking@cs.otago.ac.nz>

I have performed several motion capture sessions of speech and facial animation motion.  This data includes several session of several individuals performing a variety of expressions and utterances.  The goal of this project is to process this data in order to extract a mathematical model of the facial motion involved in speech.

Motion capture can provide some wonderful data for study, but it is by no means a magical bullet.  The data tends to be quite noisy and occasionally markers go missing for several frames of data.  In order to use this data, it must be filtered to remove the noise and reconstruct the missing information.

The motion capture data consists of the 3D locations of markers that are placed upon the subjectıs face.  The captures consist of between 40 and 80 markers.  The location for each marker is determined at 120 times per second. The markers are placed on important locations on the face in order to extract both the rigid and non-rigid motion that occurs.  The subject perform facial expressions and well as certain utterances.  Some of the captures have corresponding video.

This motion capture data can be used to drive the deformation of a completely different facial mesh.  We are developing techniques to use radial basis functions for this purpose.

We can also extract model parameters for our parametric facial model.  By using optimization techniques we can determine what the model parameters need to be, in order to have the shape deformation of our facial model that we see in the motion capture data.  By doing this for each frame we get motion curves for out facial model parameters.  By studying these parameter curves, we hope to create a mathematical model of speech and facial expressions.

This project is to support active research.  Work on this project can be just the processing of the data or also on the research end.  C/C++ and or Matlab and a decent understanding of maths is required for this project.

15.    Subdivision surfaces  (490/480)

Scott King <sking@cs.otago.ac.nz>

Catmull-Clark subdivision (as well as Doo-Sabin) allow one to define a smooth surface with just a few control points.  These surfaces can be easy for a modeller to define complex organic shapes quickly.  A common method is to subdivide some number of levels and represent the shape as triangles instead of as the limit of the subdivisions.  The limit surface can be calculated and rendered, but this is expensive.  Subdivision surfaces are becoming a very popular method for modeling, particularly for the entertainment industry.  For example, Weta switched to subdivision surfaces after the first LotR movie.

I would like to investigate the use of subdivision surfaces in facial animation.  There are two parts to this project.  The first is to implement subdivision surfaces, most likely in OpenInventor, but a strict OpenGL implementation is possible.  The second would be to then apply subdivision surfaces to facial animation.

Implementation of subdivision surfaces is not a very difficult problem.  In fact, it will be quite easy to find code on the net to do this.  There will be a bit of effort in making the code usable in our facial animation system. Then there is the possibility of modifying our facial model to take advantage of subdivision methods.  The basic concept is that as the face deforms, in order to create the correct shape, it may be necessary to locally add complexity to the facial geometry in order to create realistic facial motion. There are many ways to go with this project.  One is strictly for realism and the other is to consider computational complexity. So for computation reasons, this added complexity may also need to be removed once it is no longer necessary.

16.    Classifying Thai burial pots  (490)

Chris Handley <chandley@cs.otago.ac.nz>

I have a CD from Professor Charles Higham of the Department of Anthropology containing 300 photographs of burial pots that have been excavated from the site of Ban Lum Khao in Thailand. Some of these have been classified into a number of groups by a PhD student, however any manual system of classification is idiosyncratic and often breaks down as new data are found. For this project you would be expected to research different methods of classifying objects in general and to devise a scheme that could be applied to the current data set, but that should be robust to expansion of the data set. The results of this classification could be compared with the previous classification.

In addition to, or as part of, this task, we would like you to investigate ways of parameterising the shapes of the pots, so that we can fill in missing or broken bits. This parameterisation could also be used to explore the spaceı of possible pot shapes.

17.    Text in images (2 projects)  (490)

Chris Handley <chandley@cs.otago.ac.nz>

For most of us vision is the primary source of information. Furthermore, in the developed world, an enormous amount of information about the world around us and our place in it, is encoded as environmental text (street signs, bus stops, opening hours for libraries, museums and shops, restrictive notices, and so on), not to mention the enormous amount of information on products, food items and in books, magazines and the like. The problem is that most of this information is inaccessible to people with impaired vision.

The ultimate goal of this project (to be run in collaboration with Information Technology department at Otago Polytechnic) is to produce a device that will readı such environmental text to visually impaired people.

Project 1 involves collecting images of the real world that may or may not contain text (I have access to a set of images to start you off) and to devise methods to select areas that are very likely to contain text. I have a set of references on methods for doing this, and you will be expected to use these as a starting off point for a comprehensive literature search. Note that your application should, ultimately, run in real time, so any proposed method should be capable of being speeded up to achieve that goal.

Project 2 involves taking regions of images identified in project 1 as probably containing text, (you may have to fake this to start with) and applying an optical character recognition algorithm to it to extract the actual text. Bear in mind that the text will be in a variety of fonts, in a variety of colours and against a variety of backgrounds, and will almost certainly not be square onı to the camera. Your task will be to find an algorithm, either off the shelfı or of your own devising that will perform well under these conditions, for instance, you may need to include a dictionary to assist with guessingı words when parts are obscured.

18.    An XML Query language  (490)

Nathan Rountree <rountree@cs.otago.ac.nz>

XML (eXtensible Markup Language) describes a method of adding extra information to documents by adding special tags, <foo>like this</foo>.  It has become very popular, to the extent that HTML (the markup language for the Web) has now been replace by XHTML (an XML version of HTML).  Some people like to think that XML turns documents into databases, which suggests that you should be able to query them with an ad hoc language such as SQL.  Unfortunately, the only current candidates for an XML query language are large, unwieldy, and extremely difficult to use.  If you do this project, you will review other attempts at an XML query language (particularly XSLT, the ³official² way of transforming XML documents), and devise a cut-down language that is more useful for everyday purposes.  It would be nice if the new language could be used in a matter of minutes by a novice.  It would be very nice if you could produce a simple implementation of the new language to demonstrate it in a real-life application.

Goals:

You will have to learn a lot about XML, which is very useful from a practical point of view.  Other things to get a good grip on would be query language design (at least enough to appreciate why XSLT is so awful), and how to get a small (not necessarily efficient) implementation of a query language working quickly.  All the usual 490 skills of reading, research, comparison, evaluation, and presentation would be expected.

19.    A software tool for qualitative text analysis  (480 / 490)

Nathan Rountree <rountree@cs.otago.ac.nz>

There is a piece of software called NUDIST, which people use to analyse pieces of text.  It allows the researcher to mark keywords and tell them how many times those words are used, in what context, and lots of other stuff.  Its document format is proprietary (so you canıt use other software to analyse a marked-up NUDIST document) and some humanities researchers donıt much like the way it works anyway.  If you do this project, you will work out the essential features of a textual analysis program and build one that uses something like XML to store the document.  A working prototype would be the main goal of the project, along with a report explaining what design decisions you made and why.

Goals:

You will put into practice quite a few of the software engineering and user-interface design skills that you have picked up in your first three years.  Some knowledge of XML will need to be developed, but this is secondary to the requirements analysis for the program.  The document explaining the design rationale is at least as important as the program itself.  A short user manual would be necessary if the project is continued all the way through to implementation.

20.    Models of Saccade-Vergence interactions for robotics  (490)

Simon McCallum <simon@cs.otago.ac.nz>

With two eyes there are two types of tracking behaviour, saccade where both eyes move in the same direction and vergence where they move in opposite directions to focus on an item.  There has been extensive work on models of vergence and saccade tracking.  This project will involve researching these models and implementing at least one of these on Theseus (our robot with two cameras, each mounted on a pan/tilt base).  This project would suit a student with a reasonable background in psychology, neuroscience, or physiology.  There will be both low level programming of pick controllers and high level modelling.

21.    Optimizing shipping routes using GPS data  (490/480)

Simon McCallum <simon@cs.otago.ac.nz>

A local trucking firm has approached us to help create a competitive edge by optimizing their shipping routes.  The project will involve installing and collecting data from GPS units.  The project will involve some data mining to find the paths that are most efficient in terms of distance, time, and or profit.  For this project the student will produce a commercially usable program with a user interface designed in association with a business.  This is a 480 project as the main focus will be on the development of program for the user. There will be some research into optimization strategies and traveling salesman type problems.  This project will give the student real world experience in a growth area of geographic information systems.

22.    Aerial sensor and motor integration  (490/480)

Simon McCallum <simon@cs.otago.ac.nz>

As part of our Autonomous Aerial Vehicle project we need to incorporate several sensors including GPS, digital compass, attitude sensors, accelerometers, etc.  The data returned by these sensors will need to be interpreted and combined for presentation to a flight controller.  The controller will be developed by a Masters student during the year.  This project will work closely with the Physics department and the student should have a solid background in Digital and Analog electronics.  The project will also include the construction and programming of PIC controllers for servo motor for our model aircraft.  The amount of work required can be altered to fit either a 480 or 490.  The 490 project would include more research into the fusion of the sensors to improve performance.  For example, the use of attitude sensors and accelerometers to improve the accuracy of the GPS response.

23.    Longest increasing sequence algorithms  (490/480)

Mike Atkinson <mike@cs.otago.ac.nz>

The longest increasing subsequence of a list of length n can be found by a O(n log n) algorithm (and has recently found application in genome studies).  There is a very recent algorithm, as yet unimplemented, that purports to solve the problem if the original list is thought of as circular (as happens in bacterial genomes). The project is to implement this algorithm and use it to study the expected length of a longest increasing subsequence in the circular case.  In the ordinary case this expected length is around 2 sqrt(n) and has been the subject of over 60 years of research.  The circular case is completely untouched.

Although the algorithm proposed is quite short to describe it is, as yet, not well understood.  So there is a combination of research and practice needed before a good implementation emerges.  You will learn about an interesting area of combinatorics which, possibly, might have important applications to genome analysis.

For those doing this project as a Cosc490, you would study the context of such ³longest-type² problems and investigate the practicality of other proposed algorithms for variant problems.

24.    Grid file indexing of Formula One cars  (490/480)

Paul Werstein <werstein@cs.otago.ac.nz>

Implement a grid file based index for Formula One cars.  Compare its performance parameters to a new type of spatiotemporal index proposed in a recent paper. A data generation program and core database management system are provided. What you have to do - learn about grid files and the new spatiotemporal index. Propose a suitable form of grid file based on the constraints of the data.  Implement the grid file within the database management system.  Perform suitable performance tests.

25.    Load balancing in cluster computers  (490)

Paul Werstein <werstein@cs.otago.ac.nz>

Survey the current state of art in load balancing.  Review literature relevant to load balancing.  Look for any existing implementations.  Determine any special issues related to cluster computers.  Possibly propose a method to monitor and migrate processes in a cluster computer.

Paul Werstein <werstein@cs.otago.ac.nz>

The goal of this project is to be able to migrate a process from one computer to another in a cluster.  It would involve implementing additional Linux kernel system calls to copy the process data out to user space, modify it, and copy the data back to kernel space.  You will have to delve into the Linux kernel, but we have some documentation to assist you.

27.    Biometric Encryption  (490)

Stewart Fleming <stf@cs.otago.ac.nz>

Biometrics are often described as ³perfect² security mechanism.  After all, what could be more secure than using something as a key that you carry around as part of you all the time?  Well, as it turns out, biometric security systems have lots of holes, and there are many misconceptions both about the technology and the level of security that is actually offered.

This project would study the following important areas:

Biometric encryption ­ software and hardware technology combined to offer a greater degree of security for the enrolment, storage and comparison of biometric samples.

Consensual authority ­ the development of protocol/procedure for the acquisition and comparison of biometric samples that preserves the individual right to privacy and provides a framework where individual consent is explicitly given.

Non-repudiation ­ by establishment of a framework where biometric samples are protected and individual consent is given, how ³watertight² can the principle of non-repudiation be made?  That is, to what extent can an individual claim or deny that a biometric sample belongs to them?

This project will combine development of software techniques and use of specialized hardware for the acquisition, encryption, storage and comparison of biometric samples (mainly fingerprints).  The project will also incorporate some degree of consideration of the societal context in which biometric devices are deployed.

28.    Noise synthesis and visual texture  (490/480)

Geoff Wyvill <geoff@cs.otago.ac.nz>

In 1985, Ken Perlin caused a minor revolution in computer graphics with the invention of a fluffy texture known as filtered noiseı. This is easily programmed and enables us to generate a fantastic variety of natural and artisticı textures. But there are some problems with filtered noise. Perlinıs method used too much storage. Methods that save storage tend to be very slow. Why is this?

The basic strategy for making filtered noise is to apply a filter to a grid of pseudo-random numbers.  By using the right kind of Pseudo random number generator and making some low-level optimisation, I have created a reasonably fast implementation see: http://www.cs.otago.ac.nz/graphics/Geoff/NoisePages/Nature.html

But there are good theoretical reasons to believe that a much faster method is possible. Every decent  noise algorithm to date, averages sixty or more random values to get a 3D function. But averages of so many numbers do not vary enough so another function is used to amplify the variation. Statistical theory tells us that an average of seven values is ideal.

The purpose of this project is to study and compare the existing ways of making filtered noise. Then, if possible, devise a method that avoids the gridı of pseudo random numbers and finds a noise value more directly. If this is not possible, perhaps you can find a different kind of function equally useful for creating texture.

29.    Design of responsive user interfaces  (490/480)

Geoff Wyvill <geoff@cs.otago.ac.nz>

You are typing a large document in MSWord and suddenly your keyboard appears to freeze. The program is saving a temporary file. There is a delay of one to ten seconds with no response from the keyboard. Why is this? We have been making real-time responsive systems since the 1960s yet most common software does not operate responsively. Systems that do not respond can cause tension and even injury. Yet there seems to be no agreed way of fixing the problem. In the last fifteen years, machines have got 1000 times faster but the problem of poor response has got worse.

Perhaps there is something within the operating system or perhaps there is a missing principle in the discipline of software design. A few years ago, I designed a protocol whereby every user-event causes instant action and all long operations - saving files or drawing pictures - can be interrupted to permit instant user-response.

The idea of this project is to implement a sample application that guarantees responsiveness and document the strategy. We can test it by building a game or an editor or similar application and get some users to evaluate it.

30.    Analysis of musical form  (490/480)

Geoff Wyvill <geoff@cs.otago.ac.nz>

A few years ago a student in this department attempted to discover what makes a rag sound like a rag by analysing 25 of Scott Joplinıs piano pieces. This was successful in that we found some things we could measure; frequency of chord types for example. But we still cannot recognise even simple musical forms automatically.

The idea of this project is to investigate this problem again from first principles, to survey the literature and find or invent analytical tools. If time permits we could extend the project to attempt to recognise well defined forms like minuet and trio.

31.    XML Query Languages  (490/480)

Richard OıKeefe <ok@cs.otago.ac.nz>

XML is a notation for ordered trees, where a node may have a set of attribute=value annotations as well as a label and children.

XML is used for documents (as in XHTML), for communicating between programs (as in SOAP), and for representing ³semi-structured data².

There are several query languages for XML, notably XPath (which is part of several Web standards including XSL), XML-QL, LORE, XQL, and one of my devising called XTrack. There are others which might be worth investigating too.

These query languages tend to have bulky and informal definitions. The aim of the project is to improve our understanding of several XML query languages, their capabilities, and differences.

As a COSC480 project: You would read the relevant literature and summarise it in terms of things weıd like a query language to do or be, how well each of your chosen query languages meets these criteria, and a set of sample queries showing how each can be translated into the several languages (especially queries that cannot be translated into some language).

As a COSC490 project in formal methods:

You would try to develop a formal semantics for one query language and a set of sample queries, using the formal semantics and the sample queries to debug each other. (Your formal semantics should use an executable specification language.)

As a COSC490 project in implementation:

You would pick one of the languages and implement it in the programming language of your choice, noting in your report any unclarities in the specification and how you resolved them.

32.    Finding sentence boundaries  (490)

Richard OıKeefe <ok@cs.otago.ac.nz>

A common fault in written and typed text is run-on sentences people just don't know where to end sentences sometimes you think the schools would do something about it.  Fixing this would be a useful thing in a word processor.

Documents in ancient languages were sometimes written without explicit sentence boundaries.  (What does an Egyptian hieroglyphic full stop look like?  There isnıt one.)  For example, I have a machine-readable copy of the Old Testament which is fully morphologically analysed, but there are no full stops in it because the ancient copy on which it is based didn't have any.

The goal of the project is to develop a software component which can find likely sentence boundaries, given text where some or all of the full stops are missing.  The method it uses should not depend on the human language it is applied to.

One general kind of approach to this is to train some kind of statistical model on a corpus of ³full² text and then use it to predict where the boundaries should be in ³unmarked² text. Hidden Markov Models have proven useful for finding boundaries in DNA and for a variety of natural language processing tasks such as part-of-speech tagging.

You would need to read some of the literature on Statistical Natural Language Processing, write your own modelling code or find and modify an existing program, obtain or construct suitable training data and test data, train your model, and test it.  You might have to try more than one approach.

You may use any programming language which you determine to be suitable.  You need not worry about the complexities of Unicode. You may work with English text if you prefer.

33.    Thesaurus Searching  (490)

Richard OıKeefe <ok@cs.otago.ac.nz>

Topic in information retrieval.

Andrew Trotman, who has worked in the Information Retrieval industry, is available to serve as co-supervisor for this and related topics.

Implement and measure the effects of thesaurus search in information retrieval. Several public domain thesauri are available such as UMLS and Rogetıs. How does searching in this way affect precision and recall

You will have to learn about basic information and about thesaurus searching. While you will would extend Andrew Trotmanıs search engine or some freely available engine rather than writing your own, this project will still require a reasonable amount of programming. We have the standard TREC collection of documents and queries with known relevance judgements.

You will design, perform, and analyse a lot of computer experiments. It is not so much the depth of understanding as the amount of labour which makes this a 490 project; insightful analysis of the results is also important.

34.    Have you got the BLAS?  (490/480)

Richard OıKeefe <ok@cs.otago.ac.nz>

Topic in data structures and algorithms

There is a collection of vector and matrix processing procedures called the Basic Linear Algebra Subprograms (BLAS for short). There are three levels: vector operators, vector/matrix operations, and matrix/matrix operations. There is a model implementation in Fortran, and system vendors like Sun, DEC (now HP/Compaq), IBM, and Intel amongst others offer highly tuned implementations for their systems.

The goal of this project is to design, build, and test an object-oriented interface to some subset of the BLAS. Specifically, I would like to be able to call the BLAS from Squeak Smalltalk or GNU Eiffel. Note that the goal is to produce an interface to an existing Fortran or C library, not to re-implement the BLAS.

As a COSC480 project:

You will carry out a design for the level 1 BLAS in both Smalltalk and Eiffel. You will comment insightfully on the effects that differences in the languages have on idiomatic designs. You will construct examples showing the use of your designs. Generating really good designs is harder than you might think, especially as I expect that you will need different designs for the two languages. (What does that say about UML?) Implementation is not required for COSC480.

As a COSC490 project:

You will carry out a design for the level 1 and level 2 BLAS in either Smalltalk or Eiffel, implement your design, and test it. A good test of test cases is an important part of this project; I suggest using SUnit for Smalltalk or EiffelUnit for Eiffel.

The level 2 and 3 BLAS are concerned with several different array representations, this is why doing the level 2 BLAS is harder than just the level 1 BLAS.

Note: This is only four topics from a long list project topics available from Richard OıKeefe. See the full list at http://www.cs.otago.ac.nz/staffpriv/ok/2003.htm