To: hansen,dimitris,lohnert,priem,williams cc: hpm,mcm@cs.cmu.edu,dellaert@cs.cmu.edu Subject: neat 3D grid sensor model learning criterion From: Hans Moravec Reply-to: hpm@cmu.edu FCC: ~/Mail/MAILOUT --text follows this line-- Here's a new idea for measuring the quality of a stereo derived 3D grid that evolved in a discussion with Volker yesterday. It is easily the best yet, and interesting enough to be described even before it's implemented. The backgound: The stereo-grid approach produced some pretty encouraging results in its first runs, with sensor models pulled out of the air, but could obviously be improved, perhaps dramatically, with a less arbitrary choice of model. I hoped to let a learning process loose on parameters of the model, guided by some resulting map-goodness criterion. In several weeks I failed to find a good learning criterion among measures that compute various kinds of local solidity in the grid data. Some drove the grid to zero density, others filled it with noise. Some had parameters that could be adjusted between these extremes, or to achieve some specified average density, but none were convincingly measures of the correct answer. I had almost despaired of finding an unsupervised learning criterion, and was preparing to hand massage the best 3D grids so far to produce the best 3D ground-truth model possible for a supervised criterion. Volker yesterday reminded me that we have a kind of ground truth in the original images, albeit in 2D projection, with surface color. The grid, on the other hand, is 3D, and has no color. It is easy to project the grid's 3D into 2D, recreating the geometry of the original images, but without color the grid projections convey little information. But color for the grid can also be derived from images! The plan: To evaluate a newly constructed 3D grid, divide the images from which it was derived (via a trial sensor model) into a "coloring" set and an "evaluation" set. In my 20-pair office data, I will probably use the images from more forward positions for coloring, and those looking from the back for evaluation. Scan the 3D grid from far to near (e.g. from top and bottom towards camera height), and make a list of positive ("occupied") cells in scan order. Typically my 4-million-cell grids have a manageable 100 thousand positive cells. Each element of this list gets the grid coordinates of the cell, and also an, initially blank, "cell color" slot. Project the cells in the list into the geometry of each of the "coloring" images, producing corresponding synthetic images where each pixel indicates the identity of the closest occupied cell visible at that position, or nothing if no cell projects there. Run through the synthetic images, and at each non-empty pixel average the color of the corresponding pixel of its "coloring" image into the "cell color" variable of the indicated cell. When done, each cell in the "occupied" list will have an associated color, averaged over all the images in which its was (probably) visible. Now project the colorized grid into the geometry of the "evaluation" images, and evaluate similarity. The process is like the colorization, but instead of averaging the original image color with the cell color, the two are compared. If they are sufficiently close, the comparison counts a +1, too different, and the comparison scores as -1. Pixels that have no cell label, or whose corresponding cell has no color, score as 0. The overall score is the sum of this measure over all the evaluation images. I can think of a lot of reasons why this is a great way to measure grid quality. For one, it uses information and measures interesting qualities not used in the original grid construction. For the initial implementation, I will probably use the monochrome images, averaged down to half size, to do the (grayscale) coloring and evaluation. I have color versions of the images, and could use those later. A very interesting side benefit of the colorization process is a grid with the original scene colors, which should be very interesting to view. -- Hans Moravec August 6, 1996