Watching Sports Your Way

One option for my Masters thesis is to explore the use of computer vision in a real industrial production system. Thinking in terms of sportscasts, on the simplest end, one could automatically track players and objects (remember that annoying -- and short lived -- blue highlighted hockey puck?). On the more ambitious end, broadcasters might be able to give viewers novel and exciting viewpoints, such as a particular play from a particular player's perspective.

Imagine my disappointment in seeing that the latter had seemingly been solved already (assuming the former is relatively simple in comparison). I was recently directed to a copy of a paper called Virtual Viewpoint Replay for a Soccer Match by View Interpolation From Multiple Cameras by Naho Inamoto and Hideo Saito, where I found not only Inamoto and Saito's work on the topic, but of course, many references to related research, as well.

Ok, so maybe it's not really such a surprise that work on this area has been done in the past -- it would be naive to think otherwise [:)]. But at first glance, this paper seems to cover a method that might be well suited to the broadcast industry, thereby coming much closer to the realm of my possible thesis topic. But as we will see, there is still much room for improvement, and therefore still work available if I do end up taking this direction.

What It's All About

The basic premise of this research is to be able to watch a sports game (soccer in the case of this particular paper) from angles that weren't explicitly captured on camera. Computer vision techniques would be employed to determine what an intermediate camera between two real ones would be seeing. A user of an on-demand video system could potentially guide his own camera and see the entire game from that viewpoint, or a broadcaster could simply present a new and interesting shot of a particular play for the audience.

In the past, the methods used to synthesize these new shots fit into three categories (according to Inamoto and Saito):

1. Model Based Approach. Using the geometry of the scene, a 3-D reconstruction with a synthesized texture could be created and then reprojected into the desired novel view. The accuracy of the results depends on how well the model can be constructed, which in turn depends on having many calibrated cameras. This method is not well suited to large areas like a soccer stadium.
   
   
2. Transfer Based Approach. Instead of a 3-D model, morphing techniques can be employed to obtain the new viewpoint between two images, or a trifocal tensor can be used for image transfer. Either of these require dense correspondences between the known views, hence the two known images must be static or only slightly varying.
   
   
3. Approach Using the Plenoptic Function. The plenoptic function "describes all the radiant energy that is perceived by an observer at any point in space and time." With this function, it is possible to allow users to arbitrarily pan and tilt a virtual camera, and the resulting shots will be based on a collection of sample images. Since the plenoptic function is seven dimensions, though, it requires data reduction or compression in practical use. This makes it less suitable for the soccer example because it would be impossible to describe all the radiant energy in the stadium scene.

The New Research

Inamoto and Saito's proposed method generates images of arbitrary viewpoints "by view interpolation among real camera images." Multiple cameras will be capturing a soccer match, and when a user chooses a new virtual viewpoint, the two or three cameras closest to it are used to find correspondences and perform view interpolation. Because the field and the soccer stadium itself are fixed, they can be considered static, and processed separately from the dynamic objects (players, the ball, etc). Furthermore, much of the processing time can be done ahead of time, including the determination of the camera geometry.

Several videos that show the results of this method can be found on this research web page. In addition to simply creating new viewpoints for the user, the videos demonstrate that the method allows for effects like that seen in The Matrix, where the camera spins around stationary players.

The performance of a developed system using this method was tested on a Pentium 4 3.2 GHz desktop with 2 GB of memory and an ATI Radeon 9800 graphics card. On average, the system could process 3.7 frames every second. The processing time is linear in the number of dynamic objects contained in a scene at a given time.

What It Means For Me

Here I'd like to discuss some aspects of the reported research that I'm not sure would be entirely suitable for the production industry, and could thus be interesting areas for me the explore for my thesis. Some of these I have not mentioned above, but are still part of the discussed research, and more information can be found in the associated paper.

It's worth noting that, being Canadian, we wanted to explore the application of virtual viewpoints in the context of hockey games rather than soccer. How cool would it be to put yourself in Daniel Alfredsson's skates as he flies to the net and puts a puck in top shelf?! Keep this context in mind as you read the issues I raise below.

First, the proposed method requires that several cameras are fixed and calibrated ahead of time. The first problem with this is not too serious: there is a requirement for the stadium or arena to invest in more cameras. This is due to the fact that almost all cameras at a sports event are constantly moving to follow the action or to switch its focus to another point of interest. It is possible that this is a reasonable investment, provided that the results are worth the extra money. As will be discussed in a moment, this certainly isn't the case at this stage.

The second issue with fixed cameras could, in my opinion, be slightly more problematic. The manual work required to calibrate these cameras requires broadcasting technicians to spend time identifying corresponding points between the cameras, and identifying the static regions (such as the field or stadium in the case of soccer) in the image captured by every camera. This work takes an hour for just four cameras, and you may need more cameras than that to get a high quality result. Now, this extra work may not be relevant after all if you consider that once the cameras are calibrated, they don't need to be calibrated again because they are fixed. I'm just wondering whether there is the possibility of these cameras being taken away at the end of each game, thus forcing this task to be redone before the next game when the cameras are replaced. The possibility of human error each time could seriously affect the results for that game; for example, being slightly off on the point correspondences throws off the whole geometry of the cameras!

Next, consider a requirement that allows soccer players to be identified on the field. It is essential that the color of the ball and the players (including the uniform) be different from the field. It would seem that most soccer teams have jerseys that avoid this problem, but this is certainly not the case in hockey. Even my favorite hockey team wears white on away games, so it would be difficult to distinguish between the jersey and the white ice surface. I also believe there could be new issues when using this method for hockey related to the reflectivity of the ice. Surely the light absorbing properties of ice and turf are different, so shadows might need to be handled differently, and reflections might get in the way.

Finally, the critical issues outlined in the paper must be addressed before such a system could be used for real broadcasting. For example, players can occasionally disappear from the scene when they have not been filmed in at least two of the cameras. Problems also occur when four or five players overlap. While this may not happen quite as often on a wide open soccer field, the smaller hockey rink would have this happen all the time!

Conclusion

It's pretty clear that the issues outlined here, as well as generally improving the speed and quality of the resulting virtual video, provide a lot of potential research for an enthusiastic Masters student such as myself. I'll let you all know what I end up doing for my thesis as soon as I know!

Read the question

I recently finished grading my very first batch of assignments as a teaching assistant. Previously I had worked as a special kind of "general help" teaching assistant that wasn't assigned to any particular course, so I didn't needed to mark anything before this semester.

Most students fared rather well on their first attempt at understanding functional programming using Scheme. In fact, I only gave one failure, though it was clear this person either forgot to do the assignment until 30 seconds before it was due, or simply planned to drop the course soon anyway. A grand 1% is what they earned. By and large, the class did a good job.

But they could have done better if only they had read the questions more carefully!

Everybody forget something. Maybe it was the substitution model they were supposed to show for their multiply procedure. Or maybe they missed the fact that they were supposed to program in an iterative style. Perhaps they ignored the fact that 25% of the grade was specifically allotted for testing and documentation.

This kind of thing is common, but I never realized how many students it affected until I marked all of their work.

Ah well -- my many comments will hopefully serve as a reminder to be more careful in the next few assignments, and if nothing else, I now know myself to reread my own assignments a few times more before rushing to answer!

Heap Trick

I learned a neat trick regarding heaps today. Here's how it goes:

• Take the number of nodes in the heap and write that number down in binary.
• Erase the most significant bit.
• Starting at the root, go to the left child when you see a zero, and go to the right child when you see a one.
• When you run out of binary digits, you will be at the last node.

So if you don't feel like storing a pointer to the last node in a heap, you can use this little trick instead. Try it, it works!

Blondie24: Playing at the Edge of AI

Imagine this scenario: You have recently befriended a visitor from Mars. Martians have no knowledge of human culture, let alone any experience with our board games. But somehow your new pal has heard of checkers and desperately wants to learn how to play. So much so, in fact, that you question his "friendship" as he demands success while waving around his ray gun menacingly.

An uneasy situation to be sure, but what if in addition to having to teach the visitor far from home how to play checkers from scratch, eventually making him an expert player, the only information you were allowed to tell him is where the game pieces were allowed to be on the board and how they were allowed to be moved. After a series of games, you would tell him how many games he had won, but not which games they were.

Could you do it?

David B. Fogel faced this very same challenge, albeit without the Martians and ray guns. Instead, Fogel aimed to have a computer learn the game of checkers in this very same way. We all know how dense computers are -- they certainly won't do anything other than exactly what you tell them -- so we can see that this task is still daunting nonetheless.

In Blondie24: Playing at the Edge of AI, Fogel describes how he used evolutionary computing algorithms to have a computer teach itself checkers. In the process, he manages to give a good introduction and general review of the state of artificial intelligence, to provide interesting insight into what it truly means for software to act intelligent, and to detail how he and his colleague Kumar Chellapilla managed to evolve a neural network that could play checkers competitively with the experts.

If you have studied AI at all in the past, then you probably remember spending a lot of time on subjects like decision trees, expert systems, and search tree algorithms such as A*. Indeed, topics like these seem to be at the forefront of the field, and capturing human knowledge and reusing it in an effective way constitutes, for many, the essence of artificial intelligence.

But does the use of our own knowledge really demonstrate intelligence? As Fogel points out, not really. These kinds of programs are simply acting like we do. They make no contribution to understanding what intelligence really is, nor how it develops in the first place.

Fogel offers an alternative. He believes that mimicking what nature has done so well is the key to having software learn for itself; that is, we should be focusing on evolution.

And that's exactly what Fogel uses to create a checkers program that can win against very high ranking players. He sets up a neural network with a somewhat arbitrary configuration, using the piece placement on the squares of a checkerboard as inputs. Several networks are created with random weights between neurons; this becomes the first generation in the evolutionary process.

The networks play against each other based on the most basic rules of how pieces can move from particular squares and when the game is over. They don't know when they lose or win a game; instead, they are assigned a final score for the series of games they have played. Then the half of the generation with the lowest scores is thrown out. The better half is copied and slightly randomly mutated. This new set of neural networks becomes the next generation, and the process begins again.

I'm definitely simplifying things here (for one thing, the neural networks don't play checkers, but rather evaluate a particular board configuration), but suffice it to say that these neural networks, after many generations of evolution, could actually play checkers very well. This is quite remarkable if you think about it -- just from random mutation and survival of the fittest, we start with something more or less random that knows nothing about checkers, and eventually get something that can beat some of the best. Nowhere have we instilled our own human expertise or knowledge into the program like the creators of Chinook did, or those of Deep Blue in the case of chess.

If you are the least bit curious of the details on how Fogel and Chellapilla achieved this, I highly recommend reading his book. I couldn't help myself feeling at least as enthralled with the progress of the artificial checkers player as I have with any fictional protagonist. Fogel does a wonderful job of providing the necessary background of the field, and repeats the key points just enough so the reader doesn't get lost.

More importantly, I hope you can share in the excitement surrounding the possibilities of evolutionary computing. Though it's been around for decades, I'm not sure that it's been used to anywhere near its potential. As hardware speeds up and complicated problems can be evolved more efficiently, we might find ourselves being able to create something closer and closer to true intelligence.

If you ask me, this sounds a bit less frustrating (or dangerous) than trying to do the same with our extra terrestrial companions mentioned earlier...

Creating Mazes from Images

This semester, I'm taking a systems engineering course for my Masters. It's called Entertainment Technology, and aims to cover some pretty interesting stuff, from image processing and compositing, to using accelerometers like those in the Wii remotes, to watermarking and other content protection schemes.

In a couple of weeks, we will be giving a presentation to our classmates on a technical paper of our choice. Mine will be Image-Guided Maze Construction by Jie Xu and Craig Kaplan from the University of Waterloo. Since the topic is pretty cool, I thought I'd share what it's all about!

Artists have long been creating beautifully artistic mazes. Take Christopher Berg as a modern example. He's been at it since the fifth grade, starting with countless varieties of amoebas as the basis for his mazes. Check out some of his more recent marvels, found on the Amazeing Art website:



Xu and Kaplan state early on that Berg was an inspiration for them. Unfortunately, the techniques that Berg uses to draw his mazes don't translate well to computational algorithms. The computer (with some help from the maze designer) must create lines that will artistically convey the tone, texture, and form of the original image. But in addition to this, there must be spaces between the lines that actually make the drawing a maze!

In an interactive system designed by Xu and Kaplan, a maze designer is able to identify various areas of the image they want to turn into a maze. Each of these regions can have a particular texture applied to them; that is, the maze can follow the general direction of lines in the original image, spiral in on itself, have random direction, or be completely user-defined. Once the mazes in these regions are created, they will be interconnected by breaking a hole in the "walls" between the regions. In addition, the designer can plan out a general solution path to ensure both an interesting and challenging puzzle.

To see how to construct a maze algorithmically, you can first imagine a grid laid out within the area the maze will be created (a planar subdivision). The faces of the grid (which isn't necessarily orthogonal) are called cells, where the edges between two adjacent cells are called cell walls.

Next, consider the dual of the grid, the cell graph, where each cell is represented by a vertex, and cells that share a wall are connected by an edge. Now if you want to get a maze from the grid that doesn't contain any cycles, you simply need to find a spanning tree of this dual and erase the walls between cells connected by the spanning tree in the cell graph. A random spanning tree could be generated, or certain walls could be biased such that they are more likely to be broken first.

Finally, notice that the four maze textures described above can be used to create the grid from which to generate a maze.

In the case of directional mazes, the walls of the maze should flow in a general direction that resembles what it happening in the image the maze is based on. This is done using vector fields, from which "streamlines" are placed. Then, streamlines perpendicular to these are added, thus creating a grid. The distance between the streamlines can be adjusted, helping depict the desired tone.

For regions marked to have spiral textures, the computer will create shrinking concentric rings of the boundary shape. Radial lines are added at regular intervals to complete the grid.

The random texture is created first as a square grid, and then relaxed using an algorithm created by Singh and Pederson. User defined textures obviously must be created by the maze designer.

Here are some examples of what Xu and Kaplan's system have created, taken from their maze design project page: