SACO: All Ready To Go!

A group of twelve of us have been preparing the problems for the final round of the South African Computer Olympiad over the past month. We've spent many hours proof-reading the problems and writing over 100 check solutions to make the problems as polished as we possibly can. We are finally ready for to hit the big red button, getting the show underway.

If you're a contestant this year, best of luck to you and I'll see you tomorrow! If you're not, however, you can still compete. I announced our first ever online contest here, but this deserves a reminder. Registration is open and full details can be found here. The problems in the main event are very challenging, so if you're not used to this level of competition I recommend trying the junior contest.

Last I heard the registration numbers are fairly good, although we'd love to see you join in as well. The probability of us repeating this in future years is directly proportional to the numbers and hence its success. If anything, our Monty Python theme (with Python being a key language thanks to Mark Shuttleworth) is alone a reason good enough to participate in the fun!

What Happened With Google Code Jam?

When I visited the Google Zurich offices in June, there was a bit of discussion about the Google Code Jam. We were told that since they had so many regional code jams last year, the organisers were exhausted to the point where they decided to take a break this year. Hence the talk was that there would be no code jams this year.


Today, however, I came across a blog post on the official Google blog. This post brings back hope that the Code Jam will return soon. Quite interesting was the following line:

now we're excited to join that community in our own right, by producing a Google Code Jam of our own!

In previous years they've made use of the TopCoder platform and the contest has therefore been very TopCoder-like. Hopefully this means that they will get more involved in running things themselves and therefore moving away from the TopCoder style, which I personally dislike due to the short duration. The second practice problem the post links has a Google theme, which further suggests they will be moving away from TopCoder.

I sure hope that it returns, although I would be far more impressed if they can put together a marathon contest lasting about 24-72 hours. With marathon contests you get to work in a team and rack your brains together for much longer and it can be great fun.

Under vs Oversegmentation

I've started getting my first segmentation results for my honours project. To sum it up in a few words, image segmentation is about breaking an image up into regions. This has many applications and is often the first step in image processing, with the end results heavily relying on the segmentation quality.

The problem is that it's very difficult to define what a good segmentation is. It depends a lot on, amongst other things, the nature of the image. Lighting conditions, noise, texture - these can all have a large impact on the results. A key problem in segmentation is that of splitting up into too few (undersegmentation) or too many regions (oversegmentation). This is easily demonstrated by my first results as shown below.

The first image is the original we're trying to segment. It's the famous Lenna image used throughout image processing as the standard test image. Notice the noise in the background, texture in the hair and hat, smooth texture of the skin and many other features that one aims to handle well in image processing.


These next three images are segmentation results I obtained from my implementation of the Watershed algorithm. The first result comes out of the Watershed algorithm with no improvements to the original algorithm besides some linear filtering to reduce noise. A region is displayed by averaging out the colours in that region and assigning a single colour to the entire region. As you can see there isn't much difference between this and the original. Click on the image for a larger view and you should notice the small regions.

This is an example of severe oversegmentation. It was the major problem with the Watershed algorithm when it was first developed. Since then there have been several improvements, one of which you'll see in my subsequent results.


These next two results make use of a very simple smoothing technique to reduce the oversegmentation problem. Gradients form a key role in the algorithm and here I threshold the gradient to reduce the effect of minor differences. The two results below use different threshold values and you should easily be able to spot the differences.

The first is more ideal, with the second being undersegmented. Look at how a large chunk of the hat is grouped together with the background region. Both, however, oversegment the hair and this is where the problem with textures comes in.



There's still a very long way to go here and this is just the beginning of the results. I haven't even tried running with a different image. My eventual goal is to try produce a single segmentation algorithm to cover a wide variety of images. That's where genetic algorithms will come into play to help with the uncertainty of the image.

I must say it's nice to be able to show visual results that probably explain things better than words can explain.

UPDATE: Applying a median filter to the gradient image produces much better results. See the results in the image below. The textured areas are segmented into far fewer regions. The boundary of the hat is fully in tact. The finer details such as the eyes and mouth have less impact on the segmentation. Also, the number of tiny regions resulting from noise is greatly reduced. This shows how how much of an impact such a small change can make.

Computer Science Honours at UCT: Part 2

This is part 2 in my review of the CS honours modules at UCT. Read after reading part 1.

Introduction to Image Processing and Computer Vision (IPCV):

I've always had a small interest in image processing, so I might be a bit biased towards this module. IPCV is lectured by Patrick and I think he does an excellent job of it. He covers topics such as image transformations, feature detection and segmentation. This was also the first of many modules in which genetic algorithms were touched on. It requires a moderate amount of mathematical background, especially linear algebra. If you're into your maths in any way I'd strongly recommend it, but if you're not I'd be cautious, but still consider it. Six of the lectures are used as paper reviews in which you read a paper before the lecture and then discuss it in class.

The assignment is all about using the Hough Transform for circle detection. For those doing the module or any other image-related programming I strongly suggest the CImg library as it has a gentle learning curve and is well documented. The assignment is a simplified version of my second year project and I plenty test data available here.

Parallel Computing (PC):

This is another module I might be a bit biased towards due to personal interest in the subject. I really enjoyed it, even though it was perhaps a little lacking in detail. PC is lectured by Michelle and covers parallel architectures and parallel programming. This year there was a big emphasis on parallel genetic algorithms.

The assignment this year (it changes every year) was to program a parallel genetic algorithm without a library. Parallel programming can be tricky, especially to debug. Added together with genetic algorithms, which can be touchy, made it a not-so trivial task.

I would strongly encourage almost anyone to take PC. It's a nice thing to know how to do parallel programming, especially with the ever increasing number of cores going onto PC processors.

Agents:

I was very excited about taking the Agents module. This was the first time we covered anything related to artificial intelligence and it was lectured by Anet who's research area is agents. It is another one of those modules that has been affected by the introduction of the gaming stream. The Intelligent Systems (IS) module was moved into the gaming stream and we lost the opportunity to take it. So for us, and hopefully the impact will be lessened next year, we had both modules squeezed into one. This resulted in a broad overview of the many AI topics without much depth. Topics covered included neural networks, genetic programming (GP) and several topics related to agents ending off with complex adaptive systems.

The assignment was to program a GP to produce a strategy for predators whose goal it was to capture a single prey. This was one of the more time-consuming assignments, however it was very enjoyable. We had to produce a report on our implementation, which you can read here. The exam is apparently the most difficult of the year and take-home exam. It is often said by ex-honours students and I agree: be scared of open book exams, be very scared of take-home exams!

Genetic Algorithms (GA):

Audrey is one of the newest lecturers in our department and with all senior lecturers required to take an honours module, she started a new one on Genetic Algorithms. I don't want to harp on this too much for her sake, but she wasn't very well prepared and the module ended up having very little content. Most of the lectures were taken by the class, including all the examinable content. Hopefully Audrey will learn from her rough ride this year.

Putting the negatives aside, the module does have a lot of potential. GA's is one of Audrey's main research areas and there's a lot to learn about them. I think some of the GA content covered by other modules needs to be removed in order for this one to become a success. This year we covered the basics of GA's, applications of GA's and GA toolkits.

We each gave a 45 minute lecture in groups of up to three, with each group covering a paper. While it was not for marks, the exam covers a selection of these papers and nothing else. The assignment was to experiment with a genetic algorithm using a GA toolkit and write a report about it. I took advantage of the similarities between this and the Agents assignment and combined them. You can read my report here.

Internet Interoperability (II):

This module is taken by Hussein and that's one of the main reasons I took the module. The other reason is our assignment was all about programming a Facebook application, with the idea being to deal with interoperability issues first hand. I wrote a whole separate post one the assignment here. The module covered several topics around interoperability such as protocols, data/metadata, repositories and web services. It was an interesting module if you're interested in the web at all, but I would give it second thoughts given the choice again.

Intra-Domain Traffic Engineering (ITE):

Of all the modules I took, but not for credit, this was my favourite. Another of our newest lecturers, Antoine, started this as a new module this year. Traffic engineering is all about how to route traffic from source to destination. While this might sound simple at first, just consider what happens when links start failing. There are some fairly complex graph theory problems introduced, such as the K-shortest path problem which tries to get K disjoint shortest paths.

Antoine covers the module at a good pace, allowing for plenty discussion. So many lecturers take their lectures in such a way that almost prevents discussion, which is a real pity when you're in a smallish class. I didn't do the assignments, but there were three of them using NS. The exam is a brief oral exam covering mainly covering the assignments.

Still one more post to come and the module reviews will be done!

Part 3

Migrating to Google Apps

I've been considering a move to Google Apps for some time now. This week I finally took the step. Along with many others, I really like the gmail interface for several reasons. I've been using gmail since early 2005.


I registered the domain [redacted].co.za, which costs R150 a year, and now our whole family has name@[redacted].co.za addresses. Setup was fairly straight forward, considering that the complexity of editing CNAME and MX records is out of Google's hands. And need I mention Google Apps is a free service!

The one thing I found to be lacking was migration tools. I'm slowly migrating completely from my current gmail address to this new one. They're both essentially gmail and Google are trying to promote Google Apps, so what better thing to do than ease the migration between the two? Once they've come to realise that's crucial in converting users then easing the migration from other mail services would be awesome. They offer partial migration help as mentioned here, however, as the comments state transferring from gmail to apps isn't supported so I haven't explored it that much.

I then came across a wonderful 3rd party gadget, gXFER, that does as much as is probably possible using the gmail API. It migrates mail, labels, filter, contacts and calendars and also applies the filters to migrated mail. Mail migration is done by using the recent POP3 mail download feature, which takes a very long time if your mailbox is full. My mail is busy being transferred and it doesn't appear as though it's going to copy sent mail across, which would be a pity. It also doesn't maintain labels for emails that were manually labeled, which I suppose only Google can implement.

So far I'm happy with Google Apps. There's not much noticeable difference to a normal gmail account, but I feel it's nice having a more personalised email address while still making using of the wondrous free gmail service. I've also confused several people when they received a gtalk invite from a non-gmail address. :P

South African Computer Olympiad Online Contest

In the words of Bruce Merry:

For the first time, we will be running an online version of the South African Computer Olympiad, similar to the way this year's IOI was run as an online contest, and we would like to invite anyone who is interested to take part. The SACO is an IOI-style contest run over two
days. The online contest will run

Saturday 15 September 13:30-18:30 SAST (11:30-16:30 GMT)
Sunday 16 September 10:00-15:00 SAST ( 8:00-13:00 GMT)

More information is available at http://olympiad.cs.uct.ac.za/#online
We have not yet set up the registration system. I will make another announcement when this is ready, but I wanted to provide advance notice.


In my words:

If you participate in the 2nd round of the SACO (past/present), this is a great opportunity to see how you would have fared in the 3rd round (assuming you haven't progressed of course). If you've done any other programming contest and enjoyed it, if you've even just considered taking part or wanted to, but couldn't for any reason, it's worth a shot.

The online contest is open to everyone, including college students, people already out working in the real world and professors. It's not limited to South Africans, but open to the world. Basically, the only people that cannot compete are those involved in the organisation and those participating in the real contest.

The problems will be identical to those in the real contest. So besides competing off-site and not being eligible for the prizes, it's identical. It would be great to get a good turnout for the first run!

Languages supported are Java, C/C++, Python and Pascal.

UPDATE: Registration is now open. More details here.

Google Sky

My discovery of a flight simulator hidden in Google Earth has drawn lots of attention. I'm glad that this hasn't gone by unnoticed since I think it's a great new feature and has plenty potential to become a full-blown flight simulator.

Before revealing the flight simulator, however, I briefly touched on Google Sky. I didn't elaborate much since I thought everyone who would read my blog would either have already come across it or wouldn't be too interested in it. And I don't like the idea of posting about something that's had it's fair share in the news. However, it appears that Google Sky hasn't been covered as much as I'd thought as a number of people said they hadn't heard of it. So, I'll take this opportunity to comment on it.

This video covers how to use Sky much better than I'd be able to cover with screenshots, so I'll let you watch it before reading my comments:



To switch to sky mode, click View -> Switch to Sky. You should be taken to a view that looks like that in the next screenshot. As you can see you have a basic view of the sky above the position you were in when in earth mode, which in my case was my home town of Cape Town. The star signs are filled in and labeled so you're not completely lost. In the shot below we have Pisces and Aquarius.


The first thing I rushed to look for was full views of galaxies. I'm used to searching for everything so I tried searching for "Milky Way", but no results. Not looking good! However, a search for "galaxy" returns several results (although I was hoping for more). Below is a shot of Google Sky's view of the Whirlpool Galaxy. While arguably better images can be found with a simple image search, it's useful having all this information in one tool (combined with other great tools may I add!).


There's nothing specific to Sky in the places menu, which while disappointing, I guess they will get to adding to it at a later stage. As an alternative, their are some interesting layers. While I haven't explored them in much detail I have noticed that they provide quick jumps to some interesting sites. Below is a shot of what they label "Massive Black Hole". This is somewhere I think this could prove useful as I'm not sure the average person has seen such images.

With the fun aspect of Google Earth and what could be considered educational views at a stretch (they include some details of the sites, more of which I'm sure will come with time). You can also view the planets rotation around the sun (video has a short scene).


While not stunned by Google Sky, I do find it a nice addition to Google Earth. I'd like to see it when they allow for exploration of the planets as is now done for Earth. It doesn't have to be detailed imagery. Then imagine if they grouped this together with the flight simulator and allowed for space travel within a shuttle! Wouldn't that be amazing? The other side of course is Google Ocean. It's been said many times before that we put more effort into space exploration than the bottom of the ocean.

There's so much scope for Google Earth when you start thinking about it. It's nice to see that Google haven't stopped adding to it after it became popular. I just hope they don't overwhelm us with advertising when they realise they need to start profiting, although they've become so good at that that I'd doubt they'd make the wrong move.