Daniel E. Stevenson and Margaret M. Fleck
This document describes an implementation which still being debugged.
We hope for an alpha release in the near future. However, please
don't expect the same quality control you might expect in a finished
product.
This document describes Envision, an extension of the Scheme programming language to support research in computer vision. It includes high-level discussion, a user reference manual, example code, and directions on how to obtain and install a copy of the language. A paper on Envision appeared in the 1997 Usenix Conference on Domain-Specific Languages ( postscript), pp. 271-284.
Computer vision algorithms are notoriously difficult to implement, read, maintain, adapt, and share. This slows the progress of research in computer vision and discourages other computer scientists from using techniques developed in computer vision. We have developed a solution to this problem, where previous researchers have failed, by combining insights from computer vision and programming language design.
Envision improves computer vision programming in two ways.
Existing computer vision systems have two layers: a set of a modules and an interpreted front-end. The modules perform low-level operations, particularly image processing, and are written in C (occasionally C++) for efficiency. The interpreted front-end language may be C-like, graphical, or a modern high-level language such as Lisp. It is used to apply a sequence of modules to an input and to write high-level ("smart", "AI-ish") code. It also serves as the user front-end.
Envision replaces this pair of languages with a single user-level language, an augmented version of Scheme. Operations which would normally be written in C (e.g. image processing) are written in the same language as high-level code. However, they are defined using a special primitive (bulk-define) which invokes a specialized compiler that produces the heavily-optimized code required for image handling. To achieve this efficiency, bulk-define restricts the programmer to an appropriate subset of Envision.
Envision also introduces new abstract data types and associated operations, which greatly simplify computer vision algorithms, particularly low-level image handing operations. The most important new data structure is the sheet. Sheets represent digitized functions, such as digitized images, processed versions of images, and digitized region boundaries. Envision provides safe pointers into sheets, called samples, and a primitive scan which enumerates the locations in a sheet in a user-specifiable order.
Envision also includes standard geometrical objects , such as points (vectors), line segments, and circles. Graphical display and tagged binary file I/O are native operations, on a par with sending text to the standard output stream. Although we currently run Envision inside emacs, we intend to replace it with a modern window-based user interface. In other words, the language is designed to the common basic capabilities of the displays currently in widespread use, not to the capabilities of a VT100.
Envision's new operations allow the programmer to specify the important, high-level features of the operation. Envision's specialized compiler automatically expands these specifications into low-level code. Its output does not match the efficiency of the best hand-hacked special-purpose C code. However, it is reasonably efficient and on-going increases in processor speed will soon make it fast enough for most applications. It is more general and automatically portable. And it can be written, debugged, and modified fast, without expert knowledge.
We believe that the days of hand-optimizing C code will soon come to an end, just as hand-optimizing assembler was made obsolete a decade ago by previous advances in compiler construction and hardware speed. Creative researchers should spend their time designing and testing new techniques. Development programmers should concentrate on robustness and portability.
The following pages describe Envision's data types and functions:
Our new user guide walks you through the first stages of starting to use the system. Then examine the following examples of Envision code.
Envision is implemented as an extension of Scheme48. Scheme48 was selected because it is small, clean, portable, and free. The coprocessor is written in standard ANSI C. We believe that it will run on the full range of machines in common use, including home linux machines and laptops.
It should not be too difficult to port our extension to other implementations of Scheme. Similar extensions could also be built for other languages with similar capabilities, such as Common Lisp and ML.
Useful general references for Scheme and Scheme48 include
Since it's a bit difficult to find one's way around the documentation that comes with Scheme48, we have converted it to html format and added a few more examples for novices. (Warning: this needs to be updated from version 0.46 to 0.50.)
Our implementation of Envision is a prototype, intended to illustrate the usefulness of the new language constructs. It does not have the best possible compiler, the most efficient possible interpreter, or the optimal version of numerical operations such as interpolation. And we don't intend to make it optimal in these ways. If there is sufficient interest in the language, we hope that experts in programming languages and numerical analysis will construct better implementations. We hope that, like popular existing languages, it will eventually have several rival implementations.
However, we are very interested in feedback about the design of the language itself. There are undoubtedly bugs, missing primitives, annoying limitations, or unnecessary deviations from scheme style. There are also likely to be bugs in the documentation. We would also like to make this prototype run on as many platforms as possible. Please send feedback to stevende@uwec.edu and fleck@cs.hmc.edu.
We have tried to keep our implementation as straightforward as possible. Details are available (or will soon be available) on:
The alpha release is not yet ready. When it's ready, this section will contain details about how to obtain and install it.
Envision currently runs on the following types of machines:
Minimum system requirements are a 75MHz 486 with 16M memory and perhaps 40M of swap space. It's a bit slow on such a system, so you will want to confine yourself to small images. You must have a color display supporting at least 8-bit color.
You must be running the X window system to start envision. Scheme48 will run from the shell or from non-X emacs, but envision must be run under X. However, it requires only basic X (Xlib), not any high-level packages associated with X (e.g. widget sets, Motif, Tcl/Tk). Your X display must support 8-bit pseudo-color (color-mapped) visuals.
To install it on a new machine, first install Scheme48 if you haven't already. When Scheme48 is working, push [eventual ftp link] to get the code for Envision and follow our installation instructions . If you have problems with the installation, see our list of known problems and fixes.
Once Envision is installed, follow our new user instructions to start using the system.
To reach us, send mail to stevende@uwec.edu and fleck@cs.hmc.edu. Please send us:
