W2A-034 Image processing-0.txt
A HIGH LEVEL LANGUAGE FOR PARALLEL IMAGE PROCESSING

John Brown and Danny Crookes

Most published research in the field of parallel image processing has tended to be in the areas of parallel architectures and parallel algorithms. Work on the development of software tools such as languages has generally been less extensive. This paper describes some research which is intended to redress the balance a little, by describing I-BOL - an application-specific high level programming language intended for implementing low-level image processing applications on parallel architectures. In particular, I-BOL has been designed to be capable of implementation on distributed memory parallel machines such as transputer networks. This paper introduces the core concepts of I-BOL: its view of an image as a set of tuples; user-defined neighbourhood function; and I-BOL's facilities for recursive image processing. Solutions to a number of example problems illustrate particular aspects of the notation, including the Distance Transform, Histogram Equalization and the Hough Transform. Some consideration is given to the parallel aspects of the current implementation of I-BOL on a pipeline of transputers. A few performance measurements are quoted, giving execution times for the chosen examples on various sizes of transputer work.

Keywords: image processing, parallel languages, transputer networks, Image Algebra, recursive image processing

The application of parallelism to image processing has for long been recognized as offering considerable benefits. However, published research in this field suggests that most effort has been directed towards the development of parallel architectures and parallel algorithms. With some exceptions, work on software tools such as programming language has been less extensive. This in inevitable, since tool development for any application always lags behind algorithm development, and also since the use of tools can entail a certain loss of performance, particularly in a parallel context. However, as a step towards redressing the balance a little, this paper outlines a language for low level (parallel) image processing which has the aim of improving software productivity while yielding acceptably efficient parallel implementation.

There is a definite need for tools which will speed up the software development process for parallel systems. This is particularly true of image processing, where it is usually necessary to experiment with different algorithms before determining the best solution. Software development needs to be rapid, but this conflicts with the need for efficient parallel implementations. Programming and evaluating a range of algorithms on, say, a transputer-based parallel system, can be a lengthy and error-prone process because of the need to distribute data and handle interprocessor communication. To speed up software development, the programmer should be relieved of as much of this detail as possible. A suitable programming language is a useful productivity tool, since it can hide the details of the parallel implementation, and enable a programmer to concentrate on the image processing aspects of the problem. General-purpose languages which provide array-processing abstractions for expressing parallelism are becoming available, including Fortran 90 and High Performance Fortran, and will no doubt be very useful in the development of parallel programs. However, an application-specific language can make certain important assumptions, and choose higher level abstractions, which increase efficiency considerably. This is the approach we have adopted at QUB to language design for image processing.

One such application-specific programming language for parallel image processing is the APPLY language. APPLY was developed and implemented initially on the WARP machine at Carnegie Mellon University, as a tool for writing low-level image processing algorithms. Implementation of it have now been provided for other architectures, including transputer-based machines. In an APPLY program, the user writes a procedure which specifies the detailed operations to be performed at one pixel position in the image. The compiler then generates the code which causes the procedure to be applied to every pixel in the image.

A different approach to APPLY was taken in early work in this field at QUB (Image Algebra Language) and its implementation on a network of transputers. IAL was based on the abstractions of Image Algebra, a mathematical notation developed at the University of Florida for specifying image processing algorithms. IAL provided operations at the complete image level, with no individual pixel access. For instance, a version of the Sobel edge-finding operator could be coded in IAL as the single statement: where S and S y are the usual horizontal and vertical Sobel masks (whose weights would previously have been defined), and the operator '* +'represents convolution.

IAL proved useful for a range of low level image processing tasks, but was limited in its flexibility and expressive power, partly because it allowed no internal access to individual pixels of an image. Subsequent work to develop a more flexible and powerful notation than IAL has resulted in an extended image processing language, which we called I-BOL. (The name 'I-BOL' sounded appropriate for an image processing mechanism, but exactly what it stands for has yet to be decided!) As well as providing the 'complete image' operations of IAL as a subset, I-BOL permits access to image data at either the pixel or local neighbourhood level without being architecture-specific.

The design philosophy of I-BOL has been to make parallelism implicit by providing image processing-oriented programming abstraction which are, however, capable of efficient parallel implementation. A key question is how to provide sufficient flexibility without making it impossible for the compiler to produce an efficient parallel implementation. A balance has to be struck between user freedom and the ability to perform automatic parallelization. I-BOL is a step beyond IAL in this direction.

I-BOL has been implemented on a transputer network. The I-BOL compiler takes a program written in the language, and automatically parallelizes it by distributing the image data. 'Troublesome' features of a parallel implementation, such as interprocessor communication, and the management of borders around image segments, are taken care of by the compiler. The implementation is scalable in the sense that I-BOL programs will run on any number of processors without alteration (except for stating the actual number of processors).

This paper outlines the main concepts upon which I-BOL is based. In particular, three novel aspects of the language are discussed in more detail: the view of an image as a set of tuples, user-defined neighbourhood functions, and I-BOL's facilities for recursive image processing. A number of example programs illustrate particular aspects of the notation. These include high level programs for the Distance Transform, Histogram Equalization and the Hough Transform. Some consideration is given to the parallel aspects of the current implementation of I-BOL on transputers. A few performance statistics for the three example programs are then given for executing on transputer networks of size from 4 to 16.

STANDARD DATA STRUCTURES AND OPERATORS IN I-BOL

I-BOL provides a range of built-in types for representing data structures which are commonly used in low-level image processing. The following are the main data types available: • Image type: For storing images (as 2D arrays of pixel) The pixel type can be either integer, real or boolean; • Template type: Windows and weights for local neighbourhood operations (like a small 2D array). Templates can be used for different types of neighbourhood operations; • Vector type: One dimensional array structures (indexed from 0): • A Binaryimage type: A storage-efficient representation of sparse binary images (e.g. edge images).

The standard data types integer, real and boolean are also provided. As is common in image processing, boolean data is usually compatible with integer arithmetic operations.

As in IAL, the configuration and weights of templates can be defined initially in a value section; for instance: value

Weights in a template can be left undefined (indicated above by '('), in which case they are not included in the computation. Also, a target pixel position must be indicated (within square brackets, like [4] above), for aligning the window with the image during processing.

Operations on complete objects

A full range of arithmetic, comparison and local neighbourhood operations is provided to operate on these data structures as indivisible objects. (Operations which explicitly access individual elements of these objects are considered later.)

These object-level operations fall into the following categories:

image_operator_image
Point-to point combination of all corresponding pairs of image pixels, generating an image result. e.g.
image_operator_scalar

Point-to-point combination of all image pixels with scalar value, generating an image result. (This also covers scalar_operation_image operations). e.g.

vector_operator_vector

Point-to-point combination of all corresponding pairs of vector elements, generating a vector result e.g.

vector_operator_scalar

Point-to-point combination of all vector elements with a scalar value, generating a vector result. e.g.

image_ operator_template

The standard set of Image Algebra local neighbourhood operations is provided. These take an image and a template, and produce a result image. The range of operators includes: e.g.

global image and vector operations

These operations produce a scalar result, based on an entire image or vector. The global operators include: max min sigma count {applied to boolean image: the number of 'true' pixels} e.g.

A range of built-in functions provides standard mathematical operations on scalars, vectors and images (e.g. float, sin, abs). The standard set of scalar arithmetic and comparison operators is also available. Fuller details of these and other operations can be found elsewhere.

IMAGES AS SETS: A NOTATION FOR PIXEL ACCESS

When accessing individual pixels of an image, the conventional view of an image is as a two-dimensional array. The operations involved in processing such a structure are frequently expressed in standard programming languages using single or double loop constructs. With such an approach, programs can become architecture-dependent, since loop constructs may have to be written with a particular architecture or number of processor in mind.

The I-BOL notation provides an alternative abstraction of an image. It treats an image as a set of tuples, one tuple per pixel. An individual tuple specifies the pixel position and its grey level, and has the form in I-BOL: < row, column, grey level at this position > e.g. < i, j, g[i,j]> A complete image may be considered as a set of such items, denoted in I-BOL as: { i, j, g[i,j] }

For instance, Figure 1b shows a tuple set representation of the equivalent simple geometric image in Figure 1a,

Of course, there is no obligation on an implementation actually to represent such an image in this tuple format behind the scenes (though there might be times when it is useful to do so). But as a programming abstraction for specifying images, it is a convenient standard notation.

Constructing an image as a set

Forming a new image in I-BOL is a matter of constructing a new set of tuples. I-BOL therefore uses a notation based on the standard method for constructing a set, in which an image can be defined as:

This can be written using the I-BOL constructor notation as: { i, j, g[i,j]: C1, C2, C3...}

In this construct, ':' is read as'such that'. C1, C2 and C3 denote boolean conditions, which must either be true, or be made true during the formation of the set (i.e. a condition can either qualify a potential member, or generate potential members). A condition may be made 'true' by appropriate instantiation of variables within it. Thus the above constructor could be read as: "Find all substituations for i, j and g[i, j] such that C1, C2 and C3 are true"

This structure is called an image constructor. Syntactically, it is an expression. For instance:

This will construct an image Image1 in which the grey level of each pixel corresponds to the pixel's distance from the top left hand corner of the image. The bounds for i and j are implicitly defined by the declared bounds of Image1. Note that the condition imposes no constraint on the coordinates i and j. In general, for assignment to an image declared in the normal way, the tuples are defined over the declared space, and the conditions are used to calculate the grey level. For any position for which the conditions fail, an appropriate default grey level is defined for that position: 0 for interger images, 0.0 for real, and false for boolean. Thus, a boolean image which could be used to implement an ideal filter, comprising just those pixels within a radius R of the centre (X 0, Y 0), could be constructed as:

Vectors as sets

In a similar way to images, a one-dimensional vector can be viewed as a set of tuples. For convenience, the index of a tuple in a vector is implicit, and can be deduced from the subscript in the data value. Thus a vector is written as a set of indexed values, as in: { v[i] } A vector can be constructed using the constructor notation, as in, for instance:

Pixel referencing
I-BOL provides restricted access to the internal components of an existing image (or a vector) in several ways, but only ever within an image constructor. When constructing a set of pixels whose positions are specified in the constructor as
<i, j="">
, it is possible to reference the following sub-components of an image:
(i) all individual pixels of an image, whose positions are normally specified relative to
<i, j="">
; (ii) all local neighbourhoods, or patches, within an existing image, i.e. all subsets of pixels within a specified region relative to
<i,j>
. These patches will be overlapping. Apart from on the outside boundaries, there will be one patch for very pixel position; (iii) all non-overlapping patches, called tiles. The number of tiles is obviously less than the number of pixels by a factor of the tile size: (iv) I-BOL does allow unrestricted access to any pixel, but the implementation is likely to impose restrictions of the range of pixel positions. In a parallel implementation on a distributed memory machine, for instance, it is likely that efficient random access is guaranteed only within neighbourhoods; the restrictions on non-neighbourhood access depend on the image distribution strategy.
</i,j>
</i,>
</i,>
