Composing double loops is one of the more annoying aspects of writing vision algorithms in C. In Envision, operations are applied to all (or many) locations in an image using "scanners."
A scanner is an object which contains the code for one method of enumerating some or all of the samples in a sheet's focus area. The system will provide at least the following built-in scanners, which work on sheets of any dimensionality and enumerate all samples in the focus area.
Scan-forward enumerates locations in storage order. On 1D sheets, this is guaranteed to follow the usual 1D ordering from smaller to larger coordinates. On sheets of higher dimension, it follows the prevailing local conventions for storage of multi-dimensional arrays, typically standard row-major or column-major storage. Scan-backward enumerates locations in the reverse of the order produced by scan-forward.
The following scanners are also provided, for use on 2D sheets:
These scanners traverse a 1D path through the 2D sheet, parallel to the specified coordinate axis. Unless given a specific starting location (see below), horizontal-scan and vertical scan start one sample left and below the sheet's min-sample and the two reverse versions start one sample right and above the sheet's max-sample. Therefore, each scanner enumerates the samples along one edge of the 2D sheet, but one sample outside the sheet. These samples can be used as input to a 1D scan in the perpendicular direction, to enumerate the entire sheet. For example:
(scan (mycolumn sheet #f scan-right)
(scan (mysample mycolumn #f scan-up)
...[code using mysample]...
The form scan is used to apply an operation at every location in a sheet's focus area.
If the test argument is omitted, it defaults to #f. This will mean that the scan does not stop until it reaches the end of the sheet.
If the scanner input is omitted, it defaults to a scanner chosen by the implementation on the basis of efficiency. There is guaranteed to be a default scanner for a sheet of any dimension and it is guaranteed to enumerate all locations in the focus area. In most implementations, it will be scan-forward (storage order). However, the user should not depend on what ordering method the default scanner uses or whether the order is constant from invocation to invocation. Some implementations might process parts of the sheet in parallel. Therefore, the scanner should not be omitted unless your operation genuinely lacks order dependency.
The scan form generates a loop which binds variable to the samples in the focus area, one by one. The loop order is determined by the input scanner. The test and the expressions in the loop (expr1 expr2 ...) are evaluated with this binding. The loop halts when the test is satisfied or when it reaches the end of the focus area, whichever happens first.
The scanner returns two values. The first value is true if it stopped in the middle of the focus area, and false otherwise. The second value is the sample on which the scanner stopped. If the first value is false (halt at the end of the focus area), the second value will still be returned and be a well-formed sample. However, the user should not depend on where this sample lies with respect to the focus area.
It is sometimes necessary to scan until a suitable sample is located, return control to main lisp (e.g. to allocate more storage), and then resume the scan. To do this, the first scan returns the last sample location it found. This sample can then be passed to scan, in lieu of the sheet argument, to restart the scan.
Within coprocessor code, scan expressions are rewritten to substitute the scanner code (hygenically!) in-line. Thus, the final code does not execute function calls in the inner loop.
Scan cannot be called from scheme, only used inside co-processor functions. There is no conceptual problem with making it available from scheme, but it is a bad idea (extremely inefficient) and should not be encouraged.
Scanning an image in the wrong order can cause swapping if the image is large compared to the amount of RAM on your computer. This can dramatically slow your algorithm. When the scan argument is omitted, the default scanner chosen by the implementation should scan in an order which avoids swapping.
However, problems can still occur if you take explicit control of the scanning order or if the operation accesses a second sheet in an order close to 90 degrees rotated from the scan order of the sheet controlling the scan. A good example of the latter would be an operation which rotates an image by (say) 85 degrees. When implementing such an operation, compare the size of your sheets to your amount of RAM. If all of the sheets involved in your operation cannot fit into your RAM simultaneously, along with your active processes, you will have a swapping problem.
If you might have a swapping problem, divide the sheet controlling the scan into smaller blocks using restrict-sheet (which creates a block that shares storage with the original). Run your scan on the blocks, one by one. If your algorithm cannot be run in such a block-by-block fashion, you will have to redesign your algorithm (and you would have the same problem if you implemented it by hand in C).
Many computer vision operations scan two or more sheets in lockstep. For example, an operation which subtracts two gray-scale images might need to walk down three sheets in lockstep: the sheets for the two input images and the sheet for the output image. When the sheets have the same precision, e.g. because they are parts of a common computation and were created with the same precision, sample offset operations can be used to optimize the scanning process.
To efficiently scan multiple sheets at once, the scan loop should controlled by one sheet, typically a sheet into which output values will be saved. Before running the loop, identify corresponding samples in the sheets. These can be used to derive locations in the non-controlling sheets from locations in the sheet controlling the loop, using sample operations.
A new scanner is defined as follows
The first input is the name of the new scanner. The method-list is a list of methods for sheets of different dimensionality. Each method has the form (dimension (start-function loop-function)). Currently, the dimension must be 1 or 2. Neither input should be quoted.
In each method, the start-function and loop-function are lambda expressions. Start function takes one input: a sheet. It returns a sample right before the first sample in the sheet's storage area. loop-function takes three inputs:
The code for loop-function should extract sentinel samples at the edges of the sheet's focus area. It then loops through the focus area starting at the sample right after the input sample, generating samples one by one. Each sample is passed to the test function, then (a) the sample is passed to the loop-code function or (b) the sample is returned. If the end of the focus area is reached and no samples have passed the test, a sample outside the focus area is returned.
For the current implementation of 2D sheets, the loops in a storage-order scanner should vary the first coordinate faster than the second one.
It is probably easiest to copy-code from an example. Writing new scanners should not be required very frequently: almost all vision algorithms can use one of the built-in scanners.
Scanners live in their own private namespace. Therefore, a scanner can share a name with a function or local variable without conflict or shadowing. The correct binding is never ambiguous, since scanners only occur in the relevant position in a scan form and no other type of object can legally occur there.
It is not clear whether this is the right long-term solution. Moreover, this is not the only semantic oddness to scanners. They also behave like (hygenic) macros but their expansions are type dependent. It is not yet clear to me how to fit them nicely into scheme's formal semantics.
Ownership, Maintenance and Disclaimers
Last modified