Finding the Fiducials

(Ernest's algorithm)

The fiducial finding problem was to locate fiducials on a 360 degree omnicam image and output an Expectation function that reflected the liklihood that a fiducial was located at a certain angle in the view of the omnicam.
Several efforts were made before finding the right algorithm. The first step was to take the original omnicam image, and apply a mask to the parts of the image outside the round mirror and to the center of the image where the camera itself was reflected. Second, a Canny edge detector was applied, producing a binary image of just the edges from the omnicam.
Figure A
The omnicam image masked around the edges and in the center
Figure B
Binary image of edges from omni image filtered with Canny edge detector.
The original idea was to start at the center of the image and walk outwards from the center along a radius, looking for evenly spaced edges corressponding to the fiducials. This step would then be repeated for each radius at intervals of 1 degree. However, it soon became apparant that this is not easy to do because each radius would slice through corners of different pixels, and could skip over some of the detected edges.
Instead, the entire image (Figure B) was scanned, and for each edge pixel found (in white), the distance from the center, R, was calculated, along with the angle at which the edge pixel was found. The output was placed in a kind of accumulator matrix where the rows corresponded to the angle, and the colums were the distance R from the center. The result can be seen in Figure C.
Note that the angle "0" is along the horizontal axis towards the right of the center with the image.
Figure C
The "Accumulator" image. Rows are distance from the center, and columns represent the angle in degrees at which the edge is located.
The Accumulator image presented some difficulties with respect to finding the fiducials. First, the fiducials do not appear as straight, evenly spaced lines, but rather as slightly curved. Also, the curves are not exactly evenly spaced from one another; the spacing depends on the distance of the fiducial from the center of the image.
An algorithm was applied to try to find the fiducials by looking for edge pixels that were approximately evenly spaced. However, there were too many "false positive" fiducials detected from the noise and other edges in the image.
It seemed that if the omnicam image could be processed so that the edges of the fiducials would appear as straight lines in the image, then the fiducials could easily be sorted out from the other edges appearing in the image.
A program was written to take an omnicam image and "unwarp" it using equations from the paper "Single Viewpoint" Catadiotric Cameras" by Baker & Nayar. However, the to capture the entire image, I tried to map the image onto a cylinder that could be "unwrapped" to form a rectangular image. This doesn't work, because the points are mapped on to a curved surface, so they are still distorted. See Figure D.
The omnicam image could processed to get rid of the distortion, so that the fiducials would appear as straight lines, as long as portions of the omnicam were projected on to planes. See Figure E. However, each omnicam image would have to be separated into four or more separate images ( One each for "North, South, East, West" view from the omnicam. )
Figure D
The omnicam image edges projected onto a cylinder, which is then "unrolled" to form rectangular image. The edges of the fiducials still do not appear as lines.
Figure E
The omnicam image projected onto a plane, as if the viewer were standing in the center of the image and looking "South". Here, the edges of the fiducials do appear as lines, but only a portion of the original omnicam 360 degree field of view is visible in the image.
The idea of de-warping the edges of the fiducials into straight lines was dropped. Instead, the original "Accumulator" image of Figure C was filtered so that all stray pixels and verical lines were eliminated. The result is shown in Figure F.
Figure F
The "Accumulator" image, filtered to get rid of vertical lines and stray pixels.
Next, an algorithm transversed the "Accumulator", giving each angle (degrees in increments of 1 degree) a score, based on whether evenly spaced pixels were found. The algorithm checked the ratios of the distance R of the pixels for evenly spaced sets of pixels and sets of pixels that were twice as far apart as other sets of pixels. This corressponded to the top four lines of equal width and bottom two lines of double width on the fiducials. The resulting Expectation function is shown in Figure G. The algorithm does not scan the very top part of the image, where it is more likely to find the top of the door frame than a fiducial. (The fiducials were all hung at approximately chest height.)
Finally, the Expectation function was smoothed by passing a boxcar filter over it, so that the value at each angle is the sum of the values at all angles +/- 10 degrees from that angle.See Figure H.
Figure G
The raw Expectation function at each angle.
Figure H
The smoothed Expectation function angle.


In summary, the final Fiducial Finding Algorithm worked as follows:
1) Input omincam image with appropriate areas masked.
2) Create binary image using output from Canny edge detector.
3) Filter out all vertical lines and stray pixels.
4) Search for fiducials by traversing filtered edge image, looking for sets of pixels with the right spacing. Store the score for each angle in an Expectation row matrix.
5) Smooth the Expectation function by summing the score +/- 10 degrees on either side of each angle.
Back to main page
Last modified: Thu Dec 6 09:59:36 EST 2001