Recognition of Indoor Images Employing Qualitative Model Fittingand Supporting Relation between Objects
Keiji Yanai
Department of Computer Science,
The University of Electro-Communications

1-5-1 Chofugaoka, Chofu-shi, Tokyo 182-8585, JAPANyanai@cs.uec.ac.jp

Abstract
In this paper, we describe a new design of a recognition system for a single image of indoor scene including complex occlusions. In our system, rst, thesystem estimates 3D structure of an object by tting a3D structure model to the image qualitatively. Next, bychecking supporting relation between objects, it eliminates object candidates that are impossible to exist andestimates actual objects from their parts in the image.
Then, nally, we recognize objects that are consistent with each other. We implemented the system as amulti-agent-based image understanding system. This
paper describes an outline of the system and results ofexperiments.

1 Introduction
In usual indoor scene various objects are piling up.
For example, there exists a desk on the oor and abook on the desk. Therefore, many occlusions occur,and the recognition of an indoor image must cope withthem. In many conventional researches of the recognition for scene including occlusions, an exact shapemodel of a target object was used to recognize a single object. They t the model to partial features andestimated total appearance of the target object. They
didn't make use of spatial relation between objects.
The objective of our research is to recognize objects
in a single image of real world scene including multiple objects and complex occlusions. In our research,the \recognition" means to obtain a category nameof the object, such as \desk" and \chair", from realworld scene. However, objects represented by a category name have many di erent 3D shapes. So it is impossible to prepare exact 3D models in advance. Then,we pay attention to functional structure of objects, andwe use a qualitative 3D-structure model that represents
essential structure for function of an object[3, 5].
But, only qualitative model tting is not enough forscene including complex occlusions. Then, we introduce \supporting relation" that describes that which
object supports which one. All objects except background objects, such as oor, wall, road, and sky, mustbe supported by other objects in the real world dueto the gravity of the earth. We know such physicallaw empirically, so we can expect an existence of adesk under a workstation in the complex scene even

Koichiro Deguchi
Graduate School of Information Sciences,
Tohoku University

Aramaki-aza-Aoba 01, Aoba-ku, Sendai 980-8579, JAPAN

kodeg@fractal.is.tohoku.ac.jp

if the desk can't be seen. We provide such physicalknowledge about supporting relation with the system
and make the system with an ability to estimate actual objects from parts seen in the image and eliminate
object candidates that are impossible to exist.
In this paper, we describe an idea to introduce suchqualitative 3D model tting and \supporting relation"
checking mechanism to our multi-agent-based image
understanding system, which is called MORE (Multiagent architecture for Object REcognition)[7]. We also
show results of recognition experiments.

2 Recognition strategy
2.1

Recognition by qualitative 3D model tting

We use a prototype model that represents essential functional structure common within same kindobject[5]. For example, the functional structure of a\chair" is a combination of sitting surface and one orfour legs, and that of \desk" is a combination of desk
face and four legs. The prototype model is represented
by some model elements and a model graph. Modelelements are polygons and straight line segments according to the appearance of the object (Fig.1(a)), andthey have information about their real shape and theirgenerally expected pose in the real world. A model graph represents connection relations between themodel elements (Fig.1(b)). Each model has the extentof relative size among each elements and information
which elements are supportable and to-be-supported(Fig.1(c)). Here, the \supportable" element and the\to-be-supported" element mean that the element can
support other objects and the element must be supported by another object, respectively. These properties are used in the stage of \checking supporting relation" described later. For example, the model of \desk"
has one parallelogram as its supportable element andfour vertical line segments whose bottoms are its tobe-supported elements as shown in Fig.1(d)(e)(f).
For estimating regions of an object candidate, rst,
we extract line segments and regions by conventional methods, for example, Canny edge detector, Houghtransformation, region growing segmentation method,snake and so on. Next, we search groups of line segments and regions corresponding to each element of amodel. We t the model to the group of line segments
and regions extracted from the image (Fig.2). Here,PG(parallelogram)[a,b]vertices: fl, fr, rr, rl

PG
fl, fr, rr, rl

to-be-supported: PG(all)supportable:VL(b)(rectangle,horizontal)

VL (vertical line)[c]vertices: t, btttt
VL VL VL VL

1.0<b/a<2.50.7<c/a<1.3(b) model graph(c) properties &extent of ratio(bar,vertical)(a) elements

supportable region

candidate region of "desk"

arlb
fltt

bb

to-be-supported region

rrt

fr

"desk"
is supported
by "floor"bc
supportable region(d) appearance of model(e) supportableelement(f) to-be-supportedelements

candidate region of "floor"

Figure 1. Model representation of \desk".

none

to-be-supported region

Figure 3. Checking \supporting relation".

input
image"desk" prototype model
lines from image

virtual basis region"WS" candidate

regions from image

to-be-supported regions of "ws"= virtual basis regions of "deskbasis edges and region candidate edges and region

Figure 2. Estimating a \desk" candidate.

we call the lines and regions used in model tting as\basis edges and regions", and the regions where anobject is estimated to exist as \candidate region". A
candidate region is the total region expected without
occlusions. In addition, by using information about\supportable" and \to-be-supported" elements, we estimate \supportable region" and \to-be-supported region" in the image.
We compute con dence value of a candidate as aweighted sum of the ratio of basis region to candidate
region of each element:Vs =XW bn=1iiiei(1)where n is the number of elements, bi is the number ofpixels of a basis region or edge, and ei is the number ofpixels of candidate region or edge. Wi is the weighting
factor, and it is provided as a priori information witheach model. For example, \desk" has two elements,
desk face and legs, and Wi for them are set as 0.7 and0.3, respectively. Con dence value of a candidate isused for resolving con ict among candidates.

2.2 Checking of supporting relation
Every time the system generates a new object candidate, it examines if the \supporting relation" holds
between already generated candidate and the new one.
By checking supporting relation between objects, thesystem eliminates object candidates that are impossible to exist and estimates actual objects from parts
seen in the image.
\Supporting relation" holds when the object can beconsidered to locate on another object and to be supported by it. Checking the \supporting relation" isbasis edges and regions+ virtual basis regionbasis edges and regionsof "desk"

Figure 4. Estimating a \desk" candidate that supports the \workstation" candidate.
carried out by examining whether the to-be-supported
regions of the object is almost included in the supportable regions of another object. If so, the former
object is regarded to be supported by the latter one.
We present an example including a relation that \deskis supported by floor" in Fig.3.
If a candidate has no supporting relation, to-besupported regions of the candidate are regarded as\virtual basis regions" and the system searches a newcandidate with supportable regions including the virtual basis regions(Fig.2). In short, \virtual basis regions"are regions that can be regarded as regions of supportable elements of a new candidate. Then, the system
can detect a new candidate that couldn't be detected before. For example, when the system generates a\workstation (WS)" candidate with no supporting relation, it regards the to-be-supported region of \WS" asthe virtual basis regions of a desk face element (Fig.4).
By this mechanism, the system recognizes an object
occluded by another object.
If candidates except background objects have nosupporting relation, nally, the candidates are canceled.

2.3 Relational knowledge
The system has \relational knowledges". They aredescriptions about relative relation generally expected
between two objects. It is used for computing con dence value of relation and expecting the region whereown target object exists with high possibility. It is represented by combination of \relation name", \source

"chair" agent

agent A"chair" rec.module

image

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

region of object
candidate in an image

object's name" and \destination object's name". For
example, ``on(book,desk)'' means \a book is usually on a desk". At present we have three types ofrelations, \on", \in front of" and \on same plane".
The system judges whether each relation is holding by
the information of supporting relations and the relative
location of objects in the image.
Con dence value of relation is weighted sum of holding relations:

XC nr=1i i(2)iwhere r is the total number of relations, ni represents
if relation i is holding, it takes a value of 0 or 1, andCi is weighting factor.

2.4 Con ict resolution
If two or more agents generate di erent candidates
in the same region of the image, con ict occurs. Conicting candidates are compared by their con dence
values of candidates at rst. If di erence between thehighest value and the second highest value is more thancertain threshold value, all except the highest one arecanceled. Otherwise, con dence values of relation arecompared, then all except the highest one are canceled.
If both di erences are small, a temporary decision ismade by comparing sizes of their regions.

3 Overview of the system(2)agent Bcomm. (3) broadcast comm. (5) rec.
modulemodulemodule(4) objection

region of object
candidate in an image

Figure 6. Flow of messages.

Figure 5. Basic structure of the system.

Vr =(1)

3.1 System architecture
We implemented the system based on \MORE" architecture we proposed[7]. It is multi-agent-based architecture, and the system is constructed as an assembly of agents that recognize objects from an image separately. It enables to recognize various di erent kindsof objects by adding agents. One agent consists of arecognition module and a communication module.
A recognition module (RM) has an input image,recognizes only one kind of target object, reports its region in the input image, and generates an object
candidate.
A communication module (CM) carries out cooperation among agents. It checks supporting relations
to candidates generated by other agents and resolves
con ict among the agents. Every CM has relational
knowledges. Using them, it computes con dence valueof relation and estimates the region where own target
object exists with high possibility.

3.2 Processing ow
The processing ow among all the modules ismessage-driven. We describe the detail ow of messages in case of the example of Fig.6.
(1) Each CM sends an "initial recognition request" toeach respective RM. Then, each RM starts therecognition.
(2) Every time RM nds an object candidate, it sends
the candidate and its con dence value of the candidate to the CM.
(3) The CM checks if the candidate is supported by anyother candidates, and broadcasts the information of
the candidate 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, a con ict resolution is processed between the CMs concerned.
(5) If the broadcasted object candidate has no supporting relation and the receiving agent has relational
knowledge that the candidate is usually on its ownobject, the CM of the receiving agent sends a \conditional recognition request" to its RM. The RM starts
to nd object candidates with supportable regions
including the virtual basis regions of the candidate.
If all 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 systemcompletes. The details of this architecture were written
in [7].

4 Implementation and experiments

We have implemented an experimental system with
8 agents (\desk", \chair", \wall", \ oor", \book",\cup", \pen", and \work station (WS)") on PC cluster
system that consists of 8 PCs(Intel Celeron 450MHz)
using the PVM library[2]. In this system, each agent
is implemented on each one PC.
In the experiment for the sample image no.1
(Fig.7,320x240), ve objects (a \ oor", a "desk", two\workstation(WS)", and a \wall") were recognized.
First, two \WS" candidates were found, and the WS
agent broadcasted the candidates without \supporting
relation" to all other agents. Then, the desk agent,receiving them, estimated desk face by integrating basis edges and regions of \desk" (Fig.9) and to-besupported regions of the two \WS", that is virtual basis
regions of \desk" (Fig.10). It estimated candidate region by model tting. In this way, although only partof the desk face could be seen, a \desk" had been recognized using to-be-supported regions of the objects

5 Related work

Figure 7. Sample image
no.1.

Figure 8. Recognition
result.

Figure 9. Basis edges
and region of a \desk".

Figure10.
Tobe-supported regions oftwo \WS".

Figure 11. Sample image no.2.

Figure 12. Recognition
result.

The objective of our work is the scene recognition
when exact models of target objects are not available inadvance. Tenenbaum's work[6], in which segmented regions were labeled by the relaxation method, had similar objective to our work. But their work used too simple methods, and it was not available for complex images. After that, knowledge-based recognition systems, for example, the Schema System[1] and SIGMA[4],appeared. They used both models for single objects
and relational knowledges among objects, and achieved
an integration of bottom-up and top-down processings.
Our work is similar to theirs, but their target was notindoor image but outdoor images or aerial images thatscarcely include occlusions.

6 Conclusion

In this paper, we proposed a system that estimates
3D structure of a target object by tting qualitativemodel qualitatively, veri es object candidates by checking \supporting relation" using \supportable regions" and \to-be-supported regions". It totally realizes
a exible recognition for real world images including
complex occlusions. We have implemented the systemas a multi-agent-based image understanding system on
a PC cluster system.

Acknowledgments

A part of this work was supported by a grant fromthe Inamori Foundation.

References
Figure 13. Sample image no.3.

Figure 14. Recognition
result.

on the \desk". In addition, in this experiment, nally,some false candidates were canceled by checking \supporting relations".
In the experiment for the sample image no.2
(Fig.11,320x240), six objects (two \books", a \desk",
a \chair", a \ oor", and a \wall") were recognized(Fig.12). It was dicult to recognize front and backright legs of \desk" in this image, but the system assumed that there were four legs under desk face andthey were on the \ oor" by the model tting. No conicts with other object candidates occurred for thisrecognition, so the assumption was regarded as true.
Similarly, a \chair" was recognized on the \ oor".
Sample image no.3 (Fig.13,640x480) is more complex scene, so we used a higher-resolution image than
the image no.1 and no.2. Three \desks", four \WSs"and four \books" (two ones were false) were recognized(Fig.14). Especially, though almost of all the desk faces
were covered with four WSs, the two back desks could
be detected by using supporting relation mechanism.

[1] B. Draper, R. Collins, J. Brolio, A. Hanson, and E. Riseman. The schema system. International Journal ofComputer Vision, 3(2):209{250, 1989.
[2] A. Geist, A. Beguelin, J. Dongarra, W. Jiang,
R. Manchek, and V. Sunderam. PVM: Parallel VirtualMachine. The MIT Press, 1994.
[3] D. Kim and R. Nevatia. Recognition and localizationof generic objects for indoor navigation using functionality. Image and Vision Computing, 16:729{743, 1998.
[4] T. Matsuyama and V. S. Hwang. SIGMA: A knowledgebased aerial image understanding system. Plenum Press,New York, 1990.
[5] L. Stark. Functionality in object recognition. Computer
Vision and Image Understanding, 62(2):145{146, 1995.
[6] J. M. Tenenbaum and H. G. Barrow. Experiments ininterpretation guided segmentation. Arti cial Intelligence, 8:241{274, 1977.
[7] K. Yanai and K. Deguchi. An architecture of object
recognition system for various images based on multiagent. In 14th International Conference of PatternRecognition, volume 1, pages 278{281, 1998.