Image Processing in Prolog: Getting the Paradigm Right

Appeared in Volume 8/4, November 1995

Image processing using Prolog has been a research focus at UWCC for a number of years. Recently we have been improving our Prolog-based image processing paradigm, since our previous work was restricted to carrying out image processing operations in a deterministic manner.

The current system (PIP) is the latest in a number of systems implemented at UWCC using LPA MacProlog. Previous systems used external hardware, such as an intelligent camera, to perform image processing operations, providing 3-letter predicates within Prolog which could be used to control the hardware. For example, lpf/0 (low-pass filter) blurs an image, whereas avg/1 interrogates the hardware regarding the average image intensity. In all cases, the operation is performed on a current and an alternate image: the current image becomes the result of the operation, while the alternate image becomes the previously-current image. A range of applications has been successfully implemented using these early systems, including packing, object shape analysis, and automatic dissection of plantlets [BAT91].

PIP [JON94, JON95a] differs from the previous systems implemented at UWCC in that the image-processing is now performed by software (using C routines). This has a number of benefits, not least of which is the fact that we are no longer restricted to a predetermined set of image-processing functions: we can extend our C function repertoire as and when needed.

There are two distinct Prolog layers: the two-image model and the multi-image model. The two-image model allows the programmer to carry out image processing in the same way as in our previous systems, so providing continuity. In particular, the PIP user interface is comprised almost entirely of code from the earlier systems. Fig. 1 shows PIP in interactive mode after the user has negated the current image (using neg/0) and is about to use the lpf/0 command.

Fig. 1: Interactive mode in PIP.

By contrast, in the underlying multi-image model, image processing operations typically take one or more images as input and create a new image as the result. For example, the goal neg_im(Im1, Im2) will create a new image which is the negation of Im1 and bind Im2 to the result.

A concern is that although Prolog has proved to be an effective vehicle for image processing, it is mostly in the domain of processing operation results (e.g. measurement outcomes) that the reasoning power of Prolog has been used. The image processing operations are deterministic and also, at the higher two-image model level, destructive. This means that no previous images can be recalled (unless the rea/1 and wri/1 features we have provided for explicitly associating an image with a label are exploited). It would be far more desirable if Prolog's search ability and ease of exploring alternatives was extended to these image processing operations. This would allow us to explore a sequence of operations, discover that the result was not useful, and then automatically undo these operations through backtracking.

Our present solution is to provide an operator (the æ ("Andrew's Extension") operator), which can be used in conjunction with the two-image model. If an image processing operation is preceded by this operator then, on backtracking over this operation, the current and alternate images are restored to their state prior to the operation.

There are two problems with this solution: having just a current and alternate image is not always sufficient (e.g. we may wish to perform more than one measurement on a given image), and implementing the æ operator has proved quite difficult.

In order to solve the latter problem it has been necessary to program a fairly complex meta-interpreter, the most difficult task being to interpret the cut in an appropriate manner. A meta-interpreter for standard Prolog that accommodates the cut is already difficult to write, but in our case there has been the additional problem that when the cut is encountered, most (but not all) of the image information that has been stored for backtracking should be deleted for the sake of efficiency. A description of this meta-interpreter is in [JON95b].

In order to solve the former problem, we adopt the compromise of using rea and wri (mentioned earlier). A more satisfactory solution, which we are contemplating, is to implement behaviour similar to the current multi-image model, but allow any variable bindings (e.g. to new images) to be undone on backtracking, so freeing any associated memory in the process. As in the existing PIP system, a meta-interpreter will be needed to achieve this behaviour. We are also contemplating extending our meta-interpreter to allow robot actions carried out under the control of PIP to be undone upon backtracking: this would mean that packing applications, for example, could proceed by physical trial-and-error.

Despite the successes obtained to date, we believe that Prolog-based image processing has significant further potential. However, our experience suggests the desirability of altering the Prolog definition in some ways so that full meta-interpreters are easier to implement (see [O'KE90]), and illustrates the care that needs to be taken in designing predicates which extend the Prolog system. If it is meaningful for the effects of these predicates to be undone on backtracking, we would argue that this permits a far more natural, far more useful, style of programming to be adopted. In contrast, if the side-effects are permanent then the cynic might be entitled to ask why a procedural language had not been adopted for application development instead of Prolog.

References

[JON94] A.C. Jones and B.G. Batchelor, "A Software Architecture for Intelligent Image Processing using Prolog," Proc. Intelligent Robots & Computer Vision XIII, D.P. Casasent (ed.), pp. 178-188, Int. Society for Optical Engineering, Bellingham WA, 1994.

[JON95a] A.C. Jones and B.G. Batchelor, "PIP - An Integrated Prolog Image Processing Environment," Prolog for Industry: Proceedings of the LPA Prolog Day at the RSA, C. Spenser (ed.), pp. 39-47, Logic Programming Associates Ltd., London, 1995.

[JON95b] A.C. Jones and B.G. Batchelor, "Implementing Full Backtracking Facilities for Prolog-Based Image Processing," Proc. Machine Vision Applications, Architectures and Systems Integration IV, Int. Society for Optical Engineering, Bellingham WA, Oct. 1995.

[O'KE90] R.A. O'Keefe, The Craft of Prolog, MIT Press, Cambridge MA, 1990.

Andrew C. Jones
Dept. of Computer Science
Univ. of Wales College of Cardiff
PO Box 916, Cardiff CF2 3XF, UK
Email: Andrew.C.Jones@cs.cf.ac.uk