A: Crossing Detection
The first step in the processing of this image is the recovery of the grid points - which are the corner points of the squares used in the PRBA. This recovery is based on the response to a matched filter. In the matched filter a priori knowledge on the pattern looked for is used. In this case the regular structure and the size of the black squares represents the a priori knowledge.

Assuming that the squares are presented in 7 x 7 pixels the corresponding matched filter is given here. Black squares to the upper left and lower right with respect to the central pixel will yield a local maximum. In the opposite case a local minimum will be found. The crossing looked for is than easily defined as the point of the input image at which the convolution of this filter with the original image gives a (local) maximum absolute response. The locality of the maximum response is in turn defined by the size of the stimulus used. The (odd) size of the filter and size of area over which the maximum response is sought is a user definable parameter.

Based on this matched filter analysis we are capable of recovering the edge points of the squares in the image and assigning an attribute to them namely the direction of the color vector. This can be directed along the line y=x or y=-x as shown in this diagram. Note that this identifies which squares are colored but not how they are colored. To do so the K-means clustering algorithm Hartigan75 is used which separates the colors as much as possible in two groups. Based on this cluster algorithm a tentative color assignment of the squares is done. This results in the following attribute of the grid point: the two color points at the end of the direction vector.
Thus upon completion of the first phase of the image analysis a table is build in which each element has the following structure:

        index, (x, y), direction_bit, color_bit_1, color_bit_2

Theoretically Data Explorer has all the ingredients to implement this procedure on the high, visual, level. However we have chosen to implement it as a series of C based routines, which are bundled into one new icon called Crossing. As most important input Crossing takes the original tiff image separated into its three color fields (using the Mark option). All other parameters are defaulted at realistic values and in theory need not be set by the user. Therefore their default behavior is marked as hidden. They are dealing with characteristics properties of the stimulus and the colors used.
Two outputs are propagated: an image in which all the points found are marked, and the list as mentioned earlier is propagated as a Group. Of the former image the results for our two sample images is given A and B . The minimal program doing this work is shown in this sample. Note that since the coordinates of the points found are expressed in terms of the original tiff input image, they can readily be merged for inspection. This is shown in the following image. At this point in the analysis it is not possible to discriminate between true points and false positive points.

B: Graph recovery
For the graph recovery we are going to utilize the attribute set which has been accumulated in the previous phase and use it heavily to get a consistent graph. In two ways this set can be acquired. It can either be passed by the Crossing routine or it can be read from file. A null filename signifies the former situation. From the two images that are shown at the end of the previous subsection it will be clear that for the (almost) regular grid a simple search algorithm will suffice to reconstruct the grid. This process is symbolically denoted in the following image. Note that a priori knowledge on the original shape of the grid must be used. Note furthermore that the color information of the points is not used. Reconstruction is solely based on geometrical consideration.
From the second sample image of the previous subsection it is clear that these boundary conditions are bound to fail in interesting cases.
In such cases a more subtle approach is needed. The first step is to convert the individual points into triangles. To do so we use a simple Voronoi triangulation. Although Data Explorer provides the user with a triangulation we have chosen to implement our own routine in C. This routine takes the field, propagated by Crossing, in which positions and data were present and adds to them the connections.
A first validation is performed by checking the length of the sides of the triangles found against the user knowledge of the input grid. To make this flexible the parameter is provided to the user as an interactor while in the Message window the reduction is given. After this a series of steps follow which take into account the accumulated color and directional information. The first two checks aim at the directional information (2 to 1, disregarding the direction) and test if the three points involved agree on the color information. Schematically this is represented in the following diagram This together with the length reduction reduces the original set to 60 % of its size. A typical example of the state is shown in this figure
Next a fusion of triangles into trapezoids is realized. Two triangles may be fused if they share the same color axis, i.e. the side of which the directional vectors are equal, and if they agree on the color. It is now up to the user to either remove the remaining unpaired triangles or to keep them. Clearly the latter approach squeezes the most information out of the image. It should be stressed that so far we have concerned ourselves solely with the colored squares. A similar analysis of the image for the black squares can easily be done. Matching the two sets of trapezoids found in this way marks the end of the validation step.
Next the graph can be reconstructed. The list with validated trapezoids is now processed in a queue-like fashion, each trapezoid generating four points in the queue, which are used to scan for neighbors. In this way an index is created which determines the graph. It is added as another member to the Group propagated by the procedure in which the graph is represented as

	index, left_nbr, right_nbr, upper_nbr, lower_nbr