Semantic Scene Interpretation

The scene interpretation uses the features, i.e., planes previously computed. The background for interpretation comprises generic architectural knowledge. A model of an indoor scene is implemented as a semantic net based on the idea of Grau et al. [7] that is also used by Cantzler et al. [5].

Figure 2: Left: Semantic net for scene interpretation. Right: Externalized knowledge representation in Prolog with facts for every arc of the net and a condition for the No Feature label.

=8.0cm     

parallel(floor,floor).

parallel(ceiling,floor).

parallel(ceiling,ceiling).

parallel(floor,ceiling).

parallel(wall,wall).

parallel(X,_) :- X == nofeature.

parallel(_,X) :- X == nofeature.

orthogonal(ceiling,door).

orthogonal(ceiling,wall).
$\ldots$

equalheight(floor,floor).

equalheight(ceiling,ceiling).

equalheight(door,_).
$\ldots$

Nodes of a semantic net represent entities of the world. The relationship between the entities are encoded using different connections. Possible labels of the nodes are $L=\{\texttt{Wall},~ \texttt{Floor},~ \texttt{Ceiling},~ \texttt{Door},\linebreak\texttt{No Feature}\}$. The relationships between the features are $R=\{\texttt{parallel},~ \texttt{orthogonal}, \linebreak\texttt{above},~ \texttt{under},~ \texttt{equalheight}\}$. The labels above and under are relative to their plane and hence not commutative. Figure 2 left shows the entities and their relations. The entity door represents an open door. The semantic net can easily be extended. Further entities have to be accompanied by a more sophisticated feature detection. This paper concentrates on plane detection so that the semantic net is a subset of all indoor environments.

Prolog is used to implement and externalize the semantic net. The net is encoded by definite Horn clauses [18]. The nodes of the net are arguments and the arcs define relations on the nodes. Figure 2 right shows a part of the semantic net as a Prolog program. All facts for the relation parallel are shown. For encoding the label nofeature, a condition is used. This prevents Prolog's unification algorithm from assigning planes with the label nofeature. In addition to the representation of the semantic net, a clause of the following form is compiled from the analysis of the planes. The planes are represented by variables P0, P1, etc.:
labeling(P0,P1,P2,P3,P4) :-
parallel(P0,P1),under(P0,P1),
orthogonal(P0,P2),under(P0,P2),
orthogonal(P0,P3),under(P0,P3),
parallel(P0,P4),above(P0,P4),
$\cdots$
Prolog's unification algorithm is used to assign a consistent labeling to the planes:
consistent_labeling(P0,P1,P2,P3,P4) :- labeling(P0,P1,P2,P3,P4).
The label nofeature is considered, iff the unification fails. In this case, an additional Horn clause is used to generate a consistent labeling with explicit unifying of one variable with nofeature. All combinations are computed to unify the variable:
consistent_labeling(P0,P1,P2,P3,P4) :-
comb([P0,P1,P2,P3,P4],[nofeature]),
labeling(P0,P1,P2,P3,P4).
The process is continued with assigning two variables the label to nofeature, and so on until a Prolog's unification succeeds:
consistent_labeling(P0,P1,P2,P3,P4) :-
comb([P0,P1,P2,P3,P4],[nofeature,nofeature]),
labeling(P0,P1,P2,P3,P4).
$\cdots$
The order of the rules above is important, as in all Prolog programs. Prolog searches for clauses from top to bottom. The following three clauses are used to compute all combinations:
comb(_,[]).
comb([X|T],[X|Comb]) :- comb(T,Comb).
comb([_|T],[X|Comb]) :- comb(T,[X|Comb]).
Finally the following query is submitted:
consistent_labeling(P0,P1,P2,P3,P4).
and the automatic generated Prolog program starts and computes the solution. Table 1 shows the computation time (Pentium IV-2400, SWI-Prolog [15]) of the Prolog program and a previous complete depth first search implementation [12].

Table 1: Computation time for matching the semantic net with the planes.

number of planes	backtracking	Prolog
5	93.51 ms	89.33 ms
7	155.14 ms	101.81 ms
13	589.11 ms	313.79 ms