WWW.DISSERTATION.XLIBX.INFO
FREE ELECTRONIC LIBRARY - Dissertations, online materials
 
<< HOME
CONTACTS



Pages:     | 1 |   ...   | 5 | 6 || 8 |

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

-- [ Page 7 ] --

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;mm, M 2;nn ) are obtained considering virtual space layer ( VC, I ). From these matrices, the initial permutation matrix Pmn 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.



Pages:     | 1 |   ...   | 5 | 6 || 8 |


Similar works:

«RELATIONSHIP FRAMEWORK IN SPORT MANAGEMENT: HOW RELATIONSHIP QUALITY AFFECTS SPORT CONSUMPTION BEHAVIORS By YU KYOUM KIM A DISSERTATION PRESENTED TO THE GRADUATE SCHOOL OF THE UNIVERSITY OF FLORIDA IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY UNIVERSITY OF FLORIDA 2008 1 © 2008 Yu Kyoum Kim 2 To my wife, Hyun-Ok 3 ACKNOWLEDGMENTS This dissertation benefited tremendously from my committee. I am truly honored that I have learned from the best committee...»

«George Bernard Shaw’s Religion of Creative Evolution : A Study of Shavian Dramatic Works Thesis Submitted for the degree o f Doctor o f Philosophy at the University o f Leicester by Keum-Hee Jang Departm ent o f English & Victorian Studies Centre University o f Leicester Novem ber 2006 UMI Number: U230427 All rights reserved INFORMATION TO ALL USERS The quality of this reproduction is dependent upon the quality of the copy submitted. In the unlikely event that the author did not send a...»

«DEVITRIFICATION OF IRON BASED METALLIC GLASSES AT HIGH PRESSURES AND HIGH TEMPERATURES by ANDREW KEVIN STEMSHORN VOHRA, YOGESH K. (CHAIR) CATLEDGE, AARON S HARRISON, JOSEPH G. JANOWSKI, GREGG STOLZ, GUNTER KHARLAMPIEVA, EUGENIA A DISSERTATION Submitted to the graduate facility of The University of Alabama at Birmingham in partial fulfillment of the requirements for the degree of Doctor of Philosophy BIRMINGHAM, ALABAMA 2013 Copyright by ANDREW KEVIN STEMSHORN 2013 DEVITRIFICATION OF IRON BASED...»

«Ivan Illich Kreftingstr. 16 D 28203 Bremen Philosophy. Artifacts. Friendship Printed: 05.10.01 Filename and date: Philarpu.doc STATUS: To be pusblished in: Ivan Illich, Mirror II (working title). Copyright Ivan Illich.For further information please contact: Silja Samerski Albrechtstr.19 D 28203 Bremen Tel: +49-(0)421-7947546 e-mail: piano@uni-bremen.de Ivan Illich: Philosophy. Artifacts. Friendship 1 Ivan Illich PHILOSOPHY. ARTIFACTS. FRIENDSHIP I speak as a xenocryst. Deus in adjutorium...»

«ABSTRACT Title of Dissertation: TRANSCRIPT PROFILING AS A METHOD TO STUDY FRUIT MATURATION, TREERIPENING, AND THE ROLE OF “TREE FACTOR” IN ‘GALA’ AND ‘FUJI’ APPLES Shu-fei Lin, Doctor of Philosophy, 2005 Dissertation directed by: Professor Christopher S. Walsh Department of Natural Resource Sciences and Landscape Architecture ‘Gala’ and ‘Fuji’ are two high-quality apple (Malus domestica Borkh) cultivars. Their fruits mature and tree-ripen over a long period of time, and are...»

«The effects of habitat and predation on bay scallop populations in New York A Dissertation Presented by John Michael Carroll to The Graduate School in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy in Marine and Atmospheric Science Stony Brook University August 2012 Stony Brook University The Graduate School John Michael Carroll We, the dissertation committee for the above candidate for the Doctor of Philosophy degree, hereby recommend acceptance of this...»

«MODULATING IMMUNE RESPONSE INSIDE BIOMATERIAL-BASED NERVE CONDUITS TO STIMULATE ENDOGENOUS PERIPHERAL NERVE REGENERATION A Dissertation Presented to The Academic Faculty by Nassir Mokarram-Dorri In Partial Fulfillment of the Requirements for the Degree Doctor of Philosophy in the School of Materials Science and Engineering Georgia Institute of Technology May 2015 COPYRIGHT© 2015 BY NASSIR MOKARRAM-DORRI MODULATING IMMUNE RESPONSE INSIDE BIOMATERIAL-BASED NERVE CONDUITS TO STIMULATE ENDOGENOUS...»

«DEVELOPMENT OF TIME-HISTORY AND RESPONSE SPECTRUM ANALYSIS PROCEDURES FOR DETERMINING BRIDGE RESPONSE TO BARGE IMPACT LOADING By DAVID RONALD COWAN A DISSERTATION PRESENTED TO THE GRADUATE SCHOOL OF THE UNIVERSITY OF FLORIDA IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY UNIVERSITY OF FLORIDA © 2007 David Ronald Cowan To Zoey Elizabeth. ACKNOWLEDGMENTS Completion of this dissertation and the accompanying research would not have been feasible without the...»

«DO NORMATIVE JUDGEMENTS AIM TO REPRESENT THE WORLD? Bart Streumer b.streumer@rug.nl Ratio 26 (2013): 450-470 Also in Bart Streumer (ed.), Irrealism in Ethics Published version available here: http://dx.doi.org/10.1111/rati.12035 Abstract: Many philosophers think that normative judgements do not aim to represent the world. In this paper, I argue that this view is incompatible with the thought that when two people make conflicting normative judgements, at most one of these judgements is correct....»

«A META-ANALYSIS OF THE EFFECTS OF INTERVENTIONS TO INCREASE READING FLUENCY AMONG ELEMENTARY SCHOOL STUDENTS By Jiaxiu Yang Dissertation Submitted to the Faculty of the Graduate School of Vanderbilt University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY in Education and Human Development August, 2006 Nashville, Tennessee Approved: Professor Douglas Fuchs Professor Mark Lipsey Professor Lynn Fuchs Professor Daniel Reschly Professor Donald Compton...»

«Belt Wrestling William BAXTER SCOTLAND 2008 Belt Wrestling, the Oldest Sport? A salto from the 6th World Championships in Ufa, Bashkortostan, 2007 Belt wrestling has achieved a new dynamic and is undergoing a renaissance in the 21st century. The modern drive for its valorisation comes from the Russian Federation where several indigenous variations are still practised. To accommodate the many variations of belt wrestling throughout the world, the philosophy of the new International Belt...»

«DISCRETE CHOICE, RECREATION DEMAND, AND CONSUMER SURPLUS A Dissertation Presented to the Faculty of the Graduate School of Cornell University in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy by Eric Paul English February 2010 © 2010 Eric Paul English DISCRETE CHOICE, RECREATION DEMAND, AND CONSUMER SURPLUS Eric Paul English, Ph.D. Cornell University 2010 Three topics are examined using discrete choice models to estimate demand and consumer surplus for...»





 
<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.