Shashanka Venkataramanan

João Carreira

Google Deepmind

Yuki M Asano

Yannis Avrithis

IS IMAGENET WORTH 1 VIDEO? LEARNING STRONG IMAGE ENCODERS FROM 1 LONG UNLABELLED VIDEO

Self-supervised learning has unlocked the potential of scaling up pretraining to billions of images, since annotation is unnecessary. But are we making the best use of data? How more economical can we be? In this work, we attempt to answer this question by making two contributions. First, we investigate first-person videos and introduce a "Walking Tours" dataset. These videos are high-resolution, hourslong, captured in a single uninterrupted take, depicting a large number of objects and actions with natural scene transitions. They are unlabeled and uncurated, thus realistic for self-supervision and comparable with human learning. Second, we introduce a novel self-supervised image pretraining method tailored for learning from continuous videos. Existing methods typically adapt imagebased pretraining approaches to incorporate more frames. Instead, we advocate a "tracking to learn to recognize" approach. Our method called DORA, leads to attention maps that Discover and tRAck objects over time in an end-to-end manner, using transformer cross-attention. We derive multiple views from the tracks and use them in a classical self-supervised distillation loss. Using our novel approach, a single Walking Tours video remarkably becomes a strong competitor to ImageNet for several image and video downstream tasks. Dataset and code can be found at https://shashankvkt.github.io/dora

INTRODUCTION

(To the question "Have you read all the books in here?") No, only four of them. But I read those very, very carefully.

Jacques Derrida

Learning from large scale datasets has been at the core of great progress. In particular, the field of self-supervised learning has allowed pretraining of neural networks to scale beyond the size of labelled datasets. By avoiding costly annotation, strong performance has been demonstrated by increasing the training dataset sizes into billions of images.

But how well are those images really used? At a rate of one image per second, a dataset of 1B images would take 317 years to watch. Yet, humans develop functioning visual systems much faster i.e. face recognition [START_REF] De Haan | Recognition of individual faces and average face prototypes by 1-and 3-month-old infants[END_REF] and color sensitivity (Adams, 1987) is developed in three months, depth perception in five months [START_REF] Joseph J Campos | The emergence of fear on the visual cliff[END_REF] and visual acuity in six months [START_REF] Sokol | Measurement of infant visual acuity from pattern reversal evoked potentials[END_REF]. Besides potential genetic visual priors in humans, one stark difference is the type of data. Humans observe their visual surroundings in one continuous stream, only interrupted by sleep. Indeed, learning visual representations of images from videos is not new. However, previous works have found significant gaps in performance to image-pretrained models. They have mostly used object-centric videos scraped from the internet, and adapted image-based pretraining methods to use different frames as an extra form of data augmentation [START_REF] Gordon | [END_REF][START_REF] Parthasarathy | Self-supervised video pretraining yields strong image representations[END_REF].

Figure 1: Examples of frames from the Walking Tours dataset, containing hours-long, continuous egocentric 4K videos from urban scenes in different cities, under CC-BY license. There are a large number of objects and actions in a variety and natural transition of places, e.g. residential area, park, market, waterfront, etc., with natural transition of lighting conditions and object augmentations.

In this work, we investigate two directions. First, in the direction of data, we introduce a new dataset of open-source first-person videos, recorded for the purpose of virtual "walking tours", inspired by [START_REF] Wiles | Compressed vision for efficient video understanding[END_REF]. These videos have several advantages. Not only are the individual frames dense in semantic categories -much more so than movies, as we analyze -but these videos also directly represent the viewpoint of a human, contain few or no shot cuts nor special effects and are long (1-3h). Another benefit is their transparency: indeed, one can watch the whole dataset in one setting. The dataset we create contains 10 Walking Tours (WT) videos with CC-BY license.

Second, in the direction of the method, we develop a new self-supervised image-pretraining method that is uniquely suited for learning from natural, non-object-centric videos. Our approach is inspired by observing toddlers first learn to track objects and animals, then to recognize and differentiate them [START_REF] Paul | The nature and structure of infant form categories[END_REF][START_REF] Paul C Quinn | Evidence for representations of perceptually similar natural categories by 3-month-old and 4-month-old infants[END_REF][START_REF] Elizabeth | Core knowledge[END_REF]. Our method, called DORA, is an end-to-end training approach that "tracks to learn to recognize": given a video clip, objects in an initial frame are implicitly Discovered and tRAcked across time. The tracked objects are incentivized to be diverse by introducing a Sinkhorn-Knopp clustering of patch embeddings; the tracked instances are used as a learning signal for a classical multi-view SSL loss. Surprisingly, contrary to previous works, we find that our novel method obtains ImageNet-level performances by training on a single WT video, as evidenced by performances on segmentation and object detection downstream tasks. While humorously intentioned, Derrida's quote rings true to this finding and our results give some hope for alternative directions in SSL that depart from blind dataset scaling towards more efficient and smarter use of existing video data.

To summarize, our key contributions in this work are as follows:

1. We introduce a new dataset of 10 WT videos, with single-video and mixed-video splits.

The latter is conveniently equal in size to ImageNet. We analyze their usefulness compared to existing video and image datasets. 2. We propose a new end-to-end self-supervised visual pretraining method called DORA. It builds upon DINO but is tailored to promote tracking of multiple objects across frames. We use it to learn strong image encoders and trace the source of its improvements through extensive ablations. 3. We obtain strong performance on ADE20k segmentation and MS COCO detection, outperforming ImageNet-pretrained DINO, while instead pretraining on a single long video.

RELATED WORK

Self-supervised learning of image encoders from video data is a very active area of research. Video, and more generally temporal streams, have long been theorized to be ideal signals for unsupervised learning [START_REF] Wiskott | Slow feature analysis: Unsupervised learning of invariances[END_REF]. In computer vision, early methods have been very diverse and included pretext tasks such as egomotion prediction ( 1. Large number of objects and actions. Each frame or clip taken from a video depicts several objects and actions, e.g. walking, riding a bike, sitting, drinking etc. 2. Natural transition in lighting conditions. In some videos, the lighting gradually transitions from bright (late afternoon) to dim (dusk) then to dark (post sunset). 3. Natural transition in scenes. The videos depict transitions between places, e.g. from city center to market place to residential areas to parks to water fronts etc. 4. Natural object augmentations. Continuous variation e.g. of pose, deformation, viewpoint, perspective distortion, relative object position, occlusion, background clutter.

The abundance of information within these videos, encompassing a multitude of objects and complex scenes, presents a formidable challenge for manual annotation or curation, making it appropriate for unsupervised pretraining. To the best of our knowledge, we are the first to propose an egocentric video dataset for pretraining and evaluate it on a wealth of downstream tasks.

COMPARISON WITH OTHER VIDEO DATASETS

In WTours videos are continuous, longer and higher-resolution than even other egocentric datasets.

Using object detectors, we find that the average number of object classes is close to that of ImageNet and there is a high number of objects per frame, making WTours appropriate for representation learning. WTours is not curated and does not rely on search terms. It is data-first and more openended, thus well suited for the self-supervised setting. It is scalable since it requires no human labeling effort and more videos can be easily downloaded or even made. We are inspired by a 10k walking tours videos created by Wiles et al. ( 2022), which however is not publicly released and not studied for self-supervised learning. A more detailed discussion is given in subsection A.1.

DATASET ANALYSIS

In Figure 2, we analyse the properties of a single WTours video compared with videos of the same length from two other datasets, as well as two movie videos. In summary, our findings are as follows. From Figure 2(a), WT may exhibit gradual shifts in lightness, transitioning from bright to dim to dark, while Epic-Kitchens and AVA videos exhibit random brightness fluctuations. Lightness variations are not well expored in self-supervised pretraining. From Figure 2(b,c), unique classes appear more frequently and there are more unique objects per frame in WTours than in the other datasets. This makes WTours semantically richer. From Figure 2(d), WTours and Epic-Kitchens videos contain only one or two shots per entire video on average, while the other datasets contain hundreds. In subsection 5.2 and in Appendix C, we show that WTours significantly outperforms movies in downstream tasks, which is partially attributed to the absence of cuts. More detailed discussion of dataset analysis is given in subsection A.2.

ATTENTION-BASED MULTI-OBJECT TRACKING

Our goal is to build robust representations by leveraging the rich information in video frames. Standard SSL frameworks [START_REF] Chen | A simple framework for contrastive learning of visual representations[END_REF][START_REF] Caron | Unsupervised learning of visual features by contrasting cluster assignments[END_REF] often assume correspondences between different views. This is true whether using dense (Zhou et al., 2022a) or global representations by pooling [START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF]. While it is relatively straightforward to establish correspondences in images, it becomes more challenging when dealing with temporal deformations, requiring some form of object tracking [START_REF] Salehi | Time does tell: Selfsupervised time-tuning of dense image representations[END_REF]. In videos with a large field of view or ego-motion, obtaining correspondences becomes even more difficult. t with frame X t . We use those to mask X t (7), feed it to the student model and apply a distillation loss L O t between [CLS] token embeddings [START_REF] Loshchilov | Decoupled weight decay regularization[END_REF]. (Right) In the tracker, we obtain the query Q, key K and output Z embeddings. From the multi-head attention maps A i (1), we draw a subset I of k heads and form object prototypes P by pooling over patch queries Q (2). We refine them into P ′ to discover distinct objects, using Sinkhorn-Knopp (SK) to establish correspondences M * between P and patch embeddings Z (4) and pooling over Z (5). We then track the objects over frames X t by cross-attention T ′ t with patch key embeddings Kt (6).

⊗ 𝐾 ⊗ 𝑍 % 𝐴 ! 𝐴 " 𝐴 # 𝑄 % × 𝐴 $ 𝑃 concat heads; remove [CLS]
High-level idea We introduce DORA, based on multi-object Discovery and tRAcking. As shown in Figure 3, it leverages the attention from the [CLS] token of distinct heads in a vision transformer to identify and consistently track multiple objects within a given frame across temporal sequences. On these, a teacher-student distillation loss is then applied. Importantly, we do not use any off-theshelf object tracker or optical flow network. This keeps our pipeline simple and does not require any additional data or training. It also ensures that the learned representation is robust.

Preliminaries We are given a video clip consisting of T frames X t ∈ R h×w×c for t ∈ {1, . . . , T }, where h × w is the spatial resolution and c is the number of channels. Each frame is split into n = hw/p 2 non-overlapping patches of resolution p × p. The patches are linearly projected into embeddings of dimension d and a [CLS] token embedding is prepended. This representation is input to a transformer encoder [START_REF] Dosovitskiy | An image is worth 16x16 words: Transformers for image recognition at scale[END_REF]. The output embeddings are Z t = g θ (X t ) ∈ R (n+1)×d , where mapping g θ includes the tokenizer and encoder, while θ denotes its learnable parameters. Given an embedding Z ∈ R (n+1)×d , we write Z = [Z [CLS] ; Z], where

Z [CLS] ∈ R 1×d
is the [CLS] token embedding and Z ∈ R n×d are the patch embeddings.

Following DINO [START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF], there is a student network with parameters θ and a teacher network with identical architecture and parameters θ ′ obtained as the exponential moving average (EMA) of θ according to θ ′ ← αθ ′ + (1 -α)θ. The encoder is followed by a head that includes an MLP and a scaled softmax, such that the output token embeddings can be interpreted as probabilities.

We denote by f θ the mapping that includes the tokenizer, encoder and head.

Discovering objects with multi-head attention Starting at a first frame X t0 , we obtain the query and key embeddings Q, K ∈ R (n+1)×d from the last transformer layer of the teacher network * . According to multi-head attention, these embeddings are partitioned as

Q = [Q 1 , . . . , Q h ], K = [K 1 , . . . , K h ], where Q i , K i ∈ R (n+1)
×d/h for i = 1, . . . , h and h is the number of heads. For each head i, the self-attention matrix A i ∈ R (n+1)×(n+1) is based on the dot-product similarity between the query and key embeddings:

A i := softmax Q i (K i ) ⊤ / √ d ∈ R (n+1)×(n+1) . (1)
Given an attention matrix A ∈ R (n+1)×(n+1) , let A [CLS] := [a 1,2 , . . . , a 1,n ] ∈ R 1×n be the [CLS]attention vector between the [CLS] and patch embeddings, where a i,j is the element (i, j) of A. We draw at random a subset I := {i 1 , . . . , i k } of k < h heads and collect their [CLS]-attention vectors into A I := [(A i1 ) [CLS] ; . . . ; (A i k ) [CLS] ] ∈ R k×n . Intuitively, as expressed in rows of matrix A I , the different heads attend to different objects in the frame [START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF]. To represent the k objects in the embedding space, we use matrix A I ∈ R k×n to form linear combinations of patch embeddings Q ∈ R n×d , obtaining object prototypes

P := A I Q ∈ R k×d .
(2) This can be seen as the representation of k different [CLS] tokens in the full embedding space, capturing k objects at frame t 0 . Then, given the key embeddings K t ∈ R (n+1)×d at another frame t, we could track the objects by cross-attention

T t := softmax P K⊤ t / √ d ∈ R k×n , (3)
where Kt ∈ R n×d . Unfortunately, we observe in Figure 4 that the k attention maps obtained this way are spatially overlapping, meaning that each attention map is not delineating a single object.

Establishing object-patch correspondences To discover spatially distinct objects, we propose to establish correspondences between prototypes and patch tokens. Let Z = g θ ′ (X t0 ) ∈ R (n+1)×d be the output embeddings of the teacher network, still at frame t 0 . We seek a correspondence between the rows of P ∈ R k×d and Z ∈ R n×d , where Z are the patch token embeddings.

The goal is to find a transport plan M ∈ R k×n that minimizes the expected pairwise cost C := -P Z⊤ ∈ R k×n between prototypes and patches, while incorporating an entropic regularizer with coefficient ϵ. Matrix M is non-negative with row-wise sum 1/k and column-wise sum 1/n, representing a joint probability over P and Z with uniform marginals. The minimal solution M * is unique and can be found by forming the matrix e -C/ϵ and then applying the Sinkhorn-Knopp (SK) algorithm [START_REF] Cuturi | Sinkhorn distances: Lightspeed computation of optimal transport[END_REF], i.e., iteratively normalizing its rows and columns:

M * = SK exp P Z⊤ /ϵ ∈ R k×n , (4)
Observe the similarity with (1) and ( 3), where scaling is by √ d rather than ϵ, exp is included in softmax and normalization is on rows only rather than iterative. Then, similarly with (2), we use the optimal transport plan M * ∈ R k×n to form linear combinations of patch embeddings Z ∈ R n×d , obtaining the refined object prototypes

P ′ = M * Z ∈ R k×d .
(5)

Now, given the key embeddings K t ∈ R (n+1)×d at another frame t, we track the objects by the refined cross-attention, similarly with (3):

T ′ t := softmax P ′ K⊤ t / √ d ∈ R k×n , (6)
where Kt ∈ R n×d . Indeed, Figure 4 confirms that each of the k resulting attention maps is associated with a spatially distinct object, thanks to the established correspondences.

In contrast to previous works that use SK in the context of self-supervised learning to force an equipartitioning of images to cluster labels (Asano et al., 2020; Caron et al., 2020; Oquab et al., 2023), we rather use optimal transport to re-balance spatial correspondences to different objects.

Multi-object masking

We use the cross-attention (6) to mask the input video clip for the student network, such that each masked clip can be considered as a multi-object crop. This crop plays a similar role with local crops in DINO [START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF], but it has arbitrary shape and tracks an object over video frames. In particular, given an input frame X ∈ R h×w×c with cross-attention matrix T ′ ∈ R k×n (6) and an object i ∈ {1, . . . , k}, we reshape the i-th row of T ′ as h/p × w/p and upsample to a h × w attention map to match the spatial resolution of X, as shown in Figure 4.

We repeat along the channel dimension to form tensor T i ∈ R h×w×c and we mask X as

X oi := X ⊙ T i , ( 7
)
where ⊙ is the Hadamard product. Following DINO [START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF], given an input frame X t , we generate two standard resolution augmented global views X a t , X b t . We introduce a multi-object loss L O t for frame t, applied to the [CLS] token between the teacher f θ ′ output for one global view X u t and the student f θ output for the masked version X v,oi t of the other view X v t for i ∈ {1, . . . , k}, where u, v ∈ V = {a, b} and u ̸ = v:

L O t := u,v∈V 1 u̸ =v k i=1 f θ ′ (X u t ) [CLS] log f θ (X v,oi t ) [CLS] . (8)
In addition, as detailed in subsection B.1, we apply a local loss, following multi-crop [START_REF] Caron | Unsupervised learning of visual features by contrasting cluster assignments[END_REF]. The overall loss L is the sum of the two losses, averaged over all T frames.

EXPERIMENTS

SETUP

Tasks and methods We perform self-supervised pretraining on a single WT tour video in Venice (referred to as WT Venice ) or all 10 WT videos (referred to as WT all ) and compare with other image and video datasets. To evaluate the quality of the learned representations, we use frozen features for classification, unsupervised object discovery and video object segmentation. We fine-tune for semantic segmentation, object detection and object tracking. We compare DORA with SoTA SSL methods (da Costa et al., 2022) using our settings. We provide more details in individual sections per task. Implementation details and hyperparameters are given in Appendix B.

ABLATIONS

We examine the effect of using different pretraining video dataset and different options and parameters for DORA, measuring performance of classification on ImageNet-1k (

Number of tracked objects

We study the impact of the number k of objects. Objects are discovered using attention heads, where the total number of heads is in ViT-S/16 is h = 6. For k > h, we modify the MSA block as described in subsection B.2. In Table 2b, we observe that k = 3 works best. We hypothesize that this is a compromise between the number of objects that can be tracked and the multi-object loss (8) attempting to match small objects with the global crop.

Choice of masking and Sinkhorn-Knopp We explore the effect of using a multi-object mask (7) vs. random block-wise (Zhou et al., 2022a) and the effect of improving object-patch correspondence through SK in refined cross-attention (6) vs. (3). In Table 2c, we observe that a multi-object mask leads to a remarkable performance improvement even in the absence of SK. In fact, random blockwise mask undermines object-patch correspondence, making the effect of SK negative. By contrast, SK improves performance in the presence of multi-object mask. ). GOT-10k assesses the ability to track extremely fast moving objects, objects with illumination variation and low resolution. DORA achieves significant gains between 4-6% over DINO.

COMPARISON WITH STATE-OF-THE-ART

Dense scene understanding

Image classification and unsupervised object discovery We pretrain DORA on WTours and then we keep it frozen on the downstream task, indicating the quality of the pretrained features. Table 5(a) shows image classification on ImageNet-1k, measuring accuracy for linear probing and k-nearest neighbor. Table 5(b) shows unsupervised object discovery on Pascal-VOC 2012, using attention maps as segmentation masks to measure Jaccard similarity and CorLoc.

On both tasks, non-contrastive methods (DINO, iBOT, VICReg) outperform contrastive methods (SimCLR, SwAV), when pretrained on a single WT video. Importantly, non-contrastive methods are also more efficient to train, since no negative pairs are used. Also on both tasks, DORA outperforms DINO by a large margin, e.g. 11.6% LP and 3.9% k-NN on classification, when trained on a single WT video. Comparing DORA on WT Venice with the WT all dataset, the improvement brought by the full dataset is small when using DORA, although it is 10 times larger.

In Appendix D, we show that DORA outperforms SoTA methods on all tasks on ImageNet-1k.

CONCLUSIONS

We have introduced a dataset of 10 walking tour videos -first-person videos taken by people touring a city, with no cuts, high resolution and that are hours long. We show that learning from clips taken from these videos is surprisingly powerful: with an appropriately tailored self-supervised learning method for videos, we obtain representations that rival those obtained on ImageNet when transferring to popular downstream image and video tasks. This differs from previous state-of-theart approaches to learning image encoders from video, which also obtain such results but require large video datasets, following closely the ImageNet blueprint.

Our proposed learning method DORA is inspired by DINO, generalizing it to video by incorporating implicit multi-object tracking across video clips. We observe that the method leads to interesting emergent attention masks within the transformer model, that seem to latch on to particular objects, even through occlusions. This makes it uniquely suited to our newly introduced dataset. averaged self-attention map, extracted from the final layer of a our pretrained ViT-S/16, to retain 80% of the mass. We use the Jaccard similarity J measured as overlap between predicted mask P and the ground truth mask G as J(P, G) = G∩P G∪P . We also use CorLoc, which measures the number of correct predicted boxes, where a predicted box is said to be correct if its IoU ≥ 0.5. ADE20k: Semantic segmentation We evaluate DORA on ADE20k [START_REF] Zhou | Scene parsing through ade20k dataset[END_REF] for semantic segmentation. The dataset includes 20,000 images in the training set and 2,000 images in the validation set. We use UperNet [START_REF] Xiao | Unified perceptual parsing for scene understanding[END_REF] as the segmentation model and use DORA pretrained on WT to initialize the backbone. Following the experimental settings in iBOT (Zhou et al., 2022a), we use AdamW [START_REF] Loshchilov | Decoupled weight decay regularization[END_REF] with an initial learning rate of 6 × 10 -5 , weight decay of 1×10 -2 , and linear warmup of 1,500 iterations. We fine-tune for 160,000 iterations with a batch size of 4.

MS-COCO: Object detection

We evaluate DORA for object detection and instance segmentation on MS-COCO. We use Cascade Mask R-CNN [START_REF] Cai | Cascade r-cnn: High quality object detection and instance segmentation[END_REF], which produces bounding boxes and instance masks simultaneously on the COCO dataset. We use a multi-scale training strategy, where we resize images to have a shorter side ranging between 480 and 800, ensuring that the longer side does not exceed 1,333 pixels. The learning rate is 1 × 10 -4 and the weight decay is 0.05. During training, we fine-tune the entire network using a 1× schedule, which involves 12 epochs with learning rate reductions by a factor of 10 at epochs 9 and 11. We explore different layer decay rates, specifically 0.65, 0.75, 0.8, 0.9, with a rate of 1.0 indicating no decay.

To generate hierarchical feature maps, we utilize the features produced by layers 4, 6, 8, and 12 of our network and apply two deconvolutions for layer 4, one deconvolution for layer 6, identity mapping for layer 8, and max-pooling for layer 12. These post-processing steps enable the creation of hierarchical feature representations. It is important to note that we do not employ multi-scale testing in our experiments.

DAVIS-2017: Video object segmentation

We assess the performance of DORA for video object segmentation on DAVIS 2017 dataset (Pont-Tuset et al., 2017), which involves segmenting between 2 to 4 objects within the video frames. We follow DINO [START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF] and evaluate on video frames with a resolution of 480p. We apply label propagation on the attention map from our pretrained model and use mean region-based similarity J m and mean contour-based accuracy F m as our evaluation metrics.

GOT-10k: Object tracking We evaluate the object-tracking performance of DORA on the GOT-10k dataset [START_REF] Huang | Got-10k: A large high-diversity benchmark for generic object tracking in the wild[END_REF]. This is a large-scale benchmark for object tracking that contains 563 categories of common moving objects. The training set contains around 10,000 videos and the test set contains 180 videos. Another challenging aspect of this dataset is that the object classes in the training and test set are non-overlapping. We use the SeqTrack [START_REF] Chen | Seqtrack: Sequence to sequence learning for visual object tracking[END_REF] codebase to evaluate the performance of different methods on this dataset. In particular, we initialize the encoder weights of SeqTrack with the self-supervised weights and keep them frozen during training. While training, we only update the parameters of the lightweight decoder which consists of 2 transformer blocks. We use all the default hyperparameters. We report mean average overlap (mAO) and success rate (SR) at different thresholds. The mAO measures the class-balanced average overlap between the ground truth and predicted bounding boxes whereas SR indicates the percentage of accurately tracked ground truth bounding boxes where the overlap crosses a certain threshold.

C MORE ABLATIONS

Pretraining WT video We study the effect of pretraining on different videos of WTours. In Table 7a, we observe that the effect is minimal on both image classification and unsupervised object discovery. Notably, the fluctuation in illumination conditions within the Bangkok video influences the performance on image classification. It is also interesting to note that, while pretraining on Amsterdam is best on image classification, pretraining on Venice is best on object discovery. This could be due to the large overlap of objects in these videos with respect to the downstream datasets. However, the consistency of our method across diverse videos indicates that DORA is robust to variations in scenes, number of objects and lighting conditions. Figure 6: For each input frame X t of a video clip, refined cross-attention map T ′ t ∈ R k×n (6), using Sinkhorn-Knopp. For each object, one row of T ′ t is reshaped as h/p × w/p and upsampled to an h × w attention map overlaid on the input frame for k = 3 objects encoded in blue, red and green channel. T ′ t yields three well separated objects shown in blue, red and green.

Figures 5 and6 show example attention maps obtained using SK on different clips. These figures show that SK (6) leads to attention maps that exhibit spatial locality and are well aligned with objects in the scene. Remarkably, the masks seem to be even robust to occlusions, as shown in the sequence with a bicycle moving behind traffic lights.

Figure 2 :

 2 Figure 2: Dataset analysis of a WTours video compared with videos from Epic-Kitchens (Damen et al., 2022), AVA (Gu et al., 2018) and two entire movies, concatenated or cropped to match the duration of the WTours video. (a) Lightness vs. time. (b) Number of objects per frame vs. time. (c) Frequency of classes in entire video. (d) Number of shots. Objects detected by Detic (Zhou et al., 2022b), trained on ImageNet-21k.

Figure 3 :

 3 Figure3: DORA, our self-supervised image pretraining method from video. (Left) From an input frame X t0 , the output of the second-last layer of the teacher model is used by a multi-object tracker to generate cross-attention maps T ′ t with frame X t . We use those to mask X t(7), feed it to the student model and apply a distillation loss L O t between [CLS] token embeddings[START_REF] Loshchilov | Decoupled weight decay regularization[END_REF]. (Right) In the tracker, we obtain the query Q, key K and output Z embeddings. From the multi-head attention maps A i (1), we draw a subset I of k heads and form object prototypes P by pooling over patch queries Q (2). We refine them into P ′ to discover distinct objects, using Sinkhorn-Knopp (SK) to establish correspondences M * between P and patch embeddings Z (4) and pooling over Z (5). We then track the objects over frames X t by cross-attention T ′ t with patch key embeddings Kt (6).

Figure 4 :

 4 Figure 4: For each input frame t of a video clip (top), cross-attention map T t ∈ R k×n (3) (middle) and refined cross-attention map T ′ t ∈ R k×n (6) (bottom), using Sinkhorn-Knopp algorithm. For each object, one row of T t or T ′ t is reshaped as h/p × w/p and upsampled to an h × w attention map overlaid on the input frame for k = 3 objects encoded in blue, red and green channel. Mixed colors yellow and cyan for T t (middle, in red circle) indicate spatial overlap of two objects, while T ′ t (bottom) yields three well separated objects shown in primary colors blue, red and green.

  (a) Classification top-1 accuracy (%) on validation set of ImageNet-1k. LP: linear probing. (b) Unsupervised object discovery on validation set of Pascal-VOC 2012. Jacc.: Jaccard similarity; CorLoc: Correct Localization. Video understanding Table 4(a) shows video object segmentation by using frozen features on DAVIS-2017 (Pont-Tuset et al., 2017), which assesses the ability to segment an object over its dynamic temporal changes. DORA captures detailed temporal deformations and outperforms baseline DINO by 3.4% J m and 4.2% F m . Using only a single video for pretraining, DORA achieves almost the same performance of DINO pretrained on ImageNet (56.4% vs. 57.4% J m ). Table 4(b) shows multi-object tracking by fine-tuning on GOT-10k (Huang et al., 2021) using SeqTrack (Chen et al., 2023

Figure 5 :

 5 Figure 5: For each input frame X t of a video clip, refined cross-attention map T ′ t ∈ R k×n (6), using Sinkhorn-Knopp. For each object, one row of T ′ t is reshaped as h/p × w/p and upsampled to an h × w attention map overlaid on the input frame for k = 3 objects encoded in blue, red and green channel. T ′ t yields three well separated objects shown in blue, red and green.

Table 1 :

 1 Walking Tours vs. existing video datasets. EGO: egocentric; PRE: used for pretraining; BAL: class balance control; ANNOT: annotation type. Weak: associated data per clip (text or other modality); Class: class label per frame or clip; Loc: localization per frame (e.g. bounding box,

	DATASET	DOMAIN EGO PRE BAL ANNOT	AVG. DUR DUR #VIDEOS (SEC) (HR)	FRAME RESOLUTION
			Diverse Pretraining
	Kinetics-400 (Kay et al., 2017)	Actions	✗	✓	✓	Class	10.2	851	400	340 × 255
	AVA (Gu et al., 2018)	Actions	✗	✓	✓	Class	900	107.5	80	320 × 400
	WebVid-2M (Bain et al., 2021)	Open	✗	✓	✗	Weak	18	13k	-	320 × 240
	HowTo100M (Miech et al., 2019)	Instructions	✗	✓	✗	Weak	4	135k	-	-
				Egocentric
	Epic-Kitchens (Damen et al., 2022)	Cooking	✓	✗	✗	Loc.	510	100	37	1920 × 1080
	Ego-4D (Grauman et al., 2022)	Daily	✓	✗	✗	Loc.	1446	120	931	1920 × 1080
	Meccano (Ragusa et al., 2023)	Industry	✓	✗	✗	Loc.	1247	849	20	1920 × 1080
	Assembly-101 (Sener et al., 2022)	Assembly	✓	✗	✗	Loc.	426	167	362	1920 × 1080
			ImageNet-aligned
	R2V2 (Gordon et al., 2020)	ImageNet	✗	✓	✓	Class	-	-	-	467 × 280
	VideoNet (Parthasarathy et al., 2023) ImageNet	✗	✓	✓	Class	10	3055	-
	Walking Tours (ours)	Urban	✓	✓	✗	None	4968	23	10	3840 × 2160
										2020;
	Wang & Gupta, 2015; Orhan et al., 2020). Similar to this work, TimeTuning (Salehi et al., 2023)
	leverages the passage of time in videos by not treating it as simple augmentations. However, in
	contrast to our work, it requires an already image-pretrained backbone. VITO (Parthasarathy et al.,
	2023) improves performance relative to ImageNet, by using VideoNet, a large YouTube dataset of
	10s videos from a similar class distribution and the same number of examples as ImageNet. In this
	paper, we show that it is possible to obtain strong results from a single long video, with a very
	different visual distribution compared to ImageNet / VideoNet.
	3 WALKING TOURS DATASET
	3.1 DATASET COLLECTION AND PROPERTIES
	We collect from YouTube a new dataset of urban scenes called "Walking Tours" (WTours, or WT)
	comprising 10 egocentric videos of a person walking in different cities in Europe and Asia. The
	cities include Amsterdam, Bangkok, Chiang Mai, Istanbul, Kuala Lampur, Singapore, Stockholm,
	Venice, and Zurich. We also include a video from a Wildlife safari. Examples are shown in Figure 1.
	These videos are captured in 4K resolution (3840 × 2160 pixels) at 60 frames-per-second and are
	under Creative Commons License (CC-BY). The minimum video duration is 59 minutes (Wildlife
	safari), the maximum is 2 hours 55 minutes (Bangkok) and the average is 1 hour 38 minutes. Such
	videos are particularly interesting for visual learning because of the following properties:

Agrawal et al., 2015; Jayaraman & Grauman, 2015), active recognition (Jayaraman & Grauman, 2016), pose estimation (Chakraborty & Namboodiri, 2017), unsupervised object discovery (Croitoru et al., 2017), dense prediction (Pathak et al., 2017; Li et al., 2019), optical flow (Mahendran et al., 2018; Xiong et al., 2021), frame order prediction (Misra et al., 2016), view-point matching (Sermanet et al., 2018; Pirk et al., 2020) or learning visual correspondences (Wang et al., 2019). More recently, there have been considerable advances in self-supervised learning using ImageNet, with the main theme being extracting multiple augmentations of an image (Chen et al., 2020; Caron segmentation, mask 3D pose). AVG. DUR: average duration per video; DUR: total duration. et al., 2021) and training models to pull them together/apart. These methods have since percolated to learning from video frames (Gordon et al., 2020; Parthasarathy et al., 2023; Tschannen et al.,

Table 1

 1

, we compare WTours with existing video datasets. In summary, self-supervised pretraining on videos has been mostly limited to short, low-resolution datasets that rely on weak annotation in the form of video-text pairs

[START_REF] Bain | Frozen in time: A joint video and image encoder for end-to-end retrieval[END_REF][START_REF] Miech | Howto100m: Learning a text-video embedding by watching hundred million narrated video clips[END_REF]

or are curated, e.g. their class balance is controlled, even if their annotation is unused

[START_REF] Kay | The kinetics human action video dataset[END_REF]

). ImageNetaligned datasets (Gordon et al., 2020; Parthasarathy et al., 2023) contain short videos that are (semiautomatically) curated and annotated with the same distribution and classes as ImageNet. Egocentric video datasets (Damen et al., 2022; Grauman et al., 2022; Sener et al., 2022) have long, high-quality videos, but are the result of significant manual work. In this paper we aim to learn from videos publicly available online.

Table 2 :

 2 Effect of parameters. ViT-S/16 pretrained, then frozen. (a) Different pretraining video dataset, (b) Number k of tracked objects. (c) Random or multi-object mask, without SK (3) and with SK (6). * : subset of videos with same total duration as a single WTours video. K-400: Kinetics-400, EK: Epic-Kitchens. LP: top-1 accuracy (%) of linear probing on the validation set of ImageNet-1k. CorLoc: correct localization on validation set of Pascal-VOC 2012.

	METHOD	EPOCHS PRETRAIN	(a) SEMANTIC SEG. mIoU GAIN Accm GAIN mAP (b) OBJECT DET. (c) INSTANCE SEG. GAIN mIoU GAIN
	ViT-S/16	100	None	25.1		33.3	28.6		24.3
	iBOT (Zhou et al., 2022a)	100	WTVenice	33.9		43.3	37.6		33.0
	AttMask (Kakogeorgiou et al., 2022)	100	WTVenice	33.6		42.7	36.5		32.5
	VITO (Parthasarathy et al., 2023)	300	VideoNet	39.4		-	44.0		-
	DINO (Caron et al., 2021)	100	IN-1k	33.9		44.3	39.9		35.1
	DORA (ours)	100	WTall	36.9		48.0	40.7		36.3
	DINO (Caron et al., 2021)	100	WTVenice	32.4		43.7	37.1		32.1
	DORA (ours)	100	WTVenice	35.4	+3.0	45.5	+1.8 39.5	+2.4	34.7	+2.6

Table 3 :

 3 Semantic

segmentation, object detection and instance segmentation. ViT-S/16 pretrained, then fine-tuned. WT Venice : Walking Tours (ours), single video of Venice; WT all : all videos. IN-1k: ImageNet-1k. (a) Semantic segmentation: fine-tuning on ADE20k using UperNet. mIoU: mean IoU; Acc m : mean-class accuracy. (b) Object detection and (c) Instance segmentation: fine-tuning on MS-COCO using Cascade RCNN. mAP: mean average precision; mIoU: mean IoU.

Table 3

 3 GAIN Jm GAIN Fm GAIN mAO GAIN SR0.5 GAIN SR0.75 GAIN ViT[START_REF] Dosovitskiy | An image is worth 16x16 words: Transformers for image recognition at scale[END_REF]

	(a) shows semantic segmentation by fine-tuning on
	ADE20k (Zhou et al., 2017) using UperNet (Xiao et al., 2018). DORA outperforms DINO by
	3% mIoU, and 1.8% Acc m . It is interesting to note that DORA pretrained on 200k frames of a sin-
	gle WTours video outperforms DINO pretrained on 1.3M images of ImageNet-1k by 1.5% mIoU. A
	more comparable setting is DORA pretrained on 1.5M frames of WT

all , which outperforms DINO pretrained on ImageNet by 3% mIoU. Table 3(b) shows object detection and instance segmentation by fine-tuning on MS-COCO (Lin et al., 2014) using Cascade RCNN

[START_REF] Cai | Cascade r-cnn: High quality object detection and instance segmentation[END_REF]

. DORA outperforms DINO by 2.4% mAP and 2.6% mIoU. DORA pretrained on WT all outperforms DINO pretrained on ImageNet by 0.8% mIoU and 1.2% mAP. This shows that pretraining on WTours videos significantly improves the generality of DORA to dense prediction tasks, requiring only one tenth of the total images.

Table 4 :

 4 Video object segmentation and object tracking. ViT-S/16 pretrained, then frozen or finetuned. WT Venice : Walking Tours (ours), single video from Venice; WT all : all videos. IN-1k: ImageNet-1k. (a) Video object segmentation: frozen features on DAVIS-2017. J m : mean region similarity; F m : mean contour-based accuracy. (b) Multi-object tracking: fine-tuning on GOT-10k. mAO: mean average overlap; SR: success rate, threshold 50% and 75%.

	METHOD	EPOCHS PRETRAIN	#FRAMES (M)	(a) CLASSIFICATION LP GAIN k-NN GAIN JACC. GAIN CORLOC GAIN (b) OBJECT DISCOVERY
	SimCLR (Chen et al., 2020)	100	WTVenice	0.2	26.3	25.9	40.4	50.2
	SwAV (Caron et al., 2020)	100	WTVenice	0.2	28.0	26.4	40.6	51.4
	iBOT (Zhou et al., 2022a)	100	WTVenice	0.2	36.8	32.8	43.0	53.1
	AttMask (Kakogeorgiou et al., 2022)	100	WTVenice	0.2	35.8	31.9	43.5	54.5
	VicReg (Bardes et al., 2021)	100	WTVenice	0.2	36.5	30.1	42.7	52.1
	DINO (Caron et al., 2021)	100	WTVenice	0.2	33.8	29.9	43.8	51.2
	DORA (ours)	100	WTVenice	0.2	45.4 +11.6 33.8 +3.9 44.0 +0.2	56.2	+5.0
	DINO (Caron et al., 2021)	100	WTall	1.5	36.6	31.1	42.9	55.8
	DORA (ours)	100	WTall	1.5	45.3 +8.7	35.7 +4.6 44.3 +1.4	57.1	+1.3

Table 5 :

 5 Image classification and object discovery. ViT-S/16 pretrained, then frozen. WT Venice : Walking Tours (ours), single video from Venice; WT all : all videos.

Table 6 ,

 6 Comparison with other video datasets . . . . . . . . . . . . . . . . . . . . . . . 1 A.2 Dataset analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Multi-crop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 B.2 Implementation details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 B.3 Hyperparameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 we provide statistics of individual videos in the WTours dataset. In the following, we first compare WTours with other video datasets and then analyze WTours videos in terms of automatically extracted information, including lightness, shot changes and number of objects and categories depicted.

	Is ImageNet worth 1 video? Learning strong image
	encoders from 1 long unlabelled video
	Supplementary Material
	Table of Contents
	A More on Walking Tours	1
	A.1 B More on experimental setup	3
	B.1 C More ablations	4
	D More comparisons with state of the art	5
	E More visualizations	8
	A MORE ON WALKING TOURS
	In A.1 COMPARISON WITH OTHER VIDEO DATASETS
	In

Table 1 ,

 1 we compare WTours with different types of existing video datasets. Self-supervised pretraining on videos has been mostly limited to video datasets that rely on weak annotation in the form of video-text pairs[START_REF] Bain | Frozen in time: A joint video and image encoder for end-to-end retrieval[END_REF][START_REF] Miech | Howto100m: Learning a text-video embedding by watching hundred million narrated video clips[END_REF] or even are curated, e.g. their class balance is controlled, even if their annotation is unused[START_REF] Kay | The kinetics human action video dataset[END_REF]. Their average clip duration is small, e.g. less than 20 sec, and their resolution is also small, limiting the capacity to detect objects at a greater distance. By contrast, WTours videos are continuous, hours-long at high resolution and provide natural transitions of scenes and viewing conditions. They are not curated and thus better suited for the self-supervised setting.

	ImageNet-aligned datasets such as R2V2 (Gordon et al., 2020) and VideoNet (Parthasarathy et al.,
	2023) contain videos that are curated and annotated with the same distribution and classes as Ima-
	geNet, meant for pretraining image encoders. These videos are short, i.e. 10 seconds on average. By

contrast, WTours consists of a continuous stream of egocentric video, where the average number of classes is close to that of ImageNet, as shown in subsection 3.3. The rich information contained in 4K resolution, together with a high number of objects in a frame, makes it appropriate for representation learning. Importantly, the continuity and absence of curation make it more realistic and more comparable with human learning. Our dataset does not rely on a set of objects, human activities or other search terms but instead is data-first and more open-ended.

* For simplicity, we drop t0 from the notation.

† https://stephenfollows.com/many-shots-average-movie/

ACKNOWLEDGEMENTS

This work was in part supported by the ANR-19-CE23-0028 MEERQAT project and was performed using the HPC resources from GENCI-IDRIS Grant 2021 AD011012528. We also thank Dilara Gokay and Andrew Zisserman for their valuable feedback on this paper.

A.2 DATASET ANALYSIS

Here we present a more detailed discussion on the dataset analysis of subsection 3.3. We refer to Figure 2, where we analyse the properties of a single WTours video compared with videos of the same length from Epic-Kitchens [START_REF] Damen | Rescaling egocentric vision: Collection, pipeline and challenges for epic-kitchens-100[END_REF] and AVA [START_REF] Gu | Ava: A video dataset of spatiotemporally localized atomic visual actions[END_REF] datasets, as well as two movie videos, an action movie and a romantic movie.

Variation in lightness We measure the change in perceived brightness using the lightness value (L) across consecutive frames. From Figure 2(a), we observe a gradual shift at roughly 150 min into the WTours video, transitioning from bright to dim to dark. By contrast, Epic-Kitchens and AVA videos exhibit random brightness fluctuations, alternating between dim and bright conditions. Typically, self-supervised pretraining happens on datasets with uniform brightness levels. Datasets featuring such brightness variations are less expored.

Variation in number of objects Using Detic (Zhou et al., 2022b), a DETR-style object detector trained on ImageNet-21k, we detect objects in each frame.

The overall loss L is the sum of the multi-object loss L O t (8) and the local loss L LC t (9), averaged over all T frames: Instead, we apply multi-crop to a 300 × 300 crop that we first take from the frame. Following DINO [START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF], we obtain two global crops and six local crops. Masking ( 7) is applied to the global crops seen by the student for the multi-object loss (8), while local crops are seen directly by the student for the local loss (9). We train for 100 epochs by default.

Objects are discovered using attention heads, where the total number of heads is in ViT-S/16 is limited to h = 6. For the purpose of the ablation of the number k of objects for k > h in Table 2b, we modify the MSA block in the final layer, resulting in configurations of 16 and 32 heads. Consequently, we can identify and track up to 16 and 32 objects within the video clip. To accomplish this, we decompose the query and key embeddings of dimension d = 768 into 16 and 32 subvectors, resulting in new feature dimensions of 24 and 12 respectively, as opposed to 64 for 6 heads.

In Table 2b, we observe that tracking 16 or 32 objects results in overall poor performance possibly due to the small feature dimension, which encodes poor representations.

B.3 HYPERPARAMETERS

ImageNet-1k: Linear probing and k-NN We pretrain DORA in a self-supervised setting with ViT-S/16 using DINO for 100 and 300 epochs. We use two global and six local crops for each clip and train on 8 A100 GPUs with a global batch size of 16 × 8 = 128. We use LARS with a learning rate of 5 × 10 -4 , minimum learning rate of 5) or fine-tuned (semantic segmentation and object detection, same settings as Table 3). DORA ⋆ : DORA without tracking; when pretrained for 60 epochs, it has the same training time as DINO and iBOT.

Presence of cuts

We now analyse the effect of cuts in representation learning. Cuts are defined as instant transitions from one shot to the next, which is frequent in movies. In action movies, a single shot lasts around 4 seconds, while in romance movies, around 12 seconds on average † . To understand the effect of cuts, we compare pretraining on WTours videos and a romance movie. We use PySceneDetect (Castellano) to extract the cut timestamps in the movie and we pretrain DORA by sampling clips that do not intersect cuts; cuts naturally do not exist in WT videos. In Table 7b, we observe that the performance improves significantly in the absence of cuts, as tracking in DORA will fail across a cut.

D MORE COMPARISONS WITH STATE OF THE ART

Pretraining on ImageNet-1k We pretrain DORA on ImageNet-1k and compare with SoTA methods on multiple tasks. Unlike videos, we discover objects but do not track them. Instead, images in a mini-batch are processed independently. Given an input image X, we obtain refined object prototypes as usual (5), but the refined cross-attention ( 6) is with Kt replaced by K of the same image X. The same image X is masked for the student (7). The loss is given again by ( 8) and ( 9) with X t replaced by X, averaged over the mini-batch. We refer to this version as DORA without tracking or DORA ⋆ .

DINO [START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF] and iBOT (Zhou et al., 2022a) use only one global crop for the student, while DORA uses k object crops. To compensate, we perform an experiment where we pretrain DORA ⋆ for 60 epochs and the competitors for 100, thus all methods having the same training time.

From Table 8, we observe that DORA outperforms state-of-the-art self-supervised learning (SSL) methods like DINO and iBOT on image downstream tasks. This demonstrates that the multi-object loss not only enhances performance when pretrained on WTours videos but also achieves superior results when pretrained on ImageNet-1k images.


Keywords: combinatorics, random generation, Motzkin number, Catalan number, binary tree, unary-binary tree

Fig. 1: Rémy's right insertion of a leaf

In this paper, I consider three families of binary trees (planar binary trees or Catalan trees, Motzkin trees aka unary-binary trees, Schröder trees) and their random generation. It turns out that holonomic recurrences play a key role in the design of efficient random generation algorithms.

The three examples: binary trees, Motzkin trees, Schröder trees are interesting because they have different holonomic equations, one (Catalan numbers) has one term on the right, one (Motzkin numbers) has a sum of two terms on the right and one (Schröder numbers) has a subtraction of two terms, on the right. These yield different random generation algorithms, as this will be explained further in this paper.

This paper is associated with a library of programs written in Haskell and in Python, available on GitHub. The reader who wants to read a better rendering of the programs of this paper is invited to get the version on my web page or the version available on GitHub.

Random binary trees

 for generation of random binary trees is of linear complexity, i.e., O(n). It is based on a constructive proof of the holonomic equation [25]:

). An insertion is also possible at the root. In this case, the new inserted node becomes the root. The root can be seen as the child of a hypothetical node A binary tree of size n has n -1 internal nodes and n leaves. We label binary trees with numbers between 0 and 2n -2 such that internal nodes are labeled with odd numbers and leaves are labeled with even numbers. Inserting a node in a binary tree of size n requires drawing randomly a number between 0 and 4n -3. This process can be optimized by representing a binary tree as a list (a vector in Haskell), an idea sketched by Rémy and described by Knuth. In this vector, even values are for internal nodes and odd values are for leaves. The root is located at index 0. The left child of an internal node with label 2k + 1 is located at index 2k + 1 and its right child is located at index 2k + 2. Here is a vector representing a binary tree with 10 leaves and its drawing.

Introduction

In this paper, I am interested in efficient algorithms for randomly generating several sorts of binary trees. For this, I consider recurrences defining sequences of integer coefficients and, more precisely, I am interested in specific recurrences F n called "holonomic recurrence" where roughly speaking, "holonomic" means that F n+s is a combination, using polynomials in n, of the F i 's, for n ≤ i ≤ n + s. More precisely, (see Flajolet and Sedgewick's book [START_REF] Flajolet | Analytic Combinatorics[END_REF], Appendix B.4) the coefficients fulfill the following recurrence: P s (n)F n+s + P s-1 (n)F n+s-1 + ... + P 0 (n)F n = 0 for some n ≥ n 0 , where the P j (n) are polynomials in n. This kind of recurrence is called a P -recurrence. For instance, for Catalan numbers:

C n - n-1 ∑ k=0 C k C n-k-1 = 0
is the classical recurrence that is used in general to defined them, but it is not a P -recurrence, whereas (n + 1)C n -2(2n -1)C n-1 = 0 is the P -recurrence, which will be considered later on. Notice that initial values should be added to this P -recurrence. This will be considered in the paper for each specific case. indices 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 [START_REF] Flajolet | A calculus for the random generation of labelled combinatorial structures[END_REF] This tree was built by inserting the node 17 together with the leaf 18 in the following vector. This was done by drawing a node (internal node or leaf, here the node with label 6, right child of the node with label 9) and a direction (here right) and by inserting above this node a new internal node (labeled 17) and, below the new inserted internal node, a new leaf of the left (labeled 18). This double action (inserting the internal node and attaching the leaf) is done by choosing a number in the interval [0..33] (in general, in the interval [0..(4n -3)]). Assume that in this case the random generator returns 21. 21 contains two pieces of information : its parity (a boolean) and floor of its half. Half of 21 is 10, which tells that the new node 17 must be inserted above the 11 th node (in the vector) namely 6. Since 21 is odd, the rest of the tree (here reduced to the leaf 6) is inserted on the right (otherwise it would be inserted on the left). A new leaf 18 is inserted on the left (otherwise it would be inserted on the right).

Consider the same tree and suppose that the random value is 8. Half of 8 is 4. Hence the new internal node labeled by 17 is inserted above the node labeled by 5 and, since 8 is even, the rest of the tree is inserted on the left and a new leaf (labeled 18) is inserted on the right. The algorithm (Figure 2) works as follows. If n = 0, Rémy's algorithm returns the vector starting at 0 and filled with anything, since the whole algorithm works on the same vector with the same size. In general, say that, for n -1, Rémy's algorithm returns a vector v (vector is the concept used in Haskell for arrays that can be changed in place). In our Haskell implementation the function yields an object of type Gen (Vector Int) which returns vector and carries a hidden random number generator. One accesses to the generator by get and stores the new generator by put. One draws a random integer x between 0 and 4n -3. Let k be half of x. In the vector v one replaces the k th position with 2n -1 and one appends two elements, namely the k th item of v followed by 2n if x is even and 2n followed by the

k th item of v if x is odd.
The algorithm builds a uniformly random decorated binary tree, i.e., a binary tree with its leaves numbered 0, 2,... 2n. We notice that the construction of a tree with such labels is unique, the labels of the internal nodes are a consequence of the construction, hence are deduced from the labels of the leaves. If --x is a random value between 0 and 4n-3 --

k = x ' div ' 2 case even x of True -> return(v // [( k,2 * n-1),(2 * n-1,v!k ),(2 * n,2 * n )]) False -> return(v // [( k,2 * n-1),(2 * n-1,2 * n),(2 * n,v!k )])
Fig. 2: Haskell program for Rémy's algorithm we ignore the leaves, we get a uniform distribution for the undecorated binary trees (i.e., with no labels on the leaves).

In the program, rands is a vector of random floating numbers between 0 and 1.

Motzkin trees

Motzkin trees are also called unary-binary trees. This paper proposes an algorithm for random generation of Motzkin trees. The algorithm takes the same paradigm as this of Rémy's linear algorithm for random generation of binary trees [START_REF] Rémy | Un procédé itératif de dénombrement d'arbres binaires et son application à leur génération aléatoire[END_REF]. Assume n is the size of the trees. My algorithm for random generation of Motzkin trees is based on a bijective proof due to Dulucq and Penaud [START_REF] Dulucq | Interprétation bijective d'une récurrence des nombres de Motzkin[END_REF] of the inductive equality:

(n + 2)M n = (2n + 1)M n-1 + 3(n -1)M n-2
where the M n 's are the Motzkin numbers. At some point of the algorithm, an "oracle" choices which subprogram to call, based on M n-1 and M n-2 . Since M n-1 and M n-2 are big numbers, this induces potentially a not O(1) computation. A preprocessing allows a constant time computation for the oracle.

Motzkin numbers and Motzkin trees

The n th Motzkin number M n is the number of different ways of drawing non-intersecting chords between n points on a circle (not necessarily touching every point by a chord). Motzkin numbers count also well parenthesized expressions with a constant c, called Motzkin words. They are words of length n in the language generated by the grammar M . The bijection between sets of non intersecting chords and well parenthesized words with constant c is as follows: first one numbers nodes on the circle counterclockwise, as follows:

M = ε | c M | (M ) M
A position at the beginning of a chord on the circle corresponds to an opening parenthesis. A position at the end of a chord on the circle corresponds to a closing parenthesis. A position which is neither of those corresponds to the constant c.

Motzkin numbers count also routes in the upper quadrant from (0, 0) to (0, 4) with move up, down and straight.

The bijection is as follows: an opening parenthesis corresponds to an up, a closing parenthesis corresponds to a down and the constant c corresponds to a straight.

Motzkin number M n counts also the number in unary-binary planar trees with n edges, that are tree structures with nodes of arity one or two and with n edges. Let us call this number n of edges the size of the Motzkin tree. Notice that the number of nodes of a Motzkin tee of size n is n + 1, i.e., the size plus one. Figure 6 gives the trees for n = 4. The bijection f from well parenthesized expressions with constant

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •
Fig. 5: The 9 routes in the upper right quadrant from (0, 0) to (0, 4) with move up, down and straight c to Motzkin trees is as follows. Its inverse f -1 is also given.

f [ε] = • f [c w] = • f [w] f [(w 1 ) w 2 ] = • f [w 1 ] f [w 2 ] f -1 [•] = ε f -1 ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ • t ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ = c f -1 [t] f -1 ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ • t 1 t 2 ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ = (f -1 [t 1 ]) f -1 [t 2 ]
Motzkin numbers fulfill the equation:

M n+1 = M n + n-1 ∑ i=0 M i M n-1-i 5

Dulucq-Penaud bijection proof

As I said, Motzkin numbers fulfill the holonomic equation [START_REF] Flajolet | Analytic Combinatorics[END_REF]:

(n + 2)M n = (2n + 1)M n-1 + 3(n -1)M n-2 .
Together with the equalities M 0 = 1 and M 1 = 1, Motzkin numbers can be computed and form the sequence A001006 in the online encyclopedia of integer sequences [START_REF]The on-line encyclopedia of integer sequences[END_REF]. In this section, I present Dulucq and Penaud's proof of this equality [START_REF] Dulucq | Interprétation bijective d'une récurrence des nombres de Motzkin[END_REF]. This proof relies on the exhibition of a bijection between the objects counted by the left-hand side and those counted by the right-hand side. The first idea is to consider specific binary trees called slanting binary trees and divide those trees into 7 subclasses.

Slanting binary trees

Following Dulucq and Penaud, I represent Motzkin trees as specific binary trees in which leaves are added. In such binary trees, only the three first configurations below are allowed and the fourth and rightmost one is not.

Pierre Lescanne The first configuration corresponds to a binary node, the second configuration corresponds to a unary node and the third configuration corresponds to an end node in the classical presentation (for instance in Figure 6). I call such trees slanting trees or binary slanting trees, from the french arbres binaires penchés.

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •
Figure 6 shows the 9 Motzkin trees with 4 edges and their corresponding slanting trees. Let us label each node of a slanting tree with a number between 1 and 2m+1, where m is the number of internal nodes of the slanting tree. Let us call such a labeled tree a labeled slanting tree. Now consider labeled slanting trees with one marked leaf. Let us call it a leaf-marked slanting tree. Below there is a labeled slanting tree of size 4 and a leaf-marked labeled slanting tree, where the mark is on the leaf labeled 8. This corresponds to the vector [3, 0, 2, 5, 4, 7, 1, 6, 8].

How nodes and leaves are labeled by numbers will be explained below and is essentially like binary trees. Like binary trees, just notice that internal nodes have odd labels and leaves have even labels. From now on, let us forget the labels, but let us mark one of the leaves. In such trees with a marked leaf, we can distinguish 7 general patterns of subtrees containing the marked leaf (Figure 7 first column). The marked leaf is denoted by a star in a square, namely ⋆ . In the first group of 4 slanting trees, there are the patterns where the marked leaf is a right child and in the second group of 3 slanting trees, there are the patterns where the marked leaf is a left child, hence, due to the constraints on slanting trees, the other child (a right child) is a leaf as well.

Let us call node-marked a slanting tree in which one internal node is marked. Let us call marked tree, a slanting tree in which either a leaf or an internal node is marked.

How many leaves in a Motzkin tree?

The slanting tree associated with a Motzkin tree of size n (number of its edges) has n + 2 leaves. This can be shown by induction.

Basic case: If the Motzkin tree is •, its size is 0 and its associated slanting tree has 2 leaves.

Adding a unary node: Assume we add a unary node above a Motzkin tree t of size n, this yields a Motzkin tree t ′ of size n + 1 . The slanting tree associated with t ′ has n + 2 leaves (the number of the leave of the slanting tree u associated with t) plus a new one added, then all together n + 3.

t → t u → u
Adding a binary node: Assume we add a binary node above two Motzkin trees t 1 and t 2 of size n 1 and

Pierre Lescanne

leaf-marked Choice and slanting trees marked node-marked slanting trees slanting trees 1.

⋆ ▲ ▲ ⋆ ▲ ▲ 2.

A taxonomy of slanting trees

Recall Rémy's algorithm which consists in inserting, at a marked position (internal node or leaf), a leaf in a marked tree (see Figure 1). After insertion, the formerly marked node becomes unmarked and the inserted leaf becomes marked. Here, since we are interested in Motzkin trees, we insert a leaf on the right, above the marked node in the marked slanting tree and like in Rémy's algorithm, a leaf insertion on a marked slanting tree is performed, but unlike Rémy's algorithm the insertion is performed only on the right and a leaf-marked slanting tree is produced. This corresponds to what is done to pattern1, pattern3 and pattern4 in the middle column of Figure 7. The leaf is inserted at a marked position in the marked tree of the middle column producing the leaf-marked tree of the left column. But as we will see for the other patterns, there are other ways to increase a slanting tree when it does not correspond to one of these three patterns.

The bijection

Beside the fact one works on slanting trees with constraints, what makes also the random generation of Motzkin trees trickier than Rémy's algorithm is the structure of the holonomic equation:

(n + 2)M n = (2n + 1)M n-1 + 3(n -1)M n-2
when compared to the equation:

(n + 1)C n = 2(2n -1)C n-1
First, if we use a construction based on that equation, a Motzkin tree of size n can be built from a Motzkin tree of size n -1 or from a Motzkin tree of size n -2. Thus there are at least two cases to consider. Actually 7 cases as we will see, since the construction of a Motzkin tree of size n -1 splits in 4 cases and the construction of a Motzkin tree of size n -2 splits in 3 cases. Notice that M n counts both the number of Motzkin trees of size n and the slanting trees with n + 2 leaves.

Interpreting the holonomic equation

We conclude that (n+2)M n counts the number of leaf-marked slanting trees of size n, that (2n+1)M n-1 counts the number of marked slanting trees of size n -1 and that (n -1)M n-2 counts the number of node-marked slanting trees of size n -2. Therefore looking at the equation, we see that we should be able to build a leaf-marked slanting tree of size n from either a marked slanting tree of size n -1 or from a pair made of an item which can take one of three values and of a node-marked slanting tree of size n -2. Let us see how Dulucq and Penaud propose to proceed.

A taxonomy of leaf-marked slanting trees

Leaf-marked slanting trees can be sorted according to the position of their mark. This is done in the first column of Figure 7. This column has two parts.

The upper part

In the upper part, we have four patterns in which the marked leaf is a right child. Let us call them pattern1, pattern2, pattern3 and pattern4 (Figure 7). Three of them pattern1, pattern3 and pattern4 are obtained by Rémy's right insertion of a leaf in a marked slanting tree. The other pattern2 is not. Indeed if the marked leaf is removed, the tree that is obtained has a leaf on the left and a node on the right, which is forbidden. This pattern will be obtained another way.

The lower part

In the lower part, there are three patterns which correspond to the case where the marked leaf is a left child, hence the sibling of a leaf (Figure 9); pattern7 cannot be obtained by a right insertion of a leaf (Figure 7). I annotate it with a . But Dulucq and Penaud noticed that pattern ⋆ among marked slanting trees is not taken into consideration. Thus they propose to associate this pattern ⋆ with pattern7, as shown in Figure 7. The previously explained contribution to leaf-marked slanting trees of size n from marked slanting tree of size n -1 is summarized in Figure 8. All the patterns of marked slanting trees are taken into account.

1 ⋆ ▲ ▲ ⋆ ▲ ▲ 3 ⋆ ⋆ 4 ▲ ▲ ⋆ ⋆ ▲ ▲

Case 3(n -1)M n-2

Let us now look at the three remaining patterns: pattern2, pattern5 and pattern6; forming the lines of Figure 9. Those three patterns have the same model, namely an internal node with two children: one child is an internal node and the other child is an internal node whose children are two leaves, one of which is marked, the other is not. Depending on the position of the marked leaf, we distinguish three cases.

• LL corresponds to the case where the marked node is on the left of the top node and on the left of its parent node.

• LR corresponds to the case where the marked node is on the left of the top node and on the right of its parent node.

• RL corresponds to the case where the marked node is on the right of the top node and on the left of its parent node.

One notices that there is no case RR, because this would correspond to pattern4 considered in the previous section. As a matter of fact, the three cases LL, LR and RL correspond to the multiplicative factor 3 in the holonomic equation.

2 ⋆ ▲ ▲ LR ⋆ ▲ ▲ 5 ▲ ▲ ⋆ RL ⋆ ▲ ▲ 6 ⋆ ▲ ▲ LL ⋆ ▲ ▲

Forgetting the marks on leaves

As Rémy noticed for binary trees, since we generate the leaf-marked slanting trees of size n uniformly, we also get a uniform distribution of slanting trees of size n. Thus we can forget the marks, which we do in the concrete algorithm.

A concrete algorithm for random generation of Motzkin trees

The Haskell program of Figure 10 presents the algorithm for random generation of Motzkin trees. In what follows, I make no distinction between the algorithm and the program and I consider the Haskell program as an executable specification. The main function is called rMt and returns an object of type Gen (Vector Int) like rbt in Figure 2.

Assume that there is a function motzkin that returns the n th Motzkin number. Like for Rémy's algorithm, one represents a labeled slanting tree by a vector. In this vector, odd labels are for internal and even labels are for leaves. Notice that the algorithm preserves two properties:

1. The vector codes a slanting tree.

2. The vector of a Motzkin tree of size n has a length 2n + 3.

In order to choose which case to consider, namely (2n + 1)M n-1 (case1) or 3(n -1)M n-2 (case2), the algorithm rMt requires a random value between 0 and (n + 2)M n which we call r. If r is less than or equal to (2n + 1)M n-1 , we are in case1, else we are in case2. Said otherwise, given a random value c between 0 and

1 if c ≤ (2n+1)M n-1 (n+2)Mn
we choose case1, if not we choose case2. More abstractly, let us forget Motzkin numbers and consider an oracle which, given a random number r between 0 and 1 and an n chooses between case1 and case2. If the oracle runs in constant time and returns a boolean according to the distribution given by the above inequality then the algorithm has a linear time complexity and returns a random Motzkin tree distributed according to the above inequality. • case1: one draws at random a leaf or an internal node in a slanting tree of size n -1. This means choosing at random an index k in the vector v. We get pattern7 if three conditions are fulfilled.

Pierre Lescanne

case odd k || odd (v!k) || odd (v !( k-1)) of True -> return $ v // [( k,2 * n+1),(2 * n+1,v!k ),(2 * n+2,2 * n+2)] False -> return $ v // [( k-1,2 * n+1),(2 * n+1,v!(k-1)),( 2
1. The marked item, should be a right child. This means that k is even, since the left child of a node of index 2p + 1 is 2p + 1 and the right child of this node is 2p + 2.

2.

The marked item is a leaf. This means that v[k] is even, since leaves have even labels. Notice that Haskell uses the notation v!k for our mathematical notation v[k].

3.

The sibling item of the marked item is a leaf (a left child by the way). This means that v[k -1] is even.

In this case (k is even, v[k] is even and v[k -1] is even) one inserts a node and a leaf as shown by Figure 8, which corresponds in the code to:

v // [(k-1,2 * n+1),(2 * n+1,v!(k-1)),(2 * n+2,2 * n+2)]
In Haskell, the operator // updates vectors at once, it is called a bulk update. (2 * n+1,v!(k-1)) means that the left child is a new node, at index 2 * n + 1, which points to the former value of v!(k-1). The right child is a new leaf.

The other cases (pattern1, pattern3, pattern4) correspond to cases when one of k

, v[k] or v[k -1] is odd. The update is then v // [(k,2 * n+1),(2 * n+1,v!k),(2 * n+2,2 * n+2)]
which corresponds to the first lines of Figure 8.

• case2: In this case we consider a random node-marked slanting trees of size n -2 and a random values among LR, RL, LL. For that we draw a number r between 0 and 3n -6, from which r ÷ 3 gives a random number between 0 and n-2 (a random node) and r mode 3 yields a random number among 0, 1 and 2. We notice that LR and LL correspond to the same transformation, while RL corresponds to another transformation. In each case one adds four nodes, with labels 2n -1, 2n, 2n + 1 and 2n + 2. Thus, The linearity of the algorithm depends on an oracle which should decide an inequality in constant time.

In the implementation is the plain implementation of Figure 11, the complexity of the algorithm rMt is not asymptotically linear, due to computations on big numbers. However the inequality rand < (2n+1)M n-1

(n+2)Mn
of the oracle can be approximated by a precomputed table which I call ratioM (of actual size 10004 in my case), and which is used in the oracle in Figure 12. For sizes larger that this bound, I take just the value 0.66666666667, which is a good approximation, since the fraction goes down to the limit 2 3 . The actual implementation runs up to size 9 × 10 6 and never requires (in the benchmarks) more than 10 digits of precision (see next section). But despite the asymptotic linearity is not guaranteed, the algorithm is linear in practice.

For a better efficiency, the program rMt can run without recursive calls. In this case, the stack of the calls is first computed and the construction of the vector is performed by popping the stack. I wrote a Python program, which generates random Motzkin trees of size 9 millions in less that 50 seconds on a laptop. In all the benchmarks, I checked that the difference between the drawn rand and the fraction is always larger than 10 -10 . Hence, digits that are not 6 are never checked, which shows that the oracle called oracleRatioM corresponds to the oracle called oracleMotzkin in this size interval [0 .. 9 × 10 6 ] and runs in constant time.

Schr öder trees

In this section, I define Schröder trees and a proof by bijection of the holonomic equation for defining numbers that count Schröder trees, aka Schröder numbers or Schröder-Hipparchus numbers. This proof is the translation for Knuth's definition of Schröder trees of this due to Foata and Zeilberger [START_REF] Foata | A classic proof of a recurrence for a very classical sequence[END_REF]. From this proof I derive a quasi linear algorithm for random generation of Schröder trees.

Definition of Schr öder trees

We take the definition of Knuth [START_REF] Knuth | The Art of Computer Programming[END_REF] § 7.2.1.6 (pp. 41): "A Schröder tree is a binary tree in which every nonnull right link is colored either white or black". We represent black links with and white links with . But unlike Knuth, we follow Foata and Zeilberger [START_REF] Foata | A classic proof of a recurrence for a very classical sequence[END_REF] and we say that a Schröder tree has size n if it has n leaves, hence n -1 nodes. For instance, Schröder trees with 4 leaves are given in Figure 13. Schröder trees are counted by numbers S n , which form the sequence A001003 in the online encyclopedia of integer sequences [START_REF]The on-line encyclopedia of integer sequences[END_REF] and which fulfill the holonomic equations:

(n + 1)S n+1 -3(2n -1)S n + (n -2)S n-1 = 0 that we will use on the form

(n + 1)S n+1 = 3(2n -1)S n -(n -2)S n-1
Notice that Foata and Zeilberger [START_REF] Foata | A classic proof of a recurrence for a very classical sequence[END_REF] use for the constructive proof:

3(2n -1)S n = (n + 1)S n+1 + (n -2)S n-1 (1)
Schröder trees count also ordinary trees with n leaves and no node of degree one. One "shrinks" the white edges, merging the nodes that they connects (see [START_REF] Knuth | The Art of Computer Programming[END_REF] Exercise 66). For trees with 4 leaves, the reader can see the bijection in the lines of Figure 13 and in the odd lines of Figure 14. Trees in correspondence are on the same row. Schröder numbers count also partitions of polygons [START_REF] Etherington | Some problems of non-associative combinations[END_REF]. The bijection between ordinary trees with 4 leaves and no node of degree one and partitions of pentagons (polygons with 5 edges) is illustrated by Figure 14. First one associates with each tree a parenthesized expression in α, β, γ and δ, in this order. Then each parenthesized expression is associated with a unique partition of the pentagon. have been already named by an expression. Therefore one can associate a partition with each expression as this is presented in Figure 14. One can process the same way for hexagons, heptagons etc. Didier Arquès and Alain Giorgetti have shown that planar rooted hypergraphs with vertices only of the outer face are also counted by Schröder numbers [START_REF] Arquès | Une bijection géométrique entre une famille d'hypercartes et une famille de polygones énumérées par la série de Schröder[END_REF].

Foata and Zeilberger bijection

In identity (1):

• (2n-1)S n counts marked Schröder trees of size n, where nodes and leaves can be marked, therefore 3(2n -1)S n , counts pairs made of one of three values and of a marked Schröder tree,

• (n + 1)S n+1 counts leaf-marked Schröder trees of size n + 1,

• (n -2)S n-1 counts node-marked Schröder trees of size n -1.

In order to prove identity (1), Foata and Zeilberger build a one-to-one function which associates, with a pair of a number 0, 1 or 2 (coded by Foata and Zeilberger as L 1 , L 2 and R 1 ) and a marked Schröder tree of size n, either a leaf-marked Schröder tree of size n + 1 or a node-marked Schröder tree of size n -1.

Foata and Zeilberger bijection [START_REF] Foata | A classic proof of a recurrence for a very classical sequence[END_REF] that proves identity (1) is based on constructions similar to Rémy's insertion (Figure 1), with the difference that there are two left insertions, one that corresponds to a black link and one that corresponds to a white link (Figure 15). Due to the constraints on white links in Schröder trees, there are three patterns (Figure 16), with impossible insertion, when one tries to insert a left leaf to become a left sibling of a leaf connected with a white link. Two patterns (a and c in Figure 16) can be "recovered". The third pattern (b in in Figure 16) is shrunk toward a Schröder tree of size n -1. This will correspond to a fail in the algorithm.

Similarly there are two unreachable cases by left or right insertion. They are patterns which are the results of a right or left insertion on a leaf which are a right child by a white link.

Pierre Lescanne ▲ ⋆ ▲ ⋆ Fig. 17: Two unreachable Let us call L 1 , L 2 and R 1 the three labels. Therefore Figure 18 gives the correspondence between pairs of a label from {L 1 , L 2 , R 2 } and of a marked Schröder tree, with either a leaf-marked tree of size n + 1 or a node marked tree of size n -1.

Cases L 1 and R 1 . One inserts a leaf with a black link. This is exactly like Rémy's insertion.

Case L 2 . This case deals with a left insertion with a white right link.

First line:

The mark is on a node. The left insertion with a white right link is possible.

Second line:

The mark is on a left leaf and the right link is black. The left insertion yields a forbidden pattern (a right white link toward a leaf). But by twisting the tree and swapping the colors of the right links, one reaches the first unreachable pattern of Figure 17.

Third line:

The mark is on a left leaf and the right link is white. Then the left child is not a leaf. The left insertion is forbidden as well. Therefore by removing the left leaf one gets a node marked tree of size n -1.

Fourth line:

The mark is on a right leaf. The left insertion yields a forbidden pattern, but by swapping the colors of the right link one gets the second unreachable pattern of Figure 17.

A concrete algorithm for random generation of Schr öder trees

The program of Figure 19 presents the algorithm for random generation of Schröder trees. Like in previous cases one uses a vector (an array) of size 2n + 1. But in addition to the indices for the next nodes, one adds a boolean. This boolean says that the right link that starts from the node corresponding to this index is white. Hence each cell of the array contains a pair (k, b) where k is an index and b is a boolean. According to the constraints induced on the Schröder trees, the pair corresponding to a boolean T rue has, as a first component, an odd number, since this first component corresponds to a link to a node. Since the node is a right child, it is located at an even index. If these constraints are not fulfilled, the second component must be a F alse. Therefore in the program when she adds a pair (k, T rue) at a position m, she has to check that k is odd and m is even. In another hand, if she writes (m, (k, T rue)) for such an operation, she has to check that it is of the form (2p, (2q + 1, T rue)). This constraints is an invariant of the program. The case when Foata and Zeilberger produce a Schröder tree of size n -2 corresponds in my algorithm to a "failure", that is a "retry": the subprogram body is called with a new random generator. There are six cases. Assume one draws a number x between 0 and 6n -4 and let us call k the number x ÷ 3. The value x mod 3 discriminates among L 1 , L 2 and R 2 : 0 for L 1 , 1 for L 2 and 2 for R 1 . The cases L 1 and R 1 are easy. Assume that at the k th index the array contains (h, b). --x is a random value between 0 and 6n -4 The links are black hence the booleans are F alse.

k = x ' div ' 3 put newGenerator case x ' mod' 3 of 0 {-L1-} -> return (v // [( k,(2 * n-1,False )), (2 * n-1,(2 * n,False )), (2 * n,v!k )]) --L1 1 {-L2-} -> case odd(fst (v!k)) of True {-not a leaf -}-> return (v// [( k,(2 * n-1,False )),
L 2 and h is odd. This means that the mark is on a node. This corresponds to the code:

v// [(k,(2 * n-1,False)),(2 * n-1,(2 * n,False)),(2 * n,(fst(v!k),True))]
Clearly, 2 * n,(fst(v!k),True) fulfills the constraints (2p, (2q +1, T rue)) since fst(v!k), which we called h, is odd.

L 2 and h is even and k is odd and the second component of v!(k+1) is False: This means that the mark is on a leaf (h is even) which is a left child (k is odd) and the link that goes to the sibling leaf is black. This corresponds to the code:

v//[(k,v!(k+1)),(k+1,(2 * n-1,True)),(2 * n-1,v!k),(2 * n,(2 * n,False))]
The reader may check that the code corresponds to the picture of Figure 18, line 2. (k+1,(2 * n-1,True)) fulfills the constraints (2p, (2q + 1, T rue)) since k + 1 is even and 2n -1 is odd.

L 2 and h is even and k is odd and the other link is white and the second component of v!(k+1) is True: This corresponds to a failure, and the program loops with a new random generator.

L 2 and h is even and k is even: This means that the mark is a leaf (h is even) which is a right child. This corresponds to the code: The links are black hence the booleans are F alse.

One may notice that in the array, only values at odd indices require to carry a boolean, and this boolean is required only when the first value of the pair is odd. This suggests a better data structure which may save little space, but I did not implement it.

size time ratio 1 000 0.012s 0.024 5 000 0.031s 0.0288 10 000 0.064s 0.025 50 000 0.200s 0.0269 100 000 0.290s 0.02707 500 000

1.295s 0.027762 1 000 000 3.065s 0.027883 5 000 000 15.183s 0.0276378 10 000 000 30.738s 0.0275827 break despite in rst, the loop happens less often. In P, one breaks with probability 2 3 , in the first run of the loop, with probability 2 3 2 in the second run of the loop, with probability 2 3 3 in the third run of the loop, etc. Therefore if the cost of executing the statements of the loop is c, the total average cost of the loop is:

c ∞ ∑ i=1 2 3 i = c.

Benchmarks

Benchmarks are done on a Python program, with a while loop, which mimics the Haskell program. See Figure 20. A third column yields the ratio of number of fails over the size of the produced tree. Computations are run on a laptop with 4 Gb of memory.

Related Works

On Motzkin trees

Our work was inspired by Jean-Luc Rémy's algorithm [START_REF] Rémy | Un procédé itératif de dénombrement d'arbres binaires et son application à leur génération aléatoire[END_REF]. Laurent Alonso [START_REF] Alonso | Uniform generation of a Motzkin word[END_REF] proposed an algorithm for generating uniformly Motzkin trees. His method consists in generating the number k of binary nodes with the correct probability law; he uses then standard techniques to generate a unary-binary tree with k binary nodes among n nodes. The number of trees with k binary nodes is over-approximated by values that follow a binomial distribution: choosing k is therefore done using random generations for a binomial law and rejections. Therefore his algorithm is linear on the average, with possible but extremely rare long sequences of rejection. Dominique Gouyou-Beauchamps and Cyril Nicaud [START_REF] Gouyou | Random generation using binomial approximations[END_REF] propose a random generation for color Motzkin trees which is linear on the average and Srečko Brlek et al. [START_REF] Brlek | Non uniform random generation of generalized Motzkin paths[END_REF] propose an extension of Alonso's algorithm to generalized versions of Motzkin trees.

Axel Bacher, Olivier Bodini and Alice Jacquot [START_REF] Bacher | Efficient random sampling of binary and unarybinary trees via holonomic equations[END_REF][START_REF] Jacquot | Construction par greffes, combinatoire analytique et génération aléatoire[END_REF][START_REF] Bacher | Efficient random sampling of binary and unarybinary trees via holonomic equations[END_REF] propose an algorithm with similar ideas. Especially their Figure 2 shares similarity with our Figure 9. There "operations" G 3 , G 4 and G 5 are connected with our cases RL, LR and LL respectively. ↗ corresponds to ⋆ and ↖ corresponds to ⋆ . Like Alonso's, the algorithm they propose has a linear expected complexity, due to failures similar to those of our Schröder tree generation algorithm. Let us also mention generic Boltzmann's samplers with exact-size which apply among others to Motzkin trees [START_REF] Bendkowski | Polynomial tuning of multiparametric combinatorial samplers[END_REF][START_REF] Lescanne | Boltzmann samplers for random generation of lambda terms[END_REF] and generic algorithms [START_REF] Devroye | Simulating size-constrained Galton-Watson trees[END_REF][START_REF] Panagiotou | Exact-size sampling of enriched trees in linear time[END_REF] with linear expected complexity.

Denise and Zimmermann [START_REF] Denise | Uniform random generation of decomposable structures using floating-point arithmetic[END_REF] discuss what can be done on floating-point arithmetic when generating random structures. The authors focus on decomposable labeled structures [START_REF] Flajolet | A calculus for the random generation of labelled combinatorial structures[END_REF] and address the problem of choice (which I call oracle), with a specific section on Motzkin trees.

On Schr öder trees

After studying the random generation of Motzkin trees and reading Foata and Zeilberger paper, I started the implementation of a random generation of Schröder trees, which turns out to be of expected linear complexity. Actually Laurent Alonso, René Schott and Jean-Luc Rémy [START_REF] Alonso | Uniform generation of a Schröder tree[END_REF] proposed another linear algorithm for random generation of Schröder trees, on the same principle as Alonso's algorithm for the generation of Motzkin trees. Like this quasi-linear algorithm, it proceeds in two steps: first, it chooses randomly the number k of leaves with an adequate probability and a rejection technique, second, it generates a random Schröder tree with k leaves. In comparison, my algorithm is direct. I deal only with Schröder trees, not with Schröder trees with k leaves. I am very closed to Rémy's algorithm and to my algorithm for random generation of Motzkin trees.

Conclusion

Generating Motzkin trees and Schröder trees has many potential applications [START_REF] Donaghey | Motzkin numbers[END_REF][START_REF] Barcucci | From Motzkin to Catalan permutations[END_REF][START_REF] Alonso | Uniform generation of a Schröder tree[END_REF]. My algorithm for generation of Motzkin trees has a simple code and is linear and my algorithm for Schröder trees is direct, which means it deals only with Schröder trees. Among the possible extensions of my method which could be explored, there is the generation of extended versions of Motzkin structures like Motzkin trees with colored leaves [START_REF] Gouyou | Random generation using binomial approximations[END_REF] or Motzkin paths with k long straights [START_REF] Brlek | Non uniform random generation of generalized Motzkin paths[END_REF]. k = 1 corresponds to Motzkin paths and k = 2 to Schröder paths. On another hand, Bracucci et al. [START_REF] Barcucci | From Motzkin to Catalan permutations[END_REF] study a family of sets of permutations: M 1 , M 2 , ..., M ∞ , in which M 1 is for Motzkin permutations (that are Motzkin trees up to a bijection) and M ∞ is for Catalan permutations (that are binary trees up to a bijection) an interpolation of our method seems doable.

Deriving linear algorithms for the generation of random objects applies to other structures. Indeed the production of a holonomic function can be mechanized by the software GFUN [START_REF] Salvy | GFUN: a Maple package for the manipulation of generating and holonomic functions in one variable[END_REF]. However, for my purpose, this method has limitations, since the size of the equation can blow up as shown by Figure 3 of [START_REF] Bendkowski | On the enumeration of closures and environments with an application to random generation[END_REF] for instance.

  rbt :: Int -> Int -> Gen (Vector Int) rbt seed 0 = do put (mkStdGen seed) return( initialVector // [(0,0)]) rbt seed n = do v <-rbt seed (n-1) generator <-get let (rand, newGenerator) = randomR (0::Double,1) generator put newGenerator let x = floor (rand * fromIntegral (4 * n-3))

Fig. 3 :Fig. 4 :

 34 Fig. 3: The 9 non-intersecting chords between 4 points on a circle

Fig. 6 : 9

 69 Fig. 6: 9 Motzkin trees with 4 edges and their slanting trees

7 ⋆⋆Fig. 8 :

 78 Fig.8: Contribution of marked slanting tree of size n -1. for pattern7 marks a specific case explained in Section The lower part

Fig. 9 :

 9 Fig. 9: Contribution of node-marked slanting tree of size n -2

  rMt :: Int -> Int -> Gen (Vector Int) rMt seed 0 = do put (mkStdGen seed) return $ initialVector // [(0,1),(1,0),(2,2)] rMt seed 1 = do put (mkStdGen seed) return $ initialVector // [(0,1),(1,3),(2,0),(3,2),(4,4)] rMt seed n = do generator <-get let (rand, newGenerator) = randomR (0::Double,1) generator put newGenerator case oracle n rand of True -> case1 seed n False -> case2 seed n case1 seed n = do generator <-get let (rand, newGenerator) = randomR (0::Double,1) generator k = floor (rand * (fromIntegral (2 * n ))) v <-rMt seed (n-1) put newGenerator

Fig. 10 :

 10 Fig. 10: Haskell program for random generation of Motzkin trees

Fig. 11 :Fig. 12 :

 1112 Fig. 11: The plain oracle

Fig. 13 :

 13 Fig. 13: The 11 Schröder trees with 4 leaves.

Fig. 14 :Fig. 15 :Fig. 16 :

 141516 Fig. 14: 11 Trees having no node of degree one and 4 leaves, associated with11 partitions of pentagons

L 1

 1 corresponds in the code to Pierre Lescanne type Gen = State StdGen rst :: Int -> Int -> Gen (Vector (Int,Bool)) rst seed 0 = do put (mkStdGen seed) return ( initV // [(0,(0, False ))]) rst seed n = let g = rst seed (n-1) body generator = do v <-g let (rand, newGenerator) = randomR (0::Double,1) generator x = floor (rand * fromIntegral (6 * n-4))

( 2 *Fig. 19 :

 219 Fig. 19: Haskell program for random generation of Schröder trees.

R 2

 2 v//[(k,(2 * n-1,True)),(2 * n-1,v!k),(2 * n,(2 * n,False))] (k,(2 * n-1,True)) fulfills the constraints (2p, (2q + 1, T rue)) since k is even and 2n -1 is odd. corresponds in the code to v // [(k,(2 * n-1,False)),(2 * n-1,v!k),(2 * n,(2 * n,False))

Fig. 20 :

 20 Fig. 20: Benchmarks for Schröder trees 10.1 Ratio of failures and average linear complexity The loop in rst can be sketched by the following program P: while True: r = random.randint(0,2) if r == 0: break elif r == 1: continue else :

⋆ ▲ ▲ LR , ⋆ ▲ ▲ 3. ⋆ ⋆ 4. ▲ ▲ ⋆ ⋆ ▲ ▲ RR , ⋆ ▲ ▲ 5. ▲ ▲ ⋆ RL , ⋆ ▲ ▲ 6. ⋆ ▲ ▲ LL , ⋆ ▲ ▲7.⋆ ⋆ Fig.7: The 7 patterns of leaf-marked slanting trees n 2 , this yields a Motzkin tree t ′ of size n 1 + n 2 + 2. The slanting trees associated with t 1 t 2 have n 1 + n 2 + 4 leaves.

L 1 ⍟ ⋆ ⍟ L 2 ⋆ ▲ ▲ ⋆ ▲ ▲ ⋆ ▲ ▲ ⋆ ← → ↓↑ ▲ ⋆ ⋆ ▲ ▲ ↘ ⋆ ▲ ▲ ▲ ⋆ ▲ ⋆ ↓↑ ▲ ⋆ R 1 ⍟ ⍟ ⋆Fig.18: Foata and Zeilberger isomorphism in pictures

Acknowledgments

I thank Laurent Alonso, Maciej Bendkowski, Alain Giorgetti and Jean-Luc Rémy for interesting discussions and suggestions.