From Early Processing to Conceptual Reasoning: An Attempt to Fill the Gap

FROM EARLY PROCESSING TO CONCEPTUAL REASONING:

AN ATTEMPT TO FILL THE GAP

Giovanni Adorni, Lina Massone, Giulio Sandini, Maurizio Immovilli Department of Communication, Computer and System Sciences - University of Genoa Via ali'Opera Pia lla - 16145 Genoa - Italy Tel. +39-10-310223 - Netmail: bambi@ugdist.UUCP

ABSTRACT

This paper shows how multiple low level sources of infor­ mation can be integrated in a Iconic Data-Base, and how this data-base can be suitably organized for symbolic manipulation. The heuristics used to segment images of a simplified real world are described. Experimental results are presented.

INTRODUCTION

A main task in artificial vision is the ability to analyze images obtained from real scenes to understand their con­ tent. This may be done by assigning appropriate interpreta­ tions to objects within the scene. Accordingly, ·an image must firstly be segmented into regions that roughly correspond to objects, surfaces, or parts of objects in the scene represented by that image. Two factors combine to make the task of segmentation difficult: i) noisy data, ii) object occlusions. To solve the problem, at least three requirements are necessary, according to the computational model proposed by Marr [1]: (a) full exploitation of physi­ cal and geometrical constraints of the environment, (b) integration of multiple low level sources of information, (c) use of global knowledge (i.e. knowledge about basic physi­ cal properties of the objects).

Some of these concepts have been implemented in several systems (see, for example [2, 3, 4, 5, 6, 7, 8, 9, 10]). In particular, Nazif and Levine [11] propose an architecture for the integration, in a rule-based environment, of evi­ dences derived from several low level processes (edge detection, region analysis ... ); the aggregation of elements - edges into lines, lines into regions - is performed on the basis of Gestalt principles [12]. A similar approach is followed also by Flinchbaugh and Chandrasekaran [13].

This paper, stemming from some of the ideas and intuitions of the mentioned systems, deals mainly with iconic segmentation of images, with the purpose of provid­ ing a description of images entities, like, for example, closed contours; some principles derived from the psychol­ ogy of perception are used, many of which have been developed on an experimental ground. In particular it is shown how data derived from early processing stages can be integrated in a Iconic Data-Base, and how this data­ base can be suitably organized for symbolic manipulation. The heuristics used to segment images of a simplified real world (a low scale model of an office-like environment with planar surfaces) are described, together with their actions on a Symbolic Data-base. Experimental results are presented.

II BUILDING A ICONIC DATA-BASE

The edge detection procedure is based on the so­ called Marr-Hildreth approach, i.e. on the detection of the zero crossings of the second derivative of a Gaussian filtered image [ 1]. The filtering operator is a rotationally symmetric Laplacian of Gaussian producing contours that are closed or closed at the image boundary. During the extraction of the zero crossings, local orientation and slope are also computed to provide additional information about the local discontinuity. Unfortunately these measures are not sufficient to evaluate the perceptual relevance of a given edge because edge detection is a local operation while the perceptual evaluation of a scene is driven also by global features and by some kind of knowledge about the scene. For this reason, removing the irrelevant edges at this early stage of the visual process may be a hopeless procedure unless suitable hypotheses are made about the global pro­ perties of the scene. For the class of scenes used in our experiments (a low scale model of an office-like environ­ ment with planar surfaces, see Figure 1) the information about local orientation is used to extract linear segments as primitive elements to code boundary information (see

below).

Along with the information about contours, also regional segmentation is performed. In spite of the fact that boundary and regional representations are two different descriptions of the same entities, designing a unique frame­ work to include both boundary and regional information is no simple matter. The problem has been faced stemming from the observation that the image convolved with the Laplacian of Gaussian operator is naturally segmented into regions of either positive or negative sign, and that the borders of these regions are the zero-crossings contours. This regional segmentation has the advantage of being exactly dual to the boundary representation, making easy the process of switching from one description to the other. Moreover, due to the fact that all the contours are closed, each contour is the boundary between only two regions (one of negative sign, the other of positive sign).

At the present stage of implementation for each image a stereo pair is acquired in order to extract rough depth information [14] and, from a single view three images are acquired using red, green and blue filters.

I

-----·

The RGB color coding is then transformed into a HSV (hue, intensity, saturation) color base. The zero crossings are extracted from the "intensity" image only but the infor­ mation about local slope is computed also for hue and saturation. Each contour is described as a chain of seg­ ments (see Figure 1), which seems to be a reasonable hypothesis for the class of objects under consideration; each segment codes, besides its position in the image domain, the local properties measured from the edge detec­ tion algorithm (averaged along the segment) and a pointer to the two regional descriptors. The inclusion of explora­ tion strategies to provide 30 information by means of active movements of the observer within the environment is under consideration; occluding contours [15, 16] and motion [ 17, 18] are used as volumetric sources of information.

III BUILDING A SYMBOLIC OAT A-BASE

This section shows how numeric data derived from early processing can be organized in a data- base suitable for symbolic manipulation (Symbolic Data-Base, SOB).

SOB has been hierachically organized into three linked levels:

• segment level (SEGM)
• region level (REGION)
• simple object level (OBJ)

It is worth pointing out that SOB is not just an inter­ face to allow symbolic manipulation but it is a data struc­ ture shared by different processes which interact through it; these processes are (see Figure 2):

• (I) Image Reasoner, described in the next section;
• Perceptual Processes, devoted to scene segmentation;
• Conceptual Processes, devoted to scene interpretation.

"'

Figure 2 - Architecture of the system

In this paper only Image Reasoner is described; (2) and (3) are presented in [20, 21].

When Image Reasoner starts, a SOB for an image is created. At the beginning of the analysis, no regions and simple objects are present in SOB (no clustering has still been performed). When during the analysis, a set of seg­ ments is clustered into a closed contour, a region structure is created. In case Image Reasoner or Perceptual Processes are able to make some hypotheses about the presence of groups of regions (see next section), a simple object struc­ ture is created. Appendix I shows examples of segment and region coding in SOB together with the general struc­ ture of the simple object level.

It is worth noting that when during the analysis SOB is modified (fields content may be changed and new struc­ tures added), the old information is not destroyed; it is placed in a long term memory (LTM) from where it can be resumed if necessary, i.e. if backtracking is required.

IV REASONING ABOUT SYMBOLIC OAT A

To locate significant enuues in images it is necessary to organize segments already coded in SOB into closed con­ tours which do not, by the way, necessarily correspond to contours in the scene domain. This task is performed by the Image Reasoner (IR) .

At this purpose, information about segments is con­ sidered selectively on the basis of their length (that is, longer segments are analyzed first). All the information is hierarchically explored; information at a higher detail is used to confirm or reject the inferred structures.

IR is organized as a production system; general heuris­ tic knowledge about image properties is embodied into rules of the type precondition --) action. Actions can modify segments and regions as follows:

• create a new segment on the basis of features of

/

Figure 3

existing neighbour segments;

• delete segments which are discovered to be generated by noise or unsignificant details;
• merge more segments into one segment;
• create new regions and compute their features;
• delete existing regions;
• modify features of existing regions;
• merge two regions into one region;
• subdivide one existing region into subregions.

The output of IR is a line-drawing representation of the original image on which perceptual processes (PP) can perform occlusion analysis.

It is worth noting that IR and PP are interacting processes in the sense that, in case PP find some incon­ sistencies, IR is recalled on a better knowledge basis. At the actual stage of the implementation of the system IR is composed of about 320 rules logically divided into Segment Rules, which operate on segments and hypothesize new seg­ ments and segment clustering, and Region Rules, which hypothesize directly the presence of a region.

Let's consider the situation shown in Figure 3. By applying the rule:

the two segments can be merged into a new one. Predi­ cates in the rule preconditions return a degree of evidence to take into account errors which may occur at the early processing level; the evidence associated to the rule action is the wheighted average. A threshold criterion is used to decide when backtracking is needed. This rule can be regarded as an application of the Gestalt principle of "good continuation" . It can handle those situations where region contours present partially occluded lines which are per­ ceived by a human observer as converging into a common vertex. The term occlusion refers in this context, not only to lines hidden by physical objects, but also to lack of information due to early processing errors.

As an example of Region Rules let's consider the con­ cept of subjective contours [22, 23], i.e. those illusory con­ tours which are perceived in spite of the absence, in the visual field, of discontinuities in brightness, or surface orientation, or color and so on. In [26] a computational model for treating subjective contours has been presented, based on the concept of induced inhomogeneity [24,25]. Some rules implementing that model have been introduced in this system to handle situations like the one shown in figure 4a. An example of such rules is the following:

R_SUB.J_CONT_279:

contOur of figure 4a.

By using the information about the X, Y ,Z coordinates of each segment vertex (see appendix 1), IR is also able to infer qualitative spatial orientation of regions and spatial relationships among them. These qualitative attributes are coded as follows:

Such attributes are used by perceptual and cognitive processes.

As far as the control strategy is concerned, it has been already pointed out that the analysis starts from longer seg­ ments. Actually, four length thresholds are considered, which have been experimentally fixed. Processing an image with a lower threshold means adding new segments; their consistency with manipulations operated at a higher thres­ hold is checked and the additional constraints introduced by the presence of new segments are, possibly, used for back­ tracking.

V CONCLUSIONS

In this paper a Iconic Data-Base and a Symbolic Data-Base have been described as shared dynamic struc­ tures for low level image segmentation and high level per­ ceptual reasoning. The main characteristics of the approach are: i) the use of multiple sources of information (including edges, color, stereo and multiple views), ii) the combined extraction of regional and boundary information, iii) the use of symbolic reasoning to extract perceptually important entities, iv) the possibility of reasoning over seg­ ments or groups of segments and not over single edges, which constrains the combinatorial explosion of rules appli­ cability, v) the use of perceptual models with a strong psychological experimental background;

Low level processing is implemented in C on a MICROV AX II connected to a VDS 7001 - Eidobrain image processing system. Symbolic Data-Dase and Image Reasoner are implemented in Franz Lisp and OPS5 on a VAX-Station. Data transfer is performed through ETH­ ERNET network.

Future developments of this work are concerned with the introduction of volumetric information derived from occluding contours and motion; an interface with a geometric modeling environment based on octrees is also envisaged.

APPENDIX 1

Figure ~ shows the general SlriiCtW'e of segment, reJion and object descriptor in SDB.

----IVDIIIICI----- ...

The meaning of the various subfield is explained as follows. Every SEGM structure containa a symbolic label (LAB_SEGM) and an order numbering (LOG_POS) along a possible segment chain (NCONT). Every extremal point of a segment (EXTRi) can be a fork point (In this case IS MULT=TRUE) or not. The numerical information (INFO) is related to HSV color base (DELTA_H, DELTA_S, DELTA V). REGIONs information is related to pointerS to the two regional-descriptors. The EVIDENCE field containa information about the degree of evidence of the presence of the hypothesized segment. The initial hypothesis is that data derived from L-L stages are TRUE; in this way the EVIDENCE field of a SEGM derived from iconic data is intially set to 1.0. Every REGION structure containa a symbolic label (LAB REG), pointers to the segmenta composing the hypothesizedregion (PTR_SEGM), a regional descriptor (RDESCR) which is actually only the average light intensity, computed from con­ tours segments. A region is found by applying some rules which are stored in the RULES field and a value is assigned measuring the EVI­ DENCE of the hypotheses which have triggered the clustering operationa.

Every OBJ structure contains a symbolic label (LAB_OBJ), pointers to segments composing the hypothesized regiona (PTR_REG), the RULES used to assume the presence of a simple object and a meas­ ure of the EVIDENCE of the simple object.

Acknowledgements

The authors wish to thank Manuel Leeuwenberg, Walter Gerbino, Marco Sambin and Peter Van der Helm, for their helpful comments and suggestions. The present work was partially supported by an ESPRIT grant (P419) and from the Italian Ministry of Education under a special grant on vision.