The use of simple graphs and cliques for analysis of cartographic eye-tracking data

Abstract

Usability testing with the use of eye-tracking technology is now emerging. Measuring point of gaze is employed in different fields of research and helps to solve real world problems. One of these areas is cartography. In addition to traditional methods of analyses of eye-tracking data, as attention maps and gaze plots are, a more sophisticated method exists - scanpath comparison. Many different approaches to scanpath comparison exist. One of the most frequently used is String Edit Distance, where the gaze trajectories are replaced by the sequences of visited Areas of Interest. In cartography, these Areas of Interest could be marked around specific parts of maps - map composition elements. We have developed an online tool called ScanGraph which output is visualized as a simple graph, and similar groups of sequences are displayed as cliques of this graph. ScanGraph uses modified Levenshtein distance and Needleman-Wunsch algorithms for calculating the similarities between sequences of visited Areas of Interest. Cliques in the graph are sought with the use of the exhaustive algorithm. ScanGraph functionality is presented in the example of cartographic study dealing with uncertainty in maps. Stimuli in the study contained several visualization methods of uncertainty and eye-tracking experiment with 40 respondents was performed. With the use of ScanGraph, groups of participants with similar strategy were identified.

-

Eye-tracking is one of the most precise and objective methods of usability studies. The term usability is defined by ISO 9241-11 as “the effectiveness, efficiency, and satisfaction, with which specified users achieve specified goals in particular environments”. To be able to derive qualitative or quantitative measures of the user attitudes to the product, many evaluation methods exists: focus group studies, interview, direct observation, think-aloud protocol, screen capturing and eye-tracking [ 1 ]. Each of the methods for studying usability has its advantages and disadvantages. Methods of focus groups and interview use a direct contact with the user. They are based on a targeted questioning and recording of discussions and reactions of individuals or groups of respondents to a particular product. A very important method of usability assessment is Think-aloud. Participants verbally describe the process of particular task solving and also their feelings [ 2 ]. In the above methods, the problem is the fact that participants are not aware of all processes, and not all processes can be simply expressed in words. The information that respondents communicate during an interview or fill in the questionnaire may not correspond to reality, although respondents believe their answers [ 3 ]. Cognitive load of the respondent during a thinkaloud method can be so large that it affects his interaction with the map. In contrast, during eye-movement recording, the cognitive load associated with self-reporting is eliminated. Eye-tracking can be considered an objective method because recording eye movements does not rely on self-reporting [ 4 ]. A combination of different methods is used very often (i.e. [ 5 ] or [ 6 ]).

Hammoud and Mulligan [ 7 ] state that the beginning of the scientific study of eye movement begun at the end of the 19th century, when many methods for measuring eye movements were developed. Some of these methods were based on a mechanical transmission of the position information of the eye [ 8 ], others use study of photographs [ 9 ]. Most of the modern eye-trackers work on the principle of non-contact recording of the pupil and corneal reflection [ 10 ]. Eyetracker is usually located below the monitor displaying studied stimuli. This unit incorporates one or more infrared light that shines in the direction of the user. The apparatus also includes a camera that captures the user's eyes. The center of the pupil and the reflection of infrared light is found by image recognition. From the relative positions of these two points, the device calculates the direction of view (Point of Regard).

Eye-tracking is used in many areas. The most common are psychological studies, medicine, HCI (Human-Computer Interaction), marketing, usability studies and also cartography.

Although the eye-tracking was firstly used for the evaluation of maps and cartographic works in the late 50s of the 20th century [ 11 ], it is increasingly used in the last ten to fifteen years. The reason is the decreasing cost of equipment and the development of computer technology, which allows faster and more efficient analysis of the measured data. The eye-tracking in cartography can be used for evaluation of map portals [ 5 ], meteorological maps [ 12 ], for analysis of text labels on the map [ 13 ] or 3D visualization in cartography [ 14 ].

In most of the studies, measured data were evaluated with the use of statistical analysis of eye-tracking metrics. For visualization of the data mostly only basic visualization methods such as Scanpath or Heatmaps were used. In some cases, the most sophisticated method of analysis is needed.

The example of this sophisticated method is Scanpath Comparison. This method can be used in the situation when the similarity between different participants’ strategy is investigated. The beginning of the interest about distinctive scanning pattern can be found in the study of Noton and Stark [ 15 ], who reported a qualitative similarity in eyemovements when people viewed line drawings on multiple occasions. The scanpath consists of sequences of alternating saccades and fixations that repeat themselves when a respondent is viewing stimuli. Scanpath comparison methods can be divided into six groups (String Edit Distance, ScanMatch, Sample-based measures, Linear distance, MultiMatch and Cross-recurrence quantification analysis). The comparison of these methods is described in [ 16 ]. One of the most frequently used methods is String Edit Distance, which is used to measure the dissimilarity of character strings. For the use of String Edit Distance, the grid or Areas of Interest (AOI) have to be marked in the stimulus. The gaze trajectory (scanpath) is then replaced by a character string representing the sequence of fixations with characters for AOIs they hit. Only 10 percent of the scanpath duration is taken up by the collective duration of saccadic eye-movements. Fixations took 90 percent of the total viewing period [ 17 ]. 2

Methods

ScanGraph is a web application developed by authors of the paper. Its purpose is to analyse similarities between sequences of visited Areas of Interest from eye-tracking data. It is designed to load data directly from open-source application OGAMA [ 18 ], so no additional data preparation is needed. The motivation for the creation of the application was the lack of any other tool which will allow finding groups of participants with a similar strategy of stimuli observation based on the given degree of similarity. The interface of ScanGraph is displayed in Figure 1. The application is freely available at www.eyetracking.upol.cz/scangraph. More information about the use of the application is available in [ 19 ] and needed principles are described below. Let : Σ ∗ Σ ∗ → be a distance function measuring the distance between two given sequences (words) , ∈ Σ ∗. We require to have these properties: , , , , , , (reflexivity) (symmetry)

(triangle inequality) ScanGraph uses two distance functions based on a Levenshtein distance and Needleman-Wunsch algorithm.

Levenshtein distance is named after the Russian scientist Vladimir Levenshtein [ 20 ]. Levenshtein distance between two strings , , … , | |; , , … , | | of the length || and || (let us denote , ) is the number of deletions, insertions, or substitutions needed to transform source string into target string. Hence, , if and only if the strings are equal and , max ||, || if and only if there is any correspondence between the strings. The value of Levenshtein distance is increasing with larger differences between the strings. The modified Levenshtein distance function ´, used by the ScanGraph is defined by this equation: ´ ,

, max| |, | | .

The other used metric of sequence alignment is called NeedlemanWunsch algorithm [ 21 ] with its scoring system. , The Needleman-Wunsch algorithm (let us denote its value ) searches for concordant elements between two strings , , … , | |; , , … , | | of the length || and || . The basic scoring system used for our needs is given by Match reward equal to , Gap cost equal and Mismatch penalty equal to . Hence, , min ||, || , when is a subset of or is a subset of . The value of , is increasing with the similarity between the strings.

The modified Needleman-Wunsch algorithms ´, the ScanGraph is defined by this equation: used by ´, .

The values of ´, , ´, ∈ , express the degree of similarity. The higher the value, the greater similarity. The matrix formed by these values is constructed. The user sets a value, which represents the minimal desired degree of similarity. This value is called the parameter and is denoted as . Hence, the adjacency matrix of the graph is created from the matrix according to this relation: , if , otherwise.

Groups of sequences with a degree of similarity higher or equal to the desired parameter are equivalent to cliques in the given graph .

ScanGraph seeks the cliques as submatrices the adjacency matrix order , , where , … , , and there doesn’t exist any matrix ’ ⊃ condition. order

of , ∀, ∈ with the same

Maximal clique problem is - complete problem [ 22 ]. Hence, the algorithm doesn’t run in a polynomial time. When the computing time is too long, the greedy heuristic is used. 3

Example case study

Analysis of recorded eye-tracking data using ScanGraph can be employed in every case, where it is appropriate to compare different groups of respondents. Despite the fact that ScanGraph is quite new, it was used for several case studies yet. Analysis of differences between cartographers and non-cartographers observing different map compositions was performed in [ 19 ]. Differences between males and females during searching for point symbol in a map were found in [ 23 ]. Snopková [ 24 ] analysed differences of map reading between people with normal vision and with colour-blind participants. Apparently, ScanGraph can also be used in other fields of research (not only cartography). Pulkrtová [ 25 ] used it in her psychological thesis dealing with the different perception of red colour by males and females. Hájková [ 26 ] used ScanGraph in the study at Department of Physiotherapy, University Hospital Olomouc with patients after brain stroke. She compared the control group with two groups of patients with different types of stroke.

In this paper, possibilities of Scangraph will be presented on the example of cartographic study dealing with the uncertainty visualization of maps. Uncertainty is seen as vagueness, randomness of conditions or result of particular processes and phenomena. The concept of uncertainty is also quite often used to describe little certainty about a particular phenomenon in maps [ 27 ]. Many approaches and methods of uncertainty visualization have been developed based for example on Bertin’s theory of graphic variables and combining both static and dynamic elements of visualization [ 28 ].

The case study uses data from master thesis [ 29 ]. In this thesis, sets of cartographic symbols for visualization of an uncertainty of point, lines and areas were created. Point symbols have been set up according to the study of [ 30 ]. These symbols were placed into maps, and these maps were used as stimuli for the eye-tracking experiment and online questionnaire. The aim of the thesis was to find which visualizations are the most comprehensible for the map reader. The experiment was conducted with 40 participants. Twenty of them were students of cartography, twenty of them were respondents with no education in cartography. In the thesis, eyetracking metrics (Trial Duration, Gaze Length) and accuracy of answers were compared to all stimuli. Total of 27 maps with point symbols were used in the experiment. Thirteen of them were depicting the single phenomenon; eight were representing the combination of more phenomenon. The last six maps were showing the spatial and temporal uncertainty separately.

In the beginning, user observation of stimulus BK07 was analysed. In this case, the map contained 16 point symbols representing the possible occurrence of three animal species (wild boar, hare, and fox) with different level of uncertainty. The task was to find the most probable locality, where it is possible to found each animal. The legend for all three species was located on the right side of the stimulus. The left part contained an orthophoto map with point symbols. Areas of Interest were marked around the map field and each part of the legend (see Figure 2).

Gaze data were converted to the strings of characters according to the position of fixations in marked Areas of Interest in OGAMA software [ 18 ]. The process of conversion is displayed in Figure 3. From the scanpaths (left side of Figure 3), the character strings are generated. For the analysis, collapsed strings (with no consecutive characters - right part of Figure 3) will be used.

In the ScanGraph interface, modified Levenshtein computation method was selected. As is mentioned above, collapsed data were used for analysis. The parameter (see above for more information) was set up to . (representing the similarity at least % ). Six non-trivial cliques were found in the resulting graph (see Figure 4).

The largest clique contained five sequences (participants). Three of them were cartographers; two belonged to the group of non-cartographers. The strategy of these participants can be described as an ideal one. All of them started in the center of the screen (AOI D). Then they moved their gaze to all parts of the legend (AOI A, B, and C) and then they moved back to the map field (AOI D) and sought for the correct answer. Participants P13 and P17 made an additional fixation in the AOI A after looking into AOI B.

In the clique with four participants, the situation was similar. In this case, all sequences were “DABCD” The only exception was participant P20, who performed an additional fixation in AOI B at the end of stimulus observation.

The rest of displayed non-trivial cliques contained only two participants. All of these participants omitted AOI C during their view of the stimulus. The AOI C was marked around the last part of the legend (representing the possible occurrence of the fox). Because all legends looked similar, these participants decided not to look into the last part.

The rest of participants from the experiment were isolated nodes. That means that their sequence of visited Areas of Interest was not similar to any other sequence (according to parameter . ). An example of these sequences can be participant P29 with sequence “DABADADADADA BDBCBDAD”, P30 with sequence DAD, or P43, who spent the whole observation time in the map field (sequence “D”). All these three participants belonged to the group of noncartographers.

With the use of ScanGraph, we were able to find quickly the group of participants, who observed the stimuli in a similar way. After examination of the particular sequences, it was discovered that this sequence was the “ideal one”.

The second analysed map from the experiment was stimulus C03. The map, in this case, depicted the possible occurrence of the fox. Unlike of the previous stimuli, spatial and temporal uncertainty was displayed with two different map symbols. The task of respondents was to find a place, where is the most probable possibility (both spatial and temporal) to found a fox. Areas of Interest were again marked in the stimuli (see Figure 5). AOI A represented the correct answer. AOI B was marked around the symbol of the fox, which also served as a map title (recorded incidence of foxes). Other two AOIs were marked around two parts of the legend (spatial uncertainty - AOI C and temporal uncertainty - AOI D). The last AOI (E) was marked around the map field (except the correct answer location).

The same settings of ScanGraph as in the previous example was used, only the parameter value was set up to . . This example contained more AOIs, so the lower similarity between sequences can be assumed. When we tried to use the same value of the parameter as in the previous example ( . ), only one clique containing two participants was found. Resulting graph can be seen in Figure 6.

Total of 13 non-trivial cliques were found in the output of ScanGraph. Interesting is the comparison between two cliques containing three participants. The first one is a clique with participants P14, P22, and P27. All of them belonged to the group of cartographers. The second clique with participants P16, P29 and P43 is highlighted in Figure 6. All these participants were non-cartographers. The difference between these cliques lies in the fact, that none of the noncartographers observed the AOI B marked around the map title. Students of cartography are taught to pay attention to the map title. Similar behaviour was found in another study comparing respondents’ reading of different map compositions [ 31 ]. Non-cartographers were almost entirely omitting the map title during a free-viewing task.

The longest common subsequence , of sequences (words) , is the sequence with maximal length | | such that there exist , … , and , … , such that ∀, : ⟹ ∧ and ∀ : .

The second possible algorithm, called Damerau– Levenshtein distance [ 32 ] is an enhancement of Levenshtein distance algorithm. In addition, it calculates with transitions. ,

The Damerau–Levenshtein distance , is a distance between two sequences , , given by counting the minimum number of operations needed to transform one string into the other, where an operation is defined as an insertion, deletion, or substitution of a single character, or a transposition of two adjacent characters. For example , against .

The final selection of the used metric will depend on the character of data and distribution of AOI within the stimuli.

Unless the calculation uses the exhaustive algorithm it finds an optimal solution with all non-trivial cliques in the given graph. The computational time of the exhaustive algorithm is . When the time exceeds the tolerable limit, greedy heuristic algorithm is used. The reliability of the results is arguable. For the purposes of eye-tracking data analyses, the higher value of similarity (hence lower number of edges) is investigated. Moreover, the Bron and Kerbosch algorithm [ 33 ] for maximal clique problem will be tested and compared to the currently used algorithm. 5

Conclusion

The paper describes the newly developed tool for the analysis of eye-movement data. Eye-movements are represented as sequences of fixations recorded in Areas of Interest marked in the stimuli. The application uses modified Levenshtein distance and Needleman-Wunsch algorithms and visualize the result in the form of a simple graph. Groups of participants with similar strategy are represented as cliques of this graph. The paper describes the principles of the computations. The functionality of the application is presented in the example of cartographic case study dealing with map uncertainty visualization.

The tool is called ScanGraph and is freely available at www.eyetracking.upol.cz/scangraph.

Acknowledgment

We would like to thank Michal Kučera, who's data were used for the case study. This paper was supported by projects of Operational Program Education for Competitiveness – European Social Fund (projects CZ.1.07/2.3.00/20.0170), of the Ministry of Education, Youth and Sports of the Czech Republic and the student project IGA_PrF_2016_008 of the Palacky University.

References

[1] Li , X. , Çöltekin , A. , Kraak , M. - J. ( 2010 ) Visual exploration of eye movement data using the space-timecube . In Geographic Information Science . Springer, pp. 295 - 309 .

[2] Dykes , J. , Maceachren , A. M. , Kraak , M. - J. ( 2005 ) Exploring geovisualization . Elsevier , 710 p.

[3] Coltekin , A. , Heil , B. , Garlandini , S. , Fabrikant , S. I. ( 2009 ) Evaluating the effectiveness of interactive map interface designs: a case study integrating usability metrics with eye-movement analysis . Cartography and Geographic Information Science , 36 ( 1 ), pp. 5 - 17 .

[4] Goldberg , J. H. , Kotval , X. P. ( 1999 ) Computer interface evaluation using eye movements: methods and constructs . International Journal of Industrial Ergonomics , 24 ( 6 ), pp. 631 - 645 .

[5] Alacam , Ö. , Dalci , M. ( 2009 ) A usability study of WebMaps with eye tracking tool: the effects of iconic representation of information. In Human-Computer interaction . New trends. Springer, pp. 12 - 21 .

[6] Cutrell , E. , Guan , Z. ( 2007 ) What are you looking for?: an eye-tracking study of information usage in web search . In Proceedings of the Proceedings of the SIGCHI conference on Human factors in computing systems, ACM , pp. 407 - 416 .

[7] Hammoud , R. I. , Mulligan , J. B. ( 2008 ) Introduction to Eye Monitoring . In Passive Eye Monitoring . Springer, pp. 1 - 19 .

[8] Delabarre , E. B. ( 1898 ) A method of recording eyemovements . The American Journal of Psychology , 9 ( 4 ), pp. 572 - 574 .

[9] Dodge , R. , Cline , T. S. ( 1901 ) The angle velocity of eye movements . Psychological Review , 8 ( 2 ), pp. 145 - 157 .

[10] Holmqvist , K. , Nyström , M. , Andersson , R. , Dewhurst , R. , Jarodzka , H., Van De Weijer, J. ( 2011 ) Eye tracking: A comprehensive guide to methods and measures . Oxford University Press, 537 p.

[11] Enoch , J. M. ( 1959 ) Effect of the size of a complex display upon visual search . JOSA , 49 ( 3 ), pp. 280 - 285 .

[12] Fabrikant , S. I. , Hespanha , S. R. , Hegarty , M. ( 2010 ) Cognitively inspired and perceptually salient graphic displays for efficient spatial inference making . Annals of the Association of american Geographers , 100 ( 1 ), pp. 13 - 29 .

[13] Ooms , K. , De Maeyer , P. , Fack , V. ( 2015 ) Listen to the Map User: Cognition, Memory, and Expertise . The Cartographic Journal.

[14] Popelka , S. , Dedkova , P. Extinct village 3D visualization and its evaluation with eye-movement recording . 2014. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).

[15] Noton , D. , Stark , L. ( 1971 ) Scanpaths in saccadic eye movements while viewing and recognizing patterns . Vision Research , 9//, 11( 9 ), pp. 928 - 929 .

[16] Anderson , N. C. , Anderson , F. , Kingstone , A. , Bischof , W. F. ( 2014 ) A comparison of scanpath comparison methods . Behavior research methods , pp. 1 - 16 .

[17] Bahill , A. T. , Stark , L. ( 1979 ) The trajectories of saccadic eye movements . Scientific American , 240 ( 1 ), pp. 108 - 117 .

[18] Voßkühler , A. , Nordmeier , V. , Kuchinke , L. , Jacobs , A. M. ( 2008 ) OGAMA (Open Gaze and Mouse Analyzer): open-source software designed to analyze eye and mouse movements in slideshow study designs . Behavior research methods , 40 ( 4 ), pp. 1150 - 1162 .

[19] Dolezalova , J. , Popelka , S. ( 2016 ) ScanGraph: A Novel Scanpath Comparison Method Using Visualization of Graph Cliques . Journal of Eye Movement Research , In print.

[20] Levenshtein , V. I. ( 1966 ) Binary codes capable of correcting deletions, insertions, and reversals . Soviet physics doklady , 10 ( 8 ), pp. 707 - 710 .

[21] Needleman , S. B. , Wunsch , C. D. ( 1970 ) A general method applicable to the search for similarities in the amino acid sequence of two proteins . Journal of molecular biology , 48 ( 3 ), pp. 443 - 453 .

[22] Gross , J. L. , Yellen , J. ( 2005 ) Graph theory and its applications . CRC press.

[23] Dolezalova , J. , Popelka , S. ( 2016 ) Evaluation of user strategy on 2D and 3D city maps based on novel scanpath comparison method and graph visualization . In Proceedings of the ISPRS 2016 , Prague.

[24] Snopková , D. ( 2016 ) Tvorba a užití map osobami se sníženou schopností rozpoznání barev . Brno, Masaryk University.

[25] Pulkrtová , T. ( 2016 ) Vliv červené barvy na vnímání atraktivity žen . Brno, Masaryk University.

[26] Hájková , M. ( 2016 ) Eye tracking vyšetření predilekce očních pohybů u pacientů po cévní mozkové příhodě . Olomouc, Palacký University Olomouc.

[27] Brus , J. ( 2013 ) Uncertainty vs. spatial data quality visualisations: a case study on ecotones . International Multidisciplinary Scientific GeoConference: SGEM: Surveying Geology & mining Ecology Management , 1 , pp. 1017 .

[28] Kubíček , P. , Šašinka , Č., Stachoň , Z. ( 2012 ) UNCERTAINTY VISUALIZATION TESTING . In Proceedings of the Proceedings of the 4th conference on Cartography and GIS , Sofia, T. BANDROVA , M. KONEČNÝ , G. ZHELEZOV eds., Bulgarian Cartographic Association , pp. 247 - 256 .

[29] Kučera , M. ( 2016 ) Uživatelské testování a optimalizace vizualizací nejistoty prostorových dat . Olomouc, Palacký University Olomouc 64 p.

[30] Maceachren , A. M. , Roth , R. E. , O'brien, J., Li , B. , Swingley , D. , Gahegan , M. ( 2012 ) Visual semiotics & uncertainty visualization: An empirical study . Visualization and Computer Graphics , IEEE Transactions on, 18 ( 12 ), pp. 2496 - 2505 .

[31] Brychtova , A. , Popelka , S. , Dobesova , Z. ( 2012 ) Eye - Tracking methods for investigation of cartographic principles . In Proceedings of the 12th International Multidisciplinary Scientific GeoConference and EXPO , Varna, pp. 1041 - 1048 .

[32] Damerau , F. J. ( 1964 ) A technique for computer detection and correction of spelling errors . Communications of the ACM , 7 ( 3 ), pp. 171 - 176 .

[33] Bron , C. , Kerbosch , J. ( 1973 ) Algorithm 457: finding all cliques of an undirected graph . Communications of the ACM , 16 ( 9 ), pp. 575 - 577 .