Quagents and Vision


Flippin' 'eck! Is this Quake or the bleedin' Teletubbies?

Reading

Chapters 15, 24, and maybe 25 are a start, but you also may want to look at this Filtering Tutorial.

Our text is among the better general AI texts for computer vision and robotics, but we believe you will probably need other resources. There are loads of computer vision texts and books in the library and for sale, also generations worth of conference proceedings, journals, and of course on-line technical reports and tutorials on individual vision topics. A potentially useful resource (I'd like your opinion!) that includes whole digitized books, such as Computer Vision , by Ballard and Brown, plus sections on many computer vision techniques, is Computer Vision Online , from our old friend Rob Fisher at U. Edinburgh. Some of the links work, some don't. There could be some useful links at Counting Colored Objects , a link down in the section on "possible future projects". Or similarly with the "video surveillance" project.

Assignment

This is a team assignment. Teams of two or three are OK. Make sure there is a chance for each team member to shine. The following suggestions are all classic computer vision problems. Each is still an area of active research. Each has lots of prior literature in books and articles (survey articles are quite useful for getting a picture of what's been tried and what works in what domains). Usually, to make progress, one tries to limit the size of the problem one tackles. Thee and me solve all these problems continuously and quickly, but for now it's advisable to pick one, and further to pick a domain that is supportive of the problem you pick. Part of my problem now is that I have no idea just what the pitfalls in the Quake world are. For one thing it's dark and the colors are kind of muzzy. If the color palette is restricted there's less signal there. Also it's not clear these bots are stable camera platforms...they seem to have a little inherent jiggle that is going to make motion analysis interesting. The images may be very low resolution, which limits the amount of detail available. And so on. You can help by quickly identifying a problem you want to work on and then reporting to me if things seem not to be working out as expected.

Segmentation

Declare what objects (or parts of objects) are ``salient'' and use vision to separate their image evidence from the rest of the image. E.g. if edges and corners are important say to make a line drawing of your environment, find lines. If you want to recognize objects, usually you need to separate their image regions from the background in order to do some sort of matching. This leads you to region-growing (or splitting, or merging) algorithms and to the search for reliable features defining regions. If you are interested in moving objects (for us, other bots), you'd like to find regions in an image stream that represent where the moving objects are. Here's an interesting one: find object (presumably other bots) moving in the environment if you, the observer, are also moving. It can be done. Or you might want to compute depth maps: compute a range image, where the pixels denote range. An obvious thing to try is stereo, where you move your bot, taking images from two positions separated by some baseline. Matching the corresponding pixels of the two images gives you a disparity by which they're separated, and disparity is related to depth. Usually a black-white or color-mapped disparity map image is considered a good-enough final output for stereo.

From Tulane, here is an edge-enhance image made with an edge-finder from Matlab: As Prof Levy states:

I've attached a snapshot showing edge-filtering of a scene in Matlab/Octave, generated with the following code:
client = QuagentClient;:
[bytes,width,height] = look(client);:
a = reshape(bytes(1:4:end), width, height)'; % red plane:
b = edge(a, 'roberts', 12); % from Octave image package:
image(1-b):

Here's The Edge Finder Output

Object recognition

You might want to simplify the segmentation problem somehow (make sure the object of interest is at the center of the image? make sure the background is predictable and you can subtract it...?). Then you could tackle object recognition. How to tell one bot from another, or one item from another? My suggestion here is to use a classic clustering approach. Here are some specific ideas on features and techniques. Another idea that works is a decision tree: make visual tests of increasing difficulty (and presumably decreasing accuracy) until you're sure enough. The brave or foolhardy (Ask Andrew and Justin first!) might want to try a neural net to implement clustering (but you'll have an issue of training). Interesting issues here are: robustness of classification in the face of scale, orientation, lighting changes and obscuration. And of course how many different objects you can recognize. At the heart of the matter usually are the features that you compute.

Tracking

Track another object. Could be something static while observer is moving, or object could move, or both could move. If there is time and power enough, object could be found anew in every frame. Depending on assumptions this can work: but if object disappears temporarily one is embarrassed. This is why we have Kalman filtering, prediction, etc., which allows prediction of where an object is if its signal drops out, and which also smooth noisy data into a more accurate estimate. Also if the object-recognition problem is not trivial, then knowing where to look for it is a leg up. Given you can track another bot, then a good exercise is to follow it (while it walks at random or in a square, etc.). This is good since it closes the control loop between vision and action. Another interesting exercise might be to try to AVOID a tracker, both of you using vision. May be difficult since one must turn to see behind , I guess.

Mapping

This is not my favorite since it is not video, but is is a practical and vision-like problem. Pretend the RAYs facility is a ring of infrared range-finders. These IR sensors are very noisy, so you'll want to add some noise and dropout (certain directions, at random, give you no answer. That can happen either as an error, or of course if there really is nothing out there (in range of the sensor, that is.) You may also want to limit sensor range. Then given you are simulating an IR sensor ring, your job is automatically to make a map of the environment (mainly walls and doors are usually what gets considered here, not items, windows, bots, etc.). Of course with RAYS you have the luxury of knowing what you're seeing, so could, if you want, put items into your map: some laser range sensors can also give you the reflected spectral energy so you could almost imagine doing object recognition that way. Generally, though, the problem is to take noisy data that should originate from walls and grouping it together into line segments so you can draw an accurate map. For this one basic tool that is a favorite in computer vision classes is the Hough Transform.

Free Code!

There is a tar.gz file with raw C source code for alpha-beta and alpha-beta-gamma tracking filters. The meat of such a filter is about four lines long, the rest is various bells and whistles to deal with data dropout, uneven time intervals between readings, etc.

Randal Nelson has an extensive suite of image-analysis tools and other computer vision resources.

Intel has the Open Source Computer Vision Library,, which as both low-level and high-level routines (some care is needed...documentation and function often mysterious).

What to Hand In

Send CB a (strictly private and confidential) review of the performance of each of your teammates if there is anything special that I should know. Thats brown@cs.rochester.edu .

Make sure we can tell who did what in the project. Produce the usual beautiful writeup describing problem, approach, assumptions, results, discussion, and esp. discussion of issues raised by the quake world in particular that might be different in different domains. graphics are nice (screenshots of the domain, objects in the domain, the performance of trackers measured somehow, the raw data and the processed data from map-making etc. Don't forget the references section.

Aim for the goal that your project is so well-conceived, well-done, and well-reported that your report will take its place in the 242 Hall of Fame. I am hoping for ingenious, compelling experiments and conclusions. Create a PDF document of your writeup and upload it to BB.

Write in good scientific style in the form of a computer science technical report. You may find useful this set of advice on writing and homework. There are some example writeups of student projects on the Main Assignment Page .

---
242 Home Page

This page is maintained by Nature Lover

Last update: 1.9.04.