Zhibin Hong
email: zhibin.hong@student.

Zhe Chen
email: zhe.chen@student.

Chaohui Wang
email: chaohui.wang@u-pem.fr

Xue Mei
email: xue.mei@tema.toyota.com

Danil Prokhorov
email: danil.prokhorov@tema.toyota.com

Dacheng Tao
email: dacheng.tao@uts.edu.au

MUlti-Store Tracker (MUSTer): a Cognitive Psychology Inspired Approach to Object Tracking

Keywords:

Variations in the appearance of a tracked object, such as changes in geometry/photometry, camera viewpoint, illumination, or partial occlusion, pose a major challenge to object tracking. Here, we adopt cognitive psychology principles to design a flexible representation that can adapt to changes in object appearance during tracking. Inspired by the well-known Atkinson-Shiffrin Memory Model, we propose MUlti-Store Tracker (MUSTer), a dual-component approach consisting of short-and long-term memory stores to process target appearance memories. A powerful and efficient Integrated Correlation Filter (ICF) is employed in the short-term store for short-term tracking. The integrated long-term component, which is based on keypoint matching-tracking and RANSAC estimation, can interact with the long-term memory and provide additional information for output control. MUSTer was extensively evaluated on the CVPR2013 Online Object Tracking Benchmark (OOTB) and ALOV++ datasets. The experimental results demonstrated the superior performance of MUSTer in comparison with other state-of-art trackers.

Introduction

Object tracking is relatively easy for humans. Humans respond quickly to visual information by recognizing temporal consistency and memorizing useful visual features to recover from tracking failures when the target leaves fieldof-view. Memory is one of the most powerful, but least well understood, functions of the human brain. With the sophisticated memory system, humans are capable of adapting to complex environments and behaving stably and consistently when facing temporal issues. We hypothesize that the principles of biological memory can be exploited to design solutions to tracking problems, which can be regarded as a time-series motion estimation problem.

Although how human memory works is still not fully understood, several memory models have been proposed. We focus on the well-known Atkinson-Shiffrin Memory Model (ASMM, also known as the multi-store model, outlined in Figure 1), which was proposed by Atkinson and Shiffrin in 1968 [START_REF] Atkinson | Human memory: A proposed system and its control processes[END_REF] to explain the basic structure and function of memory. The ASMM proposes that memory exists as three separate stages: sensory memory, short-term memory, and long-term memory. First, external stimuli are delivered to the "sensory register", at which point the original input signals are transformed into chemical and physical signals for processing within the biological system. Acceptable input information is then sent to the short-term store, where information undergoes the processes of encoding, rehearsing, retrieving, and responding, after which the system can output a reasonable and appropriate response. However, the short-term store does not retain information for a long time. Long-term memorizing is actually performed by the longterm store; if a particular pattern is received repeatedly, the long-term store is activated and the pattern information is retained. Once memorized, the pattern is maintained for a certain period of time but forgotten if not reinforced. As a result, the information inside the long-term store is a stable and consistent representation of current event sequences.

By combining short-term processing and long-term maintenance, this memory model produces sensitive and stable responses to complex inputs. When the external environment is continuous and steady, short-term store processing is fast and produces immediate responses. On the other hand, if the model encounters a sudden change in input, information remembered by the long-term store is retrieved, which helps to stabilize the output. This cooperation allows humans to take reasonable actions in response to different and changing environments.

The online tracking research community have developed a number of trackers. Some [START_REF] Hare | Struck: Structured output tracking with kernels[END_REF][START_REF] Henriques | Highspeed tracking with kernelized correlation filters[END_REF][START_REF] Hong | Tracking using multilevel quantizations[END_REF][START_REF] Kwon | Robust visual tracking with double bounding box model[END_REF][START_REF] Oron | Extended lucas-kanade tracking[END_REF] are highly sensitive and accurate in the short term, while others are relatively conservative but robust over the long term (e.g., [START_REF] Kalal | Tracking-learningdetection[END_REF][START_REF] Lebeda | Long-term tracking through failure cases[END_REF][START_REF] Pernici | Object tracking by oversampling local features[END_REF][START_REF] Supancic | Self-paced learning for long-term tracking[END_REF]). In other words, some trackers can be regarded as short-term systems while others can be regarded as long-term systems. The power of ASMM to track objects by co-operation between the long-and short-term memory stores has motivated us to design a tracker that integrates a short-and long-term system to boost tracking performance.

In this paper, we propose the MUlti-Store Tracker (MUSTer) based on the ASMM. MUSTer consists of one short-term store and one long-term store that collaboratively process the image input and track the target. An Integrated Correlation Filter (ICF), which stores short-term memory and depends on spatiotemporal consistency, is employed in the short-term store to perform short-term tracking via two-stage filtering. In addition, we integrate a complementary component based on keypoint matching-tracking and RANSAC estimation that can interact with the keypoint feature database in the long-term store and control the final output and the short-term memory states. To maintain a reasonable keypoint feature database size, we adopt the well-known forgetting curve to model the rememberingforgetting loop and, in doing so, retain useful features.

Related Work

Online object tracking has long been a popular topic in computer vision. A large number of trackers have been proposed [START_REF] Li | A survey of appearance models in visual object tracking[END_REF][START_REF] Yang | Recent advances and trends in visual tracking: A review[END_REF], and the recent publication of benchmark datasets containing large numbers of sequences and standardized quantitative evaluation metrics is accelerating the pace of development in this field [START_REF] Kristan | The visual object tracking VOT2014 challenge results[END_REF][START_REF] Smeulders | Visual tracking: An experimental survey[END_REF][START_REF] Wu | Online object tracking: A benchmark[END_REF].

Various approaches that form the basis of existing trackers can be used to model the memory of the target appearance. In [START_REF] Ross | Incremental learning for robust visual tracking[END_REF], Ross et al. proposed to incrementally learn a low-dimensional subspace of the target representation. Later, Mei et al. [START_REF] Mei | Robust visual tracking and vehicle classification via sparse representation[END_REF] introduced sparse representations for tracking, subsequently adopted in many trackers [START_REF] Hong | Tracking via robust multi-task multi-view joint sparse representation[END_REF][START_REF] Zhang | Robust visual tracking via multi-task sparse learning[END_REF], in which the memory of the target appearance is modeled using a small set of target instances. In contrast to the generative approaches used in [START_REF] Ross | Incremental learning for robust visual tracking[END_REF] and [START_REF] Mei | Robust visual tracking and vehicle classification via sparse representation[END_REF], discriminative methods [START_REF] Avidan | Support vector tracking[END_REF][START_REF] Avidan | Ensemble tracking[END_REF][START_REF] Babenko | Robust object tracking with online multiple instance learning[END_REF][START_REF] Hare | Struck: Structured output tracking with kernels[END_REF][START_REF] Henriques | Exploiting the circulant structure of tracking-by-detection with kernels[END_REF][START_REF] Hong | Dual-force metric learning for robust distracter-resistant tracker[END_REF] have been proposed that consider both foreground and background information. In particular, Struck [START_REF] Hare | Struck: Structured output tracking with kernels[END_REF] is one of the best performing trackers and has been highlighted in several recent studies [START_REF] Pang | Finding the best from the second bestsinhibiting subjective bias in evaluation of visual tracking algorithms[END_REF][START_REF] Smeulders | Visual tracking: An experimental survey[END_REF][START_REF] Wu | Online object tracking: A benchmark[END_REF]. In [START_REF] Hare | Struck: Structured output tracking with kernels[END_REF], Hare et al. introduced structured SVM for tracking and trained a classifier using samples with structured labels. The correlation filter-based trackers [START_REF] Bolme | Visual object tracking using adaptive correlation filters[END_REF][START_REF] Danelljan | Accurate scale estimation for robust visual tracking[END_REF][START_REF] Danelljan | Adaptive color attributes for real-time visual tracking[END_REF][START_REF] Henriques | Exploiting the circulant structure of tracking-by-detection with kernels[END_REF][START_REF] Henriques | Highspeed tracking with kernelized correlation filters[END_REF][START_REF] Li | A scale adaptive kernel correlation filter tracker with feature integration[END_REF] are becoming increasingly popular due to their promising performance and computational efficiency. However, most of these trackers depend on the spatiotemporal consistency of visual cues and adopt relatively risky update schemes; therefore, they can only handle short-term tracking.

Some long-term tracking approaches [START_REF] Dinh | Context tracker: Exploring supporters and distracters in unconstrained environments[END_REF][START_REF] Kalal | Tracking-learningdetection[END_REF][START_REF] Lebeda | Long-term tracking through failure cases[END_REF][START_REF] Pernici | Object tracking by oversampling local features[END_REF][START_REF] Supancic | Self-paced learning for long-term tracking[END_REF]] have also been proposed with promising results. For instance, TLD [START_REF] Kalal | Tracking-learningdetection[END_REF] employs two experts to identify the false negatives and false positives to train a detector. The experts are independent, which ensures mutual compensation of their errors to alleviate "drifting". In [START_REF] Pernici | Object tracking by oversampling local features[END_REF], Pernici and Bimbo modeled the target appearance using oversampled local features. They used transitive matching to find the target keypoints and, in addition, performed occlusion detection to avoided updating errors. In [START_REF] Supancic | Self-paced learning for long-term tracking[END_REF], long-term tracking was conducted based on a self-paced learning scheme in which the target appearance was conservatively learned by selecting trustworthy frames.

Some systems have a similar architecture to ASMM. In 1997, Hochreiter and Schmidhuber introduced a special kind of artificial neural network called Long Short Term Memory [START_REF] Hochreiter | Long short-term memory[END_REF]. In this neural network, memory blocks are made up of two kind of units which are called "constant error carousels" and "multiplicative gate units". The constant error carousels memorize information and the multiplicative gate units control the information flow. These memory blocks can be regarded as the long-term store of ASMM. Together with pure feed-forward networks, which play the short-term role, long short-term memory systems show the great potential for various memory-intensive tasks, such as Figure 2. A system flowchart of the proposed tracker based on the Atkinson-Shiffrin Memory Model. The short-term processing in shortterm store is conducted by an ICF via two-stage filtering. Another set of short-term procedures including keypoint matching, keypoint tracking and RANSAC estimation is conducted by a conservative long-term component in short-term store, and it is able to interact with the long-term memory located in the long-term store. Both the results of short-term processing and long short-term processing are obtained by a controller, which decides the final output and the ICF update.

speech recognition [START_REF] Graves | Speech recognition with deep recurrent neural networks[END_REF] and music composition [START_REF] Eck | A first look at music composition using lstm recurrent neural networks[END_REF]. This makes the use of memory models for object tracking more convincing.

The Proposed Tracker

The MUSTer framework is based on the ASMM (Figure 2), which consists of a short-term store, a long-term store, and the corresponding processing units. An Integrated Correlation Filter (ICF) is employed in the short-term store to perform short-term processing and track the target based on short-term memory and spatiotemporal consistency. This component generally works accurately and efficiently in relatively stable scenarios. In addition, another relatively conservative long-term component based on keypoint matching-tracking and RANSAC estimation is introduced to conduct the long short-term processing on the fly. This interacts with the short-term memory stored in an active set of keypoints using forward-backward tracking, and it also retrieves the long-term memory for matching and updates the long-term memory based on the RANSAC estimation results and the forgetting curve. During tracking, the outputs of both the short-term and long short-term processing are sent to a controller, which decides the final MUSTer output and the ICF update. Specifically, the shortterm memory in ICF is reset when the short-term processing output is highly inconsistent with the long-term memory encoded by the output of the long short-term processing. This enables the recovery of the short-term tracking after dramatic appearance changes such as severe occlusion, the object leaving field-of-view, or rotation.

The following subsections detail successively all components in MUSTer: ICF short-term processing, the short-term processing of keypoints by the long-term component, the updating of long-term memory based on the forgetting curve, and finally, the output controller and ICF updater.

Short-term Integrated Correlation Filters

The short-term component is used to provide instant responses to the image input based on short-term memory. Recently, the robustness of correlation filter-based shortterm trackers [START_REF] Danelljan | Accurate scale estimation for robust visual tracking[END_REF][START_REF] Henriques | Highspeed tracking with kernelized correlation filters[END_REF][START_REF] Li | A scale adaptive kernel correlation filter tracker with feature integration[END_REF] has been recognized by [START_REF] Kristan | The visual object tracking VOT2014 challenge results[END_REF]. For accurate and efficient short-term processing performance, we employ Integrated Correlation Filters (ICFs), which are based on the Kernelized Correlation Filters (KCFs) [START_REF] Henriques | Highspeed tracking with kernelized correlation filters[END_REF] and the Discriminative Scale Space Correlation Filter (DSSCF) [START_REF] Danelljan | Accurate scale estimation for robust visual tracking[END_REF]. The ICF is a two-stage filtering process that performs translation estimation and scale estimation, respectively, which is similar to the pipeline described in [START_REF] Danelljan | Accurate scale estimation for robust visual tracking[END_REF] and [START_REF] Li | A scale adaptive kernel correlation filter tracker with feature integration[END_REF]. Here, ICF serves as the short-term component, where the short-term memory of ICF consists of the learned coefficients and templates for the filters.

In KCF, a classifier 𝑓 (x) = ⟨w, 𝜙(x)⟩ is trained on a 𝑀 × 𝑁 image patch x centered by the target bounding box B T 's center and 𝑝 times larger than B T . Instead of using dense sliding windows to extract training samples, the classifier considers all the cyclic shift versions x 𝑖 for training, where 𝑖 ∈ {0, ..., 𝑀 -1} × {0, ..., 𝑁 -1}. Each example x 𝑖 is assigned with a score in 𝑦 𝑖 ∈ [0, 1] generated by a Gaussian function in terms of the shifted distance, and the classifier is trained by minimizing the regression error:

min w ∑ 𝑖 (⟨w, 𝜙(x 𝑖 )⟩ -𝑦 𝑖 ) 2 + 𝜆∥w∥ 2 , ( 1
)
where 𝜙(x) is the mapping to a Hilbert space, and 𝜆 ≥ 0 is the regularization parameter controlling the model sim-plicity. Employing a kernel 𝜅(x, x ′ ) = ⟨𝜙(x), 𝜙(x ′ )⟩, the classifier can be derived as 𝑓 (x) = ∑ 𝑖 𝛼 𝑖 𝜅(x 𝑖 , x), where 𝜶 is the dual variable of w. Let us denote the Discrete Fourier Transform (DFT) of a vector with a hat "ˆ", e.g., α = F (𝜶), and denote the complex conjugate with α * . According to [START_REF] Danelljan | Adaptive color attributes for real-time visual tracking[END_REF] and [START_REF] Henriques | Highspeed tracking with kernelized correlation filters[END_REF], if the employed kernel is shift invariant, e.g., an RBF kernel, α * can be obtained based on the favorable properties of circulant matrices:

α = ŷ kxx + 𝜆 , ( 2
)
where k xx is a vector whose 𝑖th element is 𝜅(x 𝑖 , x). In particluar, for image data with 𝐶 feature channels, a concatenation x = [x1 ; ...;

x 𝐶 ] can be constructed, and the kernel correlation k xx based on a Gaussian kernel can be efficiently computed by element-wise products and simple summation over the feature channels in the Fourier domain:

k xx ′ = exp(- 1 𝜎 2 (∥x∥ 2 +∥x ′ ∥ 2 -2F -1 ( 𝐶 ∑ 𝑐=1 x𝑐 ⊙( x′𝑐 ) * ))), (3)
where ⊙ denotes the operator of element-wise products, and 𝑐 is the index of the feature channels.

During the first-stage filtering for translation estimation, given a 𝑀 ×𝑁 candidate image patch z as the search space, all cyclic patches of z can be evaluated via

f (z) = F -1 (( kxz ) ⊙ α), (4)
where f (z) is the filtering response for all the cyclic versions of z, and the translation is estimated by finding the location with the highest response. In our tracker, the candidate image patch z is centered by using the tracking result B 𝑜 of the last frame. To adapt to the short-term appearance changes of the target, the filter coefficients 𝜶 and the target template x are updated in an interpolating manner with learning rate 𝛾. In our implementation, we employ the 31-dimensional HOG descriptors [START_REF] Felzenszwalb | Object detection with discriminatively trained partbased models[END_REF], as in [START_REF] Henriques | Highspeed tracking with kernelized correlation filters[END_REF]. Moreover, for color image sequences, we further extract 10dimensional color attributes [START_REF] Danelljan | Adaptive color attributes for real-time visual tracking[END_REF][START_REF] Van De Weijer | Learning color names for real-world applications[END_REF] as complementary features and combine them with the HOG descriptors to further boost performance.

To cope with scale changes, a one-dimensional DSS-CF [START_REF] Danelljan | Accurate scale estimation for robust visual tracking[END_REF] is also trained and the second-stage filtering is performed for scale estimation. To evaluate the trained DSS-CF, 𝑆 image patches centered around the location found by the KCF filter are cropped from the image, each of size 𝑎 𝑠 𝑀 T × 𝑎 𝑠 𝑁 T , where 𝑀 T × 𝑁 T is the current size of the target, 𝑎 is the scale factor, and 𝑠 ∈ {-𝑆-1 2 , ..., 𝑆-1 2 }. All 𝑆 image patches are then resized to the template size for the feature extraction. Finally, the final output B s from the short-term processing is given as the image patch with the highest filtering response. Similar to KCF, the model parameters are also updated in an interpolating manner with learning rate 𝜇. We refer readers to [START_REF] Danelljan | Accurate scale estimation for robust visual tracking[END_REF] for more details and the implementation of DSSCF.

Short-term Processing of Keypoints

The goal of the long-term component is to conservatively learn the appearance of the target and to refresh the shortterm memory when a mistake made by the short-term component is detected.

Local Scale-Invariant Features [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF] are a powerful tool used in various computer vision tasks including recognition [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF] and scene alignment [START_REF] Liu | Sift flow: Dense correspondence across scenes and its applications[END_REF]. In particular, some promising trackers [START_REF] Grabner | Tracking the invisible: Learning where the object might be[END_REF][START_REF] Nebehay | Consensus-based matching and tracking of keypoints for object tracking[END_REF][START_REF] Pernici | Object tracking by oversampling local features[END_REF] have been proposed to model the object appearance based on Local Scale-Invariant Features (i.e., keypoints). Therefore, we employ a long-term component based on keypoint matching-tracking and RANSAC estimation to take advantage of the flexibity and shape generalizability of the keypoint-based appearance models.

The long-term memory of the target appearance is modeled by a total feature database ℳ = 𝒯 ∪ ℬ that consists of a foreground (target) feature database 𝒯 and a background feature database ℬ:

𝒯 = {(d 𝑖 , p 𝑜 𝑖 )} 𝑁𝒯 𝑖=1 , ℬ = {d 𝑖 } 𝑁ℬ 𝑖=1 . ( 5
)
Here, d 𝑖 ∈ ℛ 128 is the 128-dimensional Scale-invariant Feature Transform (SIFT) descriptors [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] of the keypoints. 𝑁 𝒯 and 𝑁 ℬ are the respective numbers of descriptors. Each target descriptor d 𝑖 ∈ 𝒯 is also associated with the corresponding coordinates p 𝑜 𝑖 ∈ ℛ 2 that remember the keypoint location in the original target template, and can be used for estimating the transformation of target state. The background feature database is important to reduce erroneous matching of target keypoints and can help to detect the occlusions.

In addition to the filtering function of ICF, another set of short-term procedures conducted in the short-term store is to consecutively process the keypoints by retrieving the long-term memory stored in ℳ and the short-term memory stored in an active set. In each frame, a SIFT detector based on the difference of Gaussians [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] is applied to an image search area to extract a set of keypoints with large responses. The set of detected keypoints associated with their SIFT descriptors is denoted as

𝒫 D = {(d 𝑘 , p 𝑘 )} 𝑁D 𝑘=1
, where p 𝑘 ∈ ℛ 2 is the coordinates of a keypoint.

Matching Keypoints. We search the total memory database ℳ for the nearest neighbors of each d 𝑘 ∈ 𝒫 D based on the Euclidean distance. We define the matching confidence of d 𝑘 and its nearest neighbor 1 d 1𝒩 𝑘 as the cosine similarity 𝐶(d 𝑘 , d 1𝒩 𝑘 ) between two descriptors. The candidate matching keypoint can be found if the matching confidence is larger than a predefined threshold, denoted as 𝜃 T for the matching of target points and 𝜃 B for that of background points. The different threshold settings are used to control the different recalls for the matching of foreground and background keypoints. In practice, the precision of the matching of target points is more important since they are used to estimate the current state of the target. Therefore, it is important to reject outliers during target point matching as discussed in [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF][START_REF] Pernici | Object tracking by oversampling local features[END_REF]. To further reject outliers, we employ the distinct non-parametric nearest neighbor classifier [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] by computing the ratio of the distances:

𝑟(d 𝑘 ) = 𝑑(d 𝑘 , d 1𝒩 𝑘 ) 𝑑(d 𝑘 , d 2𝒩 𝑘 ) , ( 6
)
where

d
⎧ ⎨ ⎩ p 𝑘 ∈ 𝒫 T , d 1𝒩 𝑘 ∈ 𝒯 , 𝐶(d 𝑘 , d 1𝒩 𝑘 ) > 𝜃 T , 𝑟(d 𝑘 ) < 𝜃 𝑟 p 𝑘 ∈ 𝒫 B , d 1𝒩 𝑘 ∈ ℬ, 𝐶(d 𝑘 , d 1𝒩 𝑘 ) > 𝜃 B p 𝑘 ∈ 𝒫 N , otherwise .
(7) Once the matched target keypoints (d 𝑘 , p 𝑘 ) ∈ 𝒫 T are determined, we further find their corresponding coordinates p 𝑜 𝑘 in the original template, which are then added into 𝒫 T so as to get the final complete version, i.e., 𝒫 T = {(d 𝑘 , p 𝑜 𝑘 , p 𝑘 )} 𝑁𝑚 𝑘=1 . Forward-Backward Tracking. In addition to matching keypoints and inspired by [START_REF] Nebehay | Consensus-based matching and tracking of keypoints for object tracking[END_REF], we also maintain an active set of keypoints 𝒫 𝑡-1

A = {(p 𝑜 𝑖 , p 𝑡-1 𝑖 )} 𝑁𝐴 𝑖=1
, where p 𝑡-1 𝑖 is the coordinates of the point in the 𝑡 -1 frame and p 𝑜 𝑖 is the corresponding coordinates of p 𝑡-1 𝑖 in the original template. This active set can be also regarded as the short-term memory of MUSTer, and it provides additional information for long short-term processing. To obtain the coordinates of p 𝑡-1 𝑖 in frame 𝐼 𝑡 , the optical flow can be computed using the Lucas-Kanade (LK) method [START_REF] Lucas | An iterative image registration technique with an application to stereo vision[END_REF]. To improve robustness, we employ a Forward-Backward (F-B) tracker [START_REF] Kalal | Tracking-learningdetection[END_REF] to obtain a set of keypoints with reliable tracking results. In the FB tracker, the forward optical flow from

RANSAC Estimation.

Once the matched and tracked keypoints are obtained, a candidate set 𝒫 C is formed consisting of the keypoints in 𝒫 T and 𝒫 𝑡 A , which is used to estimate the target state. Similar to [START_REF] Nebehay | Consensus-based matching and tracking of keypoints for object tracking[END_REF][START_REF] Pernici | Object tracking by oversampling local features[END_REF], we only consider the similarity transformation, which is more reliable than homography transformation for tracking generic objects, especially in cases where the planarity assumption does not hold [START_REF] Nebehay | Consensus-based matching and tracking of keypoints for object tracking[END_REF]. In the case of the similarity transformation, the state of the target can be defined as s 𝑡 = {𝑥 𝑡 , 𝑦 𝑡 , 𝑠 𝑡 , 𝛽 𝑡 }, which are the parameters of translations, scale, and rotation angle, respectively. To predict the target state s 𝑡 , a transformation 𝐹 s𝑡 letting 𝐹 s𝑡 (p 𝑜 𝑖 ) → p 𝑖 can be estimated using 𝒫 C = {(p 𝑜 𝑖 , p 𝑖 )} 𝑁𝐶 𝑖=1 . However, mistakes in matching and tracking keypoints cannot always be avoided, especially when the background is cluttered or rapidly changing. Therefore, we employ the RANSAC estimator to compute 𝐹 s𝑡 by randomly proposing putative solutions and identifying inliers and outliers. In our implementation, we use the robust MLESAC estimator [START_REF] Hartley | Multiple view geometry in computer vision[END_REF][START_REF] Torr | Mlesac: A new robust estimator with application to estimating image geometry[END_REF], which works by maximizing the likelihood rather than just the number of inliers.

Confidence of Matching. Once the resulting transformation 𝐹 s𝑡 is estimated, a target bounding box B 𝑙 defined by the current state can be computed. Meanwhile, a set of inlier keypoints 𝒫 I = {p 𝑖 } 𝑁𝐼 𝑖=1 can also be obtained, where the number of inliers 𝑁 𝐼 is an important evidence predicting tracking success; in general, the more inliers included in 𝐹 s𝑡 , the more confident the result. Therefore, we can define a binary variable 𝐺 𝐶 that indicates the tracking success and set it as:

𝐺 𝐶 = { True, 𝑁 𝐼 > 𝜃 𝐼 False, otherwise , (8)
where 𝜃 𝐼 is a predefined threshold controlling recall strictness. Occlusion Handling. In the proposed framework, the long-term memory is progressively updated on the fly. Therefore, it is important to consider cases of occlusion, which have been discussed previously [START_REF] Kwak | Learning occlusion with likelihoods for visual tracking[END_REF][START_REF] Pernici | Object tracking by oversampling local features[END_REF]. In particular, we consider the set 𝒫(B 𝑙 ), which consists of the keypoints inside target bounding box B 𝑙 , and the set 𝒫 O of occluding keypoints is defined as the matched background keypoints inside B 𝑙 , i.e., 𝒫 O = 𝒫(B 𝑙 ) ∩ 𝒫 B . Intuitively, if there is no occlusion, the number of occluding points 𝑁 𝑂 = |𝒫 O | should be small and close to zero. In contrast, when the target is occluded, the number of occluding keypoints, 𝑁 𝐺 = |𝒫 G |, is likely to be high and close to the number of keypoints belonging to the target. Therefore, we can consider the ratio of 𝑁 𝑂 and 𝑁 𝐺 and define a binary variable 𝐺 𝑂 that indicates occlusion occurrence:

𝐺 𝑂 = { True, 𝑁 𝑂 /𝑁 𝐺 > 𝜃 𝑜 False, otherwise , (9)
where 𝒫 G = 𝒫(B 𝑙 ) ∩ 𝒫 T is the matched target keypoints inside the region of B 𝑙 . In our implementation, we empirically set 𝜃 𝑜 = 0.5.

Update the Active Set. The active set 𝒫 𝑡

A that stores the short-term memory is updated at each frame. However, we should not track the keypoints if an occlusion is detected since the keypoints may gradually lock onto occluding objects or the background. Therefore, we set 𝒫 𝑡 A = ∅ if 𝐺 𝑂 = True. Otherwise, we set 𝒫 𝑡 A = 𝒫 I , which are the inliers found by the RANSAC estimator. However, when the target is stable or moving slowly, most of the keypoints in 𝒫 𝑡 A would be successfully tracked and identified as inliers, and meanwhile matched target keypoints would continually be added to 𝒫 𝑡 A . This might lead to a very large 𝒫 𝑡 A and thus computational inefficiency. Therefore, we design a strategy to find the redundant points in 𝒫 𝑡 A and let the candidate set of RANSAC 𝒫 C = 𝒫 T ∪ (𝒫 𝑡 A ∖ 𝒫 R ), where 𝒫 R denotes the set of redundant keypoints. This approach is based on the assumption that the matched keypoints are more reliable and, therefore, have higher priority. The redundant points are found using the quantization IDs. Specifically, a virtual grid is built upon the original target template, and each target keypoint can be assigned a quantization ID according to its corresponding coordinates p 𝑜 𝑖 in the original template. Finally, the redundant points in 𝒫 A are found by searching the repetitive quantization IDs in 𝒫 T .

Long-term Memory Updates

The use of keypoints as the appearance model allows natural handling of in-plane rotation. For instance, the keypoint database is not updated in [START_REF] Nebehay | Consensus-based matching and tracking of keypoints for object tracking[END_REF] but performance is still reasonable. However, it is still crucial to update on the fly to generalize the appearance model to handle out-of-plane rotation, severe scale changes, and appearance variations of the target [START_REF] Pernici | Object tracking by oversampling local features[END_REF].

To maintain relatively reliable memory of the target appearance, the memory database ℳ is updated conservatively only when the short-term processing is confident about the result (𝐺 𝐶 = True) and claims there is no occlusion (𝐺 𝑂 = False). Both the target keypoint database 𝒯 and the background keypoint database ℬ need to be updated. In particular, we consider the unmatched points that are important for capturing any changes in visual structure. During the update, we add the unmatched keypoints inside the B 𝑙 to 𝒯 , and those outside B 𝑙 to ℬ, as follows:

𝒯 = 𝒯 ∪ (𝒫 N ∩ 𝒫(B 𝑙 )) ℬ = ℬ ∪ (𝒫 N ∩ (𝒫 D ∖ 𝒫(B 𝑙 )) . ( 10
)
While the human brain is good at remembering, as well as forgetting. The remembering-forgetting interplay helps us effectively manage the valuable and finite memory capacity when handling massive quantities of input signals each day. To avoid the unbounded growth of the memory database ℳ, a certain capacity should be set for 𝒯 and ℬ, and features should be forgotten over time. To model remembering-forgetting, we employ the famous forgetting curve [START_REF] Ebbinghaus | Memory: A contribution to experimental psychology[END_REF] to maintain ℳ and forget unimportant features according to the retention of features. The forgetting curve hypothesizes a decline in memory retention and shows how information is lost over time when there is no attempt to retain it. The memory retention 𝑟 over time can typically be modeled using an exponential function:

𝑟 = exp(- 𝜏 Γℎ ) , ( 11
)
where ℎ is the relative strength of the memory, 𝜏 is the relative period of forgetting, and Γ is a constant controlling the scale of the timespan. In [START_REF] Felzenszwalb | Object detection with discriminatively trained partbased models[END_REF], the speed of decline in memory retention is decided by the relative strength ℎ.

For information with high relative strength ℎ, the decline in memory retention becomes slow and it is more possible to be remembered over time. The relative strength of information can be increased using certain methods such as repetitive retrieving. In MUSTer, each feature in d 𝑖 ∈ ℳ is assigned a set of memory variables (𝑟 𝑖 , 𝜏 𝑖 , ℎ 𝑖 ), where the memory retention 𝑟 𝑖 of features can be updated according to their corresponding 𝜏 𝑖 and ℎ 𝑖 . To model the process of forgetting, during each update term, all relative periods 𝜏 𝑖 of d 𝑖 ∈ ℳ are increased by 1. Moreover, for the retrieved background features d 1𝒩

𝑘

∈ ℬ where d 𝑘 ∈ 𝒫 B , and foreground features d 1𝒩 𝑘 ∈ 𝒯 where d 𝑘 ∈ (𝒫 T ∩ 𝒫 I ), the corresponding relative strength ℎ 𝑖 is increased by 1 and the relative period 𝜏 𝑖 is set to 0. In this way, the recalled features are renewed and strengthened in memory, while frequently recalled features obtain a high relative strength and become hard to forget. Once the numbers of features in the respective databases exceed a predefined memory capacity, 𝑁 𝒯 > Θ 𝒯 or 𝑁 ℬ > Θ ℬ , the features with low retention are removed and completely forgotten by the model.

Output and Short-term Memory Refreshing

Once the different processing procedures are performed in the short-term store, the results of filtering B 𝑠 and the result of the long short-term processing B 𝑙 together with the state variables 𝐺 𝐶 and 𝐺 𝑂 can be obtained by a controller. As mentioned earlier, short-term filtering is generally accurate in relatively stable scenarios. Therefore, if the results B 𝑠 and B 𝑙 are to some extent consistent (indicating that the long-term memory agrees with the output of the shortterm tracker), or the long-term component is not confident about the result (𝐺 𝐶 = False), or an occlusion is detected (𝐺 𝐶 = True), the tracking result B 𝑜 is output as B 𝑜 = B 𝑠 , and the short-term filters are updated using B 𝑜 and the predefined learning rates 𝛾 = 𝛾 𝑜 and 𝜇 = 𝜇 𝑜 . Otherwise, the tracking result is output as B 𝑜 = 𝑅(B 𝑙 ), where 𝑅(⋅) is a function to rotate a bounding box along its center and in the same orientation as B 𝑠 . Moreover, the short-term memory should be refreshed. We use B 𝑜 to update the short-term filters and set the learning rates 𝛾 and 𝜇 as 1 for the update, which cleans up all the previous short-term memory stored in the filters. In particular, the inconsistency of B 𝑠 and B 𝑙 is detected by the Intersection Over Union (IOU) metric 𝑈 (B 𝑠 , B 𝑙 ) = |B𝑠∩B 𝑙 | |B𝑠∪B 𝑙 | with a threshold 𝜃 𝑈 .

Experiments

The proposed tracker 2 was implemented using Matlab & C++ with OpenCV library 3 . The average time cost on OOTB is 0.287s/frame on a cluster node (3.4GHz, 8 cores, 32GB RAM). The parameters mentioned in Section 3 are specified as follows: 𝜃 𝑈 = 0, the learning rate 𝛾 𝑜 and 𝜇 𝑜 for the ICF are set to 0.02 and 0.01 respectively, and the padding size 𝑝 in KCF is set to 1. The thresholds for matching keypoints are set as 𝜃 𝑇 = 0.8, 𝜃 𝐵 = 0.9, 𝜃 𝑟 = 0.85, and 𝜃 𝐼 = 8. The threshold 𝜃 𝑓𝑏 for FB Tracker is set to 4. The Γ in the forgetting curve model is set to 10, while the memory capacities Θ 𝒯 and Θ ℬ of keypoint databases are both set to 2000. Note that the protocols proposed in [START_REF] Wu | Online object tracking: A benchmark[END_REF] were strictly followed and all parameters were fixed for all video sequences in the following evaluations. For each sequences, we simply use the ground truth of the first frame given by the dataset for initialization.

Evaluation on CVPR2013 OOTB

In this section, we report the evalution on the CVPR2013 Online Object Tracking Benchmark (OOTB) [START_REF] Wu | Online object tracking: A benchmark[END_REF] and compare MUSTer with a number of state-of-the-art trackers. OOTB is a popular comprehensive benchmark specifically designed for evaluating performance. OOTB contains 50 fully annotated sequences which extensively used by previous work. In [START_REF] Wu | Online object tracking: A benchmark[END_REF], the evaluation for the robustness of trackers is based on two different metrics: the precision plot and success plot. The precision plot shows the percentage of successfully tracked frames on which the Center Location Error (CLE) of a tracker is within a given threshold 𝑇 𝐶 , and a representative precision score at 𝑇 𝐶 = 20 is used for ranking the trackers. The success plot also counts the percentage of successfully tracked frames, by measuring the Intersection Over Union (IOU) metrics for trackers on each frame. In success plot, the threshold of IOU is varied from 0 to 1, and the ranking of trackers is based on the Area Under Curve (AUC) score. For more details about OOTB and the adopted metrics, we refer readers to [START_REF] Wu | Online object tracking: A benchmark[END_REF].

We run the One-Pass Evaluation (OPE) on the benchmark using the proposed MUSTer and use the online available software 4 provided by [START_REF] Wu | Online object tracking: A benchmark[END_REF] to compute the evaluation plots. For the competitor trackers, we first consider those 2 The code to reproduce the experiments is available on https:// sites.google.com/site/multistoretrackermuster/ 29 popular approaches whose results are available in OOT-B, such as Struck [START_REF] Hare | Struck: Structured output tracking with kernels[END_REF], TLD [START_REF] Kalal | Tracking-learningdetection[END_REF], SCM [START_REF] Zhong | Robust object tracking via sparsity-based collaborative model[END_REF], VTD [START_REF] Kwon | Visual tracking decomposition[END_REF], VTS [START_REF] Kwon | Tracking by sampling trackers[END_REF], and ASLA [START_REF] Jia | Visual tracking via adaptive structural local sparse appearance model[END_REF]. And on top of these, we include recent correlation filter-based trackers CN [START_REF] Danelljan | Adaptive color attributes for real-time visual tracking[END_REF], KCF [START_REF] Henriques | Highspeed tracking with kernelized correlation filters[END_REF], DSST [START_REF] Danelljan | Accurate scale estimation for robust visual tracking[END_REF], which is the best performing tracker in [START_REF] Kristan | The visual object tracking VOT2014 challenge results[END_REF], and further include very recent state-of-the-art trackers MEEM [START_REF] Zhang | Meem: Robust tracking via multiple experts using entropy minimization[END_REF], MTMVTLAD [START_REF] Mei | Robust multitask multiview tracking in videos[END_REF] and the LGT [START_REF] Čehovin | Robust visual tracking using an adaptive coupled-layer visual model[END_REF] based on coupled-layer visual model. Last but not least, we also compare quantitatively with the short-term ICF presented in Section 3.1, so as to demonstrate the importance of the long-term component in our proposed tracker.

Figure 3 shows a qualitative comparison with selected trackers on several representative videos/frames. To quantitatively compare all 37 trackers, we show the precision plot and success plot in Figure 4, which indicates that MUSTer achieves overall the best performance using both the metrics and significantly outperforms the second best tracker MEEM with 11% performance gain using the metric of AUC score. As discussed in [START_REF] Wu | Online object tracking: A benchmark[END_REF], the AUC score that measures the overall performance in success plot is more accurate than the precision score at one threshold of precision plot. Therefore, the experimental result clearly demonstrates the superior performance of the proposed tracker. In addition, MUSTer also significantly outperforms its baseline short-term component ICF, other correlation filter-based trackers DSST and KCF, and the well-known long-term tracker TLD, which validates the important role of the long-term component in MUSTer and the effectiveness of the proposed tracking framework based on ASMM.

Evaluation on ALOV++ Dataset

To further validate the robustness of MUSTer, we conducted the second evaluation on a larger dataset [START_REF] Smeulders | Visual tracking: An experimental survey[END_REF], namely ALOV++ (Amsterdam Library of Ordinary Videos), which is recently developed by Smeulders et al.. It consists of 14 challenge subsets, totally 315 sequences and focuses on systematically and experimentally evaluating trackers' robustnesses in a large variety of situations including light changes, low contrast, occlusion, etc. In [START_REF] Smeulders | Visual tracking: An experimental survey[END_REF], survival curves based on 𝐹 -score were proposed to evaluate track- To evaluate MUSTer on ALOV++ dataset, we ran MUSTer on all the 315 sequences using the ground truth of the first frame as initialization and the same parameters as the previous evaluation shown in Section 4.1. We compare our tracker with 19 popular trackers 6 that were evaluated in [START_REF] Smeulders | Visual tracking: An experimental survey[END_REF]. In addition, we also ran MEEM, ICF, DSST, KCF on ALOV++, which rank on the top five trackers in the previous evaluation. The survival curves of the top ten trackers and the average 𝐹 -scores over all sequences are shown in Figure 5, which demonstrates that MUSTer achieves the best overall performance over 24 compared trackers in this comparison.

Conclusion

In this paper, we propose the MUlti-Store Tracker (MUSTer) based on the Atkinson-Shiffrin Memory Mod-5 http://imagelab.ing.unimore.it/dsm/ 6 We refer the reader to [START_REF] Smeulders | Visual tracking: An experimental survey[END_REF] and its references for the details about the compared trackers. The evaluation results of these 19 trackers were obtained from the author of [START_REF] Smeulders | Visual tracking: An experimental survey[END_REF]. el to handle tracking memory problems. MUSTer consists of two important but relatively independent components and exploits them to process the image input according to the short-and long short-term memories of the target being tracked. In the short-term store, an Integrated Correlation Filter (ICF), which stores the short-term memory and depends on spatiotemporal consistency, is employed to provide an instant response via two-stage filtering. In addition, a complementary component based on keypoint matchingtracking and RANSAC estimation is integrated, which is able to interact with the keypoint feature database in the long-term store and control the final output and the shortterm memory states. To maintain a reasonable keypoint feature database size, the well-known forgetting curve is employed to model the remembering-forgetting loop and retain the most useful features. The experimental results on two large datasets demonstrate that the proposed tracker is capable of taking advantage of both the short-term and longterm systems and boosting the tracking performance.

Figure 1 .

 1 Figure 1. The Atkinson-Shiffrin memory model represented by an illustrative neural network. Nodes and their connections inside the short-and long-term stores represent the possible structure of the neural network inside the human brain.

p 𝑡- 1 𝑖 1 𝑖, p ′ 𝑡- 1 𝑖) 1 𝑖, p ′ 𝑡- 1 𝑖) 1 𝑖, p ′ 𝑡- 1 𝑖)

 1111111 to p 𝑡 𝑖 and the backward optical flow from p 𝑡 𝑖 to p ′ 𝑡-1 𝑖 are computed using two consecutive frames: 𝐼 𝑡-1 and 𝐼 𝑡 . The displacement 𝑑(p 𝑡-between p 𝑡-1 𝑖 and p ′ 𝑡-1 𝑖 is then used to identify any tracking failures. Ideally, 𝑑(p 𝑡-should be small if the tracking is successful. Therefore, a threshold 𝜃 𝑓𝑏 is defined and a failure is detected if 𝑑(p 𝑡-> 𝜃 𝑓𝑏 . Finally, we can obtain a set of remaining active keypoints 𝒫 𝑡 A = {(p 𝑜 𝑖 , p 𝑡 𝑖 )} 𝑁 ′ 𝐴 𝑖=1 that contain the keypoints successfully tracked by the FB tracker.

Figure 4 .

 4 Figure 4. Quantitative comparison in CVPR2013 OOTB. The performance score for each tracker is shown in the legend. For each figure, only the top 10 trackers are presented.

Figure 3 .

 3 Figure 3. Tracking results of selected algorithms in representative frames. Frame indexes are shown in the top left of each figure. The showing examples are from sequences Couple, Lemming, Jumping, Jogging, Singer2, Bolt, respectively.

Figure 5 .

 5 Figure 5. The survival curves for top ten trackers on AlOV++ dataset. The average 𝐹 -scores over all sequences are specified in the legend.

  2𝒩 𝑘 is the second nearest neighbor of d 𝑘 . The matched point d 1𝒩 𝑘 is classified as an inlier if 𝑟(d 𝑘 ) is smaller than a threshold 𝜃 𝑟 . Finally, the detected feature points (d 𝑘 , p 𝑘 ) ∈ 𝒫 D are classified into one of the three following sets: the matched target keypoints 𝒫 T , the matched background keypoints 𝒫 B and unmatched keypoints 𝒫 N , according to the formula below:

For simplicity, we denote the nearest and the second nearest neighbors of d 𝑘 in ℳ by d 1𝒩 𝑘 and d

2𝒩 𝑘 , respectively.

Acknowledgment

This project is supported by Australian Research Council Discovery Projects number DP-120103730, DP-140102164 and FT-130101457, and it is also supported by Toyota Research Institute NA collaborative project 2013001793.


Grigore Burloiu
email: gburloiu@gmail.com

Arshia Cont
email: cont@ircam.fr

Visualizing Timed, Hierarchical Code Structures in AscoGraph

Antescofo is a state-of-the-art software package for mixed music authorship and performance. In this paper, we apply an information visualisation perspective to a set of revisions in the timeline-based representation of action items in AscoGraph, the dedicated user interface to Antescofo. Our contribution is two-fold: (a) a design study of the proposed new model, and (b) a technical, algorithmic component. In the former, we show how our model relates to principles of information coherence and clarity, facility of seeking and navigation, hierarchical distinction and explicit linking. In the latter, we frame the problem of arranging action rectangles in a 2D space as a strip packing problem, with the additional constraint that the (horizontal) time coordinates of each block are fixed. We introduce three algorithms of increasing complexity for automatic arrangement, estimate their packing performance and analyse their strengths and weaknesses. We evaluate the systemic improvements achieved and their applicability for other time-based datasets, while noting the limitations of the model and resulting directions for future research.

I. INTRODUCTION

The aim of information visualisation is to organise heterogenous data graphically in a way that optimises human cognition, based on an inherent model. The model should address specific visualisation aims and yet be general enough to allow for wide public adoption and adaption to other problems from the domain. An interesting instance is the "standard" model of Western music notation: it developed over centuries to render pitch and rhythm readable, writable and playable by its users, while its semantics have been further extended to wider harmonic, instrumental and stylistic applications over the years, all the time keeping the basic framework. Still, the notation will never capture all the sonic aspects a musician might have in mind when authoring or reading a score. In this sense, any visualisation must strike a bargain between what is shown the user, and what remains hidden or implied. The major advantage of interactive models is the enabling of userled exploration and focus, so that the visible domain becomes fluid, adapting to one's own needs and preferences.

This paper addresses the problem of ergonomically representing a set of timed hierarchical structures. Our use case is a reactive system for mixed music Antescofo [START_REF] Cont | Antescofo: Anticipatory Synchronization and Control of Interactive Parameters in Computer Music[END_REF] and This project was partially funded by the French ANR INEDIT Project. its dedicated visual interface, AscoGraph [START_REF] Coffy | AscoGraph: A User Interface for Sequencing and Score Following for Interactive Music[END_REF]. Antescofo is an award-winning software 1 for authorship (programming) and execution (performance) of mixed music, defined as the live association of human musicians and reactive/interactive computer software. The system has been rapidly adopted by artists and is widely used in public concerts around the world.

Contributions of this work are however of interest to the wider domain of time-based information visualisation. Throughout this paper, we highlight aspects particular to Asco-Graph and show how they relate to more general visualisation principles and techniques. The design study thus constructed represents the primary focus of this paper.

As a secondary contribution, we introduce three new algorithms developed for spatial arrangement of timed modules in AscoGraph. They are however not specific to our system, and might be applied in other situations involving timed data-block sets.

Other visual solutions for interactive media authorship exist. We note Iannix [START_REF] Jacquemin | Iannix 0.8[END_REF] and Iscore [START_REF] Allombert | Iscore: A system for writing interaction[END_REF], fully-featured suites employing multiple timelines and drag-and-drop type functionality to manipulate actions and events. What distinguishes Antescofo-AscoGraph is the inherent system coupling of a score follower [START_REF] Cont | Antescofo: Anticipatory Synchronization and Control of Interactive Parameters in Computer Music[END_REF] with a reactive action language [START_REF] Echeveste | Operational semantics of a domain specific language for real time musician-computer interaction[END_REF] which, unlike the alternatives, allows for unassisted live performance of mixed music which is permanently responsive to the musician. AscoGraph seamlessly integrates these two core functions into a coherent visual presentation.

Inside the AscoGraph environment (Fig. 1), the code for a mixed score is listed in the text editor on the right, whose contents are reflected in the graphical display on the left hand side. The two graphical views, an instrumental piano roll and an electronic section, are coupled in musical time along a common horizontal timeline. Each musical event in the top view can have one or several corresponding action blocks in the bottom view.

Our paper starts with a short discussion in section II of the role of time in Antescofo, after which in section III we delineate the problems tackled. We then present our revisions to AscoGraph's electronic action view, as it was first described in [START_REF] Coffy | AscoGraph: A User Interface for Sequencing and Score Following for Interactive Music[END_REF], developed towards a clearer and more time-coherent visualisation of Antescofo scores. Our algorithmic solution for efficiently positioning action blocks is explained in section IV. In section V we address the issue of coherence between block width and musical time. Sections VI and VII cover block filtering and colouring -two features meant to facilitate the navigation of the score dataset. We conclude the paper with an overall discussion of the present model and future perspectives.

II. REPRESENTING TIME IN AscoGraph

We present a brief overview of temporal concepts in the Antescofo action language. It is the final goal of AscoGraph to comprehensively and coherently visualise all instances of such concepts.

We distinguish between two types of actions: atomic and compound [START_REF] Giavitto | Antescofo a notso-short introduction to version 0[END_REF]. The former correspond to points in time, and the latter to temporal intervals. For instance, an atomic action might be a simple message trigger, or a specific computation. A compound action could be an automation Curve2 unfolding over time, or a Loop construct that repeats certain atomic actions sequentially. Only compound actions can be said to have a duration (which can be dynamically determined), while atomic actions are by definition logically instantaneous.

Any combination of actions can be grouped together. Nesting compound actions within each other produces a deep hierarchy of action groups. Within a group, items can have different start times, so the "parent" action group start time is by definition the start time of the first item.

The Antescofo language supports all three major types of temporal structures: linear, cyclical and branching [START_REF] Aigner | Visualizing time-oriented data: A systematic view[END_REF]. However, the current iteration of AscoGraph is organised around a purely linear timeline. The reasons for this design choice are the following: (1) the fact that a majority of musical works are composed in linear time, (2) the analogy to classical music notation that most musicians are familiar with, (3) the similarity to commonly used timeline-based music software (e.g. ProTools, Ableton Live), and (4) the analogy to the linear nature of Antescofo code. A limitation of the model is that, while the Jump language feature allows for cyclical or branching transitions in time, this does not currently impact AscoGraph's temporal organisation.

There remains a gap between the complexity of the Antescofo action language and AscoGraph's representation capabilities. Along the development process, language concepts have been introduced that are sometimes difficult to readily represent visually. The next section details the problems that our current contribution has addressed, as a step towards bridging this gap.

III. PROBLEM DEFINITIONS

The following is a list of design requirements, to be tackled in subsequent sections. They are ordered by visual scale, from the level of action groups to the score as a whole:

• clearly represent action group content and duration. We frame this issue as a strip packing problem in section III-A, and we propose three new algorithms to solve it in section IV; • ensure time coherence between atomic and compound action items. Section V covers this requirement; • facilitate the locating of specific information. We achieve this through action filtering, presented in section VI; • represent the hierarchical structure of the code. Sections V and VII show our advances in this regard; • synthesise a useful overview of the score, showing the degree of electronic complexity over musical time. All the sections listed above contribute to this aspect, which is further discussed in the concluding section.

A. The Bin Packing Perspective

In the initial iteration of AscoGraph, it was common to have temporally overlapping action groups displayed on top of each other along the timeline. The resulted in a loss of coherence and clarity, with the widths of some action blocks no longer corresponding to their programmed durations.

In order to rectify this, we amended the model by stacking action groups in downward non-overlapping order, similarly to how the elements within groups are arranged. In the design process, we faced two challenges: (1) managing the 2D space efficiently (due to the new tendency towards vertical growth) and ( 2) maximising readability and easy navigation. The solutions we propose all strike a certain balance between these parameters.

For arranging rectangular blocks in a two-dimensional space, we translate the issue to a strip packing problem. A subset of the bin packing approach, strip packing is used in areas ranging from optimizing cloth fabric usage to multiprocessor scheduling [START_REF] Thöle | Approximation algorithms for packing and scheduling problems[END_REF]. Algorithms seek to arrange a set of rectangles within a 2D space of fixed width and bottom base, and of infinite height. In our present case, the width of the strip corresponds to the total duration of the piece, and the rectangles to be placed are the action group blocks.

Bin packing is a rapidly expanding research area, with results often being difficult to track and compare [START_REF] Riff | A revision of recent approaches for two-dimensional strip-packing problems[END_REF]. A good measure of algorithm efficiency is the absolute approximation ratio: sup I ALG(I)/OPT(I), where ALG(I) is the strip height produced by the algorithm ALG on an input I, and OPT is the optimal algorithm. By calculating a superior bound for any input we obtain a useful value for any input size [START_REF] Harren | Improved absolute approximation ratios for two-dimensional packing problems[END_REF].

Unlike existing bin packing problems, all AscoGraph action blocks must retain their X coordinate along the time axis. This constraint alone distinguishes our problem from the rest of the bin packing literature. Even multiprocessor scheduling strategies involve expediting or delaying tasks in time [START_REF] Thöle | Approximation algorithms for packing and scheduling problems[END_REF]. Thus, relying on existing algorithms becomes impractical.

IV. PACKING ALGORITHMS

We introduce three new algorithms for stacking action groups in AscoGraph's graphical editor. The user can switch between each and the original display style through the application's View menu. The appropriate option will depend on score complexity and the user's personal taste.

The interactive nature of the software demands dynamic and periodic calls to block arrangement calculation and rendering. For instance, expanding an action group to reveal its contents might free up space next to it -see Fig. 2. In order to minimise user confusion and computer processing overhead, we take several measures. Firstly, the ordering is computed for all actions in the score, and not just the ones in a specific timeframe; that way, when scrolling through a score at a constant zoom level, recalculation is not necessary. Secondly, we defined a number n = 10 of user actions between recalculations. Finally, the most recently clicked action group always stays in place, no matter what reordering process is triggered otherwise.

It is important to note that following bin packing conventions, we shall consider boxes as being placed on top of the strip base. Naturally, in the AscoGraph environment the situation is mirrored and we build downwards starting from the upper border.

In this section, we define a set of rectangles I = {r 1 ...r n }, with each r i being determined by height h i , width w i and start time x i .

A. First Fit (FF)

The first option is the trivial solution of placing the blocks in the first space they will fit, starting from the base. The main strengths of this algorithm are speed and predictability: blocks are placed in the order in which they appear in the source code text, which is also their scheduled temporal order. Since spatial position is in principle the strongest perceptual cue [START_REF] Mackinlay | Automating the design of graphical presentations of relational information[END_REF], if all groups are considered equally important then it makes sense to place the first occurring elements in the top positions. In section VI we propose filtering as a way to express precedence of certain blocks over others. Other options in this direction remain to be examined.

The downside is evident in Fig. 3a and3b. Let us consider the worst-case scenario in order to calculate the absolute approximation ratio. Let I = {r 1 ...r n } with increasing heights h i = h i-1 + ε i and for simplicity, let all rectangle widths be equal. While FF would stack them on top of each other (see Fig. 3a), the optimal configuration would stack them two by two (Fig. 3b), so that the maximum height is given by the final two elements:

FF(I ) OPT(I ) = n i=1 h i h n-1 + h n (1)
It is obvious that a finite upper bound cannot be defined.

B. First Fit Decreasing (FFD)

Note that in the previous case, the optimal configuration could be reached by simply reordering the blocks by height. This leaves room for blocks of smaller height to drop to the baseline, as we saw in Figures 2 and4b.

This insight lies at the root of the classic FFDH strip packing algorithm [START_REF] Coffman | Performance bounds for level-oriented two-dimensional packing algorithms[END_REF]. In our case, the FFD algorithm orders the blocks by non-increasing height, after which the First Fit process is applied. 3 Fig. 3c shows a basic example of an FFD arrangement, along with its optimal solution at Fig. 3d.

It is obvious that, for any n = 4 blocks, the above configuration is the one that produces the largest FFD(I)/OPT(I) ratio, by means of the gap between blocks 3 and 4. Generalizing, we can state the following:

Definition 1. Given an FFD layout, a pair of non-adjacent blocks is called a basic broken pillar, if the horizontal projection of one block, traversing upwards, intersects the other block.

In Fig. 3c, blocks 2 and 3 form a basic broken pillar.

Definition 2. In an FFD layout, a broken pillar is a chain of basic broken pillars where the top block of one is the bottom block of the next.

Theorem 1. For any configuration of blocks I,

FFD(I) -OPT(I) ≤ g, ( 2
)
where g is the accumulated vertical gap inside the tallest broken pillar.

Proof: Since, for a basic broken pillar, the reduction to be made by layout optimisation is evidently limited by the basic pillar's internal gap, we can proceed along the chain to obtain the overall maximum reduction.

Corollary 1. For any n > 4, the configuration that maximises FFD(I)/OPT(I) is generated by sequentially adding to a broken pillar exclusively.

Proof: When placing each block, if it is not adding to a broken pillar, then the difference between FFD(I) and OPT(I) remains constant. The goal must be to maximise the accumulated gap for the given set of blocks.

Corollary 2. In a broken pillar, if the accumulated vertical gap g is greater than the accumulated height of the member blocks, then g will not contribute to layout optimisation. Proof: For a basic broken pillar that satisfies these conditions 4 the conclusion is obvious. Proceeding along the chain, each gap's contribution will continue to be annulled by the stack on the opposite side.

It is now possible to present an upper bound to the absolute approximation ratio.

Theorem 2. The absolute approximation ratio of the FFD algorithm is lower than 2.

Proof:

sup I FFD(I) OPT(I) ≤ h pillar + g h pillar = 1 + g h pillar ( 3
)
where g is the accumulated gap inside the tallest broken pillar. If g ≥ h pillar , then its contribution is annulled and we must look to the second tallest broken pillar. And so on, until the fraction becomes subunitary.

C. First Fit Decreasing Towers (FFDT)

As before, the optimal configuration in the previous example hints at the following algorithm. We propose a greedy heuristic that builds upon FFD while tackling situations common in AscoGraph, like one action block sharing time with several blocks on both sides of it. (e.g. Fig. 3c andd). The basic goal is to minimise the gaps in broken pillars.

The FFDT algorithm first orders all blocks as in FFD. Then, action group towers are defined at the time-axis intersections between two or more group blocks. Their height is equal to the sum of the heights of their component blocks. For instance, in Fig. 3c andd the rectangle 2 is part of four towers: T{r 1 , r 2 }, T{r 2 }5 , T{r 2 , r 3 } and T{r 2 , r 3 , r 4 }.

The entire width being now split along these virtual vertical strips we call towers, we are now able to refine the ordering of the blocks. Alg. 1 below lists all the steps.

Algorithm 1 FFDT

(1) Compute all tower assignments and heights.

(2) For each block r i , compute:

• M T H i = the maximum tower height among the towers containing the block; • N T i = the number of towers containing the block;

(3) Order all action group blocks as follows: (3a) by decreasing M T H i if equal then (3b) by decreasing N T i ; if equal then (3c) by non-increasing block height (as in FFD). end if end if (4) Place blocks using FF.

The maximum tower height is a definite lower bound of any AscoGraph strip packing configuration. Therefore, in the FFDT heuristic the top tower will always be placed first, in an attempt not to overshoot this lower bound. Among its component blocks, the ones that are shared with many other towers are then given preference -the intention again being to maintain tower integrity as much as possible. Lastly, as with FFD, tall blocks are prioritised so as to fill gaps efficiently.

We assert that the FFDT algorithm's absolute approximation ratio is lower than 2 (similarly to FFD), and it is safe to assume it is much closer to 1.

V. TIME COHERENCE OF ATOMIC ACTIONS

As we have shown in section II, atomic actions are instantaneous and ideally should not take up horizontal space. Moreover, as seen in Figures 2 and4, they introduce unnecessary clutter in the workspace.

Our solution is to group all instances from a specific hierarchical level and display them on a single line as small circles, or conceptual points. When the mouse hovers over such a point, a list of the messages it contains is shown. Fig. 5 shows the expanded list for Group THREE; the messages are set at 3 different points in time, which is why 3 points are present in the message line. This feature also harnesses the visualisation principle of explicit linking [START_REF] Roberts | State of the art: Coordinated and multiple views in exploratory visualization[END_REF]. When the user clicks on a certain message in the expanded list, the corresponding line of code is highlighted. Thus, we capitalise on the coupling between adjoining views and their value is enhanced. This feature was already present in AscoGraph among other elements: action blocks, musical events in the piano roll, and specific lines of code are all linked and clickable.

Our new model is fully time coherent and considerably clearer than before. The user experience improvement over the classic model becomes most obvious when dealing with complex scores with many messages.

VI. TRACK FILTERING

AscoGraph implements the "visual information seeking mantra" -overview first, zoom and filter, details on demand [START_REF] Shneiderman | The eyes have it: a task by data type taxonomy for information visualizations[END_REF]. While zooming the timeline and expanding blocks to reveal their contents have already been mentioned, filtering is another function essential to information seeking and score navigation.

In Antescofo, filters are defined in the score code through regular expressions. The resulting set of objects that match a certain user-defined expression is referred to as a track [START_REF] Giavitto | Antescofo a notso-short introduction to version 0[END_REF]. The user can define up to 32 such tracks.

Fig. 6 illustrates the use of filters. Note that any number of tracks can combine into a filter. At any point, the user can click the SHOW ALL button to return to the initial view.

VII. ACTION BLOCK COLOURS

In choosing the colour scheme for AscoGraph, we observed the guidelines of Tufte [START_REF] Tufte | Envisioning Information[END_REF] that large areas should use desaturated colour and that high contrast between foreground and background improves readability. We present an additional contribution over the previous version of AscoGraph, in which each action block header had a different, randomly assigned colour.

In our new model, header colours signify (1) hierarchy and (2) filters. Unless a block header's colour is overridden by a filter highlight, it will correspond to the block's hierarchical level. First-order action groups have blue headers; afterwards we vary the hue angle in 45 degree increments. Filter highlight tones are purer and more saturated in order to clearly distinguish them from default hierarchical colours.

Message circles are by default transparent white, regardless of hierarchy. Once allocated into tracks, their colours also change accordingly.

VIII. CONCLUSIONS AND FUTURE WORK

We evaluated the current design informally over two phases. During the planning and implementation of the new features, we consulted with the internal community of composers and musicians using Antescofo at IRCAM. Their suggestions proved useful in guiding our design. In terms of feedback, there was a lot of enthusiasm over the space saving and clarity provided by the new atomic action display mode, whereas appreciation of the difference between stacking algorithms was generally more gradual. This supports the common insight that algorithm complexity is often unrelated to design impact.

The second phase started with the announcement of the new features on the public Antescofo forum 6 . This allowed the improvements to be also informally validated by the AscoGraph user-base.

In general, we have achieved increased visual integrity and coherence through the stacking of action group blocks. The most basic stacking method, First Fit, is the most easily readable option for scores of moderate depth. We also proposed two increasingly efficient stacking algorithms, FFD and FFDT, for scores containing larger concentrations of actions per time unit where vertical growth is a concern. While superior algorithms for space optimisation are technically conceivable (possibly a metaheuristic scheme built on top of FFDT), the present options were deemed appropriate for the practical use and the allowed processing overhead of the AscoGraph software.

We have also introduced a method of displaying related messages on a single line, preserving group hierarchy. The main advantages are time coherence and vertical compactness. Finally, through the filtering function and the hierarchical colour scheme, navigation through large scores has been found to be drastically improved. All the while, view linking ensures that the navigation process correlates smoothly over all three main views: score code, piano roll, and action blocks.

In the future, we consider employing more techniques to further refine the action view. At wide zoom levels, we might implement block aggregation of neighbouring groups instead of drawing them separately. Semantic zooming might also be of help: in the broad view it is pointless to burden the scene with textual detail.

Figure 1 :

 1 Figure 1: The AscoGraph visual editor for Antescofo mixed music scores. Right: the textual score describing acoustic events and connected electronic actions. Left, upper: the piano roll view of acoustic material. Left, lower: the electronic actions layout.

( a )Figure 2 :

 a2 Figure 2: Expanding an action block leaves room for another block to drop to the horizontal base.

Figure 3 :

 3 Figure 3: Horizontally constrained strip packing. The rectangle set in (a) and (b) is first arranged by First Fit, and then optimised by FFD. The set in (c) and (d) is first stacked by FFD, then optimised by FFDT.

Figure 4 :

 4 Figure 4: The three AscoGraph packing options: (a) FF -action group blocks are placed as close to the horizontal timeline as possible, in the order in which they appear in the code. (b, c) FFD -blocks are first ordered by height before being placed as in FF. (d) FFDT -blocks are first ordered according to a gap-minimisation heuristic before being placed on the timeline as in FFD.

Figure 5 :

 5 Figure 5: Time-coherent message circles display

  (a) No filtering: all group blocks are shown. (b) One filter: SPAT1 track is active. (c) Two filters: SPAT1 and SPAT2 tracks are active.

Figure 6 :

 6 Figure 6: Track filtering in AscoGraph: A line is added just below the timeline showing all available track names which the user can filter by.

http://repmus.ircam.fr/antescofo/

in Antescofo, Curves are interpreted as discrete sequences of actions, whose parameters contain variables that change over time.

The difference to the classic FFDH algorithm is the absence of horizontal levels. New blocks are stacked at the minimum possible altitude rather than a common level.

The minimum number of blocks to build a basic broken pillar is

2 blocks form the broken pillar itself, and at least 3 blocks are needed (under FFD conditions) to build a large enough gap.[START_REF] Echeveste | Operational semantics of a domain specific language for real time musician-computer interaction[END_REF] The minimal tower is one that is identical to an (isolated) action block.

http://forumnet.ircam.fr/user-groups/antescofo/forum/topic/newascograph-display-features-2/ Despite improvements, the AscoGraph model is not yet able to visualise some highly dynamic structures in an Antescofo score, such as dynamic durations, processes and more as briefly discussed in section II. This points us away from AscoGraph's linear timeline, towards a more flexible model that would accommodate all dynamic constructs in the action language.