Automatic Programming of Machine Vision Systems

Introduction

This paper describes our research on a method to gen­ erate programs for machine vision systems. The program gen­ eration process is initiated by a query from the user. This query typically requests the system to provide a program that can decide about the presence of a specific object in an image and provide measurements of a number of its parameters (e.g. its position and orientation, hinge openings etc.). In the pro­ gram generation process we use image generation models, i.e. image grammars. We try to keep these models simple and valid for different classes of scenes by including program test­ ing in example images in the program generation process.

In general the design of an industrial machine vision pro­ gram depends on a number of factors:

1. The kind of object that must be recognized.
2. The required parameter measurements and a priori avail­ able parameters.
3. The available hardware and software to perform primi­ tive measurements on images.
4. The kind of scene the object is in.
5. Overall program specifications, such as speed and reliability

In most current machine vision applications a human program­ mer accounts for these factors when he writes the program. In this paper we will discuss our research work on the automation of this programming process.

One of the fundamental problems in this automation effort is the fourth factor listed above. This factor subsumes such things as overall image quality, illumination, the presence or absence of confusing objects etc. These factors differ from application to application and their consequences are hard to model in advance. They force the human programmer to write his programs in terms of fairly low-level primitives and to design his programs by trial and error testing in images. We believe that an effective way to avoid having to make detailed application-specific models in advance is to incorporate this

Automatic programming of machine vision systems

L. J. de Ha<U

Philips Research L&bor&tories, PO BOX 80000 Eindhoven, The Netherl&nds

trial and error testing of programs in our system.

The design of our system is centered around a planner, which, given a model and a goal measurement, generates a sequence of program steps. These steps perform primitive measurements in the image and combine the results in arith­ metic steps to produce the goal measurement. The steps of such a program can be divided into two stages, hypothesis gen­ eration and verification. In hypothesis generation the program produces the desired measurements and performs only those image observations strictly needed for these measurements. In the verification stage the program uses measured parameters· to make predictions that are tested by means of observations in the image. In this paper we will concentrate on the planning of hypothesis generation programs.

The mechanism of our system will be illustrated throughout this paper by means of an example object consist­ ing of two disks of identical size

This "twodiska" object has three parameters: R, the posi­ tion of one disk, D, the connecting vector to the other disk, and S, the size of the two disks. We will suppose that D has to be measured. We will assume that there is a primitive program "diskprograml". When called by dl=diskprograml() this pro­ gram produces measurements for the position R and scale S of single disks in the image. These are then available as dl.R and dl.S respectively. (Note that "diskprograml()" does not pro­ duce a unique result if there is more . than one disk in the image. Hence we presuppose some mechanism to go through alternative results, one pair R,S for every disk in the image, e.g. by means of backtracking). A typical program to produce D in a hypothetical twodisk object in an image is:

1. dl = diskprograml()

2. d2 = diskprograml()

3. D = d2.R- dl.R

This hypothesis can be verified further by the following verification program:

Our planner accounts for the first three factors influencing pro­ grams by means of a number of input sources:

1. object models
2. queries for parameter measurements
3. a library of primitive measurement functions

Object models

Our planner is provided with models of how an image is generated given the parameters of an object. For this purpose we use context-free attribute grammars. A program to meas­ ure parameters on an object performs the inverse of the gram­ matical generation function: it produces a parsing in the sense of the grammar. For our example the grammar can be expressed in the following substitution rule:

This expresses that the two "parts" "dl 11 and "d2 11 are substi­ tuted for the 11 twodisks" object, and it gives the relations between the "attributes" R, S of dl and d2 and the attributes of the "twodisks" object.

We want the grammar has to meet several requirements:

the grammar should be, as much as possible, independent of the application (no details should be added per applica­ tion)

the planner must be able to use the grammar in such a way that the complexity of the program depends on the application but not the complexity of the grammar.

The first requirement is only put to the teat if we try the system on many kinds of application and not on just "a few" example images. We try to realize these requirements by including descriptions of objects at several levels of detail in a single grammar. For example, suppose we replace the "twod­ isks" by 11 twosquarea 11 with component squares with slightly rounded comers; for most putposes a grammatical description as a perfect square may be sufficient, but for some applications the comer rounding must be included. H this is the case, we include both the perfect square description and the rounded square as alternatives in the grammar, not necessarily stating the relation between the two descriptions (in this case that the one is a more precise version of the other).

The price we have to pay for this is that in general the grammars are not entirely consistent. The idea is that this is not fatal because the resulting programs will be tested before use.

Queries for parameter measurements

The planner must be told what its goal measurement is. This will be done by an external agent. We feel that if our sys­ tem is to be useful for current programmers we should not force them to give away all of the responsibility for program­ ming at once. We realize this in our system by formulating the goal in terms of a program. This program may contain vari­ ables which are not given a value, but which are given meaning as attributes of the grammar. For example This prompts the planner to produce a program that deter­ mines D with a precision plus or minus 2, S, not being men­ tioned, does not have to be measured. H the external agent wants to take some work from the planner, he could give the more detailed goal program

Now the planner can restrict itself to devising programs to determine R of dl and d2.

The library

A third determining factor is the availability of primitive functions. The planner must be provided with a library of such primitives, together with specifications connecting them to grammatical symbols and their attributes. An example is the "diskprograml" primiti~e mentioned above. Its formal entry in the library could be of the following form:

This expresses that diskprograml is a parsing function, which performs the inverse of the generation implied by the terminal symbol "disk" in the generative grammar. It also expresses the accuracy of the function. Preferably, the library will have to contain a number of alternative primitives, which differ in effectiveness in different contexts, for any terminal of the grammar, and possibly also for a number of non-terminals.

In our work we make use of PAPS (Picture Acquisition and Processing System), a vision system developed within PHILIPS for applications in factory automation 1 · One of the strongest properties of this system is its ability to do template matching at tv-image speeds. Most of our primitives use this facility; they generate coordinates of primitive features as posi­ tions where the template has matched. In "diskprograml 11 we have implemented the disk position measurement in this way.

The planner

Having discussed the inputs to the planner we are now in a position to discuss the planning process itself. The planner must plan a program which calculates a goal variable. This calculation can be achieved in a number of ways:

1. express the variable in a generative way in other variables by means of the grammar
2. call a primitive that can measure the variable from an image
3. solve for the variable by inverting one or more of the gen­ erative relations in the grammar

(This involves an equation solving system)

The planner tries to apply any of these rules to its goal. H it does so, any rule can recursively generate new goals. The planner continues to apply the rules on these new goals until no unknown variables remain. In the process the planner pro­ duces a trace of procedures that must be invoked in the task program. An example:

starting from print(D,±2);

where D of 11 twodisks" must be determined. The planner applies rule 3, solving D from dl.R=R and d2.R=R+D:

where R of d1 and d2 (both disks), must be determined. Applying rule 2 twice, the planner generates the final program:

where no more variables are unknown. Note that neither the equality of the two disk sizes nor the distinctness of the two disks is verified in this program. This neglect of verification is even more obvious if we query for S: the goal program: print(S,±3) leads by rule (3) with dl.S=S and rule (2) to

The second disk isn't even inspected here (of course there is no need for inspection if only images of pairs of equal sized disks are shown: the need for verification depends on the kind of scene).

In most realistic problems the planning process will be considerably more complicated, hence we have to use some pruning mechanism. This may lead the planner to miss solu­ tions. For our purposes this is not a serious problem because usually our problems have many possible solutions and we are more interested in discovering good ones than in discovering all.

Finally, we must account for the fourth factor influencing machine vision programs: the kind of scene. In this step we must compensate for inaccuracies of our models. For example, in the twodisks model we stated nothing about what happens if the two disks come close together. Yet the selection of tem­ plates for the "diskprogram1 11 primitive is likely to be affected by such a factor. Alternatively, if there are many objects in the scene which closely resemble disks, we might want a tem­ plate that distinguishes between them and a disk. The planner must choose a template appropriate for the task by testing in some example images.

This is done as follows: a teacher provides the planner with a number of example images, together with sets of attri­ butes for objects present in these images. These sets are used, with the generative grammar, to calculate the desired outcome of statements in the generated programs. By comparing these desired results with the measurements obtained from selectable primitives the planner verifies the relations and primitives it selects.

Conclusion

The work described in this paper is a continuation of the work reported by Persoon 2 · His problem: recognition of rigid objects from images by means of a learned object description, is also pursued by Bolles 3 and Faugeras 4 · We have added to this work measurement of attributes other than position, orientation and scale. (e.g. both disksize Sand distance vector D in the "twodisk" model; both orientation PHI, length L and width W variable in a rectangle model). This is a non-trivial step because the estimation of position, orientation and scale from position observations of features can be expressed as a linear estimation problem. This can be solved by accumulating observations from an image in a least-squares estimator 4 · For non-linear problems a structurally more complicated esti­ mator is needed.

This leads us in the direction of more general model­ driven image analysis systems of which ACRONYM 5 is a prominent example (for a review of related systems see 6 ). Our approach differs from this work in that we use fairly rigid object models, with only a limited number of strictly parametrized deformation modes. Moreover, we include an off-line vision planning stage, using examples. Hence we avoid the problem of interpreting a kind of scene offered for the first time to the system. In this way we try to economize on model complexity.