An Architecture of Object Recognition System for Various Images
Based on Multi-AgentKeiji Yanai
Department of Computer Science,
The University of Electro-Communications

Koichiro Deguchi
Department of Mathematical Engineering andInformation Physics, University of Tokyoyanai@cs.uec.ac.jp

deguchi@meip7.t.u-tokyo.ac.jp

1-5-1 Chofugaoka, Chofu-shi, Tokyo 182-8585, JAPAN

7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, JAPAN

Abstract

An image understanding system for real world images which has an ability to recognize various kinds ofimages is proposed. We propose a multi-agent architecture to integrate object recognition modules for individual target objects. In our method, recognized resultsby di erent agents are fused not only on the evaluations by each modules themselves but also on relationsof object locations, sizes and so on. This is carriedout autonomously between the agents concerned, andthe most reliable result is selected after the arbitration
between them. We implemented an experimental system on a parallel computer, and achieved recognition
for both indoor and outdoor images.

1. Introduction

An image understanding system for the real worldmust be able to recognize various kinds of images.
We have been developing the recognition system thatrecognizes arti cial and natural objects in a single
image[4]. Here, \recognition" means to obtain a category name of an object, for example \desk" or \chair".
To achieve this image understanding, we have to utilize
not only shapes of objects but also relations between
them as a recognition clue.
To realize such recognition we propose an architecture of an assembly of agents. In our architecture eachagent consists of a recognition module to recognize single kind of object and a communication module tocommunicate with other agents.
We describe the system architecture and experimental results on the system implemented on highly parallel computer AP1000+.
The conventional image understanding systems
based on multi-agent architecture aimed at integration of multiple algorithms[2] or exible use of relations among objects[1]. They needed consideration ofinteraction among agents one by one and complicated description of relations among objects. Therefore"chair" agent"chair" rec.module

image

resultcomm. modulecomm. modulecomm. module"desk" rec.module"floor" rec.module"desk" agent"floor" agent

Figure 1. Basic structure of the proposed system. It
is constructed as assembly of agents, and each agent
consists of a recognition module and a communication module.

they usually restricted the target image. To construct such general recognition system, their architecture
is not e ective. In our architecture, we only prepare
recognition modules for each single kind of object independently. Adding cooperation mechanism, that iscommunication module, to integrate them, we can implement the system easily.

2. Basic concept of our system

In our architecture the system is constructed as an
assembly of agents that recognized objects from an image independently. By adding agents it enables to recognize di erent kinds of images. In this architecture
one agent consists of a recognition module and a communication module. Each recognition module recognizes only one kind of object. Each communication
module communicates with other agents using relational knowledge between objects (Fig.1).
Each agent runs in order to recognize as many objects as possible in the image. Then sometimes con icts
occur among agents, that is, two or more agents nd
di erent objects in the same region on the image. Thenthey negotiate with each other to resolve the con ict.

Each agent also makes use of the information of object candidates generated by other agent. For example, when \a car" is recognized, there possibly exists\road" under it. Such cooperative process is managed
by communication modules, while recognition modules
deal with input images directly.

agent Arec.
moduleregion of object
candidate in an image

3. Recognition module and Communication module

(1)
(2)

agent Bcomm. (3) broadcast comm. (5) rec.
modulemodule
module(4) objection

region of object
candidate in an image

Figure 2. Flow of messages. (1) Initial recognition
request. (2) Information of an object candidate. (3)Broadcasting information of an object candidate. (4)Objection message. (5) Conditional recognition request.

A recognition module recognizes target objects asregions in an input image, and generates an object candidate. Our architecture do not assume special
implementation for recognition module.
In principle the recognition module recognize objects by extracting common features to various view points
and various instances from an image. For example, if
there are a parallelogram and four vertical lines below
it in the image, they are regarded as \a desk".
When recognition module nds regions of object
candidates, it scores evaluation value on it, then, sends
the information about the region and the evaluation
value to the communication module.
A communication module carries out cooperations
among agents. It keeps consistency to other agents tocheck candidates generated by the recognition module.
If a con ict between agents occurs, it negotiates withthe communication module of agents concerning thecon ict.
Every communication module knows the candidatesof other objects by exchanging the informations withother modules. If it has knowledge about relation between the candidates of other objects and its own object, it sometimes picks up recognition clues to recognize its target objects. Then, it sends them to therecognition module. \Relational knowledge" is a description about relation generally expected between two object. A communication module has only knowledge related to own target objects.

ation value of the object candidate to the communication module.
(3) The communication module broadcasts it for all other agents.
(4) Other agents examine if the broadcast is consistent
with own object candidates. If not, the agent sends
back an objection message. Then, con ict resolution
is carried out between the communication modules
concerned.
(5) When some relations exist between the broadcasted object candidate and an object of the receiving
agent, the communication module of the receiving
agent estimates region where it is expected for target objects or scale of object. The communication
module sends \conditional recognition request" tothe recognition module.
In addition to this, our architecture has \revivalmechanism". It revives an object candidate thatwas canceled once, when evaluation about relation ischanged and the result of comparison becomes invalid.
By this mechanism the system always keep object candidates that are consistent with each other.
If the modules of all the agents are in the state of
waiting for a message and there is no message on communication lines, the whole recognition of the systemhave completed.

4. Recognition ow

The processing ow of all the modules is messagedriven. Each module waits for a message from othermodules. If it receives a message, it responds the message. We describe detail ow of messages in case of theexample of Fig.2.
(1) An input image is sent to the recognition modules of
all the agents. Then each recognition module starts
recognition by the request from the communication
module.
(2) Every time a recognition module nds region, itsends the information of the region and its evalu-5. Cooperation among agents

There are two kinds of cooperations among agents.
 Con ict resolution between object candidates Recognition using relational knowledge for otherobject candidates generated by the other agent

5.1. Relational knowledge

Each communication module has knowledges about
relations generally expected between its own object and2







Table 1. Examples of relational knowledge.
desk on floor
desk taller than chair
ws on deskbook on desk

book

desk

Figure 3. Recognition using relational knowledge.
\Book" agent searches \book" candidates using information of \desk" candidate and relational knowledge of \book on desk".

Table 2. evaluation value about shape for \chair".
value
5432
1

"book on desk"

detected parts
sitting surface, seat back, stable legs
sitting surface, stable legs
sitting surface, seat backsitting surface with exact shapesitting surface with rough shape

5.2.2. Evaluation about relation

Each communication module makes evaluation
about relation by examining the number of relations
realized between its own and other objects. For example, when the communication module of \chair" agent
has relational knowledge \chair on floor", it examines if the region of \ oor" candidate exists under theregion of its own candidates in the image. If \ oor"
exists under \chair" in the image, relation \on" is considered to be realized.
The evaluation about relation is estimated by checking the relational knowledge one by one. The value isthe summation of weights of applicable relations.

other objects about relative location and scale between
two objects. They are called \relational knowledges".
Relational knowledges are represented by triplets of\source object's name", \relation name" and \destination object's name". We show some examples inTable 1.
5.2. Con ict resolution\Con ict" means that there exists the region wheretwo or more object candidates are assigned. When acon ict occurs, the concerning agents compare evaluation about object candidates and cancel one candidate.
The evaluation for candidate is done by combination ofevaluation value about shape and relation. In case of
con ict between three or more objects, the agents resolve it between two of them.
If a compatible relation holds between two objects,
one of the objects is regarded as hiding the other object. For example, if regions of \a desk" and \a book" areoverlapping and a relation knowledge \book on desk"
is applicable between them in the image, compatible
relation holds. When compatible relation holds, no objective message is sent.

5.2.3. Comparing con icting candidates

Two con icting candidates are compared by theirevaluation values about shape at rst. If di erence between two values is more than certain value, smaller
one is canceled. Otherwise, values about relation arecompared, then smaller one is canceled. If both differences are small, the decision is made by comparing
sizes of their regions.
5.3. Recognition using relational knowledge

Information on object candidates is broadcasted forreporting it to all the other agents. At this time byintegrating received information on candidates and relational knowledge, the agents sometimes can expect
the region where its own objects exist. For example, inFig.3, \desk" agent generates an object candidate, and\book" agent gets the information. Using relational
knowledge \book on desk" it estimates that a squareregion over \desk" region is \book".
The communication module of each agent examines
if it has some relation to received object candidates assoon as it receives. If some useful information is found,communication module sends it \conditional recognition request" to recognition module.

5.2.1. Evaluation about shape

Evaluation about shape is made for generated candidates by each recognition module. Evaluation value
is score in ve steps. The standard of the evaluation
depends on each recognition module. We only de ne arough standard for the value about shape.
We adopted such ve step evaluation, because each
recognition module has di erent standard of the evaluation and strict estimation is meaningless.
For example, we show the standard of the scoringfor \a desk" in Table 2. In principle, the system evaluates the value by examining the kinds of detectedcomponent parts.

6. Implementation and experiment

We have implemented an experimental system with
9 agents (\desk", \chair", \workstation", \wall",
3

no.1
no.0

Figure 4. Sample image
1 (indoor image).

Figure 5. Candidates of\desks".

Figure 8. Sample image
2 (outdoor image).

knowledge \ws on desk", cancellation did not occur
and they were regarded as compatible.
In this experiment, recognition using other object candidate and relational knowledge was realized.
\Workstation" agent recognized a workstation candidate using the information of a desk candidate and relational knowledge \ws on desk". Thus, though therecognition module simply regarded parallelograms asa keyboard or a display, a workstation could be recognized.
In the next experiment for the image of outdoor
scene shown in Fig.8 ve candidates (\sky", "a car",\road", \tree" and \wall") were generated. Con ict between \wall" and \sky" occurred, but \wall" wascanceled by comparing evaluation value about relation.
Finally we obtained the result shown in Fig.9.

no.0

Figure 6. A candidate of\chair".

Figure 9. Recognition
result (outdoor image).

Figure 7. Recognition
result (indoor image).

\ oor", \road", \car", \sky" and \tree") on parallel computer Fujitsu AP1000+ with 16 processor elements. Each agent that consists of a recognition module and a communication module is implemented onone processor element.
Implementation of each recognition module is di erent from one to one. For an arti cial object, we recognize by paying attention to the part that represents itsfunction[3]. For example, sitting surface is paid attention for \chair" and desk surface is for \desk". For anobject having no speci c shape like \road" or \ oor",
we use conventional region segmentation methods.
In rst experiment for an image of indoor scene
shown in Fig.4 ten object candidates (two \desks"(Fig.5), a \chair" (Fig.6), two \workstations", \ oor",\wall", \sky" and \tree") were generated by the respective agents. During this recognition con ict resolution
occurred seven times, cancellation occurred ve times,and revival occurred twice. Finally six objects of ve
kinds remained as shown in Fig.7. Total recognition
time was 76 seconds.
A con ict occurred between desk candidate no.0 in
Fig.5 and chair candidate no.0 in Fig.6. For chair no.0
a sitting surface, a seat back and a leg were found. So
the evaluation value about shape was 5. On the otherhand, for desk no.0 only a desk surface was found, so
the evaluation value was 3. Therefore, desk no.0 wascanceled. A con ict occurred between wall candidate
and sky candidate, too. Both of the evaluation values
about shape were 4, but the evaluation value about relation were 1 for wall because of \wall higher thanfloor" and 0 for sky. So sky candidate was canceled.
There was a region overlapping between desk candidate and workstation candidate. But, due to relation

7. Conclusion and future study

In this paper we described the architecture of image
understanding system based on multi-agent architecture. It is constructed as an assembly of agents for individual objects. Each agent has recognition and communication modules. The system recognizes both outdoor and indoor images by cooperation among agentsusing relational knowledge.
For future works, we will study how to evaluate object candidates, more e ective cooperation mechanism
and implementation of each recognition module.

References[1] T. Matsuyama and Y. Ohta eds. Special issue on \parallel, distributed and cooperative image understanding".
Journal of Japanese Society for Arti cial Intelligence,9(5):629{643, 1994. (in Japanese).
[2] Y. Ohta, M. Watanabe, and Y. Sumi. Approaches toparallel computer vision. The Institute of Electronics, Information and Communication Engineers(IEICE)Trans., E74(2):417{426, 1991.
[3] L. Stark. Functionality in object recognition. Computer
Vision and Image Understanding, 62(2):145{146, 1995.
[4] K. Yanai and K. Deguchi. Implementation of object
recognition system employing multiagent architecture
at highly parallel computer. In Proceedings of the Sixth
Parallel Computing Workshop, pages P2{a, 1996.

4