Information Technology Reference
In-Depth Information
which will occur sequentially, with a shift over time, starting with the darkest
parts of the image. Therefore, by imposing monotonically changing light back-
ground of a given shape on the original black-and-white image of the maze, it is
easy to initiate a phase wave at the desired point of the maze.
The procedure for finding the shortest path in the maze was implemented in
two main stages.
On the first stage the negative—white on black background—image of the
maze was entered into the reaction-diffusion medium (more precisely, the
image of the maze plus the background monotonically changing along the
maze was projected onto the surface of the medium with a certain selected
exposure, Fig.
5.26
). A positive image of the entered image appeared in the
medium, in which in the course of its further evolution, a wave began to
propagate with a certain delay (color change of the path in the maze from
black to white). Successive stages of its propagation were recorded by a video
camera and then entered into the memory of a PC.
Images recorded in the computer memory were subsequently used for finding
the shortest path, which was implemented as a sequence of standard digital
operations performed by a personal computer.
The developed method turned out to be rapid and efficient in the case of linear
mazes, where one entrance is connected to an arbitrary number of exits, and the
direction of the path varies by no more than 90
.
5.3.3 The Procedure for Finding the Shortest Path
in the Maze
The procedure for finding the shortest path in the maze consists of two main stages.
The first stage is the excitement of a phase wave at the selected point of the maze
and the recording of successive steps of wave propagation through the maze into the
computer memory.
The second stage is the numerical analysis of these images to determine the
shortest path between the start and the end point of the maze.
Let us discuss this procedure, starting with the case of a simple, linear, treelike
maze with one entrance and multiple exit points (Fig.
5.27
).
Suppose that a monotonically decreasing background is superimposed on the
original image at the selected entry point into the maze. After the projection of the
combined image onto the plane of the Belousov-Zhabotinsky reagent, a negative
image appears in the medium. At first the image of the original maze appears (black
image on white background). Then a propagating phase wave arises which succes-
sively changes the black color of the maze into the background color.
The time of the wave propagation through the maze depends on the gradient of
intensity of the imposed background. By varying the gradient it is easy to make this
time sufficiently small (about 3-5 s), i.e., smaller than the lifetime of the negative
phase of the image in the process of its evolution in the medium.
