Western University Computer ScienceWestern Science

    Award Winning Research

    Road Lab Research Project

    Our faculty are dedicated to achieving excellence in computer science research, making significant contributions at research centres around the world. Did you know that between 2003 and 2007, Western ranked third in Canada and second in Ontario for the impact that its research papers had on the fields of Computer Science and Engineering. The scoring takes into account the average citations per paper among universities publishing 50 or more papers in Thomson Reuters-indexed journals. In this survey, Western was only behind UBC and the University of Toronto for number of cited journal articles and papers!

    Below is a sampling of some of the fascinating research that is being conducted at Western University's Computer Science department:

    Making record albums play WITHOUT the needle touching the record!

    Are you old enough to remember what a "Record Player" is? Could this antiquated machine actually be of interest to computer vision researchers? Baozhong Tian, a former PhD student of Professor John Barron, used a digital microscope and a turntable to ‘play a record’ in a non-contact way by using optical flow to recover the orientation of the record groove’s walls. This technique could allow music buffs to hear the music without further scratching treasured albums.

    Can computers figure out what an image is representing?

    Have you ever looked at a Picasso painting and wondering "What was he trying to represent, I don't get this painting at all!". That is kind of what happens when a computer looks at a bunch of pixels. Western computer vision researchers, like award-winning Dr. Yuri Boykov, are creating algorithms that will allow a computer to really ‘see’ an image and interpret what it represents, rather than just viewing it as a series of pixels - exactly like human beings do when we look at a painting and try to figure out what Picasso meant when he painted it. Want to learn more? Come to Western and take some of our fascinating Computer Science vision courses!

    One gram (cubic centimetre) of DNA can store as much information as one trillion CDs!

    In traditional computers, we use electrical currents to represent 1s & 0s. These 1s & 0s are used to represent numbers, characters, colours, sound, pictures, basically our world, on a computer. What if we could use something other than electrical currents to represent our world? How about using DNA to represent data? DNA would take up a lot less space and energy. Western is honoured to have world renowned researcher Dr. Lila Kari, one of the leading researcher in DNA computing, working here.

    MRI Images vs. Ultrascan Images

    - Let the battle begin!
    The gold standard for tissue imaging is Magnetic Resonance Imaging (MRI) but MRIs can be very expensive. Is there a way to get ultrasound machines, which are far less costly to run, to produce results which are comparable to MRIs? This is what award-winning researcher and professor Dr. Mahmoud El-Sakka is investigating in his current research. He is using ultrasound scans of his own heart as data for his experiments. He is really putting his heart into his work!

    Improving the reliability of software

    If the software controlling your car’s brakes takes 10 milliseconds to run when it should have taken 8 milliseconds, bad things can happen. Trying to prove that software meets its constraints currently relies on testing. However, testing is never 100% guaranteed. Dr. Mike Burrell, a Western PhD graduate, was developing programming languages that allow us to prove things about the software with 100% certainty, which in the future, may save money, time and even lives!

    How many cars can we "pack" onto a ferry boat?

    Have you ever had to wait for the Chi-Cheemaun Ferry to Manitoulin Island? If the ferry is really busy, you might have to wait five hours for the next boat! Have you noticed how many differently sized cars, trucks, vans and trailers can be packed into the loading area? Perhaps if we sort the vehicles in a different order, we could add more cars. This is just one of several possible applications for award winning professor Dr. Roberto Solis-Oba’s research on rectangular box packing algorithms.

    Say YES to Roles, say NO to Top Secret!

    In James Bond movies since the 1960's we have heard how the MI5 and the CIA protect their information using the terms unclassified, classified, secret and the very hush-hush TOP SECRET. But perhaps there is a better way to protect our secrets. Top database researcher Dr. Sylvia Osborn has been playing around with "Roles": how to grant access to those roles and how to assign users to the roles in order to protect database items such as tables. This newer form of access control is now being incorporated into many databases such as DB2 and is commonplace in Oracle.

    Patent Chores and Patent Wars

    On March 3, 2006 RIM and NTP announced they had come to an agreement over a software patent dispute. After a hard fought battle in the United States RIM agreed to settle by paying NTP 612 million dollars! Under what conditions can computer scientists get patents on their work? Should universities aim to patent professors' research, and for what purpose? How do software patent laws differ in Canada and the United States? What changes are in the pipeline? These are the kind of issues that Professor Mark Perry, Western Law's Associate Dean Research and also a Computer Science professor at Western, researches everyday. Come to Western and take the "Computer Science and the Law" course to find out more!

    Easy-To-Use Design May Miss the Mark

    An easy-to-use interface is ALWAYS the best choice for a software application, right? Think again! Dr. Kamran Sedig's experiments with children playing with tangrams may prove otherwise. If the point of the software is to teach the user how to use his/her brain and to expand the user's learning capacity, then making the interface too easy may actually have the opposite effect! Western's expert on design and interaction, Dr. Sedig, is doing research that is making the world's software community re-examine interface design. Take his fourth year Human Computer Interface course to learn more.

    "Getting information off the Internet is like taking a drink from a fire hydrant" ~Mitch Kapor

    "If it is in print, then it must be true". Not necessarily! Often times someone reads an exciting new research paper and is skeptical of the paper's amazing result. Then the reader might want to see if the writer cited or referenced another paper that disputed the writer's conclusions. Wouldn't it be nice if an automated tool existed that could classify all the references and the reader could just check all the cited papers in, for example, the "Contradicting Citations" category. This tool could even be used by Google to improve their search returns. Dr. Robert Mercer and his colleague at the University of Waterloo and their combined graduate students are working on automating the classification of citations, an idea that has been around since the 1960s but even today, is mainly performed by hand.

    Why are the characters in my video game acting crazy?

    Have you ever played a video game and wondered "Why was that character rescuing me 10 seconds ago and now he is trying to kill me? Can't he remember that I am on his side?" It is EXTREMELY difficult for game designers to create characters who truly behave like real people would behave. For example, characters in video games don't remember that what they did 10 seconds earlier because programmers have not yet put the capability to remember into characters in most video games. Programmers are often so focused on putting their efforts into creating realistic LOOKING characters that they often forget to also make the characters ACT realistically. Dr. Mike Katchabaw is trying to change this in order to create a better and more fun gaming experience for hard core gamers!

    Save health care dollars AND increase patients survival chances? Wait a minute, what does this have to do with Computer Science?

    Can we improve patient outcomes AND cut health care costs. Dr. Charles Ling, an award winning professor at Western, is just crazy enough to take on this daunting challenge. His research studies the costs and benefits of the ordering, timing and selection of tests performed on patients. Perhaps if we run cheaper tests first (such as taking a patient's temperature) BEFORE we do the expensive ones (such as MRIs) maybe we can still have the same final outcome. Perhaps in other cases, the situation is so dire that we must do the most expensive one, but we will have a better outcome and lifestyle for the patient if we group it with other tests at the same time (thus the patient doesn't have to make as many trips to the hospital). Dr. Ling is using data on actual cardiac patients to test out his algorithms and improve patient results. OHIP might be surprised when they realize they should come to computer scientists for help with their budget!

    Doctors aren't the only ones whose handwriting has to be deciphered. Mathematicians need some help too!

    With writing tablets becoming more and more prevalent (have you heard of a little invention called the iPad?), there is a greater need for GOOD handwriting recognition software. Many thousands of hours of effort have gone into recognizing handwritten stories, letters and manuscripts, but there has been little research into the area of recognizing handwritten mathematical formulas. One critical road block in mathematical handwriting recognition is the lack of a standard dictionary. For example, the sample of writing in the image to the upper left could be either the letters "hello" or the letters "hdbo". Researchers can use an English dictionary to guess that the writer probably meant hello rather than hdbo. However, when writing math formulas (image to the lower left) no such dictionary exists, so researchers are left high and dry and must come up with other ways to make good guesses at what symbols the handwritten formula represents. World renowned computer algerbra researcher and professor, Dr. Stephen Watt, and his team are at the forefront of this research area. It has generated so much excitement that several undergraduate students have chosen parts of his research as the basis for their 4th year theses and summer internships.

    Elvis has NOT left the building but we don't know which floor he is on!

    There have been many advances in global positioning outdoors, but a big obstacle in 20 years of research in indoor positioning strategies is the question of which floor of a building someone is on. Some looked at adding devices to the building to help find the person but this strategy required extra money, time and effort to install the devices. Wouldn't it be nicer if we could utilize devices that are already in buildings such as WiFis networks? Some research had been done using WiFi networks but there were still issues in determining the actual floor someone was on UNTIL Dr. Hanan Lutfiyya and one of her students, Nathan Lemieux, came up with a brilliant idea! They not only collected information about the strength of the WiFi signal to figure out a position in the building, they also bought a very inexpensive altimeter to measure the barometric pressure of the position. This one extra tweak gave them some amazing test results in several large buildings on the Western campus. Who knows, they might even find Elvis yet.

    We have to understand what caused the disease before we can find the cure!

    Diseases such as schizophrenia, depression and bipolar disorders are often so complex that it is hard to pinpoint what caused them. If we look at the human genome, is it the number of mutations in the sequence that causes an illness? Or perhaps the illness is caused by the profoundness of a particular mutation? Or maybe is the problem in how it is processed? Dr. Peter Rogan, a biochemist with a cross appointment in both the Biochemistry department and the Computer Science department, believes both the breadth and depth of the mutations must be studied in order to detect and cure these illnesses. His lab studies mutations in DNA that affect how that DNA is processed, as well as mutations that change the DNA's final product. This is just one of the areas he and his graduate students are examining when they study the human genome at Western.

    Can we make this bag any smaller?

    Think of putting all your clothes in a plastic bag and then using a vacuum to suck the air out of the bag. This process can halve the size of the bag. When working with computer images, we have to do the same thing to the image. If we tried to send an uncompressed ("un-sucked") image over the Internet, it would take a long time to download. So much research into image compression has taken place that you would think there couldn't be any new ways to compress. NOT TRUE! Dr Mahmoud El-Sakka looked at how a dictionary of words is compressed for the computer, and applied those principles to the compression of images. He has had some remarkable results, getting better compression results than a lot of widely used compression algorithms. Get a smaller suitcase, at Western we might be able to compress those clothes even more!

    Why is geometry often described as cold and dry?

    The famous Mathematician Benoit Mandelbrot pondered and posed the above question in 1984. He believed one reason was in its inability to describe the shape of a cloud, a mountain, a coastline or a tree. In the early 80's he discovered a set of mathematical points on the complex plane that when graphed, created fractals: bizarre, amazing, beautiful shapes such as the one to the left. The points are created by a type of polynomial expression that, when iterated, remains bounded, i.e. does not create numbers that go outside of a boundary. Dr. Robert Corless, a world renowned mathematician and applied math professor at Western, was fortunate enough to meet Dr. Mandelbrot in the United States. This encounter led Dr Corless to study the roots of polynomials and algorithms that find the "stability" of a polynomial. He defines a stabile polynomial as a good numerical method that gives you an exact solution to a nearby problem. While pure mathematicians are not thrilled with the vague term "nearby", Dr. Corless says applied mathematicians LOVE this term because it means the mathematician can apply context of the problem. Why does this all matter, well, have you heard of a little upstart company called Google? They use some of this theoretical math in their page ranking algorithm, the algorithm that determines which pages are displayed first to a searching user!

    Getting from A to B is not as easy as you might think!

    Take a piece of graph paper. Draw a small shape called A somewhere on the far left of the paper. Draw another small shape called B somewhere on the far right of the paper. Draw a small rectangle somewhere in between the two shapes to block the direct path from shape A to shape B. Then imagine all the ways you could maneuver shape A to get to shape B. Even in a simplified 2-D world, there are lots of possibilities. Now let's make this a bit more tricky: imagine a hand reaching for a donut on a table. The wrist could turn, the elbow could swing, the shoulder could rotate and the fingers could open and close. Things get complicated very quickly, in fact the complexity doesn't just grow exponentially, it starts to grow double exponentially. One of Western's most prominent and award winning computer scientists and researchers, Dr. Eric Schost, is trying to reduce the complexity by using shapes, silhouettes, projections, shadows and lots of mathematics to simplify our world. He will figure out how to get your hand to that donut before the donut gets stale!

    Can we solve a scheduling nightmare?

    Have you ever tried to schedule your baseball playoffs? You have to worry about making sure every team plays every other team, how many baseball diamonds are available, what times will the game start, what to do if one game goes into extra innings. All these kinds of variables make scheduling problems very difficult (or as they say in Computer Science: NP Hard) types of problems to solve. Dr. Roberto Solis Oba (one of Western's best professors at explaining complex algorithms, our students say!) is using approximation algorithms and clever ordering techniques to get solutions to scheduling problems. The final solution for a given scheduling problem may not be the optimal solution, but it will approach the optimal solution. The trick is that the problems he is dealing with MUST adhere to three requirements for his algorithm to work. Come to Western and do your PhD or Masters with Dr. Solis Oba to find out what those three requirements are!

    Does sugar grow on trees? At a molecular level, it does!

    Protein is one of the building blocks of life. Proteins need sugar to function. Biochemists have found that the sugar attaches to proteins in tree-like structures. Sometimes, in abnormal situations such as cancer or HIV, the trees bind to the protein in such a way that the disease can avoid attacks from antibodies. Currently, well-trained biochemists using mass spectrometers manually identify the tree types. Dr. Kaizhong Zhang and three colleagues have created software to automate this process, thus opening the door for mass data collection and analysis of protein. So far, experiments with this new software have a 7 in 8 success rate at identifying the correct tree structures. In fact, for the 8th tree, it is unclear if the biochemist identified it correctly, or if perhaps Dr. Zhang's software actually had it right. Want to contribute to the cure of many diseases? Why not come to Western and do a double major in Biochemistry and Computer Science and learn more about Dr. Zhang's amazing research!

    This is your brain on graphs!

    Researchers have several different ways to study the brain. One common way is to use magnetic resonance imaging (MRI). In an MRI scan, the brain is divided into voxels; voxels are used to describe 1mm by 1mm by 1mm areas of the brain (about the size of a coarse grain of sea salt). When these voxels are combined we get a 3D image of the brain. A functional MRI scan can describe the flow of blood within these voxels. One of our professors, Mark Daley, decided that a PhD in computer science wasn't enough and decided to take an educational leave to also get a Masters degree in Neuroscience. He used his computer science background in graph theory to analyse patterns in the flow of blood in the brain. Dr Daley converted the voxels into an enormous graph of nodes (where each node represents a voxel) and edges (representing the connections between voxels with similar patterns of blood flow). He then used his background in matrix anaylsis and graph theory to evaluate the brain while resting (not sleeping but not active) to see what was occurring at various locations within the brain. These graphs are so big that they require the world's largest and most powerful computers to process them. Interested in computer science, graphs, matrices and doing research that might change the way we understand the human brain? Then why not come to Western for computer science!

    The eye movements of an automobile driver can reveal a lot!

    Award winning professor Dr. Steven Beauchemin’s computer vision research can be used for many applications, but perhaps one of the most beneficial involves something most of us use every day: a car. He and his graduate students are using computer vision techniques to improve driving safety with on-road vehicles. This includes detecting pedestrians, involuntary lane changes and monitoring driver facial expressions and eye movements as shown to the left. The goal is to use computer vision and robotics to improve road safety.