How can you make a computer copy an image by creating a new one with circular blobs of paint? No, it's not the human hand doing the job but a piece of software doing it all by itself.
The solution to this challenge was given in the entries to this year's edition of the Castille Resources & ICT Students Association (ICTSA) Programming Competition that was held over the last weekend of February. It was open to students and developers from local industry.
The aim of the challenge was to approximate images using a small number of circular blobs of paint. The images are all rectangular, with each of their constituent pixels ranging over just eight colours. Facing an empty (white) canvas of the same dimensions as the given image, an artist paints circular blobs of paint (each one possibly covering previously painted ones) in one of the eight possible colours. The challenge the artist faces is to end up with a painting similar to the original one, not using more than a given number of paint blobs. The task was to transform the computer into an artist through software.
The winning team of the students' category is AjaZ (Andrew Said and Julian Zammit), with TDGS (Kyle Pullicino, Adrian Duca, Kurt Portelli and Paul Felice) placing second.
The winner of the industry category is Atlas Insurance Ltd (Karl Fenech) while the second placing went to CasaSoft Ltd (Karl Cassar and Mark Cassar).
The TDGS team is from the Saint Aloysius sixth form, which is quite an achievement when you consider the high level of entries from older participants. The organisers are pushing for the participation by IT students from other educational institutions in Malta apart from University.
"The problem set was a tough one, or rather, although finding a simple solution may not be too difficult, finding an effective algorithm to approximate an image using a limited number of circular blobs of paint is not easy at all," Gordon Pace, lecturer in the Department of Computer Science in the Faculty of ICT at the University of Malta and organiser of the competition explained to i-Tech. "Although closely related to image compression as used, for instance, in jpeg files, the problem was different enough that no off-the-shelf solution can be readily adopted, forcing the participants to find original solutions."
The teams did indeed come up with different original solutions. Some went for a machine learning approach, in which the program tries to "learn" a good solution to the problem instance they are given, while others went for a heuristic or rule-of-thumb approach, which would work in most cases.
Andrew Said and Julian Zammit used a machine learning approach and created a genetic algorithm which mimics natural selection and evolution to find a good solution to the problem.
Karl Fenech was the sole member of the team from Atlas Insurance Ltd. He developed an interesting solution, in which the image was progressively scaled down. The scaled down versions of the image were then used to calculate the best area in which to try to place the next blob of colour.
The organisers are satisfied with the quality of the entries.
"Looking at some of the solutions submitted, the results are really impressive," admits Mr Pace. "I believe that this competition gives the opportunity to good coders to show off their skills, and a context in which they actively compete with their peers. Forcing them to think of a creative solution to a problem, and to work in a team, is another positive aspect of the challenge. In particular, the industry teams found it very motivating to have to solve a difficult, non-standard problem."
This year's participants seem to have experienced the same thrill and fun as the two previous editions held in 2005 and last year.
"It was both hard work and fun," according to Andrew Said, who won the students' category with Julian Zammit. "We worked hard and slept little, but kept a fun casual atmosphere. It helped that we are good friends. If we had entered alone, we both agree that it would not have been as much fun."
Karl Fenech, who won the industry category - himself a University graduate in ICT - agrees it was worth the trouble.
"The hardest part of the challenge was the brevity of the allocated time: a total of 48 hours for devising the heuristic, implementing it as code, testing it, and ironing out any bugs (and, optionally, grabbing a few hours of sleep). The aspect I enjoyed most was the adrenaline rush to produce a good-quality functional solution under the time pressure."
The main sponsor of the competition, Castille Resources Ltd, feels the pulse of the local ICT industry on a daily basis, being a specialist recruitment company in ICT.
"As the main sponsor of the event we are satisfied with the level of corporate and student participation and we were very impressed with the level of effort expended by the teams," commented Matthew Camilleri, director at Castille Resources. "We are keen to create more interest in the competition next year as our contribution towards driving local software developers to excel in these skills and help build Malta's reputation as a centre of excellence in ICT and software development in particular."
Mr Said has this advice for those who are interesting in taking a career in software development.
"If you like software development with a passion, then keeping up to speed with the latest technologies will be fun and rewarding, so being a good software developer will come naturally. The challenge in this line of work is keeping on top of new technologies, and that is what makes a good software developer."
Mr Fenech believes software development puts you right where the action is.
"Software development lies at the forefront of the present day's technological revolution. The most significant breakthrough in the last two decades was the proliferation of the internet, a change which has impacted the very fabric of our societal and personal lives, from self-education (think Wikipedia) to e-commerce to social networking. Software development gives you the opportunity to bring to life the technologies on which tomorrow's world will be run, and that, in my opinion, can provide you with a unique sense of career fulfilment."
Full details on the submissions and judges' report are available from www.cs.um.edu.mt/gordon.pace/Workshops/ICTSAPC2010/.