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
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)
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)
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. 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.
See
http://grail.cs.washington.edu/projects/subdivision/ or
http://www.scg.uwaterloo.ca/~hqle/subdivision/ for more information on
subdivision surfaces.
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.
26. Process
migration in cluster computers (490)
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