
Special Issue: 
Virtual Reality in Cultural Heritage 
Guest Editors: Marcello Carrozzino Mihai Duguleana 

Editorial Boards 
Informatica is a journal primarily covering intelligent systems in the European computer science, informatics and cognitive com­munity; scienti.c and educational as well as technical, commer­cial and industrial. Its basic aim is to enhance communications between different European structures on the basis of equal rights and international refereeing. It publishes scienti.c papers ac­cepted by at least two referees outside the author’s country. In ad­dition, it contains information about conferences, opinions, criti­cal examinations of existing publications and news. Finally, major practical achievements and innovations in the computer and infor­mation industry are presented through commercial publications as well as through independent evaluations. 
Editing and refereeing are distributed. Each editor from the Editorial Board can conduct the refereeing process by appointing two new referees or referees from the Board of Referees or Edi­torial Board. Referees should not be from the author’s country. If new referees are appointed, their names will appear in the list of referees. Each paper bears the name of the editor who appointed the referees. Each editor can propose new members for the Edi­torial Board or referees. Editors and referees inactive for a longer period can be automatically replaced. Changes in the Editorial Board are con.rmed by the Executive Editors. 
The coordination necessary is made through the Executive Edi­tors who examine the reviews, sort the accepted articles and main­tain appropriate international distribution. The Executive Board is appointed by the Society Informatika. Informatica is partially supported by the Slovenian Ministry of Higher Education, Sci­ence and Technology. 
Each author is guaranteed to receive the reviews of his article. When accepted, publication in Informatica is guaranteed in less than one year after the Executive Editors receive the corrected version of the article. 
Executive Editor – Editor in Chief 
Matjaž Gams Jamova 39, 1000 Ljubljana, Slovenia Phone: +386 1 4773 900, Fax: +386 1 251 93 85 
matjaz.gams@ijs.si http://dis.ijs.si/mezi/matjaz.html 
Editor Emeritus 
Anton P. Železnikar Volari ˇceva 8, Ljubljana, Slovenia 
s51em@lea.hamradio.si http://lea.hamradio.si/~s51em/ 
Executive Associate Editor -Deputy Managing Editor 
Mitja Luštrek, Jožef Stefan Institute 
mitja.lustrek@ijs.si 
Executive Associate Editor -Technical Editor 
Drago Torkar, Jožef Stefan Institute Jamova 39, 1000 Ljubljana, Slovenia Phone: +386 1 4773 900, Fax: +386 1 251 93 85 
drago.torkar@ijs.si 
Contact Associate Editors 
Europe, Africa: Matjaz Gams 
N. and S. America: Shahram Rahimi Asia, Australia: Ling Feng Overview papers: Maria Ganzha, Wiesław Pawłowski, 
Aleksander Denisiuk 

Editorial Board 
Juan Carlos Augusto (Argentina) 
Vladimir Batagelj (Slovenia) 
Francesco Bergadano (Italy) 
Marco Botta (Italy) 
Pavel Brazdil (Portugal) 
Andrej Brodnik (Slovenia) 
Ivan Bruha (Canada) 
Wray Buntine (Finland) 
Zhihua Cui (China) 
Aleksander Denisiuk (Poland) 
Hubert L. Dreyfus (USA) 
Jozo Dujmovi´

c (USA) Johann Eder (Austria) George Eleftherakis (Greece) Ling Feng (China) Vladimir A. Fomichov (Russia) Maria Ganzha (Poland) Sumit Goyal (India) Marjan Gušev (Macedonia) 
N. Jaisankar (India) 
Dariusz Jacek Jakóbczak (Poland) 
Dimitris Kanellopoulos (Greece) 
Samee Ullah Khan (USA) 
Hiroaki Kitano (Japan) 
Igor Kononenko (Slovenia) 
Miroslav Kubat (USA) 
Ante Lauc (Croatia) 
Jadran Lenarciˇˇ

c (Slovenia) Shiguo Lian (China) Suzana Loskovska (Macedonia) Ramon L. de Mantaras (Spain) Natividad Martínez Madrid (Germany) Sando Martinciˇ´c (Croatia) 
c-Ipiši´Angelo Montanari (Italy) Pavol Návrat (Slovakia) Jerzy R. Nawrocki (Poland) Nadia Nedjah (Brasil) Franc Novak (Slovenia) Marcin Paprzycki (USA/Poland) Wiesław Pawłowski (Poland) Ivana Podnar Žarko (Croatia) Karl H. Pribram (USA) Luc De Raedt (Belgium) Shahram Rahimi (USA) Dejan Rakovi´
c (Serbia) Jean Ramaekers (Belgium) Wilhelm Rossak (Germany) Ivan Rozman (Slovenia) Sugata Sanyal (India) Walter Schempp (Germany) Johannes Schwinn (Germany) Zhongzhi Shi (China) Oliviero Stock (Italy) Robert Trappl (Austria) Terry Winograd (USA) Stefan Wrobel (Germany) Konrad Wrona (France) Xindong Wu (USA) Yudong Zhang (China) Rushan Ziatdinov (Russia & Turkey) 
Editors' Introduction to the Special Issue on .Virtual Reality in 


Cultural Heritage” 

This Special Issue consists of a selection of the best papers from the 1st eHERITAGE Workshop held in 2016 as a session of the 19th international multi-conference 
Information Society 2016. eHERITAGE (‘Expanding the 
Research and Innovation Capacity in Cultural Heritage 
Virtual Reality Applications’) is a Coordination and 
Support project) which is addressing the challenges described in the topic H2020-TWINN-2015 of the H2020 Work programme. eHERITAGE project supports the training and transfer of know-how in the scientific area of virtual heritage, a discipline located at the intersection between new technologies and cultural heritage. Augmented and virtual reality, 3D immersive graphics, real-time haptics and intelligent systems, are all examples of technologies that can be used to provide cultural experiences in novel, more interactive ways. 
When preserving cultural heritage through means of virtual reality, researchers deal with a wide array of techniques and methods. From web-based virtual assistants to photogrammetry, there are thousands of studies out there which tackle multiple areas of interest, throughout various channels of communication. 
Coincidentally, the 1st eHERITAGE Workshop was held during the mid-term of the Horizon 2020, which is the largest research programme initiated by the EU in terms of financial support. One of the main goals of the EU is to finance projects which raise the awareness of the importance of heritage artefacts. In the last 25 years, a great community of scientists have learned, developed and promoted knowledge and skills needed to document, preserve and protect heritage. 
The 1st eHERITAGE workshop tried to cluster all the information available from the partners into just a few areas of interest. The selected papers come from the joint efforts of the 3 partners, namely the project leader Transilvania University of Brasov (Romania), Scuola Superiore Sant'Anna of Pisa (Italy) and Jozef Stefan Institute of Ljubljana (Slovenia), and represent the work results of the first project year. They deal with two main categories: intelligent systems and virtual reality applied to the field of cultural heritage. The first paper by A. Tavčar, A. Csabam and E. Butila, "Recommender system for virtual assistant supported museum tours" presents a web service for virtual museum tours based on intelligent virtual assistants that can learn user preferences and provide recommendations regarding museum exhibitions. The second paper by D. Kužnar, A. Tavčar, J. Zupančič and Mihai Duguleana, "Virtual assistant platform", proposes a novel platform which enables the use of virtual assistants as additional services on websites or as a stand-alone application on mobile platforms. S. Butnariu, A. Georgescu and F. Gîrbacia present in the paper "Using a natural user interface to enhance the ability to interact with reconstructed virtual heritage environments" an assessment of the usability of natural User Interfaces used for navigation tasks in a Virtual Environment, as opposed to the traditional WIMP paradigm. The forth paper by M. Carrozzino, C. Evangelista and R. Galdieri, "Building a 3D interactive walkthrough in a digital storytelling classroom experience" presents a real time 3D walkthrough application based on interactive VR technologies and built with an interactive digital storytelling approach. The study was carried out with and for secondary school students in order to raise their awareness about their local heritage. The fifth paper by R. Brondi, M. Carrozzino, C. Lorenzini and F. Tecchia, "Using mixed reality and natural interaction in cultural heritage applications", presents a general architecture for Mixed Reality applications exploiting solutions based on Natural User Interfaces as interaction metaphors between the Virtual Environment and the user. The last paper, by C. Lorenzini, M. Carrozzino and C. Evangelista, "An interactive digital storytelling approach to explore books in virtual environments" presents the design and the architecture of an educational 3D application enabling reading books in Virtual Environments using an entertaining approach particularly suitable for young people. 

Marcello Carrozzino Mihai Duguleana 

Recommender System for Virtual Assistant Supported Museum Tours 

Aleš Tavčar 

Department of Intelligent Systems, Jozef Stefan Institute, Jamova cesta 39, Ljubljana, Slovenia E-mail: ales.tavcar@ijs.si 
Csaba Antonya and Eugen Valentin Butila Transilvania University of Brasov, 29 Eroilor Blvd, Brasov, Romania E-mail: antonya@unitbv.ro, butila@unitbv.ro 
Keywords: virtual assistants, language processing, cultural heritage, recommender systems, artificial intelligence 
Received: July 18, 2016 

Personalization technology and services have been widely adopted in many domains, especially on various web platforms. This kind of technology is also finding its way to cultural heritage applications since it can broaden the interest for visiting cultural sights. Recommendation systems suggest to users some specific domains that they might be interested in but were unfamiliar with due to their lesser popularity. In this paper we propose a web service for virtual museum tours that is based on in telligent virtual assistants that can learn user preferences and provide recommendations regarding museum exhibitions. 
Povzetek: V pričujočem prispevku predstavimo sistem za virtualne vodene oglede muzejev. Temelji na konceptih virtualnih asistentov, kjer uporabnik postavi vprašanje v naravnem jeziku, sistem najde najprimernejši odgovor in ga prikaže v tekstovni ter grafični obliki z uporabo posnetkov muzeja. Sistem vsebuje tudi priporočilni sistem, ki na podlagi zgrajenega modela preferenc uporabnika priporoča 
oglede predmetov, za katere meni, da bodo uporabniku zanimivi. 
Introduction 
Different museums around the world offer to its visitors a wide selection of artwork, sculptures, vases, ancient objects, and other exhibits. This might be overwhelming for the visitors and most of the exhibits they see might not be of a particular interest to them. This might cause them to lose interest in the exhibition and miss artwork or other objects that are more linked to their personal preferences. This problem has been identified as an increasingly significant trend and addressed in various museums [1][2]. To address this, more and more museums are providing access to their collections in virtual environments (applications, web services, etc.) and are interested in providing new ways to deploy appealing exhibitions to improve the understanding and promote cultural heritage also in younger generations [3][4]. Based on the available digital data, applications can be developed that augment the tours for museum visitors. Ho et al. [5] reported a study where Secondary students were involved in the design and construction of a virtual museum. Virtual tours that exploit VR and AR are already available as an addition to the exhibitions in several museums and offer a more interesting and immersive experience for museum visitors. Several mobile applications and devices are already available and can be integrated in custom virtual reality interfaces [6]. Since more and more content is available in digital form and published on the internet, users would benefit from services and applications that provide virtual tours and suggest specific exhibits that users might like more. 

Monitoring what the user is doing, what he likes and dislikes, thus building a model of his preferences is an important step forward from most of the current application that mainly deliver static content to the user. Personalizing the virtual tour applications and deliver different content for each user is the next step in a modern user oriented application. There are several demanding challenges [7] when designing such systems: lack of content, learning data and users when deploying applications (cold start); data sparsity; rating mechanisms; motivating users to use the system and provide feedback, etc. 
In this paper we propose a novel online web service that offers virtual tours in museums that are covered with the Google Arts & Culture project (Google Street View). The application provides a natural language interface using a virtual assistant (VA), where users can type questions or requests in the user interface and the VA takes care of identifying the correct answer and displays the corresponding feed from Google Street View. Moreover, a recommender system is integrated in the web service that provides suggestions regarding exhibits targeted for a specific user. We will present a proof-of­concept realization (http://www.projekt­asistent.si/eheritage) of the system and define the experimental setup. 
The paper is organized as follows: firstly, a review of the related literature in the field of recommender system for virtual museum tours is provided; in Section 3, the description of the virtual assistant is provided, along with all the functionalities available to the user. In Section 4, the recommendation algorithms are presented and the experimental results are presented in Section 5. 
2 Related work 
Petridis et al. [8] presented two different virtual reality applications developed for the Herbert Museum and Art Gallery that enrich the user experience of their visitors. The first application uses mobile devices in order to deliver additional information regarding exhibitions to visitors. The second application is a serious game based scenario of the Benedictine monastery that requires solving puzzles and quizzes. 
In the literature, several research papers were published on recommendation systems for museum visits. Pechenizkiy and Calders in [9] presented a simple user-focused framework for personalizing museum tours. They focused on efficient learning since the system should be able to quickly provide relevant suggestions only after a small set of user preferences. 
Mathias et al. [10] proposed a new method for personalized museum tour recommendations. Their research tackles the problem of optimizing museum visits according to visitor’s preferences and artwork importance. Through questionnaires they showed that the system clearly improves the satisfaction of visitors who follow the proposed tour. 
Huang et al. [11] proposed a method for personalized guide recommendation system for museum visitors. The developed system used association rule mining to discover recommendations from both collective and individual visiting behavior. Using this system the visitors avoid the exposure to excessive exhibit information. Using questionnaires they showed that visitors had a positive attitude towards the provided suggestions. 
Keller and Viennet [12] have evaluated several recommendation methods to suggest relevant content to museum visitors. Their dataset was collected through a mobile interface that displayed audiovisual content to museum visitors. They were able to bookmark (like) certain content which was later regarded as positive data for the learner. Their system is similar to ours in the way they collected and regarded the data since they do not use five star ratings. 
Although research has already been performed in this area, our approach is different than the one presented in most other papers in the way it interacts with the user and presents the content. 


3 Virtual museum guide 
One of the most important concepts when creating applications that support virtual tours is the usability and user-friendliness of the user interface. We have developed a virtual assistant that understands queries typed in natural language form and provides descriptions or suggestions regarding the searched concepts. Moreover, the system can model the preferences of the 
A. Tavčar et al. 

users and can provide targeted recommendations regarding exhibitions in a virtual museum. 
3.1 Virtual assistant 
The core of the whole system is a web based virtual assistant that can, to a certain degree, understand the questions typed by the users in the natural language form. The VA is instantiated from an existing web framework that allows the creation of basic virtual assistants. It provides functionalities for a full customization of the User Interface and the creation of the VA knowledge base. Its content is created from part of the exhibits of the British Museum (http://www.britishmuseum.org/). In addition, to create a better user experience, the background page that is linked to each knowledge base entry is a Google Street View representation of the location where the exhibit is situated. Figure 1 shows the initial page that is displayed when the VA is instantiated to the content of the British Museum. The designed application can be regarded as an intelligent interface between the user and the recordings of the exhibits in Google Street View. The VA analyses the question of the user, finds the appropriate answer or description and points the user to the correct location of the object in the museum. 

Figure 1: The initial view of the British Museum application. 
The knowledge base entries can be related to a specific room in the museum, a similar group of objects, or to an important exhibit. The VA displays a description of the object, while the page in the background shows a Google Street View representation of the searched object. The user can freely move around and observe the object from different point of views (see Figure 2). 

Figure 2: Virtual tour of the Rosetta stone exhibition. 
As already mentioned, the VA analyses the question posed by the user, it then searches in its knowledge base and displays the answer. If the query is regarding a specific exhibit then the answer is a description of the object that can contain links where additional information can be found. Figure 3 displays a close-up of the VA and the answer when the user searched for information regarding the Rosetta Stone. 
Informatica 40 (2016) 279–284 281 

follows: a comma between keywords denotes OR, a new line is an AND, and the exclamation point a NOT. 
Each entry in the knowledge base has assigned one or more answers or descriptions of the searched object. The responses can be formatted and links assigned to words. In addition, it is possible to set a link that will be shown in the background when the entry is triggered. In our case, the link points to the Google Street View location of the searched object. 

Figure 3: A predefined answer regarding the Rosetta stone. 
Every exhibit or description is stored in the museum management web portal. The records regarding specific exhibits are marked and are later used by the recommender system to build a model of user preferences. 


3.2 Backend interface 
The virtual assistants provide a separate interface (see Figure 4) for each application that can be used to add new content, modify and remove existing entries from the knowledge base. In addition, it provides a mechanism to define keywords or attributes that are used to describe items for the recommender system (tag “Lastnosti” in Figure 4). The sets of keywords are usually different for each item and are used to characterize the object. Based on them, the preference profile of the user is build. The virtual assistants deliver content based on the IF THEN conditional logic (see tag “Pravilo”). For the Rosetta stone entry the rule is presented below: Figure 4: The backend form for defining entries in the knowledge base of the virtual assistant. 


The second important functionality in the backend is the online editor for defining the recommendation algorithm (see Figure 5). It enables the definition of the recommender directly in the backend interface, without the need of redeploying the code. This functionality enables each user to have a different recommendation algorithm, based on their needs. The description below the editor provides guidelines for defining a custom recommendation mechanism. It lists the set of attributes that can be used in the code, as well as the output variables that need to be defined and are required to produce recommendations. The system is initialized with 
|.
.._...
_..
h.
.. THEN {.... 
...... ......... 
.... 
a simple content-based algorithm that builds the preference vector of the user based on the attributes 
The system provides a simple mechanism to define 

linked to each object. The algorithm uses the Cosine 
rules for each entry. Sentences are composed of stemmed 

similarity to compute the distance between the user 
keywords that must be included in the search query and 

preference vector and other items in the database. The 
are linked together with the logical operators AND, OR, 

items with the highest similarity are presented to the 
and NOT. The rule is defined in the “Pravila” section as 

users as recommendations. 

Figure 5: The online editor form for defining the recommendation algorithm. 




Recommender system 
The virtual assistant by itself is a useful interaction tool and can deliver to the user a lot of information regarding museum exhibitions. However, such a simple system is not very different from an online search even though it can provide better targeted information faster. Therefore, we designed a recommendation system linked to the virtual assistant. 
Due to the specificity of the problem (no implicit rating from users) we had to design a recommendation system that learns user preferences based on implicit data (queries, time spent on each answer, motion, etc.) and item features. We decided to implement two content-based filtering algorithms, each with a different approach for providing recommendations. The first is a simple version that will serve as a baseline. To generate a recommendation, the algorithm does not compare users directly, but instead it tries to find the best recommendations for the specific and active user profile. The algorithm computes the similarities between the user profile and the items in the dataset that the user has not seen yet. The similarities are computed using the cosine 
A. Tavčar et al. 

similarity (see Eq. 1) on the profile and item vectors. Vectors that have the same orientation are the same, thus have a cosine similarity of 1. The closest is the computed value between the profile and item vectors to 1, the more similar these two vectors are. 
..............• ........ 

(1) =).
, .... .
....
(...............
.. 
.......................... 

The algorithm then ranks the similarities and identifies the item with the highest similarity for the active user. 
Figure 6 shows a schematic representation of the basic recommendation mechanism. It uses a vector of keywords or attributes that describes each item, or in our case the exhibit. The top vase in the figure has assigned the vector: .... = {........, .........., .............., ......, ..............| 
The vector of the second vase is: 
|........ 
, ....., .... 
.. , ..........,.
...{= 2..
The vector of the third vase is: 
|........ 
, ....., .... 
.. , ..............,.
...{= 3..
Since User 1 searched for the first two vases, his preference model might state that he likes big, colored and ancient vases. Based on the similarities of the user preference vector and V3, the third vase is recommended to the user. A similar mechanism is adopted for User 2. 
Figure 6: A simplified content-based recommendation mechanism for the virtual museum tour system. 
The recommendation mechanism for the second version is based on item-item similarities. This time, the model of the user is not a vector composed of attribute values; instead, the user model contains the list of items he searched for or liked. The algorithm then computes all pairs of similarities (see Eq. 2) between these and new items that the user has not seen yet. 
..........• .......... 

(2) ) = ...
, .... ...
(.... ...............
.. 
........................ 

The unseen item with the highest similarity among all pairs is recommended to the user. 

The main idea is to recommend similar items to the objects the user already liked. This way, the vector model does not get overpopulated with attributes and specific traits remain visible. This approach opens up several variations of the algorithm, which will be explored in future work. 


Experimental results 
In order to initially verify the quality of recommendations and the accuracy of the system, we designed a small experiment involving three users. Users were invited to use the virtual assistant and ask various questions, depending on their preferences. All the queries from the users were collected and stored separately as the learning set. Next, both versions of the recommendation algorithm were used to create a user model and 10-fold cross validation mechanism was used to validate the performance of the model. In each fold, part of the learning set is used to create the vector of user preferences and the other part is used as the test set for validating the recommendations. Each item is classified using the model of user preferences. If the model would recommend the item from the test set, then the recommender has correctly classified the item. 
To fully evaluate the model, the receiver operating characteristic (ROC) curve was created. It is a graphical plot that illustrates the performance of a binary classifier as its discrimination threshold is varied. The curve is created by plotting the true positive rate (recall) against the false positive rate (fall-out) at various threshold settings. The closest is the curve to the top left corner, the better the model performs (perfect classification). A point on a diagonal line results from a completely random guess. Based on the performance of the recommender model on the test set, the ROC curve was 

plotted. Figure 7 shows the ROC curve for the baseline algorithm, where items are directly compared to the 
Informatica 40 (2016) 279–284 283 


vector profile of the user. The AUC measure for this experiment was 0.67. Figure 8 shows the ROC curve obtained from the item comparison recommendation algorithm, where the model of the user is a list of items he searched for. Items to recommend are generated by computing the similarity between items in the user model and unseen objects. The AUC measure for this algorithm was 0.79, which is significantly better as the baseline version. Future versions will build upon this algorithm, since the problem domain seems to fit well with the designed approach. 
6 Conclusions 
This paper presents a web-based application for virtual tours of museums and other locations related to cultural heritage. The system enables the user to visit the exhibitions of museums using a web browser and delivers the content in a user-friendly manner. 
The core of the application is the virtual assistant that facilitates the communication with the user using natural language processing. The user would type a question to the virtual assistant in the same way he would ask another human. The system processes the query and identifies the most appropriate answer from its knowledge base. The knowledge of the assistant contains the information regarding exhibits, groups of objects and exhibition rooms of the British Museum, obtained from the Google Arts and Culture project. In addition, each answer is linked to a specific location from the Google Street view service so the user can experience a virtual tour of the museum. Moreover, the virtual assistant uses a recommendation engine that suggests specific exhibits based on the preference model of the user. We evaluated the performance of the recommendation system and showed promising results. For future work, additional algorithms could be implemented that would exploit the characteristics of the data. In addition, the virtual tour application could be improved by adding immersive technologies. 

7 	Acknowledgement 
The work was co-funded by: the Slovenian Ministry of 
Education, Science and Sports and European Union’s 
Horizon 2020 research and innovation programme under grant agreement No. 92103, project eHERITAGE (Expanding the Research and Innovation Capacity in Cultural Heritage Virtual Reality Applications). 


8 	References 
[1] 	Bowen, J. P. and Filippini-Fantoni, S. Personalization and the web from a museum perspective. In: D. Bearman and J. Trant (Eds.), Museums and the Web 2004: Selected Papers from an Int. Conference, Arlington, Virginia, USA, (2004) 63–78 
[2] 	Rutledge, L., Aroyo, L., and Stash, N. Determining user interests about museum collections. In Proceedings of the 15th international Conference on World Wide Web WWW '06. ACM Press, New York, (2006) 855-856 
[3] 	Prensky, M. Digital game-based learning. Computers in Entertainment, vol. 1, no. 1, pp. 21– 21, 2003 
[4] 	Alawad, A., Aljoufie, M., Tiwari, A. and Daghestani L. Beyond Geographical and Cultural Barriers: The Concept of a Virtual Gallery for Arts, Design & Architecture Schools in Saudi Arabia. Social Sciences and Humanities, vol. 3, no. 4, 2015. 
[5] 	Hoa, C. M. L., Nelsona, M. E. and Müeller-Wittig, 
W. Design and implementation of a student-generated virtual museum in a language curriculum to enhance collaborative multimodal meaning-making. Computers & Education, 57 (1), pp. 1083­1097, 2011 
[6] 	Choudary, O., Charvillat, V., Grigoras, R. and Gurdjos, P. MARCH: mobile augmented reality for cultural heritage. In Proceedings of the 17th ACM International Conference on Multimedia, pp. 1023– 1024, Beijing, China, 2009 
[7] 	Ardissono, L.Kuflik, T. and Petrelli, D. Personalization in cultural heritage: the road travelled and the one ahead. User Modeling and User-Adapted Interaction, vol. 22(1), pp. 73-99, 2012. 
[8] 	Petridis, P., Dunwell, I., Liarokapis, F., Constantinou, G., Arnab, S., de Freitas, S. and Hendrix, M. The Herbert Virtual Museum. Journal of Electrical and Computer Engineering, 2013. 
[9] 	Pechenizkiy, M. and Calders, T. 2007. A Framework for Guiding the Museum Tours Personalization. Proceedings UM 2007 
A. Tavčar et al. 
International Workshop on Personalization Enhanced Access to Cultural Heritage (CHIP). 

[10] Mathias, M., Moussa, A., Zhou, F., Torres-Moreno, et al. 2014. Optimisation using Natural Language Processing: Personalized Tour Recommendation for Museums. Proceedings of the 2014 Federated Conference on Computer Science and Information Systems. pp. 439-446 
[11] 
Huang, M. Y., Liu, C. H., Lee, C. Y. and Huang, Y. 

M. 
2011. Designing a Personalized Guide Recommendation System to Mitigate Information Overload in Museum Learning. Educational Technology & Society 15 (4). Pp 150-166. 



[12] Keller, 	I. and Viennet, E. 2015. Recommender Systems for Museums: Evaluation on a Real Dataset. IMMM 2015 : The Fifth International Conference on Advances in Information Mining and Management. 




Virtual Assistant Platform 
Damjan Kužnar, Aleš Tavčar and Jernej Zupančič Jozef Stefan Institute, Jamova 39, 1000 Ljubljana, Slovenia E-mail: damjan.kuznar@ijs.si 
Mihai Duguleana Transylvania University of Brasov Brasov, Romania 
Keywords: virtual assistant, SaaS, cloud application 
Received: June 15, 2016 

In this paper a novel virtual assistant platform is presented. The platform allows for easy creation, administration, and use of virtual assistants as additional services on websites and as a stand-alone application on mobile platforms. The implementation is based on the principle of Software as a Service, which significantly eases the installation and maintenance of the system and consequently reduces costs. 
Povzetek: Prispevek predstavlja platformo za virtualne asistente s poudarkom na spletni aplikaciji. 
1 Introduction 
Websites of major companies, various institutions, ministries and local administrations are often very large and have a very complex navigation structure, which makes it difficult for visitors to find the information they need. This problem is addressed by using the virtual assistant that helps the visitors find the information in natural language interaction. This kind of interaction hides the complex structure of the website in the background by providing the answers to the questions asked by the users. The use of virtual assistant allows visitors to search for information in a more natural way, which is especially important for less technically experienced users. 
In this paper we describe a virtual assistant platform that has been developed within the project Assistant [1] and is currently running more than 200 virtual assistants. Modern guidelines for development and software distribution were taken into account during the development and, therefore, the platforms was developed as a web service that runs in the cloud. The assistant represents the core for several ongoing projects dealing with tourists, municipalities and smart cities. 


2 Virtual assistant platform 
The service, which supports the creation, management and use of virtual assistants, has been developed on the principle of Software as a Service (SaaS) [2], which brings a number of benefits to customers. For example there is no need for the customer to purchase and maintain hardware, as software runs in the cloud, and no need for installing and maintaining the software. The system consists of the following components (Figure 1): 
.  Web  service  in  the  cloud,  which  allows  
subscribers and end-use rs  ease  of  use  through  
the SaaS principle.  

. 	Web client that offers visitors of a website (end­users) a rich graphic interface for communication with a virtual assistant. 
. 	Mobile clients in the form of mobile applications for the Android, iOS, BlackBerry and Windows Phone 8 platform, which enable for easy communication with a virtual assistant through mobile phones. 
. 	Administrative tools for managing virtual assistants, which allow customers to adapt their assistant to their individual needs. Tools are accessible through browser and are password protected. 
Web service [Saas] 

Administrative 
Mobile clients tools 
[iOS, Android] 



Customers 
End-users 



Figure 1: Virtual assistant platform overview. 

3 Web service 
Modularity, based on the principles of multi-agent systems [3], is an essential feature of the system. This is reflected in such a way that all system functions are implemented as independent modules (i.e. agents) and are able to communicate to each other. The system core, which plays a similar role as the platform in multi-agent systems, provides the mechanism for communication between modules. The components of the system (Figure 2) will be described below. 

Figure 2: The modular design of the system. 
3.1 Core 
The system core implements the following functions, 
allowing the modules to extend the basic functionality of 
the system: . Module management, including discovery, installation, updating, starting and stopping of the modules. The virtual assistant platform has a broad collection of modules available, which can be stopped if desired and thus speed up the system. 
. 	Registration and triggering of events, and registration of listeners that receive triggered events. The modules that trigger the events also define an arbitrary message structure that facilitates communication between modules. 
. 	RESTful API endpoints [4] definitions. Each module can define a function that can be used by end-users (through clients such as web client or mobile application). 
. 	Relational database access. The modules can store the necessary data into a relation database. 
. 	File system access. The modules that need to write and read files are provided with the required access rights. 
D. Kužnar et al. 


3.2 Modules 
The modules are independent functional components that extend the basic set of system capabilities. The core modularity allows the system to be extended to perform any task, however, this article describes the modules for the virtual assistant. Among the most important modules are: 
. 	qa: a module that receives questions from the user, forwards it to the answering modules (*_kb modules) and chooses the most appropriate response on the basis of a predefined procedure. 
. 	*_kb (eg. static_answer_kb): are modules for question answering that obtain answers in various ways. For instance rss_kb obtains answers from RSS feeds. 
. 	html5gui: a module that implements a web based graphical interface of a virtual assistant that users can interact with on websites. 
. 	applications: a module for managing applications (each module can define its own application) that virtual assistant provides to end-users in addition to the basic functionality of question answering. 

The existing system also hosts a number of other modules that provide answers to questions, facilitate the administration of the system, record the conversations between users and virtual assistant, etc. 

3.3 Messages 
Messages between the modules are transmitted when events occur within the system (e.g. when a question is received). Events can be registered and defined by the system core or by the modules that also define the structure of messages that will be sent when the event is triggered. The modules that have registered to that certain event receive the message. Those modules can then return the results of their processing back to the module that triggered the event. This enables the creation of complex processing procedures. 

3.4 REST API 
It is essential for the system to be able to communicate with the outside world. The REST specification [5] is used to create the API in the form of web services. All communication between users and the system goes through this interface, usually by the means of various graphical clients such as HTML5 client for websites and apps for mobile platforms. 
The most important functions provided by the API for virtual assistants are: . / ask (HTTP GET method) 
o 	Input parameters: 
• 	
question: a question that we want the assistants to answer. 

• 	
context (optional): the context within which the question was stated (eg. in applications and 


forms of municipal administration). Available contexts are obtained through the function / applications. 
o 	Response: 
• 	
answer: answer of a virtual assistant in HTML format. 

• 	
id: serial number of the answer, used for storing the evaluation and comments on the answer. 

• 	
URL (optional): a website that is associated with the response. In the case of using a web client, the page will automatically open in the background, in the case of mobile applications the user can open a link in the integrated browser. 


. 	/ vote / id / Up (HTTP POST method) 
o 	Input parameters: 
• 	id part of the route replaced with the value we received as part of the response of the function call / ask. It represents the number of the answer. Example: a call to / vote / 42 / up corresponds to the positive assessment of the response with the serial number 42. 
o This end point has no response . / vote / id / down (HTTP POST method) 
o 	similar to / vote / id / up, only that in this case a negative rating is recorded. In the case of multiple ratings for the same answer the most recent rating is stored. 
. 	/ comment / id (HTTP POST method) 
o 	Input parameters: 

• 	
id: number of the answer, which refers to a comment. 

• 	
comment: comment on the answer. 

• 	
name_and_surname: name and surname of the commentator. 

• 	
email (optional): E-mail of the commentator. 



o 	This end point has no response 


All functions return the answers in JSON notation [6], unless the client defines the callback input parameter, in which case the answer is returned in JSONP notation [7]. 



Web client 
Web client is used to integrate the virtual assistant in the customer’s website. The assistant can appear 
Informatica 40 (2016) 285–289 287 

automatically when the user visits a website or when the users clicks on a link that starts the assistant. 
On launch the web client (Figure 3) hovers over the content of the website and can be freely moved, allowing the user to continue browsing the web page in the background. Upon entering a question into the text box, the web client calls the web service to obtain an answer, displays it in the box below the input field and, if provided by the administrator, opens a webpage in the background that is related to the answer. In this way the web client displays a summary of the response and the visitor is invited to obtain more detailed information from the website in the background if he or she is interested. The Slovenian text in Figure 3: Who is the mayor? The major of Pivka municipality is Mr. Robert Smrdelj … 


Figure 3: Example of a virtual assistant for the Pivka municipality. 
In addition to the common virtual assistant functionality our platform also introduces the concept of applications or apps (accessible via the menu). Apps extend the basic functionality by enabling the use of specific services, e.g. ticket booking, or by focusing the search for answers on specific areas, e.g. the municipality contact information. Every customer can configure its own set of applications that it wants to offer to the visitors. 
5 Mobile apps 
Communication with the virtual assistant is also possible via mobile devices. The interface was adjusted for small screens, since the use of the web interface on mobile devices is awkward, especially for technically unskilled users. The mobile applications are important for several reasons. Mobility is the most important reason, since the user can use the assistant from anywhere, for example the user can ask “Where can I find a pharmacy?” when on the move in a municipality. In this case the assistant would find the information and offer to the user a list of pharmacies in a given municipality with the associated opening time. 
We have developed mobile applications for the two most popular mobile platforms: Android and iOS. Both mobile applications have the equivalent functionality to the web client graphical interface. Figure 4 shows the mobile applications screen design for Android platform. On the upper side of the screen is an input box where the user enters a question. Below the input field is the area for the answer, and underneath is the toolbar, where the user can find all the additional functionalities. The Slovenian text in Figure 4 corresponds to: Municipality Pivka; Do you have any question for me?; Ask me anything regarding municipality such as …. 

Figure 4: The main screenshot of the Android app. 
The functionality of mobile application is identical to the one in the web interface. The user enters the question in the search box and the application sends a query to the server that returns the most appropriate response. In the bottom toolbar there are additional assistant’s features such as: voting on a particular response (positive or negative); posting a comment on a particular answer; enabling speech synthesis; and allowing the users to select one of the applications offered by the assistant. 
Due to smaller screen sizes and data transfer restrictions on mobile devices some specific functionality is changed and adapted for mobile devices. The website 
D. Kužnar et al. 

that which contains more detailed information is accessible by clicking the "more…" button (in contrast to the web client that displays the website in the background). The app also contains the list of all available assistants and the user can select which assistant it wants to connect to. The list of assistants appears when the user opens the app for the first time but is also accessible via the app settings. Further mobile applications are adapted for the elderly and visually impaired, because in addition to speech synthesis it is also possible to increase the font size of the entire graphic interface. 
With the development of mobile applications we wanted to bring our virtual assistant platform even closer to users and to allow its use on a daily basis. 

6 Conclusion 
In this paper we presented a virtual assistant platform – framework for the creation and maintenance of virtual assistants. 
The service operates on the advanced web technology principles. The modular design enables to easily extended the service and add new functionality. Therefore, this service is suitable for a wide range of customers from municipalities and associations to public and private companies, which have their own specific requirements. 

7 Future work 
Due to its extensibility the developed virtual assistant platform can be used in various domains. We will exploit the modular architecture in several upcoming projects. Some of the existing modules will be reused, however, additional modules, specific to each project, will also be developed. In the following paragraphs the important projects will be described and their contribution to the virtual assistant platform will be presented. 
7.1 AS-IT-IC 
Austrian-Slovenian intelligent tourist information center (AS-IT-IC) project was accepted in the cross-border Cooperation Programme Interreg V-A Slovenia-Austria in the programme period 2014-2020. The project addresses the problem of not getting the desired information about natural and cultural heritage sites in the Slovenian-Austrian cross-border area in an integrated way. The goal of the project is to create a joint Austrian-Slovenian center -an ICT supported network of service providers and tourist offices, municipalities, tourists and citizens to enhance continuous cooperation between them. Virtual assistant will be one of the ICT tools that will support the AS-IT-IC center. It will provide automatic answering in natural language to the questions related to the heritage sites and various other relevant tourist information, therefore, relieving the tourist information officers from providing answers to repetitive questions. The system will, in cooperation with human operators (tourist information officers), provide all the relevant tourist information and help the tourists plan a 
area.  JSON-P.org. N.p., n.d.  Web.  30  Oct.  2011.  
During the project several new modules will be  http://www.json-p.org/  
added to the platform: path planning interface; intelligent  
search over the content on natural and cultural heritage;  
automatic information extraction of knowledge from  
existing websites with relevant content, etc.  
7.2 eHeritage  
The goal of the project is the preservation and restoration  
of nation’s cultural heritage in electronic form. With the  
advancements in the field of virtual reality, intelligent  
systems, and AI methods, experts can now use  
augmented and virtual reality, 3D immersive graphics  
and intelligent GUIs to restore and reproduce historical  
sites. Interested individual can experience the historical  
sites in novel interactive and informative ways.  
Virtual assistant platform will provide the means for  
information retrieval from existing heritage sources in a  
natural language. During the project the following new  
modules will be added to the platform: natural language  
museum navigation; automatic extraction and intelligent  
content analysis of existing heritage databases, etc.  
8 Acknowledgement  
The work was co-funded by: the Slovenian Ministry of  
Education, Science and Sports through a public call for  
funding the development of e-services and mobile  
applications for public and private non-profit  
organizations 2012-2013 (JR ESMA JZNO 2012-2013);  
Cooperation Programme Interreg V-A Slovenia-Austria  
2014-2020, project AS-IT-IC; European Union’s  
Horizon 2020 research and innovation programme under  
grant agreement No. 92103, project eHERITAGE  
(Expanding the Research and Innovation Capacity in  
Cultural Heritage Virtual Reality Applications).  
9 References  
[1] "Projekt Asistent." Domov -Projekt Asistent. N.p.,  
n.d. Web. 23 Nov. 2016. http://www.projekt­ 
asistent.si/  
[2] Choudhary, Vidyanand. "Software as a service:  
Implications for investment in software  
development." System Sciences, 2007. HICSS  
2007. 40th Annual Hawaii International Conference  
on. IEEE, 2007.  
[3] Ferber, Jacques. Multi-agent systems: an  
introduction to distributed artificial intelligence.  
Vol. 1. Reading: Addison-Wesley, 1999.  
[4] Richardson, Leonard, and Sam Ruby. RESTful web  
services. " O'Reilly Media, Inc.", 2008.  
[5] Fielding, Roy Thomas. Architectural styles and the  
design of network-based software architectures.  
Diss. University of California, Irvine, 2000.  
[6] "Introducing JSON." JSON. N.p., n.d. Web. 23  
Nov. 2016. http://www.json.org/  





Using a Natural User Interface to Enhance the Ability to Interact with Reconstructed Virtual Heritage Environments 
Silviu Butnariu, Alexandru Georgescu and Florin Gîrbacia Department of Automotive and Transport Engineering, Transilvania University of Brasov 29 Eroilor Blvd, RO-500036, Brasov, Romania E-mail: butnariu@unitbv.ro acgeorgescu@yahoo.com, garbacia@unitbv.ro 
Keywords: 3D reconstruction, virtual heritage, kinect sensor, games engine, interaction, navigation 
Received: June 28, 2016 

Virtual Reality (VR) techniques are used to create computer-simulated environments which enable new forms of cultural entertainment. One critical problem is how to design the 3D virtual environments (VE) and what methods should be used for interaction, in order to offer an entertaining experience in an ope n approach. This paper focuses on the added value of gaming methods for 3D reconstruction and interaction with 3D representations of cultural heritage assets using a NUI designed for games. The impact of game mechanics and interaction was investigated by developing a VE of a medieval burg (Brasov, Transylvania). The VE development involves high quality 3D reconstruction of the burg, creating a collection of gestures to interact with the VE, and their implementation and testing within the VE. The paper also includes a qualitative and quantitative evaluation of the implemented system, as tested by subjects who carried out a navigation session in the VE. 
Povzetek: Prispevek obravnava interakcijo kot v računalniških igrah, a v sistemih elektronske dediščine s 3D virtualno realnostjo. 
Introduction 
Technological breakthroughs in real-time computer graphics, virtual and augmented reality gave us a way to create 3D virtual environments (VE) that allow users to explore cultural heritage. Virtual Heritage (VH) supports the reconstruction, preservation, transfer and display of cultural heritage information using virtual reality. Virtual Reality (VR) refers to a system of concepts, methods and techniques used to develop simulated environments by means of modern computer systems (computers and specialized equipment). 3D historic site reconstruction is one of the most VR -supported cultural dissemination form. 
A critical problem is how to design the VH environments in order to offer an entertaining experience in an ubiquitous and personalized manner. Most literature has argued that interactive engagement in a computer-based environment is best demonstrated by games [1]. Game mechanics and interfaces represent an exceptional opportunity providing innovative approaches to interact with 3D representations of cultural heritage assets. 
In this paper we examine the potential of using computer game engines and user interface techniques, to intuitively create and explore a VE. This article attempts to find answers to the following questions: 
1. 	
What is the added value of the game mechanics for the development of VH environments? 

2. 	
What is the value and utility of this approach in cultural heritage interactive exploration, using a Natural User Interface (NUI) device? 



3. 	Are NUI technologies useful for the navigation in a 3D VH environment? 
The impact of the game mechanics and NUI interaction techniques were investigated by implementing a virtual environment of the medieval burg of Brasov. 
2 	Experimental section 
Virtual Heritage is a system built to create visual representations of cultural heritage facets like historic sites, towns, monuments or artifacts. This concept can become a platform for understanding and learning certain events and historical elements by researchers and visitors. The use of VR technology in architectural heritage facilitates access to cultural heritage sites by mitigating the preservation and dissemination difficulties. To create a VH system, one must address two basic issues: virtual environment reconstruction and interaction. The implementation of these two concepts, which is more than a mere reproduction of an archaeological site, represents a simulation process where objects, behaviors, ecosystems are combined [2, 3, 4]. The goal is to analyze the cultural artifacts, to preserve and share a record of their geometry and appearance, then to acquire detailed shape information [3, 5, 6, 7]. 
2.1 Virtual environment reconstruction 
The procedure of building virtual environments starts with a virtual construction of an archaeological site. Firstly, the potential ancient landscape (geomorphology, water system, soil, vegetation) will be rebuilt and secondly, the anthropic layer of the landscape (sites, monuments, road system, settlements). In addition, the relationships people / environment and people / people are to be defined. However, one issue is raised regarding 3D reconstruction: how can we build a realistic virtual archaeological model based on fragmentary data, in order to obtain the highest reliability and accuracy? Finally, the 3D reconstruction is an interpretation based on the complex analysis of various types of sources, where the “vision” concept has a basic role [3,8]. 
In literature, there are various archaeological reconstructed sites, from small artifacts to entire cities, from computer games to academic studies, using various technologies. The following are some examples: games – Second Life [9], Virtual Egyptian Temple, Roma Nova [10], Battle of Thermopylae, Rome 3D, Assassin’s Creed video games universe[3]; research -Poseidonia-Paestum [22], Aphrodisias Odeon [8], Santa Maria di Cerrate church [12], Suleymaniye mosque [6], city of Tomis [7]; details, reliefs -Byzantine Crypt of Santa Cristina in Carpignano Salentino, Italy [5], an Aeolus (the ruler of the winds in Greek mythology) mask [13], damaged byzantine icons [14], a boxwood prayer nut [15]. 
A 3D reconstruction of a totally or partially destroyed building requires a 3D CAD model that observes the historical construction details. The concept of "cultural heritage" involves several actions (acquiring, processing, presenting and recording data) in order to determine the position, shape, structure, size and other characteristics of a monument or historical site in 3D space at a given time [16]. 3D reconstruction involves the use of continuous surfaces, so it must use global scanning techniques. With traditional surveying techniques it can only get information of discrete lines characteristic of surfaces or edges [17]. Photogrammetry or laser scanning, combined with conventional types of data (historical chronicles, drawings, engravings, lithographs, historical photos) provides different information about the building, other than its geometry. There are several documentation techniques available: traditional manual methods (using very simple equipment: tape measure, plumbs, manual laser distance measurement), topographic methods, photogrammetric methods and scanning methods [2, 5, 12, 18, 19] or new methods, such as computer tomography (CT) technology [15]. Moreover, an important issue, besides the 3D reconstruction of buildings, is the reconstruction of facade details or smaller items, such as statues, paintings reliefs. There are a lot of applications using image processing methods [10, 12, 13, 14, 21]. At the same time, in the real world, such places are populated with people [22]. In the last years, high-resolution recording of historical sites or cultural artifacts has stimulated many researchers in different research areas: computer graphics and computer vision, reconstruction based on photogrammetry [12]. 

2.2 Interaction 
Immersive virtual environments offer users a natural setting for educational and instructive experiences, while 
S. Butnariu et al. 

the game engine technology offers an efficient solution for their development [11]. The virtual environment represents, on one hand, a static world: geomorphology, road system, vegetation, buildings, and other items that do not move and have no behavior and, on the other hand, entities represent dynamic items, some of them affected by physics, or with some form of artificial intelligence (people, rivers, fire and smoke). Every entity has a position and an orientation that can be manipulated by the engine. There is often some crossover, so that parts may be manipulated like entities. For the real-time 3D rendering procedure, 3D Game Engines represent the most appropriate tool for using detailed environments on personal computers [23]. 
The interaction between elements of the virtual environment is an important challenge, compared to the implementation of static elements. While reconstructions used in research do not require special functionalities for navigation, in case of games, the use of real time fast running applications is required. In accordance with the increasing presence of VR based software in computer applications, there has been a growing need for more realistic virtual worlds with ever increasing complexity (the size of the scenes, the complexity of details) compelling developers to invent ever more complex solutions to address the challenges created by such requirements [24]. 
Using 3D game engines to create immersive environments was rarely used technique despite the commercial success and the high level of photorealism achieved by current software / hardware technology (called Serious Games–SG) [20]. 
3D Game Engines are large and complex, but very efficient in creating huge, artificial worlds for entertainment. As they mature, they improve and mimic the real world equally realistic as their competing Virtual Reality (VR) systems counterparts [23]. Examples of these VR platforms can be seen in projects such as: 
For Virtual Reality: . Oculus Rift games developed by RiftTime (a Romanian-Moldavian collaboration) 
. 	The VOID (or the Vision of Infinite Dimensions, developed by a company in Lindon Utah. The project includes combination between haptic feedback and VR) 
. SteamVR (developed by Steam, subsidiary of Valve inc.) . Star Trek: Bridge Crew (developed by Nintendo and 
Sony) . Obstruction (developed by Cyan Worlds/ Ubisoft) . Eagle Flight (developed by the Ubisoft Montreal 
studio) . For Augmented Reality: . Minecraft (developed by Microsoft) . Pokemon GO (developed by Niantic, from San 
Francisco) . Drop Dead for GearVR (developed by PixelToys) . other technologies introduced by Alienware, 
Thrustmaster and Razer. 
The concept of “modern game engines” represents complex parallel systems that are competing for limited computing resources [10]. The technology used for developing virtual environments (games for entertainment, serious games or simulations) is limited by the development budget. Modern entertainment computer games frequently require high budget. Some of these costs can be reduced by using procedural modelling techniques for generating assets, including terrain, vegetation or whole urban environments [23]. 
Interaction in the virtual environment has two major components: navigation and contact between elements. Here are some examples from the researched literature. 
The Ancient Paestum project [11] uses UnrealEngine 2 (UE2) Runtime Edition from Epic Games that provides an integrated development environment through a content creation tool called UnrealEd, able to export objects modelled with 3D editors. Within this tool editing actions of behavior objects (such as triggers, players, non-player-character) are possible. In reference work [4] a virtual heritage is presented, where the reconstruction procedure is based on Autodesk software. Using the map editor of the game engine from Bethesda Softworks® (http://bethsoft.com/age), the virtual model was imported. All entities can be adjusted and modified. The game runs on Gamebryo from Emergent Game Technologies Inc. (http://www.gamebryo.com/) , which is based on a high-quality graphics engine and a physical engine (AI). This game engine supports scientific visualization, allows the avatar creation, and scripting. 
Another game engine is Crystal Space engine (http://www.crystalspace3d.org), detailed in reference work [24]. This software is an open-source software development kit for modern video games and virtual environments. Based on a few modules, this engine forms a complete open-source middleware solution covering most of the needs for the development of modern video games and VR environments. 
Anderson et al. [10] offers a comprehensive state-of­the-art review, which covers a lot of serious games, used in various applications: online virtual environments (e.g. Second Life), cultural heritage (e.g. Roma Nova, Ancient Pompeii, Parthenon Project), virtual museums (e.g. Virtual Egyptian Temple, The Ancient Olympic Games, Virtual Priory Undercroft Coventry), commercial historical video games (e.g. History Line: 1914–1918, Great Battles of Rome, Age of Empires series, and Total War series). 



2.3 	Game engines for virtual reconstruction of medieval cities 
The use of game methods to develop virtual heritage applications is known, and a number of projects have used this approach to reconstruct medieval cities Table 1). The ratings of dedicated websites Gamespot (http://www.gamespot.com) and IGN (http://www.ign.com) are dated back to May 2013. For some projects (especially from universities) we have little information, because they have never been released to a wider public. 
Informatica 40(2016) 291–302 293 

It was also revealed that none of the projects surveyed (online virtual tours, videos, university projects and games developed in the last 10 years) used NUI, excepting other entertainment games from platforms such as Wii, Playstation Move, Xbox 360 and Xbox ONE. 
However the compatibility of the surveyed projects with NUI sensors has not been formally tested and evaluated. In the case of new games and computer graphics engine sites, although it is speculated that the tests have started, they have never been made public. 


3 Test case: The medieval burg of 
Brasov Virtual Heritage 



Environment 

The virtual environment development of the medieval Brasov burg, based on game mechanics consisted of the following steps (Figure 1): high quality 3D reconstruction of the medieval burg of Brasov, creating a collection of gestures to interact with the virtual environment, implementing and testing gestures in the virtual environment, verifying and testing on human subjects, studying results and drawing conclusions. 
The graphics engine used in the virtual reconstruction of the medieval burg is CryEngine 3.4.5, (http://www.crytek.com/cryengine) using the Sandbox Editor within. The main reasons behind this choice are: realistic graphics, freedom of control, movement and interaction, detailed weather simulation, A.I. scripting, openness for a wide variety of 3D model types. 
Also, the interfaces and the buttons are similar to 3DstudioMax or MotionBuilder (http://www. autodesk.com/products/). These tools are provided in order to facilitate animation, scripting, and object creation. CryEngine uses many parameters in order to define the distribution of different textures or types of vegetation. Also, an algorithmic form of painting textures is used. This is the same engine used by famous games producers in developing their own games and has similar power as graphic technologies based on C++: opportunities for import-export techniques, scripting and 

Figure 1: The algorithm of a test case. 3D reconstruction of the medieval burg of Brasov. 

Project name  Camera Graphics Interactioninterface NUI Realism Interactivity Ratings journals Personalfeedback  
Perspective PersonalRating Interactiondevices Type of interface Availability Personal Rating Availability Rating GamespotRating IGNRating Rating  
Tour Virtual : Google Art Project1  first person  10  mouse and keyboard  WIMP  NO  10  No  1  NA  NA  7  
Tour Virtual2  kinematics  7  mouse  WIMP  NO  10  No  1  NA  NA  6  
Google Earth3  total  9  mouse and keyboard  WIMP  NO  10  partially  5  NA  NA  8  
Tour Virtual : “Real and Virtual”4  first person  9  mouse and keyboard  WIMP  NO  10  partially  5  NA  NA  7  
Tour Virtual : Panoramic Earth5  first person  8  mouse and keyboard  WIMP  NO  10  No  1  NA  NA  7  
Tour Virtual – Paris Medieval6  kinematics  8  mouse  WIMP  NO  10  No  1  NA  NA  5  
Battle Castle Dover7  kinematics  10  mouse  WIMP  NO  10  No  1  NA  NA  5  
Medieval City of Bologna8  kinematics  10  mouse and keyboard  WIMP  NO  10  No  1  NA  NA  7  
City Engine9  kinematics  8  mouse and keyboard  WIMP  NO  8  partially  5  NA  NA  7  
Castel Almodovar10  kinematics  7  mouse  WIMP  NO  10  No  1  NA  NA  5  
Nürnberg 3D Second Life11  third person  8  mouse and keyboard  WIMP  NO  9  Yes  10  NA  NA  8  
Assassins’s Creed  I12  third person  9  mouse and keyboard  WIMP  NO  9  Yes  10  9,00  7,70  8  
II13  10  10  third person  10  9,00  9,20  10  
Brotherhood14  10  10  10  9,00  8,00  9  
Revelations15  10  10  8,00  8,50  9  
Mount and Blade16  third and first person  8  mouse and keyboard  WIMP  NO  10  Yes  10  7,50  8,00  8  
Chivalry: Medieval Warfare17  first person  10  mouse and keyboard  WIMP  NO  9  Yes  10  NA  7,90  8  
War of the Roses18  first person  10  mouse and keyboard  WIMP  NO  10  Yes  10  7,50  7,30  9  
Medieval: Total War I şi II19  total  10  mouse and keyboard  WIMP  NO  10  Yes  10  8,80  8,80  9  
London Project20  total  10  mouse and keyboard  WIMP  NO  10  Yes  10  NA  NA  9  

Table 1: Examples of reconstructed medieval burgs [29]. 
graphics to create a virtual environment from scratch. used version that the Kinect sensor is under development Today, elements of the new DirectX 11 have been but not yet compatible with this gestures technology. implemented furthermore. We also observed back in the 

Figure 2: (a) Brasov map, 17th century [25], (b) satellite view (Google earth), (c) photos taken from ground level on 
site (by C. Postelnicu), on the T. Bradiceanu St., showing The Carpenters’ Tower in the foreground and Drapers' 
Bastion in the background along the fortified wall. [28]. 
new DirectX 11 have been mplemented furthermore.. 
In order to achieve the 3D reconstructed model of Brasov’s medieval burg (Ger.: Kronstadt, Hun.: Brasso, Rou.: Corona – in year 1235, Middle Ages), several sources of information were used: old maps (Fig. 2,a) [25], satellite photos -Google Earth (http://www.google.com/earth/) (Fig. 2,b), photos of present fortifications (Fig. 2,c), and other historical sources, such as information from The Carpenter Tower Museum, The National Museum of History and The First Romanian School of Brasov (situated within St. Nicholas Church courtyard), The Virtual Museum inside The Drapers’ Bastion, documents from The National Heritage Centre, information from The City Hall Museum, monographs [26, 27]. The southern defense wall of the burg which also includes some major towers like The Drapers' Bastion and The Carpenters’ Tower has been recently rebuilt in detail (orange in Fig. 2,b).. 
We used different 3D reconstruction methods: image-based reconstruction, 3D modeling, 3D reconstruction from multiple images (especially for details) and multiplication. Implementation of the 3D reconstructed environment into the virtual medium (engine interface) and interaction tasks, has been achieved using CryEngine software in collaboration with other software applications listed below. First we focused on rebuilding the southern part of the burg, near Mount Tâmpa. 
Later we added the specific elements for the Carpenters Tower interior, using other application software: ARC 3D (http://www.arc3d.be/) Google Sketch-up (http://www.sketchup.com/), 3D StudioMax2011 (http://www.autodesk.com/products). The additional free plug-in Play-Up needed to be installed so that the import-export operations between platforms be valid and accurately interpreted by the engine models (http://www.playuptools.com/). The original purpose of the project was to reconstruct the burg only partially. Later, the project grew significantly, elements such as walls, streets and buildings appearing throughout the stage. 
The first step was to reconstruct the site geomorphology. The land is almost unchanged since the Middle Ages, taken as point of reference. In the second stage, we rebuilt in detail the southern part of the defense wall of the medieval burg of Brasov. Furthermore Fig. 3 illustrates the result of a 3D reconstruction of the old burg of Brasov: land, gateway to the settlement, comparison with the old map, and reconstructed south­eastern and northern defense walls in high detail then added the remaining walls and buildings to complete Bra.ov’s medieval burg. 

The major monuments (towers, gates, The Black Church, etc.) were reproduced and located according to plans and historical documents (Josephine map, Radu Oltean’s map etc). In the beginning, our intention was to create a virtual panorama using photos and textures acquired on site. Later, due to high consumption of resources (processing and graphics), we chose to use a random reconstruction of buildings between the virtual walls of the virtual burg of Brasov, by multiplying models for atmosphere, most of which are similar also in reality. 
The advantages of using the game engines technologies for the reconstruction of Brasov medieval burg were: easy integration of day-night cycle in order to emphasize the mountain climate and to simulate the specific atmosphere of the real city, Brasov; the use of specific medieval and natural elements (torches on fire, the sounds of birds and other animals, a few square stacks of straw, wood furniture items, etc.) with the aim to re-create a realistic atmosphere; modeling a realistic water channel area (the medieval “defense moat”) in order to obtain a more accurate representation; building the town’s borders (walls, fences, etc.) in order to separate the accessible area in the virtual environment from the rest of the city region, to increase the sensation of immersion; modeling the wooden pillars on the wooden architecture of the buildings (stairs, walkways, bridges, squares, etc.); generating random copies of virtual buildings; possibility to easily adjust the virtual medieval burg items (scaling the dimensions of virtual doors in all the reconstructed buildings, in order to facilitate access inside the building of the controlled avatar; the slope of the virtual mountain Tâmpa, near the wall of defense, in order to facilitate climbing, should the user want;  adjustments to the water channel areas). 
3.1 Interaction techniques description 
In recent years, the most effective implemented technologies have been based on keyboard-mouse controls, joystick or other controllers. All these devices operate on the simple unidirectional model: up, down, left, right. These interfaces and hardware components can be wired or wireless. The virtual environment perspective has evolved from two to three dimensions, and thus intuitive human-computer interfaces that allow interaction based on complex commands have become necessary. Interfaces that recognize user’s gestures seem to be suitable and more intuitive for interaction with virtual environments. In order to control the virtual environment using gestures, human body position, 
con.guration and movements need to be tracked by 
different sensing technologies. Mainly, these technologies are attached to the user as body suits and 
are based on magnetic .eld or optical trackers. These 
solutions offer suitable accuracy for gesture recognition, but they are expensive and uncomfortable to wear. Recently, ubiquitous tracking sensors suitable for controller-free gestures interfaces have been released. 

Among these sensors, used especially in the latest video games, we can mention the following: Microsoft Kinect®, Nintendo Wii®, Xsens, Lukotronic, Leap Motion. 
To achieve the stated purpose of this study, we chose the Microsoft Kinect® (http://www.microsoft.com/en­us/kinectforwindows/) sensor because it is inexpensive, off-the-shelf and widely available on the market for end-users. Kinect has a RGB camera, depth sensor and multi-array microphone thus being able to detect human natural movement and sound. The software technology enables advanced gesture recognition, facial recognition and voice recognition. A dedicated application can locate the joints of the user in space and track their movements over time, based on the virtual skeleton superimposed over the user's body profile. The software used to create a control interface and communication between user and sensor, as well as the interface between the sensor and computer commands, is Flexible Action and Articulated Skeleton Toolkit (FAAST), developed by MxR, South California University (http://projects.ict.usc.edu/mxr/). FAAST is a middleware software used to facilitate the integration of gesture control interfaces based on game 

Figure 3: The 3D virtual reconstruction of ancient buildings. (a) the reconstructed old saxon town streets; (b) the 
Main Gateway; (c) the same gateway, detail from ancient map [25]; (d) the south -eastern defense wall with the 

Carpenters’ Tower exterior (e) and interior (f), photos taken from Cryengine 3.4.5; (g) the medieval burg of 
Brasov, XVII century [28]. 

control devices in virtual environments. For this purpose, it uses OpenNI and the Microsoft Kinect technology for Windows, both software systems dedicated to tracking human movement through a virtual skeleton. FAAST is free and can be redistributed for commercial or non­commercial purposes. 

Figure 4: Used nodes of human skeleton in FAAST application software. 
The reason for choosing this software is simple: unlike other Kinect-computer interfaces, FAAST acts promptly on calibration and can easily send commands to the computer. Besides, response times are lower, increasing the accuracy. This interface is much easier to manage than Kinect drivers and other dedicated products such as Brekel Kinect or Microsoft Kinect for Windows. The program translates the user’s skeleton over a VRPN server (Virtual-Reality Peripheral Network -a device-independent and network-transparent system for accessing virtual reality peripherals in VR applications) identified as Tracker @ ip address if it’s run over the same computer as the client. The server starts automatically when the feature set of the program connects to the sensor. According to the OpenNI rules, 

used joints (nodes) are presented in Fig. 4. The user’s 
body consists of line segments linked by joints. The system continuously checks the user’s stick .gure and the motion of the joints are used to recognize the interaction gestures. 
In order to navigate in the virtual environment using just a Kinect sensor, we propose a simple and intuitive model, based on the main types of movements and choices in a virtual environment: change of perspective and/or plan of interaction with the environment, activation of certain objects and commands -such as grabbing and/or throwing objects in the scene, their manipulation in a virtual environment, pushing or pulling certain objects in the scene. A series of gestures were developed based on skeleton joints tracking, which were mapped to the interaction commands with the virtual environment: moving forward & back, swimming, panning left and right (strafing), grabbing, jumping, and squatting (or crouching). The following graphic (Fig. 5) illustrates an example of gesture sensing in the real environment, interpretation in FAAST application and the result in virtual environment. Figure 6 below lists the interaction commands mapped to gestures, based on the above presented procedure. 

3.2 Experimental data 
The aim of the evaluation study presented in this section is to assess the way game interface can be used for virtual heritage applications. In the conducted experiment we compared the proposed game natural interaction interface with a traditional WIMP interface. For our test case, we decided to use the old burg of Brasov virtual heritage environment previously presented. 

Figure 5: The act of opening a door and its effect in the virtual environment. Man on the left -hand side of photo: Alexandru Constantin Georgescu – author -after which the motions and map were scaled. 

Figure 6: Used gestures commands. 
We carried out a usability test on a number of 24 subjects aged 19 to 57 (mean= 29,80). Each subject filled in a questionnaire providing information about age and sex, previous experience in playing games and using VR technologies, experience with virtual environments and computer skills. A few of the subjects, usually PhD students, had previous experience in using natural user interfaces. However, all the users were pro.cient in at least one game (as virtual environment) and had good computer skills. 
At the beginning, each subject was informed about the purpose of the experiment and specific instructions were given. They were asked to perform two tests: first, 

to navigate to the Carpenters’ Tower from the old burg of 
Brasov and find some objects using traditional desktop tools with 2D input (keyboard and mouse). The same task was then performed using the proposed game-like natural user interface. Before the test, each participant was allowed to understand and familiarize with the game interface settings. 
The users had 20 minutes, prior to the experiment, to practice the natural game interface functions of navigation and interaction with the virtual environment. Half of the users first used the traditional desktop WIMP interface, then, after a 20 minute break, they were asked to conduct the same task using the game interface newly created. The other half interacted with the virtual environment using the proposed game interface in first instance, and then the desktop system. Each time value was recorded for the assessment of the results. The application ran on a Windows 7 PC with Intel Xeon 3,6 GHz Processor and 16 GB RAM with a NVIDIA Quadro 6000 GPU. 

3.3 Results and discussion 
The task completion time was measured for each participant. Fig. 7 displays the average time needed by the subjects to complete the assigned tasks using both user interfaces. Concerning the performance evaluation, it is to be observed that natural game interface does not considerably improve the navigation in the virtual environment, compared to conventional WIMP interface. 
Informatica 40(2016) 291–302 299 

to run ample moves in front of special devices (Microsoft Kinect). 
Age of respond ents  First impres sion  Inter acti on  Funct ionali ty  Acc ura cy  Easy to learn  Easy to underst and  Av era ge  
19-24 (12pers)  3,83  3,50  3,50  3,42  4,17  4,17  3,76  
25-34 (6 pers)  3,50  3,33  3,50  2,83  4,33  4,67  3,69  
35-44 (3 pers)  3,33  3,33  3,67  3,67  4,67  4,67  3,89  
45-60 (3 pers)  3,00  2,67  3,00  3,00  4,33  4,67  3,44  

Table 2: Mean values of responses by age of respondents. 

In the second phase, we tried to establish a correlation with the gender of the subjects. The results, presented in Table 3, show a significant tendency in women of not being impressed by the new equipment. 


Gender of responde nts  First impres sion  Inte racti on  Funct ionali ty  Acc ura cy  Easy to learn  Easy to underst and  Av era ge  
M (17 pers)  3,82  3,41  3,59  3,29  4,41  4,47  3,83  
F (7 pers)  3,00  3,14  3,14  3,14  4,00  4,29  3,45  

Figure 7: Comparative tests. 
At the end of the experiment the participants were asked to rate the game interfaces on a 5-point Likert scale: Strongly agree (5), Agree (4), Neutral (3), Disagree (2) or Strongly disagree (1) (Fig. 8). The post experiment questionnaire was meant to evaluate ease of use, satisfaction level, and intuitiveness of the game-like interface. 

Figure 8. Results of the subjective questionnaire 
In the first phase, the mean value of responses by age participants was calculated. The results are shown in Table 2. We can observe a decrease of the mean value with age, which can be interpreted, on the first hand, as reluctance to new devices used to interact with machines, and on the other hand, as reservation of the older subjects 
Table 3: The mean values of the responses by gender. 

One aspect that all the studied groups have in common is that this new method of interacting with virtual environments is very easy to learn and understand. Another important element is the accuracy of the interaction, which did not receive a good rating. It was determined that more training is required in order to obtain good accuracy, which might be a natural factor also in regard to any type of new technology. 
It can be observed that the time values for completing the task were higher when the game-based interface was used, as compared with the 2D traditional devices. This can be due to the existing depth camera tracking limitation which does not allow obtaining a precise and stable tracking. 
In comparison with the traditional WIMP interface, the subjects expressed great interest in using game technologies for virtual heritage. The stated reasons relate to the more intuitive virtual environment and the simplification of the series of windows and menus needed for various operations. The users appreciated the gestures interaction functionalities which offered the opportunity of a natural communication of commands. The subjects considered the game interface commands easy to learn and understand, thanks to the natural and intuitive communication paradigm. 


4 Conclusions 
This paper discusses the development of a VH application based on NUI game methods. The test case developed for this purpose was the 3D complex reconstruction of the medieval burg of Brasov, Transylvania, using an available game engine. The advantage of using game technology for development of cultural heritage virtual environment resides in the possibility to achieve better quality, faster development, complexity and .delity by using high quality real-time graphics, powerful AI to handle character behavior, advanced algorithms for character movement system. 
We also proposed and developed a simple and intuitive interface for virtual environment exploration based on the main types of movement gestures as a next step in helping the ever expanding progress of future generations of communication interfaces. The navigation includes forward/backward movement, left/right turn and jump/squat. In the interactive 3D reconstructed medieval burg of Brasov, the user can choose which buildings and rooms to visit, interact with and manipulate virtual objects, experience near-photorealism in indoor and wide-open outdoor environments and extraordinary real-time special effects (like swimming) or the weather system. 
The experiments and trials conducted on subjects showed the feasibility of hand gesture-based navigation techniques and the fact that the natural interaction approach presented herein is preferred by the users in an unconstrained 3D navigation. 
In comparison with the traditional navigation methods using keyboard and mouse, the participants perceive the NUI navigation interface intuitive and easy to use. It is our firm belief that NUI interfaces enable new forms of virtualized cultural heritage which amplify the user’s experience and, for example, can attract a larger number of visitors in museums. 
In future works we will focus on improving movement gestures by filtering the data or using other more performant new NUI devices in order to obtain a more accurate and stable user tracking. 


5 	Acknowledgement 
Author Contributions: Silviu Butnariu contributed to the theoretical research and the state-of-the art. Alexandru Constantin Georgescu contributed to the 3D reconstruction, linking the NUI, calibration through devices and drivers and simulation. Florin Girbacia contributed to testing solutions, recording and processing data. 

6 	Conflicts of Interest 
The authors declare no conflict of interest. 


7 	References 
[1] 	Champion E. (2008). Otherness of Place: Game-based Interaction and Learning in Virtual Heritage Projects. International Journal of Heritage Studies, 14, 210 – 228. 
[2] 	Noh Z. ; Shahrizal Sunar M. ; Pan Z. (2009). A Review on Augmented Reality for Virtual Heritage System, Learning by Playing. Game-based Education System Design and Development, Lecture Notes in Computer Science, 5670, 50-61 
S. Butnariu et al. 

[3] 	Pescarin S. (2012). Ancient Landscape Reconstruction, in 1st Digital Cultural Heritage Workshop, The Cyprus Institute, Nicosia, Cyprus. 
[4] 	Rua H.; Alvito P. (2011). Living the Past: 3D Models, Virtual Reality and Game Engines as Tools for Supporting Archaeology and the Reconstruction of Cultural Heritage – the Case-Study of the Roman Villa of Casal De Freiria, Journal of Archaeological Science, 38, 3296-3308. 
[5] 	Beraldin J.-A.; Picard M.; El-Hakim S.; Godin G., Borgeat L., et al. (2005). Virtual Reconstruction of Heritage Sites: Opportunities and Challenges Created by 3d Technologies, in The International Workshop on Recording, Modeling and Visualization of Cultural Heritage, Ascona, Switzerland. 
[6] 	Mansor I.; Puteri S.J.; Maisarah A.; Nurul S. A. L.; Nor Zalifa Z. A. (2007). Virtual Reality in Heritage Studies and Historical Reconstruction through Animation – a Case Study of a 16th Century University Complex in the Ottoman World, in 7th International Conference on Construction Applications of Virtual Reality, Penn State University, USA. 
[7] 	Popovici D. M.; Querrec R.; Bogdan C. M.; Popovici N. (2010). A Behavioral Perspective of Virtual Heritage Reconstruction, Int. J. of Computers, Communications & Control, V, 8. 
[8] 	de Heras Ciechomski P.; Ulicny B.; Cetre R.; Thalmann D. (2004). A Case Study of a Virtual Audience in a Reconstruction of an Ancient Roman Odeon in Aphrodisias, in VAST-04The 5th International Symposium on Virtual Reality, Archaeology and Cultural Heritage,. 
[9] 	3D Virtual World Second Life (accesed on 13 November 2013). Available online: http://secondlife.com/ 
[10] Anderson 	E. F.; McLoughlin L.; Liarokapis F.; Peters C.; Petridis P. et al. (2010). Developing Serious Games for Cultural Heritage: A State-of-the-Art Review, Virtual Reality, 14, 255-275. 
[11] de 	Chiara R. (2006). Real Positioning in Virtual Environments Using Game Engines, in Eurographics Italian Chapter Conference ed. by R. De Amicis and G. Conti, The Eurographics Association, p. 6. 
[12] Gabellone F. (2009). Ancient Contexts and Virtual Reality: From Reconstructive Study to the Construction of Knowledge Models, Journal of Cultural Heritage, 10, e112-e117. 
[13] Bianco 	G.; Gallo A.; Bruno F.; Muzzupappa M. (2013). A Comparative Analysis between Active and Passive Techniques for Underwater 3D Reconstruction of Close-Range Objects, Sensors, 13, 11007-11031. 
[14] Lanitis A.; Stylianou 	G. (2009). e-Restoration of Faces Appearing In Cultural Heritage Artefacts, in Proceedings of 15th International Conference on Virtual Systems and Multimedia, VSMM '09, Vienna, 15-20. 
[15] Zhang X.; Blaas J.; Botha C.; Reischig P.; Bravin A., et al. (2012). Process for the 3d Virtual Reconstruction of a Microcultural Heritage Artifact Obtained by Synchrotron Radiation CT Technology Using Open Source and Free Software, Journal of Cultural Heritage, 13, 5. 
[16] Yilmaz, 	H. M.; Yakar M.; Yildiz F. (2008). Documentation of historical caravansaries by digital close range photogrammetry. Automation in Construction, 17(4), 489-498. 
[17] Núnez 	Andrés, A.; Buill Pozuelo, F.; Regot Marimón, J.; de Mesa Gisbert. (2012). A. Generation of virtual models of cultural heritage. Journal of Cultural Heritage, 13(1), 103-106. 
[18] de Mesa A.; Regot J.; Núnez M. A.; Buill F. (2009). Métodos y procesos para el levantamiento de reconstrucción tridimensional gráfica de elementos del patrimonio cultural. La iglesia de Sant Sever de Barcelona, Revista EGA, 14,82-89. 
[19] Styliadis 	A. D. (2007). CAAD for Demolished Buildings Modeling with Reverse Engineering Functionality, Cadastre Journal RevCAD, 7, 41-74. 
[20] Carrozzino 	M.; Evangelista C.; Brondi R.; Lorenzini C.; Bergamasco M. (2012) Social Networks and Web-Based Serious Games as Novel Educational Tools. Procedia Computer Science, 15, 303-306. 
[21] Chevrier 	C.; Charbonneau N.; Grussenmeyer P.; Perrin J-P. (2010). Parametric Documenting of Built Heritage: 3D Virtual Reconstruction of Arhitectural Details. International Journal of Arhitectural Computing, 8 (2), 131-147. 
[22] Ulicny B.; Thalmann D. (2002). Crowd Simulation for Virtual Heritage, Proceedings of First International Workshop on 3D Virtual Heritage, 28­
32. 
[23] Johnston D. (2004). 	3D Games Engines as a New Reality, in 4th Annual CM316 , Conference on Multimedia Systems http://mms.ecs.soton.ac.uk/ mms2004/abstracts.php , Southampton University, UK, p. 8. 
[24] Tyberghein J.; Sunshine E.; Richter F.; Gist M.; van Brussel C. (2010). Developing Video Games and Virtual Environments with the Crystal Space Engine, (www.crystalspace3d.org) 
[25] Brasov 	map, accessed on 24 October 2013 from http://art-historia.blogspot.ro/2009/04/afisele-art­historia.html 
[26] Oltean 	V.; Radu M.; Marin E.; Nussbächer G.Bra.ov (2004). Bra.ov Monografie Comerciala, Camera de Comer. .i Industrie Bra.ov, ISBN: 973­0-03514-8, Bra.ov, 40-52. 
[27] Oltean 	V. (2010). Configura.ia Istorică .i Bisericească a Bra.ovului, (Sec. XIII – XX), Ed. Andreiana, ISBN 978-606-8106-19-9, Sibiu, 14-88. 
[28] 	Georgescu A. C.; (2013). Navigarea .i interac.ionarea prin gesturi în oraşe medievale reconstruite virtual, Master Dissertation thesis at Universitatea Transilvania Bra.ov, Bra.ov, 1-82. 
[29] (1)http://www.googleartproject.com/museums/ altesnational; (2) http://www.viagensimagens.com/; 
Informatica 40(2016) 291–302 301 
(3) http://www.google.com/earth/index.html; (4) http://www.learn.columbia.edu/ha/html/medieval.ht ml; (5) http://www.panoramicearth.com/; (6) http://www.secretsofparis.com/heathers-secret­blog/virtual-tour-of-medieval-paris.html; (7) http://www.youtube.com/watch?v= _DeqEnsme 7c&feature=html5_3d; (8) http://www.youtube.com/ watch?v=5U5mSluzZzc; (9) http://www.esri.com/ software/cityengine/ , http://www.procedural.com/ cityengine/ (10) http://www.youtube.com/ watch?v=z-qT5ye9O6Q, http://claudiomarr. blogspot.ro/; (11) http://www.youtube.com /watch?v=sLCQgmWkgI0; (12) https://www. ubisoft.com/en-US/game/assassins-creed/; (13) http://assassinscreed.ubi.com/en-us/games/assassins­creed-2.aspx; (14) http://assassinscreed.ubi.com /en­us/games/assassins-creed-brotherhood.aspx; (15) http://assassinscreed.ubi. com/en­us/games/assassins-creed-revelations.aspx; (16) https:// www.taleworlds.com; (17) http:// www.tornbanner.com/chivalry/esrb/; (18) http:// www.fatsharkgames.com/portfolio_page/war-of-the­roses/; (19) http://www.creative-assembly.com/ game/arena; (20) http://triumphantgoat. blogspot.co.uk/ [or https://www.cryengine.com/ community/viewtopic.php?f=328&t=109027 ] 



Building a 3D Interactive Walkthrough in a Digital Storytelling Classroom Experience 
Marcello Carrozzino and Chiara Evangelista 
Laboratorio Percro of Scuola Superiore Sant’Anna 
Via Alamanni 13, San Giuliano Terme (PI) -Italy E-mail: m.carrozzino, c.evangelista@sssup.it 
Riccardo Galdieri Universita di Pisa Lungarno Pacinotti, 43, Pisa E-mail: riccardo.galdieri@gmail.com 

Keywords: digital storytelling, virtual environments, virtual reality, interaction, education, learning 
Received: July 9, 2016 

This paper presents a real time 3D walkthrough application based on interactive VR technologies, designed and realized with and for secondary school students in order to raise their awareness about their local heritage, in particular the Medieval Walls of Grosseto, Tuscany, one of the rare examples in Italy of defensive walls remained nearly intact to this date. After detailing the learning methodology used in the classroom experiences, the paper thoroughly presents the strategy used to realize the resources needed to build the 3D model of the old town and the final application, built with an interactive digital storytelling approach. 
Povzetek: Opisan je 3D sistem virtualne realnosti za Medieval Walls of Grosseto, Toskana, Italija. 
Introduction 
Several recent educational approaches are successfully exploiting technologies (such as tablets, smart phones, videogames, etc.) which kids use routinely. In this respect, Interactive Digital Storytelling (IDS) [1] represents an interesting opportunity taking advantage of multimedia technologies to develop learning mechanisms 
[2] , with the added values of providing a tool able to convey even complex concepts in an intuitive and playful way, and easily customized to meet different needs, personalities, capabilities [3] . 
Following these principles, we have in the past [4] 
[5] setup a learning methodology and experimented a number of educational programs focused on the following objectives: conveying a content, identified together with teachers, by telling a story; providing knowledge about technology, by means of a learning-by­doing approach enabling kids to create a multimedia product suitable to tell the chosen story; enhancing team skills in kids. 
We have applied such a methodology to the case of the Grosseto, a town in Tuscany whose city walls have remained almost completely intact since their foundations in the XVI century, following a development approach already experimented with success in previous occasions related to the towns of Pisa [6] and Lucca [7] . The result is an interactive application that will be disseminated on the web, exploiting HTML5 3D features, and as a kiosk in local museums using touch interaction. 

2 Related work 
In general, when dealing with Digital Storytelling teachers have usually to keep into account previous experiences of children, their wish to participate, interact and collaborate, their attention span, the perceptual modes of their personal style of learning. Interactive Digital Storytelling is undoubtedly and firmly bound to interactive multimedia, by means of which it conveys content and knowledge [8] . Computers and multimedia let children create virtual environments, new worlds that interact with the real world. This interaction between real and digital allows to setup innovative educational methods and tools that exploit a novel concept of 
“tangibility”: toys, workbooks, drawings assume new 
embodiments and turn into virtual worlds, hypertexts, bytes. 
Using Interactive Digital Storytelling for educational purposes has a number of positive impacts. When using technological tools together with a good and aimed pedagogy, children are stimulated and their enthusiasm is awoken. Moreover, technological means are themselves very appealing for children, who feel strongly encouraged to make use of them to communicate their experiences [9] . There is a large number of projects 
which use computer-based tools to tell stories; a 
thorough selection is hosted on the “The Educational Uses of Digital Storytelling” website of the University 
of Houston. In [10] it is explained how Digital Storytelling may literally hook children into writing, 
offering, at the same time, useful insight on the teacher’s 
role. In [10] the involvement of the family in developing multimedia tools (in this case, e-portfolios) in early childhood education is explored. An important side effect is the development of individual creativity. Similarly, in 
[12] Digital Storytelling is introduced as a way to exhort children to tell about themselves and their personal story. 
Previous relevant investigations on digital storytelling as a learning tool for the specific case of humanities cultural heritage are found in [13] , where it is seen as a means to build "a safe and empowering space for cross-cultural collaboration and learning", and in [14] , where narrative is seen, together with digital technologies, as a support for lifelong learning in cultural settings, being it central to collaboration and to the building of community identity. In latest years new digital technologies, such as VR and AR, are providing powerful means to support IDS due to the better involvement achieved thanks to immersion. Interesting discussions on the use of VR as the digital means for storytelling are found in [15] and [16] . 


3 The learning methodology 
The learning methodology we commonly use in our classroom experiences engages kids in the creation of a multimedia product, such as a movie or a game, in order to stimulate their curiosity and motivation through the use of technology to create, tell and share a story. 
The protocol we follow is commonly based on the following steps: 
1. definition of the learning objective and of the time schedule, together with the teachers; 
2. 
identification of the story object of the narration; 

3. 
definition of the multimedia product; 

4. 
identification of the technological layer; 

5. 
realization of the storyboard; 

6. 
production of the resources (text, images, etc.); 

7. 
development of the product; 

8. 
test and evaluation feedback. 


All these steps see the participation of teachers and students, but especially the first steps deeply involve the teachers as they require to define the topic (usually integrated in the existing school programs), the learning aim and the calendar of meetings (Fig. 1), that has to be defined in accordance with the normal school activities. Subject to the availability of tools and equipment in schools, and depending on the multimedia product to be realized, the technological resources to be used in the process are identified. If needed special equipment, such as Virtual Reality devices, is made available by our institution. A storyboard is then created. Starting from a first draft of the story, the narration becomes structured and broken into elements. At this stage, we also identify all the "fancy" elements meant to improve the involvement, the level of the desired interaction, and 
M. Carrozzino et al. 

other detail features such as non-linearity, immersion, participation and navigation. 
Depending on the storyboard, we identify the needed resources (text, audio, drawings, images etc.) that are collected, if already existing, or otherwise created from scratch. This also requires to translate the story into the visual language, using traditional means such as technical drawing, art expressions and creativity, to be later associated with other digital means, such as scanners and graphics tablets. Drawing is one of the aspects we mainly focus on, as it is an important way for developing creativity and permitting kids to mature. Especially in primary schools drawings often offer a better way than language does for understanding children, as they commonly represent objects not as they actually appear, but rather through a schematic reduction to the essential. 
Once all the material needed to tell the story has been identified and/or collected, it is processed using digital techniques, such as 3D scanning, image editing, digital recording. Voice, sound, and artistic expression are channels enabling students to communicate their thoughts and their creativity in a spontaneous and entertaining way. In order to accomplish the needed operations, the basics of computer science and digital imaging are introduced to the students. In the case of more complex projects involving also 3D environments, students are also introduced to the basics of 3D geometry and shape modelling. 
All the processed material is then gathered and used for the production stage according to the defined outcome. At this stage the work is commonly divided into tasks, some of which are collectively performed while others are distributed depending on the different abilities and preferences. When the product is particularly demanding in terms of the needed technological expertise (for instance programming), we typically continuously assist the development or, in some cases, we completely take over the activity. 
When the product is ready, all the people involved (kids, teachers and we, as tutors) deeply test it, sharing the outcome also with other classrooms, in order to assess the level of clearness of content, to gather suggestions useful to improve the result and to fix errors and inaccuracies. Sometimes, in addition to observation, questionnaires are also provided to all the participants in order to better evaluate the overall experience. 

4 The classroom experience 
The MuraVagando project was developed in order to introduce high school students to their own cultural heritage in a way that differed from the usual in-class activity. The project has been organized by Scuola Superiore Sant'Anna of Pisa and Mnemosyne Digital Culture, supported by the History Institute of the Contemporary Age (ISGREC) of Grosseto, and developed together with the V classes of the Polo Bianciardi Arts High School of Grosseto. The students have undertaken an innovative educational path aimed at acquiring scientific and technological competencies applied to the communication of cultural heritage. This experimentation dealing with the Town Walls of Grosseto has built on a knowledge base previously formed in other experiences of the same high school students and integrated with a VR-based technological approach. To enrich their daily learning experience, students were made part of the creation pipeline of a Virtual Application, also named MuraVagando, which enables users to visit a 3D reconstruction of their home town, Grosseto. A series of meetings in the classroom has leaded to get the students familiar with the concepts of storyboard making, 3D modelling, video shooting/editing and 3D programming. 
Being “Arts and Drawings” their area of expertise, students were asked to use their artistic skills in order to design a nice-looking interface as well as producing several assets to be used in the final application. After visiting the most relevant historical sites of the city to familiarize with the local artistic style, students were guided to design every element of the final application and its features under our technical supervision. They were first asked to draft a draft of the main User Interface, comprehensive of buttons, background images, menus and icons. After that, every student was asked to select a unique spot of the city, draw it on paper, write a description to be used as label, draw a stylized icon, and draw a cardboard cut-out of what a local citizen would have looked like when that opera was created. Once all the assets were completed and digitalized, our task was to find the best fit for all those elements, creating a digital scene that users could explore and share. 



The interactive walkthrough 
The final product is a large 3D interactive reconstruction 
of Grosseto’s Old Town and of its walls that can be 
accessed both as a web-page and as a stand-alone applications running on touch-screens, also providing portability to immersive setups such as Oculus Rift. Particular focus was put on reconstructing all those elements that students have focused on throughout the entire project, such as churches, statues, protective walls and ramparts, as well as other elements they have chosen for their drawings. The application consists of a single centred canvas rendering the 3D scene; a contextual menu is positioned to the left side of the canvas containing four items named “Bastioni” (ramparts), “Chiese ed edifice” (churches and buildings), “Monumenti” (monuments) and “Video” (Figure 1, top). A slightly different layout with the same functionalities is presented in the Web version of the MuraVagando application (Fig. 1, bottom). While pressing on any of these buttons, a second menu appears to the right side of the canvas, showing a list of specific elements belonging to the selected category. A single button representing the city map is positioned right below the canvas, and it is used to access the corresponding view mode. 

5.1 The scene 
The main focus of the scene is always on the external walls, cardinal element of the entire project and main architectural element of the town. 

The walls have been reconstructed in 3D in accordance with the real structure and with the students’ drawings. Transparency was applied on the floor edges to create a turntable effects: the walls and the city are standing on a drawing that fades out to merge with the surrounding environment. It is important to notice that the final model is not a precise scale reconstruction of the actual town: each point of interest chosen by the students was highlighted by scaling up the corresponding mesh to make it stand out from the context, and brighter materials were applied for the same purpose. Each of these spots comes with a descriptive panel written by the same student, presented in the model as a big wooden board (see Figure 2). Panels locations are also used as landing point for state transitions activated by the already described menus. 



5.2 Navigation 
Users can navigate the scene in three different modes: 
-Free Mode: on Free Mode, users can freely move inside the scene with no limitations. In the Kiosk version, a combination of touch gestures and GUI buttons is used to move/rotate/pan the view. In the Web version, mouse and keyboard are used for the same purpose. 
-City Tour: on City Tour mode, the camera follows a predefined path that starts from just outside the city walls, and moves around the entire scene, like a modern drone. The camera visits all the interesting spots in the scene in a continuous seamless loop, however users can still “look around” by rotating the view while moving on the predefined path. This mode is used as default when the application does not receive any input for more than 30 seconds in Free Mode. 
-Map Mode: on Map Mode (see Figure 3), the camera floats above the scene, continuously rotating on the vertical axis. Hotspots corresponding to the most relevant locations can be selected either by touching (kiosk version) or by clicking (web version) the circular elements representing them. Selecting a hotspot triggers a change in the view bringing the virtual camera just in front of the location corresponding to the hotspot. 
Each navigation mode can be activated in any moment by using the GUI. Smooth transitions are implemented during the location changes to avoid spatial disorientation, both when switching navigation mode and after a hotspot or a menu item selection. 
Figure 3: The map mode. 


6 Technical implementation 
Both versions of the application have been developed using the Unity engine, so as to allow a fast portability to various platforms, including web versions. 

6.1 3D models 
The main challenge of modelling a web-based scene including dozens of different monuments and buildings is to keep the number of vertices low. While buildings, such as churches or palaces, can be effectively approximated to boxes, other elements such as statues, fountains and walls require a more complex geometry to be described without too much data loss. Different modelling pipelines had therefore to be used in order to create the meshes: 


M. Carrozzino et al. 

1) the old Medieval walls have been reconstructed by repeating a mesh sample on a NURBS path. A high-poly version was first created; subsequently a low-poly version was modelled, following the high-poly version topology and transferring the UV coordinates from the first model to the other; 
2) the most important buildings, such as churches or fountains (see Figure 4), have been manually modelled, following the proportions given by the students’ drawings. Such models were also scaled up in order to stand out from the overall view. Minor structures such as modern houses were also recreated, based on their real position; 

Figure 4: A manually modeled element. 

3) statues have been modelled loosely according to their shape. However, since students provided only one perspective drawing for each statue in the project, it was decided to use a billboard mesh resembling the statues front shape, to map the drawing as a texture, and extrude some vertices in order to create a 3D effect (see Fig. 5); 
Figure 5: Sculpture billboards. 

4) minor elements have been procedurally generated by using Unity: trees were added to the scene with the Unity Tree Editor, and the sky was created by using the Unity standard skybox material. (Fig. 6). 
All the manually built models have been realized by using the free modelling tool Blender. 


6.2 Textures and materials 
One of the biggest challenge of the project was to achieve a homogeneous look. The students were encouraged to use their own style to realize the drawings, and this brought inconsistency among the produced material. The papers we received came in different colours and styles, using different backgrounds; some students drew different parts of the same object while some others drew just the main view, and most importantly for a 3D model, most of them drew in perspective mode, rather than using an orthogonal view. 
The only shared feature we could identify amongst the drawings was a certain similarity with cartoons. Besides that, all the drawings differed from each other in terms of style, proportion, colours and techniques used. Being purpose of the project to preserve students artworks, the chosen approach was to create a game-alike “cartoony” environment, applying the drawings as textures on the meshes, reducing the reflectivity and increasing saturation (see Figure 7). Minor buildings were rendered using CEL shading materials for the same purpose. 
To avoid inconsistency in the scene, we pre­processed each single drawing we received with an image processing tool, increasing the yellow balance where needed, and adjusting proportions. Once the images had a homogeneous appearance, they were imported into Blender and applied as textures to the UV unwrapped models we previously created. No normal mapping was applied, to keep the scene as “toony” as possible. 

A special case is represented by videos. During the first meetings with the students, it was agreed all together that the application should speak the language of young people, avoiding as much as possible a formal approach. Therefore, the entire experience was conceived as a gathering where some of the students of the school invite people of the same age to wander around the ancient walls (MuraVagando recalls the Italian term for “wandering”) and discover a place in their town rich of stories and cultural elements, yet often disregarded by young people. Therefore in the beginning, and occasionally in specific points of the town, cut-scene videos appear that have been shot by students playing as actors. In order to keep consistency in the visual environment, videos do not substitute the 3D scene as often happens; instead they are mapped onto virtual signboards (see Figure 8, top) placed close to the locations referred by the videos. The overall consistency is also kept using the same type of virtual signboard to 
Informatica 40 (2016) 303–309 307 

display text descriptions related to the architectural elements and placed close to them (see Figure 8, centre). 
Finally, we decide to insert an easter-egg represented by a room in the interior of a building onto whose walls the names of the teachers and of the students involved in the project appears as carved into stone (see Figure 8, bottom). 

Figure 8: Virtual signboard displaying a video (top) and a text description (center). Easter egg with the participant names carved into stone (bottom). 

6.3 User interface 
As mentioned above, the project comes in two different versions: a web-based HTML page and a Kiosk version, 
i.e. a standard Unity executable file to be used on touch­screens. Although the versions share a similar design, due to the different devices on which they are hosted some elements of the GUI had to be positioned differently. 
In both the web and the touch-screen version, a 

contextual menu called “Categories” is positioned on the 
left side of the main canvas, but while the web version did have enough space to avoid overlapping the rendered scene, the touch-screen application came with different proportions and the buttons had to be positioned on top of the rendering canvas. Once any of these category 
button is pressed, a second menu called “Places” appears 
on the right side with the same parameters described for the category menu. Clicking on any of these places button applies a parabolic roto-translation transformation of the camera from its current position to the location of the specified element in the scene. 
A third menu named “Navigation” is used to activate the navigation modes described in section 5.2, but while in the web version the menu is composed of three different icons positioned below the canvas, in the Kiosk versions two arrows have been added to move the camera forward and backward while in Free Mode, so that no complex gestures must be used to move the camera around the scene. 
A different UI is presented while in Map Mode: once the camera reaches its top position above the model, users can no longer access the contextual menus and they cannot freely move around the scene; they can only select from some hotspots placed on the scene. 


6.4 Code structure 
Being the Unity Engine mainly used in game development, the design process has benefited from structuring the entire project as a videogame. However, this choice also presented its downsides, as Unity puts special restrictions on how elements interact with each other in the scene. Specifically, reserved folder names had to be considered to load assets at runtime, and the GameObject – Component relationship had to be taken into account while designing the scripts and their behaviour. 
The entire scene is controlled by the singleton “Scene Handler”, a component attached to an empty “GameObject”. Main tasks of this script are: 
-controlling the application status. In addition to the status described in section 5.2, the application also features other more specific statuses in which users watch a video, or the camera is undergoing an animation between two different positions, etc. Transitions between those status were handled by the component to ensure that only one status could be active at the same time; 
-animating the camera. Once a transition is activated, a parabolic trajectory is computed based on the current camera position and rotation, the final position and rotation, the desired parable height and the animation duration in terms of time and frames; 
-communication with the external functions (Web only). While the Kiosk version is completely handled by Unity, the web page is mostly independent and Unity takes only care of rendering inside the specified canvas element. However, external JavaScript functions can be called to interact with the component and modify the application behaviour; 


7 	Conclusions 
The project ended in June and so far was only publicly presented once at a conference. The application is going to be published on the web in October and agreements are being taken with local cultural institutions to place 
M. Carrozzino et al. 

two interactive kiosks running the application. In this phase we plan to run a user study in order to gather information about the efficacy of the application as a dissemination tool and to identify guidelines for future developments. 
In the framework of the EU 2020-TWINN-2015 eHERITAGE project (grant number 692103), a number of possible future directions have been identified for the project and its possible extensions also to other urban contexts (the city of Brasov in Romania being an example), such as the implementation of a semi-guided navigation mode based on a suggestion system keeping into account user model statistics and location-based information and the support to user-generated content in order to expand and enhance the 3D model through a cooperative effort. The latter option might also suggests to continue with classroom experiences, oriented in this case to the realization of aimed and defined components rather than of the model of a whole urban context from scratch like in this experience. 

8 	Acknowledgments 
We would like to thank Elena Vellati and Luciana Rocchi of ISGREC (Istituto Storico Grossetano della Resistenza e dell'Eta Contemporanea) for creating the opportunity for this project to happen. We would also like to thank students and teachers of Polo Bianciardi, Grosseto, in particular Marcella Parisi, Marta Rabagli and Biagio Cuomo, for the guidance and coordination of the students’ work and for their contribution to the final application. 

9 	References 
[1] 	Lambert, J. (2006). 2nd edit. Digital Storytelling: capturing lives, creating community, Berkeley 
[2] 	Xu, Y., Park, H., & Baek, Y. (2011). A New Approach Toward Digital Storytelling: An Activity Focused on Writing Self-efficacy in a Virtual Learning Environment. Educational Technology & Society, 14(4), 181-191. 
[3] 	Sadik, A. (2008). Digital storytelling: A meaningful technology-integrated approach for engaged student learning. Educational technology research and development, 56(4), 487-506. 
[4] 	Baroni, A., Evangelista, C., Carrozzino, M., & Bergamasco, M. (2005, June). Building 3D interactive environments for the children's narrative: a didactic project. In Proceedings of the 2005 ACM SIGCHI International Conference on Advances in computer entertainment technology (pp. 350-353). ACM 
[5] 	Carrozzino, M., Evangelista, C., Neri, V., & Bergamasco, M. (2012). Interactive Digital Storytelling for Children's Education. Educational Stages and Interactive Learning: From Kindergarten to Workplace Training, IGI Global, 231-252. 
[6] 	Carrozzino, M., Brogi, A., Tecchia, F., & Bergamasco, M. (2005, June). The 3D interactive 
visit to Piazza dei Miracoli, Italy. In Proceedings of 
the 2005 ACM SIGCHI International Conference 
on Advances in computer entertainment technology 
(pp. 192-195). ACM 

[7] 	Camin, L., Carrozzino, M., Leonardi, R., & Negri, 
A. (2010). Nuove tecnologie per la conoscenza e la 
comunicazione di Lucca romana. Archeologia e 
calcolatori, (21), 49-73. 

[8] 	Petrucco C., De Rossi M. (2009) Narrare con il Digital Storytelling a scuola e nelle organizzazioni, Edizione Carrocci, 2009 
[9] 	Barrett, H. (2006). Researching and Evaluating Digital Storytelling as a Deep Learning Tool. In C. Crawford et al. (Eds.), Proceedings of Society for Information Technology and Teacher Education International Conference 2006 (pp. 647-654). Chesapeake, VA: AACE 
[10] Banaszewski, T. 	(2002). Digital Storytelling .nds its place in the classroom. Multimedia Schools, 9(1), 32-35. 
[11] Barrett, H. (2004) Electronic portfolios 	as digital stories of deep learning: Emerging digital tools to support reflection in learner-centered portfolios. Retrieved February 21, 2011 from: http://electronicportfolios. org/digistory/epstory.html 
[12] Ohler, 	J. (2008). Digital Storytelling in the classroom, Corwinn Press 2008 
[13] Benmayor, 	R. (2008). Digital storytelling as a signature pedagogy for the new humanities. Arts and Humanities in Higher Education, 7(2), 188-204. 
[14] Mulholland, 	P., & Collins, T. (2002, September). Using digital narratives to support the collaborative learning and exploration of cultural heritage. In Database and Expert Systems Applications, 2002. Proceedings. 13th International Workshop on (pp. 527-531). IEEE. 
[15] Bimber, O., Encarnaçao, L. M., & Schmalstieg, D. (2003, May). The virtual showcase as a new platform for augmented reality digital storytelling. In Proceedings of the workshop on Virtual environments 2003 (pp. 87-95). ACM. 
[16] Aylett, 	R., & Louchart, S. (2003). Towards a narrative theory of virtual reality. Virtual Reality, 7(1), 2-9. 



Using Mixed Reality and Natural Interaction in Cultural Heritage Applications 
Raffaello Brondi, Marcello Carrozzino, Cristian Lorenzini and Franco Tecchia 
Laboratorio Percro of Scuola Superiore Sant’Anna 

Via Alamanni 13, San Giuliano Terme (PI) -Italy E-mail: r.brondi, m.carrozzino, c.lorenzini, f.tecchia@sssup.it 
Keywords: natural interaction, mixed reality, virtual reality, cultural heritage, museum application 
Received: June 27, 2016 

In this paper, we present a general architecture for Mixed Reality applications. The proposed solution has been developed in order to provide a useful instrument to develop Cultural Heritage applications. During the design of the system, particular attention was given to intangible knowledge, such as manual activities, performing arts, lost civilizations habits, representing a particular heritage poorly addressed by previous studies. The system aims at providing an easy and engaging infrastructure to develop immersive application to be used for communication / dissemination and education purposes. The proposed architecture exploits Natural User Interfaces solutions as interaction metaphor between the Virtual Environment and the user. Natural interaction in fact provides high sense of presence and immersion to the user, improving the user engagement and fostering the learning process. 
The paper presents also two case studies, where two different applications aimed at teaching and disseminating crafts knowledge, in particular printmaking and weaving, have been developed on top of the presented architecture. 
Povzetek: Predstavljena je mešana resničnost za namene elektronske kulturne dediščine. 
Introdction 
Virtual Reality (VR) applications create interactive environments in which the observer feels totally immersed: users can move or interact in a completely synthetic world [1]. Differently, in Augmented Reality (AR) applications the digital content is integrated into the real environment [2]. VR and AR technologies are becoming extremely popular and are used nowadays to implement many kind of applications in several different fields: military, medicine, education, visualization, entertainment, etc…. These two technologies represent two different expressions of a common family of technologies and applications falling under the definition of Mixed Reality (MR). Milgram and Kishino [3] 
theorized the concept of “virtuality continuum” in order 
to create a classification able to describe this concept. They placed on one extreme of the continuum the real world and on the other side a completely virtual world. The space of virtuality continuum lying between the two extremes, all the technologies and applications, represents different flavors of Mixed Reality (MR), including AR (real environments augmented with virtual contents) and Augmented Virtuality (virtual environments augmented with real contents). Several researches have focused on Mixed — rather Virtual or Augmented — Environments, how their adoption can affect several aspects of the user experience and how at the same time they are affected by the new arising technologies. 

VR and MR applications in the context of Cultural Heritage (CH) are nowadays gaining an increasing consent, for a variety of purposes including digital conservation (reconstructing artwork damaged or destroyed) [4][5], for validation of scientific hypotheses in archeological reconstructions [6] and for education [7]. At the same time the recent spreading of depth sensors together with sensorised controllers is nowadays shaping the way we interact with the Virtual Environments (VE). Natural User Interfaces1 (NUIs) are becoming more and more popular, and new richer interaction metaphors can be designed in order to improve the engagement and sense of presence of the users providing a completely new experience [8]. NUIs enabling visitors to be physically and emotionally involved during a virtual experience are becoming popular also in the Cultural Heritage context [9]. 
In this paper we present a general architecture for Mixed Reality systems that can be used to provide an immersive experience to Cultural Heritage visitors. The 
1 Natural User Interface is a term used to identify human-computer interactions based on typical inter-human communication. These interfaces allow computers to understand the innate human means of interaction (e.g. voice and gestures) and do not require humans to "learn" the language of computers (e.g., keyboard and mouse). 
proposed solution can be used both for dissemination purposes, as it enhances the engagement of the user, and for training/teaching activities. In particular such systems results extremely effective when trying to transmit intangible knowledge, as like as craftsmanship, since it allows the visitors to physically emulate the proposed actions. Moreover the system can be used both with static prerecorded material and with real-time capture of the real context. 

2 State of the art 
As above mentioned, differently from VR, MR mixes 
“synthetic” and “real” information making them 
coexisting in the same environment. Most of the applications developed in the context of CH are based on Augmented Reality. Among the first AR applications developed in the CH field is ARCHEOGUIDE [10]. Using a Head Mounted Display (HMD) visitors of archaeological sites can see virtual reconstructions of the temples and other monuments directly superimposed on the real ruins. Nowadays, thanks to the ubiquitous networking availability and the technological progresses in mobile computing, the ARCHEOGUIDE concept has been further developed. New research is focusing on mobile devices as a gateway to provide augmented cultural content everywhere [11]. 
Other AR applications developed in the same field aim at providing new ways of interaction between visitors and artworks inside museums. This “augmentation” of the real-world environment can lead to an intuitive access to museum information and enhances the impact of the museum exhibition on virtual visitors [12]. Wojciechowski et al. [13] developed an AR-system composed by an authoring tool and an AR-browser. Using the former instrument, museum superintendents can design Virtual and Augmented Reality exhibitions. Through the AR-browser, installed for example in a kiosk, visitors can see the representations of cultural objects overlaid on the video captured by a camera. Similarly Chen et al. [14] proposed a new AR guidance system for museums based on markers. ARCube [15] exploits a 3D marker to enable 360° interaction with fully reconstructed three-dimensional archaeological artefacts in real-world contexts. Debenham et al. [16] developed an AR-system used inside the Natural History Museum in London which provides visitors with augmented contents through hand-held displays in order to enable an exciting new way to present the evolutionary history of our planet. In 
[17] Augmented Reality has been used instead to improve the work of the restorers and promote communication and cooperation between them. 
The great success of AR in the Cultural Heritage context is mainly related to the fact that they provide an easy, engaging and friendly way to access information related to a particular asset, commonly by keeping the cultural asset in the foreground and enriching its images with digital content. When dealing with intangible assets, such as performing arts, manual activities, lost civilizations habits, there is not a real concrete object to 
R. Brondi et al. 

augment. This kind of evanescent knowledge requires a deeper usage of virtual components [18] because the real part is not physically present or is not always available. 
All MR solutions usually needs to merge 3D (live or recorded) information coming from the real environment with a 3D synthetic environment as smoothly as possible. By using immersive displays like HMDs, the user experience can be further enhanced. Tecchia et al. in their work [19] proposed a HMD visualization system including the real time stream of 3D images of user's hands recorded with a depth-camera. The system makes use of two colored markers placed on top of the user hands to enable a basic interaction with the VE. The depth sensor put on top of the HMD was in charge of recording the peri-personal space and in particular the user hands. The acquired stream was used to recreate a representation of the user inside the VE. Moreover, using the combination of RGB and depth information coming from the camera, the system recognizes the fingers movements in the environment allowing the user interaction with the environment (e.g. virtual object pinching). 
The metaphors of interaction enabled inside MR applications, from completely Virtual to Augmented ones, represent another extremely important design aspect. Specific solutions impact differently on the sense of Presence, Immersion and Engagement of the user. In the context of CH applications, improving these factors can enhance the impact of a dissemination application. It becomes even more important when the aim of the application is learning or training. Safeguarding and passing over skills and intangible cultural heritage features is the subject of several experiments, as well as large research projects [20][21]. Carrozzino et al. [9] argued that Immersive VEs combined with natural interaction would provide a powerful solution to develop a system to transfer practical skills. 
In the last years several researchers and technological industry leaders have focused on the development of different solutions enabling a smooth and simple natural interaction of the user inside the VE. Most of the efforts so far are focusing on hand tracking solutions [22][23][24]. The Leap Motion Controller represents one of the latest technological products created to enable user natural interaction inside the VE based on hand tracking/gestures. It is gaining a lot of popularity due to the ease of use and tracking performance achieved with the latest updates. This device can be easily integrated in any VR/MR application in order to allow users to see and interact with the VE with their own hands. Coupling the Leap Motion controller with an HMD (e.g. the Oculus Rift or HTC Vive) provides developers with an extremely powerful and relatively cheap VR/MR solution that can be used in many Cultural Heritage contexts to provide extremely engaging experiences to the users. 
Given these premises, the presented architecture aims at providing an easy way to develop MR applications, exploiting the capabilities of HMDs and immersive displays in general, coupled with devices, like the Leap Motion, able to track user hands in order to 

Figure 1: Architecture overview. 
create engaging interactive applications in the context of CH. 



The architecture 
The proposed system has been designed and realized on top of the XVR technology [25], an in-house made VR-oriented framework offering a graphics engine for the real-time visualization of complex three-dimensional models and the support to a wide range of VR devices (such as trackers, motion capture devices, stereo projection systems and HMDs). XVR applications are developed using a dedicated scripting language whose constructs and commands are targeted to VR, including the support to 3D animation, 3D sound effects, audio and video streaming and advanced user interaction. This choice has allowed a good flexibility in terms of support of hardware devices and ease of developing dedicated software add-ons able to expand the capabilities of the framework. Figure 1 gives an overview of the developed system which can be divided in three main parts. A low level infrastructure based on XVR and responsible for the direct interaction with the visualization system. This component is in charge of managing not only the stereoscopic rendering on the immersive displays but also the VE update according to the tracking technologies of the visualization system used. This system element allows applications developed on the proposed system to run on the latest HMDs, the Oculus Rift and HTC Vive, and also on projection based systems like CAVEs displays. 

On top of this low level component the system is composed by a Mixed Reality module which is in charge of merging the real content coming from various streams (audio, images or video either 2D or 3D) with the virtual contents. The resources coming from the real world can be either pre-recorded or real-time captures of the world. The system takes care of handling the different streams, registering them inside the VE and rendering them to the user. 
Dedicated tools have been developed in order to handle 3D video (RGBD streams) acquired with depth cameras like the Microsoft Kinect, since existing tools lack of the features needed to opportunely post-process this kind of data. In particular the suite of developed tools allow to trim the stream (in order to select specific portions of the stored data) and to clean the video data in order to make it easier to seamlessly mix it with the virtual environment (see Figure 2). The use of these tools allow to separate, with a good precision, the desired content of the stream from the unwanted background/noise. 
The virtual content consists of 3D models and Virtual Storyboards (VS). The system interprets the VS, a sequence of instructions defining the application storyboard, in real time. The VS, defined in text files in order to be easily authored by any text tool, provides the possibility of defining custom key-points that can alter 

Figure 2: Cleaning 3D video streams acquired with depth cameras using the developed tools. 
the flow of the application. 
The VS allows also to specify how the real world resources and other elements (e.g. camera animations, interactive elements, movements and dialogues) are displayed in the VE and how the user can interact with them. All the resources and the relationship between the resources, the action of the users, the timing and the environment are defined in these configuration files. This allows to easily replicate the same functionalities in different contexts, loading custom resources and developing different applications. 
3.1 Interaction in the VE 
The developed architecture contains a hand interaction module dedicated to the management of user interaction with the VE. The module is in charge of tracking the user hands and detecting gestures. Using the tracking information, a virtual representation of the user hands is provided in the VE. The system animates the virtual hands interpreting the information coming from the sensors used to capture the user. For each hand, first it uses the position of the palm in order to evaluate the position of the user virtual representation. Then for each finger, it evaluates the angles to be applied to each phalange. 
The detected gestures are used in order to enable actions to undertake in the Virtual Environment. Currently pointing, tapping and pinching gestures have been implemented in the system. These actions can be used to develop the user interaction with the environment 
(e.g. selection/pressing of GUI elements like a button, object selection and or transformation). The module offers an abstraction to the above infrastructure allowing the use of different input systems. The architecture have been tested with the Leap Motion Controller and with the CyberGlove II. Other hand tracking systems will be included in the future. 


3.2 Case Studies 
Using our architecture, two different case study applications have been developed, for two different kinds of intangible Cultural Heritage dealing with craftsmanship. 
The subject of the first application has been the work of printmakers. The VE replicates a structured print house featuring different locations where artisans can show their job, retracing all the steps involved in the process of making a stamp. An approach similar to "I'm in VR" has been used to stream pre-recorded depth-movies inside the 3D VE [21], in order to reproduce real artisan movements. Depth movies allow to observe human motion with a high level of detail. More complex systems using graphics animations would require the use of very expensive motion tracking systems that can also hinder the artisan work (see Figure 3, right). 
R. Brondi et al. 


Figure 3: The pedagogical agent inside the VE (left) and the artisan pre-recorded depth-movies (right). 

Artisans are visualized as pre-recorded depth-movies tessellated in real-time, rendered as polygonal meshes and merged inside the VE. Users can also explore the environment using natural movements or teleporting themselves in different places; they can also interact with the environment by selecting 3D objects and GUI buttons using the provided NUI. 

Figure 4: Watching own hands and artisan’s hands at the same time. 

A virtual character, a pedagogical agent, guides the user through the environment in order to explain the actions of the artisans and to provide information about their work (see Figure 3, left). Visitors, beyond observing the artisans from a classic “third person view” (see Figure 3 right), can observe the manual activities from a “first person point of view” (see Figure 4) as they were seeing his/her own hands. Furthermore, when in first person view, users can try to emulate the movements of the artisan as they see both their own hands, captured by the hand tracking device, and the artisan’s ones. 
The second application developed with the proposed architecture is related to the work of weavers. Weaving is a repetitive manual job, made on a loom. The developed application recreates an artisan workshop where different weavers are working. Users can freely explore the space around the artisan and, like the previously described application, see their own hands and overlap them to the "ghost" hands of the artisan in order to learn how to perform some of the actions needed during the work of weavers. The artisans' hands can be visualized both as pre-recorded depth-movies and as computer graphics animated "avatars". The 3D avatar animations have been recorded using the Cyber Globe II. Using the data gloves 

to capture the artisans’ hands movements has been 
possible in this case because weavers commonly wear gloves in their work and therefore this did not hinder the 
artisan’s activities. This allowed also to compare depth 
videos against avatar animations (see Figure 5) in terms of information delivery and perceived quality. 



4 	Acknowledgments 
The design and implementation of the proposed architecture has been carried out in the context of the AMICA project, funded by Fondazione TIM under the 
“Beni Invisibili” financing program. 
The study of the related work, the setup of the test methodology and the design of future expansions of the described methodology have been carried out in the context of the EU 2020-TWINN-2015 eHERITAGE project (grant number 692103). 


5 	References 
[1] 	Riva, Giuseppe. "Virtual reality as communication tool: A sociocognitive analysis." Presence: Teleoperators and Virtual Environments 8.4 (1999): 462-468. 
[2] 	Azuma, Ronald T. "A survey of augmented reality." Presence: Teleoperators and virtual environments 

6.4 (1997): 355-385. 
[3] 	Milgram, Paul, and Fumio Kishino. "A taxonomy of mixed reality visual displays." IEICE TRANSACTIONS on Information and Systems 

77.12 (1994): 1321-1329. 
[4] 	Carrozzino, Marcello, et al. "The virtual museum of sculpture." Proceedings of the 3rd international conference on Digital Interactive Media in Entertainment and Arts. ACM, 2008. 
[5] 	Brondi, Raffaello, and Marcello Carrozzino. "ARTworks: An Augmented Reality Interface as an Aid for Restoration Professionals." International Conference on Augmented and Virtual Reality. Springer International Publishing, 2015. 
[6] 	Barceló, J. A., Forte, M., & Sanders, D. H. (Eds.). (2000). Virtual reality in archaeology. Oxford, UK: ArchaeoPress. 
[7] 	Economou, Maria, and L. Pujol. "Educational tool or expensive toy? Evaluating VR evaluation and its relevance for virtual heritage." en New Heritage. New media and cultural heritage, Oxon, Routledge (2006). 
[8] 	Brondi, R., Alem, L., Avveduto, G., Faita, C., Carrozzino, M., Tecchia, F., & Bergamasco, M. 
Informatica 40 (2016) 311–316 315 
(2015, September). Evaluating the impact of highly immersive technologies and natural interaction on player engagement and flow experience in games. In International Conference on Entertainment Computing (pp. 169-181). Springer International Publishing. http://doi.acm.org/10.1145/161468.16147 

[9] 	Carrozzino, M., Lorenzini, C., Duguleana, M., Evangelista, C., Brondi, R., Tecchia, F., & Bergamasco, M. (2016, June). An Immersive VR Experience to Learn the Craft of Printmaking. In International Conference on Augmented Reality, Virtual Reality and Computer Graphics (pp. 378­389). Springer International Publishing. 
[10] Vlahakis, V., Karigiannis, J., Tsotros, M., Gounaris, M., Almeida, L., Stricker, D., ... & Ioannidis, N. (2001, November). Archeoguide: first results of an augmented reality, mobile computing system in cultural heritage sites. In Virtual Reality, Archeology, and Cultural Heritage (pp. 131-140). 
[11] Brondi, 	R., Carrozzino, M., Tecchia, F., & Bergamasco, M. (2012, May). Mobile augmented reality for cultural dissemination. In Proceedings of 1st International Conference on Information Technologies for Performing Arts, Media Access and Entertainment, Firenze, Italy (pp. 113-117). 
[12] Sylaiou Styliani, Liarokapis Fotis, Kotsakis Kostas, and Patias Petros. Virtual museums, a survey and some issues for consideration. Journal of cultural Heritage, 10(4):520–528, 2009, Elsevier. 
[13] Rafal Wojciechowski, Krzysztof Walczak, 	Martin White, and Wojciech Cellary. Building virtual and augmented reality museum exhibitions. In Proceedings of the ninth international conference on 3D Web technology, pages 135–144. ACM, 2004. 
[14] Chia-Yen 	Chen, Bao Rong Chang, and Po-Sen Huang. Multimedia augmented reality information system for museum guidance. Personal and ubiquitous computing, 18 (2):315–322, 2014, Springer. 
[15] B Jiménez Fernández-Palacios, F Nex, A Rizzi, and F Remondino. Arcube – the augmented reality cube for archaeology. Archaeometry, 2014, Wiley Online Library 
[16] Paul 	Debenham, Graham Thomas, and Jonathan Trout. Evolutionary augmented reality at the natural history museum. In Mixed and Augmented Reality (ISMAR), 2011 10th IEEE International Symposium on, pages 249–250. IEEE, 2011. 
[17] Brondi, 	Raffaello, and Marcello Carrozzino. "Fostering collaboration among restoration professionals using augmented reality." 2014 IEEE 23rd International WETICE Conference. IEEE, 2014. 
[18] Papagiannakis, 	G., Ponder, M., Molet, T., Kshirsagar, S., Cordier, F., Magnenat-Thalmann, M., & Thalmann, D. (2002). LIFEPLUS: revival of life in ancient Pompeii, virtual systems and multimedia. In Proceedings of VSMM 2002 (No. VRLAB-CONF-2007-038). 
[19] Tecchia, Franco, et al. "I'm in VR!: using your own hands in a fully immersive MR system." Proceedings of the 20th ACM Symposium on Virtual Reality Software and Technology. ACM, 2014. 
[20] Skills 	project, CORDIS EU, available at: http://cordis.europa.eu/project/rcn/103956_en.html 
[21] Carrozzino, 	M., et al. (2015). AMICA-Virtual Reality as a Tool for Learning and Communicating the Craftsmanship of Engraving. Proceedings of 2015 Digital Heritage International Congress, (pp. 187-188) 
[22] Piumsomboon, T., Altimira, D., Kim, H., Clark, A., Lee, G., & Billinghurst, M. (2014, September). Grasp-Shell vs gesture-speech: A comparison of 
R. Brondi et al. 
direct and indirect natural interaction techniques in augmented reality. In Mixed and Augmented Reality (ISMAR), 2014 IEEE International Symposium on (pp. 73-82). IEEE. 

[23] Rautaray, 	S. S., & Agrawal, A. (2015). Vision based hand gesture recognition for human computer interaction: a survey. Artificial Intelligence Review, 43(1), 1-54. 
[24] Ding, W. 	and Marchionini, G. 1997. A Study on Video Browsing Strategies. Technical Report. University of Maryland at College Park. 
[25] Tecchia, Franco et al.. "A Flexible Framework for Wide-Spectrum VR Development." Presence 19.4 (2010): 302-312 




An Interactive Digital Storytelling Approach to Explore Books in Virtual Environments 
Cristian Lorenzini, Chiara Evangelista and Marcello Carrozzino Laboratorio Percro of Scuola Superiore Sant’Anna – Via Alamanni 13, Sam Giuliano Terme (PI) – Italy E-mail: c.lorenzini, m.carrozzino, c.evangelista@sssup.it 
Cristian Postelnicu, Universitatea Transilvania Brasov -Bulevardul Eroilor 29, Bra.ov -Romania E-mail: cristian.postelnicu@yahoo.com 
Maurizio Maltese Universita di Pisa – Lungarno Pacinotti, 43, Pisa – Italy E-mail: mauritrue@gmail.com 

Keywords: digital storytelling, virtual environments, virtual reality, immersion, interaction, libraries archives, education, learning 
Received: June 14, 2016 

This paper presents the design and the architecture of an educational 3D application enabling reading books in Virtual Environments exploiting an Interactive Digital Storytelling paradigm, in order to disseminate culture using an entertaining approach particularly suitable for young people. We also 
present two case studies using this approach: the first one is related to the Lonicer’s Kreuterbuch, a XVI 
century medicine manuscript; the second one is a book composed by three fables written by Lev Tolstoy. 
The paper presents also a preliminary usability test in order to evaluate the suitability of such an 
approach in terms of engagement and comprehension. 

Povzetek: Razvit je sistem za 3D prikazovanje knjig in aplikacija na dveh konkretnih knjigah -
Kreuterbuch, Tolstoy. 

Introduction 

Virtual Reality (VR) is a set of technologies enabling to solution is to use digital means to add features able to recreate interactive environments wherein users can make the reading experience more engaging. move or interact, feeling completely immersed in the In many contexts, VR is often used in combination scene. VR can be used to facilitate and improve learning with Digital Storytelling (DS). DS is defined as the process [1], relying on the sense of Immersion and practice of combining narrative with digital content, Presence in the scene in order to increase the engagement including images, sound, and videos. The outcome is of the users [2]. VR is increasingly and commonly used commonly a movie or, in case interaction is enabled, a for the dissemination of Cultural Heritage [3] and also in videogame or a virtual experience[7]. DS contributes to museums, in order to engage visitors into new the engagement of the users levering on their emotions, experiences [4] or to provide unprecedented access to so that they feel encouraged to continue the story in order collections also to categories of public which are to solve initial questions. commonly excluded. A relevant example is provided by In order to implement a new way to engage the users blind people. In museums it is usually forbidden to touch in digital reproduction of books and in order to explore the exhibited objects. VR offers a way out of this further opportunities offered by the combination of DS limitation by providing simulated contact with digital and VR, we have designed and implemented a VR models of the artworks by using haptic interfaces [5][6]. application that we call augmented book (AB) [8]. This 
In general, it is not possible to touch artworks application provides an immersive exploration of a because this can harm perishable objects such as, for digital copy of a book or manuscript placed in a three-example, manuscripts, being ancient paper particularly dimensional context. The augmented book allows to subject to damages in case of inappropriate handling. interactively experience the navigation and the Many libraries typically proceed to the digitization of exploration of the book pages and their content, with the their book collections aiming at improving their addition of DS elements conceived in order to increase accessibility. These digital reproductions are often used the application appeal. This paper presents this by researchers for their studies, but commonly do not application and also demonstrates the potentials of virtual raise particular interest in casual users. A possible technologies to engage children into reading by enabling an approach different both from traditional books and e-books. 
2 The book application 
In the AB approach, users can not only browse, see and 
zoom the book’s original pages, but also explore 
additional resources (such as transcriptions, translations, video, audio, animations, 3D text images and 3D models) 
according to an enriched storyboard “augmenting” the 
book content. Hotspots are placed on relevant points of the book interacting with which users can select pictures or other relevant content triggering videos, 3D animated objects, pop-up captions, and audio narration (see Figure 1). 

Figure 1: An example of Augmented Book. 
The AB, developed using the XVR technology [9], parses and interprets an XML file that specifies the layout resources on the environment and manages their behavior. 
The separation between resources and application allows an easy extension of the book, being the definition of the content independent from the container software application. This flexibility yields several advantages: the same application is adaptable to almost all books, and the same book can be “upgraded” enriching objects or inserting additional content. Indeed, these operations only involve editing the XML resource file, instead of modifying the application which would require programming skills (see Figure 2). 

Figure 2: The XML schema of the AB. 
The XML schema defines the resources loaded by the application, organizing the book like a container of pages where information is mapped onto. On each page it is possible to define a number of selectable hotspots together with their position on the page. Each hotspot can 
C. Lorenzini et al. 

be linked to images, 3D models, videos or audios; it is additionally possible to describe a specific behavior (for instance: animation, fading, etc.). 
The separation of concerns has been applied also to the interaction (enabling the use of devices such as touch screen, mouse, joystick, Microsoft Kinect etc.) and to the visualization modes (adapting to tablets, desktop PCs, or immersive stereoscopic visualization systems like CAVEs). For all these reasons, this application can be considered a sort of framework to enable advanced presentations of books in Virtual Environments. 
The look and feel of the application has been conceived in order to improve the 3D effect even in absence of stereoscopy (which is indeed supported). For instance, 3D objects augmenting the book appear emerging more evidently in foreground with an enhanced parallax. The depth perception is increased using textures baked with lighting information and self-shadows for 3D objects and a fading-to-black technique darkening the book during the pop-up phase with additional shadow casting able to increase the depth perception. The general 3D effect is obviously even more perceivable on immersive devices, such as HMD or CAVE-like systems, on which the application has been specifically adapted and tested. 
In order to adapt to different visualization systems, the application provides two different GUI modes. The first one is made using 2D overlaid buttons, suitable for desktop and touch devices (see Figure 1). The second one makes use of 3D buttons integrated inside the Virtual Environment, more suitable for immersive visualization modes (see Figure 3). 

Figure 3: The GUI integrated in the Environment. 

The resource file allows also to specify the background audio and several sound effects enabled during the exploration. 

3 Case studies 
Using the AB framework, two different virtual books have been developed. The first one was implemented inside a larger project named MUBIL [10][11], an interdisciplinary cooperation project partnered by the Gunnerus Library of Trondheim, the Norwegian University of Science and Technology, and the PERCRO 
laboratory of Scuola Superiore Sant’Anna, Pisa. The aim 
of the project was dealing with the creation of a hybrid exhibition space where the content of the historical archives of the Library have been presented to a wider public, with a special attention to youngsters. 
In this project, a treatise on medicinal distillation, written by Adam Lonicer (1528-1586) was augmented. In this case the information provided, besides being referred to the text itself and the author, were related also to alchemy and science in general at that particular historical period. In the Lonicer Augmented Book (ALB), models and 3D animations inspired to the original book illustrations have been purposely developed (see Figures 4). 

Figure 4: Pop-up models over the Augmented Book. 
ALB includes also some videos: for instance the first book illustration was transposed into 3D through a series of depth layers as shown in Figure 5, and on top of this a movie was produced where a specific narration synced with the 3D exploration of the resulting environment described the place, the characters, the facts etc. 

Figure 5: The realization of the video using different layers. 
In the ALB users can also browse, zoom and pan the original pages of the book and access the transcription of the book pages in a more readable format (the original book uses gothic fonts commonly hard to be read) or the translations into other languages, such as Norwegian or English (the original being written in ancient German). 

The second book is composed of a set of three fables written by Lev Tolstoy. In his life, Tolstoi wrote many fables with educational purposes in order to spread knowledge among the young population of Russia, characterized of a low level of schooling during the XVIII-XIX centuries. The Russian Readers book (original title Russkie knigi diya chteniya, 1875) is a collection of legends and fables from the folk tradition, often adapted to the context, and physical considerations made using a simple language in order to disseminate collective knowledge and educate young people. The treated arguments and the used language make novellas contained in The Russian Readers intrinsically interesting to be developed in a DS application. For that, we have chosen three different fables: “How does the wind form”, an explanation of the physical phenomena of the wind, “Magnet”, a folk legend regarding the birth of magnets used as a pretext in order to also explain their physical properties, and “The right judge”, a moral value fable in which a judge makes decisions using his wit. 
Like the ALB, the Augmented Tolstoy Book (ATB) has been developed as content for the AB framework. Readers can browse pages and read them translated either in Italian or in the native Russian language. Italian texts are from the book “I quattro libri di lettura”, Lev Tolstoy (ISBN Editions, 2013) and the native Russian texts and Cyrillic typefaces are from site www.rvb.ru. 
The pictures present in the book pages act as selectable hotspots. When a picture is selected, a 3D representation of it moves over the book. This 3D representation of the images was created subdividing the 2D picture into layers and moving these layers into different depths, in order to simulate a depth effect (see Figure 6). 

Figure 6: The image divided in depth layers. 


4 Test and validation of ATB 
In order to evaluate the application, a preliminary test was setup involving 20 volunteers working in our laboratory (therefore with a high education level) dealing with a ATB session featuring one of the three fables. We 
selected “Magnet” because of its immediacy and of its 
variety, as it contains mixed elements of fable and scientific descriptions. 
We have divided the sample of the users in a test group (TG) and in a control group (CG), each of them composed by 10 users. TG has experienced the fable using the ATB application, while CG has read the same fable on a traditional paper book. 
The objective of the test session was to evaluate the pleasantness of the ATB experience, to test if ATB makes explicit all his features and to assess if reading the fable through ATB gives a better comprehension than using a normal book. In order to perform this assessment, TG have answered to a set of subjective Usability Questions (UQ) and Comprehension Questions (CQ), while CG has answered only to CQ. 
Analyzing UQ responses, we can see that TG found that ATB provides a higher sense of expressivity (see Figure 7), mainly due to the ATB 3D interactive features. 

Figure 7: ATB expressivity (left) and 
perceived contribution of 3D to expressivity (right). 


Figure 8: ATB perceived difficulty (left) and 
ATB involvement of the user (right). 

ATB was also considered easy to use, and able to provide a significant sense of involvement (see Figure 8). 
In terms of comprehension, the results of TG and CG are comparable, even if CG obtains slightly better results. A possible reason could be that, being the fable fairly short, it may be easier/faster for users to read and learn in a traditional fashion. In particular, some of the questions were aimed at understanding if the impact of the introduction of the augmented content was mainly positive (i.e. help the comprehension by means of additional information) or negative (i.e. acting as element of distraction). The homogeneity observed across the two groups suggests that the impact was mainly at the involvement/amusement level rather than at the understanding one. 
C. Lorenzini et al. 


5 Conclusions 
The Interactive Digital Storytelling approach pursued within the Augmented Book application suggests that good results can be achieved in terms of comprehension, while at the same time eliciting a better involvement. Although, as above mentioned, editing an AB is as easy as modifying a text file, we are also planning to build a dedicated visual editor in order to make this process even easier and accessible also to non-technical people. 
Although a proper validation of the ALB was not carried out, it has found an exceptionally warm reception in terms of audience satisfaction when presented on several occasions in public exhibitions. 
Instead, the validation test of the ATB, although preliminary, provides useful contributes to the implementation of further Augmented Books. However, we plan to perform a more proper assessment on children, i.e. the public to which the original book was targeted, in order to obtain more useful results especially as far as the comprehension of the text is concerned. 
In this sense, we have already contacted schools interested in participating to the expansion of the book and to insert such technologies in curricular scholastic activities. 
In the framework of the eHeritage project, we are also preparing a new version of the AB supporting different types of 3D animations and more interactivity, The new AB will be tested on the Constitutio Criminalis Theresiana, a penal code of great historical relevance, which also includes plenty of illustrations effectively translated into 3D animations. 

6 Acknowledgments 
The study of the related work, the setup of the test methodology and the design of future expansions of the described methodology have been carried out in the context of the EU 2020-TWINN-2015 eHERITAGE project (grant number 692103). Special thanks to the Gunnerus Library and, in particular, to Alexandra Angeletaki which coordinated the MUBIL project. 

7 References 
[1] 	Riva, Giuseppe. "Virtual reality as communication tool: A sociocognitive analysis." Presence: Teleoperators and Virtual Environments 8.4 (1999): 462-468. 
[2] 	Furness, T., William Winn, and Rose Yu. "The impact of three dimensional immersive virtual environments on modern pedagogy: Global change, VR, and learning." Proceedings of Workshops in Seattle, Washington, and Loughborough, England in May and June. 1997. 
[3] 	Carrozzino, Marcello, et al. "The 3D interactive visit to Piazza dei Miracoli, Italy." Proceedings of the 2005 ACM SIGCHI International Conference on Advances in computer entertainment technology. ACM, 2005. 
[4] 	Wojciechowski, Rafal, et al. "Building virtual and augmented reality museum exhibitions." 
Proceedings of the ninth international conference on 3D Web technology. ACM, 2004. 
[5] 	Iglesias, R., et al. "Computer graphics access for blind people through a haptic and audio virtual environment." Haptic, Audio and Visual Environments and Their Applications, 2004. HAVE 2004. Proceedings. The 3rd IEEE International Workshop on. IEEE, 2004. 
[6] 	Loscos, Céline, et al. "The Museum of Pure Form: touching real statues in an immersive virtual museum." VAST. 2004. 
[7] 	Robin, Bernard R. "Digital storytelling: A powerful technology tool for the 21st century classroom." Theory into practice 47.3 (2008): 220-228. 
[8] 	Angeletaki, A., Carrozzino, M., & Giannakos, M. N. (2013, October). Mubil: Creating an Immersive Experience of Old Books to Support Learning in a 
Informatica 40 (2016) 317–321 321 
Museum-Archive Environment. In International Conference on Entertainment Computing (pp. 180­184). Springer Berlin Heidelberg. 

[9] 	Tecchia, Franco et al.. "A Flexible Framework for Wide-Spectrum VR Development." Presence 19.4 (2010): 302-312. 
[10] Carrozzino, M., et al. "Information landscapes for the communication of ancient manuscripts heritage." Digital Heritage International Congress (DigitalHeritage), 2013. Vol. 2. IEEE, 2013. 
[11] Lorenzini, 	C., et al. "A Virtual Laboratory An immersive VR experience to spread ancient libraries heritage." 2015 Digital Heritage. Vol. 2. IEEE, 2015. 


IJCAI 2016 – The Best AI Times Ever? 

Matjaz Gams, 
Jožef Stefan Institute, Jamova 39, 1000 Ljubljana, Slovenia 
E-mail: matjaz.gams@ijs.si Keywords: Conference report, IJCAI, AI Received: August 5, 2016 

Editorial 
25th Artificial Intelligence (IJCAI) was held in New York, USA from July 9th to July 15th. This was the first IJCAI annual conference after a series of two-years intervals. Before the event, some concern was raised regarding the expected number of contributions because of the twice shorter time for preparation and paper submission. Another issue was the New York itself as one of the most expensive world metropolis. In reality, 2300 papers were submitted and 1700 participants poured into the Hilton hotel, one of the best numbers of all times. Of 2300 papers, 551 were accepted. The conference was accompanied with various events such as 3-days of workshops and tutorials, and a visit to the Museum of modern arts. The central theme of IJCAI’16 was “Human aware AI”. Indeed, many papers dealt with AI systems 
The 2016 International Joint Conference on 
recognizing human physical and mental state and activities including sentiments and feelings. On the other hand, this IJCAI was much more cautious in terms of too much AI hype. For example, while papers were dealing with feelings, it was often emphasized that there is a distinction between human feelings and what is perceived through AI systems. Similarly, the researchers were careful not to provide a tentative but unreal claim to 
“fully” understand or simulate human properties. 
Of particular interest were the “White House workshops” at which several White House leaders, i.e. political leaders of medium range openly and privately discussed several AI-related issues with the invited scientists. While such relations with national official are of great importance, it was a bit unclear if this mixture of politics and science leaves no influence on the scientific objectivity. An example was an issue of police treatment of suspects of different heritage. This is a valid research as long as politicians remain remote. Otherwise, such analyses should be treated as compromised by default since history tells us that nearly all research was more or less influenced as soon as politics was involved in any way. Having observed that, the influence of AI on leadership is of great value and importance since it can provide valuable estimation of future actions. 
In terms of AI progress in the last year and AI relevance in real world, it was often emphasized that now it is the golden AI era, the best AI times ever. The number of killer AI applications is growing fastest ever, there are lots of new AI students, and applicants with knowledge of AI or machine learning have advantage at job applications. 

It was particularly interesting to observe the relation between the IJCAI leaders and the superintelligence (SI) issues. In recent years, a world-wide attention was caused by top world thinkers like Hawkins, Gates or Musk that AI will soon by-pass humans in nearly all mental activities, and that the emergence of SI might endanger the human race. As a result, at IJCAI’15 in Argentina several aspects of SI were discussed. For example, a position to prohibit autonomous weapons in a similar way as biological weapons was proposed. Following these events in several societies, a world-wide movement to stop autonomous weapons was established. Intensive lobbying was carried out in several countries and in particular in UN. 
In 2016, leading AI researchers have taken a pragmatical stance on the SI issue. Instead of trying to define intellectual world opinions, the main orientation was “back to the future”, i.e. back to the technical achievements. AI visions and trends were distanced from the IJCAI leadership nearly as kind of speculations and science fiction. Moreover, several warnings were issued that expectation and prognoses of computers overpassing humans are technically not correct, rather resembling overhyped media reactions. 
The influence of AI on our everyday life is neither fully understood not fully appreciated. While killer applications, i.e. great successes, are reasonably well presented in major media, e.g. organ exchange, self-driving cars, Google’s AlphaGo or Amazon’s AI, several other achievements are not. Consider an example that was not presented in main-stream media: When an infants of an AI researcher Michael Jordan was examined by ultrasound, white dots were discover near the heart. The clinical advice was to perform an additional test with 1/250 chance of causing severe consequences including death. As AI scientist and father he examined all available papers and in particular those describing the sensing data and clinical experience. The scientific relation between the white dots and the later observed problems was empirically correctly observed and derived. But there was an unexpected catch: the screens progressed to higher resolution showing little white dots as a result of the moving heart. This hypothesis fitted well to the empirical observation that a percentage of pictures of white dots increased substantially after the advanced screens were observed. Unaware of the modifications, medical staff performed unnecessary many demanding tests. Worldwide, the number was counted in thousands or even tens of thousands. No medal was delivered to the AI researcher observing a small, but important glimpse in the infant screening procedure except for himself not exposing his son to the unnecessary risk. However, the observation quickly spread all over the world. 
Time for some superficial and some substantial critical observations. In terms of conference organization, several issues improved compared to the last one. For example, the banquet at the Central Park Zoo was quite a nice picnic and not the usual pig-style mess or boring stationary dinners. And New York is still a city that never slips with its charm included. Still, the food was from time to time nearly cold and there were no IJCAI shirts as traditional at other locations. 
Since the author of this editorial last visited NY and Twin Towers around 20 years ago, comparing memories and the current situation was quite interesting. Most observable, people have become much more tolerant in the traffic and among each other. It felt kind of European, kind of warm and nice. On the other hand, the NYC progress is not nearly comparable to the progress of Shanghai, Dubai or even Moscow. Something is essentially wrong with the developed countries that is causing the stalling. Human top countries would better redefine themselves sooner than later. 
In summary: While turning attention to the fantastic technical AI progress is no doubt a reasonable orientation, distancing from predicting the future seems strange, in particular in the land of the free and brave. Nevertheless, AI is changing our everyday life and future at a pace unbelievable even for AI experts. 
Acknowledgement: 
I would like to sincerely thank IJCAI 2016 Conference 
Chair Dr. Gearhard Brewka for reading this editorial and 
providing valuable remarks. 





Statistic-Based Dynamic Complexity Measurement for Web Service System 
Chengying Mao School of Software and Communication Engineering Jiangxi University of Finance and Economics, 330013 Nanchang, China E-mail: maochy@yeah.net 
Keywords: web services, QoS, variability, execution trace, entropy 
Received: January 25, 2016 
The existing research mainly concerns on the static complexity measurement for service-based system, but the dynamic features like execution behavior have been ignored. In this paper, we proposed a hierarchical measurement framework for evaluating the complexity of Web services from the dynamic aspect. At the level of single service, .uctuation rate is used to represent the QoS (Quality of Service) change during service invocation. Then, a cumulative distribution function is used to measure the dynamic complexity of service performance. At the system level, execution vectors and the corresponding probabilities can be counted according to the trace set of system dynamic executions. Subsequently, the complexity of dynamic execution behaviors can be calculated by the usage of entropy value. In addition, the rationality of above metrics has been validated by the studies on two real applications. 
Povzetek: Predlagan je hierarhi ˇcnih spletnih storitev. 
cni okvir za evalvacijo kompleksnosti dinamiˇ
1 Introduction 
In recent years, Web services have been widely utilized for building distributed system over Internet. Different from the traditional software paradigm, the rapid and on-demand service composition in SOA (Service-Oriented Architec­ture) cause a series of problems on the analysis, design and maintenance of service system. Since some quantitative information like the complexity metric is bene.cial to the software engineering activities, such as project cost estima­tion, system testing, and fault repairing, it is necessary to well understand the structure and behavior of service-based software system. However, These service systems usually run in the dynamic, heterogeneous and changeable envi­ronment. As a result, how to measure the complexities of them is a brand-new and challenge problem. 
Almost all existing methods are concerned with system’s static complexity. They used the models like BPEL (busi­ness process execution language) [1, 2], Petri-Net [3] or their variants to describe system logic. Subsequently, the complexities of basic structure units in the business process of service system are de.ned as atomic metrics. Based on them, the structure complexity of whole service system is calculated according to the aggregation mode among the service units in composition logic. Although the execu­tion probability of each branch is considered, the probabil­ity obtained by counting historical data is still a relatively static value. Therefore, the dynamic features of service system, such as the replacement of service at run-time and the business logic changes in service system evolution, are hard to be depicted by the existing complexity measure­ment framework. For this reason, we will mainly focus on the complexity of service system from the perspective of dynamic behaviors of service or system running. 
In this paper, we proposed a framework to measure the dynamic complexity at both single service level and service composition level. For a single service, its dynamic fea­ture is principally re.ected by the quality variation along with execution time. While considering the whole ser­vice system, its dynamic behavior mainly lies in invoca­tion sequence of services at each time of system execution. Based on the above consideration, our framework investi­gates the dynamic complexity of Web services in follow­ing two aspects: For a single Web service, QoS (quality of service [4]) records are collected in the run-time environ­ments .rstly, and then the uncertainty of QoS performance is measured by statistical analysis. At the service com­position level, the execution traces of Web service system are the important information for measuring the dynamic complexity. First, the traces of system dynamic execution are collected by a monitor, which can be implemented by aspect-oriented technology [5, 6]. Then, the records are converted into vectors in accordance with the occurrence of each service. Subsequently, the complexity computation method is provided based on the above execution vectors and Shannon entropy theory. Finally, the feasibility and ef­fectiveness of above two kinds of metrics are validated by two real applications. 
The main contributions of this paper can be addressed as follows. 
(1) 
Take the variation of QoS as the dynamic feature of ser­vice unit, we propose a statistical metric for depicting the .uctuation of QoS records of a single Web service. 

(2) 
Through collecting the execution traces of service sys­tem, the diversi.cation of system execution behaviors 


is measured by the entropy of execution vectors. 

(3) Studies on two examples and two real applications are performed to validate the effectiveness of our presented measurements. 
The structure of the paper is as follows. In the next sec­tion, some existing complexity researches on Web services that are closely related with our presented approach are stated. In section 3, the dynamic complexity of Web ser­vices is de.ned and discussed. The method for measuring dynamic complexity of a single service is addressed in sec­tion 4. Section 5 gives the measurement of dynamic com­plexity for service composition. Meanwhile, sections 4 and 5 utilize an example to demonstrate the usage of the pro­posed methods, respectively. Further, the proposed mea­surements are validated by two real applications in section 
6. Finally, section 7 concludes the paper. 

2 	Related work 
How to understand and measure the complexity of Web ser­vices has received much attention in recent years. For a single Web service, some existing object-oriented metrics have been adopted for measuring the complexity of service interface [7]. In the aspect of application, some tools like WSDAudit [8] have been developed for measuring service interface .les. These metrics perform the complexity anal­ysis from the perspective of service code, so they can only evaluate the complexity of a service for outside calling. Al­though they can guide users to design the service invocation code, it can not re.ect the dynamic behaviors of Web ser­vices. 
Besides the consideration of static architecture complex­ity [9], the studies on the complexity of business process in service system have also been investigated [10]. Espe­cially, Jorge Cardoso [1, 11] has done some very in.uen­tial work in this direction. Similar to other related studies [12, 13, 14], Cardoso’s work mainly concerns on the struc­tural complexity of service system. First, the complexities of basic structure units are de.ned. Then, system com­plexity is calculated according to the aggregation mode of these service units. In addition, cohesion/coupling metrics [15, 16] and cognitive weights [17] are also used for mea­suring the process complexity of service system. However, all above methods are mainly concerned with system com­plexity in static aspect. That is to say, all above methods have a basic assumption that the composition architecture of Web services is unchanged during the system execution. 
Jung et al. [18] presented an entropy-based method to measure the uncertainty of process models. Although they have considered the execution probability of each branch, the probability obtained by counting historical data is still a relative static value, so it is dif.cult to evaluate the dynamic complexity in a speci.c execution context. In addition, the computation for the complex processes is quite com­plicated. Recently, Martin Ibl and Jan ˇ
Capek use stochastic Petri nets (SPN) to model the business processes [19]. They map all reachable marking of SPN into the continuous-time Markov chain and then calculating its stationary probabili­ties, the uncertainty of a process model is then measured as the entropy of the Markov chain. Like Jung et al.’s work, theirs approach highly depends on the .xed architecture of service system, and only analyze the static pro.le of possi­ble state. These pro.les are not the real behaviors produced at run-time. Therefore, they are still belongs to the static complexity model indeed. 

In the past few years, the dynamic complexity measure­ments for object-oriented design and software have been extensively studied [20, 21]. However, the existing work mainly concerns on the coupling between classes, objects and methods. That is to say, the dynamic feature is re.ected by the interactions between objects. Since loose-coupling and distributed are two notable characters of service sys­tem, the information coupling between services is not very worth taking into consideration while analyzing the com­plexity of service system at runtime. In our solution, the diversity (uncertainty) of execution traces is viewed as an indicator of dynamic complexity of service system. Re­cently, Lavazza et al. [22] evaluated quality attributes of Web services through analyzing the speci.cations in form of XML .les. Although their quality attributes include dy­namic indicators like coupling, most of them are extended from the traditional static complexity metrics such as LOC or McCabe cyclomatic complexity. 

3 	Dynamic complexity of web services 
The complexity analysis and measurement of software sys­tem have been studied over four decades. At the early stage, the related researches mainly focus on the static properties of a software system, that is so-called static com­plexity. Although the static metrics can quantify the com­plexity of design or source code of a given application, they are still insuf.cient in evaluating the dynamic behaviour of the application at runtime [23]. Accordingly, dynamic soft­ware metrics gradually become a growing research topic in the .led of software measurement [24], especially for object-oriented software [25]. 
As stated previously, the static complexity of service system has been investigated from various aspects such as control dependency or data dependency. However, the dy­namic complexity for this new emerging software system has not been fully exploited yet. Referring to the de.ni­tions of dynamic software measures in [22, 26], here we de.ne the dynamic complexity of a Web service system as the diversity of its execution behaviors in dynamic environ­ment. 
De.nition 1. The dynamic complexity of Web services (a single service or whole service system) can be de.ned as the variability (or uncertainty) of execution behaviors. That is to say, the less change of execution records means the lower complexity in dynamic aspect. 
In the previous de.nitions about dynamic complexity, such as Lavazza et al.’s work [22, 26], they mainly extend the concepts of static metrics to quantify dynamic features of execution traces or speci.cations represented by XML. In their theoretical framework, the dynamic software met­rics are still re.ected by some basic and axiomatic issues such as size, McCabe complexity, coupling, cohesion and so on. However, when we measure the diversity of execu­tion behaviours of Web services, the statistical indicators (e.g., entropy) rather than static metric-like issues are in­troduced here. 
With regard to a single Web service, the dynamic fea­tures are mainly re.ected by its runtime performance, that is quality of service (QoS). In order to measure the vari­ability of service performance, QoS records should be col­lected between the same time gap. Then, these records are used for volatility analysis so as to scale the dynamic com­plexity of service unit. In the paper, the distribution of .uc­tuation rate and its cumulative function are used to measure the uncertainty of Web service’s performance. 
For service-based system, it is easy to see that the dy­namic complexity involves not only system’s static struc­ture but also the run-time scenarios including input data, execution environment and observed results. As a result, in order to precisely measure the dynamic complexity of service system, the execution traces and system behaviors should be recorded .rstly. Then, the entropy of execution vector partitions is referred as an indicator of dynamic com­plexity . 
According to the above de.nition, the dynamic complex­ity in this paper mainly re.ects the performance uncertainty of single service or the diversity of service system execu­tion behaviours. For a single service, service requesters can use the dynamic complexity metric to make scienti.c decision on service selection. In the application scenario of service selection, it needs to choose the most satis.ed one from the functional equivalence set of services. From the perspective of performance stability, services with the lower dynamic complexity should be recommended as the preferred candidates. For the whole service system, the results of dynamic complexity are bene.cial for software developers and maintainers to understand the evolution of service system or to perform rational system refactoring. 

4 	Dynamic complexity for a single service 
4.1 Measurement method 
For a Web service, its QoS generally includes the following issues [4]: response time, throughout, availability, reliabil­ity, etc. For the sake of simplicity, we take response time as an example to illustrate our method here. 
De.nition 2. For the QoS record set of a given service, its .uctuation rate at time slot ti can be calculated as: 

ri = |qi - Qi,.|/Qi,. (1) 

where qi is the QoS value of the time slot ti, Qi,. is the mean value at the backward .-step fragment w.r.t. qi, i.e., 
Qi,. = (qi-. + qi-.+1 + · · · + qi-1)/. (2) 

In particular, Qi,. = qi-1 if . = 1. 
It is not hard to .nd that, ri re.ects the amplitude of QoS change at the current time slot ti. In literature [27], Wang et al. adopt the difference between qi and the mean of set {qi} to represent the uncertainty of service performance. However, this mode may fail to express dynamic complex­ity when the QoS mean values of two services have a big gap. In order to overcome this problem, we adopt the dif­ference between service’s current QoS to the mean of the latest consecutive QoSs to describe the .uctuation of ser­vice performance. 
Here, suppose a sequence of .uctuation rates R= (r1, r2, · · · , rn) has been calculated by continuous moni­toring on a given Web service. In order to measure the dy­namic complexity of service performance, the distribution of .uctuation rates should be counted. Given k partition­ing points C=(c1, c2, · · · , ck), the cumulative partitioning probability pj(1 . j . k) can be computed according to formula (3). Here, c1 < c2 < · · · < ck. 
|R(cj)|
pj = , R(cj) = {ri|ri . cj, 1 . i . n} (3) 
n 

where |R(cj)| represents the cardinality of set R(cj). Ob­viously, R(cj ) . R, 0 . pj . 1. 
Accordingly, the dynamic complexity DCqos of a single service can be expressed as follows. 
p1 + p2 + · · · + pk
DCqos = 1 - 	(4)
k 

The meaning of the above dynamic complexity can be intuitively explained in the way of graphical representa­tion. As shown in Fig.1, X-coord. represents the units from 1 to 5 (i.e., the ordinal number j in formula (3)), Y­coord. represents the corresponding cumulative partition­ing probability pj. The proportion of the grey area relative to the whole 5×1 rectangular area approximately equals to (p1 + p2 + · · · + pk)/k, so the proportion of the remaining white part is DCqos . It is easy to see that, the more low-amplitude .uctuation rate means the lower dynamic com­plexity. For the two services in Fig. 1, DCqos of service 1 is obviously lower than that of service 2. 

4.2 Example One 
To validate the rationality of our proposed metric for a sin­gle service’s dynamic performance, response times of two Web services in a continuous period have been gathered here. All 31 records for each service are illustrated in Fig. 
2. 


Figure 2: Response times of two sample Web services. 

Here, we set . to 1, so the .uctuation rate is calculated by |qi - qi-1|/qi-1. Based on the above 31 records, 30 rates can be collected for each service, i.e. n = 30. In this example, 9 partitioning points are utilized for dividing the .uctuation rates, i.e. C = (0.01, 0.02, 0.05, 0.1, 0.2, 0.5, 1, 2, 5). Then, the partitioning probabilities of two services (i.e., ws1 and ws2 in Fig. 2) can be calculated according to formula (3). For the .rst service, {pj}ws1 = (0, 0.2, 0.57, 0.73, 0.9, 0.9, 0.97, 1.0, 1.0). For the second one, {pj}ws2 = (0, 0.07, 0.1, 0.3, 0.47, 0.7, 0.9, 0.9, 1.0). Therefore, the dynamic complexities of two services are DCqos (ws1) = 0.3037 and DCqos (ws2) = 0.5074, respectively. 
From the view of instinctive experience, ws2’s change is more frequent and violent than that of ws1 in Fig. 2. According to the results in this case, the above dynamic complexity metric can exactly re.ects the dynamic variety of two different services’ performance. 


5 	Dynamic complexity for service composition 
5.1 Modeling and measurement 
When measuring the behaviors of a whole system, exe­cution records (a.k.a. traces) are the important source of information for consideration. Based on our previous re­search [28], the concept of execution trace can be de.ned as below. 
De.nition 3. The execution trace of Web service system can be de.ned as 2-tuple et = ({ws}+, f s), where {ws}+ = < wsi, wsj , . . . , wsk > is the ordered sequence of ser­vice executions (i, j and k are the service ordinal numbers in whole service set), f s is the .nal result (or state) of exe­cution sequence {ws}+ . 
Generally speaking, f s is one of the following three states: success (S), wrong result (W ) and failure (F , or exception). Take the service system shown in Fig. 3 as an example, an execution of the system may be (< ws1, ws2, ws3, ws5, ws2, ws4, ws5, ws7 >, W ). 

Figure 3: An example Web service system W S 1. 

De.nition 4. Given a service system contains m service units, the execution vector of the system can be denoted as a vector with length m + 1, i.e. ev = ({ws}m, f s). Here, {ws}m is an occurrence list from service 1 to service m. 
Obviously, any execution trace et can be converted into an execution vector ev. (1) If wsj (1 . j . m) doesn’t exist in et, the j-th value in ev (i.e. ev[j]) is 0. (2) If wsj appears only once in et, ev[j]=1. (3) If wsj appears more than one time in et, ev[j]=2. Thus, ev[j] . {0, 1, 2}. For the last element of ev, ev[m + 1] . {S, W, F }. 
For the trace related with Fig. 3, the corresponding ex­ecution vector can be expressed as (1, 2, 1, 1, 2, 0, 1, W ). Here, the j-th (1 . j . m) number represents the oc­currence frequency of wsj in the given execution trace. According to the above de.nition, the frequency number could only be the following three choices: 0, 1 or 2. 
De.nition 5. The execution partition of a Web service system is a map structure ep = (ev, prob), where ev is an execution vector of that system, and prob is the probability of occurrence of ev in the set of system execution traces. 
In Fig. 3, the diamond frame represents the branch struc­ture. For the sample service system (denoted as W S1), the execution partitions in a possible scenario can be gathered and listed in Table 1. In this execution scenario, six exe­cution partitions can run successfully. For the remaining two, service system will produce the wrong result in one case, and system will throw an exception in the other case. For each execution partition, the corresponding probabil­ity can be counted through collecting the traces during the dynamic execution of system. 
For a Web service system, once the execution traces have been collected and the execution partition have been counted, the complexity indicating system’s dynamic exe­cution behaviors can be measured from the perspective of information theory. 
Table 1: One possible execution partition set for the service system W S 1. 
No. ws1 ws2 ws3 ws4 ws5 ws6 ws7 f s prob 

ep1  1  1  1  0  1  0  1  S  0.1  
ep2  1  2  2  0  2  0  1  S  0.15  
ep3  1  1  0  1  1  0  1  S  0.15  
ep4  1  2  0  2  2  0  1  F  0.1  
ep5  1  2  1  1  2  0  1  W  0.1  
ep6  1  2  2  1  2  0  1  S  0.1  
ep7  1  2  1  2  2  0  1  S  0.15  
ep8  1  0  0  0  0  0  1  S  0.15  

Suppose the execution partition set of a service system is E P = {epi}, where epi = (evi, probi), then the dynamic complexity of system execution can be calculated as below. 
|.EP | DCexe = - probi · log2 probi (5) 
i=1 

where |E P | is the cardinality of set EP . Obviously, 0 . DCexe . 1, the larger value of DCexe means more com­plex execution behaviors of a given Web service system. 
For the execution traces (ET ) of service system W S 1, its DCexe metric can be computed according to the execution partitions shown in Table 1, that is, DCexe(E TW S 1) = -4 × 0.1 × log2 0.1 - 4 × 0.15 × log2 0.15 = 2.9710. 

5.2 Example Two 
In order to validate our entropy-based metric for system dynamic execution behaviors, the following two cases are studied here. 
(1) Study on different execution traces. Here, suppose service system W S 1 runs in another context, so a new exe­cution trace set E T . of system W S1 can be collected. In a similar way, the execution partitions of this kind of execu­tion can also be counted in Table 2. In the current scenario, system behaviors do not exhibit as much diversity as to the execution illustrated in Table 1. Intuitively, the dynamic complexity in the latter execution scenario (i.e., E T .) must be lower than that in the former scenario (i.e., E T ). 
For the second execution trace set ET . , its dynamic complexity can also be calculated according to the occur­rence probabilities and formula (5). 
DCexe(E T . ) = -3 × 0.1 × log2 0.1 - 2 × 0.2 ×
W S 1 

log2 0.2 - 0.3 × log2 0.3 = 2.4464. 
According to the above results, relation DCexe(E T . ) < DCexe(E TW S1) is workable. It
W S 1 

is not hard to .nd that, the metric computed by our method is in very good agreement with the human cognitive. 
(2) Study on different service systems. In order to demon­strate the distinguishability of our measurement method for different service systems, we performed the analysis on the other system shown in Fig. 4. In this .gure, symbol ‘.’ represents the parallel execution relation, and the diamond symbol is still for the choice relation. Since the execution relation after service ws2 is a parallel structure, the execu­tion behaviors of system W S 2 are much simpler than those of W S 1 according to the common sense. 

Figure 4: The other example Web service system W S 2. 

Here, suppose the possible traces and the corresponding partitions are shown in Table 3. Since the relation between ws3 and ws4 is parallel, ws2, ws3, ws4 and ws5 must ap­pear at the same time. Meanwhile, there is a loop from ws2 to ws5, so the occurrence frequencies of services between them should be 1 or 2 in a consistent manner. 
For the above traces of system W S 2, i.e. E TW S2, its dynamic complexity can also be calculated here. Through comparing the metrics of W S 1 and W S 2, it is clear that our proposed metrics can precisely re.ect the actual situa­tions. 
DCexe(E TW S2) = -2 × 0.3 × log2 0.3 - 0.4 × log2 0.4 = 1.5710. 


6 	Empirical study on real applications 
Although the above two examples have demonstrated the feasibility of our proposed methods for measuring the dy­namic complexity of Web services, they are not from the scenarios of real applications. Thus, it is necessary to val­idate our methods on the cases from the real and public benchmarks. 
6.1 Study on service’s performance 
In this section, the following research question should be identi.ed so as to con.rm the effectiveness of our proposed 
Table 2: The other possible execution partition set for system W S 1. 
No. ws1 ws2 ws3 ws4 ws5 ws6 ws7 f s prob 

ep1  1  1  1  0  1  0  1  S  0.1  
ep2  1  2  2  0  2  0  1  S  0.2  
ep3  1  1  0  1  1  0  1  S  0.1  
ep4  1  2  0  2  2  0  1  F  0.1  
ep5  1  2  1  1  2  0  1  W  0.2  
ep6  1  0  0  0  0  0  1  S  0.3  

Table 3: The possible execution partitions for system W S 2. 
No.  ws1  ws2  ws3  ws4  ws5  ws6  ws7  f s  prob  
ep1  1  1  1  1  1  0  1  W  0.3  
ep2  1  2  2  2  2  0  1  S  0.4  
ep3  1  0  0  0  0  0  1  S  0.3  

measurements. 
RQ1: Can the dynamic complexity measurement for sin­gle Web service precisely depict the .uctuation of QoS per­formance? 
To answer the above question, the public QoS records of Web services are introduced in our experimental analysis. WS-DREAM1 is a set of QoS datasets which are collected from real-world Web services by Zheng et al. [29]. Here, the third subset is used in this study. It contains the real-world QoS evaluation results from 142 users on 4532 Web services on 64 different time slots. For the limit of space, we did not investigate the time-aware QoS records of all users for all services. As similar in [30], the records of user #9 for services #741 and #745 are used as benchmarks in the experiments. The QoS records at 64 different time slots of these two services are illustrated in Fig. 5, where sub-.gure 5(a) is for service #741 and sub-.gure 5(b) is for service #745. Through intuitively comparing the stability of QoSs (i.e. response times here) of two services, it is easy to see that service #745 is obviously complex than service #741 from perspective of performance. 
According to Equation (1), the .uctuation rate vectors of the above two services can be calculated. Since the length of time slots is 64, the length of each .uctuation rate vector should be 63. In this case study, we also set the step-length (.) in Equation (1) as 1, that is to say, the .uctuation rates of the considered two services are computed by means of |qi - qi-1|/qi-1 (1 . i . 63). Based on the above cal­culation, the sequence of .uctuation of services #741 and #745 can be expressed as (0.0035, 0.0035, 0.0534, 0.1486, 0.5119, · · · ) and (6.0030, 0.8602, 5.4185, 0.0273, 0.3612, · · · ), respectively. 
Since the .uctuation rate of service #745 will exceed .ve, the number of partitioning points which are used to divide the .uctuation rates is assigned with 10. Ac­cordingly, the set of partitioning points is designed as C=(0.01,0.02, 0.05, 0.1, 0.2, 0.5, 1, 2, 5, 10). Based on this partitioning, the cumulative partitioning probabil­ities of these two services can be calculated respectively, that is, {pj}#741=(0.0476, 0.0794, 0.1905, 0.3810, 0.5238, 0.8571, 0.9683, 0.9683, 1.0, 1.0) and {pj }#745=(0.0794, 0.0952, 0.2063, 0.4127, 0.5079, 0.5873, 0.7937, 0.9048, 0.9524, 1.0). Further, the dynamic complexities of them can be achieved by applying Equation (4), i.e., DCqos (#741)=0.3984 and DCqos (#745)=0.4460. Ac­cording to the above measurement results, service #741 is more complex than service #745 with respect to QoS per­formance. The relation between these two services is con­sistent with the intuitive judgement. 
Through the validation on real QoS dataset named WS­DREAM, we can conform that the proposed metric for dy­namic complexity of a single service is feasible and ratio­nal. 

6.2 	Study on execution behaviours of service system 
Similarly, we also should investigate the research question on the effect of dynamic complexity measurement for Web service system. 
RQ2: Can the dynamic complexity based on execution vector and Shannon entropy scienti.cally measure the di­versi.cation of system execution behaviors? 
Here, a subject application LoanDemo from the sam­ples of Oracle BPEL Process Manager [31, 32] is adopted for experimental analysis. The business logic of this ser­vice system is described by BPEL, and the main pro­cess is depicted by the .le LoanFlow.bpel as shown in the code listing 1 of reference [32]. In the main pro­cess, UnitedLoanService and StarLoanService are two composite services whose execution can be further decomposed by a BPEL .le. Here, for the sake of simpli­.cation, we only further describe the work.ow process of service StarLoanService by BPEL code (refers to the code listing 2 in [32]). 
1http://www.wsdream.com/dataset.html 	The process of whole service system is depicted in Fig. 


(b) user #9 for services #745 
Figure 5: The time period QoS feature of response time. 

6(a), in which the oval node represents basic service unit, the black strip stands for the parallel logical node and the diamond box is for the branch logic. It should be noted that, the work.ow process includes both external services and basic execution activities, here treat both of them as the basic service units. Compared with the original version (see Fig. 6(a)) of system logic, the updated system (refer to Fig. 6(b)) considers the activity about exception handling and the different treatment for VIP customers. Therefore, two new services (i.e., S13 and S14) are added into the work.ow process of the updated system. 
In order to compare the dynamic complexities between the original and updated service systems, we .rstly collect (or simulate) the execution traces of each service system separately, and then apply the metric de.ned in Section 5.1 to measure the complexity of each trace set. Here, we set the number (N) of execution traces as 20, and collect the same size of traces for both service systems. In this case study, we assume each service in LoanDemo system can execute successfully, that is, the .nal results of all execu­tion traces are S (success). 
According to the de.nition 5, the above collected traces of each service system can be formed as execution par­titions. The corresponding partitions of original and up­dated service systems are shown in Tables 4 and 5, re­spectively. When the size of trace set (N) is equal to 20, the partitioning number (|E P |) is 2 for the original sys­tem, and is 7 for the updated system. Based on the results in Tables 4 and 5, we can further calculated the dynamic complexities in the light of Equation (5). For the origi­nal service system, its complexity DCexe(E Toriginal ) = -0.55 × log2 0.55 - 0.45 × log2 0.45 = 0.9928. Simi­larly, for the updated system, the corresponding complexity DCexe(E Tupdated) = 2.5016. Thus, we can say that the updated service system is more complex than the original one from the perspective of dynamic execution behaviors. It it not hard to .nd that the conclusion is consistent with the subjective judgement. 
The above comparison is only performed on a case of execution trace set. It should be noted that, given a num­ber of trace set size, the collected trace sets may have some minor variance. For this reason, we repeat the above analysis 100 times and obtain the entropy distri­bution of each system version. As shown in Fig. 7(a), the mean of dynamic complexity for the original sys­tem is 0.9721, and the corresponding value of the up­dated system is 2.4125. Since the complexity of the orig­inal system (DCexe(E Toriginal )) is always less than or equal to 1.0, and the complexity of the updated system (DCexe(E Tupdated)) is always higher than 1.5, the rela­tion DCexe(E Toriginal ) < DCexe(E Tupdated) is always kept regardless of experiment trials. 
While revisiting the updated service system, we .nd that the number of possible execution paths is eight in Fig. 6(b), however the partitioning number (|E P |) in Table 5 is only seven. That is to say, the collected execution traces are not suf.cient to cover all possi­ble execution scenarios. Due to this reason, we re­peat the experiments for the case of N=50. In this setting of trace set size, the dynamic complexities of these two system versions are DCexe(E Toriginal )=0.9857 and DCexe(ETupdated)=2.5790. Obviously, the relation DCexe(E Toriginal ) < DCexe(ETupdated) can still be kept here. Through comparing Figs. 6(a) with 6(b), we can .nd that the distribution of dynamic complexity will be more stable with the increase of trace set size. Take the updated service system as an example, the distribution box of updated system’s complexity in Fig. 6(b) is obviously shorter than that in Fig. 6(a). That is to say, the complexity result in case of N=50 is more credible than that in case of N=20. However, the relation between the complexities of two system versions usually will not be affected by the size of execution trace set. On the other hand, the larger trace set means greater effort on trace collection and complex­ity computation. Therefore, we suggest to adopt a medium scale to set the size number (N) of trace set. 
Based on the above observations, we can conclude that the measurement based on execution vector and Shannon entropy is suitable to measure the dynamic complexity of Web service system. 

(a) The original process (b) The updated process Figure 6: The business process of Web service system LoanDemo. 


7 Conclusion 
Although some studies on the evaluation of process com­plexity in service system have been investigated, the met­rics for understanding the dynamic complexity of system behaviors are still very lack. In this paper, a two-level mea­surement framework for assessing the dynamic variability of Web services has been presented. At service level, the uncertainty of service QoS is measured by continuous mon­itoring and .uctuation rate statistic. At system level, the ex­ecution traces are classi.ed into vectors, then the entropy of vector probabilities is calculated as the complexity indi­cator of system execution behaviors. Finally, the effective­ness of the proposed metrics has been evaluated by two real applications. 


Acknowledgments 
We are grateful to Changfu Xu for collecting the partial experimental results in this paper. This work was sup­ported in part by the National Natural Science Foundation of China (NSFC) under Grant No. 61462030, the Natu­ral Science Foundation of Jiangxi Province under Grant No. 20151BAB207018, the Science Foundation of Jiangxi Educational Committee under Grant No. GJJ150465, and the Program for Outstanding Young Academic Talent in Jiangxi University of Finance and Economics. 

References 
[1] J. Cardoso. Complexity Analysis of BPEL Web Pro­cesses, Software Process: Improvement and Practice, vol. 12, no. 1, 2007, pp. 35-49. 
[2] R. M. Parizi and A. A. A. Ghani. An Ensemble of Complexity Metrics for BPEL Web Processes. Proc. of the 9th ACIS International Conference on Software Engineering, Arti.cial Intelligence, Networking, and Parallel/Distributed Computing (SNPD’08), Phuket, Thailand, August 6-8, 2008, pp. 753-758. 
[3] C. Mao. Complexity Analysis for Petri Net-based Business Process in Web Service Composition, Proc. 

Table 4: The execution partitions for the service system shown in Fig. 6(a), N=20. 
No. S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S11 S12 f s prob 

ep1 1 1 1 1 1 1 1 1 1 1 0 1 S 0.55 ep2 1 1 1 1 1 1 1 1 1 1 1 0 S 0.45 
Table 5: The execution partitions for the service system shown in Fig. 6(b), N=20. 
No.  S1  S2  S3  S4  S5  S6  S7  S8  S9  S10  S11  S12  S13  S14  f s  prob  
ep1  1  1  1  1  1  1  1  1  1  1  0  1  0  0  S  0.35  
ep2  1  1  1  1  1  1  1  1  1  0  1  1  0  0  S  0.1  
ep3  1  1  1  1  1  1  1  0  1  1  0  1  0  1  S  0.15  
ep4  1  1  1  1  1  1  1  0  1  0  1  1  0  1  S  0.2  
ep5  1  1  1  0  1  1  1  1  1  1  0  1  1  0  S  0.05  
ep6  1  1  1  0  1  1  1  0  1  1  0  1  1  1  S  0.1  
ep7  1  1  1  0  1  1  1  0  1  0  1  1  1  1  S  0.05  

of the 5th IEEE Intl Symp. on Service-Oriented Sys­tem Engineering (SOSE’10), Nanjing, China, June 4­5, 2010, pp.193-196. 
[4] D. A. Menasce. QoS Issues in Web Services, IEEE Internet Computing, vol. 6, no. 6, 2002, pp. 72-75. 
[5] M. Sun, B. Li, and P. Zhang. Monitoring BPEL-based Web Service Composition using AOP, Proc. of the 8th IEEE/ACIS International Conference on Computer and Information Science (ACIS-ICIS’09), Shanghai, China, June 1-3, 2009, pp. 1172-1177. 
[6] C. Mao. AOP-based 	Testability Improvement for Component-based Software. Proc. of the 31st Annual International Computer Software and Applications Conference (COMPSAC’07), Vol. II, Beijing, China, July 24-27, 2007, pp.547-552. 
[7] J. L. O. Coscia, M. Crasso, and et al. Estimating Web Service Interface Complexity and Quality through Conventional Object-Oriented Metrics, Proc. of the XV Iberoamerican Conference on Software Engineer­ing (CIbSE’12), Buenos Aires, Argentina, April 24­27, 2012, pp. 154-167. 
[8] H. M. Sneed. Measuring Web Service Interfaces, 
Proc. of the 12th IEEE International Symposium on Web Systems Evolution (WSE’10), Timisoara, September 17-18, 2010, pp. 111-115. 
[9] J. Zhao. Complexity Metrics for Software Architec­ture, IEICE Trans. Inf. & Syst., vol. E87-D, no. 8, 2004, pp. 2151-2156. 

[10] L. S. González, F. G. Rubio, and et al. Measurement in Business Processes: A Systematic Review, Busi­ness Process Management Journal, vol. 16, no. 1, 2010, pp. 114-134. 
[11] J. Cardoso. Business Process Control-.ow Complex­ity: Metric, Evaluation, and Validation, Int. J. Web Service Research, vol. 5, no. 2, 2008, pp. 49-76. 
[12] K. B. Lassen and W. M. P. Aalst. Complexity Metrics for Work.ow Nets, Information and Software Tech­nology, vol. 51, 2009, pp. 610-626. 
[13] C. Mao. Control and Data Complexity Metrics for Web Service Compositions, Proc. of the 10th Inter­national Conference on Quality Software (QSIC’10), Zhangjiajie, China, July 14-15, 2010, pp. 349-352. 
[14] A. Khoshkbarforoushha, P. Jamshidi, and et al. Met­rics for BPEL Process Context-independency Anal­ysis, Service-Oriented Computing and Applications, vol. 5, no. 3, 2011, pp. 139-157. 
[15] I. T. P. Vanderfeesten, H. A. Reijers, and W. M. P. Aalst. Evaluating Work.ow Process Designs using Cohesion and Coupling Metrics, Computers in Indus­try, vol. 59, no. 5, 2008, pp. 420-437. 
[16] A. Kazemi, A. N. Azizkandi, and et al. Measuring the Conceptual Coupling of Services using Latent Semantic Indexing, Proc. of IEEE 8th International Conference on Services Computing (SCC’11), Wash­ington DC, USA, July 4-9, 2011, pp. 504-511. 
[17] R. 	Laue and V. Gruhn. Complexity Metrics for Business Process Models, Pro. of the 9th Interna­tional Conference on Business Information Systems (BIS’06), Klagenfurt, Austria, May 31 -June 2, 2006, pp. 1-12. 
[18] J.-Y. Jung, C.-H. Chin, and J. Cardoso. An Entropy-based Uncertainty Measure of Process Models, Infor­mation Processing Letters, vol. 111, 2011, pp. 135­
141. 

[19] M. Ibl and J. ˇCapek. Measure of Uncertainty in Pro­cess Models using Stochastic Petri Nets and Shannon Entropy, Entropy, 2016, vol. 18, no. 33, pp. 1-14. 
[20] S. Yacoub, H. Ammar, T. Robinson. Dynamic Metrics for Object-Oriented Designs. Proc. of the 5th Inter­


(b) The entropy distribution when N=50 

Figure 7: The entropy distributions of two service systems (repeated trials = 100). 
national Software Metrics Symposium, Boca Raton, USA, November 4-6, 1999, pp.50-61. 

[21] E. Arisholm, L. C. Briand, A. Foyen. Dynamic Cou­pling Measures for Object-Oriented Software. IEEE Transactions on Software Engineering, 2004, vol. 30, no. 8, pp. 491-506. 
[22] L. Lavazza, S. Morasca, and D. Tosi. Enriching Spec­i.cations to Represent Quality in Web Services in a Comprehensive Way, Proc. of the 9th IEEE Interna­tional Symposium on Service-Oriented System Engi­neering (SOSE’15), Redwood City, CA, USA, March 30-April 3, 2015, pp. 203-208. 
[23] J. K. Chhabra and V. Gupta. A Survey of Dynamic Software Metrics, Journal of Computer Science and Technology, 2010, vol. 25, no. 5, pp. 1016-1029. 
[24] A. Tahir and S. G. MacDonell. A Systematic Map­ping Study on Dynamic Metrics and Software Qual­ity, Proc. of the 28th IEEE International Conference on Software Maintenance (ICSM’12), Riva del Garda, Trento, Italy, September 23-30, 2012, pp. 326-335. 
[25] A. Gosain and G. Sharma. Dynamic Software Metrics for Object Oriented Software: A Review, Advances 
in Intelligent Systems and Computing, vol. 340, 2015, pp. 579-589. 

[26] L. Lavazza, S. Morasca, and et al. On the De.nition of Dynamic Software Measures, Proc. of the 6th In­ternational ACM Symposium on Empirical Software Engineering and Measurement (ESEM’12), Lund, Sweden, September 19C20, 2012, pp. 39-48. 
[27] S. Wang, Z. Zheng, and et al. Reliable Web Service Selection via QoS Uncertainty Computing, Int. J. Web and Grid Services, vol. 7, no. 4, 2011, pp. 410-426. 
[28] C. Mao, I. Tervonen, and J. Chen. Diagnosing Web Services System Based on Execution Traces Pattern Analysis, Proc. of the 8th IEEE International Confer­ence on e-Business Engineering (ICEBE’11), Beijing, China, October 19-21, 2011, pp. 117-122. 
[29] Y. 	Zhang, Z. Zheng, and M. R. Lyu. WSPred: A Time-Aware Personalized QoS Prediction Framework for Web Services, Proc. of the 22th IEEE Symposium on Software Reliability Engineering (ISSRE’11), Hi­roshima, Japan, November 29 -December 2, 2011, pp. 210-219. 
[30] H. Ma, Z. Hu, and et al. Toward Trustworthy Cloud Service Selection: A Time-aware Approach using In­terval Neutrosophic Set, Journal of Parallel and Dis­tributed Computing, vol. 96, 2016, pp. 75-94. 
[31] Oracle Corporation. Oracle BPEL Process Manager, available at http://www.oracle.com/ technology/prod­ucts/ias/bpel/index.html, accessed in June 2016. 
[32] C. Mao. Static Inter-BPEL Program Slicing for Web Services, Int. J. Simulation and Process Modelling, vol. 7, no. 3, 2012, pp. 204-216. 

Appendix 
The business processes of two composite services are shown in the following two code listings. The code is written in BPEL (Business Process Execution Lan­guage) which is published by OASIS standard organiza­tion to specify actions within business processes with Web services. The process of the whole service application (LoanDemo) is shown in the Listing 1, and the process of subsystem StarLoanService is described by Listing 2. The code except shadow lines represents the original busi­ness logic, and the shadow part means the modi.ed code in the updated version of system. 
The two process graphs in Fig. 6 are the corresponding logic representations of the original BPEL code and up­dated code, respectively. It should be pointed out that, be­sides the external service units, the actions of task execu­tion in BPEL code are also treated as atomic service nodes in Fig. 6. At the same time, the updated code segments are represented by the oval red nodes in process graph. 
Listing 1: The BPEL code of LoanDemo application. 
<process name="LoanFlow" ...> 

<partnerLinks> 
<--Include client, creditRatingService, UnitedLoanService and StarLoanService --> 
... 

</partnerLinks> 
<variables> 
<variable name="input" .../> 
<variable name="crInput" .../> 
<variable name="crOutput" .../> 
<variable name="crError" .../> 
<variable name="loanApplication" .../> 
<variable name="loanOffer1" .../> 
<variable name="loanOffer2" .../> 
<variable name="selectedLoanOffer" .../> 

</variables> 

<sequence> <receive name="receiveInput" partnerLink="client" portType="tns:LoanFlow" operation="initiate" variable="input" createInstance="yes"/> <scope name="GetCreditRating"> <--Watch for faults (exceptions) being thrown from creditRatingService --> <faultHandlers> <catch faultName="services:NegativeCredit" faultVariable = "crError"> <assign> <copy> <from expression="number(-1000)"/> <to variable="input" part="creditRating"/> </copy> </assign> </catch> </faultHandlers> 
<sequence> <assign> <copy> <from variable="input" part="SSN"/> <to variable="crInput" part="SSN"/> </ 
copy> 
</assign> 
<invoke name="invokeCR" partnerLink="creditRatingService" portType="services: 

CreditRatingService" operation="process" inputVariable="crInput" outputVariable=" crOutput"/> <assign> <copy> <from variable="crOutput" part="rating"/> <to variable="input" part=" creditRating"/> </copy> </assign> </sequence> </scope> 
<scope name="GetLoanOffer"> 

<sequence> <assign> <copy> <from variable="input"> <to variable="loanApplication"/> </copy> </assign> <flow> 
<sequence> <invoke name="invokeUnitedLoan" partnerLink="UnitedLoanService" portType="services: LoanService" operation="initiate" inputVariable="loanApplication"/> <receive name="receive_invokeUnitedLoan" partnerLink="UnitedLoanService" portType=" 
services:LoanServiceCallback" operation="onResult" variable="loanOffer1"/> 
</sequence> 
<sequence> 

<invoke name="invokeStarLoan" partnerLink="StarLoanService" portType="services:LoanService " operation="initiate" inputVariable="loanApplication"/> <receive name="receive_invokeStarLoan" partnerLink="StarLoanService" portType="services: LoanServiceCallback" operation="onResult" variable="loanOffer2"/> </sequence> 
</flow> </sequence> </scope> 

<scope name="SelectOffer" variableAccessSerializable="no"> <switch> <--If loanOffer1 is greater (worse) than loanOffer2 --> <case condition="bpws:getVariableData(’loanOffer1’,’APR’) > bpws:getVariableData(’loanOffer2 ’,’APR’)"> <assign> <copy> <from variable="loanOffer2" part="APR/> <to variable="selectedLoanOffer" part="APR"/> </copy> </assign> 
</case> <otherwise> <assign> <copy> <from variable="loanOffer1" part="APR"/> <to variable="selectedLoanOffer" part="APR"/> </copy> </assign> 
</otherwise> 
</switch> 
</scope> 


<invoke name="replyOutput" partnerLink="client" portType="tns:LoanFlowCallback" operation=" onResult" inputVariable="selectedLoanOffer"/> </sequence> </process> 
Listing 2: The BPEL code of service StarLoanService. 
<process name="StarLoanService" ... 
<partnerLinks> 
<partnerLink name="LoanFlow" .../> 
<partnerLink name="IDCheckService" .../> 

</partnerLinks> 
<variables> 
<variable name="loanApp" .../> 
<varaible name="sNumber" .../> 
<varaible name="crdRate" .../> 
<variable name="apRate" .../> 
<variable name="loanOffer" .../> 

</variables> 

<sequence> <receive name="receive_loanApplication" partnerLink="LoanFlow" portType="services:LoanService" operation="initiate" variable="loanApp" createInstance="yes"/> <assign><copy><from variable="loanApp" part="SSN"/> <to variable="sNumber"/></copy> 
<copy><from variable="loanApp" part="creditRating"/> <to variable="crdRate"/> </copy> </assign> <invoke name="invokeIDCheck" partnerLink="idCheckService" portType="services:IDCheckService" 
operation="idCheck" inputVariable="sNumber" outputVariable="idStatus"/> 
</sequence> 

<sequence> 

<if> <condition idStatus = "vip" crdRate="high"/> <assign> <copy> <from expression="number(0.0015)"/> <to variable="apRate"/></copy> </assign> 
<else> 

<assign> <copy> <from expression="number(0.002)"/> <to variable="apRate"/></copy> </assign> 
</if> 
<assign><copy><from variable="apRate"/> <to variable="loanOffer" part="APR"/></copy> 
</assign> 

<invoke name="replyLoanService" partnerLink="LoanFlow" portType="services:LoanServiceCallback" operation="onResult" inputVariable="loanOffer"/> </sequence> </process> 

Adaptive Coherence-enhancing Diffusion Flow for Color Images 
V. B. Surya Prasath Computational Imaging and VisAnalysis (CIVA) Lab, Department of Computer Science University of Missouri-Columbia, USA E-mail: prasaths@missouri.edu 
Keywords: coherence, structure tensor, anisotropic diffusion, image restoration 
Received: July 7, 2016 
Color image restoration is one of the fundamental problems in image processing pipelines. Variational reg­ularization and diffusion partial differential equations (PDEs) are widely used in solving these low-level image smoothing and noise removal problems. In this paper, we consider a new adaptive coherence en­hancing diffusion (CED) .lter which combines anisotropic diffusion and structure tensor derived diffusion functions. By exploiting isotropic smoothing in homogeneous regions and anisotropic diffusion tensor .ltering in edges and corners we obtain a PDE .ow which can removing noise while preserving impor­tant image details. Compared to the original CED approach our proposed adaptive CED (ACED) obtains stable smoothing results. Experimental results on synthetic and real color images show that the proposed .lter has good noise removal properties and quantitative measurements indicate it obtains better structure preservation as well. 
Povzetek: Predlagan je nov algoritem za obnavljanje barv slik. 
1 	Introduction 
Image restoration is an important low-level image process­ing which is still an active area of research in computer sci­ence. Among a wide variety of image noise removal meth­ods two important classes of techniques are variational reg­ularization and partial differential equation (PDE) based .l­ters [1]. Perona and Malik [2] proposed an anisotropic dif­fusion .ltering based on a nonlinear PDE for image denois­ing and edge detection. Though the Perona-Malik (PM) PDE obtained edge preserving restorations under noise, it is known to create blocky artifacts in homogenous (.at re­gions where the pixel values do not vary much) regions in the resultant images. 
Various modi.cations and adaptations of PM PDE in particular and other PDEs in general have been proposed in the last two decades. One of the important class of im­proved PDE based .lter is due to Weickert who provided a uni.ed theory of anisotropic diffusion [4]. The structure tensor provided better orientation estimation and edge dis­crimination for steering the diffusion process away from image discontinuities and to make smoothing strong in ho­mogenous regions. Weickert [5] proposed an elegant for­mulation which handles coherence enhancement for color images with tuning the eigenvalues of the structure tensor in a controlled manner. Structure tensors provide a geo­metric analysis of digital images via eigenvalues and vec­tors and there have been applications in edge detection and image denoising literature. 
In this work, we base our new PDE based .ltering ap­proach on Weickert’s coherence-enhancing diffusion [5] with an adaptive choice of diffusion functions for better edge and corner preservation while smoothing out random noise. For this, we utilize structure tensor eigenvalues for controlling anisotropic smoothing according to geomet­ric content of the images. This adaptive choice facilitates isotropic diffusion in homogenous regions and anisotropic diffusion near sharp edges, corners. Our proposed .lter is robust to noise and we conduct detailed experimental re­sults on noisy synthetic and real images to prove the effec­tiveness. Comparison results with related .lters show that we obtain better restoration results visually as well as based on peak signal to noise ratio and structure similarity. 
We conduct experimental results on synthetic and vari­ous corrupted real color test images and test our method against some related .lters from the literature. Our exper­iments show that both visually and quantitatively our pro­posed adaptive approach obtained better restoration results. 

2 	Adaptive coherence enhancing diffusion 
2.1 Preliminaries 
We start with the basic assumptions and notations of coherence-enhancing diffusion .ltering framework. Let u0 : . . R2 › R be the input (possibly noisy) grayscale image. Weickert [4] provided a uni.ed tensor diffusion for­mulation which is given by the following parabolic nonlin­

(a) Input (b) CED [5] (c) Proposed ACED 
Figure 1: Comparison of noise-free synthetic Square color image .ltering with coherence-enhancing diffusion .ows at the same terminal time T = 25. (a) Inupt image, and (b) Original Weickert’s CED [5] (Eqn. (1) with (7)), and our proposed ACED (Eqn. (1) with (8)). In (b) and (c) on the left we show the residue |u(x, T ) - u0| which are enhanced for better visualization. Our proposed method obtains stable salient edges of the central square and other texture regions are grouped well. 
ear PDE, For vectorial images the common structure tensor is given 
. .
. .
. 

by,
.u(x, t) 
= div (D(J.(\u.))\u) , x . .,.t (1)
u(x, 0) = u0(x), x . .,

N
N
i
J.(\u.) = w i J.(\u.), (6) u(x, t) = 0, x . ... 
i=1 

The resultant sequence of images {u(·, t)}T , for a .nite
t=0 

time T represents a nonlinear scale space. Here the diffu­sion tensor D is dependent on the image information via the structure tensor J.(\u.). Structure tensors encode local image information with .rst order directional derivatives and is given by, 
 N 
i i

with= 1, and w> 0 are the averaging factors.
i=1 w

Interpretation of this tensor for vectorial images in terms of eigenvalues and eigenvectors carries over from grayscale case, see [5] for more details. A simple choice is to chose 
i

w= 1/N for all i = 1, . . . , N representing all channels have similar meaning, range and reliability. We restrict our­selves here to color images (RGB, N=3), and the formula­
J.(\u.) G. * (u.)2 G. * (u.)x(u.)y
x
=(2) 
  

tion holds true for multispectral imagery as well. 
Weickert [5] proposed the following particular choices
G. * (u.)x(u.)y G. * (u.)2 
y

for steering smoothing for coherence enhancement diffu­where [(u.)x, (u.)y]T (XT denotes the transpose of vec­sion (CED),tor/matrix X) is the gradient of u. (pre-smoothed image 
u. = G. * u), G. = (2..2)-1 exp (- |x|2 /2.2) is the Gaussian kernel and * denotes the convolution operation. Let the eigenvalues and eigenvectors of the structure tensor be (.+, .-), and (v+, v-) respectively. Weickert’s uni.ed 
 
. = .-,
. + (1 - .) exp (- ) if .+ 
(.+-.-)2 
f+ =
., else, 
f- = .. (7) 

tensor diffusion formulation is given by, 
T T
D = f+(.+, .-)v+v + f-(.+, .-)v-v-, (3)
+ 

where where f+, f- are the diffusivities perpendicular and parallel to structure orientations. The eigenvectors of the structure tensor J. matrix can be calculated as, 
.± 

 
 
 
with . > 0 is known as the coherence factor (if the co­herence is inferior to . the .ux is increasing with the co­herence while if the coherence is larger then . the .ux de­creases as the coherence grows), . > 0 a small parameter added to keep the tensor diffusion matrix D in Eqn. (3) pos­itive de.nite. Note that (.+-.-)2 measures the coherence within a window of scale .. This particular choice obtained 
1 

good diffusion results when the structures are oriented in 
trace2(J.) + 4det(J.). (4)
= trace(J.) ±

one particular direction, however can smooth out corners
2

and other singularities as multiple directional informationFor vector valued (multichannel) images u : . . R2 › is lost, see Figure 1.
RN 1 2
with u = (u, u, . . . , uN ) channels the PDE (1) can be written using a common diffusion tensor, 
. .
. 
.ui(x, t)

 
 
i
= divD(J.(\u.))\u, x . ., 


2.2 Adaptive coherence-enhancing diffusion 

.t 
(5)
x . .,
u(x, 0) = u0(x), 

In this work, to control the .ltering better and to preserve
.
. 
u(x, t) = 0, x . ... image singularities better we chose the following adaptive 





(b) ACED .ow at T = 10, 100, 300 
Figure 2: Comparison of coherence-enhancing diffusion .ows at the same terminal times for S tarryN ight painting by van Gogh (Saint-Rémy, 1889, The Museum of Modern Art, New York, USA) color image. Top row: original Weickert’s CED [5] (Eqn. (5) with (7)). Bottom row: Our proposed ACED (Eqn. (5) with (8)) at terminal iterations T = 10, 100, 300. Note the different effect of .ows on long level lines. 
diffusivities, 
.2 
+
f+ = exp - 
ß1 
.2 .2 
+ -
f- = 1 - exp - exp - (8)
ß1 ß2 

With this choice of diffusivities we observe the following salient points: 
. 
If either of the eigenvalues .+ or .- is high the dif­fusion is now in the direction of v+ or v-, which in turn means at corners (where .± is high) anisotropic diffusion is applied. 

. 
Original CED formulation’s diffusion oriented in the direction of v+ is kept intact and the diffusivity f- is now incorporates orientation direction v- (coherence orientation). 

. 
The parameters ß1, ß2 control the diffusivities along v+, v-. 

. 
In homogeneous (.at regions where the pixel values do not vary) areas the diffusion is still isotropic. 



The diffusion PDE in Eqn. (5) where the diffusion matrix in Eqn. (3) given with this diffusivities (8) obtains adap­tive coherence enhancing diffusion (ACED) for smoothing color images with salient edges, corners better preserved as we will see in the experimental results next. 


3 Experimental results 
3.1 Setup and parameters 
The PDE based .lters (CED) are implemented using the implicit .nite differences method with coherence parame­ter . = 5 × 10-4 , . = 0.01 (to keep D positive de.nite), pre-smoothing Gaussian standard deviations . = 4, . = 1, and step size .t = 0.24. The new parameters in our ACED ß1 = 20, and ß = 20 are set in all the experiments reported here. 

3.2 Comparison results 
Figure 1 shows a comparison of Weickert’s original CED [5] (Eqn. (1) with (7)), and our proposed adaptive im­provement ACED (Eqn. (1) with (8)) at the same terminal time T = 25. We show the residue |u(x, T ) - u0| to high­light the amount of noise removed in both these methods. As can be seen, our proposed ACED preserves the cen­tral square’s edges through the diffusion .ow and smaller texture regions are grouped better than the original CED Table 1: Mean structural similarity (MSSIM) metric values for results of various schemes with noise level .n = 30 for standard test color images from USC-SIPI Miscellaneous dataset (size † = 256 × 256 and ‡ = 512 × 512). MSSIM value closer to one indicates the higher quality of the de-noised image. The top result in each color test image is indicated by boldface. 
Image  CED [5]  Ours  
Baboon‡  0.6047  0.6087  
Barbara‡  0.7129  0.7964  
Boat†  0.6786  0.7013  
Car‡  0.7214  0.7853  
Couple†  0.7016  0.7020  
F-16†  0.8699  0.8898  
Girl1†  0.7081  0.7174  
Girl2†  0.8210  0.8522  
Girl3†  0.8020  0.8309  
House†  0.7024  0.7812  
IPI†  0.8335  0.8929  
IPIC†  0.7899  0.8125  
Lena‡  0.7581  0.7824  
Peppers‡  0.7737  0.8026  
Splash‡  0.7938  0.8136  
Tiffany‡  0.7633  0.8107  
Tree†  0.7099  0.7325  



Image  CED [5]  Ours  
Baboon‡  20.48  20.53  
Barbara‡  24.59  25.94  
Boat‡  25.21  24.98  
Car‡  26.01  25.83  
Couple†  27.18  26.97  
F-16†  24.56  26.50  
Girl1†  26.66  27.21  
Girl2†  29.34  28.05  
Girl3†  29.92  29.68  
House†  28.95  28.39  
IPI†  30.38  29.32  
IPIC†  29.05  28.64  
Lena‡  28.56  27.89  
Peppers‡  28.61  28.03  
Splash‡  31.65  31.18  
Tiffany‡  29.67  28.99  
Tree†  25.73  25.10  


Table 2: PSNR (dB) values for results of various schemes with noise level .n = 20 for standard images of size 
† = 256 × 256 (Noisy PSNR = 22.11) and ‡ = 512 × 512 (Noisy PSNR = 22.09). Higher PSNR value indicate bet­ter denoising result. The top result in each color test image is indicated by boldface. 
(a) Noise-free 


(b) Noisy 

Figure 3: Comparison of (a) noise-free smoothing and 
(b) noisy Baboon color image .ltering with coherence-enhancing diffusion (CED) .ows at the same terminal time T = 25. Left column -original Weickert’s CED [5] (Eqn. (1) with (7)), right column -Our pro­posed ACED (Eqn. (1) with (8)). Restored image, and residue |u(x, T ) - u0| (enhanced for better visualization) are shown in each case. Our proposed method obtains bet­ter noise removal and salient edges are preserved well. Bet­ter viewed online and zoomed-in. 
formulation. 
To show visually the qualitative differences of the .ows we utilize the S tarryN ight, a painting by van Gogh 

(a) Day 

(b) Night 
Figure 4: We obtain interesting non-realistic photo realistic results with our proposed ACED. We show two examples (a) 

daylight, and (b) night lights. Better viewed online. 
(Saint-Rémy, 1889, Courtesy of The Museum of Modern Art, NY, USA) color image of size 606 × 480. Figure 2 shows CED and our proposed ACED at iterations T = 10, 100, and 300. As can be seen, we obtain two different be­haviors with respect to the coherency of long level lines. CED obtains a long .owing structures whereas our ACED obtains long lines interspersed with small .owing lines in­side big structures. This property shows that our adaptive choice of diffusivities (8) helps the .ow retain corners and singularities better than the original (7). 
Next in Figure 3 we compare CED .ows on noise-free and noisy (additive Gaussian noise of standard de­viation .n = 30 added in all three channels indepen­dently) Baboon color image of size 512 × 512. Figure 3(a) shows comparison on noise-free image and the correspond­ing CED, proposed ACED results at the iteration T = 25. Our proposed ACED obtains better coherency as can be seen by mouth and surrounding whiskers. A similar visual analysis shows in noisy case, Figure 3(b), indicate we ob­tain better noise removal while maintaining all the salient edges and thin linear structures. These are further corrob­orated by the corresponding residue images showing how much of structure and random noise are removed. 

We note that for a fair comparison to the original CED formulation we kept all the parameters in our proposed ACED the same including the terminal time T of the cor­responding PDE .ows. The convergence result for the dis­cretized versions, as iterations increases t › ., of both CED and proposed ACED are the same and we defer the discussion of deeper theoretical results of the correspond­ing nonlinear PDEs for future. 
To quantitatively compare the noise removal and struc­ture preservation we use two standard error metrics utilized widely in the image processing literature. Peak signal to noise ratio (PSNR) is given by, 
3 × umax
PSNR = 20 * log10 . dB, 
MSE 

where MSE = (mn)-1 (u - uO)2, mean squared er­ror, with uO is the original (noise free) image, m × n de­notes the image size, umax denotes the maximum value, for example in 8-bit images umax = 255. A difference of 
0.5 dB can be identi.ed visually. Mean structural similar­ity (MSSIM) index is in the range [0, 1] and is known to be a better error metric than traditional signal to noise ra­tio. It is the mean value of the structural similarity (SSIM) metric [6]. We use the default parameters for SSIM and the MATLAB code is available online1 . The SSIM is cal­culated between two windows .1 and .2 of common size N × N, and is given by, 
(2µ.1 µ.2 + c1)(2..1.2 + c2)

SSIM(.1, .2) = 	,
(µ2 + µ2 + c1)(.2 + .2 + c2)
.1 .2 .1 .2 

where µ.i the average of .i, .2 the variance of .i, ..1.2
.i 

the covariance, and c1, c2 stabilization parameters. The MSSIM value near 1 implies the optimal denoising capa­bility of a method and we used the default parameters. 
Table 1 and Table 2 show PSNR (dB) and MSSIM val­ues for CED and our proposed ACED methods compared on some standard color test images which are synthetically perturbed by additive Gaussian noise of standard devia­tion .n = 30. Though our proposed ACED is not the top performing method in all the tested images in terms of PSNR, we note that the purpose of adaptive CED is to obtain smoothed images with coherent structures in tact. Further, PSNR is known to be not the right metric in evalu­ating the performance of denoising methods and MSSIM is more apt. We remark that the optimal stopping time T > 0 for denoising is determined based on best possible MSSIM value in these synthetically noise added cases. 
Finally, we show in Figure 4 some smoothing results from mobile phone imagery (12 mega-pixel). Figure 4(a) shows a picture taken in day-light conditions with no .ash and our proposed ACED obtains .ow like small structures while keeping the bigger regions intact. A similar result is observed in Figure 4(b) where a night time image is cap­tured with an in-built .ash. The smoothing property of our .ow provides visually pleasing results in both cases. 
1https://ece.uwaterloo.ca/ z70wang/research/ssim/ 



4 Conclusions 
In this work, we considered a new PDE based .lter for color image coherence enhancing smoothing and noise re­moval. By a combination of anisotropic diffusion with structure tensor driven adaptive functions, our method ob­tains edge preserving smoothing results which result in bet­ter noise removal capabilities. Experimental results on a variety of noisy images indicate the potential of our pro­posed approach and compared with other original coher­ence enhancing diffusion .lter we obtained better restora­tion results as well. One of our important future work is in extending the proposed method by incorporating other adaptive diffusive regularizers and to handle mixed noise removal [3] and consider multispectral imagery [7]. 


References 
[1] G. Aubert 	and P. Kornprobst (2006) Mathematical problems in image processing: Partial differential equation and calculus of variations, Springer-Verlag. 
[2] P. Perona and J. Malik (1990) Scale-space and edge de­tection using anisotropic diffusion, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 12, No. 7, pp. 629–639. 
[3] D. N. H. Thanh, S. D. Dvoenko, D. V. Sang (2016) A mixed noise removal method based on total variation, Informatica, Vol. 40, pp. 159–167. 
[4] J. Weickert (1998) Anisotropic diffusion in image pro­cessing. B.G. Teubner-Verlag, Stuttgart, Germany. 
[5] J. Weickert (1999) Coherence-enhancing diffusion of colour images, Image and Vision Computing, pp. 201– 
212. 

[6] Z. Wang, A. C. Bovik, H. R. Sheikh, E. P. Simoncelli (2004) Image quality assessment: from error visibil­ity to structural similarity. IEEE Transactions on Image Processing, Vol. 13, No. 4, pp. 600–612. 
[7] V. B. S. Prasath and A. Singh, Multispectral image de-noising by wellposed anistropic diffusion with chan­nel coupling, Inter. J. Remote Sens, Vol. 31, No. 8, pp. 2091–2099, 2010. 

Rough-Mereology Framework for Making Medical Treatment Decisions Based on Granular Computing 
Mohammed M. Eissa Information Systems Department, Faculty of Business Administration and Information Systems French University in Egypt, Cairo, Egypt E-mail: Mohammed.mamdouh@gmail.com 
Mohammed Elmogy Information Technology Dept., Faculty of Computers and Information, Mansoura University, Mansoura, Egypt E-mail: elmogy@gmail.com 
Mohamed Hashem Information Systems Dept., Faculty of Computers and Information, Ain Shams University, Cairo, Egypt E-mail: mhashem100@yahoo.com 
Keywords: rough – mereology, granular reflection, rough inclusion, hepatitis C virus (HCV), coronary heart disease (CHD) 
Received: August 19, 2015 

The medical field is considered as one of the most significant research resources. It receives a significant interest from researchers in the field of informatics and medical experts. It has a tremendous amount of data on various diseases and their symptoms that causes difficulty in diagnosing diseases. Therefore, several medical approaches based on knowledge discovery in the database have been proposed and developed. They include data mining techniques for cleaning, filtering, dimension reduction, and induction of rules. In this paper, a Rough-Mereology framework is proposed for classification of Hepatitis C Virus (HCV) and Coronary Heart Disease (CHD) medical datasets. The proposed system uses granular reflection mechanism based on rough inclusion to generate sets of granules at different radiuses. It selects the optimum radius based on accuracy to induce a set of rules that help medical experts to take Therapeutic Medical Decisions. During the experiments, the Rough based granular computing supplies a complimentary and comprehensive framework for the analysis of medical datasets. 
Povzetek: Prispevek uvaja novo metodo strojnega učenja na dveh domenah: hepatitis in srce. 
Introduction 
Because of the vast amount of medical data in different forms, the medical field has become one of the richest areas of scientific research and informatics. It can improve medical decisions, reduce costs, and provide finest therapeutic service for patients. Therefore, several medical approaches based on knowledge discovery in the database have been proposed and developed. 
In this section, we focus on two of the most currently common diseases in the world. They are Coronary Heart Disease (CHD) and Hepatitis C virus (HCV). CHD is one of most common disease in our modern life. It is the hardening of the vessels by greasy stores called plaque. The heart must get oxygen and supplements to functioning efficiently. Blood conveys the oxygen and supplements to the heart through arteries. As the plaque composed of the walls of the arteries, blood flow is decreased [1], [2], [3]. 
The second common disease is the HCV, which is a most popular liver disease. HCV currently infects millions of people in different countries. It results in intense illness, which is regularly turned into a deadly disease. It can prompt liver failure and liver cancer that leads to death. Infected blood that is transmitted between people is considered as the main reason for HCV infection [4]. 

Despite the significant progress in the medical field, the large number of medical indicators of both CHD and HCV make finding relationships between those indicators a difficult task. Consequently, the techniques of knowledge discovery in databases (KDD) are widely developed to determine relationships between medical indicators. It can predict the factors that affect treatment decisions using the historical cases, which are stored in medical datasets. 
The organization of the rest of this paper will be as follows. In Section 2, overviews of the Rough-Mereology and Granular Computing frameworks are described. Section 3 discusses some current related work. The proposed framework is demonstrated in Section 4. Description of medical datasets, framework analysis, and experimental results are presented in Section 5. Research conclusion and future work are shown in Section 6. 
2 	Rough-mereology based granular computing: a brief overview 
The information granularity concept, which is used in many areas, is proposed by Zadeh [5]. Most of the researchers characterized the main concepts of the granular computing from distinctive perspectives. Like an umbrella, Granular Computing covers themes in different fields even if they are considered disconnected. Granular Computing includes three main topics. These topics are Rough sets theory (RST) that is proposed by Pawlak [6], the theory of fuzzy sets that is introduced by Zadeh [7], and quotient space hypothesis that is presented by L. Zhang and B. Zhang [8]. One of the essential benefits of RST is its powerful data analysis and immediate application in classification. The main principals of RST will be discussed in the next subsections. 
2.1 Knowledge representation 
Granulation of a universe involves dividing the universe into subsets or grouping individual objects into a set of clusters. A granule is a subset of the universe. A family of granules that contains every object in the universe is called a granulation of the Universe. Let " is a non-empty finite set of objects, !! is a non-empty set of attributes, is a language defined using attributes in !!, #. is a non-empty set of values for . . !!. and . is an information function. Then, the information table can be formulated as follows [9]: 
K5 M !! D " . . !!# "A . . !! ! 1! 
On the other hand, a generalized approximation space can be defined as ! . ". . .!. where is the uncertainty function on " with values in the power set ... "!. which is the neighborhood of .) and . is the inclusion function defined on the ......... ....... ... .! . ... .! with values [0,1] measuring the degree of inclusion of sets [10]. 
The 	lower approximation and the upper 
...... ) approximation ...... ! operations can be defined by equations (2) and (3), where . .!. ! represents the Rough similarity relation, as shown in Fig. 1: 
...... . ". . ". . .!. ! . .# .! 
...... . ". . ". . .!. ! . .# .! 


2.2 Rough mereology 
Rough Mereology is proposed by Lesniewski [12] as the theory of concept. The primitive relation of Mereology is a part of the relation. According to Polkowski and Artiemjew [13], the Mereology relation is described in equation (4), where . .. .! is a partial relation (proper part) and ... .. .! is ingredient relation means informally an improper part [14]. 
... .. .! . . .. .! .. . . . .! 
M. M. Eissa et al. 


Figure 1: The definitions of approximations expressed regarding granules of knowledge [11]. 
The relation of the ingredient is a part order of things [14]. . . . .. .! means rough Mereology relation x is part of y at least degree r, also described as shown in equation (5). 
. . !. .! . .... . !. .! . . . !! . . . .! .! 

Rough inclusion relation satisfies the similarity properties of Rough Mereology as mentioned in the next section. 

2.3 Rough inclusion 
The Rough inclusion function is the extension of Rough i............... relation (IND) of traditional RST. However, Rough inclusion is less complexity time than ................ relation in traditional RST. The Rough Inclusion Function . . "!. "! . $...% defines the degree of inclusion of X in Y. It means in Rough Mereology x is part of y at least degree . .. . . . , ... .. .! . . . .. . . .! . . .!. a is an attribute in an information system. Rough inclusion can be represented in terms of indescribability relation as shown in the following equation: 
$ . !! 
. . !. .! .. . . . 	.! 
.... !!! 

There are three types of measures associated with granules. The first measures a single granule that indicates the relative size of the granule. The second measures the relationships among granules. Finally, the third measures the relationships between a granule and a family of granules, as indicated in following equations [15]. 
.. .!.. .!. 
!....... ...... . .! . 	.! 
. .! .. .!.. .!. 
#....... . .! . 	.! 
. .! .. .!.. ..!. 
.. .! . . ... .! . . . . ... .! 
. .! .. .!.. ..!. 
. . .! 
. .! 
The granule g of radius r can be defined as shown in equation (10), where µ is Jough inclusion of n object x ... . . $...%. 
.. . . #..". . . .. .. .!#. ..! 




Related work 
Granular Computing in the framework of RST and its extensions has been widely discussed by many researchers [16], [17], [18], [19], [20], [21], [22], [23], 
[24] and [25]. Rough-Mereology as an extension of RST is used in different knowledge discovery application areas. For example, Zheng and Zhan [26] explored Granular Computing technique based on Rough Mereology for rule generation. This research indicated that Granular Computing could improve the performance of reaching association rule based on approximation spaces. It is applied to a rule-based classifier. However, the model was not extended to handle more classifiers, and it is based on minimum length principle. 
A survey of Rough-Mereology applications in knowledge discovery and intelligent systems is introduced by Polkowski [27]. On the other hand, Polkowski and Artiemjew [28] developed a model using granular reflections in the frame of Rough-Mereology for rules induction and classification. They made a comparative analysis of exhaustive RS classifier whose accuracy is less than their proposed model. 
Many researchers used Granular Computing in the frame of RS and its extension Rough-Mereology for the classification of the medical datasets. For example, RS approach is developed by Zaki et al. [29] to transfer numeric attributes to discrete attributes and to induce HCV rules for classification. Although the approach did not use any reduction algorithm for attribute reduction, the classification accuracy was satisfied. 
Badria et al. [30] proposed a Rough based Granular model by using the fundamental of RS. The model was used to discover attributes dependencies, data transformation, and the dynamic dimension reduction. Then, set of rules induced to make medical decisions. 
Eissa et al. [31] introduced an HCV classifier based on a hybrid Rough genetic model. The model based on RS in the transformation of datasets, dimension reduction, and rule induction. A genetic algorithm is used in filtering and selecting the best rules that are encoded inside chromosomes to increase the accuracy. 
Polkowski and Artiemjew [32] developed a granular classifier for coronary disease. The proposed model concentrated on dealing with missing values in a pre­processing phase, creating new information table and applying the granular classifier to discover absence or presence of coronary disease. 
In this work, Rough-Mereology framework based on Granular Computing model is introduced to classify HCV at some stage in testing a new drug for HCV treatment. In addition, Coronary Artery Disease dataset is 
Informatica 40 (2016) 343–352 345 

used to determine the number of blocked vessels in coronary. Section 4 provides a brief description and analysis of the proposed framework. 
4 	The proposed framework based on rough-mereology model 
Although the great development of technologies of storage, data retrieval, and the vast amount of different forms of medical data, the research in the medical field has become one of the richest areas in informatics. They are made available to the medical research community. Forecasting a disease will remain one of the most defy tasks for researchers to provide prediction models for enhancing treatment decisions [33]. 
The proposed framework uses extended RS based on Granular Computing methodology to identify the most relevant attributes. It induces medical treatment rules from diverse medical datasets. The development processes of the proposed framework demonstrated in Fig. 2. It requires pre-processing of the medical dataset to remove redundancy, inconsistency, and convert continues data to discretized one to be more suitable for processing. In addition, attribute reduction is needed to find the optimum attributes that represent the datasets without losing the value of the data. Whereas, Rough Mereology and Rough inclusion techniques are utilized to clustering the datasets into sets of granules with different radius. They select the granules with optimum radius for inducing sets of medical rules, which are required for treatment decisions. The main steps of the proposed model will be illustrated in the next subsections. 
4.1 The pre-processing phase: 
4.1.1 Construction of information table 
For classification tasks, it is assumed that each object in the information table is associated with a unique class label. Objects can be divided into classes, which form a granulation of the universe. Without loss of generality, we assume that there is a unique attribute class, which takes class labels as its values. The set of attributes is expressed as .. . . . ".....#, where D is the set of attributes that is used to describe the objects, also called the set of conditional attributes. A granule is a definable granule if it is associated with at least one formula, i.e. X5m .! where . . .. The extended upper and lower approximations are calculated based on Rough inclusion after the construction of the medical information table and using Rough inclusion relation to finding the elementary granules. Its essential purpose is to seek for an approximation scheme that can efficiently solve a complex problem. 

Mereology model. 


4.1.2 	Rough sets boolean reasoning discretization 
The objective of discretization is to discover a set of cut points to partition the range into a small number of intervals that have good class coherence. It is usually measured by an evaluation function. In addition to the maximization of interdependence between class labels and attribute values, a perfect discretization technique ought to have an optional objective to speed up learning process and classification accuracy [34]. 
In this paper, the Rough sets Boolean Reasoning (RSBR) is used as a classification based discretization algorithm. It converts the continuous medical attributes into discrete ones. RSBR algorithm is described in Fig. 3, in which (i) define a set of Boolean variables "# "!, then a new decision table !. is created using boolean variables "# "!. defined in the previous step ( !. is called P-discretization of decision table), then searching for a minimal subset of P that discerns all the objects in different decision classes. Finally, we obtain the prime implicants denoted by the discrenibility formula in disjunctive normal form DNF form. The minimal subset of P is chosen to preserve discrenibility [35]. 


Figure 3: The RSBR discretization algorithm. 


4.2 Attribute reduction algorithm 
One of the important phases of the RST is the attribute reduction. In an information system, some attributes may be redundant and useless. If those redundant and useless attributes are removed without influencing the classification, they will be considered as superfluous attributes [36]. 
The core concept is commonly used in all reducts [37]. The attribute reduction concept can improve the performance of the generated rule systems. It accelerates the rule induction process by finding all minimal subsets of attributes. These attributes have the same number of elementary sets without the loss of the classification power of the reduced information system [38]. 
In this phase, discernibility matrix-based algorithm is utilized for reduction of superfluous attributes in medical datasets. Let .. . .. . . .. .. . ! be a decision table. we denote ... matrix called discernibility matrix M such that: 
.. 	.. .! . ... .. 
#.. . 	..! 
". . ! . . .! . . .!#. .. .! . ... .. 

Using discernibility matrix [39], attributes reduction can be constructed as shown in Fig. 4. 



Figure 4: The attribute reduction algorithm. 


4.3 Classification phase 
In this phase, Rough Mereology uses Rough inclusion relation as a similarity technique in the classification of medical datasets. It produces sets of granules at different radiuses that draw the outlines for inducing decision rules. First, Rough Mereology using Rough inclusion to construct Rough inclusion similarity table that describes the similarity of each object in each attribute in the medical datasets. Second, the clustering of the medical datasets into sets of granules with different radius are done by reproducing Rough inclusion table with different granule radius table. It re.ects the degree of similarity between the medical indicators. Finally, the granular reflection of inclusion into the set of granules is applied using voting by training object algorithm to select the most optimized granules by selecting granule radius that achieves the best accuracy. The primary steps in the steps of the classification algorithm are provided in Fig. 5. 


5 	The experimental results and Discussion 

5.1 The description of the medical datasets 
In this paper, the historical medical data are collected from different medical research resources (Badria and Attia [40], Barakat et al. [41] and Amir et al. [42]). In addition, several meetings with medical experts had made to discuss and understand the contents of the medical datasets and to get a clear idea about the diseases. The computations of rules have been only done on the tr ining d t set. Lhe comput tions’ results of the rules were applied to the classification of the granules from the tested dataset. 

Figure 5: The Rough–Mereology classification algorithm. 
Hepatitis C Virus (HCV) Dataset 
These data were gathered from clinical trials at some stages in testing a new drug for HCV, which is recently developed and patented by Badria and Attia in 2007 [40]. It comprised of 119 HCV cases. Each case is portrayed by 28 medical indicators: 23 numerical indicators and 5 categorical indicators. The intention of the dataset is to forecast the presence or absence of the HCV. The attributes description of the HCV exists in Table 1. For each HCV record, patient data out of 27 condition attributes and the decision attribute describe the presence or absence of HCV-related to the proposed medication. All these data were gathered from the treatment of HCV and were divided with the splitting factor of 0.25 into training and test sets. 
Coronary Heart Disease (CHD) Dataset 
CHD dataset was collected from Cardiology Department, Faculty of Medicine, Mansoura University, Egypt. It consists of 215 Coronary patients that included condition attributes like age, sex, family history, smoking, and other medical measures. In addition, it shows the decision label that indicates the number of the vessels that may be injected (no vessel, single, two, and multiple). Most of the attributes are binary attributes and age attribute is the only numerical one, as shown in Table 
2. 
For training and testing purposes, with a splitting factor of 25 %, CHD dataset is divided into training and testing sets [41], [42]. 
ID  Medical Indicators  Indicator Description  
1  Sex  Male or female  
2  Source  Source of HCV: blood transfusion, non-sterile tools by dentist or surgery  
3  S.G.P.T (ALT)  normal 0 to 40 U/L  
4  S.G.O.T (AST)  normal 0 to 45 U/L  
5  Serum Bilirubin (SB)  normal 0 to 1.1 mg/dL  
6  Serum Albumen (SA)  Serum Albumin; 3.5 to 5.1 g/dL  
7  Serum Ferritin  the normal 22 to 300  
8  Ascites  No, Mild, and Ascites  
9  Spleen  Normal, Absent, and Enlarged  
10  Lesions  0,1 or 2  
11  Portal vein ( P.V )  Natural diameter is 12 mm  
12  PCR  Quantitative analysis of the virus U/mL  
13  PLT  Platelets normal 150 to 450 /cm m  
14  WBC  White Blood Corpuscles normal 4 to 11/cm m  
15  HGB Haemoglobin  male 12.5 to 17.5 g/dL female 11.5 to 16.5 g/dL  
16  Headache  Yes or No  
17  Blood Pressure  Yes or No  
18  Nausea  Yes or No  
19  Vertigo  Yes or No  
20  Vomiting  Yes or No  
21  Constipation  Yes or No  
22  Diarrhea  Yes or No  
23  Appetite  Yes or No  
24  Gasp  Yes or No  
25  Fatigue  Yes or No  
26  Skin colour  Yes or No  
27  Eye Colour  Yes or No  
28  Decision  -1 absent, 1 present of HCV  

Table 1: The HCV dataset. 
Table 2: The CHD dataset. 


5.2 Data pre-processing stage 
As shown in Fig. 2, the data pre-processing phase includes constructing the medical information table using Rough inclusion relationship. It generates elementary granules and discretizes of continuous medical attributes. It converts the continuous values of an attribute to a set of intervals. 
In this paper, a supervised discretization algorithm in light of a mix of RS and Boolean Reasoning are utilized. The RSBR combines discretization and classification, which is unlike some of the discretization methods. The RSBR algorithm shows the best results in the classification of the used medical datasets. Tables 3 and 4 illustrate the new HCV and CHD information table after applying the discretization stage. 
Table 3: The discretized HCV dataset. 
ID  Medical Indicators  Indicator Description  
1  Sex  Male or female (0, 1)  
2  Source  Source of HCV : blood (0),dentist(1)or surgery (2)  
3  S.G.P.T (ALT)  >62 AND <62 [0] less  [1] greater  
4  S.G.O.T (AST)  >34 AND<34 [0] less  [1] greater  
5  (SB)Serum Bilirubin  <0.56 AND >0.56 [0] less  [1] greater  
6  (SA)Serum Albumen  Serum Albumin 3.5 to 5.1  
7  Serum Ferritin  >80 AND <80 [0] less  [1] greater  
8  Ascites  No(0), Mild (1), and Ascites (2)  
9  Spleen  Normal (0), Absent(1), and Enlarged (2)  
10  Lesions  0,1 or 2  
11  ( P.V )Portal vein  >13 AND <13, [0] less,[1] greater  
12  WBC  White Blood Corpuscles 4 to 11  
13  PCR  Quantitative analysis of the virus  
14  PLT  >161,<161 [0] less  [1] greater  
15  HGB  >13.1 AND <13.1 [0] less  [1] greater  
16  Headache  0,1  
17  Blood Pressure  0,1  
18  Nausea  0,1  
19  Vertigo  0,1  
20  Vomiting  0,1  
21  Constipation  0,1  
22  Diarrhea  0,1  
23  Appetite  0,1  
24  Gasp  0,1  
25  Fatigue  0,1  
26  Skin color  0,1  
27  Eye Color  0,1  
28  Decision  -1absent,1 present of HCV  

ID  Medical Indicators  Indicator Description  
1  Age  Continuous values between 35 and 62  
2  sex  Male or female  
3  smoking  Yes  or no  
4  diabetes mellitus (Dm)  Yes  or no  
5  Dyslipidemia (dyslipid)  Yes or no  
6  Family history (family_h)  Yes  or no  
7  Left main coronary artery (lmca)  Normal or diseased  
8  Left anterior descending artery (lad)  Normal or diseased  
9  First diagonal artery (d1)  Normal or diseased  
10  Second diagonal artery (d2)  Normal or diseased  
11  Left circumflex artery (lcx)  Normal or diseased  
12  Obtuse marginal artery1 (om1)  Normal or diseased  
13  Obtuse marginal artery2 (om2)  Normal or diseased  
14  Right coronary artery (rca)  Normal or diseased  
15  Posterior descending coronary artery (pda)  Normal or diseased  
16  Decision Label  number of vessels may be injected (no vessel, single, two, and multi)  

ID  Medical Indicators  Indicator Description  
1  Age  [*, 52), [52,59), [59,61) and [61, *)  
2  sex  0,1  
3  smoking  0,1  
4  diabetes mellitus (Dm)  0,1  
5  Dyslipidemia (dyslipid)  0,1  
6  Family history (family_h)  0,1  
7  Left main coronary artery (lmca)  0,1  
8  Left anterior descending artery (lad)  0,1  
9  First diagonal artery (d1)  0,1  
10  Second diagonal artery (d2)  0,1  
11  Left circumflex artery (lcx)  0,1  
12  Obtuse marginal artery1 (om1)  0,1  
13  Obtuse marginal artery2 (om2)  0,1  
14  Right coronary artery (rca)  0,1  
15  Posterior descending coronary artery (pda)  0,1  
16  Decision  number of vessels may be injected (no vessel0, single1, two2, and multiple 3)  


5.3 	Medical datasets attribute reduction stage 
In this stage, reduction algorithm that is based on discernibility matrix is utilized to reduce the number of attributes in medical data, as shown in Fig. 4. It successfully reduced CHD conditional attributes to 7 attributes. In addition, it reduces the HCV medical indicators from 27 to 9 indicators. 


5.4 	Classification of medical datasets stage 
In this stage, Granular Computing in the frame of Rough Mereology formalized the idea of the granular reflection of the medical datasets. First, applying Rough Mereology concept in the frame of Rough inclusion to the medical datasets to induce Rough inclusion similarity table. 
Second, a set of Rough inclusion tables is constructed by re-applying the first step with different radius r in the interval [0, 1] for clustering the datasets into sets of granules with different radius. In CHD dataset, 7 Rough inclusion tables are produced, as shown in Tables 5 and 6. In HCV dataset, 9 Rough inclusion tables are introduced, as shown in Tables 7 and 8. 
After the granular reflection of the medical datasets, it re.ects inclusion t bles into a set of granules. Voting by training object is applied in two steps. First, it computes the accuracy measure for each Rough inclusion table with different radiuses r. Second, it selects the optimum radius with the highest accuracy that represents the optimized granules. 
Results of the accuracy measure for CHD shows that the accuracy measure at r3 is the highest accuracy, which equals to 96.2%, as shown in Tables 5 and 6. For HCV dataset, the granule radius r5 is the optimal granule with accuracy equals to 96.6, as shown in Tables 7 and 8. 
Informatica 40 (2016) 343–352 349 

Samples of decision rules of HCV and CHD are shown 
in Tables 9 and 10, respectively. 
Table 5: The CHD granules accuracy. 

Radius  (rgran)  Accuracy Measure (accg)  
r0=0  90.0  
r1=0.166667  85.7  
r2=0.333333  92.1  
r3=0.5  96.2  
r4=0.666667  93  
r5=0.833333  0  
r6=1  0  


Table 6: The CHD Confusion Matrix radius r3. 
Predicted  
Actual  Single  Two  Multi  no  
Single  12  1  0  0  0.92  
Two  0  10  0  0  1  
Multi  0  0  14  0  1  
no  0  1  0  15  0.94  
1  0.83  1  1  0.96  

Table 7: The HCV granules Accuracy. 
Radius  (rgran)  Accuracy Measure (accg)  
r0 =0  88.9  
r1 =0.111111  74.5  
r2 =0.222222  94.7  
r3 =0.333333  93.6  
r4 =0.444444  95.4  
r5 =0.555556  96.6  
r6 =0.666667  90.2  
r7 =0.777778  0  
r8=0.888889  0  
r9=1  0  

Table 8: The HCV Confusion Matrix radius r5. 
Predicted  
Actual  absent  present  
absent  4  0  1  
present  1  24  0.96  
0.8  1  0.97  


Table 9: A sample of HCV treatment decision rules. 
medical experts to make relationships between varieties of medical indicators. It reduces the ratio of the false positive diagnosis that leads to taking accurate treatment 
HCV Decision Rules  Accuracy  
IF Sex(m) AND S#G#O#T (AST)3([34, *)) AND Ascites 3(no) AND Spleen3(normal) AND HGB 3([13.1, *)) then 1  0.9885  
IF S#G#O#T (AST)3([34, *)) AND Seru Ferritin 3([86, *)) AND Ascites 3(no) AND Spleen3(normal) AND HGB 3([13.1, *)) then 1  0.9754  
IF Sex(m) AND Seru# Bilrubin (SB)3([0.45, *)) AND Seru# Albuin (SA)3([*, 4.2)) AND Ascites 3(no) AND PLT 3([*, 161.000)) then 1  0.9611  
IF Source(blood) AND Portal vien ( P#V ) 9([12, *)) AND PCR9([*, 23)) then 1  0.9601  
IF Sex(m) AND Source(blood) AND Portal vien ( P#V ) 9([12, *)) AND PCR9([*, 23)) then -1  0.9552  


Figure 6: The comparative study of the different classification models. 
The proposed framework is constructed by creating the medical decision table based on Rough-Mereology concepts. It uses Rough Sets Boolean Reasoning algorithm in the discretization of continues medical data sets. It makes attribute reduction using discernibility matrix based reduction algorithm to discover the characteristics insignificant arrangement of qualities to maintain the knowledge. Finally, it induces the medical decision rules from produced set of granules generated using Rough inclusion similarity tables with different radius r in the interval [0, 1]. Then, it computes granular reflection by computing accuracy rate of each similarity tables. It selects the optimal granules with higher accuracy. The most promising rules are discovered and chosen with the highest priority for classification purposes. 
The experimental results showed that the proposed framework can classify multi-valued decision class (CHD dataset) with acceptable classification rate. According to the competitive analysis, the classification accuracy of the proposed model on the other hybrid RS models with Genetic Algorithm and Artificial Neural Network is improved. The proposed model achieves the best case for the accuracy rather than other models. 
Although Rough-Mereology based on Granular Computing model achieve good classification accuracy, the proposed framework will be enhanced for classifying complex information systems. 



References 
[1] 	Truswell, A. S. (2002). Cereal grains and coronary heart disease. European journal of clinical nutrition, 56(1), 1-14. 
[2] 	Marcus, F. I., McKenna, W. J., Sherrill, D., Basso, C., Bauce, B., Bluemke, D. A. & Fontaine, G. (2010). Diagnosis of arrhythmogenic right ventricular cardiomyopathy/dysplasia. European heart journal, ehq025. 
[3] 	Da Silva Gasparotto, G., Gasparotto, L. P. R., da Silva, M. P., Bontorin, M. S., Lissa, M., & de Campos, W. (2012). Cardiovascular risk factors in freshman physical education course: comparison between the sexes. ;onKcienti e K úde 11(3), 406. 
A comparative analysis of the proposed model and other Knowledge Discovery models, such as RS, Back Propagation, and Genetic Algorithm, are conducted. In addition, some hybrid models like Rough Granular-Back­propagation and Rough Genetic are used to evaluate the proposed framework classification power and its impact related to the size of training datasets. Table 11 and Fig. 6 show the comparison between the classification accuracy of the different tested models based on HCV and CHD datasets. 
Table 10: A sample of CHD treatment decision Rules. 

CAD Decision Rules  Accuracy  
IF age([46, 48)) AND sex(female) AND dyslipid(yes) then0  0.91  
IF age([56, 59)) AND sex(female) AND dyslipid(yes)  then 2  0.96  
IF age([54, 56)) AND sex(female) AND dyslipid(no) then 1  0.89  
IF age([38, 42)) AND sex(female) AND dyslipid(no) then 3  0.92  
IF age([59, 61)) AND sex(female) then 2  0.9730  

Table 11: The classification accuracy of different models based on HCV and CHD datasets. 

Classification Model  HCV  CAD  
Rough Set  95.5  92  
Back-Propagation (Neural Network)  93  95.6  
Genetic-Algorithm  92.1  93.7  
Hybrid Rough-Genetic  95  95.1  
Rough Granular Back-Propagation  94.8  94.4  
Rough -Mereology based on Granular Computing  96.6  96.2  


Conclusions 
Rough-Mereology theory is an extension of the RST that replaces the indescribability relation with similarity relation Rough inclusion relation. Rough-Mereology is dedicated to the concept of granular computing in constructing elementary information granules. It finds the relationships between information granules and building granules network. 
In this paper, new Rough-Mereology based on Granular Computing model is introduced. It helps 
[4] 	Wasik, S., Jackowiak, P., Krawczyk, J. B., Kedziora, P., Formanowicz, P., Figlerowicz, M., & :ł żewicz B. 2010!. Low rds prediction of @; therapy efficiency. Computational and mathematical methods in medicine, 11(2), 185-199. 
[5] 	Zadeh, L. A. (2011). A note on Z-numbers. Information Sciences, 181(14), 2923­2932. 
[6] 	Pawlak, Z. (1982). Rough sets. International Journal of Computer & Information Sciences, 11(5), 341-356. 
[7] 	Zadeh, L. A. (1996). Fuzzy logic= computing with words. IEEE transactions on fuzzy systems, 4(2), 103-111. 
[8] 	Ling, Z., & Bo, Z. (2003). Theory of fuzzy quotient space (methods of fuzzy granular computing). 
[9] 	Livi, L., Rizzi, A., & Sadeghian, A. (2015). Granular modeling and computing approaches for intelligent analysis of non-geometric data. Applied Soft Computing, 27, 567-574. 
[10] Yao, 	Y. Y., & Yao, J. T. (2002, May). Granular computing as a basis for consistent classification problems. In Proceedings of PAKDD (Vol. 2, pp. 101-106). 
[11] Yao, 	Y. (2011). Two semantic issues in a probabilistic rough set model.Fundamenta Informaticae, 108(3-4), 249-265. 
[12] Eissa, M. M., Elmogy, M., & Hashem, M. (2014, December). Rough—Granular neural network model for making treatment decisions of Hepatitis 
C. In Informatics and Systems (INFOS), 2014 9th International Conference on (pp. DEKM-19). IEEE. 
[13] Polkowski, 	L. (2007, June). Granulation of knowledge in decision systems: The approach based on rough inclusions. The method and its applications. In International Conference on Rough Sets and Intelligent Systems Paradigms(pp. 69-79). Springer Berlin Heidelberg. 
[14] Polkowski, L., 	& Artiemjew, P. (2011). Granular computing in the frame of rough mereology. a case study: Classification of data into decision categories by means of granular reflections of data. International journal of intelligent systems, 26(6), 555-571. 
[15] Yager, 	R. R. (2002, October). Using granular objects in multi-source data fusion. In International Conference on Rough Sets and Current Trends in Computing (pp. 324-330). Springer Berlin Heidelberg. 
[16] Yao, 	Y. (2005, July). Perspectives of granular computing. In 2005 IEEE international conference on granular computing (Vol. 1, pp. 85-90). IEEE. 
[17] Yao, 	Y. Y. (2001). Information granulation and rough set approximation.International Journal of Intelligent Systems, 16(1), 87-104. 
[18] Guan, Y. Y., Wang, H. K., Wang, Y., & Yang, F. (2009). Attribute reduction and optimal decision rules acquisition for continuous valued information systems. Information Sciences, 179(17), 2974­2984. 
Informatica 40 (2016) 343–352 351 

[19] Skowron, 	A., & Wasilewski, P. (2011). Toward interactive rough-granular computing. Control and Cybernetics, 40, 213-235. 
[20] Polkowski, L. (2013). Rough Mereology as a Tool for Knowledge Discovery and Reasoning in Intelligent Systems: A Survey. 
[21] Skowron, 	A., Stepaniuk, J., & Swiniarski, R. (2012). Modeling rough granular computing based on approximation spaces. Information Sciences, 184(1), 20-43. 
[22] Qian, 	Y., Liang, J., Wei-zhi, Z. W., & Dang, C. (2011). Information granularity in fuzzy binary GrC model. IEEE Transactions on Fuzzy Systems, 19(2), 253-264. 
[23] Ganivada, 	A., Ray, S. S., & Pal, S. K. (2012). Fuzzy rough granular self-organizing map and fuzzy rough entropy. Theoretical Computer Science, 466, 37-63. 
[24] Lin, T. 	Y., & Louie, E. (2003). Association rules with additional semantics modeled by binary relations. In Rough Set Theory and Granular Computing (pp. 147-156). Springer Berlin Heidelberg. 
[25] Riza, L. S., Janusz, A., Bergmeir, C., Cornelis, C., 
@errer >. Śle <. & :enítez B. E. 2014!. 
Implementing algorithms of rough set theory and fuzzy rough set theory in the R package “roughsets.” Information Sciences, 287, 68-89. 

[26] Zheng, H. Z., Chu, D. H., & Zhan, D. C. 	(2005). Association Rule Algorithm Based on Bitmap and Granular Computing. Artificial Intelligence and Machine Learning (AIML) Journal, 5(3), 51-54. 
[27] Polkowski, L. (2013). Rough Mereology as a Tool for Knowledge Discovery and Reasoning in Intelligent Systems: A Survey. 
[28] Polkowski, L., 	& Artiemjew, P. (2011). Granular computing in the frame of rough mereology. a case study: Classification of data into decision categories 
by  means  of  granular  reflections  of  
data. International  journal  of  intelligent  
systems, 26(6), 555-571.  

[29] 
Zaki, A., Salama, M. A., Hefny, H., & Hassanien, 

A. 
E. (2012, December). Rough sets-based rules generation approach: A hepatitis c virus data sets. In International Conference on Advanced Machine Learning Technologies and Applications (pp. 52­59). Springer Berlin Heidelberg. 



[30] Badria, 	F. A., Eissa, M. M., Elmogy, M., & Hashem, M. (2013, October). Rough Based Granular Computing Approach for Making Treatment Decisions of Hepatitis C. In 23rd International Conference on Computer Theory and Applications ICCTA, Alexandria, Egypt (pp. 29­31). 
[31] 
Eissa, M. M., Elmogy, M., Hashem, M., & Badria, 

F. 
A. (2014, April). Hybrid rough genetic algorithm model for making treatment decisions of hepatitis 

C. 
In Engineering and Technology (ICET), 2014 International Conference on (pp. 1-8). IEEE. 



[32] Polkowski, 	L., & Artiemjew, P. (2007, August). Granular computing: Granular classifiers and 
missing values. In 6th IEEE International 
Conference on Cognitive Informatics (pp. 186-194). 
IEEE. 

[33] Ding, 	S., & Tong, C. (2011). Research and Comparison of Granularity Cluster Analysis Methods. International Journal of Advancements in Computing Technology, Advanced Institute of Convergence Information Technology,3(7), 154­
159. 
[34] 	? rci  K. Duengo B. Káez B. 9. Dopez . & Herrera, F. (2013). A survey of discretization techniques: Taxonomy and empirical analysis in supervised learning. IEEE Transactions on Knowledge and Data Engineering, 25(4), 734-750. 
[35] Ding, S., Chen, J., Xu, X., & Li, J. (2011). Rough neural networks: a review.J Comput Inf Syst, 7(7), 2338-2346. 
[36] Jiang, F., & Sui, Y. (2015). A novel approach for discretization of continuous attributes in rough set theory. Knowledge-Based Systems, 73, 324-334. 
[37] Zhang, D. B., & Wang, Y. N. (2006). Fuzzy-rough neural network and its application to vowel recognition. Control and Decision, 21(2), 221. 
[38] Suguna, 	N., & Thanushkodi, K. G. (2011). An independent rough set approach hybrid with artificial bee colony algorithm for dimensionality reduction. American Journal of Applied Sciences, 8(3), 261. 
[39] Wang, R., Miao, D., & Hu, G. (2006, December). Discernibility matrix based algorithm for reduction of attributes. In Proceedings of the 2006 IEEE/WIC/ACM international conference on Web Intelligence and Intelligent Agent Technology (pp. 477-480). IEEE Computer Society. 
[40] Badria, 	F. A., & Attia, H. A. (2007). Effect of selected natural products, thioproline and Pegasys on hepatic platelet activating factor (paf) In ccl4­induced hepatic fibrosis in rats. Saudi Pharmaceutical Journal, 15(2), 96-104. 
[41] Barakat S. 	I., Eissa M. M., EL-Henawy I.(2009). Hybrid Rough Sets and Probabilistic Flow Graph Model In Coronary Artery Disease. In. Egyptian Computer Science Journal, 33. 
[42] Amir, 	M. Z., Eissa, M. M., & EL-Henawy, I. (2010). Hybrid Rough Sets and Decision Tree Model In Coronary Heart Disease. Zagazig University Medical Journal January. 


Tie Persistence in Academic Social Networks 

Djamila Mohdeb, Adelhak Boubetra and Mourad Charikhi Department of Computer Science, University of Bordj Bou Arreridj, Bordj Bou Arreridj, Algeria E-mail: djamila.mhb@gmail.com, {boubetraabd, mcharikhi}@yahoo.fr 
Keywords: link persistence, link prediction, link strength, social network evolution, academic social network 
Received: May 12, 2016 

This paper attempts to shed light on the importance of some social academic-related factors in determining the strength of links in academic social networks. Our purpose is to assess the extent to which the frequency of the tie, the academic closeness between its actors, and the scientific contributions of the actors in the tie can affect the scientific collaboration relationship between them. We propose a model that relies on this three link strength indicators in order to predict the tie persistence in academic social networks. We experimented the model on a social network extracted from the DBLP computer science bibliographic network. We compared the output of the model with that of the link prediction baseline methods. The results show better performance of the proposed model. 
Povzetek: Prispevek analizira vpliv socialnih povezav v omrežjih na akademski uspeh s pomočjo DBLP. 

Introduction 
The investigation of academic networks is increasingly an important topic in the area of social networks mining. Comprehending these complex networks is important to understand the trends of knowledge production through the world. A typical academic network contains a set of multi-typed entities (scientists, papers, journals, institutions…etc.) linked by a set of multi-typed associations (Figure 1-a). The collaboration network is the mainly used social projection of the scientific academic network. It consists of a set of nodes representing scientists, and a set of links representing collaboration relations between nodes. Frequently, researchers use co-authorship relations to construct collaboration networks as they denote formal cooperation between scientific actors. A collaboration network is composed by connecting every set of authors who share the same publications (Figure 1-b). This type of networks exhibits in general the same characteristics as social 
networks. They are of “small world” type, where the 
clustering coefficient, which describes the transitivity in the network, is high. As a result, the average distance between any two scientists in the network is short, and it does not usually exceed five or six degrees [33]. They are also scale free following a power law in several node properties and their structures are affected by the preferential attachment phenomenon [18, 37]. Studying the evolution and the dynamics of collaboration networks remains a continuing concern in social networks mining since the advances of science depend crucially on this type of interactions between scientists [23]. Studies in this field focus on the analysis of the observed changes in the network structure caused by both the links and the nodes. Among link analysis tasks, subjects in link mining literature. A link prediction model attempts to predict the appearance, the persistence, and the disappearance of a social network links relying on some of its given snapshots in the past. However, in this paper, we do not address the entire link prediction problem but only the sub-question that concerns the driving factors behind the persistence of the ties in academic social networks. The tie persistence seems to be an occasionally studied problem despite its importance. This importance is related mainly to the existence of a minority of nodes and links that persists always in spite of the rapid dynamicity of the network overtime. Identifying the driving factors behind the structure persistence is as important as identifying the driving factors behind the structure evolution. Thus, this work attempts to resolve the link persistence problem using a link strength based technique that can measure the collaborative importance of the existent collaboration relationships in the network. This technique relies on three strength indicators that have been proposed in the social psychology literature [8, 34]: the frequency of interactions between the actors, their contributions in the relation, and the social closeness between them. Furthermore, the possible validity of the important relation is verified according to two relevant academic-related attributes that mostly must be taken into account in the context of scientific collaborations: the scientific productivity of the relation and the professional rank (status) of the scientists involved within. Our proposed tie persistence prediction model combines these link strength indicators to assess the strength of the scientific collaboration relationships between researchers in order to identify the persistent ties in a dynamic and time-varying academic social milieu. 

the link prediction problem [28] is one of most studied Figure 1: An example of an academic social network (b) extracted from a bibliographic network (a) (Authors (A) who share the same papers (P) in the bibliographic bipartite graph (a) are connected with co -authorship links in the academic social network (b)). 


The remaining part of the paper is organized as follows: we begin with a brief overview of the previous research in the area. Then we explain our methodology for predicting the persistence of collaboration relations. We continue by presenting the performed experiments to validate the proposed model. Next, we report the findings of the research and discuss their implications. Then, we investigate the influence of the parameters of the model on its performance. Finally, we conclude with a brief summary of the findings and some suggestions for further research. 


Related work 
Social networks evolution problem addresses the question on how a social network evolves over time. Consequently, several sub-questions rise from this problematic. The most important are about the laws that govern the evolution and the factors that influence it. In this context, the study of the evolution of academic social networks has been a popular research topic in these recent few years. In the literature, the evolution of academic social networks may be analyzed on two levels: the macro level (the entire network) and the micro level (the simplest components of the network) [3]. Our work focuses on understanding the micro-level changes at the actor level. Specifically, it aims to predict the persistence of a tie between two nodes. This issue is a sub-question of the well-known link prediction problem, which addresses predicting the new links that join a social network in a given future time. Naturally, the link persistence issue is not independent from link prediction. 
This is for the reason that an actor’s future links (which a 
link prediction model tries to predict) may incorporate also the old links that continue to be present in the future. The earliest studies on the link prediction are that proposed by Adamic and Adar [1] and by Liben-Nowell and Kleinberg [28] for social networks. They proposed unsupervised models basing on computing similarity scores between the network nodes using graph-based similarity measures that rely mainly on the topological structure of the network or on the node attributes. Later, the work of Hasan et al. [20] has argued for the effectiveness of the supervised models rather than the unsupervised ones. In addition to these two classical approaches, researchers have developed several models following various paradigms that include for example similarity-based models, feature-based models, probabilistic models, relational models, graphical models, linear algebraic models; and random walks based models [4, 16]. An in-depth survey of these approaches may be found in [21]. The link prediction models can obviously predict the link persistence between two nodes by restricting the model application to only direct (1-hop) neighbors. However, since the main concern of the link prediction problem is to predict the new relations and not the repeated ones, so predicting persistent links using a link prediction model may run the risk of providing modest results. Therefore, it will be interesting to develop independent models in which the only goal is to identify factors that drive the persistence of the tie between two nodes. In this regards, social psychology literature provided important evidence about the various factors that influence the link persistence and decay. These factors are mostly: structural embeddedness (common acquaintances) [11, 14, 32], homophily [11, 32], social support [38], frequent contact (interaction) [38], social closeness [38], distance [32], status, and experience [11]. 

Moreover, there is some evidence on the “liability of newness”, which means that newly formed ties tend to 
decay more quickly than old-timer ties [11]. On the other hand, there are few models that tried to treat the link persistence prediction problem. For instance, Hidalgo et al. [22] used a rule-based technique to predict the tie persistence in mobile phone social networks relying on their observations about the correlation between network topological variables (degree, clustering, reciprocity and topological overlap) with the tie persistence. Akoglu and Dalvi [2] proposed a logistic regression-based model for tie persistence prediction in large phone and SMS networks, which takes into account the fact that node and link attributes like neighborhood overlap, reciprocity, clustering coefficient, and node degree affect the link persistence between the actors. 
Using decision tree and logistic regression based models, Raeder et al. [35] demonstrated that persistent ties in a cell-phone network are those characterized by high-levels of interaction frequency coupled with relatively constant re-activations of the tie overtime. On the contrary, ties that are candidates to decay, are characterized by relatively low levels of interaction and non-reciprocity. Apart from mobile phone social networks, Kirvan-Swaine et al. [26] studied the tie decay in the online social network of Twitter. Their findings revealed that reciprocity, embeddedness, power, and 
Informatica 40 (2016) 353–364 355 

status influence significantly the tie breaking between follower-followee links in the online social network. Differently from these studies, this paper proposes an unsupervised model for the tie persistence prediction in academic social networks. The proposed approach combines academic-related tie and node attributes to estimate the strength of relations between scientists. The model then reckons on its expectation about the possible scientists’ collaboration preferences to validate or invalidate the collaborative importance of relations and their probable continuity in the future. 
Algorithm 1. Tie persistence prediction model 
Input . : source author Output ...(.) collaborative importance score of the target author . 
For each author . in the network do Extract bylines of all publications of . Calculate the collaborative importance of each byline 
For each co-author . belongs to the publications bylines of . do 
Calculate the collaborative productivity of the relation between . and . 

If “Productive collaboration” then 

Assign . the collaborative importance of the publication byline he belongs to 
Else If the professional rank (academic age) of . equals to ........ then collaborative importance of . ...(.) . . // . has no need to . 
End if End if End for End For 


Tie persistence prediction model 
The strength of social links may be estimated using various strength indicators that can reflect the different dimensions of a given relationship. In the case of academic links, the strength may be better captured using indicators that are related to the knowledge production since the knowledge production represents the ultimate goal of academic collaboration relations [23]. To predict the persistence or the dissolution of an existent collaboration relationship between two scientists, our proposed model follows two steps (see Algorithm 1). First, it measures the collaborative importance of the existing relations of a given scientist using three strength indicators: the frequency of the relation, the contribution of the concerned actor within, and the social-academic closeness between its actors. Second, the model decides to retain or to terminate the existing relation depending on its expectation about the behavior of the concerned author toward this relation given its collaborative importance to him. Formally saying for each author ., we collect the publication bylines from his papers. The publication byline is the list of . authors who have co-written a given paper .. For each set of authors in each paper, the model measures the collaborative importance of the relation according to the author .. Given the collaborative importance of the relation, the model then verifies its collaborative productivity and checks the professional rank of the author in order to decide finally whether it is better to keep or to terminate the existing relation. Therefore, if a given relation passes the two steps successfully, every co-author who belongs to its related publication byline will take the collaborative importance value of the publication byline; otherwise, the model will suppose the inutility of a future collaboration relation between the concerned co-authors. Below, we give a detailed explanation of the model. 

3.1 Computing collaborative importance 
...(.... .) . (.... (...).......(.)) . (....... (.. ...)..... (... )) . (..(...).....(...) ) 
(1) Where: -. is the author, ... is the publication byline to which an author . belongs. -.... (...) is the number of times the author . has published papers having the byline .... -...... (.) is the total number of publications of the author .. 
-....... (.. ... ) is the contribution of the author . in the paper in comparison with his co-authors in the publication byline .... 
-	..(...) is the social-academic closeness factor of the publication byline ... . 
3.1.1 Frequency 
The frequency [8, 34] is an intuitive indicator of the link strength. It represents the number of times a set of authors have participated to the publication of the same papers. A high value of frequency of a publication byline indicates some trust between its members. 


3.1.2 Social-academic closeness factor 
The closeness [8, 34] encompasses a wide variety of meanings characterizing the social proximity between actors in social networks. To estimate this proximity, relationship scholars have conceptualized multiple measures such as RCI (Relationship Closeness Inventory) [7], IOS (Inclusion-of-Other-in-Self Scale) [3], and URCS (Unidimensional Relationship Closeness Scale) [13]. These measures are not deterministic models but scoring systems relying on questionnaires attempting to capture the various dimensions of the relationship. In [3], Aron et .al (the developers of IOS measure) 
postulated that in close relationship “people are 
motivated to include another in the self in order to 
include that other’s resources”. These resources may be anything that can “facilitate the achievement of goals”. 
Obviously, in academic social networks, the knowledge is that valuable resource a scientist hope others will share with him/her. Co-authored publications characterize scientific relations, but the type of publications may reveal the social-academic closeness between the actors of these relations. The concept of closeness in our model is oriented to estimate mainly the familiarity between the collaborators. Therefore, we suppose that a book type publication is more important than a journal paper type, and a journal paper type is more important than a conference paper type. This is based on the relevance of 
the “book” type as the most valuable publication and on 
previous observations [17, 18] that have shown that authors sharing journal papers are professionally and socially closer than authors sharing common conference papers. This is for the reason that journal papers have a much higher impact than conference papers as they receive more citations [17]. In addition, a relevant work requires more time to be produced and the relative length of the time spent in the publication production may 
multiply the chance of familiarity between the paper’s 
co-authors. 
Formally, the social-academic closeness factor for a 
given publication having a byline ... is expected to 
respect the constraint: 

..(.... ........ . ......) . ..(.... ........ 
. ........ ......) 
. ..(.... ........ 
. ........... ......) 
. 	Estimating the social-academic closeness from the type of publication 
We use in our model a scoring system bit similar to psychological measures described above in order to assess the social-academic closeness between publication co-authors. First, we construct an ordered list arranging publications types according to their relevance . . 
D. Mohdeb et al. 

{.. .... . .. ....... ..... . .. .......... ..... | 
Then, we penalize a given type of publication by discounting from its initial default value . a portion equals to . (. is a model parameter) multiplied by the order of the publication type in the arrangement list of publication types .. 
.. . . . (. . .) . . (. .. .. (. . .) . . . .) 
(2) 
-	. is the default value of publication. It is 
estimated to be . . .. 
-	. a regular portion the value of publication . 
loses by the degradation from a publication type 
to another. 
-	. is the order of the type of publication in the 
arrangement list. 


3.1.3 Author contribution in the relation 
The investment in the relation is another relevant strength indicator proposed in [8, 34]. Contribution is a domain-specific concept that can take different meanings according to the context it is used in. In academic social networks, the contribution of a scientist in a collaboration relation can be reflected in the credit that he deserves in the related publication in comparison with his co-authors. The proposed model estimates this credit using the Network-Based Allocation (NBA) model of co­authorship credit proposed by Kim and Diesner [24]. The NBA model uses the order of the author in the publication byline in addition to the length of the author list involved in to calculate his final credit. Noting that in many research fields, the order reveals reliable information about the contribution of the author in the publication with the exception of some disciplines such as Mathematics, Economics or High Energy Physics, which follow in their publications alphabetical order of authors [12, 24]. The NBA model is flexible in partitioning the credit between the co-authors of a given paper. It is based on the idea that each author belonging to a publication byline of length . and having an initial co-authorship credit equals to ., distributes a portion of his credit (equals to .. ) in equal amounts to his preceding authors on the byline. We can calculate final credits for each coauthor as follows: 
. . ... (. . .. . . .) .. . . . . (. . . . .) 
... 

.
.. . . . . .. . ... . . (. . .. . . .) . 
... 
... 

.

... . (. . .. ) . .. . ... . . (. . . . .. . . .) 
. ... .
... . . . .. 	(. . .. . . .) 
(3) 
Where: 

- . is the initial co-authorship credit given to each  
author.  
- . is the value of the paper (assumed equals to  
1), . is the number of the authors on a paper.  
- ..  is  the  transferable  credit,  calculated  by  
assigning a distribution factor . . }...~ to the  
initial co-authorship credit ..  The distribution  
factor . is the ratio of initial credit that should  
be distributed by each coauthor.  
- . is the order of authors  

Co-writers deserve equal co-authorship credits in a given publication if . . .. If . . . this means that, the first author have the higher possible value of contribution in the publication and the role of non-first authors is negligible. 


3.2 	Predicting scientist’s collaboration preferences 
A collaboration relationship between two scientific actors becomes subject to some academic reckonings to be continued or terminated even if it seems strong. These reckonings are mainly related to the academic attributes of the author and the effect of the output of this relation on his scientific career. Our approach assumes that the persistence of an important collaboration relation between an author and his coauthor depends on two relevant academic-related factors: the professional rank of the author (status) and the collaborative productivity of the relationship. Relying on early observations [15, 30], our model assumes that a newcomer or a junior researcher needs to conserve his important relations despite its unproductivity for the reason that his rank as a beginner obligates him to develop his coauthors network by exploiting these important relations for his benefit. By contrast, an experienced researcher has always the possibility to terminate any unproductive relation that cannot offer him a scientific advantage. 
3.2.1 Author professional rank 
The professional rank or the status of an author is related to his scientific and professional career. It naturally influences the collaboration preferences [5, 9] since the collaboration choices of an experienced scientist differs widely from the collaboration choices of a novice scientist. The reason behind this is the relatively large or small scientific network that a senior or a beginner scientist have respectively. 


3.2.2 Collaborative productivity 
The productivity rate is an essential factor to validate the importance of a collaboration relation. Nevertheless, considering this factor differs according to the academic professional experience of the scientist [5, 9]. The proposed model considers a co-authorship relation as a 
“productive collaboration” if the number of 
collaborations between the author and the coauthor equals to at least the median of the duration of their relationship. Noting that the duration is a useful tie 
Informatica 40 (2016) 353–364 357 

strength indicator to estimate the strength of links between actors in social networks [8, 34]. 
. (.. .) .. . ........... .............. . ......... (.. .) . (. . .).. (. . .. . ..) 
(4) Where: 
-......... (.. .) is the number of collaborations between the author . and his coauthor .. 
-	. is the duration of the relationship between . and .. -.. is the time (in year) of the last collaboration between the author and the coauthor. -.. is the time (in year) of the first collaboration between the author and the coauthor. 





4 Experiments 
4.1 	Dataset 
To demonstrate the performance of our approach, data are extracted from the well-known DBLP Computer Science Bibliography database, a huge digital library from the University of Trier, which covers publications in various computer science fields. We selected randomly from the « DBLP » database a set of 2250 authors from different research areas in computer science who appeared between year 1993 and 2008. After that, we equally divided this subset into three author sets basing on the academic age of the authors in the DBLP bibliographic network. We measured the academic age of a scientist as the number of years since his first publication. The academic age obtained from the DBLP do not exactly reflect the professional rank of the author but can offer a hint about his experience (except for cases where an author’s publications are not indexed by DBLP). 
Therefore, we had the following sets: -The Newcomers set: authors with an academic age less than six years. -The Juniors set: authors with an academic age between six and ten years. -The Seniors set: authors with an academic age greater than ten years. Table 1 summarizes dataset statistics. 
Table 1: Dataset statistics. 
N  E  S  Avg. C  
Seniors  18 834  62 550  750  26.54  
Juniors  17 699  57 655  750  22.68  
Newcomers  17 076  56 417  750  21.78  
53 609  176 622  2250  23.66  

N, E: number of nodes and edges in the full network, S: number of source authors, Avg. C: average number of co-authors per source 
We draw the reader’s attention to the fact that the quality 
of our data can be affected by the performance of the method used by DBLP to resolve the author name disambiguation problem [27]. Relying on the recent study of Kim and Diesner [25], the value ranges of the findings may vary if we use a different method for name disambiguation. Fortunately, as the latter study confirmed, this may not have a distortive effect on the general trend of the network evolution on which our findings depend. 


4.2 Experimental setup 
First, for learning the link persistence prediction model, we formed a general network combining all the co-authorship networks from 2003 to 2014 that correspond to the scientists belonging to the three author subsets. Let an author pair be (.. .), we call . the source author, and . the target author. The source authors are those who belong to the three author sets mentioned above (newcomers, juniors, and seniors). The target authors are the direct neighbors (i.e. 1-hop neighbors) of the source authors. Then, we chose the sub-network data between 2003 and 2008 as training set, and the sub­network data between 2009 and 2014 as testing set. Second, the general parameters that we used for framing the link persistence model are the following: 
-The professional rank of an author was calculated according to his academic age. 
-As in the default setting of NBA co-authorship credit model [24], we assumed . . ... as the ratio of the initial credit that should be distributed by each author belonging to the publication byline of a given paper (Eq. 3). The advantage of this setting is maximizing the contribution of first authors as well as avoiding neglecting the contribution of non-first authors. 
-For the social-academic closeness factor in Eq. 2, we assumed . . .... the ratio of the initial value of the publication an author loses according to the type of the publication. As such, the social-academic closeness factor is ......... for the publication types: book, journal paper, and conference paper, respectively. We recall that our estimation of the social-academic closeness factor is based on a simple intuitive scoring system because we cannot exactly measure this value due to its psychological complex nature. 


4.3 Evaluation framework 
In order to show the effectiveness of our tie persistence prediction method for social academic networks, we compared its performance with the baseline methods used for the link prediction problem since they can also measure link persistence. The baseline methods considered are Common Neighbor (CN), Jaccard's Coefficient (JC), Adamic/Adar (AA), Preferential Attachment (PA), and Page Rank (PR). Formal descriptions of these methods are illustrated in Table 2. 

Common Neighbor [19] is a simple metric that counts the number of shared neighbors (i.e. the number of paths of length 2) between two nodes. The Jaccard's coefficient 
[36] divides the common neighbors of a pair of nodes by the size of the union of their neighbors. The Adamic/Adar measure [1] weighs the rarer common features more heavily. These three metrics are related to the positive impact of the common acquaintances (structural embeddedness) on the tie formation and persistence between social actors. From the perspective of the tie persistence problem, they provide information about the social and scientific circles where a scientist moves. It is then reasonable to assume that, if two related scientists deal with the same scientific entourage, it is likely that their relation persists. The Preferential attachment [6] of two nodes is the product of their degrees. In our context, it is used to assume that a scientist tend to keep relations with highly connected scientists who have a better status [9, 12]. The PageRank algorithm [10] ranks the node proportionally to the probability that it will be attained through a random walk on the network. 
Table 2: Link prediction baseline metrics. 
Metrics  Description  
Common Neighbor (CN)  .. (.. .) . ..(.) . .(.).  
Jaccard’s coefficient (JC)  .. (.. .) . ..(.) . .(.). ..(.) . .(.).  
Adamic/Adar (AA)  .. (.. .) . . . . . .(.)..(.) . ... ..(.).  
Preferential attachment (PA)  .. (.. .) . ..(.) . .(.).  
PageRank (named  Similarity score between . and .  
as Rooted  is measured as the stationary  
PageRank in [28])  distribution of . under the following random walk: . With probability ., return to .. . With probability . . ., move to a random neighbor.  

. and . denote two given nodes in the social network. .(.). .(.) represent the set of neighbors of . and . respectively. 
For evaluating the methods used in this study, we employed a threshold curve metric: AUCPR (Area under the Precision Recall Curve) and two fixed threshold metrics: Precision and Recall. Precision is the probability that a randomly selected positive prediction by the classifier is correct. Recall is the probability that a randomly selected positive instance is detected by the classifier. A Precision-Recall (PR) curve plots precision vs. recall. AUCPR is thought to give a more reliable informative view of an algorithm's performance in comparison with the other common performance evaluation measures especially for the link prediction 
Table 3: PRECISION performance results. 
LPP  AA  CN  JC  PA  PR  
Newcomers  0.4597  0.4429  0.4615  0.4613  0.4535  0.3198  
Juniors  0.3621  0.3494  0.3542  0.3542  0.3504  0.2770  
Seniors  0.3846  0.3601  0.3731  0.3731  0.3644  0.2790  
Avg. Precision  0.4021  0.3841  0.3963  0.3962  0.3894  0.2919  

LPP: Link Persistence Prediction method, AA: Adamic-Adar, CN: Common Neighbor, 
JC: Jaccard’s Coefficient, PA: Preferential Attachment, PR: Page Rank 

Table 4: RECALL performance results. 
LPP  AA  CN  JC  PA  PR  
Newcomers  0.6161  0.5571  0.5003  0.5002  0.5306  0.3918  
Juniors  0.5704  0.5080  0.4561  0.4561  0.5060  0.3583  
Seniors  0.5424  0.4970  0.4394  0.4394  0.4973  0.3423  
Avg. Recall  0.5763  0.5207  0.4653  0.4653  0.5113  0.3642  

Table 5: AUCPR performance results. 
LPP  AA  CN  JC  PA  PR  
Newcomers  0.6264  0.5748  0.5557  0.5551  0.5558  0.4071  
Juniors  0.4823  0.4549  0.4281  0.4281  0.4283  0.3533  
Seniors  0.4902  0.4461  0.4254  0.4254  0.4253  0.3546  
Avg. AUCPR  0.5330  0.4920  0.4697  0.4695  0.4698  0.3717  

task [29]. This is mainly related to its fairness and efficiency in overcoming the class imbalance, which is not much present in the tie persistence prediction problem but very frequent in the link prediction problem. A high area under the curve characterizes both high recall and high precision. 
......... . .. .(.. . ..) ...... . ...(.. . ..) 



Results and discussion 
Performance results measured in Precision, Recall, and AUCPR for all baseline methods and link persistence prediction method (LPP) are presented in Tables 3, 4, and 5. The values in bold face indicate the best overall prediction performance for the corresponding dataset. It is evident that Precision, Recall, and AUCPR agree about the best method and show in general the same performance trend. Interestingly, we note well performance of link persistence prediction method (LPP): about 57% of persisting ties are correctly classified by the model (recall) and about 40% of the ties that the model predicts to persist do in fact  persist. The proposed link persistence prediction method reveals the best performance in all the three datasets (except for its precision value in the Newcomers set) and provides significant enhancement over the link prediction baseline methods. AUCPR show notable performance of the proposed model in comparison with link prediction baselines with approximately 8% as relative improvement. The gain is remarkable from the perspective of Recall in which it reaches 10.5% but somewhat minimal from the perspective of Precision with only 1% as relative improvement. Apart from our proposed method, we note insufficient performance of the path-based method PageRank, which is explicable due to the fact that the target authors are direct neighbors. It is clear that a low distance such as 1-hop distance may have a negative impact on the effectiveness of a random walk based predictor. In contrast, we note good performance of the neighbor-based link prediction 

methods Common Neighbor, Adamic/Adar, Jaccard’s 
coefficient, and Preferential attachment. As well, the results show that the performance of the neighbor-based methods is comparable in terms of Precision but the Adamic/Adar beats the three other metrics in terms of Recall and AUCPR. While the existing works in link prediction reported the performance of Adamic/Adar in co-authorship networks [28], the results of this predictor and the other neighbor-based metrics are consistent also with previous studies that signed the positive effect of the 
structural embeddedness and the actors’ status on the tie 
persistence in social networks [2, 11, 14, 26, 32, 35]. Turning to the academic context of our model, these findings may be justified from different angles. An important thing to notice is that academic social networks are extremely dynamic networks. Rare are the nodes or the links that continue to accompany a scientist to a long period since the first collaboration even if they are academically strong. Moreover, the decay of a strong collaboration relation during a given time period sometimes can be confused by the tie inactivity. So, a possible explanation of our findings may be related to the social independence of the author as researcher. A scientist in an environment where there is no need to sentimental support as in real social networks seeks always a scientific support, which can be obtained from different scientific entities or scientists who share with him the same ideas or the same research interests. Indeed, as he raises, his knowledge and expertise increase, his research interests develop, and his collaboration network evolves and gets larger. This is the reason behind the fact that the Recall in all the tested methods is higher than the Precision. All the methods can better expect the relevance of a collaboration relation but show less performance in expecting its probable continuity in the future. This is well apparent when observing the impact of the author’s professional experience on the persistence of his direct collaboration relations. In general, the results show 
that the higher the author’s professional rank the lower 
the persistence prediction accuracy. This is reasonable since it is more difficult to expect the collaboration strategies of an experienced author for the reason that his choices are mainly independent, irregular, and do not follow clear trends. On the contrary, a scientist in his earlier career deals only with a few number of collaborators for a limited number of years. Mostly, his collaborators consist in his advisor and some colleagues who work with the same advisor. As the expertise of the scientist increases, his scientific network expands including a growing number of novice, junior, and senior researchers providing a large collaboration network with a high number of weak ties and a small number of strong ties, logically in a future step, many links will decay and few links will persist. Certainly, the model needs to be refined and improved, but we can say that the present findings illustrate that the frequency, the contribution of the authors, and the type of the publication (that expresses the social-academic closeness between the co-authors) play a significant role 
Table 6: LPP Performance results with different 
values of parameters ., ., and different settings of 
publication types order. 
.  Avg. PREC  Avg. REC  Avg. AUCPR  
d = 0  0.4220  0.5465  0.5447  
d=0.25  0.4043  0.5727  0.5385  
d = 0.5  0.4021  0.5763  0.5330  
d=0.75  0.3770  0.5730  0.5055  
d = 1  0.3790  0.4755  0.4813  
Order of Pub Types  
B-C-J  0.4008  0.5814  0.5374  
B-J-C  0.4021  0.5763  0.5330  
C-B-J  0.4012  0.5825  0.5384  
C-J-B  0.3990  0.5809  0.5347  
Theta (.)  
T = 0.1  0.3947  0.5761  0.5273  
T=0.25  0.4021  0.5763  0.5330  
T = 0.3  0.3889  0.5714  0.5191  
T = 0.4  0.3784  0.5638  0.5043  

D. Mohdeb et al. 

in determining the persistence of a scientific collaboration relation. Furthermore, they encourage the consideration of the probable collaboration preferences that a scientist may pursue during his scientific career regarding some academic-related attributes such as academic experience and collaborative productivity in order to provide an additional gain in the prediction performance. 
6 Influence of the model parameters 
Next, we investigate the impact of co-authorship credit and social-academic closeness factor on the performance of the proposed tie persistent predictor. We depicts in Figure 2, 3, and 4 the plots of performance (Precision, Recall, and AUCPR) resulted from applying different values of parameters . (NBA co-authorship credit model), and . (social-academic closeness factor), and from changing the relevance order of publication types (social-academic closeness factor). When the e.ect of a parameter is under experimentation, the other parameters are assigned with the default values that have been described previously in Section 4.2. Table 6 describes the overall Precision, Recall, and AUCPR on the complete dataset (that combines the three author sets Newcomers, Juniors, and Seniors) according to the various values of the aforementioned parameters. 
6.1 	The parameter . 
Our results (Figure 2, Table 6) indicate that the performance of the proposed method varies inversely with .. The more the co-authorship credits get far from equality between the co-authors of the same paper (. . 
.), the more the prediction accuracy of the proposed model gets lower. The only exception is for the Recall that peaks the best value when . . ... (i.e. the first co­author has more than 50% as contribution in a given paper). It is a difficult conclusion to draw without careful investigations that computer scientists in their publications share equal credits with their co-authors because the first authors in a given publication have generally the greater contribution within [24]. Instead, we can assume that contributions may take other forms beyond the formal way (co-authoring the publication). This includes for example informal discussions between co-authors, supervision (advising), technical or academic assistance…etc. and all other practices that strengthen the academic relations between scientists but unfortunately, they are difficult to estimate formally. 

6.2 	The order of publication types and the parameter . 
The three versions of tie persistence predictor (LPP) that are relevant to the three orders B-C-J, C-B-J, and C-J-B respectively (Figure 3, Table 6), show comparable performance results in Precision, Recall and AUCPR. As for the B-J-C order (the default order of publication types), a lower Recall, a comparable AUCPR, and a slightly greater Precision are marked. Two observations 

Figure 2: Performance of LPP with different values of parameter .. 

Figure 3: Performance of LPP with different settings of publication types order. 

Figure 4: Performance of LPP with different values of parameter .. 
are worth noting here. First, the results reveal that 
“books” do not play a relevant role in determining the 
social-academic closeness between computer scientists. We think that this is not due to the unimportance of books but to the fact that this type of publication is not frequent in computer science field [18]. Second, if we 
ignore the “book” publication type, we observe that 
while using the ordinary order (B-J-C) seems yield to slightly more precision, the overall performance remains nearly comparable to the performance of the other order settings where conference papers are considered more relevant than journal papers (B-C-J, C-B-J, and C-J-B). In the DBLP bibliographic database, journal papers are less frequent than conference papers even though they have much higher impact [17]. Consequently, the outcome that we can assume from these conflicting findings is that the high frequency of conference papers in computer science collaboration networks reinforces positively the role of this type of publication in defining the social-academic closeness factor between computer scientists. The parameter . maintains the difference in relevance between the three publication types: book, journal paper, and conference paper. We tested . with the default order B-J-C. The results (Figure 4, Table 6) show that the greater the difference between relevance values of publication types, the lower the prediction accuracy. This means that . should be an appropriate value, which does not underestimate the role of publications, whatever their types, in maintaining the academic closeness between collaborators. . . .... seems to be a suitable value since it gives convenient social-academic closeness values, which contribute to the well performance of the tie persistent predictor. 




Conclusion 
Studying the dynamics of a tie is a crucial step to comprehend the structure and the evolution overtime of social networks. In an academic social network, this is related to a number of factors that must be examined in order to better fix their actual effects on maintaining the connectivity of the network. We modeled a tie persistence prediction approach basing on estimating the tie strength using three factors: the frequency of collaborations, the social-academic closeness, and the scientific contributions of the scientists; and taking into account two other scientists’ academic-related attributes: the collaborative productivity and the professional rank. Experimenting the model, we found significant impact of the aforementioned factors on the persistence or the dissolution of collaboration relations between scientists in academic social networks. Our findings also reported that a strong collaboration relation does not always persist due to other academic reckonings that are not easy to expect mostly for experienced scientists. It would be interesting then to develop useful techniques that have the ability to catch such unexpected collaboration choices. There is much room for improvement, particularly designing better metrics to estimate the contribution of the author in the relation and the social-academic closeness between the co-authors. As well, using the academic age to infer approximately the 
author’s professional rank is a limited method. It would 
be better to develop efficient schemes that may provide 
realistic information about scientists’ status in academic 
social networks. Further research might also investigate the impact of other academic-related attributes and other tie strength indicators, which have not been invested in this paper such as trust, reciprocity, and breadth of topics. Finally, applying the proposed model on larger academic networks and on academic networks from other academic fields may improve the performance of the tie persistence predictor and provide much understanding of collaboration trends in these disciplines. 


References 
[1] 	Adamic, L. A., & Adar, E. (2003). Friends and neighbors on the Web. Social Networks, 25(3), 211–230. 
[2] 	Akoglu, L., & Dalvi, B. (2010). Structure, tie persistence and event detection in large phone and SMS networks. In Proceedings of the Eighth Workshop on Mining and Learning with Graphs ­
MLG ’10 (pp. 10–17). 
[3] 	Aron, A., Aron, E., & Smollan, D. (1992). Inclusion of other in the self scale and the structure of interpersonal closeness. Journal of Personality and Social Psychology, 63, 596–612. 
[4] 	Backstrom, L., & Leskovec, J. (2010). Supervised random walks: Predicting and recommending links in social networks. Proceedings of the Fourth ACM International Conference on Web Search and Data Mining, 635–644. 
D. Mohdeb et al. 

[5] 	Bahr, A. H., & Zemon, M. (2000). Collaborative authorship in the journal literature: Perspectives for academic librarians who wish to publish. College & Research Libraries, 61(5), 410–419. 
[6] 	Barabasi, A. L. et al. (2002). Evolution of the social network of scientific collaborations. Physica A 311, 590–614. 
[7] 	Berscheid, E., Snyder, M., & Omoto, A. M. (1989). The relationship closeness inventory: Assessing the closeness of interpersonal relationships. Journal of Personality and Social Psychology, 57, 792–807. 
[8] 	Blumstein, P., & Kollock, P. (1988). Personal Relationships. Annual Review of Sociology, 14, 467–490. 
[9] 	Bozeman, B., & Corley, E. (2004). Scientists’ collaboration strategies: Implications for scientific and technical human capital. Research Policy, 33(4), 599–616. 
[10] Brin, S., & Page, L. (1998). The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 30(1/7), 107–17. 
[11] Burt, 	R. S. (2000). Decay functions. Social Networks, 22, 1–28. 
[12] Costas, 	R., & Bordons, M. (2011). Do age and professional rank influence the order of authorship in scientific publications? Some evidence from a micro-level perspective. Scientometrics, 88(1), 145–161. 
[13] Dibble, J. L., Levine, T. R., & Park, H. S. (2012). The Unidimensional Relationship Closeness Scale (URCS): Reliability and validity evidence for a new measure of relationship closeness. Psychological Assessment, 24(3), 565–572. 
[14] Feld, 	S. L. (1997). Structural embeddedness and stability of interpersonal relations. Social Networks. 19, 91-95. 
[15] 
Fonseca, L., Velloso, S., Wofchuk, S., & De Meis, 

L. 
(1998). The relationship between advisors and students. Scientometrics, 41(3), 299–312. 



[16] Fouss, F., Pirotte, A., Renders, J. M., & Saerens, M. (2007). Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation. IEEE Transactions on Knowledge and Data Engineering, 19(3), 355– 
369. 

[17] Franceschet 	M. (2010). The role of conference publications in computer science: a bibliometric view. Communications of the ACM, 53(12), 129­
132. 

[18] Franceschet, M. (2011). Collaboration in computer science: A network science approach. Journal of the American Society for Information Science and Technology, 62(10), 1992–2012. 
[19] Girvan, 	M. & Newman, M. E. J. (2002). Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America, 99(12), 7821–7826. 
[20] Hasan, M. Al, Chaoji, V., Salem, S., & Zaki, M. (2006). Link prediction using supervised learning. 
SDM’06: Workshop on Link analysis, Counter 
terrorism and Security. 
[21] Hasan, M. Al, & Zaki, M. J. 	(2011). A Survey in link prediction in social networks. In Social Network Data Analytics (pp. 243–275). 
[22] Hidalgo, 	C. A., & Rodriguez-Sickert, C. (2008). The dynamics of a mobile phone network. Physica 
A: Statistical Mechanics and Its Applications, 387(12), 3017–3024. 
[23] Katz, 	J. S., & Martin, B. R. (1997). What is research collaboration?. Research Policy, 26(1), 1– 
18. 
[24] Kim, 	J., & Diesner, J. (2014). A network-based approach to coauthorship credit allocation. Scientometrics, 1–16. 
[25] Kim, J., & Diesner, J. 	(2015). The effect of data pre-processing on understanding the evolution of collaboration networks. Journal of Informetrics, 9(1), 226-236. 
[26] Kivran-Swaine, F., Govindan, 	P., & Naaman, M. (2011). The impact of network structure on breaking ties in online social networks: Unfollowing on Twitter. Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, 1101–1104. 
[27] Ley, 	M. (2009). DBLP: some lessons learned. Proceedings of VLDB Endow., 2(2), 1493-1500. 
[28] Liben-Nowell, D., & Kleinberg, J. (2003). The link prediction problem for social networks. Proceedings of the Twelfth Annual ACM International Conference on Information and Knowledge Management (CIKM), 556–559. 
[29] Lichtenwalter, R., & Chawla, N. V. (2012). Link prediction: Fair and effective evaluation. Proceedings of the 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2012, 376–383. 
[30] Long, J. S., & McGinnis, R. (1985). The effects of the mentor on the academic career. Scientometrics, 7(3-6), 255–280. 
[31] Mali, F., Kronegger, L., Doreian, P., & Ferligoj, A. (2012). Dynamic scientific co-authorship networks. Understanding Complex Systems, 195–232. 
[32] Martin, J. L., & Yeung, K. T. (2006). Persistence of close personal ties over a 12-year period. Social Networks, 28(4), 331–362. 
[33] Newman, M. E. 	J. (2001). Scientific collaboration networks: I. Network construction and fundamental results. Physical Review E, 64(1), 1–8. 
[34] Perlman, D., & Fehr, B. 	(1987). The development of intimate relationships. In Intimate Relationships Development and Deterioration (pp. 13–42). 
[35] Raeder, T., Lizardo, O., Hachen, D., & Chawla, N. 
V. (2011). Predictors of short-term decay of cell phone contacts in a large-scale communication network. Social Networks, 33(4), 245–257. 
[36] Salton, G., & McGill, M. J. (1983). Introduction to modern information retrieval. Introduction to Modern Information Retrieval. 
[37] Velden, T., Haque, A. U., & Lagoze, C. (2010). A new approach to analyzing patterns of collaboration in co-authorship networks: Mesoscopic analysis and interpretation. Scientometrics, 85(1), 219–242. 

[38] Wellman, B., Wong, R. Y., Tindall, D., & Nazer, N. (1997). A decade of network change: Turnover, persistence and stability in personal communities. Social Networks, 19, 27–50. 


A Temporal Perspective on the Paradox of Pinocchio's Nose 
Matjaž Gams 
Jozef Stefan Institute, Jamova 39, Ljubljana, Slovenia 
Eva Černčič 

University of Southampton, Southampton SO17 1BJ, United Kingdom 
Angelo Montanari Universita degli Studi di Udine Polo Scientifico Rizzi Univerza, Udine UD, Italy 
Keywords: logical paradoxes, Pinocchio, nose growth 
Received: March 15, 2016 

The paradox in the question originates from the well-known children story of Pinocchio, starring a 
wooden boy whose nose grows whenever he is lying. The paradox stems from his statement: “My nose is 
growing". In real life, a statement that a person's nose grows should not cause any problems, since noses have the property of growing; however, the statement refers to a specific growth, associated with lying and logic. In this paper, we present yet another view, based on artificial-intelligence agents. 
Povzetek: Prispevek obravnava paradoks Ostržkovega nosa in v nasprotju s prevladujočim svetovnim mnenjem pokaže pravilnost Eldridge-Smithovega paradoksa, čeprav velja le kratek čas. 
The Paradox of Pinocchio's Nose was first proposed on February 2001 by 11-year-old Veronique Eldridge-Smith, the daughter of Peter Eldridge-Smith, who wrote an article in the journal Analysis. It was often proclaimed to be a liar paradox, but this paper finds the paradox valid. However, as with most logic paradoxes when faced with real life and AI solutions, the paradox turns out valid for only a short period of time. 
To formalize the problem as a logical puzzle [1], we treat it as a set of propositions: 
The statement: “Pinocchio's nose is growing" is true if and only if Pinocchio's nose is growing at the moment. 
Pinocchio's nose is growing if and only if he is telling a lie. 
Pinocchio is saying: “My nose is growing". 
We can give the following abstract form to the problem. Let ‘P’ denote the sentence “My nose is growing", and let P be its description in the natural language, i.e., the action of nose growth. Then, if ‘A’ is any statement by Pinocchio, we are left with the following system: 
True(‘P’) iff P 
P iff False(‘A’) 
A = P 
We evaluate the system in the following way. We assume ‘P’ is true. Thus, (1) implies the truth of P. However, by (2) ‘A’ is false and (3) yields that so is ‘P’. Summarising, we can conclude that True(‘P’) implies False(‘P’). A similar argument may be conducted to show that False(‘P’) implies True(‘P’), and, hence, we can conclude that True(‘P’) if and only if False(‘P’). 

According to Peter (and Veronique) Eldridge-Smith, who originally formulated the problem in [2] and further elaborated on it in [3], the Pinocchio paradox is an improved version of the classical liar paradox, where any attempt to assign a binary truth value to the statement: “This sentence is not true" leads to the conclusion that the statement is true if and only if it is false. The same conclusion is reached in the Pinocchio case, where his nose is growing if and only if it is not growing. However, as Eldridge-Smith points out [2], the Pinocchio paradox differs from the classical Liar paradox in one important feature: “(the nose) is growing" is not a synonym for “(the sentence) is not true", as having one's nose grow is not a semantic feature. Hence, the way out from the Liar paradox originally proposed by Tarski, explained in [4] (to exclude semantic predicates from the object language), and refined by Kripke [5] (to define a non-strict metalanguage hierarchy that allows non-paradoxical uses of semantic predicates in the object language) does not work here. Unlike the liar paradox, the Pinocchio's nose should represent a “true paradox" as declared by Eldridge-Smith. A discussion followed by Beall and Eldridge-Smith [6, 7, 8], who argued whether the Pinocchio paradox affords no argument against ‘simply semantic dialetheism’ or not, without mutual agreement. 
In this paper, we focus our attention on another distinctive feature of the Pinocchio paradox: its temporal dimension. Eldridge-Smith himself briefly mentions it at the very beginning of his paper [2]. In the original formulation of the paradox, indeed, given by his daughter Veronique, Pinocchio says ‘My nose will be growing'. Quoting Eldridge-Smith: “The use of a future tense ties in with when Pinocchio's nose is supposed to grow after telling a lie. Philosophers will naturally want to know how soon afterwards. (There is an interesting version of the Epimenides though, if one does not restrict how soon Pinocchio's nose should grow. Imagine Pinocchio says 
‘My nose will grow' but everything else Pinocchio says is 
true. Then, Pinocchio's nose will grow if and only if it does not.)". 
In the following, we elaborate on the temporal issues involved in the Pinocchio paradox from an artificial intelligence perspective [9], showing the possibility of another interpretation of the paradox. First, we observe that the temporal length of the utterance cannot be ignored. Utterances are not instantaneous, and any statement can be properly evaluated only at the moment when it is completed. Second, we assume that Pinocchio, despite his fictive nature, has to abide to the laws of our universe (which is evident through other stories about Pinocchio). In this context, some computing mechanism (fictive or real, still obeying laws of the ‘computing universe') must evaluate Pinocchio's statements and possibly ignite the growing of the nose, say in time .. Afterwards, in the case of untruth, the nose growth is instantaneously triggered for a period of time, say x, independent of the nature of lies. 
Now, we can consider the most basic case, in which prior to saying ‘P’, where P indicates a lie, Pinocchio was quiet, e.g., at sleep. Timing of ‘P’ on the time line corresponds to the point in time t0 when the sentence was completed. 

Figure 1: Simple nose growth. 
Timing of the nose growth is depicted in Figure 1. In case of a lie, Pinocchio's nose grows between t0 + . and t0 
+ . + x. If ‘P’ indicates the sentence “My nose is growing now", then the mechanism evaluates P at t0, which turns out to be a lie, and Figure 1 correctly displays the process of nose growing, since at the moment of speaking his nose was not growing. 
Let us consider now a more complicated situation where Pinocchio did tell some lie in the past, with the consequence of growing nose in the present, or will tell some lie in the near future, interacting with the time schema of nose growing. Consider the case of two sequential lies, completed at times t0 and t1, respectively, where at time t1 the sentence “My nose is growing now" is uttered. Depending on the timing of t1, we distinguish two non-trivial cases: 
t0 < t1 < t0 + .: the first one is of purely theoretical 
interest, as it involves completing the sentence in a time frame smaller than is physically possible. Nevertheless, 
as his nose is not yet in the growth phase, the total growth time is going to be extended, as displayed in Figure 2. 
M. Gams et al. 


Figure 2: Nose growth in case of overlapping lies. 
t0 + . < t1 < t0 + . + x: in that period his nose is already growing, due to the previous lie, and thus no further action is taken. 
Cases with a slightly different formulation of the sentence may also be of interest. “My nose will be growing" is obviously a true statement, since Pinocchio will sooner or later utter another lie (notice that since evaluating Pinocchio's statements takes some time, there is in any case a delay between the completion of the utterance and the possible start of the process of nose growing, thus avoiding the variant of the Epimenides mentioned by Eldridge-Smith in [2]). 
But what about: “My nose will be growing at time t", formally denoted by ‘P(t)'? This sentence is unproblematic for t < t0 + . since it is obviously a lie and consequently his nose will grow, starting at t0 + .. But for t . t0 + . we obtain the original formulation of the problem, resulting in the paradoxical state, which cannot be avoided as in the case of the liar paradox. However, as mentioned we can elaborate the problem from the point of view of artificial intelligence [9, 10], by assuming that there exists an agent that computes the truth of Pinocchio's statement continuously over time. For the sake of simplicity, we assume that the computing time is . (as we did before) and that the shortest observable/measurable time interval is .. The behaviour of the agent responsible for the nose growth can be defined as follows: 
for every time step ., compute: if False(‘P(t)') holds at time t = tc, where tc represent the current time of the evaluation, then trigger nose growth for a period of time x, starting at tc + . 
Let us consider the statement ‘P(t)’ for some 

meaningful values of t. 
t = t0: we have the original formulation of the problem, which was already discussed before. The same evaluation applies to all times t < t0 + . as the agent knows no growth mechanism could be triggered resulting in growth at time t. 
t = t0 + .: ‘P(t)’ is processed and evaluated at t0 (the evaluation process takes time .). As the system cannot decide whether the statement is true or false for time t0 + ., the paradoxical state appears in the time interval [t0 + .; t0 + . +.], and the agent cannot cause growing the nose at time t0 + .. But the growth mechanism can be triggered already for the growth at time t0 + . + ., as an intelligent agent knows there was no mechanism triggered that would result in the nose growth at time t (= t0 + .). Notice the way we assimilated a paradoxical state to a state with no information (undecided) and we assumed that if an agent has no information about the fact that statement ‘P’ is false at time t, it makes no action. This may look, to some extent, arbitrary, but we consider such a choice the most reasonable one. Moreover, at the time of decision there are in fact only two possibilities: the nose starts growing or not. A short time later, the agent can conclude something in both cases. Therefore, the true paradox actually disappears after a short time in any sensible interpretation, not only in the above-mentioned one. 

Figure 3: Nose growth in case of Pinocchio's statement: 
“My nose will be growing at the time t0 + . ". 
t > t0 + .: ‘P(t)’ is first processed at t0 and then successively at each step . later, until the evaluation at time t – . + ., where it becomes clear if nose will be growing at time t. If the growth mechanism was not triggered by some previous lie, the scenario presented in Figure 3 repeats with a short contradicting moment (the paradoxical state) followed by the nose growth as shown in Figure 4. 


Figure 4: Nose growth in case of Pinocchio's statement: 
“My nose will be growing at the time greater than t0 + . 
(iii) ". 
Finally, Pinocchio can proclaim that his nose will 
grow in some intervals, say, from t1 to t2. Let t = (t1;t2). Analyses depend on the length of the interval. In particular, we distinguish the following cases: 
t2 < t1 + .: due to the length scale of the interval, the situation is treated in the same manner as if interval was a point, as discussed above. 
t1 + .< t2 < t1 + . + x: the agent evaluates ‘P(t)’ in time intervals .. The paradoxical state appears for a short 
moment at t1 -. + ., then the growth mechanism is triggered. At all later evaluations, a truth value is 
assigned to ‘P’, due to triggered nose growth. Thus, the 
situation is identical as in Figure 4. 
t2 > t1 + . + x: the treatment of the problem is the same as in the previous case until time t1 + . + x, where a paradoxical state appears again and another nose growth is triggered. This process can repeat itself numerous times until the evaluation at time t2 yields the truth value. The situation is depicted in Figure 5. 


Figure 5: Nose growth: interval evaluation. 
The contribution of the paper can be summarized as follows. In [2, 3], Peter Eldridge-Smith introduced the paradox of Pinocchio's nose growth and pointed out that, unlike the liar paradox, it is a true paradox, which cannot 
Informatica 40 (2016) 365–368 367 

be solved by disallowing problematic uses of semantic predicates in the object language. In this paper, we argued that Pinocchio paradox can be suitably confined to some very small time intervals. 
Unlike the liar paradox, which is based on a timeless truth statement, the treatment of Pinocchio paradox is a time-dependent truth statement. It is not new that time and paradoxes can be intertwined: for example, the Ross-Littlewood paradox [11] deals with time and infinity, but it is not directly related to this paper. 
We showed that the Pinocchio paradox can be analysed using a temporal approach, which takes time aspects, such as the temporal length of utterances as well as the duration of the process of statement evaluation, into consideration, and consequently makes it possible to significantly reduce the (temporal) extent of the paradox. On the other hand, for that particular period of time, Eldridge-Smith's claim that the Pinocchio paradox differs from the classical Liar paradox seems to be valid. 
1 	References 
[1] 	Kremer, P. (2009) The Revision Theory of Truth. The Stanford Encyclopedia of Philosophy (Spring 2009 Edition), Edward N. Zalta (ed.), http://plato.stanford.edu/archives/spr2009/ entries/truth-revision/. 
[2] 	Eldridge-Smith, P., Eldridge-Smith, V. (2010) The Pinocchio paradox. Analysis 70:212-215. 
[3] 	Eldridge-Smith, P. (2011) Pinocchio against the dialetheists. Analysis 71:306-308. 
[4] 	Hodges, W. (2013) Tarski's Truth Definitions. The Stanford Encyclopedia of Philosophy. (Spring 2009 Edition), Edward N. Zalta (ed.). 
[5] 	Kripke, S. (1975) Outline of a Theory of Truth. The Journal of Philosophy, 72(19):690-716. 
[6] 	Beall, J. C. (2011) Dialetheists against Pinocchio. Analysis 71 (4):689-691. 
[7] 	Eldridge-Smith, P. (2012) Pinocchio beards the Barber. Analysis 72:749-752. 
[8] 	Beall, J. C. (2014) Rapunzel Shaves Pinocchio’s Beard. Contradictions: Logic, History, Actuality. 6:27-30. 
[9] 	Russel, S., Norvig, P. (2010) Artificial intelligence: a modern approach (third edition), Prentice Hall. 
[10] Wooldridge, 	M. J., Jennings N. R. (2014) Intelligent Agents, Springer. 
[11] Littlewood, 	J. E. (1953) A Mathematical Miscellany. Methuen; reprinted as Littlewood's Miscellany, B. Bollobas (ed.), Cambridge: Cambridge University Press, 1986. 


Verifying Time Complexity of Turing Machines 

David Gajser IMFM, Jadranska 19, 1000 Ljubljana, Slovenia E-mail: david.gajser@fmf.uni-lj.si 
Thesis summary 
Keywords: Turing machine, relativization, NP-completeness, crossing sequence, decidability, lower bound, time com­plexity, running time, linear time 
Received: November 4, 2016 
This paper presents a summary of the doctoral dissertation [1] of the author, which analyzes in detail the following problem. For a function T : N › R.0, how hard is it to verify whether a given Turing machine runs in time at most T (n)? Is it even possible? 
Povzetek: Prispevek predstavlja povzetek doktorske disertacije [1] avtorja, v kateri je podrobneje obrav­navan naslednji problem. Naj bo T : N › R.0 poljubna funkcija. Kako težko je preveriti, ali je ˇcasovna zahtevnost danega Turingovega stroja T (n)? Je to sploh mogoˇ
ce preveriti? 

While it is tempting to argue about a Turing ma­chine’s time complexity, we cannot algorithmically tell even whether a given Turing machine halts on the empty input (a folkloric result). Can we perhaps algorithmi­cally check whether it is of a speci.ed time complexity? While the answer is no in most cases, there is an interest­ing case where the answer is yes: verifying a time bound T (n) = C n + D, C, D . N, for a given one-tape Turing machine. 
There are at least two natural types of questions about whether a Turing machine obeys a given time bound: 
– 	
For a function T : N › R>0, does a given Turing machine run in time O(T (n))? 

– 	
For a function T : N › R>0, does a given Turing machine run in time T (n), i.e., does it make at most T (n) steps on all computations on inputs of length n for all n? 



It is a folklore that it is undecidable whether a Turing ma­chine runs in time O(1), thus the .rst question is undecid­able for all practical functions T . We state a generalization of this well known fact in the dissertation and prove it using standard techniques. However, for the second question, it is not hard to see that it is decidable whether a given Tur­ing machine runs in time C for some constant C . N: we just need to simulate the given Turing machine on all the inputs up to the length C [2]. It would be interesting if the second question were decidable also for linear functions T . However, we prove that it is decidable whether a multi-tape Turing machine runs in time T (n) if and only if we have the “eccentric” case T (n0) < n0 + 1 for some n0 . N. The time bound n + 1 is special because it minimally enables a multi-tape Turing machine to mark time while simulating another Turing machine. The timekeeping can be done on the input tape by just moving the head to the right until the blank symbol at the end marks n + 1 steps, while the other tapes are used for the simulation. But what if the simulation has to be performed on the same tape as the timekeeping, i.e., how much time do we need for a one-tape Turing ma­chine to count steps and simulate another Turing machine? We show in [2] that .(n log n) time is enough: 
Let T : N › R>0 be a function such that T (n) = .(n log n) and, for all n . N, it holds T (n) . n+ 1. Then it is undecidable whether a given one-tape Turing machine runs in time T (n). 
We also provide a nice contrast [2]: 
For any “nice” function T : N › R>0, T (n) = o(n log n), it is decidable whether a given one-tape Tur­ing machine runs in time T (n). 
Hence, a one-tape Turing machine that runs in time T (n) = o(n log n) cannot count steps while simulating another Turing machine. There is another well known fact about one-tape Turing machines that makes the time bounds .(n log n) special: these bounds are the tightest that al­low a one-tape Turing machine to recognize a non-regular language [4]. 
An interesting fact is that one-tape Turing machines that run in time o(n log n) actually run in linear time [2, 4]. Thus, we can conclude that the most natural algorithmi­cally veri.able time bounds for one-tape Turing machines are the linear ones. This motivates the analysis of the com­putational complexity of the following problems parame­terized by integers C, D . N. The problem H A LT1 is
C n+D 

de.ned as 
Given a one-tape NTM*, does it run in time C n + D? 
*NTM is an abbreviation for non-deterministic Turing machine. Until 

and the problem D -HA LT1 is de.ned as 
C n+D 
Given a one-tape DTM†, does it run in time C n + D? 
For the analyses of the problems HA LT1 and
C n+D 

D-HA LT1 , we .x an input alphabet ., |.| . 2, and 
C n+D 

a tape alphabet . . .. It follows that the length of most standard encodings of q-state one-tape Turing machines is O(q2). To make it simple, we assume that each code of a q-state one-tape Turing machines has length .(q2) and when we will talk about the complexity of the problems HA LT1 , we will always use q as the parameter to mea-
C n+D 

sure the length of the input. We prove the following [3]. 
For all integers C . 2 and D . 1, all of the following holds. 
1. The problems HA LT1 and D -H A LT1 are 
C n+D C n+D 
co-NP-complete. 
2. The problems HA LT1 and D -H A LT1 
C n+D cannot
C n+D be solved in time o(q(C-1)/4) by multi-tape NTMs. 
3. The complements of the problems HA LT1 
C n+D and D-HA LT1 can be solved in time
C n+D 
O(qC+2) by multi-tape NTMs. 

4. 
The complement of the problem HA LT1 

C n+D cannot be solved in time o(q(C-1)/2) by multi-tape NTMs. 

5. 
The complement of the problem D-HA LT1 


C n+D cannot be solved in time o(q(C-1)/4) by multi-tape NTMs. 

To put the theorem in short, the problems HA LT1 
C n+D and D -H A LT1 are co-NP-complete with a non-
C n+D 

deterministic and co-non-deterministic time complexity 
lower bound .(q0.25C-1) and a co-non-deterministic time C+2).
complexity upper bound O(q
The main techical tools in the analyses of one-tape Tur­ing machines that we used were crossing sequences and diagonalization. We argue that our main results are proved with techniques that relativize. 

References 
[1] D. 	Gajser. Verifying Time Complexity of Turing Machines. FMF UL, 2015. Thesis also available on http://eccc.hpi­web.de/static/books/Verifying_Time_Complexity_of _Turing_Machines/. 
[2] D. Gajser. 	Verifying time complexity of Turing ma­chines. Theor. Comput. Sci., 600:86 – 97, 2015. 
[3] D. Gajser. 	Verifying whether one-tape Turing ma­chines run in linear time. ECCC, TR15-036, 2015. 
this point it was irrelevant whether the Turing machines were determinis­tic or non-deterministic. 
†DTM is an abbreviation for deterministic Turing machine. 

[4] G. Pighizzini. Nondeterministic one-tape off-line Tur­ing machines and their time complexity. J. Autom. Lang. Comb., 14(1):107–124, 2009. 

In memory of Marvin Minsky 


Picture source: Wikipedia. 
Wikipedia writes: Marvin Lee Minsky (August 9, 1927 – January 24, 2016) was an American cognitive scientist in the field of artificial intelligence(AI), and author of several texts on AI and philosophy. As a visionary “father of artificial intelligence” (in a Turing-like fashion) he was often an outspoken advocate for the view that humans would one day create machines whose intelligence would rival our own. He founded the Artificial Intelligence Laboratory -now known as the Computer Science and Artificial Intelligence Laboratory -and cofounded the Media Lab. He was recipient of several awards, including the IJCAI Award for Research Excellence in 1991 and the prestigious ACM A.M. Turing Award, an equivalent of a Nobel Prize for computer science. In the words of Nicholas Negroponte: "Marvin talked in riddles that made perfect sense, were always profound and often so funny that you would find yourself laughing days later. His genius was so self-evident that it defined 'awesome.' The Lab bathed in his reflected light." Born in New York City (recently hosting IJCAI'16), he attended the Ethical Culture Fieldston School, the Bronx High School of Science, Phillips Academy, and Harvard University. He then went to Princeton University, where he earned his Ph.D in mathematics in 1954 (the year Turing died). At the time of his death, he was professor emeritus at CSAIL and at the MIT Media Lab. Professor Minsky laid the foundation for the field of artificial intelligence by demonstrating the possibilities of imparting common-sense reasoning to computers. Fascinated by the mysteries of human intelligence and thinking, Professor Minsky saw no difference between the thinking processes of humans and those of machines. He specialized on computational ideas to characterize human psychological processes and produced theories on how to endow machines with intelligence. He modeled human perception and intelligence, and built practical robots. He designed and built some of the first visual scanners and mechanical hands with tactile sensors, and built the first randomly wired neural network learning machine, which he called Snarc. 
Informatica 40 (2016) 371–372 371 

As said by Alan Kay: “Marvin was one of the very few people in computing whose visions and perspectives liberated the computer from being a glorified adding machine to start to realize its destiny as one of the most powerful amplifiers for human endeavors in history”. Also: “He used to say, ‘You don’t really understand something if you only understand it one way’”. In this way, he also influenced the author of this memoriam to introduce the Principle and Paradox of Multiple Knowledge. Minsky had argued that several activities (if not most) would be vastly safer and simpler with manipulators driven locally by intelligent computers or remotely by human operators. He foresaw microsurgery could be done by surgeons who work at one end of a telepresence system at a comfortably large scale, which has become a regular practice. Minsky devoted large amount of attention to perceptrons, machine learning algorithms that capture some of the characteristics of neural behavior. Minsky, working with Seymour Papert, showed what perceptrons could and could not do; together they wrote the book Perceptrons, which is considered a foundational work in the analysis of artificial neural networks. However, some of his criticism of NN capabilities caused a research delay in that field. Minsky and Papert introduced childhood education using Logo, the educational programming language, and developed the first Logo "turtle" robot. One of Minsky’s best-known ideas centers on a Theory of Frames. He wrote, "the ingredients of most theories both in Artificial Intelligence and in Psychology have been on the whole too minute, local, and unstructured to account–either practically or phenomenologically – for the effectiveness of common-sense thought." He tried to address those issues by "pretending to have a unified, coherent theory" based on his proposal to label data-structures in memory as frames and considering how frames must work, individually and in groups. Today, frames are a major part of knowledge representation and reasoning schemes even though they are often named differently. Minsky and Papert also developed what came to be called The Society of Mind theory, which attempts to explain how intelligence could be a product of the interaction of simpler parts (in recent years Koch and Tonini kind of destroyed the idea that the smaller parts can be unintelligible). In 1986, Minsky published The Society of Mind, a seminal book on the theory written for a general audience. It proposed “that intelligence is not the product of any singular mechanism but comes from the managed interaction of a diverse variety of resourceful agents,” as he wrote on his website. Underlying that hypothesis was his and Professor 
Papert’s belief that there is no real difference between 
humans and machines. Humans, they maintained, are actually machines of a kind whose brains are made up of many semiautonomous but unintelligent “agents.” (Again pls note that the current mainstream holds that these agents can be rather simple, but still must have basic properties such as e.g. at least local consciousness to possibly result in a conscious integrated agent. But with this modification, the basic idea stands today as it did then.) Different tasks, they said, “require fundamentally different mechanisms.” Their theory was at time misunderstood that humans are machines, but more likely Minsky had in mind that one can build intelligent machines as Turing proposed. As an extension of the multiple theories Minsky published The Emotion Machine in 2006, a book analysing theories of how human minds work and suggesting alternative theories, often replacing simple one-level ideas with more complex multiple ones. He wrote that our resourceful intelligence arises from many ways of thinking (search, analogy, divide and conquer, elevation, reformulation, contradiction, simulation, logical reasoning, and impersonation) that are spread across many levels of mental activity (instinctive reactions, learned reactions, deliberative thinking, reflective thinking, self-reflective thinking, and self-conscious emotions). With all fantastic systems like Soar putting aside, we are still not able to fully implement his ideas. In the words of Patrick Winston: "Many years ago, when I was a student casting about for what I wanted to do, I wandered into one of Marvin's classes. Magic happened. I was awed and inspired. I left that class saying to 
myself, ‘I want to do what he does.’ I have been awed 
and inspired ever since. Marvin became my teacher, mentor, colleague, and friend. I will miss him at a level beyond description. " Note: This paper is to some extend assembled from available publications on this issue with emphasis on the multiple-view theories and the Principle of multiple knowledge, and a huge respect to Marvin Minsky from the author. 

JOŽEF STEFAN INSTITUTE 
Jožef Stefan (1835-1893) was one of the most prominent physicists of the 19th century. Born to Slovene parents, he obtained his Ph.D. at Vienna University, where he was later Director of the Physics Institute, Vice-President of the Vienna Academy of Sciences and a member of several sci­enti.c institutions in Europe. Stefan explored many areas in hydrodynamics, optics, acoustics, electricity, magnetism and the kinetic theory of gases. Among other things, he originated the law that the total radiation from a black body is proportional to the 4th power of its absolute tem­perature, known as the Stefan–Boltzmann law. 
The Jožef Stefan Institute (JSI) is the leading indepen­dent scienti.c research institution in Slovenia, covering a broad spectrum of fundamental and applied research in the .elds of physics, chemistry and biochemistry, electronics and information science, nuclear science technology, en­ergy research and environmental science. 
The Jožef Stefan Institute (JSI) is a research organisation for pure and applied research in the natural sciences and technology. Both are closely interconnected in research de­partments composed of different task teams. Emphasis in basic research is given to the development and education of young scientists, while applied research and development serve for the transfer of advanced knowledge, contributing to the development of the national economy and society in general. 
At present the Institute, with a total of about 900 staff, has 700 researchers, about 250 of whom are postgraduates, around 500 of whom have doctorates (Ph.D.), and around 200 of whom have permanent professorships or temporary teaching assignments at the Universities. 
In view of its activities and status, the JSI plays the role of a national institute, complementing the role of the uni­versities and bridging the gap between basic science and applications. 
Research at the JSI includes the following major .elds: physics; chemistry; electronics, informatics and computer sciences; biochemistry; ecology; reactor technology; ap­plied mathematics. Most of the activities are more or less closely connected to information sciences, in particu­lar computer sciences, arti.cial intelligence, language and speech technologies, computer-aided design, computer ar­chitectures, biocybernetics and robotics, computer automa­tion and control, professional electronics, digital communi­cations and networks, and applied mathematics. 
The Institute is located in Ljubljana, the capital of the in­dependent state of Slovenia (or S¦nia). The capital today is considered a crossroad between East, West and Mediter­ranean Europe, offering excellent productive capabilities and solid business opportunities, with strong international connections. Ljubljana is connected to important centers such as Prague, Budapest, Vienna, Zagreb, Milan, Rome, Monaco, Nice, Bern and Munich, all within a radius of 600 km. 
From the Jožef Stefan Institute, the Technology park “Ljubljana” has been proposed as part of the national strat­egy for technological development to foster synergies be­tween research and industry, to promote joint ventures be­tween university bodies, research institutes and innovative industry, to act as an incubator for high-tech initiatives and to accelerate the development cycle of innovative products. 
Part of the Institute was reorganized into several high-tech units supported by and connected within the Technol­ogy park at the Jožef Stefan Institute, established as the beginning of a regional Technology park "Ljubljana". The project was developed at a particularly historical moment, characterized by the process of state reorganisation, privati­sation and private initiative. The national Technology Park is a shareholding company hosting an independent venture-capital institution. 
The promoters and operational entities of the project are the Republic of Slovenia, Ministry of Higher Education, Science and Technology and the Jožef Stefan Institute. The framework of the operation also includes the University of Ljubljana, the National Institute of Chemistry, the Institute for Electronics and Vacuum Technology and the Institute for Materials and Construction Research among others. In addition, the project is supported by the Ministry of the Economy, the National Chamber of Economy and the City of Ljubljana. 
Jožef Stefan Institute Jamova 39, 1000 Ljubljana, Slovenia Tel.:+386 1 4773 900, Fax.:+386 1 251 93 85 WWW: http://www.ijs.si E-mail: matjaz.gams@ijs.si Public relations: Polona Strnad 
INFORMATICA 
AN INTERNATIONAL JOURNAL OF COMPUTING AND INFORMATICS 
INVITATION, COOPERATION 

Submissions and Refereeing 
Please register as an author and submit a manuscript at: http://www.informatica.si. At least two referees outside the au­thor’s country will examine it, and they are invited to make as many remarks as possible from typing errors to global philosoph­ical disagreements. The chosen editor will send the author the obtained reviews. If the paper is accepted, the editor will also send an email to the managing editor. The executive board will inform the author that the paper has been accepted, and the author will send the paper to the managing editor. The paper will be pub­lished within one year of receipt of email with the text in Infor­matica MS Word format or Informatica LATEX format and .gures in .eps format. Style and examples of papers can be obtained from http://www.informatica.si. Opinions, news, calls for conferences, calls for papers, etc. should be sent directly to the managing edi­tor. 

SUBSCRIPTION 
Please, complete the order form and send it to Dr. Drago Torkar, Informatica, Institut Jožef Stefan, Jamova 39, 1000 Ljubljana, Slovenia. E-mail: drago.torkar@ijs.si 
Since 1977, Informatica has been a major Slovenian scienti.c journal of computing and informatics, including telecommunica­tions, automation and other related areas. In its 16th year (more than twentytwo years ago) it became truly international, although it still remains connected to Central Europe. The basic aim of In­formatica is to impose intellectual values (science, engineering) in a distributed organisation. 
Informatica is a journal primarily covering intelligent systems in the European computer science, informatics and cognitive com­munity; scienti.c and educational as well as technical, commer­cial and industrial. Its basic aim is to enhance communications between different European structures on the basis of equal rights and international refereeing. It publishes scienti.c papers ac­cepted by at least two referees outside the author’s country. In ad­dition, it contains information about conferences, opinions, criti­cal examinations of existing publications and news. Finally, major practical achievements and innovations in the computer and infor­mation industry are presented through commercial publications as well as through independent evaluations. 
Editing and refereeing are distributed. Each editor can conduct the refereeing process by appointing two new referees or referees from the Board of Referees or Editorial Board. Referees should not be from the author’s country. If new referees are appointed, their names will appear in the Refereeing Board. 
Informatica web edition is free of charge and accessible at 
http://www.informatica.si. 
Informatica print edition is free of charge for major scienti.c, ed­ucational and governmental institutions. Others should subscribe. 

Informatica WWW: 

http://www.informatica.si/ 

Referees from 2008 on: 

A. Abraham, S. Abraham, R. Accornero, A. Adhikari, R. Ahmad, G. Alvarez, N. Anciaux, R. Arora, I. Awan, J. Azimi, C. Badica, Z. Balogh, S. Banerjee, G. Barbier, A. Baruzzo, B. Batagelj, T. Beaubouef, N. Beaulieu, M. ter Beek, P. Bellavista, K. Bilal, S. Bishop, J. Bodlaj, M. Bohanec, D. Bolme, Z. Bonikowski, B. Boškovi´c, M. Botta, 
P. Brazdil, J. Brest, J. Brichau, A. Brodnik, D. Brown, I. Bruha, M. Bruynooghe, W. Buntine, D.D. Burdescu, J. Buys, X. Cai, Y. Cai, J.C. Cano, T. Cao, J.-V. Capella-Hernández, N. Carver, M. Cavazza, R. Ceylan, A. Chebotko, 
I. Chekalov, J. Chen, L.-M. Cheng, G. Chiola, Y.-C. Chiou, I. Chorbev, S.R. Choudhary, S.S.M. Chow, K.R. Chowdhury, V. Christlein, W. Chu, L. Chung, M. Ciglariˇ
c, J.-N. Colin, V. Cortellessa, J. Cui, P. Cui, Z. Cui, D. Cutting, A. Cuzzocrea, V. Cvjetkovic, J. Cypryjanski, L. ˇCerepnalkoski, I. ˇc, G. Daniele, G. 
Cehovin, D. ˇCosi´Danoy, M. Dash, S. Datt, A. Datta, M.-Y. Day, F. Debili, C.J. Debono, J. Dediˇ
c, P. Degano, A. Dekdouk, H. Demirel, B. Demoen, S. Dendamrongvit, T. Deng, A. Derezinska, J. Dezert, G. Dias, I. Dimitrovski, S. Dobrišek, 
Q. Dou, J. Doumen, E. Dovgan, B. Dragovich, D. Drajic, O. Drbohlav, M. Drole, J. Dujmovi´c, O. Ebers, J. Eder, 
S. Elaluf-Calderwood, E. Engström, U. riza Erturk, A. Farago, C. Fei, L. Feng, Y.X. Feng, B. Filipiˇ
c, I. Fister, I. Fister Jr., D. Fišer, A. Flores, V.A. Fomichov, S. Forli, A. Freitas, J. Fridrich, S. Friedman, C. Fu, X. Fu, T. Fujimoto, G. Fung, S. Gabrielli, D. Galindo, A. Gambarara, M. Gams, M. Ganzha, J. Garbajosa, R. Gennari, G. Georgeson, N. Gligori´car, M. Grgurovi´
c, S. Goel, G.H. Gonnet, D.S. Goodsell, S. Gordillo, J. Gore, M. Gr ˇc, D. Grosse, Z.-H. Guan, D. Gubiani, M. Guid, C. Guo, B. Gupta, M. Gusev, M. Hahsler, Z. Haiping, A. Hameed, C. Hamzaçebi, Q.-L. Han, H. Hanping, T. Härder, J.N. Hatzopoulos, S. Hazelhurst, K. Hempstalk, J.M.G. Hidalgo, J. Hodgson, M. Holbl, M.P. Hong, G. Howells, M. Hu, J. Hyvärinen, D. Ienco, B. Ionescu, R. Irfan, N. Jaisankar, D. Jakobovi´c, K. Jassem, I. Jawhar, Y. Jia, T. Jin, I. Jureta, .. Juriˇci´c, S. K, S. Kalajdziski, Y. Kalantidis, B. Kaluža, 
D. Kanellopoulos, R. Kapoor, D. Karapetyan, A. Kassler, D.S. Katz, A. Kaveh, S.U. Khan, M. Khattak, V. Khomenko, E.S. Khorasani, I. Kitanovski, D. Kocev, J. Kocijan, J. Kollár, A. Kontostathis, P. Korošec, A. Koschmider, D. Košir, J. Kovaˇc, A. Krajnc, M. Krevs, J. Krogstie, P. Krsek, M. Kubat, M. Kukar, A. Kulis, A.P.S. Kumar, H. Kwa´
snicka, W.K. Lai, C.-S. Laih, K.-Y. Lam, N. Landwehr, J. Lanir, A. Lavrov, M. Layouni, G. Leban, 
A. Lee, Y.-C. Lee, U. Legat, A. Leonardis, G. Li, G.-Z. Li, J. Li, X. Li, X. Li, Y. Li, Y. Li, S. Lian, L. Liao, C. Lim, J.-C. Lin, H. Liu, J. Liu, P. Liu, X. Liu, X. Liu, F. Logist, S. Loskovska, H. Lu, Z. Lu, X. Luo, M. Luštrek, I.V. Lyustig, S.A. Madani, M. Mahoney, S.U.R. Malik, Y. Marinakis, D. Marinciˇˇ
c, J. Marques-Silva, A. Martin, D. Marwede, M. Matijaševi´
c, T. Matsui, L. McMillan, A. McPherson, A. McPherson, Z. Meng, M.C. Mihaescu, V. Milea, N. Min-Allah, E. Minisci, V. Miši´c, A.-H. Mogos, P. Mohapatra, D.D. Monica, A. Montanari, A. Moroni, J. Mosegaard, M. Moškon, L. de M. Mourelle, H. Moustafa, M. Možina, M. Mrak, Y. Mu, J. Mula, D. Nagamalai, 
M. Di Natale, A. Navarra, P. Navrat, N. Nedjah, R. Nejabati, W. Ng, Z. Ni, E.S. Nielsen, O. Nouali, F. Novak, B. Novikov, P. Nurmi, D. Obrul, B. Oliboni, X. Pan, M. Panˇcur, W. Pang, G. Papa, M. Paprzycki, M. Paraliˇc, B.-K. Park, P. Patel, T.B. Pedersen, Z. Peng, R.G. Pensa, J. Perš, D. Petcu, B. Petelin, M. Petkovšek, D. Pevec, M. Piˇcan, M. Polo, V. Pomponiu, E. Popescu, D. Poshyvanyk, B. Potoˇ
culin, R. Piltaver, E. Pirogova, V. Podpeˇcnik, 
R.J. Povinelli, S.R.M. Prasanna, K. Pripuži´c, G. Puppis, H. Qian, Y. Qian, L. Qiao, C. Qin, J. Que, J.-J. Quisquater, C. Rafe, S. Rahimi, V. Rajkoviˇc, J. Ramaekers, J. Ramon, R. Ravnik, Y. Reddy, W. 
c, D. Rakovi´Reimche, H. Rezankova, D. Rispoli, B. Ristevski, B. Robiˇ
c, J.A. Rodriguez-Aguilar, P. Rohatgi, W. Rossak, I. Rožanc, J. Rupnik, S.B. Sadkhan, K. Saeed, M. Saeki, K.S.M. Sahari, C. Sakharwade, E. Sakkopoulos, P. Sala, 
M.H. Samadzadeh, J.S. Sandhu, P. Scaglioso, V. Schau, W. Schempp, J. Seberry, A. Senanayake, M. Senobari, 
T.C. 
Seong, S. Shamala, c. shi, Z. Shi, L. Shiguo, N. Shilov, Z.-E.H. Slimane, F. Smith, H. Sneed, P. Sokolowski, 

T. 
Song, A. Soppera, A. Sorniotti, M. Stajdohar, L. Stanescu, D. Strnad, X. Sun, L. Šajn, R. Šenkeˇrík, M.R. Šikonja, J. Šilc, I. Škrjanc, T. Štajner, B. Šter, V. Štruc, H. Takizawa, C. Talcott, N. Tomasev, D. Torkar, S. Torrente, M. Trampuš, C. Tranoris, K. Trojacanec, M. Tschierschke, F. De Turck, J. Twycross, N. Tziritas, W. Vanhoof, P. Vateekul, L.A. Vese, A. Visconti, B. Vlaoviˇc, M. Vozalis, P. Vraˇc, C.-H. 


c, V. Vojisavljevi´car, V. Vrani´Wang, H. Wang, H. Wang, H. Wang, S. Wang, X.-F. Wang, X. Wang, Y. Wang, A. Wasilewska, S. Wenzel, V. Wickramasinghe, J. Wong, S. Wrobel, K. Wrona, B. Wu, L. Xiang, Y. Xiang, D. Xiao, F. Xie, L. Xie, Z. Xing, H. Yang, X. Yang, N.Y. Yen, C. Yong-Sheng, J.J. You, G. Yu, X. Zabulis, A. Zainal, A. Zamuda, M. Zand, Z. Zhang, 
Z. Zhao, D. Zheng, J. Zheng, X. Zheng, Z.-H. Zhou, F. Zhuang, A. Zimmermann, M.J. Zuo, B. Zupan, M. Zuqiang, B. Žalik, J. Žižka, 


Informatica 

An International Journal of Computing and Informatics 
Web edition of Informatica may be accessed at: http://www.informatica.si. 
Subscription Information Informatica (ISSN 0350-5596) is published four times a year in Spring, Summer, 
Autumn, and Winter (4 issues per year) by the Slovene Society Informatika, Litostrojska cesta 54, 1000 Ljubljana, 
Slovenia. 
The subscription rate for 2016 (Volume 40) is 

– 
60 EUR for institutions, 


– 
30 EUR for individuals, and 



– 
15 EUR for students 
Claims for missing issues will be honored free of charge within six months after the publication date of the issue. 



Typesetting: Borut Žnidar. 
Printing: ABO gra.ka d.o.o., Ob železnici 16, 1000 Ljubljana. 


Orders may be placed by email (drago.torkar@ijs.si), telephone (+386 1 477 3900) or fax (+386 1 251 93 85). The 
payment should be made to our bank account no.: 02083-0013014662 at NLB d.d., 1520 Ljubljana, Trg republike 
2, Slovenija, IBAN no.: SI56020830013014662, SWIFT Code: LJBASI2X. 

Informatica is published by Slovene Society Informatika (president Niko Schlamberger) in cooperation with the 
following societies (and contact persons): 
Slovene Society for Pattern Recognition (Simon Dobrišek) 
Slovenian Arti.cial Intelligence Society (Mitja Luštrek) 
Cognitive Science Society (Olga Markiˇ

c) Slovenian Society of Mathematicians, Physicists and Astronomers (Marej Brešar) Automatic Control Society of Slovenia (Nenad Muškinja) Slovenian Association of Technical and Natural Sciences / Engineering Academy of Slovenia (Stane Pejovnik) ACM Slovenia (Matjaž Gams) 
Informatica is .nancially supported by the Slovenian research agency from the Call for co-.nancing of scienti.c periodical publications. 
Informatica is surveyed by: ACM Digital Library, Citeseer, COBISS, Compendex, Computer & Information Systems Abstracts, Computer Database, Computer Science Index, Current Mathematical Publications, DBLP Computer Science Bibliography, Directory of Open Access Journals, InfoTrac OneFile, Inspec, Linguistic and Language Behaviour Abstracts, Mathematical Reviews, MatSciNet, MatSci on SilverPlatter, Scopus, Zentralblatt Math 

Volume 40 Number 3 September 2016 ISSN 0350-5596 


Editors’ Introduction to the Special Issue on "Virtual 
Reality in Cultural Heritage" Recommender system for virtual assistant supported museum tours Virtual Assistant Platform 
Using a Natural User Interface to Enhance the Ability to Interact with Reconstructed Virtual Heritage Environments 
Building a 3D Interactive Walkthrough in a Digital 
Storytelling Classroom Experience Using Mixed Reality and Natural Interaction in Cultural Heritage Applications 
An Interactive Digital Storytelling Approach to Explore Books in Virtual Environments 
End of Special Issue / Start of normal papers 
IJCAI 2016 -The best AI times ever? 
Statistic-Based Dynamic Complexity Measurement for Web Service System Adaptive Coherence-enhancing Diffusion Flow for 
Color Images 
Rough-Mereology Framework for Making Medical Treatment Decisions Based on Granular Computing Tie Persistence in Academic Social Networks 
A Temporal Perspective on the Paradox of Pinocchio’s Nose Verifying Time Complexity of Turing Machines 
M. Carrozzino, M. Duguleana A. Tav ˇcar, A. Csabam, E. Butila D. Kužnar, A. Tav ˇcar, J. Zupan ˇci ˇc, M. Duguleana S. Butnariu, A. Georgescu, F. Gîrbacia  277 279 285 291  
M. Carrozzino, C. Evangelista, R. Galdieri R. Brondi, M. Carrozzino, C. Lorenzini, F. Tecchia C. Lorenzini, M. Carrozzino, C. Evangelista, M. Maltese  303 311 317  
M. Gams C. Mao  323 325  
V.B.S. Prasath  337  
M.M. Eissa, M. Elmogy, M. Hashem  343  
D. Mohdeb, A. Boubetra, M. Charikhi M. Gams, E. ˇCernˇciˇc, A. Montanari D. Gajser  353 365 369  

In memory of Marvin Minsky 
Informatica 40 (2016) Number 3, pp. 277–373