|
Sidan är under uppdatering. Essay Project ProposalsThemes: Security, protocols and systems, database systems, programming languages, language technology, artificial intelligence, algorithms, computer graphics, simulation, speech and music SecurityTitle: Security Monitoring Theme: Security Subject: Security monitoring is a technique used to enforce security policies, for instance for access control. A very general and flexible approach to security monitoring uses automata to represent security policies. For instance, a security automaton with two states *unchecked* and *checked* can be used to define the policy that boarding of an aircraft should be allowed only after check in has been properly completed. In an ongoing EU project HATS (www.hats-project.org) we are exploring the use of security automata and automata inlining for multithreaded Java and a prototype inliner has been developed. A lot of open ends are left, however, which may be suitable for small student projects. Possible essay projects:
References:
Contact: Get in touch with Mads or PhD student Andreas Lundblad in the theory corridor if you are interested in this line of work. Supervisor: Mads Dam Title: Multilevel secure programming Theme: Security Subject: Many programs need to process data with different security requirements. A webshop, for instance, may need to process data on behalf of customers, payment receivers, and suppliers, with different requirements regarding confidentiality and integrity. In multilevel security data is assigned security levels in some security lattice, and a multilevel secure program must respect this lattice such that data e.g. at a high confidentility level cannot be read by agents at level "public". Several prototype languages such as FlowCAML and JIF have been developed over the recent years to support multilevel secure programming using type systems. A project in the area of multilevel secure programming might experiment with such a language to try it out on a concrete application, or it might document or compare some approaches to multilevel security in the literature. Possible essay projects:
References:
Contact: Seeral researchers in the theory group is currently active in this research area. Talk to a member of {Mads,Gurvan le Guernic,Musard Balliu} if you are interested in joining this work. Supervisor: Mads Dam Title: Proof of work Theme: Security Subject: One way to try to avoid DOS attacks,
brute force attacks or having someone use a mail server for mass email
(SPAM) is to use a proof of work
protocol. Essentially it involves the server not processing a client
request right away. Instead it sends a Study, present and implement a proof of work protocol. Explain assumptions and examine performance. References:
Supervisor: Mikael Goldmann Title: Secure multiparty computation Theme: Security Subject: In the design of secure cryptographic protocols, one important aspect is to define what it would mean for the protocol to be secure — without a definition of security, it is of course impossible to prove that a protocol is secure. The notion of an ideal functionality can be intuitively described by an example. Consider the fallowing sealed bid auction: There is a trusted person to whom all others can send a bid over a secure channel. Once the auction is over the winner is the one who handed in the highest bid, and that person pays the value of the second highest bid. The trusted person announces the winner and the value of the second highest bid amd the bidders do not learn anything else about the other bids. This would be our ideal functionality. Now, let us say that we want to remove the trusted person and instead use cryptography. We then want to prove that the cryptographic protocol behaves the same as the ideal functionality, i.e., that (for all practical purposes) the outcome is the same and the information leaked to the participants is the same. There are a number of frameworks available for implementing secure multiplarty computation. Use one or two to implement some simple examples. Document your examples and the properties of the framework(s). If you look at more than one, then do a comparison on e.g., usability and efficiency. References: Some frameworks Supervisor: Mikael Goldmann Title: Net voting Theme: Security Subject: Most people agree that traditional ballot voting should be replaced by some form of net voting. The security issues have been deterrent so far, but now is the time to present an attractive solution. The goal of the project is to pinpoint the weak points and the fortes of different possibilities and to recommend the ultimate net voting system. Project highlights:
References:
Supervisor: Henrik Eriksson Protocols and SystemsTitle: System Virtualization Theme: Protocols and systems Subject: A hypervisor, or systems virtualizer, is a slim piece of systems software operating directly on top of processing hardware, allowing several guest systems to share a common physical processor. Virtualization is a key enabling technology for cloud computing, but it also is promising for embedded systems, for instance to provide memory separation between an (insecure) operating system implemented as one guest system and a set of security services as another guest system. In a research project currently running as a collaboration between SICS and the theory group at CSC we are developing a hypervisor for the ARM family of processors. In the context of this project it is possible to identify some interesting and challenging subjects that a suitable as essay projects. One topic might be to understand and document the design, and implement some benchmark tests together with the research student Oliver Schwarz at SICS currently responsible for the work. Interested students should get in touch with Mads. References
Supervisor: Mads Dam Title: GPGPU APIs and architectures Theme: Paralell programming Subject: Using graphics cards and APIs, such as OpenCL and CUDA C, for general purpose programming, have in recent years become a cost-effective way to radically improve the performance of many commonly used algorithms. In some cases speed-ups of as much as 100 times have been reported relative to typical CPU implementations. The question is for what applications can you get such speed-ups. For which kind of problems are GPU architectures not at all suitable? Are there any fundamental differences between the GPU architectures from AMD and NVidia, that could explain observed differences in benchmarks? Project ideas:
References:
Supervisor: Mårten Björkman Database SystemsTitle: Building 3D Models of a City Theme: Spatial Databases Subject: The objective of this thesis is to explore different approaches to building 3D models of a city from readily available data sources. The inputs to the problem are: 1) a database of polygons (e.g. from OpenStreetMaps) that represent buildings over the region of interest; (2) height measurements (e.g. derived from LIDAR data) represented as a two dimensional array at a fixed granularity (e.g. every 50cm x 50cm cell) over the region of interest. The output of the problem is a 3D model of some sort that can readily be accessed by first person shooter type engines where building ids can easily be recovered. An additional interesting issue might be investigating how to obtain (or synthesize) textures for the faces of the 3D objects. Preferably the student(s) will implement and evaluate a (partial) solution using real data for an area in Stockholm including the KTH campus. Alternatively the thesis might review various approaches to this problem taken by outside industrial or academic groups. References: Supervisor: Michael Minnock Title: Implementing A View for Visibility in PostGIS Theme: Spatial Databases Subject: Spatial Databases often contain polygons that represent objects such as buildings. Assuming only a 2D representation, how can we define a view for the visibility relationship. That is, given a user (at a known x,y coordinate), how can we define the view canSee(userId, buildingId)? Clearly there are multiple ways to solve this problem. You will define, explore and evaluate alternatives for PostGIS. Time permitting, richer issues like determining the amount of visual angle a building occupies from the user's perspective could be implemented and evaluated. Also given height and elevation attributes for buildings, you could consider generalizing your solutions to 3D visibility determination. Note that we could provide a database containing the polygons of the buildings in and around the KTH campus for benchmarking purposes. References: Supervisor: Michael Minnock Title: Generating Efficient SQL over Views in PostGIS Theme: Databases Subject: Modern databases give us a lot of power to define views. This is especially interesting in spatial databases where we can define views such as 'near to', 'left of', etc. In practice however, these views are not always accessed in the most efficient manner. In fact often the whole view will be needlessly materialized. In many industrial cases this does not have much practical impact. Programmers experiment with EXPLAIN ANALYSE and design an approach that either spreads a complex query over a sequence of queries, or they write the query in such a way that forces order of evaluation via sub-queries. Where this 'hand-crafted' approach breaks down, is when we automatically build SQL from logical expressions (e.g. Datalog). This thesis will explore aspects of this generating efficient SQL in such cases. The student(s) may focus their efforts through benchmarking query performance over the spatial database used in the SpaceBook project. References: Supervisor: Michael Minnock Programming LanguagesTitle: Software model checking using BLAST or SPIN Theme: Programming languages Subject: Model checking is based on the idea of automatically traversing a program execution graph to determine some desired property such as: Is there a way for program line 47 to be executed? Will execution eventually terminate? Does the equation x = y^2 - tmp always hold? Since these problems are generally undecidable, answers cannot be guaranteed, neither can they be guaranteed to be obtainable in reasonable time. Even so, with good engineering and using suitable abstractions, good results can nonetheless often be obtained. Examples of model checkers are BLAST, for C programs, and SPIN which is mainly applied to communications software or protocol modeling. Project ideas: The goal of an essay project on software model checking would be to learn a model checking tool such as BLAST or SPIN and apply it to a selected application. Many examples exist in the literature which can serve a suitable starting points. It would be possible, for instance, to start from a worked example and augment it step by step by adding some additional features. It is important to keep in mind that complexity often increases very quickly, so by adding features simplifications of the existing code/models will very often be needed. So small increments are highly recommended. References:
Supervisor: Mads Dam Title: Call by contract and SPEC# Theme: Programming languages Subject: In the call-by-contract paradigm, methods, objects, and classes are equipped with contracts - formal assertions - that describe how they are expected to behave. For instance, methods may be equipped with pre- and postconditions to determine properties that should be established upon method entry, resp. exit. Much work has been been done to realize such contract-oriented programming frameworks over the past 10-15 years. A well-known example for Java is the Java Modeling Language, JML, for which a number of prototype tools have been developed. See the reference below. Another example is SPEC# which extends the C# programming language with contracts. A related project is Code Contracts, also at Microsoft Research, which uses Microsoft's common intermediate language format to support contracts in a more language-independent way. Project ideas: Projects can be defined based on one of the JML tools, SPEC#, or Code Contracts. Many other tools with similar functionality exists, including some developed here. A suitable project will be to select one of the above tools and learn it well enough to apply it to a selected application. Given the time available for the work, it is better to start from something modest and add complexity, than the other way around. One possible outcome for the ambitious might be to produce a lab suitable for a future advanced programming languages course. References:
Supervisor: Mads Dam Title: ABS -An experimental object-based programming language Theme: Programming languages Subject: ABS is an experimental object-based programming language at a level of abstraction somewhere between UML and Jav. ABS is being developed in the EU project HATS. The theory group is involved in several aspects of ABS language use, design, and implementation. Currently a language definition for a core part of ABS is available, along with prototype compilers and other tools. At KTH we are currently developing a compiler/virtualization layer for ABS with the goal of allowing programs execute efficiently on a highly dynamic network and dynamically adapt to changes in operating conditions. There are opportunities for defining a number of small projects of a size suitable for an essay project in the context of this work. Possible essay projects:
References:
Contact: Mads Dam or Karl Palmskog in the theory corridor Supervisor: Mads Dam Title: Go, Erlang and F# Theme: Programming languages Subject: With the increasing multi core processor PC available today, functional languages has gained popularity. Go is a new language developed by old C/Unix designers with built in concurrency support (basically a unix pipe construct). Erlang (1982) is a revived programming language used by Ericcson, Klarna (online payment company) and others. Erlang has built in concurrency that also support scaling on several machines. F# was developed from ML, an old functional language, and is promoted by Microsoft on the .NET platform. Essay project proposal:
References: Supervisor: Alexander Baltatzis Language TechnologyTitle: Linguistic steganography Theme: Language technology Subject: Steganography is the technique of hiding secret messages. For instance, if one writes a message with lemon juice on a piece of paper, the paper looks blank until it is heated, when the message magically re-appears. Another example is the technique (used during the second world war) of shrinking a text to a tiny dot, and then hiding the dot on top of a full stop in an innocuous letter. A recent twist of the same idea is linguistic steganography, where secret machine-readable data is encoded as a seemingly innocuous natural-language text. This can be done either by generating the natural-language text from scratch in such a way that it encodes the secret message, or alternatively by modifying an existing text. In the latter case, the encoding is made by making cleverly substituting sentences, words or characters in the original text. Possible essay project:
References:
Supervisor: Johan Boye Title: Program plagiarism detection Theme: Language Technology Subject: At KTH CSC we use a tool to try to detect similarities between students' solutions to programming assignments. The toold was originally developed for Pascal and has worked pretty well, as far as can be determined. This is partly due to Pascal's requirement that a procedure or function is declared prior to being called which enforces a certain structure on a lot of programs -- procedures and functions cannot be put in arbitrary order. Languages like Java and python give you more freedom to rearrange classes and methods in a file which may make it easier to fool the tool. The topic is to investigate the effectiveness of the old tool and consider and test some hopefully better method of detecting plagiarised code. On possible approach is to compute a call graph from the source code of two solutions and examine if the graphs are similar. Supervisor: Johan Boye Title: Automatic classification of opinions Theme: Language technology Subject: Many companies worry about their public image. Therefore it is of great interest to be able to automatically sift through blogs and articles and count the number of occurrences where the a certain product is mentioned in a positive way, and compare it to the number of times it is mentioned in a negative way. It order to do this rapidly and to a low cost, it would be preferable to use a simple classification method, provided it gives sufficiently accurate results. One possibility is to use a "bag-of-words" approach, i.e. only take into account which words occur in the text, not their grammatical relations. Possible essay project:
References:
Supervisor: Johan Boye Artificial IntelligenceTitle: Automatic Wordfeud / Scrabble player Theme: Language technology / Artificial intelligence Subject: The objective is to implement and evaluate different strategies for playing the immensely popular Wordfeud (Scrabble) game. For instance, a straightforward greedy strategy would always choose the move which gives the maximum number of points, whereas a more sophisticated strategy would also consider the possible responses of the opponent. (A good move gives many points but also limits the opponent's possibilities of making a good move in return). Such a sophisticated strategy would necessarily take into account which tiles have already been used, as well as the probabilities of the opponent being in possession of certain tiles. Different strategies can be evaluated by letting them play many games against each other. References: Supervisor: Johan Boye Title: 'Sims' for Pedestrian Behavior Theme: Artificial intelligence Subject: We are all familiar with the game, 'The Sims'. In this thesis you will explore building a simulation of a pedestrian walking around Stockholm. You will be given a spatial database that has buildings, streets, museums, etc. (obtained from OpenStreetsMaps). The pedestrian will have a mental model of what they are interested in, what they know about the city, etc. This will result in the simulated pedestrian embarking on a tour around the city. You will build a more or less complicated simulator using whatever algorithm you wish. Now what can you say about the resulting behavior? Is it human like or not? Is it possible for you to generate walking paths that are indistinguishable from real human walking paths? If you instantiate your simulator under two alternative parameter settings, how could you determine that one parameter setting produced more 'human like' behavior than the other. What are the wider implications for AI research if we succeed in generating convincing simulated behavior? Supervisor: Michael Minnock Title: Grounding Language in Perception Theme: Machine Learning Subject: Quoting Jeffery Siskind: Suppose that you were a child. And suppose that you heard the utterance 'John walked to school'. And suppose that when hearing this utterance, you saw John walk to school. And suppose, following Jackendoff (1983), that upon seeing John walk to school, your perceptual faculty could produce the expression GO(John, TO(school)) to represent that event. And further suppose that you would entertain this expression as the meaning of the utterance that you just heard. At birth, you could not have known the meanings of the words 'John', 'walked', 'to', and 'school', for such information is specific to English. Yet, in the process of learning English, you come to possess a mental lexicon that maps the words 'John', 'walked', 'to', and 'school' to representations like 'John', 'GO(x,y)', 'TO(x)', and 'school', respectively. This paper explores one way that this might be done. In this thesis, you are to replicate (some variant of) Siskind's experiment and comment on its suitability for practical application. References: Supervisor: Michael Minnock Algorithms and ProblemsTitle: Multi-skill call centers Theme: Problem solving Subject: Modern call centers often handle a large variety of calls. When a customer calls, he is first asked to give information concerning his reason for calling. This is usually made either via a push-button interface, or an interface that employs automatic speech recognition. Once the type of the call has been identified, the call is routed to a queue serviced by dedicated service agents. On the other hand, many service agents have multiple skills and are capable of handling more than one type of call. Thus, in general the relation between call types and service agents is a many-to-many relation (i.e. calls of a given type can be handled by several different agents, and a given agent can handle serveral different call types). Due to the ever-increasing proliferation of such multi-skill call centers, their organisation and properties has become an active research area. Two of the problems studied by computer scientists and mathematicians is the staffing an routing problems:
Possible essay project:
References:
Supervisor: Johan Boye Title: Analysis of voting algorithms Theme: Algorithms Subject: Parliament seats are to be divided proportionally to the parties, but also proportionally over Sweden. Many algorithms exist for optimizing the solution to this problem and different countries employ very different algorithms. A rational choice is possible only when the outcome of the competing algorithms has been computed for many political situations. The goal of the project is to program two or three algorithms and study their behaviour in different situations. Parameter tweaking is particularly interesting. Project highlights:
References:
Supervisor: Henrik Eriksson Title: Clustering Theme: Algorithms Subject: Investigate use of different clustering algorithms for classification on relatively large data sets. Possible uses include recognition of hand written characters and classification of articles. References:
Supervisor: Mikael Goldmann Title: Constructing Hierarchical Variability Models for Software Product Lines Theme: Formal Methods Subject: Dilian Gurov (KTH CSC), Bjarte Østvold and Ina Schaefer have propsed a formal, tree-like, representation of software product lines, where the tree represents a family of different products where each product is assembled from "artifacts" (e.g., modules, classes or methods). For instance, a product line could be the thunderbird mail client which has a code base made up of parts that are common to all platforms as well as parts for specific platforms, such as OSX, Linux or Windows. A product in this case is a particular choice of software components suitable to run on a particular platform, and the product line consists of all thunderbird implementations for all the platforms supported. The tree-like model is intended to capture both the common components and the variants. If a product line (that is a set of products where each product is simply a set of software components) has certain properties, then a "good" hierarchical variability model can be computed for the given product line. The project involves understanding the above results and writing a program that given a product line computes the unique optimal model (provided it exists). You should consider the complexity of your implementation so that it is efficient. Possible extensions are to visualize the model graphically or to find "good" models for product lines that are not simple enough to be handled by the given method. Contact: Dilian Gurov Supervisor: Mikael Goldmann Title: Sudoko solvers Theme: Algorithms Subject: In principle Sudoku can be solved using a brute-force algorithm but it is more interesting to find an efficient sudoku solver. The task is to study and implement som sudoku solving algorithms, and hopefully to design your own solution or variation. The algorithms should be tested and bench marked against sudoku instances of varying difficulty. Supervisor: Mikael Goldmann Title: Asymmetric travelling sales person Theme: Algorithms Subject: In the normal, symmetric, version of the travelling sales person problem disances are symmetric, that is, for two cities i, j the distance from i to j is the same as the distance from j to i. However in practice that may not hold. For instance in a city where some streets are one way, the distances may not be symetric. Much less is known about how to find good tours for the asymmetric case. Study this problem, examine available algorithms, implement a few and compare them on reasonable-size examples. You will need to make reasonably efficient implementations. Supervisor: Mikael Goldmann Title: Optimal Yatzee Theme: Algorithms Subject: Construct a program that plays Yatzee well, preferably optimally. The program should, given the current result and the current values of the dice, determine which dice to save or, if all three throws have been used in this round, determine where to put the score. There are several variations of this problem. The simplest one is to always maximize the expected points you will get, and a probably more difficult one is to, given both your own and an opponents current score, maximize the likelyhood of winning, provided the opponent also aims to win. There are also variations depending on the exact rules used. Supervisor: Mikael Goldmann Title: Finding the shortest connection with a genetic algorithm Theme: Genetic algorithms Subject: A Steiner network is the shortest road network connecting a given set of points in the plane. The four corners of the unit square may be connected along three sides (total length 3) or by the two diagonals and an internal node at the center (total length 2.828), but the Steiner solution has two internal nodes and total length 2.732 /try to find it!). Finding the Steiner solution is NP-hard in general, so exhaustive search is out of the question. However, starting with a small set of (bad) candidates, we may use selection and mutation to improve the set and eventually converge to one proposed solution. This may be the correct solution but it may also be just a local optimum, so the procedure has to be repeated hundreds of times. This idea has played an important role in the discussion about Darwinian evolution vs.~intelligent design, see reference [D Thomas]. Project highlights:
References:
Supervisor: Henrik Eriksson Computer Graphics and VisualisationTitle: Particle systems and flock behaviours Theme: Computer graphics / Simulations Subject: Particle systems are based on modelling and visualisation of a larger or smaller set of particles and can be applied to create images of e.g. fireworks, smoke and water cascades. Similar techniques can also be used to model the behaviour of flocks, of for examples birds, that are given specific characteristics in order to keep together, avoid collisions, etc. Possible essay projects:
References:
Supervisor: Mårten Björkman Title: Perceptual aspects of computer graphics and visualisation Theme: Computer graphics Subject: Human visual perception plays a large role in what to visualise in computer graphics. A commonly used technique is to draw objects located far away in a lower resolution, a technique which is called ”level of detail” (LOD). There are also other techniques that exploit what the human visual system is unable to perceive. Possible essay projects:
References:
Supervisor: Mårten Björkman Title: Graphics with limited resources Theme: Computer graphics Subject: Lots of software development today are done for portable devices, such as mobile phones. Computer graphics has today become a natural component in such devices. However, portable devices are limited in terms of screen resolutions, memory and processor capabilities and battery resources. Some of these obstacles will be possible to overcome in the near future, but some problems will always remain, such as the limited sizes of screens for example. Possible essay projects:
References:
Supervisor: Mårten Björkman Title: Multiplayer games on IOS Theme: Visualisation Subject: The sheer explosion of games for IOS and Android is spectacular; currently there are more than 500 000 apps in Apple App Store, most of which are games. Although multiplayer is almost mandatory on other platforms, it's relatively rare on mobile devices, typically due to high costs for the connections and high amount of drop-outs. This is rapidly changing though, and games start to appear. In parallel, the interest and popularity of e-sports (live and via YouTube channels) is increasing. Possible essay projects:
Contact: Björn Thuresson (CSC Visualisation lab) Supervisor: Mårten Björkman Title: Large scale multi touch Theme: Visualisation Subject: In recent years, multi touch has become an extremely common way of interacting with digital content, especially via mobile platforms. There are also larger scale examples, e.g., Microsoft Surface and Multitouch, and the full support for multi touch in Windows 7 (and in 8). In the visualisation studio at CSC we have a Surface 1 and will get a Surface 2 when it's released. The Surface platform is somewhat different from its competitors in that it also has object recognition. Possible essay projects:
Contact: Björn Thuresson (CSC Visualisation lab) Supervisor: Mårten Björkman Title: High resolution stereoscopic solutions Theme: Visualisation Subject: In the visualiation studio at CSC we have two 4K projectors (JVC D-ILA) with Infitec interference filters delivering a stereo image. We have two specially built servers by Zaxel to produce the content. The cluster is used to seamlessly switch between computer-generated material in mono and stereo, and cinema in mono and stereo. Possible essay projects:
Contact: Björn Thuresson (CSC Visualisation lab) Supervisor: Mårten Björkman Title: Stereoscopy (3D) for home use Theme: Visualisation Subject: Currently, there are several solutions for experiencing stereoscopy (popularly referred to as 3D) at home. The applications are most often cinema (on DVD or blu-ray) or games. There are also a few example of TV content in 3D. In the visualiation studio at CSC we have a workstation for nVIDIA 3D Vision. Possible essay projects:
Contact: Björn Thuresson (CSC Visualisation lab) Supervisor: Mårten Björkman Title: A mobile dictionary sans words Theme: Visualisation Subject: Travellers have sometimes a difficult task of making themselves understood in various situations in many parts of the world. The language barrier can often become a huge problem very fast, even in typical situations of daily life. Can you drink this water? Where is the nearest 24hr pharmacy? Do you have anything vegetarian on the menu? Often conversations are supported by gestures and amateur drawings, which sometimes resolve the situation - and sometimes not. The assumption is that having a timely set of professional images and drawings, corresponding to a fair set of everyday needs and wisely chosen subjects can resolve many of these situations in an efficient manner. The aim of this thesis proposal is to bring fourth a model as well as a working, navigational demonstrator of a wordless dictionary for everyday life, aiming to aid the traveller by providing assorted high-quality professional images to help bridge the babelicious conversation between two or more parties who to a greater or lesser extent lack the ability to interact using the spoken word alone. Related theory will be investigated and applied. Possible essay project:
Contact: Alex Jonsson (KTH / MoSync) Supervisor: Mårten Björkman Title: Graph editor Theme: Computer graphics Subject: In computer science, automata and graphs are important and useful mathematical concepts. Often these are represented in some textual format which represents the states and the transitions of the automata/graph. However, graphs are more understandable if they are visualized by circles to represent states and arrows (or lines) to represent transitions. There are quit a number of tools available for transforming the textual representation of a graph to a visual representation, e.g. Graphviz which transforms DOT textual format of a graph to a variety of image formats (e.g. jpeg,ps,etc.). There are also tools that provide graphical user interface for drawing and editing visually represented graphs. For example www.lucidchart.com application in google Chrome provides a web-based graph drawing interface or Dia Diagram Editor which is a tool to draw structured diagrams. The task of this project is to develop a web-based application that accepts a textual representation of a graph as input, and provides facilities for visually displaying and editing the graph. Furthermore, The application should be able to transform the visualized graphs into a textual format. To this end, existing tools and techniques can be exploited and thus a part of the project is to investigate the available web-based graph editors (e.g., www.lucidchart.com application in google Chrome). Possible Essay Projects:
References:
Contact: Get in touch with Siavash Soleimanifard in room 1433, E building, KTH main campus if you are interested in this line of work. Supervisor: Mads Dam SimulationTitle: Event based vs. activity based simulation Theme: Web apps/Programming languages Subject: An office building obviously needs lifts but how many, how large and how quick? Such questions may be studied by computer simulation of lifts and people involved. For specific lift parameters and employee parameters, the simulation results will tell you such things as average waiting times at rush hours. In activity based simulations, time moves in small steps with all ongoing activities being updated. Activities are the movements of lifts and people. In event based simulations, time moves from one event to the next event. Events are instantaneous, such as a button being pressed or the lift arriving. Random events have to be implemented differently in the two paradigms and the whole program structure is quite different. Which of the two paradigms is best in a particular case? The goal of the project is to try to answer that question by programming the same model in the two different ways. Project highlights:
References:
Supervisor: Henrik Eriksson Title: Silverfish simulation Theme: Simulation/Genetics Subject:You have all seen them when you switch on the bathroom light: little bugs, either scurrying to safety or playing dead. Their behaviour has of course been optimized by millions of years of evolution. Is it possible to simulate this? Will the simulated silverfish act more and more intelligently for each generation? Project highlights:
References:
Supervisor: Henrik Eriksson Title: Robot door opening Theme: Robotic control/Simulation Subject: Given a robot in a household environment, it is an interesting problem how to open doors, drawers, etc. If a door has never been encountered before, a robot with limited sensing abilities may not know where the hinges are located or how the door can move, thus having problems opening it. The aim of this project is to implement one or more adaptive controllers that perform continual estimation of the door kinematics, in order to allow for smooth door opening. The implemented controllers will be tested in simulation, and different conditions and settings will be tested and evaluated. Details of the modelling of the door opening task, and the formal description of the controllers can be obtained from Yiannis Karayiannidis (CVAP/CSC). This task requires good programming skills. Supervisor: Mårten Björkman Speech and MusicTitle: Design of new musical instruments for iPAD Theme: Sound and Music Computing Subject: A number of new musical instruments have been specially designed for the iPAD. The features of these instruments and their potential for musical expression are not explored. The use of sensor technology for reproducing and augmenting the functionalities of the interfaces with the player of common musical instruments is a particular challenge. Does it contribute something new to music performance or is it faking expressive interaction? Possible essay project: Study and give a structured overview of a new musical instruments making use of iPAD. Explore the different uses of the sensor technology of the iPAD, and relate them to the main musical features of the new instrument, the characteristics of the interaction with the player, and the connection between iPAD sensor technology and musical expression features. Based on the accumulated knowledge, design and implement the basic features of a successful new instrument using iPAD which is truly expressive. References:
Supervisor: Anders Askenfelt and Roberto Bresin Title: Sonification of physiological parameters Theme: Sound and Music Computing Subject: In the last couple of years many apps for real-time monitoring physiological parameters such as heartbeat rate during running have been developed for both iPhone and Android mobiles. This enables runners to check theirs own heartbeat rate by looking at the mobile phone display. Sonification ('visualization' by sound) of physiological parameters is a much more attractive way to explore in order to e.g. synchronize and monitor athletes' movements for optimal performance or for medical diagnosis, monitoring and evaluation of treatment. By sonification complex structures in physiological data can be detected and evaluated in real time. Possible essay project: Study and survey the performance of the most popular running log programs analyzing heartbeat rate. Based on an overview of literature for heartbeat rate sonification for professional purposes, suggest a better design for sonification of heartbeat rate which can guide elite runners to continuously optimize their running actions during performance. The new design is implemented in a mobile and evaluated under field conditions. References:
Supervisor: Anders Askenfelt and Roberto Bresin Title: Music Information Retrieval using the Million Song Dataset Theme: Sound and Music Computing Subject: Music Information Retrieval (MIR) is about using audio features and meta information in order to make predictions about different musical aspects. It can be related to both high-level descriptions such as predicting genre, music similarity ("if you like this one you may also like..."), musical moods, as well as more specific things like melodic recognition and retrieval or tempo estimation. Advanced signal processing methods are used for computing audio features. For mapping features to descriptions often machine learning methods or statistical inference methods are used. The Million Song Data set (MSD) provides a way to “kick-start” an investigation in MIR since it contains a large number of pre-computed audio features for one million songs. Possible essay project: Make an overview of the available data and audio features in the MSD dataset and related sources like last.fm tags. Suggest how this can be used to predict different high-level aspects (genre, mood, similarity) and give examples of possible applications. Pick one of the ideas in 1) and make a prototype application. This could be a web application, mobile phone app or a Matlab script. References:
Supervisor: Anders Askenfelt & Anders Friberg Title: New approaches to expressive sound interaction for mobile devices Theme: Sound and Music Computing Subject: Smartphones or tablets offer a large range of possibilities for incorporating sound in the interaction with the user. Interaction can e.g. be multi-modal with gesture-based interface but how these features can support meaningful and novel ways of interaction with the user is to a large extent an unexplored field. Possible essay project: Design and implement a system for efficient and expressive sound interaction on a smartphone or tablet. The focus can be in one of three areas: human-computer interaction (e.g. usability), medical/clinical use or art. Implement the basic features of the proposed system on a smartphone, and compare the suggested mode of interaction with graphic-based alternatives. Evaluate the expressive capabilities of the system and efficiency in interaction. References:
Supervisor: Anders Askenfelt & Kjetil Falkenberg Hansen Title: Swype for desktops Theme: Speech Technology Subject: Android's Swype is a text input method for touch screen-based mobile telephones. It makes it easy to input words by drawing gestures on a virtual keyboard instead of pointing at each key singularly. The system is based on machine learning methods that can be trained on a number of swype examples and learn how classify gestures into words. Possible essay project: Develop and test a swype system for a desktop or laptop computer by using mouse or tablet input as well as touch screen input. Some important steps in the development include; implementing of a virtual keyboard that accepts input from common pointing devices (mouse, tablet, touch screen), and use of the virtual keyboard to record word examples and implement Hidden Markov Model algorithms for learning and testing. The system is trained and evaluated with a limited number of words. References:
Supervisor: Anders Askenfelt & Giampiero Salvi Title: Visualizing chronograms using HTML5 Theme: Speech Technology Subject: The study of spoken dialogue - how people speak to each other - is increasingly important as spoken dialogue interfaces are getting increasingly common. Spoken dialogue is continuous in nature and is realized in a linear fashion over time. Chronograms provide visual representation of how the dialogue (or any other ordered sequence of events) progresses. However, the appropriate window size over the chronogram varies with its motivation - different time spans are appropriate for different analyses. This project is about developing a general web based tool - using HTML5, CSS3 and java script - to visualize chronograms of arbitrary length and level of detail. Possible essay project: Design and implement a general tool for visualizing chronograms on a screen that allows the user to zoom, scroll and perform pagination of the dialogue into segments of different length. Pre-processed dialogue data for different types of dialogue, that can be used for proof-of-concept and evaluation of the tool are available. References:
Supervisor: Anders Askenfelt & Jens Edlund Title: Web based control for an interactive talking robot Theme: Speech Technology Subject: In HTML5, the restriction prohibiting web pages to easily open sockets and utilize full duplex connections is removed with the introduction of the WebSockets protocol. This opens up a whole new range of browser based pure html/css/javascript applications that can be implemented in a straightforward manner to do tasks that previously could only be achieved using proprietary technologies and work-arounds. Possible essay project: Controlling the speech and movement of the talking robot head FurHat from a web page. To do this, the currently used CTT Broker, needs to be adapted so that it accepts WebSockets and a Broker client for HTML5 needs to be implemented. The system's functionality and robustness is evaluated in typical dialogue situations (using commands like "say", "turn head" and similar). References:
The project requires good to excellent Java skills and basic skills in HTML/Javascript. Supervisor: Anders Askenfelt & Jens Edlund Title: Visualizing dialogue data using HTML5 Theme: Speech Technology Subject: Spoken dialogue, as well as many other phenomena, is continuous in nature. Roughly speaking one word is presented after another in a linear fashion over time. Such data can be annotated by attaching labels to each segment (e.g. word). The labels can represent virtually anything; in dialogue research common examples include laughter, breathing, and utterance type. Possible essay project: In order to get an overview of annotated continuously ordered data, a general web based tool (using HTML5, CSS3 and java script) is developed to visualize the distribution of labels attached to ordered segments. Prepared dialogue data from two different types of dialogue in which statistics are expected to differ noticeably is available for proof-of-concept testing, visualization and evaluation. References: Examples of illustrations of statistics on this type of data can be found in
Supervisor: Anders Askenfelt & Anna Hjalmarsson Title: Annotation app for Android (and Iphone) Theme: Speech Technology Subject: One of the most time consuming aspects of much modern research on human behavior is manual annotation of data. In many cases, this is an expensive and unavoidable step to get ground truth for machine learning and automatic analyses. In speech research, a common task is to annotate speech fragments or utterances with respect to some specific parameter, such as "is this laughter?", "is this a question or a statement?", or "is the speaker out of breath?". Currently it is common to use so-called crowd-sourcing or services such as the Mechanical Turk (www.mturk.com) for this type of task. A less common but highly interesting variety of this is to use custom-built annotation apps for smart phones. Possible essay project: Develop an Android app that can annotate speech data from an audio file according to an annotation specification. Audio files and realistic annotation tasks for proof of concept and evaluation are available. A successful annotation of the provided data will generate new research results. References:
Supervisor: Anders Askenfelt & Anna Hjalmarsson Title: Facial animation player based on WebGL Theme: Speech technology/ Computer graphics Subject: Recent web-browsers come with the capability to natively display complex 3D content with hardware accelerated rendering. A possible use of this capability would be browser-based facial animation of speaking agents for enhancing interactive content on web pages. Possible essay project: The WebGL standard allows for high quality browser-based 3D graphics. This could be tried on a browser-based player for facial animation with synchronized audio. The animation could e.g. be performed using shape interpolation, and driven by text or audio data. Several facial models are available for comparison. The evaluation could focus on how animation of different parts of the face enhances the interaction, or how contradictory information in animation and speech content influences a man - machine spoken dialogue. References:
Supervisor: Anders Askenfelt & Jonas Beskow Title: Sing me your status Theme: Speech and Music Technology Subject: A system capable of singing short text messages (SMS, twitter-tweets, chat messages, status updates etc...) could be a useful way of enhancing the content. Possible essay project: Composing a melody to a given text requires artistic skill and inspiration, but a rule-based matching strategy can probably produce decent results. One approach could be to use text-to-speech software to transcribe the text into a sequence of phonemes, and then analyze the phrasing and the placement of focused syllables. This data set could be matched against a set of known melodies, according to some rhythmic criteria based on intelligibility and artistic considerations. The result can be listened to through a singing speech synthesizer. The evaluation will show why and how a human composer would have performed much better. Supervisor: Anders Askenfelt & Jonas Beskow Title: A nineteen tone scale synth Theme: Web apps/Programming languages Subject: ChucK is a new (and developing) audio programming language for real-time synthesis, composition, performance, and now, analysis. As far as is known, it has only been used for music using the traditional scale with each octave being divided into twelve tones. Theoretical considerations suggest that dividing the octave into nineteen parts might be a fascinating alternative. However, no such instrument exists. The goal of the project is to explore the opportunities of this new scale. Project highlights:
References:
Supervisor: Henrik Eriksson |