# «EXTRACTION OF CONTEXTUAL KNOWLEDGE AND AMBIGUITY HANDLING FOR ONTOLOGY IN VIRTUAL ENVIRONMENT A Dissertation by HYUN SOO LEE Submitted to the Office ...»

Figure 59 (a) shows that context library has a format of Metaearth architecture, while Figure 59 (b) shows that context library’s Metaearth architecture has the four complete layers. Ontology cores have contexts such as “window”, “wall” or “unknown” (Figure 59 (a)) which link to each library core. These context libraries are constructed from existing Metaearth architecture or user’s operation. Unlike context library, however, generated Metaearth architecture (Section 4 or 5) lacks the ontology layer. In this dissertation, context library is the pattern graph ( G2 ) and Metaearth architecture is the target graph ( G1 ). Equations (25) and (26) are the context library and the target Metaearth architecture with a representation of Virtual ontology as shown in Section 3.2.

and MR is the mapping relationship between C 1 and VC such that MR : C1 VC, As shown in equation (26), VO does not have any context ( C 2 ) and mapping edge ( MR ) to the library core. Even though CL and VO are considered as a subgraph and a graph, this problem differs from a general graph-subgraph isomorphic matching

**problem because:**

A general graph-subgraph isomorphic matching problem handles a general graph such as G {V, E} without edge. However, Metaearth architecture has a special structure and each edge ( i I ) in the virtual space layer may have a direction (the interaction between two virtual components). This directed edge may be important for representing the interaction and movement of the virtual components. As an NPcomplete problem (Theorem 1), it is difficult to find an exact solution.

** Theorem 1. Graph-subgraph isomorphic matching with CL : {VC, I, C1, MR, C 2, CR} and VO : {VC, I, C1, MR} is an NP-Complete problem.**

Proof. Graph-subgraph isomorphic matching is an NP complete problem by Garey’s theorem [71] which is proven using a general subgraph( G1 {V1, E1} ) and a general graph ( G2 {V2, E2 } ). For the general graph, CL : {VC, I, C1, MR, C 2, CR} graph can be converted to

G2 {V2, E2 }. Thus, it is an NP-hard problem and it can be reducible to decision problem class C. Ergo, it is an NP-Complete problem.

Ullmann’s algorithm [72] and Messmer and Bunke’s algorithm [76] are modified in this dissertation, since it can handle a similar problem with a near-optimal solution.

Their algorithms have advantages in that they can check the subgraph isomorphic matching problem and outperform in the maximal click problem. However, their algorithm is limited because it cannot find all graph-subgraph matching pairs and is only workable on general graph structure. In order to overcome the limitation of Ullmann’s

Ullmann’s algorithm and Messmer and Bunke’s algorithm, graph-subgraph isomorphism is detected using permutation matrices. From G1 and G2, two adjacent matrices are obtained such as M 1 and M 2. Then, permutation matrix ( P ) is calculated from M 1 and M 2 such as each element pi, j of P

VO : {VC, I, C1, MR} and CL : {VC, I, C1, MR, C 2, CR}, two adjacency Matrices ( M 1;mm, M 2;nn ) are obtained considering virtual space layer ( VC, I ). From these matrices, the initial permutation matrix Pmn is calculated. If P does not exist, we conclude that there is no isomorphic relationship. Otherwise, all matching edges are detected using Ullmann’s backtracking method. After detecting all pairs, the mapping relationship between MR1 and MR2 is examined. If each edge in MR1 is mapped into MR2, we conclude that two Metaearth architectures have the graph-subgraph isomorphic problem. Then, CL ’s C 2 is mapped into VO ’s C 1 using the mapping relation ( CR1 ).

Figure 60 shows the suggested procedure.

Figure 60. Context mapping in Meteaearth architecture using graph-subgraph

Our suggested algorithm can detect all subgraphs ( context library). However, the size of the generated Metaearth architecture is large and performance decreases. Table 12 shows the comparison of algorithm complexity.

Table 12. Comparison of algorithm complexity between Ullmann’s algorithm and the

As shown in Table 11, the complexity of the suggested algorithm is similar to Ullmann’s method. Considering that Metaearth architecture has a more complicated structure than a general graph, our suggested algorithm is a workable solution. The following section describes its effectiveness using a simulation study.

## 6.3 SIMULATION AND ANALYSIS OF CONTEXT MAPPING METHOD

As a simulation study, a Metaearth architecture with 100 virtual components ( | VC | 100 ) and 2510 interactions ( | I | 2510 ) is generated.Figures 61 (a) and (b) show the generated Metaearth architecture and a context library with 6 virtual components, 8 interactions and 6 contexts. Each context in the context library belongs to MH1 (Material Handler #1), MP1 (Material Processor #1), MP2 (Material Processor #2) and MT1 (Material Translator #1). Using Ullmann’s algorithm [72] and Messmer and Bunke’s algorithm [76], 373 subgraphs are detected.

Figure 62 shows parts of the detected subgraphs. However, the detected subgraphs cannot be considered as the structures with isomorphic relationship in Metaearth architecture, because, each subgraph structure may have different library cores.

** Figure 62. Parts of detected subgraph using existing algorithms.**

The suggested algorithm extracts the exact pattern as shown in Figure 63 (a).

Then, the contexts are mapped into the detected structure (Figure 63(b)).

(a) Detected structure with the sample structure of context library

The suggested algorithm is effective in detecting the same structure with context library and mapping contexts. However, this algorithm only works with well-defined context libraries. The construction of context library and variation are discussed in the following section.

In this dissertation, the application domain is fixed as a generation of virtual environment. “Knowledge of virtual environment” is represented as contexts. A 2D image is considered as “unknown environment”. The structure of knowledge is represented with Metaearth architecture. Virtual ontology is constructed as a context mapping procedure into Metaearth architecture.

Section 3 introduces Metaearth architecture as a good format of virtual ontology.

Since Metaearth architecture can replace other formats in terms of scene graph and support construction of large scale virtual environments (LSVE), more theoretical investigation and effort to optimize this structure are required. In addition, even though construction methods are proposed, another construction method considering various application domains is considered.

As characteristics of the suggested virtual ontology generation method, these do not depend heavily on prior knowledge and human operation. Considering the input image’s visual cue such as fuzzy colors, edge and shape, input images are oversegmented and merged using conditions. In this dissertation, fuzzy color and edge information are used for more important criteria than shape information such as width ratio, height ratio, and bounding box. For more clarified segmentation with good quality, shape information can be considered with higher weight. In this concept, Voronoi diagram (VD) approach can be applied. If each segment is divided into more detail using the characteristics of Voronoi region (each Voronoi region has a convex shape), bounding box approach and width/height ratio approaches can be applied more easily to generate accurate virtual ontology.

Even though the suggested approaches are independent from the pre-trained mechanisms, the determination of several parameters for object merging and semantic merging are significant issues. The quality of the generated virtual ontology depends on these parameters. If training methods such as Neural Nets and statistical learning methods are applied to determine these parameters, more accurate virtual ontology can be generated.

Section 4’s algorithm generates virtual ontology from a 2D image, but the generated model does not have Z depth information. If some existing reasoning methods as described in Section 2 are applied, virtual ontology with Z depth can be generated.

The approach in Section 5 constructs virtual ontology with Z-depth. It has many advantages for handling ambiguities, and offers rapid 3D reconstruction and virtual ontology generation. However, it can be more effective via the unifying approach with RANSAC and fuzzy color segmentation which rectify the input image pairs. If two consecutive processes are merged and unified, the algorithm complexity will be much lower and improve the speed.

Section 6 describes how the contexts are mapped to Metaearth architecture. An approach using graph-subgraph isomorphism is proposed and tested. The prior condition of this approach is in the prior construction of context libraries which are another type of Metaearth architecture. In a real situation, the construction of context library can be considered a problem. Even though the suggested methods have a target for generating virtual ontology automatically, the generation and preparation of context library needs human’s intervention such as mapping contexts to the library cores. The accurate context mapping can guarantee more accurate generation of virtual ontology. As a further study, the context library can be generated from existing Metaearth architecture. Using graph cut and detection methods, a Metaearth architecture can be divided into many small architectures and each divulged structure can be used as a context library with contexts.

Finally, the generated virtual environment with virtual ontology is used in virtual interaction analysis as a next stage. Since virtual interaction analysis requires mutual interactions among virtual components, seamless processing from input to virtual interaction analysis can be achieved using the suggested method.

This dissertation proposes how virtual ontology can be constructed from an unknown environment. Virtual ontology is defined as a structure of virtual environment with semantics. In this dissertation, the contextual knowledge is used as a representation of semantics. While many existing 3D reconstruction approaches generate atomic virtual model without virtual ontology, this research suggests the generation of relational models and models with virtual ontology.

Metaearth architecture is introduced as the data structure of virtual ontology. The architecture consists of a virtual space layer, mapping layer, library layer and ontology layers. In the virtual space layer, the interaction and relationship between virtual components can be described. Each virtual component in the virtual space layer is connected to library cores in the library layer, thus contributing to the design of LSVEs with less redundancy. The library cores are then linked to the ontology core, a contextual knowledge.

Section 4 generates a relational model from a 2D input image. Unlike other scene understanding techniques, the suggested method extracts virtual ontology using Metaearth architecture. As an intermediate process, fuzzy color based over-segmentation method makes it possible to generate scene segmentation without pre-defined knowledge or human intervention. In addition, the scene structure is generated through the semantic-merging process.

While Section 4’s model lacks Z-depth information, Section 5’s model generates virtual ontology with Z-depth information. To handle many ambiguities in extracting 3D information, fuzzy dynamic programming is applied. A hybrid approach with FDP and Section 4’s algorithm generates more accurate virtual ontology with Z-depth.

Finally, the generated relational model is converted into a model with structural knowledge using a context mapping process. Contextual knowledge is mapped into Metaearth architecture of the model with structural knowledge via the suggested isomorphic matching method. The relational model’s Metaearth architecture is effectively compared to the context library’s Metaearth architecture and the contexts in context library are mapped into the targeted Metaearth architecture.

The overall procedure contributes to the generation of models with structural knowledge from 2D images. The successful generation of models with structural knowledge can guarantee automatic and autonomous processing in virtual interaction analysis. This approach can generate an LSVE with virtual ontology and intelligence in less time and with less computational effort. It can also increase the use of generated virtual models and enhance seamless information processing.

1. Gardner, L., Automated Manufacturing. 1985: ASTM STP 862.

2. Jaynes, C., Seales, W. B., Calvert, K, Fei, Z. and Griffioen, J., The Metaverse - a networked collection of inexpensive self-configuring, immersive environments.

Eurographics workshop on Virtual Environments, 2003: p. 115-123.

3. Stepenson, N., Snow crash. 1993: United States, Spectra Books.

4. Lamotte, W., P. Quax, and E. Flerackers, Large-scale networked virtual environment: architecture and applications. Campus-Wide Information Systems, 2008. 25(5): p. 329-341.

5. Keller, J. and G. Simon, Solipsis: a massively multi-participant virtual world.: p.

1-5, International conference on Parallel and Distributed Techniques and Applications, 2003.

6. Hariri, B., S. Shirmohammadi, and M.R. Pakravan, A distributed interest management scheme for massively multi-user virtual environments. Virtual Environment, Human-Computer Interfaces and Measurement Systems, 2008: p1Morse, K.L., L. Bic, and M. Dillencourt, Interest management in large-scale

**virtual environment. Presence: Teleoperators and Virtual Environments, 2000. 9:**

p. 52-88.