Systems and Computers in Japan, Vol. 33, No. 11, 2002
Translated from Denshi Joho Tsushin Gakkai Ronbunshi, Vol. J84-D-II, No. 8, August 2001, pp. 1741–1752

Recognition of Indoor Images Employing Supporting Relation
between Objects
Keiji Yanai1 and Koichiro Deguchi2
1

Department of Computer Science, The University of Electro-Communications, Tokyo, 182-8585 Japan
2

Graduate School of Information Sciences, Tohoku University, Sendai, 980-8579 JapanSUMMARY

1. Introduction
The objective of our research is to realize a systemthat recognizes objects and their spatial relations in a single
image of a real-world scene including complex occlusions.
In our research, “object recognition” means to obtain the
category name of the object, such as “desk” and “chair,”from an image of a real-world scene. In this paper, we
restrict the recognition target to an indoor scene, and we
propose a new recognition method for treating complex
occlusions.
In a usual indoor scene, various objects are piled up.
For example, there exists a desk on the floor and a book on
the desk (Fig. 1). Therefore, many occlusions occur, and theIn this paper, we describe a new design of a recognition system for a single image of an indoor scene including
complex occlusions. In conventional works, the systems
could not recognize images of an indoor scene including
complex occlusions. Our system can treat them by employing supporting relation between objects. In our system, first,
the system estimates the 3D structure of an object by fitting
a 3D structure model to the image qualitatively. Next, by
checking the supporting relation between objects, it eliminates object candidates that cannot exist and estimates real
objects from their parts in the image. Finally, the system
recognizes objects that are compatible with each other. We
implemented the system as a multi-agent-based image understanding system. In this paper, we describe the design ofthe system and results of experiments. © 2002 Wiley Periodicals, Inc. Syst Comp Jpn, 33(11): 14–26, 2002; Published
online in Wiley InterScience (www.interscience.
wiley.com). DOI 10.1002/scj.10142

Key words: ordinary object recognition; scene understanding; image understanding system; supporting relation.
Contract grant sponsor: Supported in part by a grant from the Inamori
Foundation.

Fig. 1. An example of an image of an indoor scene.
© 2002 Wiley Periodicals, Inc.
14

In our research, for the recognition of scenes including complex occlusions, we adopt 3D model fitting andreasoning about the “supporting relation,” which is different from simple 2D recognition by region segmentation andlabeling. First, we estimate the 3D structure of objects byqualitative fitting of 3D structure models that reflect thefunctionality of the objects themselves. Then, we reason
about the “supporting relation” between objects, which is
the relation in which an object is on another object.
Model fitting is first carried out for such image features as edges and regions extracted from an image. In thisresearch, since our main interest is an ability to deal withreal-world objects that have various shapes and views, we
adopt a method by which the variety of target object views
can be handled. Then we eliminate object candidates thatcannot exist and estimate actual objects from their parts
seen in the image by inferring supporting relations, whichenables us to compensate the uncertainty of estimation of
the 3D structure of objects. In this way, we can recognize
objects in an image of an indoor scene including complex
occlusions without exact shape models.
In this paper, we describe our approach to introducing
qualitative 3D model fitting and the “supporting relation”
checking mechanism, and next describe the knowledge ofrelations between objects, a method of evaluation of object
candidates based on it, and an implementation based on ourmultiagent-based image understanding system, which iscalled MORE (Multiagent architecture for Object REcognition) [14, 15]. Finally, we present the results of recognition experiments.

recognition of an indoor image must deal with them. In
many conventional investigations of the recognition of ascene including occlusions, an exact shape model of a target
object is used to recognize a single object. They fit themodel to partial features and estimate the total appearanceof the target object. In such a way, these approaches are
effective for recognition of objects that have constantshapes such as industrial parts. For real-world scenes, however, it is impossible to prepare exact 3D models of thetarget objects in advance, since objects represented by one
category name have many different 3D shapes. Therefore,
we use structural models of objects for the recognition ofreal-world scenes. For such a scene including complex
occlusions as in Fig. 1, however, it is difficult to recognize
all objects even with structural models.
In our research, using effectively the spatial relations
between objects that are not exploited in conventional recognition systems for a single object, we propose a newrecognition method for a scene including complex occlusions when exact shape models are not obtained in advance.
Our previously proposed system [14, 15] and conventional image understanding systems for a single real-worldimage including multiple objects, such as the Schema System [4], make use of spatial relations among objects as arecognition clue. Since their targets are landscape or aerial
images, they perform recognition by region segmentationand labeling. Basically, they treat a target image as a 2D
scene and interpret 2D spatial relations on the image evenfor a 3D scene. Such 2D analysis for a 3D scene is effective
in aerial images and distant view images of an outdoor
scene, since in such scenes the depth of target objects ismuch smaller than the distance to the scene. However, forshort-range view images such as an indoor image, 2D
analysis is not effective, because by 2D analysis the systemcannot determine front-and-back and top-and-bottom relations between objects. The depths of target objects in ashort-range view scene cannot be ignored. Therefore, 2D
analysis cannot make the best use of spatial information
among objects, and is not effective in handling complex
occlusions.
On the other hand, since humans have knowledge ofthe rough 3D structure of objects existing in the real world,even from a single image they can estimate the 3D structureof objects and 3D spatial relation among them. A humanalso has a knowledge of physical laws, such that an object
without support falls. Thus, for example, if a personal
computer is on a flat board whose legs are not seen, we caninfer from our knowledge that the flat board has legs and isa part of a desk, that there is a floor under it, and that thefloor supports the desk. For a system that understands a 3D
scene from a single 2D image, it is necessary to provide a
3D spatial reasoning ability based on qualitative physicallaws.

2. Recognition of an Individual Object
Since objects represented by such nouns as “desk”
and “chair” have various shapes, it is impossible to prepare
exact shape models in advance. Therefore, in this research,
to recognize each single object, we prepare prototype models that represent essential functional structures common to
the same kind of objects [5, 10, 11]. For example, thefunctional structure of a “chair” is a combination of a sitting
surface and one or four legs, and that of a “desk” is acombination of a desk face and four legs. By fitting models
to image features extracted from an image and estimatedfrom “supporting relations,” we infer the existence of objects and the 3D structure of object candidates. For some
objects we prepare several prototype models, and we selectthe model with the highest confidence value from among
them.
Although such a simple model fitting method enables
us to recognize objects with various shapes, it sometimes
confuses different kinds of objects and creates conflicts. In
this case, we resolve the conflict by evaluation of relations15

as shown in Fig. 2(f). Figure 2(d) shows the weight valueof each model element used evaluating the confidence valueof an object candidate.

to other objects as well as accuracy of model fitting, andidentify the target objects.
2.1. Representation of a model

2.2. Method of fitting a model to the image
A prototype model is represented by model elements
and a model graph. Model elements are polygons andstraight line segments according to the appearance of theobject [Fig. 2(a)], which carry information about their realshape and their generally expected pose in the real world.
A model graph represents connecting relations between themodel elements [Fig. 2(b)]. In Fig. 2(b), the model elementsof the desk are defined as a parallelogram (PG) with four
vertices (fl, fr, rr, rl) and a vertical line (VL) with twovertices (t, b). The lengths of two edges of the parallelogram
are a and b, respectively, and the length of the vertical line
is c. These two model elements are defined as a horizontal
rectangle plane and a vertical bar in the real world. The
model graph in Fig. 2(b) indicates that an upper vertex(t) of
each vertical line is connected to each vertex of a parallelogram. In such a way, we define a “desk” model as consistingof a horizontal plane and vertical legs [Fig. 2(e)], and a“chair” as consisting of a horizontal sitting plane and vertical legs, so that the common structures of many “desks”
and “chairs” are well represented by these models.
Each model has information on a range of relative
sizes of model elements and properties regarding whichelements are supportable and which are to-be-supported[Fig. 2(c)]. Here, a “supportable” element and a “to-besupported” element mean an element that can support
other objects and an element that must be supported byanother object, respectively. These properties are used in
the stage of checking supporting relations described later.
For example, the model of “desk” has one parallelogram(PG) as its supportable element and four vertical line (VL)
segments whose bottoms are its to-be-supported elements

For detecting an object candidate, we first extract line
segments and regions from the image. These line segments
and regions are called basis elements, since they are evidence for fitting a model. We extract them by conventional
image processing algorithms, for example, the Canny edge
detector [2], the Hough transformation, the region growing
segmentation method, and so on. Next, we group line
segments and regions into proximity pairs of lines, parallelpairs of lines, U-shapes, which consist of a parallel pair oflines and their connecting line, and parallelograms by theperceptual grouping method [7].
We infer the qualitative 3D structure as well as theexistence of an object candidate by fitting a model to groupsof line segments and regions extracted from the image (Fig.
3). We judge whether a model is applicable or not by
examining whether the range of sizes of all elements assigned to a model beforehand is satisfied and whether theconfidence value of a candidate, which represents goodness of fit, exceeds a threshold value. If fitting is successful,an object candidate is generated.
In addition, we estimate which parts are vertical,
horizontal, supportable, and to-be-supported by using theproperties of model elements related to the categories ofvertical, horizontal, supportable, and to-be-supported. Although this model fitting is qualitative without quantitative
accuracy, we can obtain the size and direction of an object
candidate accurately enough to carry out qualitative reasoning about supporting relations. We call the regions and line
segments of an object candidate estimated by fitting amodel “candidate elements.” Candidate elements are all
elements expected to be viewed without occlusions.
The confidence value of a candidate used in resolving conflicts among models is scored from 0 to 1. It is

Fig. 2. An example of model representation of “desk.”

Fig. 3. Flow of estimating an object candidate of “desk.”

16

between already generated candidates and the new one. Bychecking the supporting relation between objects, the system eliminates object candidates that cannot exist and estimates actual objects from their parts seen in the image.
The “supporting relation” holds when an object canbe considered to be located on another object and to besupported by it. Checking of the “supporting relation” iscarried out by examining whether the regions of to-be-supported elements of the object are almost all included in theregion of supportable elements of another object. If so, theformer object is regarded as supported by the latter one. We
present an example including the relations that “desk is
supported by floor” and “book is supported by desk” in Fig. 5.
In Fig. 5, we can also consider the book to be supported directly by the floor. However, we can infer floor ⇒desk ⇒ book, from floor ⇒ desk, floor ⇒ book, and desk
⇒ book, where the relation that object A supports object B
is defined as A ⇒ B.
If a candidate has no supporting relation, to-be-supported elements of the candidate are regarded as “virtualbasis elements,” and the system searches for a new candidate with supportable elements including the virtual basis
elements (Fig. 6). This search is carried out for kinds ofobjects that have the possibility of supporting the candidate

Fig. 4. Estimating an object candidate of “floor.”

defined as the weighted sum of the ratios of the corresponding basis elements to the candidate elements, as follows:(1)

where n is the number of elements, bi is the number of pixelsof the i-th basis element, and ei is the number of pixels of
the i-th candidate element. Ci is a weighting factor, which
represents the degree of importance of each element and isprovided as a priori information with each model. For
example, “desk” has six elements, a contour and a regionof a desk face and each leg, and the Wi for them are set as
0.4, 0.3, and 0.1, respectively.
We fit a plane model to background objects, such as
floors, walls, roads, and sky, that have no constant shape,
as shown in Fig. 4. For these background objects, the model
elements are only plane regions. We compute confidence
value of a candidate for them as follows:(2)
where b is the number of pixels of the region of a basis
element, and e is the number of pixels of the region of acandidate element.

3. Checking Supporting Relation
The “supporting relation” is the relation that an
object is supported by other objects. All objects except
background objects, such as floors, walls, roads, and sky,must be supported by other objects in the real world due togravity. Humans know such qualitative physical laws empirically, and they may have an effect on human perception.
Then, according to this fundamental rule of real-world
scenes, the system makes use of relations regarding which
object supports which object.
Each time the system generates a new object candidate, it examines whether the “supporting relation” holds

Fig. 5. Checking “supporting relation.”17

Fig. 6. Estimating a “desk” candidate that supports the “workstation” candidate by combining virtual basis elements andbasis elements.

with no supporting relation according to the “relational
knowledge” that we shall describe later. Thus, the system
can detect a new candidate that could not be detected before.
For example, if the system generates a “workstation(WS)” candidate with no supporting relation, it regards the
to-be-supported elements of “WS” as the virtual basis elements of a desk face element (Fig. 6). The system searches
the surrounding area of the virtual basis element for a new
candidate including it as a supportable element, and, as aresult, detects “desk” by fitting a model to the basis elements extracted from an image and the virtual basis elements generated from the to-be-supported elements of“WS.”
In this way, by introducing the “supporting relation,”
the system recognizes an object occluded by another object.
If candidates other than background objects have nosupporting relation, finally, the candidates are canceled.

Relational knowledge is represented by a combination of “name of relation,” “source object’s name,” and“destination object’s name.” For example, “on(book,desk)” and “next-to(chair, desk)” mean “abook is usually on a desk” and “a chair is usually next to adesk,” respectively. At present, we have two types of relations, “on” and “next-to.”The system judges whether each relation holds by the
information on supporting relations and the relative location of objects in the image. This judgment is made bychecking the relational knowledge one by one. “on(A,B)” holds when object A is supported by object B. “nextto(A, B)” holds when both objects A and B are supported by the same one object, and are located on the same
support-capable plane. The system uses all relational
knowledge to ascertain whether relations are applicable.
The confidence value of relations Vre is determined
as a weighted sum of holding relations:

4. Evaluation of Relational Knowledge andObject Candidates(3)

where r is the total number of relations, ni represents
whether relation i holds, taking a value of 0 or 1, and k is aconstant. We set k to 0.4 for the experiments. ci is a weighting factor that represents the significance of each relation.
At present, it is set 1.0 for the relation “on” and 0.5 for the
relation “next-to.”Equation (3) includes an exponential term, so that theincrease of Vre is much larger when the number of holding

4.1. Relational knowledge
The system processes “relational knowledge” beforehand. In our system, it consists of descriptions of therelative spatial relations generally expected between two
objects. It is used for computing the confidence value of
relations and inferring a new object candidate that has
supporting relation to already detected candidates.

18

relations increases from one to two, compared to the casein which it increases from five to six. The confidence valueof relations Vre takes a value from 0 to 1. It is estimated bychecking relational knowledge items one by one. It can be
regarded as the degree of naturalness of existence of acandidate in the scene.
4.2. Evaluation of object candidates
If two or more agents generate different candidates
in the same region of an image, a conflict occurs. Conflicting candidates are compared by confidence value V. V iscalculated as a weighted sum of the confidence value of acandidate Vim and the confidence value of relations Vre as
follows:

Fig. 7. Basic structure of the system.

(4)

dition, a nonfixed processing flow allows flexible fusion of
top-down and bottom-up processing.
One agent consists of a recognition module which
recognizes a single kind of object, and a communication
module which cooperates with other agents.
A recognition module (RM) has models of objects,
and recognizes only one kind of target object in an input
image. Each time an RM finds a new object candidate, it
computes its confidence value of a candidate, then sends
information about the basis elements, candidate elements,
supportable elements, to-be-supported elements, and theconfidence value of a candidate to the communication
module in the same agent. In our architecture, we do notassume a special implementation for an RM. A suitable
recognition module is implemented by using suitable recognition methods, algorithms, knowledge, and knowledge
representation.
A communication module (CM) carries out negotiation among the agents so as to maintain consistency over
the whole system. A CM receives information about object
candidates from the RM, exchanges it with other CMs, andresolves conflicts by comparing confidence values. Every
CM has relational knowledge. Using this knowledge, it
computes the confidence value of relations, and it checks
supporting relations with respect to candidates generated
by other agents.

(5)
where S is the total number of pixels of candidate elements
and w is a constant that controls the balance between Vim
and Vre. The weights are tuned by taking the size of acandidate into account. If the number of pixels S of thecandidate is more than 2w, the ratio of the weight of Vim and
Vre is 2 : 1. Otherwise, it is S : w. This emphasizes Vre of thecandidates having a small number of pixels when evaluating V. We set w to 2500 for the experiments.
As a result of comparison of V, the candidate with thehighest value remains, and all other candidates are eliminated.
There are no established confidence values of object
candidates in an image understanding system, and various
evaluation methods have been used in many systems. We
modified the method used in Ref. 5 and applied it for oursystem.

5. Overview of the System
5.1. System architecture
We designed the system based on “MORE” (Multiagent architecture for Object REcognition), which we
proposed in Refs. 14 and 15. “MORE” is a multiagentbased architecture. The system is constructed as an assembly of agents that recognize a single kind of object from animage separately, and it has no central management mechanism (Fig. 7). This architecture enables the system to recognize various different kinds of objects by adding agents.
Since we can apply different knowledge representation andrecognition methods for each agent, it is suitable for implementing a large-scale image understanding system. In ad-

5.2. Processing flow
The processing flow among all of the modules ismessage-driven. We describe the detailed flow of messages
for the example of Fig. 8.
(1) An input image is sent to the recognition modulesof all of the agents. Each CM sends an “initial recognition
request” to each respective RM. Then, each RM starts therecognition.

19

station (WS)”] on a PC cluster system consisting of six PCs(Intel Celeron 450MHz with 128 MB memory) using thePVM library [6]. In this experimental system, since we have
not yet taken account of effective load balancing, each agent
is implemented on each PC, and all recognition modules
extract basis elements from an input image independently.
It is possible to share processing of basis element extraction. In this section, we give a description of the processingof two sample images of a relatively simple indoor scene
and a more complex scene, and describe the experimental
results for 20 indoor images.

Fig. 8. Flow of messages. (1) Initial recognition
request. (2) Information on a new object candidate.
(3) Broadcasting information of a new object
candidate. (4) To-be-supported request message.
(5) Objection message. (6) Re-recognition
request.

6.1. Example of recognition
After the system is given an input image, which is a
256-level gray-scale image, the image is sent to the RMs in
all agents, and the RMs start extracting straight line segments and regions as image features. When sample image
No. 1 (Fig. 9, 480 × 360) is given, first, straight line
segments (Fig. 10) and regions (Fig. 11) are obtained byextraction processing of image features such as edge detection, line detection, and region segmentation. Next, thesystem extracts proximity pairs of lines, parallel pairs oflines, U-shapes, which consist of a parallel pair of lines andtheir connecting line, and parallelograms by groupingstraight line segments (Fig. 12). The RM of the “WS” agent
extracts two parallelograms as front parts of display monitors of workstations as the most prominent features and one
parallelogram and one U-shape for parts of keyboards. The
RM of the “WS” agent fits a model of the front part of thedisplay and a model of a keyboard to the parallelogramswith two vertical edges and the parallelograms in the frontof a display, respectively, and generates two new object
candidates (Fig. 13). The right-side parts of WS candidates
are detected from vertical straight line segments behind thefront parts of the display monitors. In addition, the RM
infers parallelogram elements from the bottom straightedges of the front sides and right sides of displays, andconsiders the region consisting of them and the region of
the keyboards as to-be-supported elements of the “WS”
candidates (Fig. 14). Thus, the “WS” agent generates two(2) Each time an RM finds an object candidate, it
sends information on the candidate and its candidate confidence value to the CM.
(3) The CM checks whether the candidate is supported by any other candidates, and broadcasts the information on the candidate to all other agents.
(4) If a candidate other than a background object is
not supported by any object candidate, the CMs generate
virtual basis elements and broadcast their information as a
“to-be-supported request.”(5) Other agents examine whether the broadcast is
consistent with their own object candidates. If not, theagents sends back an “objection message.” Then conflict
resolution is performed between the CMs concerned.
(6) If a CM receives a “to-be-supported request” andhas relational knowledge that the candidate is usually on its
own object, the CM sends a “conditional recognition
request” to its RM. The RM starts to find object candidates
with supportable elements overlapping the virtual basis
elements of the candidate.
In addition, our system has a “revival mechanism.”
The system revives an object candidate that was eliminatedonce, when its confidence value of relations is changed andthe result of conflict resolution becomes invalid. By thismechanism the system always keeps object candidates thatare consistent with others, and maintains consistency
among agents. If all modules of all of the agents are in thestate of waiting for a message and there is no message on
the communication lines, the whole recognition activity ofthe system terminates.

6. Experiments
We implemented an experimental system with six
agents [“desk,” “chair,” “wall,” “floor,” “book,” and “work-

Fig. 9. Sample image No. 1.

20new candidates, but neither of them is supported by any
object candidates. Then, the CM of the “WS” agent broadcasts not only the information on the two new candidates,
but also “to-be-supported request” to other agents.
At first, the “desk” agent detects no desk candidates,
since the obtained image features are only straight edges
and regions, which constitute insufficient information (Fig.
15). However, after receiving a “to-be-supported request”
with information on virtual basis elements from the “WS”
agent, the “desk” agent tries to detect a new candidate thathas the virtual basis elements as its basis elements, since it
has relational knowledge “on(desk, WS).” The “desk”
agent detects enough basis elements to generate a new desk
candidate by joining the virtual basis elements to somestraight edges and regions (Fig. 16). By fitting a model tothese basis elements, a desk candidate can be detected (Fig.
17). In addition, a floor is detected correctly by a “to-besupported request” from the “desk” agent. Finally, two“WSs,” two “desks,” and a “floor” are detected as shownin Fig. 18.
We next describe an experiment with sample image
No. 2 (Fig. 19, 640 × 480) which is a more complex scene
than sample image No. 1. In this experiment, first, four WSs
are detected (Fig. 20). Their to-be-supported elements areshown in Fig. 21. At the same time, “books” are detected,
and 10 “book” candidates are generated (Fig. 22). Then,
three WSs, excluding the second WS from the right generate a conflict with books. By conflict resolution, three WSs
remain and books are eliminated. For example, in theconflict between the keyboard of the rightmost WS and thebook, the candidate confidence values Vim are 0.78 and
0.59, the confidence values of relations Vre are 0.33 and
0.33, and total confidence values V are 0.62 and 0.43,
respectively. As a result, the book candidates are eliminated.
The real keyboard of the second WS candidate from theright is recognized as a book candidate, since the positionof its keyboard part is detected incorrectly.
Since the WS candidates and the remaining bookcandidates have no supported object candidates, “to-besupported requests” are issued. Then, the “desk” agent joins
virtual basis elements that originate from the to-be-sup-Fig. 10. Extracted straight edges.

Fig. 11. Extracted regions.

Fig. 12. Parallelograms and U-shapes.

Fig. 13. Two “WS” candidates.

Fig. 14. To-be-supported elements of two “WS”
candidates.

Fig. 15. Basis elements of a “desk.”

21

Fig. 16. Virtual elements and basis elements of a “desk”
candidate.

Fig. 21. To-be-supported elements of four “WS”
candidates.

ported elements of WS candidates (Fig. 21) and bookcandidates to the basis elements of desk candidates (Fig.
23), so that the agent can recognize the desk candidate,although much of the desk face is occluded by other objects(Figs. 24, 25). Three of five book candidates causing noconflict fail to have identified object candidates supporting
them, and are eliminated due to no supporting relation.
Actually, these book candidates are incorrectly detected,
and are eliminated correctly by checking the supporting
relation. Finally, “WSs,” “desks,” “books,” a “chair,” and a“floor” are recognized correctly, although two “books” on
the right-back desk are recognized incorrectly as shown in
Fig. 26. In this experiment, we implemented “WS” agent torecognize its candidate as a pair consisting of a display anda keyboard, so that two main bodies on the right-back desk
are not recognized.

Fig. 17. A “desk” candidate.

Fig. 18. Recognition result.

6.2. Experimental results
We performed recognition experiments on 20 indoor
images whose size was 480 × 360. We show 12 out of the
20 images used in this experiment in Fig. 27. In this figure,the images in the upper row are quite simple, those in thelower row are complex, and those in the middle row haveintermediate complexity. The numbers of images in eachcategory are 7, 7, and 6, respectively. We evaluate the resultsby dividing them into three grades, “almost entirely cor-

Fig. 19. Sample image No. 2.

Fig. 22. “Book” candidates.

Fig. 20. Four “WS” candidates.

22

Fig. 23. Basis elements of “desk” candidates.

Fig. 27. 12 out of 20 images for experiments. Images in
the upper row are quite simple, those in the lower row arecomplex, and those in the middle row haveintermediate complexity.

rect,” “half correct,” and “almost entirely incorrect.” The
numbers of images in these three grades are 9, 6 and 5,
respectively, as shown in Table 1.
Fig. 24. Virtual basis elements and basis elements of“desk” candidates.

6.3. Discussion
In the experiment with 20 indoor images, an example
of “almost entirely correct” images is sample image No. 1
shown in Fig. 9. A “desk” is recognized by checking the
supporting relations and recognition with virtual basis elements, although most of the desk face is covered by two“WSs.”
Figure 28 is an example of “half correct” images. In
this image, there are a “notebook PC,” piled “books,” anopened “notebook” on the desk, a “bookshelf,” and “book”
in the bookshelf. A “notebook PC” and an opened “notebook” are recognized as a “WS” and a “book,” respectively,
and a “desk” is recognized correctly by checking supporting relation as shown in Fig. 29. However, since the RM of
the “book” agent is implemented to recognize a parallelogram as a book, a parallelogram or a U-shape is not extracted, and the piled “books” and the “book” in thebookshelf are not recognized. If we use the relational
knowledge “on(book, book),” if a book on the top is

Fig. 25. Three “desk” candidates.

Table 1. Results for 20 images
almost entirely
correct
9Fig. 26. Recognition result.

23

half correct

almost entirely
incorrect

6

5

not recognized, books under it are also not recognized. To
deal with such a case, it is desirable to prepare a model ofa block of books in contact with each other in advance.
An example of “almost entirely incorrect” images isshown in Fig. 30, and its result is shown in Fig. 31. This
image is so complex that only parts of “floor” are recognized. Although the display of a “WS” appears clearly in
the image, the color of the keyboard on the desk is so similar
to the color of the desk face that the system cannot recognize the “WS.” This depends on the resolution of the input
images, so that it is desirable to introduce multiresolution
analysis, which can recognize the rough structure of thescene for a lower-resolution image first, and will later
recognize details for only the needed parts of a higher-resolution image. There exist unknown objects on the center
desk, for which models are not prepared. A wrapper without
constant shape is on the front side of the center desk, and it
is difficult to represent an object without constant shapesuch as a wrapper for rigid model fitting. It is necessary to
introduce active contour and textural analysis methods.

Fig. 28. An example image whose results are halfcorrect.

7. Related Works
Fig. 29. Recognition result.
The objective of our work is scene recognition whenexact models of target objects are not available in advance.
The work conducted by Tenenbaum and Barrow [13], inwhich segmented regions were labeled by the relaxation
method, had similar objectives to our work. But their work
used too simple methods, and it was not usable for complex
images. After that, knowledge-based recognition systems,
for example, that of Ohta [9], the Schema System [4], and
SIGMA [8], appeared. They used both models for single
objects and relational knowledge among objects, andachieved an integration of bottom-up and top-down processing. Our work is also similar to theirs, but their target
was not indoor images but outdoor images or aerial images
that seldom include occlusions and need not be treated inthree-dimensional space, because their method of utilizing
spatial information is two-dimensional.
The features of our system are that we estimate
supportable and to-be-supported elements by fitting 3D
structure models to partial features extracted from an image, and verify the generated object candidates by checking
supporting relations. A similar system, which generates
individual object candidates and verifies them based onrelations among candidates, is CONDOR [12]. Its methodof recognition is called context-based recognition. However, CONDOR employs two-dimensional recognition forimages of an outdoor scene. It does not employ qualitative
three-dimensional recognition like our system.
Cooper and colleagues [3] and Brand [1] realized
recognition with consideration of the physical relation thatan object supported another object against gravity. In theirFig. 30. An example image whose results are almost
entirely incorrect.

Fig. 31. Recognition result.

24

work, the systems analyzed scenes based on knowledge of
qualitative physical laws. However, the objective of theirwork was not recognition but understanding of physicalaction from images. Therefore, the target objects were
simple objects like blocks.
In our system, in recognizing an individual object,such as a “desk” or “chair,” represented by a general noun,
we pay attention to the essential structure that provides thefunctions of an object. This idea is imported from functionbased recognition [10, 11]. It claims that the essence of an
artifact is to provide functions to humans and that we should
recognize an artifact by examining whether it has a shapeproviding a relevant function.

REFERENCES
1. Brand M. Physics-based visual understanding. Comput Vision Image Understanding 1997;65:192–205.
2. Canny J. A computational approach to edge detection. IEEE Trans Pattern Anal Machine Intell
1986;5:140–150.
3. Cooper PR, Birnbaum LA, Brand ME. Causal scene
understanding. Comput Vision Image Understanding
1995;62:215–231.
4. Draper B, Collins R, Brolio J, Hanson A, Riseman E.
The schema system. Int J Comput Vision
1989;3:209–250.
5. Kim D, Nevatia R. Recognition and localization ofgeneric objects for indoor navigation using functionality. Image Vision Comput 1998;16:729–743.
6. Geist A, Beguelin A, Dongarra J, et al. PVM: Parallel
virtual machine. MIT Press; 1994.
7. Lowe DG. Perceptual organization and visual recognition. Kluwer Academic; 1985.
8. Matsuyama T, Hwang VS. SIGMA: A knowledgebased aerial image understanding system. Plenum
Press; 1990.
9. Ohta Y. Knowledge-based interpretation of outdoor
natural color scenes. Pitman Advanced Publishing
Program; 1985.
10. Stark L, Bowyer K. Achieving generalized object
recognition through reasoning about association offunction to structure. IEEE Trans Pattern Anal Machine Intell 1991;13:1097–1104.
11. Stark L, Bowyer K. Function-based generic recognition for multiple object categories. Comput Vision
Image Understanding 1994;50:1–21.
12. Strat TM, Fischler MA. Context-based vision: Recognizing objects using information from both 2-D
and 3-D imagery. IEEE Trans Pattern Anal MachineIntell 1991;13:1050–1065.
13. Tenenbaum JM, Barrow HG. Experiments in interpretation guided segmentation. Artif Intell
1977;8:241–274.
14. Yanai K, Deguchi K. An architecture of object recognition system for various images based on multiagent. Proc 14th Int Conf Pattern Recognition
1998;1:278–281.
15. Yanai K, Deguchi K. A multi-agent architecture ofobject recognition system for various images. TransInf Process Soc Japan 1998;39:170–177. (in Japanese)

8. Conclusion
In this paper, we have proposed a system that estimates the 3D structure of a target object by fitting a qualitative model qualitatively, and verifies object candidates bychecking the “supporting relation” using “supportable regions” and “to-be-supported regions.” It totally realizes
flexible recognition for real-world indoor images including
complex occlusions. We have implemented the system as amultiagent-based image understanding system on a PC
cluster.
In the present system, we often obtain imperfectresults due to insufficient ability of the recognition modules. Thus, in future work, we plan to study how to construct
a recognition module with greater ability and more effective
cooperation mechanisms and learning mechanisms to makeup for the insufficient ability of individual recognition
modules. We also plan to make use of high-resolution
images recently obtainable by digital cameras easily inorder to recognize objects that appear with small size in animage.
Experiments using the current implementation revealed no problems of convergence of recognition processing and stability of recognition results. In systems of larger
scale by increasing the number of agents in the future,
however, we will need to analyze behavior of the system inthis respect.

Acknowledgment. Part of this work was supported
by a grant from the Inamori Foundation.

25

AUTHORS (from left to right)

Keiji Yanai received his B.E. and M.E. degrees from the University of Tokyo in 1995 and 1997. He then became a research
associate in the Department of Computer Science of the University of Electro-Communications. His recent research interests
include an image understanding system and a multimedia database.
Koichiro Deguchi received his B.E., M.E., and D.Eng. degrees from the University of Tokyo in 1974, 1976, and 1980.
From 1984 to 1987, he was an associate professor in the Department of Information Engineering, Yamagata University, andfrom 1988 to 1998, an associate professor in the Department of Mathematical Engineering and Information Physics, Universityof Tokyo. Since then, he has been a professor in the Graduate School of Information Sciences, Tohoku University. His recent
research interests include computer vision, signal processing, and multiprocessor architecture for them.

26