PVV: A Goal-Oriented System for Industrial Vision

PVV - A &GAL-ORIENTED SYSTEM FOR INDUSTRIAL VISION

Augustin Lux and Viviane Souvignitr

Lt~boratoire UA6 B.P.62 38142 St."artin d'H~rts Cfdex 6renoble - frt~nce

• A "ducription" 11odule based on in edge-tracking progra11 is capible of finding features in the i11age <straight line seg11entsl. It can work in a bottoM-up fashion, finding features in a given area of the iMage; and in a top-down fashion, verifying the presence of predicted illage-features. Its perforMance depends on a large set of para11eters of thresholds, tolerances, windows, and goal conditions. Yhen no goal condition is set, the 11odule works in a bottoM-up fishion. The 11ore precisely a goal is defined, the 11ore the analysis is selective.

· The PVV 11odule interprets the i11age features found in ter11s of object 11odels in the object plt~ne. PVV generates geo11etrical hypotheses coMbining a set of 11odel features with a set of i11age features. IMage features lacking in the 11ost plausible hypothesis are used to for11 new goals for the description 11odule. Yhen a hypothesis is sufficiently pliusible the syste11 reports success.

• A calibration Module converts illage-plilne coordinates to/fro11 object plane coordiniltes. The calibration 11odule works with in orthosrt~phic projection.

This structure gives a nu11ber of advantages. i11porhnt

• 1/ I11age description is co11pletely controlled by interpretation. PVV uses unguided i11age description only to establish initial hypothetet, uting conservative part~11eter valuet to assure description speed and reliability. During the prediction t~nd verifict~tion cycles description is applied with a well-defined goal to li11ited pirts of the i11age. In this ct~se description pirillleters are chosen to allow for fine dett~ils.

21 The overall systeM is viewpoint independent. Viewpoint infor11ation is contiined in the calibrt~tion 11odule only, it does not affect the interpretation.

3/ The choice of extended features as the bisis for interpretation li11its : the co11binatorics of the feature !latching.

In this paper we dPscribe PVV's global structure and the interpretation 11odule. The description 11odule is presented in a forthco11ing report <Lux 1983>.

Several co11parable syste11s have been described in the litterature; in pirticular (Perkins 1977>, tYachidi

· This work has been supported by the DRET under research contract n.81/665

ABSTRACT

The PVV systeM applies the principle of goal directed vision to the localisation of parts in 2-D scenes. It contains a description Module working in unconstrained botto11-up fashion, or constrained by goal para11eters. The goals for description are defined by the interpretation 11odule as a function of the Most plausible current hypothesis. Hypotheses are generated according to the results of description. The syste11 has been entirely i11ple11ented on a Microco11puter and is being used as vision sensor for the laboratory' s robots.

INTRODUCTION

A 11ajor proble11 in co11puter vision co11es froft the ditil explosion facing the description ftodule. &oal directed procetsing is an illportt~nt strt~tegy for the solution of this proble11; it introduces il top-down co11ponent to li11it the processing to the ditil necesst~ry for the syste11 to succeed.

PVV - Prediction and Verification in Vision - is a goal-directed syste11 in which interpretation and description ue i11ple11ented as· coroutines. It localizes and identifies one or 11ore partiillly visible objects in il grey level i11age on the bt~sis of two-dillensional object 11odels. The syste11 has the Modular structure shown in figure 1.

and Tsuji 1977>, <Bolles and Cain 19821. In spite of the very siftilar overall specifications, the internal structure of these syste11s is quite different.

Perkins ' syste11 shares with PVV the use of extended featu~es, the 11ain differences are its use of concurves as the basis for ftodel-to-iftage 11atching, and the ftulti-pass structure.

The prograft by Yachida end Tsuji use of the prediction-verification liftited to co11pletely visible objects. ftakes intensive paradigft but is It uses a richer

set of feature types.

The local-feature-focus <LFFI Method proposed by <Bolles and Cain) identifies and localizes partially visible objects on the basis of clusters of local features (sftall holes and corners>. The LFF ftethod and PVV can be considered as two co11ple11entary subsets of a 11ore general vision syste11 1 each of which already is sufficient to solve a nu11ber of interesting vision tasks. LFF features sophisticated Model analysis and the use of 11axi11al cliques to construct initial hypotheses; PVV features global construction of hypotheses, opti11al interaction between i11age interpretation and description, and general ca11era position.

IV TASK BEHAVIOR

Figures 2 to 4 illustrate the Main features of the syste11. In the exaftple of fig.2 the systeft is asked to find a lightswitch cover in a heap of sMall parts. The ftodel is .shown in fig.2a. Figures 2b to 2f illustrate the 11ajor phases of the analysis. The systeM fi~st activates the description 11odule to se<:ll'Ch for a llne with sufficient contrast in a predefined way <dotted line on the botto" of figure 2b). Uhile tracking this line <turning around the electric plug>, three straight line segftents are found (figure 2bl, until the line is lost due to vanishing contrast in the white region in the upper part of the iftage. These segMents give rise to four initial hypotheses, two of which are shown in

figures 2c and 2d.

Notice that iMage lines and MOdel lines do not need to coincide in a hypothesis - they only have to overlap. But allowing for partial visibility and accidental align11ent increases the nuMber of possible hypotheses. Constraining iftage feature length during ftatching can reduce by a factor of three the nuRber of hypotheses generated in this exaMple; only o~e hypothesis is generated if i11age feature le1gth 11 liRited to 1.5 tiRes the candidate Radel feature

length.

The Most plaU&ible hypothesis then is verified by asking the description Rodule to find the expected Rissing features. Figure 2e shows the area where ~ne of these is looked for. Figure 2f shows the l1ne segRents effectively detected at the end. A le~st squares fit is used to coRpute the best transforMation superiRposing the Rodel on these segMents in the obje~t plane. Typical precision is about 1 degree 1n rotation, and better than one pixel in translation, which is sufficient for our robots.

Figul'es 3a (iRage> and 3b (Model superi11posed on found iftage features) show how the systeft can handle a probleft where the detection of a low contrast line is necessary to disaRbiguate an object location. It would be unreasonable to search for this line without having a well justified hypothesis, since line tracking with a very low contrast threshold is bound to be tifte consufting and to find spurious lines.

Figures 4a (iftage, found segMents, initial hypothesis) and 4b (final hypothesis> illustrate syste11 perforftance with very noisy data. Noise in this case is produced by highlights and shadows on the object. The initial hypothesis is strongly affected by this noise. Softe predicted segftents are found, however, enabling the syste" to coftpute a satisfying final solution.

V THE F'VV INTERPRETATION IIODULE

Interpretation starts with an initial call to the description ftodule, then control oscillates between hypothesis generation and hypothesis verification until the goal is reached or all possibilities are exhausted.

A IIODELS AHD HYPOTHESES

A Rodel is a feature list describing the visual appearance of an object in its reference position in the object plane. It ftay contain features representing parts of the outer contour, inner contours or lines visible on the ftodelised surfaces. The features are not necessarily contiguous, and do not have to describe

closed lines.

A hypothesis represents an object as a Radel instance with a given position in the object plane. A hypothesis is coftposed of: 1) A ftodel feature to iMage feature association list. 2> A planar transforMation, superiftposing the ftodel features - at least partially and within a certain tolerance on the associated iftage features. 3) A plausibility and a validity value describing the current status of the hypothesis. The plausibility is a nufterical function of the iMage features confirfting the hypothesis. The validity is a nuftber giving an account of the unsuccessful feature predicictions.

B HYPOTHESIS GENERATION

The initial hypothesis generation constructs all possible hypotheses according to the initial iMage features extracted froft different regions of the iMage. Several parafteters allow to adapt the systeft to varying situations:

• the nuftber of initial iftage features
• the threshold of MiniMal plausibility
• the tolerance for accidental alignMents

On subsequent calls to this phase, which take place when new hypotheses are needed to achieve the goal, they are generated in a Rore 1elective Manner. Existing hypotheses are updated and/or a liMited nuMber of new hypotheses are generated. Iftage features necessary for these operations are taken by order of decreasing reliability. If these operations fail, the description ftodule is called to search for More features.

C HYPOTHESIS VERIFICATION

The hypothesis having the highest plausibility value is subftitted to a sequence of prediction - verification cycles. The syste" deterMines the Most iftportant non instantiated ftodel feature. A window in the iftage is coftputed where this feature should be found. This prediction results in a call to the description ftodule with a well circuMscribed goal. The description Module either finds one or several segMents which are part of the searched feature, in which case the hypothesis ' plausibility is increased. Or the description "odule does not find the predicted feature, and the hypothesis ' validity is decreased. Predictions and verifications are cycled through until one of the following three conditions is satisfied:

• plausibility > confir"ation-threshold
• validity < refute-threshold
• no unused feature left

A hyprithesis beeing confirfted, PVV has localized and identified an object in the scene. If a hypothesis is rejected, or can be neither confirfted nor rejected once all features have been searched, the Most plausible hypothesis is selected between the reMaining ones. If it is not valid enough control passes to the hypothesis generation Module.

VI CONCLUSION AND FUTURE ~ORK

The systeM described in this paper has been developped in FORTRAN on a large tiMe- sharing systeft <KULTICS on a HB-68) and entirely iRpleRented on a LSI-11/23 "icrocoftputer. It is connected with the LK ftanipulator language interpreter <Kiribel and Hazer 1982>. Prografts occupy about 55K words, RiniMUft heap size is 4K words. Execution tiftes are not yet ' significant, since the syste" spends its tiMe swapping the prograft on floppy disk. The interpretation phase of the first exa"ple (fig.2l takes about 1.8sec. on the HB-68.

~ork is continuing on the description Rodule to adftit "ore varied feature types.

The interpretation Module is being coftpleted to handle ftultiple-object hypotheses with occlusion analysis.

ACKNOULEDGEKENTS

• The PVV interpretation Module owes Much to a prograM written by R.Popplestone in POP-2 during his stay at the IKAG Laboratory winter 1981.