Monday, January 14, 2008

Research in Computational Video

From what I understand, the seminar given to the School of Computer Science last week by Gerhard Roth (entitled Past, Current and Future Research in Computational Video with Applications to Gaming) was part of a competition for a faculty position required for the new game development program. I believe the idea was to have candidates share the kind of research they do and how it would be useful to game development. Dr. Roth was the first to present and he discussed his involvement in some really interesting computer vision research over the past decade or so.

Dr. Roth was part of the computational video group at the NRC (National Research Council Canada) before its funding was cut, and he teaches a computer vision course to fourth year computer science students here at Carleton (which I took during my undergrad).

One of the research projects Dr. Roth was involved with is the NAVIRE project. Very similar in nature to Google Street View, this project was a collaborative effort between the University of Ottawa and the NRC. The team used panoramic cameras to capture surroundings from the viewpoint of a person traveling along a road. The captured data was transformed into cubes, which could then be viewed with specialized software. Dr. Roth claims that NAVIRE solved several problems that Google's system did not, though it is not immediately clear to me what these are. Sifting through some of their publications might shed some light on this.

Another interesting project described in Dr. Roth's presentation related to another technology that should interest Google: image classification and retrieval. For the former, the user would select a subimage, probably a particular object to search for, and the system would retrieve all images that contained a subimage strongly similar to the search criteria image. To do this, various lighting conditions have to be accounted for as well as slightly different perspective viewpoints or scales. Occlusions must also be considered. For the latter, a number of images are categorized into a predefined set of semantic descriptions, such as car, dog, umbrella, and so on. After these categories are trained using a control set of images, the system would be able to give the probability that a new image belongs to a particular category. Test results are decent with only 100 training images for each category.

There were more projects mentioned in the presentation, but I'd like to move to those that interest me the most. I've discussed the concept of tangible user interfaces more than once (here and here), so by now it should be obvious how excited the topic makes me. Watching Dr. Roth talk about his experiences with them (under the mostly equivalent name of perceptual user interfaces) reminded me of this, and even gave me a whole new idea for a thesis! (I'll save a post on this new idea for another day, maybe after I talk to my supervisor about it).

In particular, Dr. Roth has been involved a lot with something called augmented reality. This should not be confused with virtual reality: the former uses real live video feeds and adds interesting computed imagery to it, while virtual reality tends not to combine real video with the virtual. The image below shows a good example of how augmented reality could be used.

(Image from http://www.vr.ucl.ac.uk/projects/arthur/)

Here, the two users have headsets on that show them a video feed of whatever is actually in the room, as well as the augmentation of the cityscape they are working with for the purposes of urban planning. Placeholder objects are physically manipulated on the table, but replaced with the virtual models in the video result displayed to the users.

It's not hard to imagine that a sizable investment would be necessary for this system, given that each user requires a head-mounted display unit. The alternative is to use consumer devices with front mounted cameras like cell phones and tablet PC's, such as is seen in this image.

(Image from http://studierstube.icg.tu-graz.ac.at/handheld_ar/smartphone.php)

It may not be as immersive as a system using headsets might be, but the potential for gaming is much more realistic for devices that everybody already owns. And that's where the seminar concludes: Dr. Roth believes that with an investment of several inexpensive tablet computers upgraded with inertial devices, some really interesting collaborative games could be developed. I'd be up for that!

Thursday, January 10, 2008

Online Resources for CS Students

I recently received an email from a lady at the Virtual Hosting blog (not entirely sure why they have a blog, or why they blog about such strange things as I'm seeing on their front page right now, but anyway....). They posted an article called "50+ Killer Online Resources for Computer Science Students". She thought you, my readers, might be interested. I checked out a few links and it looks like there should be some good stuff there. Let me know if you liked it!

Wednesday, January 9, 2008

The "COMP 4804" Debate

There has been a bit of debate going on at our School of Computer Science for a while now. The big question is whether a fourth year algorithms course should be or shouldn't be included in particular streams of the Bachelor of Computer Science degree (for example, the game development stream). The argument is that the more applied areas of computer science have too much else to learn, and that these more difficult courses may be scaring students away.

Personally, I think it should always be required, since it is the stuff at the heart of computer science in the first place!

Before we go any further, let me share with you the calendar description for the course:
COMP 4804 [0.5 credit]
Design and Analysis of Algorithms II
A second course on the design and analysis of algorithms. Topics include: advanced recurrence relations, algebraic complexity, advanced graph algorithms, amortized analysis, algorithms for NP-complete problems, randomized algorithms. Also offered at the graduate level, with additional or different requirements, as COMP 5703, for which additional credit is precluded.
Prerequisite: COMP 3804 or permission of the School.
Lectures three hours a week.

The last three points are what the course focussed on most when I took it (I believe some of the subject matter has been shuffled between the always mandatory COMP 3804 and this course). I honestly cannot imagine any computer science degree (which, it should be noted, is very different from a software engineering degree or a computer programming diploma) being complete without an understanding of these topics!

The pure-theory algorithms folk at school will naturally tend to push this course as mandatory, as it represents everything they do. But the professors who work in more applied subjects should care just as much! At the end of the day, everyone needs algorithms to accomplish their tasks. And nobody is immune to encountering problems that can be solved efficiently using approximations or randomized processes, or perhaps even problems that can't be solved efficiently at all!

Imagine the time that could be wasted on trying to solve a problem that ends up being NP-complete. If you don't know how to recognize it as such, you might hammer away at it until you realize you have too much data to crunch and not enough time to crunch it in. It's not that unlikely, no matter the domain!

Of course, if you do go to grad school without this knowledge, you will be at a huge disadvantage. I've attended only one computational geometry class so far this year, and already randomized algorithms were used to solve the very first example. Having taken COMP 4804 made all the difference in understanding what was going on right away rather than having to struggle to figure it out later on. The weirdest part is that COMP 4804 isn't even required to get into grad school, and since many computer science streams (including at our own school!) don't require it, there's a pretty good chance that you just won't have the knowledge when you start your graduate studies.

What do you think? Have you taken an advanced algorithms class and loved it? Or do you think it really isn't always all that useful? Share your thoughts as comments!

Friday, January 4, 2008

Portfolio Showcase

I think that every professional in our industry deserves a good portfolio. Far too often have I seen well-intentioned students grab a domain name and slap up a basic infrastructure with the text "more to come soon." I tend to check back because I am interested in what friends and colleagues are up to, but I rarely see anything new.

Granted, these people generally do a lot behind the scenes because this is what they are interested in. They like to set up content management systems or write their own code. I went the other route with my portfolio: I just used Dreamweaver to put something together fairly quickly. I don't even know if it is completely valid HTML or CSS. My friends would cringe at the thought! :)

I'm glad I decided to go this way, if for no other reason than the fact that it's been really easy to actually add the content. I have no desire or need to update the back end to the latest and greatest, so I can concentrate on what really counts to me. I love being able to add information about my latest school projects or cool graphics I've made.

Which brings me to the real point of this post: to showcase my portfolio! I am planning to change hosts and my new domain gailcarmichael.com will eventually point to the portfolio instead of redirecting to this blog, but until then, check me out at http://www.scs.carleton.ca/~gbanaszk/. Drop me a comment if you liked anything you saw, or better yet, tell me where to find your portfolio!

Thursday, January 3, 2008

Street Selection and Self-Organizing Maps

Maps have become an essential part of many of our lives, helping us to get from one place to another for centuries. With the widespread availability of relatively recent digital technologies, such as Google Maps, the need to display maps at different resolutions has never been greater.

Think of the kinds of features that are shown in this map of Canada:


View Larger Map

Not a lot is shown beyond a bit of water and some major political markings. When zooming into Ontario, bodies of water become more clear and major roads are now shown:


View Larger Map

Finally, much more detail, including local roads, is possible when looking at just the city of Ottawa:


View Larger Map

There is obviously some decision making happening behind the scenes in order to display the most important features for a particular level of zoom (or resolution, as it were).

Let's look specifically at road networks, ignoring the other features for this discussion. There are two levels of work to be done when determining what roads should be shown at a particular level of detail. This whole process is known as generalization, since we must decide what subset of all the available information will be shown.

The first step of generalization involves examining the model of the road network and using information about street connections, types, and so on to pick out the most important or relevant pieces to show.

Once we have the data that is to be visualized, the second step analyzes the geometric properties of the chosen roads and uses the results to simplify the graphical rendering of the roads. For example, a road with many small bends that can't be rendered onto the screen as such will be simplified to a straight line instead.

It is in the first step that self-organizing maps (or SOMs) can play a role. These maps are actually neural networks that are used to cluster and visualize data. To make a longish story short (and simplified), you create vectors with as many dimensions as you have numerical properties about each item you want to cluster. Using these numbers, the SOM sorts out the data so that items that are most alike end being "close" together. You might, for example, have a SOM that is represented by a two dimensional grid, and the input vectors will be organized into the cells based on their similarities.

In the case of selecting roads from a network, there are some obvious numerical values that can be used to describe each street for use in the SOM, such as length. There are, however, also some less obvious choices that seem to help categorize roads in a more useful way. A good list of attributes for each road is as follows:
  • Number of streets that intersect this one
  • A measure of closeness between this road and all others around it, using shortest path distances
  • A measure of betweenness, the proportion of shortest paths between all other roads that pass through this one
  • Length and width (i.e. number of lanes)
  • A numerical representation of the class of road (i.e. avenue, street, highway, freeway, etc)
  • Speed limit
Using these properties, roads can be clustered into a SOM. We can then pick a group of similar roads very easily. If we are careful about using the numerical properties so that when the value increases, so does the corresponding importance of the road, we can simply pick the SOM cells with the highest average values for the vectors stored within. These roads will be used in the map's final generalization.

For more information, please have a look at my final project for the GIS class I took in the fall semester. I implemented street selection using SOMs. The file includes my write-up of the project as well as the Java code used. Be sure to look at the README file if you plan to play with it as you will need to do a bit of work to set things up.