«EXTRACTION OF CONTEXTUAL KNOWLEDGE AND AMBIGUITY HANDLING FOR ONTOLOGY IN VIRTUAL ENVIRONMENT A Dissertation by HYUN SOO LEE Submitted to the Office ...»
EXTRACTION OF CONTEXTUAL KNOWLEDGE
AND AMBIGUITY HANDLING FOR ONTOLOGY IN VIRTUAL ENVIRONMENT
HYUN SOO LEE
Submitted to the Office of Graduate Studies of
Texas A&M University
in partial fulfillment of the requirements for the degree of
DOCTOR OF PHILOSOPHY
Major Subject: Industrial Engineering
Extraction of Contextual Knowledge and Ambiguity Handling for Ontology in Virtual Environment Copyright 2010 Hyun Soo Lee
EXTRACTION OF CONTEXTUAL KNOWLEDGE
AND AMBIGUITY HANDLING FOR ONTOLOGY IN VIRTUAL ENVIRONMENTA Dissertation by HYUN SOO LEE Submitted to the Office of Graduate Studies of Texas A&M University in partial fulfillment of the requirements for the degree of
DOCTOR OF PHILOSOPHY
Chair of Committee, Amarnath Banerjee Committee Members, Lewis Ntaimo James A. Wall Yoonsuck Choe Head of Department, Brett A. Peters August 2010 Major Subject: Industrial Engineering iii ABSTRACT Extraction of Contextual Knowledge and Ambiguity Handling for Ontology in Virtual Environment. (August 2010) Hyun Soo Lee, B.S., Sungkyunkwan University;
M.S., Pohang University of Science and Technology Chair of Advisory Committee: Dr. Amarnath Banerjee This dissertation investigates the extraction of knowledge from a known environment. Virtual ontology – the extracted knowledge – is defined as a structure of a virtual environment with semantics. While many existing 3D reconstruction approaches can generate virtual environments without structure and related knowledge, the use of Metaearth architecture is proposed as a more descriptive data structure for virtual ontology. Its architecture consists of four layers: interactions and relationships between virtual components can be represented in the virtual space layer; and the library layers contribute to the design of large-scale virtual environments with less redundancy; and the mapping layer links the library layer to the virtual space layer; and the ontology layer functions as a context for the extracted knowledge.
The dissertation suggests two construction methodologies. The first method generates a scene structure from a 2D image. Unlike other scene understanding techniques, the suggested method generates scene ontology without prior knowledge and
over-segmentation method is suggested. The second method generates virtual ontology with 3D information using multi-view scenes. The many ambiguities in extracting 3D information are resolved by employing a new fuzzy dynamic programming method (FDP). The hybrid approach of FDP and 3D reconstruction method generates more accurate virtual ontology with 3D information.
A virtual model is equipped with virtual ontology whereby contextual knowledge can be mapped into the Metaearth architecture via the proposed isomorphic matching method. The suggested procedure guarantees the automatic and autonomous processing
I am heartily thankful to my Ph.D. advisor, Dr. Banerjee. This dissertation and related research studies could not have been completed without the great guidance and continuous encouragement of Dr. Amarnath Banerjee. I will not forget his passion and great personality forever. I would also like to acknowledge my committee members: Dr.
Lewis Ntaimo, Dr. James Wall and Dr. Yoonsuck Choe for their encouragement and precious comments.
There are many other people at Texas A&M University who have helped me stay motivated. My lab members, Dr. Bikram Sharda, Dr. Abdullah Cerekci and Hongsuk Park provided insights that guided and challenged my thinking, substantially improving my research product. I am also making it indebted to many of my student colleagues.
Additionally, the Department of Industrial and Systems Engineering provides an stimulating environment in which to learn and grow. I am especially grateful to Judy Meeks for always being so kind in assisting me in many different ways.
On a more personal note, I would like to thank my parents, Sejong Lee and Suna Kim, and my brother, Kangsoo Lee and his wife, Dayoung You, for keeping me always positive and supporting my career decisions with their endless sacrifices. Finally, a special thanks to my wife Heejae Choi for her patience and faith in me. Without her
TABLE OF CONTENTS
LIST OF FIGURES
LIST OF TABLES
3.1 Virtual ontology
3.2 Metaearth architecture
5. CONSTRUCTION OF VIRTUAL ONTOLOGYUSING MULTIVIEW SCENES
6. CONTEXT MAPPING FOR VIRTUAL ONTOLOGY
6.1 Graph and subgraph isomorphism
6.2 Metaearth-sub Metaearth isomorphism and context mapping............. 107
6.3 Simulation and analysis of context mapping method
7.1 Research issues and further study
7.2 Summary and contributions
Figure 1 Structure and context in a virtual robot
Figure 2 IDEF-0 diagram of the suggested approach
Figure 5 IDEF-0 diagram for context mapping procedure
Figure 6 Classification of existing methodologies
Figure 7 Cornelis et al.’s method
Figure 8 Grimsdale and Lambourn’s reconstruction method using an expert system
Figure 10 Metaearth architecture
Figure 11 Virtual space layer’s interaction representation
Figure 12 Metaearth architecture for conveyor belts
Figure 13 Metaearth architecture for a virtual factory
Figure 14 Generation of each layer in Metaearth architecture
Figure 15 Metaearth architecture for distributed virtual plant model
Figure 21 General procedure of K-means algorithm
Figure 22 Determination of K using nonlinear programming
Figure 23 Segmented regions using nonlinear programming
Figure 24 Fuzzy color generation
Figure 25 The initial over-segmented image
Figure 26 Example of over-abstraction
Figure 27 Result of cell division
Figure 28 Pre-defined size for determining a noise region
Figure 29 Extraction of a threshold value for noise region handling in the Red color space
Figure 30 Result of fuzzy color-based segmentation
Figure 31 Over-segmented region with fuzzy colors
Figure 32 Elements of a vertex and an edge
Figure 37 Difficulties of shape-related merging condition
Figure 38 An example of object merging
Figure 39 Metaearth architecture after object-merging process
Figure 40 Semantic-merging concept
Figure 42 Metaearth architecture after semantic merging
Figure 43 Overall procedure of the suggested approach
Figure 44 Sensitivity analysis using ANOVA
Figure 45 Metaearth architecture from Tsukuba image
Figure 46 Stereo vision process
Figure 47 Reconstruction process
Figure 48 Stereo images with occluded/non-occluded region
Figure 50 Image rectification
Figure 51 Block matching methods using fuzzy colors
Figure 52 Faugeras et al.’s dynamic programming for detecting occluded regions
Figure 53 Fuzzy sum of absolute dissimilarity cost and fuzzy gradient-based dissimilarity cost functions
Figure 54 Z depth extraction using FDP
Figure 55 Generation of virtual ontology with Z-depth from Tsukuba stereo image pairs
Figure 56 Isomorphism of two scene graphs
Figure 57 Graph-subgraph isomorphism between G2 and G1
Figure 58 Graph-subgraph isomorphism in CAD feature recognition
Figure 60 Context mapping in Meteaearth architecture using graph-subgraph isomorphic matching
Figure 61 Generated Metaearth architecture
Figure 62 Parts of detected subgraph using existing algorithms
Table 1 Related research fields and usage
Table 2 Characteristics of existing research studies in scene understanding
Table 6 Cell division process using EM algorithm
Table 7 Complexity of the suggested algorithm
Table 9 Coincidence degree between ground truth and the suggested approach using different parameters
Table 10 Problems in virtual model construction
Table 11 Proposed FDP method
Table 12 Comparison of algorithm complexity between Ullmann’s algorithm and the suggested algorithm
Rapid development of 3D technologies is encouraging wider application of virtual model and many virtual reality (VR) technologies in the design, control, monitoring and simulation of industrial processes. In 3D technologies’ early stage, the size of virtual environment-embedded applications in manufacturing was relatively small – from equipment, workstation, cell, and shop floor levels to facility levels . Now, the sizes and complexities of virtual systems have grown far larger due to the Internet and ubiquitous technologies.
This trend has combined with large-scale virtual environments (LSVEs), such as metaverse [2, 3], networked virtual environments (NVEs) , massively multi-user virtual environments (MMVEs) [5, 6] and large-scale distributed simulations (LSDSs) . To date, however, much of the relevant literature has ignored how to effectively generate these types of LSVEs. Especially at issue is the quantity of virtual components that can be quickly and simply constructed using the appropriate data structure. Lee and Banerjee have suggested an architecture and interaction modeling methodology known as the Metaearth architecture . This dissertation extends their work by describing the construction of this new methodology from different input sources.
Since virtual components in LSVE often are derived from components in real applications, key characteristics include an automatic/semi-automatic mechanism and This dissertation follows the style of Journal of Manufacturing Systems.
descriptions of the interactions or relationships among the constructed virtual components. To describe any relationship, each virtual component requires a certain type of structures and application-related semantics. The semantics can be represented using several contexts. For example, assume a virtual factory with conveyor belts, robots and industrial machines. The tasks are to visualize the actual factory, as well as measure several production performances against time and space constraints. Each virtual robot needs to be equipped with a structure and contexts in order to produce optimal analyses and simulations. Hence, the structure of each virtual robot will be used for a kinematic structure of the virtual robot, and the mapped contexts of each virtual robot part can be used for the constraints of each component of the virtual robot. Figure 1 shows an example of structure and contexts in a virtual robot.
In a virtual environment, such as a virtual model of natural scenes, the structure can be represented with a “scene graph”. Without this structure and mapped context information, the generated LSVE with many virtual components cannot be used automatically or semi-automatically in the next process: virtual interaction analysis – the analysis and simulation activity using virtual models’ interactions. Some examples are: Traffic simulation such as navigation and collision testing Flight simulation Driver training Electronic simulation Video games As structures and contexts of virtual models have crucial roles in virtual interaction analysis, the extraction process of structure and context mapping activities is an important task in the establishment of LSVE.
We caution, however, that knowledge extraction from unknown environments is one of the most challenging issues encountered in science and engineering fields, because knowledge can be a set of meaningful data among overall data, relationships (between the target and source) or inference rules.
Generally, the knowledge extraction procedure consists of a classification process and an intensification process. The classification process identifies the meanings from source data, and the intensification process increases the degree of the meanings. In the computer science domain, many pattern extraction techniques can be mapped to classification techniques, and learning algorithms for the intensification process. The identified pattern via the classification process can be targeted knowledge itself, or it can be used as the basis for acquiring knowledge. We can combine the patterns with learning algorithms to make them converge with the targeted knowledge. In this fashion, meaningful data can be extracted and converted into knowledge.
Knowledge extraction functions as an important tool for the seamless processing