Eye-gaze data are generally expressed by sequences of fixations. Each fixation is recorded as a point with coordinates and gaze duration. The preprocessing step makes preparation for the next pattern mining procedures: outlier removal ensures the consistency of remaining scanpaths, AOI extraction facilitates a higher-level representation, center identification retains the spatial distribution of scanpath components.

Generally speaking, the barycenter of points in a cluster is regarded as the representative or examplar of the cluster. Likewise, we aggregate multiple scanpaths into a single one by computing the “barycenter” of the scanpath set. In other words, we try to calculate a representative scanpath that is the closest to individual scanpaths in terms of average distance. Mathematically, the representative scanpath is defined as follows:

where r is the representative scanpath, s′ is any scanpath that may become the representative scanpath, s is an individual scanpath in the given scanpath set sps, and Dist is a function calculating the distance or dissimilarity between two scanpaths.

Here we utilize Dynamic Time Warping (DTW) to measure scanpath distance. DTW was first put forward for speech recognition and then widely used in time series analysis (30). Traditional string matching algorithms like Needleman-Wunsch algorithm (31) and Levenshtein Distance (32) simply treat scanpaths as strings and need to additionally construct a cost matrix to take into account spatial proximity, while DTW already involves the construction. In most cases, scanpaths are recorded as sequences of components with coordinates. Given two scanpaths A=Am=<a1,a2,⋯,am> and B=Bn=<b1,b2,⋯,bn>, the DTW distance is recursively computed by the following formula:

where Ai, Bj are the subsequences of A and B, ai and bj are components of scanpaths A and B respectively, δ() is the Euclidean distance function. The distance or dissimilarity between scanpath A and B is:

It is difficult to directly get the optimal solution of Equation (1). Hence, we add the following constraints to make it feasible:

These constraints not only simplify the aggregation but also force the obtained scanpath to be more reasonable. The first constraint guarantees the aggregated scanpath is expressed at a higher level. The second and the third constraints ensure that the aggregated scanpath will not deviate too far from individual scanpaths. We propose two methods for scanpath aggregation.

Heuristic Method. The heuristic method first constructs a candidate set for each AOI. The candidate set contains all the potential subsequent AOIs for a certain AOI. In other words, AOIs in the candidate set for AOIi must follow AOIi in at least one individual scanpath. Then all the possible scanpaths are enumerated by extending scanpaths of 1 fixation to scanpaths of n fixations. A scanpath is extended by choosing an AOI from the candidate set of the last AOI on the scanpath and adding it to the end. When the occurrence count of a certain AOI is equal to its maximum occurrence count in individual scanpths, the AOI is removed from the candidate set and thus will not appear in later enumerated scanpaths. Finally, the scanpath with the smallest DTW from individual scanpaths is chosen from all the enumerated scanpaths as the representative. n is the specified maximum fixation number. When n is large enough, we can get the theoretically optimal result for Equation (2), which provides a lower bound of the average distance.

Candidate-constrained DTW Barycenter Averaging (CDBA) algorithm. Since the heuristic method is time and space consuming, we propose another algorithm for scanpath aggregation by imposing some constraints on the DTW Barycenter Averaging (DBA) algorithm (33) as an approximation (25). CDBA also needs to construct a candidate set for each AOI and adjust the set members like the heuristic method. Then it defines an initial average scanpath as the reference scanpath and then updates the reference scanpath iteratively. For each iteration, CDBA consists of two steps: computing DTW between every individual scanpath and the reference scanpath and updating the components of the reference scanpath.

The above two steps are repeated until the reference scanpath does not change. The process of CDBA is summarized in Algorithm 2.

After scanpath aggregation, we obtain an aggregated scanpath that can tell us not only which areas draw our attention but also the priority of attraction. In this section, we aim to embed gaze duration into the aggregated scanpath. To specify how long an AOI can hold our attention, we transform each individual scanpath (of fixations) into an AOI sequence (of clusters) and statistically analyze the gaze duration of each AOI for all the individual scanpaths. The gaze duration of each AOI in the aggregated scanpath is obtained by averaging the gaze duration of the same AOI in all the individual sequences. Note that when we analyze AOI duration, one and the same AOI appearing more than once in a sequence is regarded as different AOIs and will be distinguished by their appearing order in the sequence.

To investigate the rationality of representative scanpaths, we conduct experiments on two large public eye-tracking data sets, namely OSIE data set (34) and MIT1003 data set (35).

The key process in our framework is scanpath aggregation, which can be substituted by other methods like eMine (11), STA (13), SPAM (20) and IOC (22). The first three of them can not directly operate on scanpaths consisting of fixations with coordinates and need to convert scanpaths into character strings. IOC also relies on some preprocessing steps for scanpath quantization. To make sure the comparison is fair, we adopt the same preprocessing step in our framework. The outlier removal process averagely excludes 0.61 and 0.86 scanpaths per image for OSIE and MIT 1003 data sets, respectively. In addition, despite the outlier removal process, eMine still fails to produce any result for some images, so for eMine algorithm, we only consider cases in which eMine algorithm has final outputs. For SPAM algorithm, we set the minimum supporting number of subjects as the half of the total number, which may lead to more than one frequent subsequences, so we choose from these frequent subsequences the one that is optimal with regard to Equation (1) as the representative scanpath. For IOC algorithm, we adapt it for our framework by taking DTW as its distance function and choosing the scanpath with the smallest average DTW. For the heuristic method, we need to determine the specified maximum number n when enumerating all the possible scanpaths. Figure 3 shows average DTW varying with given maximum length n. For both data sets, when n is equal to or larger than 8, the average DTW does not change and the heuristic method can get the theoretically best results. So the maximum number is set as 8 in later discussion for the heuristic method unless otherwise stated.

Due to the high degree of viewing freedom, it is hard to define ground truth representative scanpaths. The only way to evaluate the rationality of the obtained scanpath is to compare it against each individual scanpath with the standard string-edit algorithm as suggested by Eraslan et al. (13, 14). More sophisticated methods to compare scanpaths like ScanMatch (27), MultiMatch (36), and ScanGraph (37) are also developed, facilitating the evaluation.

In our experiment, the evaluation of representative scanpaths is conducted at three different levels:

Analysis of Scanpath Length. Scanpath length reflects the frequency of attention shift. Figure 4 and Figure 5 analyze the length of representative scanpaths for both OSIE and MIT1003 datasets. From Figure 4 (a) and Figure 5 (a), we can find that length distributions of individual scanpaths are similar to normal distribution, which indicates that for only a small number of images, people concentrate on certain areas (hardly shift) or roam over the whole image (frequently shift) while for most images the shift frequency is relatively stable, neither too large nor too small. Thus the bell-shaped property should also be reflected by representative scanpaths. Considering that all the representative scanpaths are AOI based while individual scanpaths are fixations based, the absolute values of scanpath length may be different but the bell-shaped property of scanpath length distribution should be kept. However, eMine, STA and SPAM fail to retain this property and obtain right-tailed distributions. All of them are more likely to get shorter representative scanpaths, which reflect the pattern that for most images, subjects tend to concentrate on certain areas and hardly shift their attention. IOC, CDBA and the heuristic method can keep the bell-shaped distributions.

Analysis of Scanpath Shape. In this part, we evaluate the ability of representative scanpaths to reflect attention distribution and attention shift, that is, the shape of representative scanpaths. We measure this ability by computing the average distance (DTW) between the representative scanpath and all the actually recorded scanpaths as suggested by Le Meur et al. (24). Quantitative results are shown in Table 1. A smaller DTW means a better result. The average DTW between representative scanpaths obtained by the heuristic method and all the recorded scanpaths is the smallest. In other words, the heuristic method produces the best solutions for Equation (1), followed by CDBA and IOC. The results of statistical analysis are presented in Table 2, which shows there is a significant difference between the results of our proposed “barycenter” based methods (CDBA and heuristic) and other methods.

Analysis of Overall Scanpath Similarity. In this part, we estimate and assign gaze duration to scanpaths obtained in the aggregation step. Note that none of the existing algorithms except for STA have discussed representative scanpaths with gaze duration. Even though STA employs the duration information when identifying trending elements, it still focuses on the analysis of trending scanpaths and does not further analyze gaze duration. To make fair comparisons, we combine our gaze duration analysis method with all the methods proposed for scanpath aggregation, i.e., eMine, SPAM, STA and IOC. The overall scanpath similarity is evaluated by MultiMatch (Jarodzka et al., 2010) and ScanMatch (Cristino et al., 2010). MultiMatch compares scanpaths from five aspects: vector similarity, direction similarity, length similarity, position similarity and duration similarity. ScanMatch only outputs an integrated score reflecting order consistency, spatial proximity and duration similarity. The parameters involved in ScanMatch implementation are set as follows: Xbin = 24, Ybin = 18, Threshold = 3.5, GapValue = 0, TempBin = 100 (TempBin =0 when duration is not taken into account). We compare the representative scanpath with each actually recorded scanpath using both algorithms and compute the average scores. Table 3 shows the results on both datasets. The larger the scores, the better the results. Our proposed methods (CDBA* and Heuristic*) still outperform eMine, STA and SPAM, but the advantages of our methods over IOC are not so obvious. Then we further conduct statistical test on the ScanMatch results (with duration). The difference between the proposed methods and the first three methods, i.e., eMine, STA and SPAM, is significant on both data sets but this is not the case with IOC. It can be seen that although the heuristic method can get a smaller average distance in terms of DTW, scores of MultiMatch and ScanMatch are neck and neck with CDBA and IOC on both datasets. This may be caused by the fact that DTW directly takes Euclidean distance as elements in the cost matrix while both MultiMatch and ScanMatch conduct scanpath simplification or quantization before comparison.

In our experiment, we can regard the adaptation of IOC as constructing a candidate set that contains AOI-level scanpaths transformed from individual fixation-level scanpaths. In other words, IOC actually finds an optimal solution of Equation (1) under stricter constraints. In addition, CDBA and the heuristic method are also based on Equation (1), and the outputs of CDBA can actually be regarded as approximations of the heuristic results. Compared with the heuristic method, IOC chooses from a smaller candidate set while CDBA searches the set in a more efficient way, but these three algorithms share a similar idea, choosing a scanpath from a candidate scanpath set as the representative. In this sense, all the algorithms we discussed above can be categorized as follows: (1) “barycenter” based: IOC, CDBA, heuristic; (2) subsequence based: eMine, SPAM; (3) others: STA.

When evaluated by scanpath length, the “barycenter” based method can well keep the bell shaped distribution of scanpath length. The comparison by DTW also indicates that all the “barycenter” based methods can produce representative scanpaths similar to actually recorded individual scanpaths in scanpath shape. As for overall scanpath similarity, the “barycenter” based methods improve the performance by a large margin over others, which consolidates that “barycenter” based aggregated scanpaths are more suitable to be combined with gaze duration to get final representative scanpaths. In summary, representative scanpaths obtained by “barycenter” based methods can better describe viewing patterns.

Figures 6 shows the aggregated scanpaths obtained by different algorithms. In Figure 6, red circles represent AOIs. Yellow arrows indicate the direction and numbers indicate the order. Images 1009 and 1033 respectively contain only one conspicuous foreground object and three objects without many distractors in the background while image 1263 and image 1270 both contain multiple objects with complex background. eMine, STA and SPAM obviously produce shorter scanpaths that may not be able reflect complete viewing patterns. In particular, eMine only identifies one common AOI in all the individual scanpaths and fails to provide any information about attention shift for images 1009, 1033 and 1263. The “barycenter” based methods (IOC, CDBA and the heuristic method) produce identical results for images 1009 and 1263. For image 1009, the representative scanpaths show that attention is first attracted by the dog head, then transferred to the body and finally go back to the head. For image 1263, the pattern is that subjects are first attracted by faces, then linger between faces, next explore objects with which the female and the male are interacting (the food they are eating), and finally redirect their attention to human faces. For images 1033 and 1270, representative scanpaths obtained by IOC, CDBA and the heuristic method are a little different. It is difficult to conclude which scanpath can better describe the viewing pattern since they actually contain some common segments. Take image 1270 for example, all the three representative scanpaths start by an AOI located near image center, which is consistent with the well-known center bias. The main difference between obtained patterns lies in the priority of the AOI on the zip-top can and the AOI on the computer screen. The heuristic method and CDBA prioritizes the AOI on the zip-top can while IOC is on the contrary. Note that there are some letters on the can. Considering text is a top-down factor capable of guiding visual attention (38), the pattern obtained by the heuristic method and the CDBA algorithm may be more reasonable. In addition, although we do not have any so-called ground truth viewing pattern, the identified patterns seem to be congruent with human intuition and some verified findings such as center bias, top-down effect, etc, whether there are one or several foreground objects, simple or complex backgrounds. However, in some cases where the priorities of different visual stimuli are not clear (e.g., image 1033), the identified patterns can only provide limitedly useful knowledge.

Figure 7 visualizes obtained representative scanpaths obtained by our proposed methods (CDBA and huristic) with duration pattern for image i1182314083 from MIT1003 data set (35). The radius of red circles is proportional to the total gaze duration on the corresponding AOI. Figure 8 shows the duration patterns of individual scanpaths. It is can be seen that the duration pattern of the representative scanpath is visually consistent with the duration pattern of individual scanpaths and can reflect the group trend from an overall perspective.