Information Technology Reference
In-Depth Information
Fig. 5.28 Main stages of the algorithm of the determination of the shortest path in the maze
image obtained after the Paint Bucket operation from the initial image of the maze
allows for removing the fragment not associated with the exit.
All image processing operations used to implement the discussed procedures can
be performed using the software package Adobe Photoshop 5.0.
Successive repetition of this procedure for each passage of the branch point
allows to eliminate all dead-end branches (and the paths to other possible end
points) and to determine the path from the maze entrance to the selected end point.
We make a remark about the applicability of the procedure for finding the
shortest paths in linear treelike mazes.
The advantage of this procedure is that there is no need to determine the location
of the branch point by a human operator. The shortest path can be found as a result
of processing of individual images, sequentially recorded during wave propagation.
Moreover, for each image the following sequence of operations is performed
(assuming that
the recording process begins with the first of them, L1; see
Fig.
5.27
):
Subtraction of the L1 image from the initial image of the labyrinth L0, in order to
determine the path that the wave passes from the beginning up to the point of
wave propagation being considered (L0-1).
Filling in the fragments L1 connected with the end point by the background color
(L1-1).
Subtraction of L1-1 from L1, i.e., clipping the paths not connected with the end
point (L1-2). The subtraction of any fragment of the background intensity must
correspond to the zero level of intensity.
Addition of L0-1 and L1-2 to determine the current image of the maze (L01),
which is used in the next step instead of L0.
