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 5 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.
Please put the number and title of each of your choices on the form. Numbers alone are too easy to muddle and mistakes could make you miss your first choice.
Michael Albert (malbert@cs.otago.ac.nz)
400 level project coordinator
Alistair Knott (alik@cs.otago.ac.nz)
with
Scott King (sking@cs.otago.ac.nz)
The AI, graphics and vision labs are collaborating on developing an animated conversational agent. The AI lab is building a dialogue system, that allows a user to converse with an agent using natural language (either English or Maori). The graphics lab is building a 'talking head', which can function as the interface for this dialogue system. The vision lab is building a head tracker, so that the talking head can maintain 'eye contact' with the user during the conversation.
The current project is to improve the interface between the talking head and the dialogue system. There are two main things to be done:
(i) Design a markup language for the sentences sent to the talking head, so that head gestures can be synchronised with the sentences which are spoken. There can be different levels of markup: for instance, whole sentences can perform different 'dialogue acts' (e.g. asking a question, answering yes or no, making an assertion, uttering a greeting), or parts of sentences might be associated with actions (e.g. a nod or frown to accompany emphasised words in a sentence). (For a 480 project, a limited set of dialogue acts would be covered.)
(ii) Implement the markup language.
For more information on the talking head, there is a paper at
http://www.cs.otago.ac.nz/staffpriv/alik/papers/casapaper.pdf
and a demo at: http://www.cs.otago.ac.nz/staffpriv/sking/Kare/
Alistair Knott (alik@cs.otago.ac.nz)
This project is to implement a neural network model of visual object categorisation. According to this model, the categorisation system works by parsing the visual field into very simple visual features, and then progressively combining these features into complex combinations of features. To prevent a combinatorial explosion of combinations, units which encode feature combinations become progressively insensitive to the location of these combinations, so that the units which finally encode what type of object is present abstract away completely from whereabouts on the retina the object is. This model agrees with a number of experimental observations about the human object recognition system. For more information, see here:
http://riesenhuberlab.neuro.georgetown.edu/hmax/
The project will involve a literature review of papers about object recognition, and then the implementation of a specific model. This implementation may involve an extension of some existing Java code produced in the department. COSC343 would be a useful background, and taking either COSC453 or COSC460 would also be useful.
If taken for a 480 project, the model implemented would have to distinguish between a smallish set of objects - say the letters of the alphabet. For a 490 project, a larger set of more complex objects should be envisaged.
Alistair Knott (alik@cs.otago.ac.nz)
with
Simon McCallum (simon@cs.otago.ac.nz)
In a classic experiment, Gunnar Johansson (1973) attached lights to a human actor's limbs and put the actor in a dark room. If the actor stood still, an observer could not recognise what they were looking at: they just saw a collection of lights. But as soon as the actor started moving, the observer immediately saw a moving person, and recognised the action being performed. This experiment is seen as evidence that the human visual system can recognise actions just using information about the patterns of movement in the image, rather than information about shape or form.
The aim of this project is to implement a model of this mechanism. There has been lots of work in this area, so to start with a review of the literature will be needed. A model will then be chosen to implement. The goal of the project is to build a system that can recognise actions in Johansson-style point-light displays. Some useful software for modelling the early visual system has already been developed by students in the department; the project may well involve extending some of this software. We also have access to the University's "Gollum-style" motion capture suite, which can create point-light displays from arbitrary actions.
For an introductory paper about action recognition, and a demo of a point-light display, see here:
http://www.uni-tuebingen.de/uni/knv/arl/arl-model_bm.html
This project will involve the use of neural networks. COSC343 would be a useful background, and taking either COSC453 or COSC460 would also be useful.
Willem Labuschagne
(willem@cs.otago.ac.nz)
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. The report should constitute an expository survey.
The topic has been the subject of many research papers in journals like Artificial Intelligence, and constitutes a coherent subfield of Applied Logic with links to philosophy, concurrency, and program correctness. A student choosing this topic will become familiar with some of the key papers in this enormous literature. The main purpose to be served by the project is preparation for further research. As for the 480/490 distinction, it is easy to tune this project either by restricting its scope to modal approaches only (COSC480) or by including first-order approaches such as those of McDermott and Allen (COSC490). I do not anticipate that there would be any programming involved. The project would not make sense unless the student enrols for COSC462 as well.
Willem Labuschagne (willem@cs.otago.ac.nz)
Since Plato, philosophers have regarded knowledge as beliefs that are true and in some sense justified rather than 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).
The topic can be given a philosophical flavour inasmuch as it links up very naturally with epistemology. Or the topic can be given a psychological flavour by looking at categorisation and category-based induction. The topic constitutes an important, but somewhat incoherent, subfield of Applied Logic with links to multi-agent systems and agent communication languages. The aim would be to construct a coherent comparative picture by starting from a few key papers and searching outwards from this core. Because of the flexibility of approach that the topic lends itself to, there is no simple way to draw a distinction between the 480 and 490 versions.
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 may seem trivial, but 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. For more information on Cluedo, see
http://www.hasbro.com/pl/page.viewproduct/product_id.9622/dn/default.cfm
The project assumes familiarization with literature in game theory (microeconomics).
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 investigated in [Hans van Ditmarsch, The Russian Cards Problem, Studia Logica, 2003] and also in Mike Atkinson's theory group, the last resulted in various combinatorial generalizations. There appear to be 102 solutions (essentially: two only) for the seven cards problem, but this is not proven. The purpose of this project is to prove or refute that conjecture - preferably by implementing some algorithm that will produce the answer. There may remain time to also investigate some generalizations.
Hans van Ditmarsch
(hans@cs.otago.ac.nz)
In the game PIT, between three and seven players try to corner the market on some commodity, such as barley, corn, etc. It is played with cards, and game actions consist of offers and agreements to swap cards. The first player to collect all cards of a given commodity, wins the game. This game has been investigated for some time by various people in the Information Science department (Stephen Cranefield, Martin Purvis), and I am currently collaborating with them on this issue, for example., we are implementing a simplified version for 12 cards. The goal of this project is to describe a simplified version of the PIT game in precise game theoretical terms and to investigate some simple properties of that formalization. For more information on PIT, see
www.hasbro.com/common/instruct/pit.pdf .
The project assumes familiarization with literature in game theory (microeconomics).
Hans van Ditmarsch (hans@cs.otago.ac.nz)
A refutation tree is a standard two-dimensional representation of resolution derivations. Given a logic program, a computation rule and a goal, different resolution derivations result from selecting different matching clauses in the program. These derivations can be visualized as separate branches in the refutation tree. This process can also be reversed: given an refutation tree where leaf nodes are labelled with either succeed (for the empty clause) or fail, and neither other nodes nor links are labelled, one can construct a program, a computation rule and a goal that match this abstract tree. Thus we can introduce in a visual way basic logic programming concepts such as resolution strategies and finite failure. This might facilitate learning logic programming and Prolog. The goal of the project is to implement a visual tool to derive programs from refutation trees and vice versa, and to investigate some properties of programs sharing the same refutation tree-shape. For more information, see also
http://www.cs.otago.ac.nz/staffpriv/hans/art2003.ps .
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 practice 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.
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.
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.
Zhiyi Huang (hzy@cs.otago.ac.nz)
MINIX is a small, well-structured operating system intended mainly for educational purposes. Since it is small, it could be advantageous to use it for small computer systems such as embedded systems. However, some bits and pieces in the system are missing and need to be added in order to run many serious applications. For example, there is no select system call implemented in the system, which is very important for many network applications such as MPI. You are going to study MINIX and implement the select system call in this project. It is a good chance to learn the real skills of implementing an OS kernel.
Paul Werstein (werstein@cs.otago.ac.nz)
The current socket interface uses TCP/IP as the underlying transport mechanism. A recent MSc thesis developed a kernel-to-kernel message passing system (K2KMP). The goal of this project is to build a socket interface using K2KMP instead of TCP/IP. The project requires some kernel level programming. The research group has some books to guide this effort. We have several machines which we can provide Œroot¹ access to.
A 480 project would implement a minimal socket interface. A 490 project would implement a more complete interface and include some performance testing.
Paul Werstein (werstein@cs.otago.ac.nz)
The department has a cluster of 32 Linux PC¹s. Remote access to the cluster is by way of a gateway machine. The other nodes in the cluster are considered worker nodes. The goal of this project is to be able to monitor processes running on the worker nodes from the gateway machine. In other words, the process should appear to a user as if it were actually running on the gateway machine. The project requires some kernel level programming. The research group has some books to guide this effort.
A 480 project would implement a minimal capability. A 490 project would implement a more complete interface and include significant testing.
Paul Werstein (werstein@cs.otago.ac.nz)
The department has a cluster of 32 Linux PC¹s. Remote access to the cluster is by way of a gateway machine. The other nodes in the cluster are considered worker nodes. 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. The project requires some kernel level programming. The research group has some books to guide this effort.
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.
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 sped 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.
Brendan McCane (mccane@cs.otago.ac.nz)
This project involves the creation of a virtual room or virtual world which contains interacting autonomous virtual characters. The characters in the world should:
· interact with each other in a natural way most especially through sound and vision (or simulated versions of each).
· be autonomous and intelligent. That is be able to adapt their behaviour according to stimuli from their environment.
As envisaged the project involves a synthesis of computer graphics and artificial intelligence techniques. Initially it will involve a review of already existing tools such as appropriate rendering engines, avatars, speech/sound generation and understanding etc. The major programming effort initially will involve bolting together these various tools to produce a prototype environment. This project is very open-ended and the student will be encouraged to pursue it in the direction that most interests them.
Brendan McCane (mccane@cs.otago.ac.nz)
The watching window is an unencumbered virtual environment where the view of the world that is seen is determined by the eye position of the user. In the current implementation the eye position is estimated based on a reasonably accurate determination of the user's head position. To improve the faithfulness of the user experience, we wish to improve the accuracy of the eye detection process. Such a project involves two main challenges. Firstly, given an off-centre view of a person's head, can their eye position be accurately determined regardless of the person's appearance (eg if they are wearing glasses)? Secondly, can we detect the eyes at frame rate speeds?
Initially, this project will involve a review of the current state-of-the-art in eye detection and a familiarisation with the watching window code base. The second part of the project will involve choosing and implementing a current eye-detection algorithm or developing a new algorithm for the task.
For a 480 student, investigation of one technique should be sufficient. For a 490 student, it is expected that two techniques will be investigated. It is expected the student will be enrolled in Computer Vision.
Brendan McCane (mccane@cs.otago.ac.nz)
I currently have a project in conjunction with the Anatomy Department for taking measurements from x-rays of the lumbar spine. In its present state, the project requires the user to outline each vertebra using a simple spline editor. We would like to automate or semi-automate this task. A well established technique for performing this kind of task is called deformable templates. The idea is that you have a base shape and various modes of allowable deformation and you automatically deform the base shape according to the information contained in the image. The project will consist of implementing the deformable templates technique and testing it on example x-ray images.
Depending on the outcome, we would like to investigate if the method can be modified to allow for some user interaction by, for example, allowing the user to modify the base shape according to the allowable deformations.
For a 480 project, it is expected that just implementing and testing the deformable templates method will be sufficient. For 490, either further investigation involving user interaction as described above, or the investigation of more recent techniques, will be required. It is expected that the student will be enrolled in Computer Vision.
Nathan Rountree (rountree@cs.otago.ac.nz)
Neural networks can provide remarkably accurate models that map features to an output variable. However, to achieve decent accuracy, a network must be exposed to training examples over and over again. I have come up with a fairly reliable way of transforming statements of fact into networks that behave as if they "know" things before you start training them. Those networks train much more quickly, since they are already close to the best accuracy they can achieve. What I'd like to know is, what happens if we start off a network with knowledge that is incomplete or unsure? Does the (correct part of the) initial knowledge get destroyed during training? Is the network helped or hindered by this sort of information?
By the end of this project, you would have a strong grounding in machine learning, both from a symbolic and connectionist viewpoint. Since this is a fairly active research area, I would expect any interesting results you get to be publishable in an academic conference or journal. Since this topic will require strong research methodology, I would consider it only appropriate for 490.
Nathan Rountree (rountree@cs.otago.ac.nz)
We have access to several large and interesting databases for instance: the History Department's Caversham Project database, which is full of social and economic data from about 100 years ago; and the Otago Graduate Destinations Survey database, which contains decades of more recent social and economic data. There are many patterns that may (or may not) be hiding in such databases; this is a project about identifying the types of pattern that may be of interest, finding instances of those patterns (or evidence of their absence), carefully drawing inferences from those patterns, and reporting on the whole thing in a coherent manner.
The main output of this project will be a report on the database of interest. How far you will ³dig² will depend on whether you do it as a 480 or 490 project. If you dig up something interesting (and express it sufficiently well), there are many avenues for publication of the results. An aptitude for data mining, and the clear writing that must attend it, will stand you in good stead in industry, scientific computing, business research, or post-graduate study.
Nathan Rountree (rountree@cs.otago.ac.nz)
Cluster analysis is a technique used in data mining to help determine whether there are distinct groups of items in a database. The basic idea is to start with one object, then find the closest object to it, then the next, and so on. If the ³next² object is ³farther away² than most objects of any current group, start a new group. This is great when all the features of your database are continuous (such as time and distance) but not so good for categorical attributes (what is closer to a Ford: a Buick or a Chevrolet?). Recently there have been several attempts to come up with good ³distance² metrics for categorical data. In this project, you will implement and compare a few of them, and assess their utility.
Although the research methodology needs to be very tidy for this project, it can easily be limited in scope to suit a 480 project. For a 490 project, I would expect to see a greater command of the literature, and more detailed comparison of metrics. In either case, there is a great deal of interest in the development of these techniques in the data mining community, so there would be opportunity to publish sound results. At the end of this project you would have a good grasp of unsupervised machine learning techniques, experimental method, and the use of a modern statistical analysis package.
Mike Atkinson (mike@cs.otago.ac.nz)
Suppose we are given some objects (from a totally ordered set) that we wish to sort but we also want to exploit any previous knowledge about their order (e.g. we might know that X is greater than both Y and Z and that Y is less than W). How difficult is it to sort the objects if we are only allowed to make comparisons between them?
One way to measure this difficulty is to count the possible orders compatible with what we initially know (for the example these are YZWX, YZXW, ZYWX, ZYXW, YWZX, 5 in all). Computing these counts is not easy for large numbers of objects in that it is known that an efficient algorithm is very unlikely to exist. Nevertheless, there are some situations where specialized algorithms work well in theory (although some have never been implemented). One strand of the project is to implement these. Among other things that will require the design of a data type that represents partial order information so that previously computed results can be re-used. Another is to use these counting techniques to work out an optimal sequence of comparisons to sort the objects. Yet another is to produce a GUI that will allow users to specify the given order relation in a visual way, integrated with the counting tools.
Some mathematical experience would be useful but no specific knowledge is necessary.
Simon McCallum (simon@cs.otago.ac.nz)
We have a project working on creating a fully autonomous unmanned airplane. This project will continue the work of a Master¹s project which is near completion. For a 480 project merely drawing together the different components with a full writeup will be necessary. For a 490 additional control structures must be added as well as building a platform for sensor expansion.
Simon McCallum (simon@cs.otago.ac.nz)
I will look to take applications for working as a computer game design team. This project will only run if I am convinced of the ability and desire of every team member to work on the project. This will be a group of 3-4 people working on developing a computer game. Each member of the group will be co-supervised with other members of the department on specialist areas, for example networking, graphics, etc.
Simon McCallum (simon@cs.otago.ac.nz)
Using cameras mounted on rotating mounts you will investigate vergence actions to focus two cameras on a single location, as well as actions related to saccade movements to the periphery of the visual environment. This will be a difficult project as it requires a knowledge of both low level driver control as well as high level vision.
Scott King (sking@cs.otago.ac.nz)
Speech generation has improved greatly in recent years. One area where advancements have been and still need to be made, is in prosody - the meter of the speech (prosody includes other parameters). For this project you will modify Festival - a freely available text-to-speech system - to read poetry in various styles, (for instance iambic pentameter).
For this project you should enjoy reading and reciting poetry. The project will require code in Scheme and possibly C++. Knowing Scheme or lisp will certainly help but is not a strict requirement. For a 490 more styles should be handled.
For this project you should enjoy reading and reciting poetry. The project will require code in Scheme and possibly C++. Knowing Scheme or lisp will certainly help but is not a strict requirement.
Note: For this, and other projects supervised by Scott King, owing to special circumstances, you must get approval from Scott before choosing one of his topics, and the workload may be heavier in Semester 1 than Semester 2.
Scott King (sking@cs.otago.ac.nz)
and
Brendan McCane (mccane@cs.otago.ac.nz)
with
Alistair Knott (alik@cs.otago.ac.nz)
We currently have a prototype system that incorporates the research of the supervisors. When finished the system will allow someone to interact with a 3D talking character with hand gestures and speech. This project involves getting software from many different sources and getting it to work together.
There will be software installation and integration, software evaluation, scripting and some development. Currently the system does rough head tracking and the user can type in text and the system speaks back to the user.
Speech recognition is the highest priority. After that: gesture recognition, personality, expanded vocabulary, environmental awareness, and prosody/emotion are next. The student will be able to choose which areas to work on. Being able to search the web and find and implement technology is a must. Coding from scratch and researching new techniques need not happen, but can if desired.
Scott King (sking@cs.otago.ac.nz)
For this project you will implement various shaders on the GPU using Cg. Current programmable GPUs give incredible performance and high quality. Using a high-level language such as Cg allows more rapid development of advanced rendering techniques. This project will involve writing shaders primarily to support facial animation, but there is room for other options. For this project you must have a good understanding of graphics, particularly rendering and decent math skills.
Scott King (sking@cs.otago.ac.nz)
I have several projects in computer graphics, primarily in facial animation, that can be worked on. Topics such as hair modeling and rendering; facial modeling (creating specialized models that are capable of realistic animation and rendering for the eyes and skull, and modifying existing models for the lips and tongue); facial animation in games; adding emotion and prosody to synthetic speech; motion capture processing; tree rendering; and fire rendering are possible.
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.
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.
Richard O¹Keefe (ok@cs.otago.ac.nz)
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 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.
Richard O¹Keefe (ok@cs.otago.ac.nz)
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: These are only four topics from a longer list of project topics available from Richard O¹Keefe. See the full list at http://www.cs.otago.ac.nz/staffpriv/ok/alltop04.htm
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.
A start was made by a student in 2003 but there is still much to do on this topic.
Geoff Wyvill (geoff@cs.otago.ac.nz)
There are about twenty established commercial programs that operate as Œword processors¹ for musicians to prepare musical scores. They vary greatly in price and in capability. The idea of this project is to make a detailed comparison of some of these systems and, at the same time, to discover what is important to make such a system convenient for the practising musician.
Part of the problem is that it can take several weeks for a beginner to become an effective user of some of these systems. By that time, most people have developed a strong desire to continue working with the system they know even when it may be far less capable and convenient that one of its cheaper competitors.
A good start has been made over the summer vacation. About six systems have been compared and the report of this work will be available as a starting point.
My long-term goal is to create an open source music scoring system that will outperform all of the commercial systems. But first we must find out what is truly useful.
Geoff Wyvill (geoff@cs.otago.ac.nz)
The Watching Window is an experimental virtual reality display that has been built by the Graphics and Vision research group. It consists of a rear projection screen and a number of TV cameras that can track the hands and eyes of the user. We have demonstration programs that provide various different experiences. We have a simple window where the user can enjoy the view. By moving the head, you see different parts of the scene as you would through a real window. We have a space invader style game where you have to dodge rocks that are aimed at your head. And we have a painting program that lets you daub the screen with virtual paint. The idea of this project is to propose and create an interesting activity to demonstrate the watching window.
Geoff Wyvill (geoff@cs.otago.ac.nz)
Auto-stereograms are pictures that can be viewed as 3D or 2D images. They depend, for this effect, on an implicit knowledge of the 3D structure of objects portrayed. Mostly they are used to represent stylised objects that have been created as 3D computer models. But all the information needed to create an auto-stereogram is inherently contained in a stereo pair of photographs of any natural scene.
This project is to devise software or a process to make auto-stereograms from stereo pairs.
Geoff Wyvill (geoff@cs.otago.ac.nz)
From the World Wide Web you can find thousands of music samples encoded as MIDI files. The MIDI format encodes the notes and timing for an ideal performance of a song or other musical work. But unlike a sound file, MIDI files are short and precise and do not carry noisy or ambiguous information. Thus we have the possibility to write a program that will find the source of a melody or fragment of a remembered tune. The idea of this project is to devise a suitable indexing system to do this job, to implement it and to collect enough Œsongs¹ from the Web to create the beginnings of a musical dictionary indexed by melody.
The project is very open ended. One obvious extension would be to investigate similar tunes and make good guesses where a melodic fragment was entered incorrectly. A basic knowledge of music notation is needed for this project.
Stewart Fleming (stf@cs.otago.ac.nz)
Monarch Wildlife Cruises Ltd are forward planning with the idea of introducing a computer booking system, possibly integrated with their website, and aligned with a laptop computer on board the boat.
In this project you would design and implement such a system. This is a ³hands on² project which involves both technical issues and dealing with a real client.
Stewart Fleming (stf@cs.otago.ac.nz)
Building on the work originally done by Ben Handley on Homage (resource-efficient anonymous group authentication) and subsequent revision and strengthening (Sonil Gohil's summer bursary project), this project aims to provide a robust, wide-ranging implementation of the protocols for authentication without identification and biometric encryption. The end-product of this work is expected to be a software system that can perform end-to-end authentication in a distributed environment that preserves anonymity.
This work could be done as a 480 project, building on existing work. To extend it to a full 490 project, the scope of the work would expand in terms of robustness and deployment of the system on a server basis, for example to provide an anonymous authentication service that would complement existing PKI and digital certificate servers such as Verisign.
Michael Albert (malbert@cs.otago.ac.nz)
Meta-heuristics are generic problem solving strategies designed to provide good approximations to solutions of discrete (or combinatorial) optimization problems. They include genetic algorithms, simulated annealing, tabu search and ant-colony optimization among others. However, code for using these strategies is usually written more or less from scratch each time a new problem is considered. An exception to this rule is GAUL (http://gaul.sourceforge.net/) a library for use in applications involving genetic algorithms.
As a 480 project you would design a general interface to libraries implementing meta-heuristics, and implement a basic instance of such a library for one of the standard meta-heuristics.
As a 490 project, more implementation would be required, together with a deeper consideration in the design phase of efficiency issues (which are quite important, to say the least, in large scale combinatorial optimization problems).
In either case, a supply of non-standard sample problems for testing would be available.
Michael Albert (malbert@cs.otago.ac.nz)
How many ways can a loop of rope be laid across a line on the floor? The, exact or approximate, answer to this question (after defining it carefully) and other questions of the same type are of interest to mathematicians and theoretical physicists. Recent work by Mike Paterson (University of Warwick) and myself has established better bounds on these numbers than were previously known. We combined some novel technical arguments with a moderately large amount of computation to obtain these bounds. The code used was, to be honest, hacked together and has reached the limits of its usefulness. The aim of this project is to improve these results through more effective computing.
As a 480 project the aim would be to work inside the rough framework provided by the existing code, but to attempt to implement some superior algorithms and other local improvements to the methods.
As a 490 project a wider investigation of methods appropriate to this family of problems would be undertaken. This might well include parallelizing the problem and/or making use of ³idle² resources to deal with parts of the problem.
For either version, a certain degree of mathematical sophistication would be desirable (though not essential).
Michael Albert (malbert@cs.otago.ac.nz)
Clobber is an abstract game developed by myself, J.P. Grossman, and Richard Nowakowski in 2001 which has been receiving a significant amount of interest both among combinatorial game theorists, and as a playable game (see for instance: http://www.maa.org/mathland/mathtrek_04_29_02.html). This project aims to produce an effective, sophisticated, interface for playing Clobber, including an AI player,
One of the interesting features of Clobber in this regard is that some quite complex positions can be analysed completely using, for example, CGSuite, a recently released toolkit for combinatorial game theory. An effective AI player should then use a combination of exact and heuristic analysis to prune the game tree effectively. Another feature of Clobber which makes this an interesting task is that, at present, no good heuristic evaluation functions are known.
As a 480 project this is a largely practical exercise. A 490 project would also take on one or more of: consideration of integrating existing software (eg. using CGSuite as a back end to a Clobber player); adding a generic player engine to CGSuite; and dealing with the general question of how best to combine heuristic and exact analysis in a game player.