A Production System for Region Analysis

A PRODUCTION SYSTEM FOR REGION ANALYSIS

Yu-ichi Ohta, Takeo Kanade, and Toshiyuki Sakai

Department of Information Science Kyoto University Kyoto, 606, JAPAN

Production system architectures are useful for knowledge representation. We have applied the architecture to image analysis in the framework of region growing and developed an outdoor-scene anaJyzer. In this paper , the following three problems are addressed to make production systems workable in scene analysis . l) Appropriate size of knowledge represented in a production rule. 2 ) Reduction of computation. 3) Control of the analysis toward goal.

l. I.NTRODUCTION

A production system consists of a set of produc­ tion rules and a database. A production rule is the unit of knowledge r epres entation and the database records the facts about input image. The control structure of production systems is heterarchical. Each production rule is a pair of a condition and an action and is "watching" the database. Whenever the predicate in the condit ion part is satisfied, the system evaluates the action part and modifies the database. Because of this, it is easy to add or modify knowledge in production systems. This is u useful feature to organize an analysis system for complex scenes, such as outdoor scenes, which include various kinds of objects.

We have made an outdoor-scene analyzer in the framework of region growing using production system for knowledge representation and control structure[l). In this paper, we describe the outline of our scene analyzer and discuss production systems from the view point of image analysis.

2 . OUTLINE OF ANALYSIS MECHANISM

Figure l shows the schemati c diagram of the analysis mechanism in our system. The system receives an input color image as digitized red­ green-bJue intensity arrays and constructs a semantic description of the scene.

Preliminary segmentation The primary objec­ tive of the preliminary segmentation process is not the reduction but the structuring of raw image data i nto usable information; The input color image is segmented into a set of coherent

"patches" and organized into a fully structured symbolic description. In the higher-level pro­ cesses , all picture-processing operations are performed on this structured description rather than the raw image data. The "patch" is an important element to describe the input image and to build a production system in our region analyzer.

Plan generation The plan generation process extracts the overall structure of the scene to obtain clues concerning which knowledge should be applied to what part of the scene. First, pat ches with large area are selec ted as key­ patches from the segmented image. It is reason­ able to assume that most of them correspond to large parts of objects in the scene. Labels of obj ects are assigned to each of the keypatches and the degree of correctness is computed using knowledge, which is represented as a collection of knowledge-blocks[2], about the properties of and the relations between objects. The result of the interpretation, called a plan, is a set of labels and their correctness values assigned to each keypatch, e.g. (sky=0.6, building=0.2, tree=O.l, road=O.l), etc. The plan is updated whenever significant fact , such as the position of scene horizon, is found by the production rules in the analysis process.

Database The structured description of a segmented image, the plan, and the scene descrip­ tion so far obtained are all stored in the data­ base. Figure 2 illustrates the structure of the scene description built as the result of analysis. Scene, object, region, sub-region, patch, and pixel are the important concepts which constitute the hierarchical structure of our description. The patch corresponds to the result of the preliminary segmentation. All the descriptive elements are organized into the hierarchical structure by "part-of" relation. Relations between parts of objects, such as "adjacent" or "occluded", are described between corresponding regions.

Production rules and agenda There are two types of production rules in our system; to-do rules and if-done rules. They correspond to consequent and antecedent theorems of PLANNER[3], respectively. A to-do rule performs basic oper­ ations in region growing process . It examines each patch which is not yet interpreted in the segmented image by the fuzzy predicate in its condition part and determines whether the action can be executed for it. The executable action is given a score to indicate its priority, and added into the agenda. The agenda manages those actions which are executable in the present context through their scores. The action with the highest score is executed and as the result the agenda is updated. An if-done rule is triggered by the execution of a certain action of the to- do rules. It performs an additional operation in making the scene description, such as extracting the position of scene horizon, etc.

3. DISCUSSIONS

We have to solve three problems to import the production system architecture to image analysis. The first is the problem of what "size" of pro­ duction rule is appropriate for region analysis, the second is the problem of how to reduce the amount of computation, and the last is the prob­ lem of how to direct the analysis to goal.

0 What "size" of production rule is appropriate?

What size of knowledge should be represented by one production rule? As an example of "large" knowledge size, it is possible that each produc­ tion rule corresponds to one object to be extracted and has whole knowledge about the object. This scheme enables to perform skillful analysis according to the characteristics of each object. On the other hand, the rules become large and complex and it is difficult to manage them.

Small sized knowledge In our system the size of knowledge represented by a rule is fairly small. Each rule is described as a combination of basic operations in region growing: selecting an un-interpreted patch from the segmented image, assigning a label to it, and assembling it into the scene description. This scheme has the following merits: each rule is simple and easy to modify, and the interaction among rules can be performed in a clear way because the access method to the database is simple.

Reinforcements Because the analysis proceeds patch by patch in our scheme, it is difficult to deal with global constraints such as object shape or relation between objects. We took three steps to cope with this situation. First, a plan is generated as rough interpretation of the input scene. This enables the production rules to catch information about global structure of the scene. Secondly, patches can be dealt with as a set at a time, and it becomes possible to extract object which is defined as a combination of mutually constrained patches such as windows of a building or a car on r oad . Lastly , we have devised special rules which extract information from the segmented image without sticking to the patch-by-patch analysis. This kind of rules, for example, is used to extrac t the shape of a building.

0 How to reduce the amount of computation?

In production systems the control program must grasp the state of executable actions at any moment in the analysis process. The agenda mus t be updated whenever the database is changed. Roughly speaking, the number of tests to be done each time is estimated as:

(the number of un-inte rpreted patches)

X (the number of production rules). It becomes several thousancl and it is too many. Furthermore, the predicate in the condition part of the production rules includes time- consuming pictur0- processing functi ons . It is necessary to reduce the number of the patches and produc­ tion rules which must be actually examined at a time . For this , the structurr. of scenes must be ttiken int o consideration.

"Globullty" und "Locality" A scene usually has two different properties from the view point of image analysis : "Globa.:.i ty" and ".:..Ocali ty". Analysis results such as determination of scene horizon or detect ion of objects may have signifi­ cant influence on the analysis of over all struc­ ture of the scene. This property is called "Globality". On the other hand, the results of analysis in a small part of an object scarcely has influence on the analysis of other parts in the scene. This property is called "Locality" . These two properties are utilized in the control

structure of our scene analyzer.

Scene phase and object phase In order to deal with such t wo propert..i cs o f scenes , two phusen art' set up in tlw control program. They are scc·ne phase and objec~ L phase . The task of the sc~pnc phase is to analyze overall structure of input scene without sLicking to details. So, it is almost meaningless to examine small patches in the scene phase analysis and only the key­ patches are examined. Whenever a keypatch is labeled, the scene phase is activated and all un-interpreted keypatches are re-examined. In the object phase, analysis of detailed structures are performed under the context of the results in the scene phase analysis. When a patch which belongs to a object is labeled, the object phase corresponding to the object is activated and the patches touching the patch just labeled are examined or re-examined.

Dividing rules into subset:> The set of pro­ duction rules can be divided into subsets to be used in the scene phase and the object phases corresponding to each object. In each phase, only the subset corresponding to that phase is activated by the control program to examine the un-interpreted patches.

Consequently , the number of tests to be done at a time is r educed to several .LO ' s .

0 How to direct the analysis to goal?

It is an important feature of production systems that each production rule independently checks the database and modi fies it whenever the condi­ tion is satisfied . However, two problems need to be considered to make this mechanism actually work ; a method to direct the analys is to goal and a method to r esolve the conflict among the executable actions which are inconsistent with each other.

Score As was described , evc~ry executable action is registered in the agenda with its score and the action whi~h has the highest score is executed to change the database . Then the score plays an i mportant role to direct the analysi s toward goal. The value of score asso­ ciated to each c'xecutable act Lnn is cal c~ulated as the sum of a base value and a premium value. The base value is a constant given to each pro­ due tion rule, and it plays a role to specify the order of analysis. The premium value is given as the degree of satisfaction of the condition of production rul e at the situation the rule was examined, and it plays a r ole t.o guide the analysis toward the correct interpretation. To sum up, the analysis proceeds toward goal guided by the premium values following the strategy specified by the base values.

Conflict resolution In our system , the basic operation which changes the database is very simple : to assign an object label to u patch. This makes the detection of the,· incorwiL;tent actions quite straightforward. Whcncv,~r a puLch is interpreted by executing an action registered in the agenda, every action whi ch is e;oing to give a different interpretation to the patch just interpreted is decided to be inconsistent and deleted from the agenda.

In this paper , we described a production system which was applied to region analysis. Some problems and their solutions were discussed .