Special Project: Visual Search Routines

In this project we will design some primitives for performing the sort of visual searches discussed in Shimon Ullman's Visual Routines paper.

Radial Search

A radial search sweeps a ray clockwise or counterclockwise from a starting point until the ray either intersects an object or reaches a termination point. A radial search can be used to find a "leftmost" object, or the object "just to the right" of another object, from the agent's point of view. From this polar perspective, "leftmost" does not necessarily correspond to something like "minimum x coordinate".
Point radialSearch(const Point &origin, const Point &startPt, const Point &endPt, Sketch sketch);

ShapeRoot radialSearch(ShapeRoot &origin, const Point &startPt, const Point &endPt, const UnaryShapePred &pred);
  • origin is the place from which the search ray emanates.
  • startPt and endPt are points hit by the ray at the start and end of the search, respectively.
  • sketch is a sketch to be searched until the ray hits a non-zero value.
  • pred is s unary shape predicate. In the second form of radialSearch, where origin is a shape, that shape's shapespace is searched for a shape that satisfied pred.

Contour Tracing Search

A contour tracing search sweeps an attentional spotlight along a contour until the spotlight intersects something of interest, or the end of the contour is reached. A contour tracing search can be used to answer questions such as "does this curve intersect more than one X"? See Ullman's figures 11 and 17 for examples.

Project Steps

Step 1

  1. Comment on the radialSearch method specification. Has anything been omitted? What is the best algorithm to use for each of the two forms of this method?

  2. Flesh out the contour tracing search idea. As for radial search, we want one version that works on sketches and another that works on shapes. What arguments should each method take? What is the best algorithm to use for each method?

Step 2

  1. Implement your own versions of the radialSearch and contourTrace methods, and test them on some representative examples.

  2. Prepare a brief (1-2 page) writeup describing the approach you took, any limitations or drawbacks you can identify, and your results.

  3. Due by Friday, March 8. (People leaving town should hand this in by the 7th.)
Dave Touretzky
Last modified: Fri Mar 1 04:54:24 EST 2013