{'fraction_non_alphanumeric': 0.032868360889301215, 'fraction_numerical': 0.010718664060170306, 'mean_word_length': 4.75324056423942, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Towards Streaming Image Understanding

Embodied perception refers to the ability of an autonomous agent to perceive its environment so that it can (re)act. The responsiveness of the agent is largely governed by latency of its processing pipeline. While past work has studied the algorithmic trade-off between latency and accuracy, there has not been a clear metric to compare different methods along the Pareto optimal latency-accuracy curve. We point out a discrepancy between standard offline evaluation and real-time applications: by the time an algorithm finishes processing a particular image frame, the surrounding world has changed. To these ends, we present an approach that coherently integrates latency and accuracy into a single metric for real-time online perception, which we refer to as"streaming accuracy". The key insight behind this metric is to jointly evaluate the output of the entire perception stack at every time instant, forcing the stack to consider the amount of streaming data that should be ignored while computation is occurring. More broadly, building upon this metric, we introduce a meta-benchmark that systematically converts any image understanding task into a streaming image understanding task. We focus on the illustrative tasks of object detection and instance segmentation in urban video streams, and contribute a novel dataset with high-quality and temporally-dense annotations. Our proposed solutions and their empirical analysis demonstrate a number of surprising conclusions: (1) there exists an optimal"sweet spot"that maximizes streaming accuracy along the Pareto optimal latency-accuracy curve, (2) asynchronous tracking and future forecasting naturally emerge as internal representations that enable streaming image understanding, and (3) dynamic scheduling can be used to overcome temporal aliasing, yielding the paradoxical result that latency is sometimes minimized by sitting idle and"doing nothing".


Introduction
Embodied perception refers to the ability of an autonomous agent to perceive its environment so that it can (re)act. A crucial quantity governing the responsiveness of the agent is its reaction time. Practical applications, such as self-driving vehicles or augmented reality and virtual reality (AR/VR), may require reaction time that rivals that of humans, which is typically 200 milliseconds (ms) for visual stimuli [21]. In such settings, low-latency algorithms are imperative to ensure safe operation or enable a truly immersive experience.
Historically, the computer vision community has not particularly focused on algorithmic latency. This is one reason why a disparate set of techniques  Fig. 1. Latency is inevitable in a real-world perception system. The system takes a snapshot of the world at t1 (the car is at location A), and when the algorithm finishes processing this observation, the surrounding world has already changed at t2 (the car is now at location B, and thus there is a mismatch between prediction A and ground truth B). If we define streaming perception as a task of continuously reporting back the current state of the world, then how should one evaluate vision algorithms under such a setting? We invite the readers to watch a video on the project website that compares a standard frame-aligned visualization with our latency-aware visualization [Link].
(and conference venues) have been developed for robotic vision. Interestingly, latency has been well studied recently (e.g., fast but not necessarily state-ofthe-art accurate detectors such as [32,26,24]). But it has still been primarily explored in an offline setting. Vision-for-online-perception imposes quite different latency demands as shown in Fig. 1, because by the time an algorithm finishes processing a particular image frame -say, after 200ms -the surrounding world has changed! This forces perception to be ultimately predictive of the future. In fact, such predictive forecasting is a fundamental property of human vision (e.g., as required whenever a baseball player strikes a fast ball [29]). So we argue that streaming perception should be of interest to general computer vision researchers.
Contribution (meta-benchmark) To help explore embodied vision in a truly online streaming context, we introduce a general meta-benchmark that systematically converts any image understanding task into a streaming image understanding task. Our key insight is that streaming perception requires understanding the state of the world at all time instants -when a new frame arrives, streaming algorithms must report the state of the world even if they have not done processing the previous frame. Within this meta-benchmark, we introduce an approach to measure the real-time performance of perception systems. The approach is as simple as querying the state of the world at all time instants, and the quality of the response is measured by the original task metric. Such an approach naturally merges latency and accuracy into a single metric. Therefore, the trade-off between accuracy versus latency can now be measured quantitatively. Interestingly, our meta-benchmark naturally evaluates the perception stack as a whole.
For example, a stack may include detection, tracking, and forecasting modules. Our meta-benchmark can be used to directly compare such modular stacks to end-to-end black-box algorithms [27]. In addition, our approach addresses the issue that overall latency of concurrent systems is hard to evaluate (e.g., latency cannot be simply characterized by the runtime of a single module).
Contribution (analysis) Motivated by perception for autonomous vehicles, we instantiate our meta-benchmark on the illustrative tasks of object detection and instance segmentation in urban video streams. Accompanied with our streaming evaluation is a novel dataset with high-quality, high-frame-rate, and temporallydense annotations of urban videos. Our evaluation on these tasks demonstrates a number of surprising conclusions. (1) Streaming perception is significantly more challenging than offline perception. Standard metrics like object-detection average precision (AP) dramatically drop (from 38.0 to 6.2), indicating the need for the community to focus on such problems. (2) Decision-theoretic scheduling, asynchronous tracking, and future forecasting naturally emerge as internal representations that enable accurate streaming image understanding, recovering much of the performance drop (boosting performance to 17.8). With simulation, we can verify that infinite compute resources modestly improves performance to 20.3, implying that our conclusions are fundamental to streaming processing, no matter the hardware. (3) It is well known that perception algorithms can be tuned to trade off accuracy versus latency. Our analysis shows that there exists an optimal "sweet spot" that uniquely maximizes streaming accuracy. This provides a different perspective on such well-explored trade-offs. (4) Finally, we demonstrate the effectiveness of decision-theoretic reasoning that dynamically schedules which frame to process at what time. Our analysis reveals the paradox that latency is minimized by sometimes sitting idle and "doing nothing"! Intuitively, it is sometimes better to wait for a fresh frame rather than to begin processing one that will soon become "stale".

Related Work
Latency evaluation Latency is a well-studied subject in computer vision. One school of research focuses on reducing the FLOPS of backbone networks [19,38], while another school focuses on reducing the runtime of testing time algorithms [32,26,24]. We follow suit and create a latency-accuracy plot under our experiment setting (Fig. 2). While such a plot is suggestive of the trade-off for offline data processing (e.g., archived video footage), it fails to capture the fact that when the algorithm finishes processing, the surrounding world has already changed. Therefore, we believe that existing plots do not reveal the streaming performance of these algorithms. Aside from computational latency, prior work has also investigated algorithmic latency [28], evaluated by running algorithms on a video in the offline fashion and measuring how long the algorithm takes in the number of frames to detect an object after it appears. In comparison, our evaluation is done in the more realistic online real-time setting, and applies to any single image understanding task, instead of just object detection. Real-time evaluation There has not been much prior effort to evaluate vision algorithms in the real-time fashion in the research community. Notable exceptions include work on real-time tracking and real-time simultaneous localization and mapping (SLAM). First, the VOT2017 tracking benchmark specifically included a real-time challenge [22]. Its benchmark toolkit sends out frames at 20 FPS to participants' trackers and asks them to report back results before the next frame arrives. If the tracker fails to respond in time, the last reported result is used. This is equivalent to applying zero-order hold to trackers' outputs. In our benchmarks, we adopt a similar zero-order hold strategy, but extend it to a broader context of arbitrary image understanding tasks and allow for a more delicate interplay between detection, tracking, and forecasting. Second, the literature on real-time SLAM also considers benchmark evaluation under a "hard-enforced" real-time requirement [4,13]. Our analysis suggests that hard-enforcement is too stringent of a formulation; algorithms should be allowed to run longer than the frame rate, but should still be scored on their ability to report the state of the world (e.g., localized map) at frame rate.
Progressive and anytime algorithms There exists a body of work on progressive and anytime algorithms that can generate outputs with lower latency. Such work can be traced back to classic research on intelligent planning under resource constraints [3] and flexible computation [18], studied in the context of AI with bounded rationality [33]. Progressive processing [40] is a paradigm that splits up an algorithm into sequential modules that can be dynamically scheduled. Often, scheduling is formulated as a decision-theoretic problem under resource constraints, which can be solved in some cases with Markov decision processes (MDPs). Anytime algorithms are capable of returning a solution at any point in time [39]. Our work revisits these classic computation paradigms in the context of streaming perception, specifically demonstrating that classic visual tasks (like tracking and forecasting) naturally emerge in such bounded resource settings.

Proposed Evaluation
In the previous section, we have shown that existing latency evaluation fails to capture the streaming performance. To address this issue, here we propose a new  Fig. 3. Our proposed streaming perception evaluation. A streaming algorithm f is provided with (timestamped) observations up until the current time t and refreshes an output buffer with its latest prediction of the current state of the world. At the same time, the benchmark constantly queries the output buffer for estimates of world states. Crucially, f must consider the amount of streaming observations that should be ignored while computation is occurring. . method of evaluation. Intuitively, a streaming benchmark no longer evaluates a function, but a piece of executable code over a continuous time frame. The code has access to a sensor input buffer that stores the most recent image frame. The code is responsible for maintaining an output buffer that represents the up-todate estimate of the state of the world (e.g., a list of bounding boxes of objects in the scene). The benchmark examines this output buffer, comparing it with a ground truth stream of the actual world state (Fig. 3).

Formal definition
We model a data stream as a set of sensor observations, ground-truth world states, and timestamps, denoted respectively as {(x i , y i , t i )} T i=1 . Let f be a streaming algorithm to be evaluated. At any continuous time t, the algorithm f is provided with observations (and timestamps) that have appeared so far: We allow the algorithm f to generate an output prediction at any time. Let s j be the timestamp that indicates when a particular predictionŷ j is produced. The subscript j indexes over the N outputs generated by f over the entire stream: [all outputs by f ] (2) Note that this output stream is not synchronized with the input stream, and N has no direct relationship with T . Generally speaking, we expect algorithms to run slower than the frame rate (N < T ).
We benchmark algorithm f by comparing its most recent output at time t i to the ground-truth y i . We first compute the index of the most recent output: This is equivalent to the benchmark applying a zero-order hold for the algorithm's outputs to produce continuous estimation of the world states . Given an arbitrary single-frame loss L, the benchmark formally evaluates: [evaluation] (4) By construction, the streaming loss above can be applied to any single-frame task that computes a loss over a set of ground truth and prediction pairs.

Emergent tracking and forecasting
At first glance, "instant" evaluation may seem unreasonable: the benchmark at time t queries the state at time t. Although x t is made available to the algorithm, any finite-time algorithm cannot make use of it to generate its prediction. For example, if the algorithm takes time ∆t to perform its computation, then to make a prediction at time t, it can only use data before time t − ∆t. We argue that this is the realistic setting for streaming perception, both in biological and robotic systems. Humans and autonomous vehicles must react to the instantaneous state of the world when interacting with dynamic scenes. Such requirements strongly suggest that perception should be inherently predictive of the future. Our benchmark similarly "forces" algorithms to reason and forecast into the future, to compensate for the mismatch between the last processed observation and the present. One may also wish to take into account the inference time of downstream actuation modules (that say, need to optimize a motion plan that will be executed given the perceived state of the world). It is straightforward to extend our benchmark to require algorithms to generate a forecast of the world state when the downstream module finishes its processing. For example, at time t the benchmark queries the state of the world at time t + η, where η > 0 represents the inference time of the downstream actuation module.
In order to forecast, the algorithms need to reason temporally through tracking (in the case of object detection). For example, constant velocity forecasting requires the tracks of each object over time in order to compute the velocity. Generally, there are two categories of trackers -post-hoc association and templatebased visual tracking. In this paper, we refer them in short as "association" and "tracking", respectively. Association of previously computed detections can be made extremely lightweight with simple linking of bounding boxes (e.g., based on the overlap). However, association does not make use of the image itself as done in (visual) tracking. We posit that trackers may produce better streaming accuracy for scenes with highly unpredictable motion. As part of emergent solutions to our streaming perception problem, we include both association and tracking in our experiments in the next section.
Finally, it is natural to seek out an end-to-end system that directly optimizes streaming perception accuracy. We include one such method in Appendix C.2 to show that tracking and forecasting-based representations may also emerge from gradient-based learning.  Because our metric is runtime dependent, we need to specify the computational constraints to enable a fair comparison between algorithms. We first investigate a single GPU model (Fig. 4a), which is used for existing latency analysis in prior art. In the single GPU model, only a single GPU job (e.g., detection or visual tracking) can run at a time. Such a restriction avoids multi-job interference and memory capacity issues. Note that a reasonable number of CPU jobs are allowed to run concurrently with the GPU job. For example, we allow bounding box association and forecasting modules to run on the CPU in Fig. 7.

Computational constraints
Nowadays, it is common to have multiple GPUs in a single system. We investigate an infinite GPU model (Fig. 4b), with no restriction on the number of GPU jobs that can run concurrently. We implement this infinite computation model with simulation, described in the next subsection.

Challenges for practical implementation
While our benchmark is conceptually simple, there are several practical hurdles. First, we require high-frame-rate ground truth annotations. However, due to high annotation cost, most existing video datasets are annotated at rather sparse frame rates. For example, YouTube-VIS is annotated at 6 FPS, while the video data rate is 30 FPS [37]. Second, our evaluation is hardware dependent -the same algorithm on different hardware may yield different streaming performance. Third, stochasticity in actual runtimes yields stochasticity in the streaming performance. Note that the last two issues are also prevalent in existing offline runtime analyses. Here we present high-level ideas for the solutions and leave additional details to Appendix A.1 & A.2.
Pseudo ground truth We explore the use of pseudo ground truth labels as a surrogate to manual high-frame-rate annotations. The pseudo labels are obtained by running state-of-the-art, arbitrarily expensive offline algorithms on each frame of a benchmark video. While the absolute performance numbers (when benchmarked on ground truth and pseudo ground truth labels) differ, we find that the rankings of algorithms are remarkably stable. The Pearson correlation coefficient of the scores of the two ground truth sets is 0.9925, suggesting that the real score is literally a linear function of the pseudo score. Moreover, we find that offline pseudo ground truth could also be used to self-supervise the training of streaming algorithms.
Simulation While streaming performance is hardware dependent, we now demonstrate that the benchmark can be evaluated on simulated hardware. In simulation, the benchmark assigns a runtime to each module of the algorithm, instead of measuring the wall-clock time. Then based on the assigned runtime, the simulator generates the corresponding output timestamps. The assigned runtime to each module provides a layer of abstraction on the hardware.
The benefit of simulation is to allow us to assess the algorithm performance on non-existent hardware, e.g., a future GPU that is 20% faster or infinite GPUs in a single system. Simulation also allows our benchmark to inform practitioners about computation platforms necessary to obtain a certain level of accuracy.
Runtime-induced variance Due to algorithmic choice and system scheduling, different runs of the same algorithm may end up with different runtimes. This variation across runs also affects the overall streaming performance. Fortunately, we empirically find that such variance causes a standard deviation of up to 0.5% under our experiment setting. Therefore, we omit variance report in our experiments.

Solutions and Analysis
In this section, we instantiate our meta-benchmark on the illustrative task of object detection. While we show results on streaming detection, several key ideas also generalize to other tasks. An instantiation on instance segmentation can be found in Appendix A.5. We first explain the setup and present the solutions and analysis. For the solutions, we first consider single-frame detectors, and then add forecasting and tracking one by one into the discussion. We focus on the most effective combination of detectors, trackers, and forecasters which we have evaluated, but include additional methods in Appendix C.

Setup
We extend the publicly available video dataset ArgoVerse 1.1 [6] with our own annotations for streaming evaluation, which we name ArgoVerse-HD (High-framerate Detection). It contains diverse urban outdoor scenes from two US cities. We select ArgoVerse for its embodied setting (autonomous driving) and its highframe-rate senor data (30 FPS). We focus on the task of 2D object detection for our streaming evaluation. Under this setting, the state of the world y t is a list of bounding boxes of the objects of interest. While ArgoVerse has multiple sensors, we only use the center RGB camera for simplicity. We collect our own annotations since the dataset does not provide dense 2D annotations 1  annotations, we follow MS COCO [25] class definitions and format. For example, we include the "iscrowd" attribute for ambiguous cases where each instance cannot be identified, and therefore the algorithms will not be wrongfully penalized. We use only a subset of 8 classes (from 80 MS COCO classes) that are directly relevant to autonomous driving: person, bicycle, car, motorcycle, bus, truck, traffic light, and stop sign. This definition allows us to evaluate off-the-shelf models trained on MS COCO. No training is involved in the following experiments unless otherwise specified. All numbers are computed on the validation set, which contains 24 videos ranging from 15-30 seconds each (the total number of frames is 15k). Figure 5 shows a comparison of our annotation with that of MS COCO. Additional comparison with other related datasets can be found in Appendix A.3. All output timing is measured on a single Geforce GTX 1080 Ti GPU (a Tesla V100 counterpart is provided in Appendix A.6). Table 1 includes the main results of using just detectors for streaming perception. We first examine the case of running a state-of-the-art detector -Hybrid Task Cascade (HTC) [7], both in the offline and the streaming settings. The AP drops significantly in the streaming setting. Such a result is not entirely surprising due to its high runtime (700ms). A commonly adopted strategy for real-time applications is to run a detector that is within the frame rate. We point out that Table 1. Performance of existing detectors for streaming perception. The number after @ is the input scale (the full resolution is 1920 × 1200). * means using GPU for image pre-processing as opposed to using CPU in the off-the-shelf setting. The last column is the mean runtime of the detector for a single frame in milliseconds (mask branch disabled if applicable). The first baseline is to run an accurate detector (row 1), and we observe a significant drop of AP in the online real-time setting (row 2). Another commonly adopted baseline for embodied perception is to run a fast detector (row 3-4), whose runtime is smaller than unit time interval (33ms for 30 FPS streams). Neither of these baselines achieves good performance. Searching over a wide suite of detectors and input scales, we find that the optimal solution is Mask R-CNN (ResNet 50) operating at 0.5 input scale (row 5-6). In addition, our scheduling algorithm (Alg. 1) boosts the performance by 1.0/2.3 for AP/APL (row 7). In the hypothetical infinite GPU setting, a more expensive detector yields better trade-off (input scale switching from 0.5 to 0.75, almost doubling the runtime), and it further boosts the performance to 14.4 (row 8), which is the optimal solution achieved by just running the detector. Simulation suggests that 4 GPUs suffice to maximize streaming accuracy for this solution this strategy may be problematic, since such a hard-constrained time budget results in poor accuracy for challenging tasks (Table 1 row 3-4). In addition, we find that many existing network implementations are optimized for throughput rather than latency, reflecting the bias of the community for offline versus online processing! For example, image pre-processing (e.g., resizing and normalizing) is often done on CPU, where it can be pipelined with data pre-fetching. By moving it to GPU, we save 21ms in latency (for an input of size 960 × 600).

Detection-Only
In our benchmarks, it is a choice for the streaming algorithm to decide when and what to process. Figure 6 compares a straight-forward schedule with our dynamic schedule (Alg. 1). Such subtlety is the result of temporal quantization. While spatial quantization has been studied in computer vision [17], temporal quantization in the streaming setting has not been well explored (to our knowledge). Our proposed scheduling policy (Alg. 1) minimizes the temporal mismatch of the output stream and the data stream, thus increasing the overall streaming performance. Empirically, we find that it raises the AP for the detector (Table 1 row 7). We provide theoretical reasoning showing its superiority and results for a wide suite of detectors in Appendix ??. Note that Alg. 1 is by construction task agnostic (not specific to object detection). detector finishes processing the current frame before the next frame arrives. An accurate (and thus slow) detector does not process every frame due to high latency. In this example, frame 1 is skipped. Note that the goal of streaming perception is not to process every frame but to produce accurate state estimations in a timely manner.
(b) A straight-forward schedule for slow algorithms (runtime > unit time interval) is to always process the latest available frame upon the completion of the previous processing (idle-free). However, the latest available frame might be stale, and we find that it might be better to sit idle and wait (our dynamic schedule, Alg. 1). In this illustration, when the algorithm finishes processing frame 1, Alg. 1 determines that frame 2 is stale and decides to wait for frame 3 by comparing the tails τ2 and τ3.
Algorithm 1 Shrinking-tail policy 1: Given finishing time s and algorithm runtime r in the unit of frames (assuming r > 1), this policy returns whether the algorithm should wait for the next frame 2: Define tail function

Forecasting
Now we expand our solution space to include forecasting methods. We experimented with both constant velocity models and first-order Kalman filters. We find good performance with the latter, given a small modification to handle asynchronous sensor measurements (Fig. 7). The classic Kalman filter [20] operates on uniform time steps, coupling prediction and correction updates at each step. In our case, we perform correction updates only when a sensor measurement is available, but predict at every step. Second, due to frame-skipping, the Kalman filter should be time-varying (the transition and the process noise depend on the length of the time interval, details can be found in Appendix B.2). Association for bounding boxes across frames is required to update the Kalman filter, and we apply IoU-based greedy matching. For association and forecasting, the computation involves only bounding box coordinates and therefore is very lightweight (< 2ms on CPU). We find that such overhead has little influence on the overall AP. The results are summarized in Table 2.
Streamer (meta-detector) Note that our dynamic scheduler (Alg. 1) and asynchronous Kalman forecaster can be applied to any off-the-shelf detector, regardless of its underlying latency (or accuracy). This means that we can assemble these modules into a meta-detector -which we call Streamer -that converts any detector into a streaming detection system that reports real-time . Scheduling for association and forecasting. Association takes place immediately after a new detection result becomes available, and it links the bounding boxes in two consecutive detection results. Forecasting takes place right before the next time step and it uses an asynchronous Kalman filter to produce an output as the estimation of the current world state. By default, the prediction step also updates internal states in the Kalman filter and is always called before the update step. In our case, we perform multiple update-free predictions (green blocks) until we receive a frame result. Table 2. Streaming perception with joint detection, association, and forecasting. Association is done by IoU-based greedy matching, while forecasting is done by an asynchronous Kalman filter. First, we observe that forecasting greatly boosts the performance (from Table 1  detections at an arbitrary framerate. Appendix B.4 evaluates the improvement in streaming AP across 80 different settings (8 detectors × 5 image scales × 2 compute models), which vary from 4% to 80% with an average improvement of 33%.

Visual tracking
Visual tracking is an alternative for low-latency inference, due to its faster speed than a detector. For our experiments, we adopt the state-of-the-art multi-object tracker [1] (which is second place in the MOT'19 challenge [10] and is open sourced), and modify it to only track previously identified objects. This tracker is built upon a two-stage detector and for our experiment, we try out the configurations of Mask R-CNN with different backbones and with different input scales. Also, we need a scheduling scheme for this detection plus tracking setting. For simplicity, we only explored running detection at fixed strides of 2, 5, 15, and 30. For example, stride 30 means that we run the detector once and then run the tracker 29 times, with the tracker getting reset after each new detection. Table 3 row 1 contains the best configuration over backbone, input scale, and detection stride. Table 3. Streaming perception with joint detection, visual tracking, and forecasting. We see that initially visual trackers do not outperform simple association (

Discussion
Streaming perception remains a challenge Our analysis suggests that streaming perception involves careful integration of detection, tracking, forecasting, and dynamic scheduling. While we present several strong solutions for streaming perception, the gap between the streaming performance and the offline performance remains significant (20.3 versus 38.0 in AP). This suggests that there is considerable room for improvement by building a better detector, tracker, forecaster, or even an end-to-end model that blurs boundary of these modules.
Formulations of real-time computation Common folk wisdom for real-time applications like online detection requires that detectors run within the sensor frame rate. Indeed, classic formulations of anytime processing require algorithms to satisfy a "contract" that they will finish under a compute budget [39]. Our analysis suggests that this view of computation might be too myopic as evidenced by contemporary robotic systems [31]. Instead, we argue that the sensor rate and compute budget should be seen as design choices that can be tuned to optimize a downstream task. Our streaming benchmark allows for such a global perspective.
Generalization to other tasks By construction, our meta-benchmark and dynamic scheduler (Alg. 1) are not restricted to object detection. We illustrate such generalization with an additional task of instance segmentation (Fig. 9). However, there are several practical concerns that need to be addressed. Densely annotating video frames for instance segmentation is almost prohibitively expensive. Therefore, we adopt offline pseudo ground truth (Section 3.4) to evaluate streaming performance. Another concern is that the forecasting module is taskspecific. In the case of instance segmentation, we implement it as forecasting the bounding boxes and then warping the masks accordingly. Please refer to Appendix A.5 for the complete streaming instance segmentation benchmark.

Conclusion and Future Work
We introduce a meta-benchmark for systematically converting any image understanding task into a streaming perception task that naturally trades off computation between multiple modules (e.g., detection versus tracking). We instantiate this meta-benchmark on tasks of object detection and instance segmentation. In general, we find online perception to be dramatically more challenging than its offline counterpart, though significant performance can be recovered by incorporating forecasting. We use our analysis to develop a simple meta-detector that converts any detector (with any internal latency) into a streaming perception system that can operate at any frame rate dictated by a downstream task (such as a motion planner). We hope that our analysis will lead to future endeavor in this under-explored but crucial aspect of real-time embodied perception. There is an additional family of algorithms which can be evaluated by our meta-benchmark, but is not explored in this work -attentional processing. By spending more compute only on spatially [15] or temporally [30] challenging segments, attentional processing has the potential to achieve better efficiencyaccuracy tradeoff. We leave this as future work.
Acknowledgements: This work was supported by the CMU Argo AI Center for Autonomous Vehicle Research. Annotations for ArgoVerse-HD were provided by Scale AI. We summary the contents of the appendix as follows. Appendix A describes additional details of our meta-benchmark, including pseudo ground-truth, simulation, dataset and instantiations for novel hardware and task. Appendix B provides additional details of our proposed solutions, including scheduling, tracking and forecasting. Finally, Appendix C includes additional baselines for a more thorough evaluation.

A.1 Pseudo Ground Truth
We adopt the state-of-the-art detector -Hybrid Task Cascade (HTC) [7] for computing the offline pseudo ground truth. As shown in Table 1, this detector performs reasonably well in the offline setting. Also, the offline performance has a considerable gap with methods in the real-time streaming setting. As shown in the main text, the evaluation of the same set of methods with both real and pseudo ground truth has results with a linear correlation of 0.9925. Therefore, our pseudo ground truth can be used to rank streaming perception algorithms. Note that since we have annotated the bounding boxes, we use real ground truth for evaluating detection performance. We use pseudo ground truth for instance segmentation evaluation, where the annotation is much more expensive (Section A.5).

A.2 Simulation
In a real benchmark run, the output timestamp s j is simply the wall-clock time when the algorithm produces the output. In simulation, the output timestamp is computed from runtimes of different modules. For example, if we run a singleframe detector on a single GPU, the output timestamp equals the time when it starts processing this frame plus runtime of the detector. Note that for complicated perception systems, we need to consider runtimes of all different modules (if it is significant enough, in our case > 1 ms), in order to accurately simulate the results.
Modeling runtime distribution Existing latency analysis [32,26,24] usually reports only the mean runtime of an algorithm. However, due to algorithmic choice and system scheduling, runtime is in fact stochastic (Fig. A). Runtime can also depend on the data itself for some adaptive algorithms. If we consider a series of runtimes over a data stream, runtimes can even be correlated, e.g., a complicated scene in one frame may imply a high chance of having a complicated scene in the following frames. Therefore, we need to correctly model runtime distribution as opposed to representing it as a single number. Fortunately, we found that a simple empirical distribution together with an I.I.D. assumption (Independent, Identically Distributed) on runtime works quite well for practical benchmark scenarios. We first run the algorithm over the entire dataset to get the empirical distribution of runtimes. At test time, we randomly sample a runtime when needed from the empirical distribution, without considering the correlation across time. Empirically, we found that the results (streaming AP) from a simulated run is within the variance of a real run. 5XQWLPHPV 'HQVLW\ Simulation for non-existent hardware/algorithm Through simulation, our evaluation protocol does not directly depend on hardware, but on a collection of runtime distributions for different modules (known as a runtime profile). One thus has the freedom to alter the distributions. For example, a simple manipulation is to scale runtime samples by a constant and this can model if an algorithm runs certain times faster or slower. In Table 3, we have shown the performance for a non-existent tracker that runs twice faster while maintains the same level of accuracy. Here, we show that we can even estimate the performance on non-existent hardware: assuming that we are given only a Geforce GTX 1080 Ti GPU, our goal is to estimate the performance on a Tesla V100 GPU. We find that Tesla V100 makes our detectors run 16% faster, and then we can scale all the runtime samples obtained on 1080 Ti accordingly. For Mask R-CNN R50 @ s0.5, the simulation reports back 12.652 in AP while a real run on Tesla V100 reports back 12.645, showing that the simulation is accurate enough for our purpose of evaluation.
Infinite GPUs In simulation, we are not restricted by the number of physical GPUs present in a system. Therefore, we are able to perform analysis in the infinite GPU setting. In this setting, each detector or visual tracker runs on a different device without any interference with each other. Equivalently, we run a new GPU job on an existing device as long as it is idle. As a result, the simulation also provides information on how many GPUs are required for a particular infinite GPU experiment in practice (i.e., the maximum number of concurrent jobs). We summarize the number of GPUs required for the experiments in the main text in Table A. Runtime-induced variance As mentioned in the previous section, runtime is stochastic and has a variance up to 11.1% (standard deviation normalized by mean). Fortunately, such a variance does not transfer to the variance of our streaming metric. Empirically, we found that the variance of streaming AP of different runs is around 0.5% for the same algorithm. In comparison, independent training runs of Mask R-CNN [17] on MS COCO [25] with the same random seed yield a variance of 0.3% on the AP (cudnn back-propagation is stochastic by default) [23]. Also, our simulated runs have a variance (by varying the random seed) of 0.5%. Such a low variance is because the score is computed over the entire dataset instead of each frame. Since the stochastic noise in our evaluation is at the same level as CNN training, we can safely ignore runtime-induced variance for our evaluation.

A.3 Dataset Annotation and Comparison
Based on the publicly available video dataset ArgoVerse 1.1 [6], we build our dataset with high-frame-rate annotations for streaming evaluation -ArgoVerse-HD (High-frame-rate Detection). One key feature is that the annotation follows MS COCO [25] standards, thus allowing direct evaluation of COCO pre-trained models on this self-driving vehicle dataset. The annotation is done at 30 FPS without any interpolation used. Unlike some self-driving vehicle datasets where only cars on the road are annotated [35], we also annotate background objects since they can potentially enter the drivable area. Of course, objects that are too small are omitted and our minimum size is 5 × 15 or 15 × 5 (based on the aspect ratio of the object). We outsourced the annotation job to Scale AI. In Table B

A.4 Experiment Settings
Platforms The CPU used in our experiments is Xeon Gold 5120, and the GPU is Geforce GTX 1080 Ti. The software environment is PyTorch 1.1 with CUDA 10.0.
Timing The setup which we time single-frame algorithms mimics the scenario in real-world applications. The offline pipeline involves several steps: loading data from the disk, image pre-processing, neural network forward pass, and result post-processing. Our timing excludes the first step of loading data from the disk. This step is mainly for dataset-based evaluation. In actual embodied applications, data come from sensors instead of disks. This is implemented by loading the entire video to the main memory before the evaluation starts. In summary, our timing (e.g., the last column of Table 1) starts at the time when the algorithm receives the image in the main memory, and ends at the time when the results are available in the main memory (instead of in the GPU memory).

A.5 Alternate Task: Instance Segmentation
In the main text, we propose a meta-benchmark and mention that it can be instantiated with different tasks. In this section, we include full benchmark evaluation for streaming instance segmentation. Instance segmentation is a more fine-grained task than object detection. This creates challenges for streaming evaluation as annotation becomes more expensive and forecasting is not straight-forward. We address these two issues by leveraging pseudo ground truth and warping masks according to the forecasted bounding boxes.
Another issue which we observed is that off-the-shelf pipelines are usually designed for benchmark evaluation or visualization. First, similar to object detection, we adopt GPU image pre-processing by default. Second, we found that more than 90% of the time within the mask head of Mask R-CNN is spent on transforming masks from the RoI space to the image space and compressing them in a format to be recognized by the COCO evaluation toolkit. Clearly, compression can be disabled for streaming perception. We point out that mask transformation can also be disabled. In practice, masks are used to tell if a specific point or region contains the object. Instead of transforming the mask (which involves object-specific image resizing operations), we can transform the query points or regions, which is simply a linear transformation over points or control points. Therefore, our timing does not include RoI-to-image transformation or mask compression. Furthermore, this also implies that we do not pay an additional cost for masks in forecasting, since only the box coordinates are updated but the masks remain in the RoI space. For the instance segmentation benchmark, we use the same dataset and the same method HTC [7] for the pseudo ground truth as for detection, and we include 4 methods: Mask R-CNN [17] and Cascade Mask R-CNN [5] with ResNet 50 and ResNet 101 backbones. Since these are hybrid methods that produce both instance boxes and masks, we can measure the overhead of including masks as the difference between runtime with and without the mask head in Table C. We find that the average overhead is around 13%. We include the streaming evaluation in Tables D and E (with forecasting). Table D. Streaming evaluation for instance segmentation. We find that many of our observations for object detection still hold for instance segmentation: (1) AP drops significantly when moving from offline to real time, (2) the optimal "sweet spot" is not the fastest algorithm but the algorithm with runtime more than the unit frame interval, and (3) both our dynamic scheduling and infinite GPUs further boost the performance. Note that the absolute numbers might appear higher than the tables in the main text since we use pseudo ground truth here  In the main text, we propose a meta-benchmark and mention that it can be instantiated with different hardware platforms. In this section, we include full benchmark evaluation for streaming detection with Tesla V100 (a faster GPU than GTX 1080 Ti used in the main text). While our benchmark is hardware dependent, the method of evaluation generalizes across hardware platforms, and our conclusions largely hold when the hardware environment changes. We follow the same setup as in the experiments in the main text, except that we use Tesla V100 from Amazon Web Services (EC2 instance of type p3.2xlarge). We provide the results for detection, forecasting, and tracking in Tables F, G, and H, respectively. We see that the improvement due to better hardware is largely orthogonal to the algorithmic improvement proposed in the main text. Table F. Performance of detectors for streaming perception on Tesla V100 (a faster GPU than the Geforce GTX 1080 Ti used in the main text). By comparing with Table 1 in the main text, we see that runtime is shortened and the AP is increased due to the boost of hardware performance. Different from Table 1, we only consider GPU image pre-processing here for simplicity. Interestingly, with additional computation power, Tesla V100 enables more expensive models like input scale 0.75 (row 4) and Cascade Mask R-CNN (row 5) to be the optimal configurations (detector and scale) under their corresponding settings. Note that the improvement from our dynamic scheduler is orthogonal to the boost from hardware performance  Table G. Streaming perception with joint detection, association, and forecasting on Tesla V100 (corresponding to Table 2 in the main text). We observe similar boost as in the detection only setting (Table F). The "re-optimize detection" step finds that Mask R-CNN R50 @ s1.0 outperforms Cascade Mask R-CNN R50 @ s0.5 with forecasting (row2), and it also happens to be the optimal detector with infinite GPUs (row 3) ID Method AP APL APM APS AP50 AP75 In the main text, we propose the dynamic scheduling algorithm (Alg. 1) to reduce temporal aliasing. Such an algorithm is counter-intuitive in that minimizes latency by sometimes sitting idle. Here, we provide a theoretical analysis over why it is optimal, and then empirically show that it boosts the AP for a large suite of detectors.
Theoretical Analysis for Scheduling Single-Frame Algorithms Alg. 1 applies single-frame algorithms to streaming perception assuming no concurrency (i.e., a single job at a time). To simplify notation, we assume a fixed input frame rate where frame x i is the frame available at time i ∈ {0, . . . , T − 1} (using zero-based indexing here). Let g be a single-frame algorithm, and the input frame index (or simply input index) k j be the input frame that was processed to generate output o j = (ŷ j , s j ): ifŷ j = g(x i ), then k j = i. Definition (Temporal Mismatch) When the benchmark queries the state of the world for frame i, the temporal mismatch is δ i := i − k j , where j = arg max j s j ≤ i. If there is no output available, δ i := 0.
Temporal mismatch for single-frame algorithms. Take t = 3 as an example (highlighted in orange): when the benchmark queries for y3, the latest prediction is g(x0), whose input index is 0, thus leading to a temporal mismatch of 3 (frames).
Intuitively, the temporal mismatch measures the latency of the algorithm in the unit of the number of frames. For example, if a single-frame algorithm takes 3 frames to process, then the average temporal mismatch is 3. Figure B shows an example of how to compute the temporal mismatch. This mismatch can actually be minimized through proper scheduling. Note that if an algorithm always has runtime smaller than the duration of one frame, no schedule can reduce the mismatch, which is on average 1. Therefore, for the following reasoning, we assume that runtime r for algorithm g is greater than 1 (r is represented in the units of the number of frames). Definition (Scheduling Policy) A scheduling policy is a Boolean-valued function: (t, r) → B, where t is the current time and r is runtime of algorithm g. The policy function is called when algorithm g finishes processing a frame, and if the policy function returns true, algorithm g will wait for the next frame and otherwise, continue to process the latest available frame.
Under the above definition, idle-free is a policy that always returns false. Idlefree is the commonly adopted approach for asynchronous processing. However, we will show shortly that it is actually suboptimal. For simplicity, we assume that runtime r is constant. In addition, we assume that under all policies, algorithm g starts processing the first frame immediately at t = 0. This avoids the degenerate case where algorithm processes nothing and yields a zero overall temporal mismatch. Note that our discussion is based upon this concept of tail from Alg. 1: τ (t) = t − t . We first observe a special type of execution block: Definition (Shrinking-Tail Block) Denoting the start and end time of an execution block as t 1 and t 2 , a shrinking-tail block is an execution block such that τ (t 1 ) > τ (t 2 ). The most important observation is that waiting yields less temporal mismatch when the next block is tail-shrinking if one does not wait. Let the tails of the start and end time of the two execution blocks of "waiting is set to false or true" be τ 1 , τ 2 , τ 3 , and τ 4 respectively (Fig. C). By definition, τ 3 = 0 and τ 4 = τ (r). We observe that (1 − τ 1 ) + τ 2 = τ (r). The two decisions yield the same output until before t 0 + 4, where waiting has one less mismatch than no waiting. No waiting is leading in terms of finishing time (τ 2 and τ 4 ), but τ 4 − τ 2 = 1 − τ 1 < 1. Balancing the gain and loss, we see that waiting is more advantageous if the next block shrinks the tail when not to wait. Therefore, our shrinking-tail policy (Alg. 1) can be interpreted as idle-free without shrinkingtail blocks and thus outperforms idle-free in most of the cases.
Practical Performance of Dynamic Scheduling We apply our dynamic schedule (Alg. 1) to a wide suite of detectors under the same settings as our main experiments and summarize the results in Table I. We see that the improvement generalizes to most of the cases. Table I. Empirical performance comparison before and after using Alg. 1. We see that our shrinking-tail policy consistently boosts the streaming performance for different detectors and for different input scales. We also observe some failure cases (last two rows), where runtime is close to one frame duration. This is because our theoretical analysis assumes constant runtime, while it is dynamic in practice. Hence, the variance in runtime when it is a boundary value can make a noticeable difference on the performance Method AP (Before) AP (After) Runtime (ms) Runtime (frames) SSD @ s0.5 9.7 9.7 66.7 2.0 RetinaNet R50 @ s0. 5 10.9 11.6 54.5 1.6 RetinaNet R101 @ s0.5 9.9 9.9 66.8 2.0 Mask R-CNN R101 @ s0. 5 11.0 11.1 68.  [2], which assumes that the area (the product of the width and the height) varies linearly instead of that each of the width and the height varies linearly. We find that such a representation produces lower numbers in AP. As explained in the main text, Kalman filter needs to be asynchronous and time-varying for streaming perception. Let ∆t k be the time-varying intervals between updates or prediction steps, we pick the transition matrix to be: and the process noise to be Intuitively, the process noise is larger the longer the between the updates. All forecasting modules are implemented on the CPU and thus can be parallelized while the detector runs on the GPU. Our batched (over multiple objects) implementation of the asynchronous Kalman filter takes 0.98 ± 0.39ms for the update step and 0.22 ± 0.07ms for the prediction step, which are relatively very small overheads compared to detector runtimes. For scalable evaluation, we assume zero runtime for the association and forecasting module, and implement forecasting as post-processing of the detection outputs. One might wonder that a simulated post-processing run and an actual real-time parallel execution might have different final APs. We have also implemented the latter for verification purposes. For most settings the differences are within 1%. Although for some settings the difference can reach 3%, we find such fluctuation does not affect the relative rankings.  Multi-object visual tracker. The advantage of a visual tracker is that it runs faster than a detector and thus yields lower latency for streaming perception. The multi-object tracker used here is modified from [1]. It is mostly the same as a two-stage detector, except that its box head uses the last known object location as input in place of region proposals. Therefore, we get a computation saving by not running the RPN head. Runtime is measured for Mask R-CNN (ResNet 50) with input scale 0.5.

B.3 Additional Details for Visual Tracking
For our tracking experiments (Section 4.4), we adapt and modify the state-ofthe-art multi-object tracker [1]. A component breakdown in Fig. D explains how this tracker works and why it has the potential to achieve better performance under the streaming setting.

B.4 Evaluation of Our Meta-Detector Streamer
Streamer is introduced in Section 4.3 in the main text. Given a detector and an input scale, Streamer automatically schedules the detector and employs forecasting to compensate for some of its latency. In the single GPU case, our dynamic schedule (Alg. 1) is used and in the infinite GPU case, idle-free scheduling (Fig. 4c) is used. Proper scheduling requires the knowledge of runtime of the algorithm, which is known in the case of benchmark evaluation. When applied in the wild, we can optionally track runtime of the algorithm on unseen data and adjust the scheduling accordingly. The forecasting module is implemented with asynchronous Kalman filter (Section B.2).
Streamer has several key features. First, it enables synchronous processing for an asynchronous problem. Under the commonly studied settings (both offline and online), computation is synchronous in that the outputs and the inputs have a natural one-to-one correspondence. Therefore, many existing temporal reasoning models assume that the inputs are at a uniform rate and each input corresponds to an output [11,16,14]. In the real-time setting, however, such a relationship does not exist due to the latency of the algorithm, i.e., the number of outputs can be arbitrary. Streamer converts detectors with arbitrary runtimes into systems that output at a designated fixed rate. In short, it abstracts away the asynchronous nature of the problem and therefore allows downstream synchronous processing. Second, by adopting forecasting, Streamer significantly boosts the performance of streaming perception. In Tables J and K, we evaluate the detection AP before and after applying our meta-detector. We observe relative improvement from 4% to 80% with an average of 33% in detection AP under 80 different settings (8 detectors × 5 image scales × 2 compute models). Note that the difference of this evaluation and benchmark evaluation in the main text is that we fix the detector and input scale here, while benchmark evaluation searches over the best configuration of detectors and input scales. For the infinite GPU settings, we discount the boost from additional compute itself. Table J. Performance boost after applying Streamer. "(B)" standards for "Before", and "(A)" standards for "After". The evaluation setting is the same as Table 1 in the main text. This table assumes a single GPU, and an infinite GPU counterpart can be found in Table K. Under this setting, we observe significant improvement in AP, ranging from 5% to 78%, and averaging at 34%  Table K. Performance boost after applying Streamer. "(B)" standards for "Before", and "(A)" standards for "After". The evaluation setting is the same as Table 1 in the  main text. This table assumes infinite GPUs, and a single GPU counterpart can be found in Table J Fig. E. Scheduling for linear forecasting. The scheduling is similar as with the Kalman filter case in that both are asynchronous. The difference is that linear forecasting does not explicitly maintain a state representation but only stores two latest detection results. Association takes place immediately after a new detection result becomes available, and it links the bounding boxes in two consecutive detection results and computes a velocity estimate. Forecasting takes place right before the next time step, and it uses linear extrapolation to produce an output as the estimation of the current world state. The equations represent the computation for reporting to benchmark query at t = 4. b is a simplified representation for object location. At this time, only detection results for frame 0 and 1 are available, but through association and forecasting, the algorithm can make a better prediction for the current world state.
Potentially better implementation We acknowledge that there are additional bells and whistles to reduce runtime of object detectors, which might further improve the results on our benchmark. We focus on general techniques instead of device-or application-specific ones. For example, we have explored GPU image pre-processing, which is applicable to all GPUs. Another implementation technique is to use half-precision floating-point numbers (FP16), which we have not explored, since it will only pay off for certain GPUs that have been optimized for FP16 computation (it is reported that FP16 yields only marginal testing time speed boost on 1080 Ti [9]).

C.1 Forecasting Baselines
We have also tested linear extrapolation (i.e., constant velocity) and quadratic extrapolation for forecasting detection results. We include an illustration of linear forecasting in Fig. E, and the quadratic counterpart is a straight-forward extension that involves three latest detection results. Though they produce inferior results than Kalman filter, we include the results in Table L for completeness.

C.2 An End-to-End Baseline
In the main text, we break down the streaming detection task into detection, tracking, and forecasting for modular analysis. Alternatively, it is also possible to train a model that directly outputs detection results in the future. F2F [27] is one such model. Building upon Mask R-CNN, it does temporal reasoning and forecasting at the level of FPN feature maps. Note that no explicit tracking is performed. In this section, we compare against this end-to-end baseline in both offline and streaming settings.
In the offline setting, the algorithm is given s frames as input history, and outputs detection results for t frames ahead. This is the same as the evaluation in [27]. We set both s and t to be 3, as the optimal detector in our forecasting experiments ( Table 2) has runtime of 2.78 frames. Since F2F forecasts at the FPN feature level, it is agnostic to second stage tasks. In our evaluation, we focus on the bounding box detection task instead of instance segmentation. Also, we conduct experiments on ArgoVerse-HD, consistent with the setting in our other experiments. Due to a lack of annotation, we adopt pseudo ground truth (Section A.1) for training (data from the original training set of ArgoVerse 1.1 [6]). We implement our own version of F2F based on mmdetection (instead of Detectron as done in [27]). We train the model for 12 epochs end-to-end (a 50% longer schedule than combined stages in [27]). For a fair comparison, we also finetuned the detectors on ArgoVerse with the same pseudo ground truth. For Mask R-CNN ResNet 50 at scale 0.5, it boosts the offline box AP from 19.4 to 22.9. We use this finetuned detector in our method to compare against F2F. The results are summarized in Table M. We see that an end-to-end solution does not immediately boost the performance. We believe that it is still an open prob- lem on how to effectively replace tracking and forecasting with an end-to-end solution.
In the streaming setting, F2F can be viewed as a detector that compensates its own latency. The results are summarized in Table N. We see that F2F is too expensive compared with other streaming solutions, showing that forecasting can help only if it is fast under our evaluation. Note that the detectors (row 1-2) are not finetuned as in the offline case, which means that they can be further improved. Table N. Streaming evaluation for the end-to-end method F2F [27]. The setting is the same as the experiments in the main text. Rows 1 and 2 are the optimized detector and the Kalman filter forecasting solution from the main text. The underlying detectors used are Mask R-CNN ResNet 50 at scale 0.5 and scale 0.75 respectively. Row 3 suggests that F2F has a low streaming AP, due to its forecasting module being very expensive (last column, runtime in milliseconds). For diagnostics purpose, we assume F2F to run as fast as our optimized detector (row 4), and arm it with our scheduling algorithm (row 5